International Journal of Intelligent Systems and Applications (IJISA)
IJISA Vol. 13, No. 1, 8 Feb. 2021
Cover page and Table of Contents: PDF (size: 490KB)
An Enhanced Adaptive k-Nearest Neighbor Classifier Using Simulated Annealing
Full Text (PDF, 490KB), PP.34-44
Views: 0 Downloads: 0
Author(s)
Anozie Onyezewe
1,*
Armand F. Kana
1
Fatimah B. Abdullahi
1
Aminu O. Abdulsalami
1
Index Terms
Adaptive Algorithms, Classification, Heuristic Learning, k-Nearest Neighbor (kNN), Parameter Optimization
Abstract
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.
Cite This Paper
Anozie Onyezewe, Armand F. Kana, Fatimah B. Abdullahi, Aminu O. Abdulsalami, "An Enhanced Adaptive k-Nearest Neighbor Classifier Using Simulated Annealing", International Journal of Intelligent Systems and Applications(IJISA), Vol.13, No.1, pp.34-44, 2021. DOI:10.5815/ijisa.2021.01.03
Reference
[1]T. M. Cover, and P. E. Hart, “Nearest Neighbor Pattern Classification,” IEEE Transactions on Information Theory 13, 1967, pp. 21–27.
[2]N. Nilsson, Learning Machines: Foundations of Trainable Pattern-Classifying Systems, 1965.
[3]G. S. Sebestyen, Decision-making Processes in Pattern Recognition (ACM monograph series), 1962.
[4]P. Rani, “A Review of Various KNN Techniques,” International Journal for Research in Applied Science & Engineering Technology, 2017.
[5]J. Han, M. Kamber, and J. Pei, Data Mining Concepts and Techniques. Boston: Elsevier Inc, 2012.
[6]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.
[7]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
[8]W. Ian, F. Eibe, “Data Mining: Practical Machine Learning Tools and Techniques,” Elsevier, 2005, pp. 129-135
[9]S. Berchtold, B. Ertl, and Keim, “A Fast Nearest Neighbor Search in High-dimensional Space,” International Conference on Data Engineering, 1998, pp. 209-218.
[10]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.
[11]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.
[12]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.
[13]S. Sun, and R. Huang, “An Adaptive K-Nearest Neighbor Algorithm”. Seventh International Conference on Fuzzy Systems and Knowledge Discovery, 2010.
[14]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.
[15]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.
[16]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.
[17]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.
[18]M. Abdullahi, Md. Ngadi, “Hybrid Symbiotic Organisms Search Optimization Algorithm for Scheduling of Tasks on Cloud Computing Environment,” PLoSONE 11(6):e0158229, 2016.