Using conjunction of attribute values for classification

ABSTRACT

Advances in the efficient discovery of frequent itemsets have led to the development of a number of schemes that use frequent itemsets to aid developing accurate and efficient classifiers. These approaches use the frequent itemsets to generate a set of composite features that expand the dimensionality of the underlying dataset. In this paper, we build upon this work and (i) present a variety of schemes for composite feature selection that achieve a substantial reduction in the number of features without adversely affecting the accuracy gains, and (ii) show (both analytically and experimentally) that the composite features can lead to improved classification models even in the context of support vector machines, in which the dimensionality can automatically be expanded by the use of appropriate kernel functions.

REFERENCES

• 1: Ramesh C. Agarwal , Charu C. Aggarwal , V. V. V. Prasad, Depth first generation of long patterns, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.108-118, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347114]
• 2: 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
• 3: Carla E. Brodley , Paul E. Utgoff, Multivariate Versus Univariate Decision Trees, University of Massachusetts, Amherst, MA, 1992
• 4: J. Dougherty, R. Kohavi, and M. Sahami. Supervised and unsupervised discretisation of continuous features. In Machine Learning: Proceedings of the Twelfth Internation Conference, 1995.
• 5: U. M. Fayyad and K. B. Irani. Multi-interval discretization of continuous-valued attributes for classification learning. In Proceedings of the 13th International Joint Conference on Artificial Intelligence, 1993.
• 6: Giulia Pagallo , David Haussler, Boolean Feature Discovery in Empirical Learning, Machine Learning, v.5 n.1, p.71-99, Mar. 1990 [doi>10.1023/A:1022611825350]
• 7: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.1-12, May 15-18, 2000, Dallas, Texas, United States
• 8: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 9: Neal Lesh , Mohammed J. Zaki , Mitsunori Ogihara, Mining features for sequence classification, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.342-346, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312275]
• 10: 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
• 11: B. Liu, W. Hsu, and Y. Ma. Integrating classification and association rule mining. In 4th Internation Conference on Knowledge Discovery and Data Mining, 1998.
• 12: C. J. Matheus and L. Rendell. Constructive induction on decision trees. In Proceedings of the Eleventh International Joint Conference on Artifical Intelligence, 1989.
• 13: C. Merz and P. Murphy. UCI repository of machine learning databases, 1998.
• 14: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 15: P. M. Murphy and M. J. Pazzani. Id2-of-3: Constructive induction of m-of-n concepts for discriminators in decision trees. In Proc. of the 8th Int ÿ Workshop on Machine Learning, 1991.
• 16: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 17: M. R. S. Pattern recognition as knowledge guided computer induction. Technical report, University of Illinois at Urbana Champaign, 1978.
• 18: Masakazu Seno , George Karypis, LPMiner: An Algorithm for Finding Frequent Itemsets Using Length-Decreasing Support Constraint, Proceedings of the 2001 IEEE International Conference on Data Mining, p.505-512, November 29-December 02, 2001
• 19: P. Smyth , R. M. Goodman, An Information Theoretic Approach to Rule Induction from Databases, IEEE Transactions on Knowledge and Data Engineering, v.4 n.4, p.301-316, August 1992 [doi>10.1109/69.149926]
• 20: V. Vapnik. Statistical Learning Theory. John Wiley, New York, 1998.
• 21: J. Weston, S. Mukherjee, O. Chapelle, M. Pontil, T. Poggio, and V. Vapnik. Feature selection fof svms. Advances in Neural Information Processing Systems, 2000.
• 22: 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]
• 23: Mohammed J. Zaki, Scalable Algorithms for Association Mining, IEEE Transactions on Knowledge and Data Engineering, v.12 n.3, p.372-390, May 2000 [doi>10.1109/69.846291]
• 24: Mohammed J. Zaki , Neal Lesh , Mitsunori Ogihara, PlanMine: Predicting Plan Failures Using Sequence Mining, Artificial Intelligence Review, v.14 n.6, p.421-446, December 1, 2000 [doi>10.1023/A:1006612804250]
• 25: Z. Zheng. Constructing conjunctive attributes using production rules. Journal of Research and Practice in Information Technology, 2000.
• 26: Z. Zijian. A comparison of constructive induction with different types of new attribute. Technical report, School of Computing and Mathematics, Deakin University, Geelong, Victoria, Australia, 1996.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning

General Terms:
Algorithms

Keywords:
SVM, association rules, classification, conjunctive attributes, feature selection