Resumen de clasificadores rápidos basados en el algoritmo del vecino más cercano
DOI:
https://doi.org/10.5281/zenodo.6963998Palabras clave:
regla del vecino más cercano, clasificadores rápidos, vecino cercanoResumen
Actualmente, en diferentes ciencias como la medicina, las geociencias, la astronomía, entre otras, la tarea de clasificación supervisada ha dado solución a muchos problemas importantes. Uno de los algoritmos de clasificación supervisada más utilizados ha sido k vecinos más cercanos (o k Neares Neighbors, k-NN), el cual ha mostrado ser un algoritmo simple, pero efectivo. El algoritmo k vecinos más cercanos realiza una comparación exhaustiva entre el nuevo objeto a clasificar y todos los elementos del conjunto de entrenamiento. Sin embargo, cuando el conjunto de entrenamiento es grande, este proceso es costoso y en algunos casos esta búsqueda exhaustiva se vuelve un proceso muy lento o inaplicable. Para agilizar el proceso de clasificación y omitir comparaciones, se han propuesto en los últimos años clasificadores rápidos basados en el algoritmo del vecino más cercano (Fast k-NN). La mayoría de estos algoritmos Fast k-NN se basan en las propiedades métricas de la función de distancia para omitir comparaciones o bien otras heurísticas.
Métricas
Citas
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).
Publicado
Cómo citar
Número
Sección
Licencia
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
Esta revista adhiere a la licencia Creative Commons en la definición de su política de acceso abierto y reúso del material publicado, en los términos siguientes:
- Accesibilidad a los artículos y demás publicaciones de manera total o parcial bajo el concepto de copia, distribución, comunicación pública, acceso interactivo (por internet u otros medios), manteniendo de manera explícita el reconocimiento al autor o autores y a la propia revista (reconocimiento de autoría).
- Advertencia de que si se remezcla, modifican los artículos o se emplean fragmentos en otras creaciones, no se puede distribuir el material modificado, ni tampoco se permite reconstruir versiones a partir de los artículos originales publicados (obras derivadas).
- Se prohíbe el uso de contenidos de los artículos publicados, total o parcialmente, con fines lucrativos (reconocimiento no comercial).
El autor conserva los derechos de autor, transfiere u otorga derechos comerciales exclusivos al editor, y se utiliza una licencia no comercial.
