The IOC algorithm: efficient many-class non-parametric classification for high-dimensional data

ABSTRACT

This paper is about a variant of k nearest neighbor classification on large many-class high dimensional datasets.K nearest neighbor remains a popular classification technique, especially in areas such as computer vision, drug activity prediction and astrophysics. Furthermore, many more modern classifiers, such as kernel-based Bayes classifiers or the prediction phase of SVMs, require computational regimes similar to k-NN. We believe that tractable k-NN algorithms therefore continue to be important.This paper relies on the insight that even with many classes, the task of finding the majority class among the k nearest neighbors of a query need not require us to explicitly find those k nearest neighbors. This insight was previously used in (Liu et al., 2003) in two algorithms called KNS2 and KNS3 which dealt with fast classification in the case of two classes. In this paper we show how a different approach, IOC (standing for the International Olympic Committee) can apply to the case of n classes where n > 2.IOC assumes a slightly different processing of the datapoints in the neighborhood of the query. This allows it to search a set of metric trees, one for each class. During the searches it is possible to quickly prune away classes that cannot possibly be the majority.We give experimental results on datasets of up to 5.8 x 10⁵ records and 1.5 x 10³ attributes, frequently showing an order of magnitude acceleration compared with each of (i) conventional linear scan, (ii) a well-known independent SR-tree implementation of conventional k-NN and (iii) a highly optimized conventional k-NN metric tree search.

REFERENCES

• 1: David William Aha , Dennis F. Kibler, A study of instance-based algorithms for supervised learning tasks: mathematical, empirical, and psychological evaluations, 1990
• 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: Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM (JACM), v.45 n.6, p.891-923, Nov. 1998 [doi>10.1145/293347.293348]
• 4: Jock A. Blackard. Forest covertype database. http://kdd.ics.uci.edu/databases/covertype/covertype.data.html.
• 5: Paolo Ciaccia , Marco Patella , Pavel Zezula, M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Proceedings of the 23rd International Conference on Very Large Data Bases, p.426-435, August 25-29, 1997
• 6: Ron Cole and Mark Fanty. Isolet spoken letter recognition database. ftp://ftp.ics.uci.edu/pub/machine-learning-databases/isolet/.
• 7: Jerome H. Freidman , Jon Louis Bentley , Raphael Ari Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.209-226, Sept. 1977 [doi>10.1145/355744.355745]
• 8: Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
• 9: J. M. Hammersley. The Distribution of Distances in a Hypersphere. Annals of Mathematical Statistics, 21:447--452, 1950.
• 10: CMU informedia digital video library project. The trec-2001 video trackorganized by nist shot boundary task. 2001.
• 11: IOC. International olympic committee: Candidature acceptance procedure. http://multimedia.olympic.org/pdf/ en report 711.pdf, 1999.
• 12: Norio Katayama and Shin'ichi Satoh. The SR-tree: an index structure for high-dimensional nearest neighbor queries. pages 369--380, 1997.
• 13: Nicholas Kushmerick. Internet advertisements. ftp://ftp.ics.uci.edu/pub/machine-learning-databases/internet ads/.
• 14: Ting Liu, Andrew Moore, and Alexander Gray. Efficient exact k-nn and nonparametric classification in high dimensions. In Proceedings of Neural Information Processing Systems, 2003.
• 15: Andrew W. Moore, The Anchors Hierarchy: Using the Triangle Inequality to Survive High Dimensional Data, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.397-405, June 30-July 03, 2000
• 16: Stephen M. Omohundro, Bumptrees for efficient function, constraint, and classification learning, Proceedings of the 1990 conference on Advances in neural information processing systems 3, p.693-699, October 1990, Denver, Colorado, United States
• 17: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 18: Yanjun Qi, Alexander G. Hauptmann, and Ting Liu. Supervised classification for video shot segmentation. In proceedings of 2003 IEEE International Conference on Multimedia & Expo, 2003.
• 19: D. B. Skalak. Prototype and Feature Selection by Sampling and Random Mutation Hill Climbing Algorithms. In W. W. Cohen and H. Hirsh, editors, Machine Learning: Proceedings of the Eleventh International Conference. Morgan Kaufmann, 1994.
• 20: David J. Slate. Letter recognition database. ftp://ftp.ics.uci.edu/pub/machine-learning-databases/letter-recognition/.
• 21: J. K. Uhlmann. Satisfying general proximity/similarity queries with metric trees. Information Processing Letters, 40:175--179, 1991.
• 22: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
classification, high dimension, k nearest neighbor, metric tree