Unified algorithm for undirected discovery of exception rules
2005; Wiley; Volume: 20; Issue: 7 Linguagem: Inglês
10.1002/int.20090
ISSN1098-111X
AutoresEinoshin Suzuki, Jan M. Żytkow,
Tópico(s)Bayesian Modeling and Causal Inference
ResumoInternational Journal of Intelligent SystemsVolume 20, Issue 7 p. 673-691 Research Article Unified algorithm for undirected discovery of exception rules Einoshin Suzuki, Einoshin Suzuki [email protected] Electrical and Computer Engineering, Yokohama National University, Hodogaya, Yokohama 240-8501, JapanSearch for more papers by this authorJan M. Żytkow, Jan M. Żytkow [email protected] Computer Science Department, University of North Carolina at Charlotte, Charlotte, NC 28223, USASearch for more papers by this author Einoshin Suzuki, Einoshin Suzuki [email protected] Electrical and Computer Engineering, Yokohama National University, Hodogaya, Yokohama 240-8501, JapanSearch for more papers by this authorJan M. Żytkow, Jan M. Żytkow [email protected] Computer Science Department, University of North Carolina at Charlotte, Charlotte, NC 28223, USASearch for more papers by this author First published: 16 May 2005 https://doi.org/10.1002/int.20090Citations: 21AboutPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Abstract This article presents an algorithm that seeks every possible exception rule that violates a commonsense rule and satisfies several assumptions of simplicity. Exception rules, which represent systematic deviation from commonsense rules, are often found interesting. Discovery of pairs that consist of a commonsense rule and an exception rule, resulting from undirected search for unexpected exception rules, was successful in various domains. In the past, however, an exception rule represented a change of conclusion caused by adding an extra condition to the premise of a commonsense rule. That approach formalized only one type of exception and failed to represent other types. To provide a systematic treatment of exceptions, we categorize exception rules into 11 categories, and we propose a unified algorithm for discovering all of them. Preliminary results on 15 real-world datasets provide an empirical proof of effectiveness of our algorithm in discovering interesting knowledge. The empirical results also match our theoretical analysis of exceptions, showing that the 11 types can be partitioned in three classes according to the frequency with which they occur in data. © 2005 Wiley Periodicals, Inc. Int J Int Syst 20: 673–691, 2005. References 1 Mitchell TM. Machine learning and data mining. Commun ACM 1999; 42: 31– 36. 2 Knorr EM, Ng RT. Algorithms for mining distance-based outliers in large datasets. In: Proc 24th Annual Int Conf on Very Large Data Bases, New York, August 24–27, 1998. pp 392– 403. 3 Sarawagi S. Explaining differences in multidimensional aggregates. In: Proc 25th Int Conf on Very Large Data Bases, Edinburgh, Scotland, September 7–10, 1999. pp 42– 53. 4 Liu B, Hsu W, Chen S. Using general impressions to analyze discovered classification rules. In: Proc Third Int Conf on Knowledge Discovery and Data Mining, Newport Beach, California, August 14–17, 1997. pp 31– 36. 5 Liu B, Hsu W, Mun L-F, Lee H-Y. Finding interesting patterns using user expectations. IEEE Trans Knowl Data Eng 1999; 11: 817– 832. 6 Liu B, Hsu W, Ma Y. Pruning and summarizing the discovered associations. In: Proc Fifth ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining, San Diego, California, August 15–18, 1999. pp 125– 134. 7 Padmanabhan B, Tuzhilin A. A belief-driven method for discovering unexpected patterns. In: Proc Fourth Int Conf on Knowledge Discovery and Data Mining, New York, August 27–31, 1998. pp 94– 100. 8 Silberschatz A, Tuzhilin A. On subjective measure of interestingness in knowledge discovery. In: Proc First Int Conf on Knowledge Discovery and Data Mining, Montreal, August 20–21, 1995. pp 275– 281. 9 Silberschatz A, Tuzhilin A. What makes patterns interesting in knowledge discovery systems. IEEE Trans Knowl Data Eng 1996; 8: 970– 974. 10 Suzuki E, Shimura M. Exceptional knowledge discovery in databases based on information theory. In: Proc Second Int Conf on Knowledge Discovery and Data Mining, Portland, Oregon, August 2–4, 1996. pp 275– 278. 11 Suzuki E. Discovering unexpected exceptions: A stochastic approach. In: Proc Fourth Int Workshop on Rough Sets, Fuzzy Sets, and Machine Discovery, Tokyo, Japan, November 6–8, 1996. pp 225– 232. 12 Suzuki E. Autonomous discovery of reliable exception rules. In: Proc Third Int Conf on Knowledge Discovery and Data Mining, Newport Beach, California, August 14–17, 1997. pp 259– 262. 13 Suzuki E, Kodratoff Y. Discovery of surprising exception rules based on intensity of implication. In: JM Żytkow, M Quafafou, editors. Principles of data mining and knowledge discovery. Lecture Notes in Artificial Intelligence 1510. Berlin: Springer; 1998. pp 10– 18. 14 Suzuki E. Scheduled discovery of exception rules. In: S Arikawa, K Furukawa, editors. Discovery science. Lecture Notes in Artificial Intelligence 1721. Berlin: Springer; 1999. pp 184– 195. 15 Suzuki E. Undirected discovery of interesting exception rules. Int J Pattern Recogn Artif Intell 2002; 16: 1065– 1086. 16 Suzuki E. Evaluation scheme for exception rule/group discovery. In: N Zhong, J Liu, editors. Intelligent technologies for information analysis. Berlin: Springer; 2004. pp 89– 108. 17 Yugami N, Ohta Y, Okamoto S. Fast discovery of interesting rules. In: T Terano, H Liu, ALP Chen, editors. Knowledge discovery and data mining. Lecture Notes in Artificial Intelligence 1805. Berlin: Springer; 2000. pp 17– 28. 18 Suzuki E, Tsumoto S. Evaluating hypothesis-driven exception-rule discovery with medical data sets. In: T Terano, H Liu, ALP Chen, editors. Knowledge discovery and data mining. Lecture Notes in Artificial Intelligence 1805. Berlin: Springer; 2000. pp 86– 97. 19 Agrawal R, Mannila H, Srikant R, Toivonen H, Verkamo AI. Fast discovery of association rules. In: UM Fayyad, G Piatetsky-Shapiro, P Smyth, R Uthurusamy, editors. Advances in knowledge discovery and data mining. Menlo Park, CA: AAAI Press; 1996. pp 307– 328. 20 Blake CL, Merz CJ. UCI Repository of Machine Learning Databases. Department of Information and Computer Science, University of California Irvine; 1998. Available at http://www.ics.uci.edu/∼mlearn/MLRepository.html. 21 Suzuki E, Żytkow JM. Unified algorithm for undirected discovery of exception rules. In: DA Zighed, J Komorowski, JM Żytkow, editors. Principles of data mining and knowledge discovery. Lecture Notes in Artificial Intelligence 1910. Berlin: Springer; 2000. pp 169– 180. 22 Smyth P, Goodman RM. An information theoretic approach to rule induction from databases. IEEE Trans Knowl Data Eng 1992; 4: 301– 316. 23 Tsumoto S, Terano T, Inada M, Niimi A, Tazaki E, Negishi N, Suyama A, Yamaguti T, Tachibana Y, Dong J-Z, Zhong N, Ohsuga S, Kamiishi Y, Sugaya S, Suzuki E, Tsukada M, Inoguchi A, Washio T, Motoda H, Fukuda T, Morimoto Y, Matsuzawa H, Okada T, Oyama M, Ho TB, Nguyen TD, Nguyen NB. Comparison of data mining methods using common medical datasets. In: ISM Symp on Data Mining and Knowledge Discovery in Data Science, Tokyo, Japan, March 18–19, 1999. pp 63– 72. 24 Dougherty J, Kohavi R, Sahami M. Supervised and unsupervised discretization of continuous features. In: Proc 12th Int Conf on Machine Learning, Tahoe City, California, July 9–12, 1995. pp 194– 202. Citing Literature Volume20, Issue7Special Issue: Knowledge Discovery: Dedicated to Jan M. ŻytkowJuly 2005Pages 673-691 ReferencesRelatedInformation
Referência(s)