An Enhanced Adaptive k-Nearest Neighbor Classifier Using Simulated Annealing

Автор: Anozie Onyezewe, Armand F. Kana, Fatimah B. Abdullahi, Aminu O. Abdulsalami

Журнал: International Journal of Intelligent Systems and Applications @ijisa

Статья в выпуске: 1 vol.13, 2021 года.

Бесплатный доступ

The k-Nearest Neighbor classifier is a non-complex and widely applied data classification algorithm which does well in real-world applications. The overall classification accuracy of the k-Nearest Neighbor algorithm largely depends on the choice of the number of nearest neighbors(k). The use of a constant k value does not always yield the best solutions especially for real-world datasets with an irregular class and density distribution of data points as it totally ignores the class and density distribution of a test point’s k-environment or neighborhood. A resolution to this problem is to dynamically choose k for each test instance to be classified. However, given a large dataset, it becomes very tasking to maximize the k-Nearest Neighbor performance by tuning k. This work proposes the use of Simulated Annealing, a metaheuristic search algorithm, to select optimal k, thus eliminating the prospect of an exhaustive search for optimal k. The results obtained in four different classification tasks demonstrate a significant improvement in the computational efficiency against the k-Nearest Neighbor methods that perform exhaustive search for k, as accurate nearest neighbors are returned faster for k-Nearest Neighbor classification, thus reducing the computation time.

Еще

Adaptive Algorithms, Classification, Heuristic Learning, k-Nearest Neighbor (kNN), Parameter Optimization

Короткий адрес: https://sciup.org/15017526

IDR: 15017526   |   DOI: 10.5815/ijisa.2021.01.03

Список литературы An Enhanced Adaptive k-Nearest Neighbor Classifier Using Simulated Annealing

  • T. M. Cover, and P. E. Hart, “Nearest Neighbor Pattern Classification,” IEEE Transactions on Information Theory 13, 1967, pp. 21–27.
  • N. Nilsson, Learning Machines: Foundations of Trainable Pattern-Classifying Systems, 1965.
  • G. S. Sebestyen, Decision-making Processes in Pattern Recognition (ACM monograph series), 1962.
  • P. Rani, “A Review of Various KNN Techniques,” International Journal for Research in Applied Science & Engineering Technology, 2017.
  • J. Han, M. Kamber, and J. Pei, Data Mining Concepts and Techniques. Boston: Elsevier Inc, 2012.
  • I. Tsang, J. Kwok, and P. Cheung, “Core Vector Machines: Fast SVM Training on Very Large Data Sets,” Journal of Machine Learning Research, 2005, pp. 363-392.
  • S. Zhou, T. Ling, and J. Guan, “Fast Text Classification: A Training Corpus Pruning Based Approach,” Proceedings of Data-base Systems for Advanced Applications, Kyoto, Japan: IEEE Computer Society, 2003, pp. 127-136
  • W. Ian, F. Eibe, “Data Mining: Practical Machine Learning Tools and Techniques,” Elsevier, 2005, pp. 129-135
  • S. Berchtold, B. Ertl, and Keim, “A Fast Nearest Neighbor Search in High-dimensional Space,” International Conference on Data Engineering, 1998, pp. 209-218.
  • B. LI, S. Yu, and Q. Lu, “An Improved K-Nearest Neighbor Algorithm for Text Categorization,” in Proceedings of the 20th International Conference on Computer Processing of Oriental Languages . China: Shenyang, 2003.
  • L. Jiang, H. Zhang, and Z. Cai, “Dynamic K-Nearest-Neighbor Naive Bayes with Attribute Weighted,” International Conference on Fuzzy Systems and Knowledge Discovery. Springer, Berlin, Heidelberg, 2006.
  • C. Yang, Y. Li, C. Zhang, and Y. Hu, “A Fast KNN Algorithm Based on Simulated Annealing”. Department of Computing & Information Technology, Fudan University, 2007.
  • S. Sun, and R. Huang, “An Adaptive K-Nearest Neighbor Algorithm”. Seventh International Conference on Fuzzy Systems and Knowledge Discovery, 2010.
  • W. Liu, and S. Chawla, “Class Confidence Weighted KNN Algorithms for Imbalanced Datasets,” Pacific-Asia Conference on Knowledge Discovery and Data Mining, 2011, pp. 345-356.
  • M. Kuhkan, “A Method to Improve the Accuracy of K-Nearest Neighbor Algorithm,” International Journal of Computer Engineering and Information Technology, 2016, pp. 90-95.
  • S. Mullick, S. Datta, and S. Das, “Adaptive Learning-Based K-Nearest Neighbour Classifiers With Resilience to Class Imbalance,” IEEE transactions on neural networks and learning systems, 2018.
  • M. Kibanov, M. Becker, J. Mueller, M. Atzmueller, A. Hotho, and G. Stumme, “Adaptive KNN Using Expected Accuracy for Classification of Geo-Spatial Data,” Symposium on Applied Computing. Pau, France, 2018.
  • M. Abdullahi, Md. Ngadi, “Hybrid Symbiotic Organisms Search Optimization Algorithm for Scheduling of Tasks on Cloud Computing Environment,” PLoSONE 11(6):e0158229, 2016.
Еще
Статья научная