Abstract
This paper presents an algorithm for discovering pairs of an exception rule and a common sense rule under a prespecified schedule. An exception rule, which represents a regularity of exceptions to a common sense rule, often exhibits interestingness. Discovery of pairs of an exception rule and a common sense rule has been successful in various domains. In this method, however, both the number of discovered rules and time needed for discovery depend on the values of thresholds, and an appropriate choice of them requires expertise on the data set and on the discovery algorithm. In order to circumvent this problem, we propose two scheduling policies for updating values of these thresholds based on a novel data structure. The data structure consists of multiple balanced search-trees, and efficiently manages discovered patterns with multiple indices. One of the policies represents a full specification of up-dating by the user, and the other iteratively improves a threshold value by deleting the worst pattern with respect to its corresponding index. Preliminary results on four real-world data sets are highly promising. Our algorithm settled values of thresholds appropriately, and discovered interesting exception-rules from all these data sets.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Y. Dimopoulos and A. Kakas: “Learning Non-Monotonic Logic Programs: Learning Exceptions”, Machine Learning: ECML-95, LNAI 912, Springer-Verlag, Berlin, pp. 122–137 (1995).
J. Dougherty, R. Kohavi and M. Sahami: “Supervised and Unsupervised Discretization of Continuous Features”, Proc. Twelfth Int’l Conf. Machine Learning, Morgan Kaufmann, San Francisco, pp. 194–202 (1995).
N. Inoue et al.: “Regional Questionnaire Survey on the 1995 Hyogo-ken Nambu Earthquake”, Zisin, Vol. 51, No. 4, pp. 395–407 (in Japanese, 1999).
C.J. Merz and P.M. Murphy: “UCI Repository of Machine Learning Databases”, http://www.ics.uci.edu/~mlearn/MLRepository.html, Dept. of Information and Computer Sci., Univ. of California Irvine (1996).
B. Padmanabhan and A. Tuzhilin: “A Belief-Driven Method for Discovering Unexpected Patterns”, Proc. Fourth Int’l Conf. Knowledge Discovery and Data Mining, AAAI Press, Menlo Park, Calif., pp. 94–100 (1998).
P. Smyth and R.M. Goodman: “An Information Theoretic Approach to Rule Induction from Databases”, IEEE Trans. Knowledge and Data Eng., Vol. 4, No. 4, pp. 301–316 (1992).
E. Suzuki and M. Shimura: Exceptional Knowledge Discovery in Databases Based on Information Theory, Proc. Second Int’l Conf. Knowledge Discovery and Data Mining, AAAI Press, Menlo Park, Calif., pp. 275–278 (1996).
E. Suzuki: “Discovering Unexpected Exceptions: A Stochastic Approach”, Proc. Fourth Int’l Workshop Rough Sets, Fuzzy Sets, and Machine Discovery, Japanese Research Group on Rough Sets, Tokyo, pp. 225–232 (1996).
E. Suzuki: “Autonomous Discovery of Reliable Exception Rules”, Proc. Third Int’l Conf. Knowledge Discovery and Data Mining, AAAI Press, Menlo Park, Calif., pp. 259–262 (1997).
E. Suzuki and Y. Kodratoff: “Discovery of Surprising Exception Rules based on Intensity of Implication”, Principles of Data Mining and Knowledge Discovery, LNAI 1510, Springer-Verlag, Berlin, pp. 10–18 (1998).
S. Tsumoto et al.: “Comparison of Data Mining Methods using Common Medical Datasets”, ISM Symposium: Data Mining and Knowledge Discovery in Data Science, The Inst. of Statistical Math., Tokyo, pp. 63–72 (1999).
N. Wirth: Algorithms + Data Structures = Programs, Prentice-Hall, Englewood Cliffs, N.J. (1976).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Suzuki, E. (1999). Scheduled Discovery of Exception Rules. In: Arikawa, S., Furukawa, K. (eds) Discovery Science. DS 1999. Lecture Notes in Computer Science(), vol 1721. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46846-3_17
Download citation
DOI: https://doi.org/10.1007/3-540-46846-3_17
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66713-1
Online ISBN: 978-3-540-46846-2
eBook Packages: Springer Book Archive