Summary of Fast Classifiers Based on the Nearest Neighbor Algorithm
DOI:
https://doi.org/10.5281/zenodo.6963998Keywords:
Nearest neighbor rule, Fast k-NN/k-MSN classifiersAbstract
Currently, in different sciences such as medicine, geosciences, astronomy, among others, the supervised classification task has provided solutions to many important problems. One of the most used supervised classification algorithms has been k nearest neighbors (or k Neares Neighbors, k-NN), which has shown to be a simple but effective algorithm. The k nearest neighbors algorithm performs an exhaustive comparison between the new object to be classified and all the elements of the training set. However, when the training set is large, this process is expensive and in some cases this exhaustive search becomes very slow or inapplicable. In order to speed up the classification process and omit comparisons, fast classifiers based on the nearest neighbor algorithm (Fast k-NN) have been proposed in recent years. Most of these Fast k-NN algorithms rely on the metric properties of the distance function to omit comparisons or other heuristics.
Metrics
References
Arya S., Mount D., Netanyahu N., Silverman R., and Wu A. (1998). "An optimal algorithm for approximate nearest neighbor searching in high dimensions". J. ACM 45 (6) 891-923.
Athitsos V., Alon J. and Sclaroff S. (2005) “Efficient nearest neighbour classification using cascade of approximate with similarity measures”. Boston University Computer Science Tech. Report No. 2005-009.
Bandyopadhyay S. & Maulik U. (2002).“Efficient prototype reordering in nearest neighbor classification”. Pattern Recognition 35 pp: 2791-2799.
Cover T. M. and Hart P. E. (1967). "Nearest neighbor pattern classification". Trans. Information Theory. 13, pp. 21¬27.
Deerwester S., Dumals S., Furnas T., Landauer G. & Harshman R. (1990). “Indexing by latent semantic analysis”. J. Amer. Soc. Inform. Sci. 41, pp. 391-407
Fisher F. & Patrick E. (1970).“A preprocessing algorithm for nearest neighbour decision rules”. Proc. Nat. Electronics Conf., vol. 26, pp. 481-485
Friedman J. H., Bentley J. L. and Finkel R. A. (1977). “An algorithm for finding best matches in logarithmic expected time”. ACM Transactions on Mathematical Software 3 (3), pp.209-226
Fukunaga K. and Narendra P. (1975). "A branch and bound algorithm for computing k-nearest neighbors". IEEE Trans. Comput. 24, pp. 743-750
Gersho A. and Gray R. (1991).“Vector Quantization and Signal Compression”. Kluwer Academic, Boston, MA.
Gómez-Ballester E., Mico L., and Oncina J. (2006). "Some approaches to improve tree-based nearest neighbor search algorithms". Pattern Recognition Letters, vol. 39 pp. 171-179
Hwang W. & Wen K. (2002). “Fast kNN classification algorithm based on partial distance search”. Electronics Letters,vol 34: 21, pp. 2062-2063.
Kalantari I. and McDonald G. (1983).“A data structure and an algorithm for the nearest point problem”. IEEE Trans. Software Eng. 9, pp. 631-634
Nene S. and Nayar S. (1997). “A simple algorithm for nearest neighbour search in high dimensions”. IEEE Trans. Pattern Anal. Mach. Intell. 19(9) 989-1003.
Niijima, S. and Kuhara, S. (2005). “Effective nearest neighbors methods for multiclass cancer classification using microarray data”. Poster presented at the 16th International Conference on Genome Informatics, December 19-21, 2005, Yokohama Pacifico,Japan.
Oncina J., Thollard F., Gomez-Ballester E., Mica L., and Moreno-Seco F. (2007). "A Tabular Pruning Rule in TreeBased Fast Nearest Neighbor Search Algorithms". IbPRIA, LNCS 4478, pp. 306-313.
Orchard, Michael T. (1991). A fast nearest-neighbor search algorithm. In 1991 International Conference on Acoustics, Speech and Signal Processing, 1991. ICASSP-91., Volume 4 (pp. 2297–3000). IEEE Press.
Wolfson H. (1990). Model-Based object recognition by geometric hashing. Proc. First European Conf. Comp. Vision, pp. 526-536.
Yalin Chen, Zhiyang Li, Jia Shi, Zhaobin Liu, Wenyu Qu. (2018). Stacked K-Means Hashing Quantization for Nearest Neighbor Search. 2018 IEEE Fourth International Conference on Multimedia Big Data (BigMM).
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
This journal adheres to the Creative Commons license in the definition of its policy of open access and reuse of published material, in the following terms:
- Accessibility to articles and other publications in whole or in part under the concept of copying, distribution, public communication , interactive access (through the Internet or other means), explicitly maintaining the recognition of the author or authors and the journal itself (authorship acknowledgment).
- Warning that if the articles are remixed, modified or fragments used in other creations, the modified material cannot be distributed, nor is it allowed to reconstruct versions from the original published articles (derived works).
- The use of the contents of the published articles, in whole or in part, for profit (non-commercial recognition) is prohibited.
The author retains copyright, transfers or grants exclusive commercial rights to the publisher, and a non-commercial license is used.
