Abstract
This paper introduces a new associative approach for significant acceleration of k Nearest Neighbor classifiers (kNN). The kNN classifier is a lazy method, i.e. it does not create a computational model, so it is inefficient during classification using big training data sets because it requires going through all training patterns when classifying each sample. In this paper, we propose to use Associative Graph Data Structures (AGDS) as an efficient model for storing training patterns and their relations, allowing for fast access to nearest neighbors during classification made by kNNs. Hence, the AGDS significantly accelerates the classification made by kNNs, especially for large and huge training datasets. In this paper, we introduce an Associative Acceleration Algorithm and demonstrate how it works on this associative structure substantially reducing the number of checked patterns and quickly selecting k nearest neighbors for kNNs. The presented approach was compared to classic kNN approaches successfully.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abidin, T., Perrizo, W.: A fast and scalable nearest neighbor based classifier for data mining. In: Proceedings of ACM SAC 2006, Dijon, France, pp. 536–540. ACM Press, New York (2006)
Agrawal, R.: Extensions of k-nearest neighbor algorithm. Res. J. Appl. Sci. Eng. Technol. 13(1), 24–29 (2016)
Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)
Goodfellow, I., Bengio, Y., Courville, A.: Deep Learning. MIT Press, Cambridge (2016)
Grana, M.: Advances in Knowledge-Based and Intelligent Information and Engineering Systems. IOS Press, Amsterdam (2012)
Horzyk, A.: Artificial Associative Systems and Associative Artificial Intelligence. EXIT, Warsaw (2013)
Horzyk, A.: Associative graph data structures with an efficient access via AVB+trees. In: 11th Conference on Human System Interaction (HSI 2018). IEEE Xplore (2018, in print)
Horzyk, A.: Neurons can sort data efficiently. In: Rutkowski, L., Korytkowski, M., Scherer, R., Tadeusiewicz, R., Zadeh, L.A., Zurada, J.M. (eds.) ICAISC 2017. LNCS (LNAI), vol. 10245, pp. 64–74. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59063-9_6
Horzyk, A.: Deep associative semantic neural graphs for knowledge representation and fast data exploration. In: Proceedings of KEOD 2017, pp. 67–79. Scitepress Digital Library (2017)
Horzyk, A., Starzyk, J.A.: Multi-class and multi-label classification using associative pulsing neural networks. In: 2018 IEEE WCCI IJCNN, pp. 427–434. IEEE Xplore (2018)
Jensen, R., Cornelis, C.: A new approach to fuzzy-rough nearest neighbour classification. In: Chan, C.-C., Grzymala-Busse, J.W., Ziarko, W.P. (eds.) RSCTC 2008. LNCS (LNAI), vol. 5306, pp. 310–319. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-88425-5_32
Kalat, J.W.: Biological Grounds of Psychology, 10th edn. Wadsworth Publishing, Belmont (2008)
Tadeusiewicz, R.: New trends in neurocybernetics. Comput. Methods Mater. Sci. 10, 1–7 (2010)
Tadeusiewicz, R.: Introduction to intelligent systems. In: Fault Diagnosis. Models, Artificial Intelligence, Applications, CRC Press, Boca Raton (2011)
Shalev-Shwartz, S., Ben-David, S.: Understanding Machine Learning: From Theory to Algorithms. Cambridge university Press, Cambridge (2014)
Vivencio, D.P., et al.: Feature-weighted k-nearest neighbor classifier. In: Proceedings of FOCI, pp. 481–486 (2007)
Witten, I.H., Frank, E.: Data Mining: Practical Machine Learning Tools and Techniques, 2nd edn. Morgan Kaufmann Publishers, Morgan Kaufmann Publishers (2005)
Wu, X., Zhu, X., Wu, G.Q., Ding, W.: Data mining with big data. Trans. Knowl. Data Eng. 26(1), 97–107 (2014)
UCI ML Repository. https://archive.ics.uci.edu/ml/index.php. Accessed 25 May 2018
Dudani, S.A.: The distance-weighted k-nearest neighbor rule. IEEE Trans. Syst. Man Cybern. 6, 325–327 (1976)
Gou, J., Lan, D., Zhang, Y., Xiong, T.: A new distance-weighted k-nearest neighbor classifier. J. Inf. Comput. Sci. 9(6), 1429–1436 (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Horzyk, A., Gołdon, K. (2018). Associative Graph Data Structures Used for Acceleration of K Nearest Neighbor Classifiers. In: Kůrková, V., Manolopoulos, Y., Hammer, B., Iliadis, L., Maglogiannis, I. (eds) Artificial Neural Networks and Machine Learning – ICANN 2018. ICANN 2018. Lecture Notes in Computer Science(), vol 11139. Springer, Cham. https://doi.org/10.1007/978-3-030-01418-6_64
Download citation
DOI: https://doi.org/10.1007/978-3-030-01418-6_64
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-01417-9
Online ISBN: 978-3-030-01418-6
eBook Packages: Computer ScienceComputer Science (R0)