Enhancing K-Nearest Neighbors for Categorical Data Classification Using Similarity-Based Distance Metrics
DOI:
https://doi.org/10.33411/IJIST/1965Keywords:
Machine Learning, Classification, K-Nearest Neighbors (KNN), Lin Similarity, Value Difference Metric (VDM), Tanimoto Similarity, Categorical Data Classification, Android Malware DetectionAbstract
Categorical data are pervasive in real-world classification problems, yet most machine learning algorithms, including support vector machines, decision trees and neural networks, are formulated for numeric feature spaces. The K-Nearest Neighbor (KNN) classifier is particularly affected because its decision rule depends entirely on a distance function that is not naturally defined over unordered categorical values. Encoding categorical attributes into numeric form imposes an artificial ordering and causes information loss, which motivates the use of similarity measures designed specifically for categorical attributes. This study presents a controlled comparative evaluation of three similarity-based KNN variants under an identical experimental protocol: Lin-KNN, which uses matching-based similarity; VDM-KNN, which uses class-conditional probability differences; and Tanimoto-KNN, which uses overlap-based similarity. The three models were assessed on two publicly available categorical benchmark datasets obtained from Kaggle, namely the Mushroom dataset (edible versus poisonous) and an Android permission-based malware detection dataset (benign versus malicious). Mutual-information based feature selection was applied independently for each similarity measure, the number of neighbours was tuned by grid search over stratified cross-validation on the training partition only, and performance was reported using accuracy, precision, recall and F1-score. Lin-KNN achieved the highest overall performance with an average accuracy of 95.56%, precision of 95.57%, recall of 95.55% and F1-score of 95.56%. VDM-KNN was highly competitive with an average accuracy of 94.44%, precision of 94.45%, recall of 94.43% and F1-score of 94.43%, and was the stronger of the two on the malware dataset. Tanimoto-KNN was consistently weaker, with an average accuracy of 81.44%, precision of 85.22%, recall of 81.56% and F1-score of 80.14%. Differences between the models were further examined through repeated stratified cross-validation and non-parametric significance testing. The results demonstrate that no single similarity measure dominates across categorical domains: matching-based similarity is preferable for strongly structured attribute spaces in which attribute agreement aligns closely with class separability, whereas class-conditional similarity is preferable for sparse, weakly discriminative binary attribute spaces such as Android permissions. These findings provide practical guidance for selecting an appropriate KNN variant in real-world machine learning applications involving categorical data.
References
B. A. Hassan et al., “An Enhanced Similarity Measure–Driven K-Nearest Neighbor Framework for Categorical Data Classification,” Int. J. Innov. Sci. Technol., vol. 7, no. 4, pp. 2757–2772, 2025, Accessed: Jul. 12, 2026. [Online]. Available: https://ideas.repec.org/a/abq/ijist1/v7y2025i4p2757-2772.html
Roy Thomas, “A Novel Ensemble Method for Detecting Outliers in Categorical Data,” Int. J. Adv. Trends Comput. Sci. Eng., vol. 9, no. 4, pp. 4947–4953, 2021, doi: 10.30534/ijatcse/2020/108942020.
O. L. V. B. Surya Prasath, Haneen Arafat Abu Alfeilat, Ahmad B. A. Hassanat, “Distance and Similarity Measures Effect on the Performance of K-Nearest Neighbor Classifier -- A Review,” Big Data, vol. 7, no. 4, pp. 221–248, 2019, doi: https://doi.org/10.48550/arXiv.1708.04321.
A. Islam, S. B. Belhaouari, A. U. Rehman, and H. Bensmail, “KNNOR: An oversampling technique for imbalanced datasets[Formula presented],” Appl. Soft Comput., vol. 115, Jan. 2022, doi: 10.1016/J.ASOC.2021.108288.
B. Guindon and Y. Zhang, “Application of the Dice Coefficient to Accuracy Assessment of Object-Based Image Classification,” Can. J. Remote Sens., vol. 43, no. 1, pp. 48–61, Jan. 2017, doi: 10.1080/07038992.2017.1259557.
“(PDF) Comparison of Euclidean Distance Function and Manhattan Distance Function Using K-Mediods.” Accessed: Jul. 25, 2026. [Online]. Available: https://www.researchgate.net/publication/291970199_Comparison_of_Euclidean_Distance_Function_and_Manhattan_Distance_Function_Using_K-Mediods
A. F. Pulungan, M. Zarlis, and S. Suwilo, “Analysis of Braycurtis, Canberra and Euclidean Distance in KNN Algorithm,” SinkrOn, vol. 4, no. 1, p. 74, Sep. 2019, doi: 10.33395/SINKRON.V4I1.10207.
V. T. Jaglan, Vivek, “Comparison of Jaccard, Dice, Cosine Similarity Coefficient To Find Best Fitness Value for Web Retrieved Documents Using Genetic Algorithm,” Int. J. Innov. Eng. Technol., vol. 2, no. 4, pp. 202–205, 2013, [Online]. Available: https://www.researchgate.net/publication/306204167_Comparison_of_Jaccard_Dice_Cosine_Similarity_Coefficient_To_Find_Best_Fitness_Value_for_Web_Retrieved_Documents_Using_Genetic_Algorithm
J. Antorán, U. Bhatt, T. Adel, A. Weller, and J. M. Hernández-Lobato, “Getting a CLUE: A Method for Explaining Uncertainty Estimates,” ICLR 2021 - 9th Int. Conf. Learn. Represent., Jun. 2020, Accessed: Jul. 25, 2026. [Online]. Available: https://arxiv.org/pdf/2006.06848
H. Dhaker, P. Ngom, B. Ibrahimouf, and M. Mbodj, “Overlap Coefficients Based on Kullback-Leibler of Two Normal Densities: Equal Means Case,” J. Math. Res., vol. 11, no. 2, p. 114, Mar. 2019, doi: 10.5539/JMR.V11N2P114.
R. K. A. Vijay Verma, “A New Similarity Measure Based on Simple Matching Coefficient for Improving the Accuracy of Collaborative Recommendations,” Int. J. Inf. Technol. Comput. Sci., vol. 11, no. 6, 2019, doi: https://doi.org/10.5815/ijitcs.2019.06.05.
T. Dinh et al., “Categorical data clustering: 25 years beyond K-modes,” Expert Syst. Appl., vol. 272, p. 126608, May 2025, doi: 10.1016/J.ESWA.2025.126608.
E. U. Oti, M. O. Olusola, F. C. Eze, and S. U. Enogwe, “Comprehensive Review of K-Means Clustering Algorithms,” Int. J. Adv. Sci. Res. Eng., vol. 07, no. 08, pp. 64–69, 2021, doi: 10.31695/IJASRE.2021.34050.
M. Kim and R. S. Ramakrishna, “Projected clustering for categorical datasets,” Pattern Recognit. Lett., vol. 27, no. 12, pp. 1405–1417, Sep. 2006, doi: 10.1016/J.PATREC.2006.01.011.
M. Á. Carreira-Perpiñán and W. Wang, “The K-modes algorithm for clustering,” Apr. 2013, Accessed: Aug. 09, 2026. [Online]. Available: https://arxiv.org/pdf/1304.6478
M. J. Zaki and M. Peters, “CLICKS: Mining subspace clusters in categorical data via K-partite maximal cliques,” Proc. - Int. Conf. Data Eng., pp. 355–356, 2005, doi: 10.1109/ICDE.2005.33.
S. Sharma and M. Singh, “Generalized similarity measure for categorical data clustering,” 2016 Int. Conf. Adv. Comput. Commun. Informatics, ICACCI 2016, pp. 765–769, Nov. 2016, doi: 10.1109/ICACCI.2016.7732138.
H. L. Chen, K. T. Chuang, and M. S. Chen, “On data labeling for clustering categorical data,” IEEE Trans. Knowl. Data Eng., vol. 20, no. 11, pp. 1458–1471, Nov. 2008, doi: 10.1109/TKDE.2008.81.
“Semantic Similarity- A Review of Approaches and Metrics | Request PDF.” Accessed: Aug. 09, 2026. [Online]. Available: https://www.researchgate.net/publication/325411209_Semantic_Similarity-_A_Review_of_Approaches_and_Metrics
M. C. Abounaima, F. Z. Mazouri El, L. Lamrini, N. Nfissi, N. El Makhfi, and M. Ouzarf, “The Pearson Correlation Coefficient Applied to Compare Multi-Criteria Methods: Case the Ranking Problematic,” 2020 1st Int. Conf. Innov. Res. Appl. Sci. Eng. Technol. IRASET 2020, Apr. 2020, doi: 10.1109/IRASET48871.2020.9092242.
X. Zeng, Y. Liao, Y. Liu, and Q. Zou, “Prediction and validation of disease genes using HeteSim scores,” IEEE/ACM Trans. Comput. Biol. Bioinforma., vol. 14, no. 3, pp. 687–695, May 2017, doi: 10.1109/TCBB.2016.2520947.
H. C. Sayali D. Jadhav, “Comparative Study of K-NN , Naive Bayes and Decision Tree Classification Techniques,” Int. J. Sci. Res., vol. 5, no. 1, pp. 1842–1845, 2016, [Online]. Available: https://www.semanticscholar.org/paper/Comparative-Study-of-K-NN-%2C-Naive-Bayes-and-Tree-Jadhav-Channe/51c068c263ee197a292df5b74b58c8c55df9f9ca
“(PDF) Comparative Study of Four Supervised Machine Learning Techniques for Classification.” Accessed: Jul. 25, 2026. [Online]. Available: https://www.researchgate.net/publication/319313534_Comparative_Study_of_Four_Supervised_Machine_Learning_Techniques_for_Classification
M. Z. Islam, J. Liu, J. Li, L. Liu, and W. Kang, “A semantics aware random forest for text classification,” Int. Conf. Inf. Knowl. Manag. Proc., pp. 1061–1070, Nov. 2019, doi: 10.1145/3357384.3357891; Journal: Acmconferences;Pagegroup:String:Publication.
Kedar Potdar, Taher S. Pardawala, Chinmay D. Pai, “A Comparative Study of Categorical Variable Encoding Techniques for Neural Network Classifiers,” Int. J. Comput. Appl., vol. 175, no. 4, 2017, [Online]. Available: https://www.ijcaonline.org/archives/volume175/number4/potdar-2017-ijca-915495.pdf
A. A. Nair, T. D. Tran, A. Reiter, and M. A. Lediju Bell, “A Deep Learning Based Alternative to Beamforming Ultrasound Images,” ICASSP, IEEE Int. Conf. Acoust. Speech Signal Process. - Proc., vol. 2018-April, pp. 3359–3363, Sep. 2018, doi: 10.1109/ICASSP.2018.8461575.
M. C. Rahim Taheri, Meysam Ghahramani, Reza Javidan, Mohammad Shojafar, Zahra Pooranian, “Similarity-based Android malware detection using Hamming distance of static binary features,” Futur. Gener. Comput. Syst., vol. 105, pp. 230–247, 2020, doi: https://doi.org/10.1016/j.future.2019.11.034.
L. E. Tiago R.L. dos Santos, Zárate, “Categorical data clustering: What similarity measure to recommend?,” Expert Syst. Appl., vol. 42, no. 3, pp. 1247–1260, 2015, doi: https://doi.org/10.1016/j.eswa.2014.09.012.
Mohammad Bolandraftar, “Application of K-Nearest Neighbor (KNN) Approach for Predicting Economic Events: Theoretical Background,” Academia, 2013, [Online]. Available: https://www.academia.edu/82354140/Application_of_K_Nearest_Neighbor_KNN_Approach_for_Predicting_Economic_Events_Theoretical_Background
A. A. Vatinno, A. Simpson, V. Ramakrishnan, H. S. Bonilha, L. Bonilha, and N. J. Seo, “The Prognostic Utility of EEG in Stroke Recovery: A Systematic Review and Meta-Analysis,” Neurorehabil. Neural Repair, vol. 36, no. 4–5, p. 255, Apr. 2022, doi: 10.1177/15459683221078294.
S. Naseer et al., “Enhanced network anomaly detection based on deep neural networks,” IEEE Access, vol. 6, pp. 48231–48246, Aug. 2018, doi: 10.1109/ACCESS.2018.2863036.
L. Cai, S. Zhao, F. Meng, and T. Zhang, “Adaptive K-NN metric classification based on improved Kepler optimization algorithm,” J. Supercomput. 2024 811, vol. 81, no. 1, pp. 66-, Oct. 2024, doi: 10.1007/S11227-024-06559-Y.
M. S. Jawthari, “Predicting students’ academic performance using a modified kNN algorithm,",” journalPollack, vol. 16, no. 3, 2021, doi: doi: 10.1556/606.2021.00374.
D. Theng and K. K. Bhoyar, “Feature selection techniques for machine learning: a survey of more than two decades of research,” Knowl. Inf. Syst. 2023 663, vol. 66, no. 3, pp. 1575–1637, Dec. 2023, doi: 10.1007/S10115-023-02010-5.
A. M. Vommi and T. K. Battula, “A hybrid filter-wrapper feature selection using Fuzzy KNN based on Bonferroni mean for medical datasets classification: A COVID-19 case study,” Expert Syst. Appl., vol. 218, p. 119612, May 2023, doi: 10.1016/J.ESWA.2023.119612.
A. Muzaffar, H. Ragab Hassen, M. A. Lones, and H. Zantout, “An in-depth review of machine learning based Android malware detection,” Comput. Secur., vol. 121, p. 102833, Oct. 2022, doi: 10.1016/J.COSE.2022.102833.
F. Akbar, M. Hussain, R. Mumtaz, Q. Riaz, A. W. A. Wahab, and K. H. Jung, “Permissions-Based Detection of Android Malware Using Machine Learning,” Symmetry 2022, Vol. 14, Page 718, vol. 14, no. 4, p. 718, Apr. 2022, doi: 10.3390/SYM14040718.
D. Ö. Şahin, O. E. Kural, S. Akleylek, and E. Kılıç, “A novel permission-based Android malware detection system using feature selection based on linear regression,” Neural Comput. Appl. 2021 357, vol. 35, no. 7, pp. 4903–4918, Mar. 2021, doi: 10.1007/S00521-021-05875-1.
M. S. Ahmed et al., “Comparative Analysis of Interpretable Mushroom Classification using Several Machine Learning Models,” Proc. 2022 25th Int. Conf. Comput. Inf. Technol. ICCIT 2022, pp. 31–36, 2022, doi: 10.1109/ICCIT57492.2022.10055555.
K. Tutuncu, I. Cinar, R. Kursun, and M. Koklu, “Edible and Poisonous Mushrooms Classification by Machine Learning Algorithms,” 2022 11th Mediterr. Conf. Embed. Comput. MECO 2022, 2022, doi: 10.1109/MECO55406.2022.9797212.
M. Sabri, R. Verde, and A. Balzanella, “FWLMkNN: Efficient functional K-nearest neighbor based on clustering and functional data analysis,” Expert Syst. Appl., vol. 292, p. 128567, Nov. 2025, doi: 10.1016/J.ESWA.2025.128567.
A. Surendran, K. Zsigmond, K. Lopez Perez, and R. A. Miranda Quintana, “Is Tanimoto a metric?,” bioRxiv, p. 2025.02.18.638904, 2025.
D. Anastasiu and G. Karypis, “Efficient identification of Tanimoto nearest neighbors: All-pairs similarity search using the extended Jaccard coefficient,” Int. J. Data Sci. Anal., vol. 4, 2017, doi: 10.1007/s41060-017-0064-z.
K. Rieck KONRADRIECK and F. Pavel Laskov PAVELLASKOV, “Linear-Time Computation of Similarity Measures for Sequential Data,” J. Mach. Learn. Res., vol. 9, pp. 23–48, 2008.
DemšarJanez, “Statistical Comparisons of Classifiers over Multiple Data Sets,” J. Mach. Learn. Res., Dec. 2006, doi: 10.5555/1248547.1248548.
“Mushroom - UCI Machine Learning Repository.” Accessed: Aug. 09, 2026. [Online]. Available: https://archive.ics.uci.edu/dataset/73/mushroom
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2006 50SEA

This work is licensed under a Creative Commons Attribution 4.0 International License.


















