On support thresholds in associative classification

ABSTRACT

Associative classification is a well-known technique for structured data classification. Most previous works on associative classification use support based pruning for rule extraction, and usually set the threshold value to 1%. This threshold allows rule extraction to be tractable and on the average yields a good accuracy. We believe that this threshold may be not accurate in some cases, since the class distribution in the dataset is not taken into account. In this paper we investigate the effect of support threshold on classification accuracy. Lower support thresholds are often unfeasible with current extraction algorithms, or may cause the generation of a huge rule set. To observe the effect of varying the support threshold, we first propose a compact form to encode a complete rule set. We then develop a new classifier, named L³_G, based on the compact form. Taking advantage of the compact form, the classifier can be built also with rather low support rules. We ran a variety of experiments with different support thresholds on datasets from the UCI machine learning database repository. The experiments showed that the optimal accuracy is obtained for variable threshold values, sometime lower than 1%.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 2: Elena Baralis , Paolo Garza, A Lazy Approach to Pruning Classification Rules, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.35, December 09-12, 2002
• 3: Yves Bastide , Rafik Taouil , Nicolas Pasquier , Gerd Stumme , Lotfi Lakhal, Mining frequent patterns with counting inference, ACM SIGKDD Explorations Newsletter, v.2 n.2, p.66-75, Dec. 2000 [doi>10.1145/380995.381017]
• 4: Roberto J. Bayardo, Jr., Efficiently mining long patterns from databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.85-93, June 01-04, 1998, Seattle, Washington, United States
• 5: C. Blake and C. Merz. UCI repository of machine learning databases, 1998.
• 6: Jean-François Boulicaut , Artur Bykowski , Christophe Rigotti, Free-Sets: A Condensed Representation of Boolean Data for the Approximation of Frequency Queries, Data Mining and Knowledge Discovery, v.7 n.1, p.5-22, January 2003 [doi>10.1023/A:1021571501451]
• 7: Sergey Brin , Rajeev Motwani , Craig Silverstein, Beyond market baskets: generalizing association rules to correlations, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.265-276, May 11-15, 1997, Tucson, Arizona, United States
• 8: Artur Bykowski , Christophe Rigotti, A condensed representation to find frequent patterns, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.267-273, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375604]
• 9: B. Cremilleux and J.-F. Boulicaut. Simplest rules characterizing classes generated by delta-free sets. In ES'02.
• 10: Guozhu Dong , Xiuzhen Zhang , Limsoon Wong , Jinyan Li, CAEP: Classification by Aggregating Emerging Patterns, Proceedings of the Second International Conference on Discovery Science, p.30-42, December 01, 1999
• 11: E. Baralis and S. Chiusano. Minimal non redundant classification rule sets. IEEE ICDM Workshop on Foundations of Data Mining and Discovery, 2002.
• 12: Wenmin Li , Jiawei Han , Jian Pei, CMAR: Accurate and Efficient Classification Based on Multiple Class-Association Rules, Proceedings of the 2001 IEEE International Conference on Data Mining, p.369-376, November 29-December 02, 2001
• 13: B. Liu, W. Hsu, and Y. Ma. Integrating classification and association rule mining. In KDD'98.
• 14: Bing Liu , Yiming Ma , Ching Kian Wong, Improving an Association Rule Based Classifier, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.504-509, September 13-16, 2000
• 15: Nicolas Pasquier , Yves Bastide , Rafik Taouil , Lotfi Lakhal, Efficient mining of association rules using closed itemset lattices, Information Systems, v.24 n.1, p.25-46, March 1999 [doi>10.1016/S0306-4379(99)00003-4]
• 16: N. Pasquier, Y. Bastide, R. Taouil, and L. Lakhal. Closed itemsets discovery of small covers for association rules. In Networking and Information Systems, June 2001.
• 17: J. Pei, J. Han, and R. Mao. Closet: An efficient algorithm for mining frequent closed itemsets. In ACM SIGMOD DMKD'00.
• 18: J. Quinlan. C4.5: program for classification learning. Morgan Kaufmann, 1992.
• 19: Ke Wang , Senqiang Zhou , Yu He, Growing decision trees on support-less association rules, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.265-269, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347147]
• 20: Mohammed J. Zaki, Generating non-redundant association rules, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.34-43, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347101]
• 21: M. Zaki and C.-J. Hsiao. Charm: An efficient algorithm for closed itemset mining. In SIAM'02.