International Journal of Intelligent Systems and Applications(IJISA)
ISSN: 2074-904X (Print), ISSN: 2074-9058 (Online)
Published By: MECS Press
IJISA Vol.13, No.1, Feb. 2021
An Enhanced Adaptive k-Nearest Neighbor Classifier Using Simulated Annealing
Full Text (PDF, 925KB), PP.34-44
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
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.