A novel distance-based classifier built on pattern ranking

ABSTRACT

Instance-based classifiers that compute similarity between instances suffer from the presence of noise in the training set and from over-fitting. In this paper we propose a new type of distance-based classifier that instead of computing distances between instances computes the distance between each test instance and the classes. Both are represented by patterns in the space of the frequent itemsets. We ranked the itemsets by metrics of itemset significance. Then we considered only the top portion of the ranking that leads the classifier to reach the maximum accuracy. We have experimented on a large collection of datasets from UCI archive with different proximity measures and different metrics of itemsets ranking.

We show that our method has many benefits: it reduces the number of distance computations, improves the classification accuracy of state-of-the art classifiers, like decision trees, SVM, k-nn, Naive Bayes, rule-based classifiers and association rule-based ones and outperforms the competitors especially on noise data.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 2: David W. Aha , Dennis Kibler , Marc K. Albert, Instance-Based Learning Algorithms, Machine Learning, v.6 n.1, p.37-66, Jan. 1991 [doi>10.1023/A:1022689900470]
• 3: B. Bigi. Using K-L distance for text categorization. Advances in Information Retrieval, 2633: 76, 2003.
• 4: Hong Cheng, Xifeng Yan, Jiawei Han, and Chih-Wei Hsu. Discriminative frequent pattern analysis for effective classification. ICDE, 0: 716--725, 2007.
• 5: W. Cohen. Fast effective rule induction. Proc. Int. Conf. Machine Learning, pages 115--123, 1995.
• 6: T. M. Cover and P. E. Hart. Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13: 21--27, 1967.
• 7: Pedro Domingos, Unifying instance-based and rule-based induction, Machine Learning, v.24 n.2, p.141-168, Aug. 1996 [doi>10.1023/A:1018006431188]
• 8: Hongjian Fan , Kotagiri Ramamohanarao, Fast Discovery and the Generalization of Strong Jumping Emerging Patterns for Building Compact and Accurate Classifiers, IEEE Transactions on Knowledge and Data Engineering, v.18 n.6, p.721-737, June 2006 [doi>10.1109/TKDE.2006.95]
• 9: Usama M. Fayyad and Keki B. Irani. Multi-interval discretization of continuous valued attributes for classification learning. Proc. IJCAI'93, pp. 1022--1027.
• 10: S. S. Keerthi , S. K. Shevade , C. Bhattacharyya , K. R. K. Murthy, Improvements to Platt's SMO Algorithm for SVM Classifier Design, Neural Computation, v.13 n.3, p.637-649, March 2001 [doi>10.1162/089976601300014493]
• 11: Ron Kohavi, The Power of Decision Tables, Proceedings of the 8th European Conference on Machine Learning, p.174-189, April 25-27, 1995
• 12: S. Kullback and R. A. Leibler. On information and sufficiency. Annals of Mathematical Statistics, 22: 79--86, 1951.
• 13: 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
• 14: Bing Liu, Wynne Hsu, and Yiming Ma. Integrating classification and association rule mining. In SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pages 80--86, 1998.
• 15: Rosa Meo, Theory of dependence values, ACM Transactions on Database Systems (TODS), v.25 n.3, p.380-406, Sept. 2000 [doi>10.1145/363951.363956]
• 16: Dimitris Meretakis , Beat Wüthrich, Extending naïve Bayes classifiers using long itemsets, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.165-174, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312222]
• 17: R. F. Sproull. Refinements to nearest-neighbor searching in k-dimensional trees. Algorithmica, 6(1--6): 579--589, 1991.
• 18: T. Steinbach and Kumar. Introduction to Data Mining. Pearson education, 2006.
• 19: D. Randall Wilson , Tony R. Martinez, Reduction Techniques for Instance-BasedLearning Algorithms, Machine Learning, v.38 n.3, p.257-286, March 2000 [doi>10.1023/A:1007626913721]

INDEX TERMS

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

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

General Terms:
Algorithms, Experimentation, Reliability

Keywords:
frequent itemsets, instance-base learning