research-article

An Improved k-NN Classification with Dynamic k

Authors:

Xiao-Feng Zhong,

Jing-Hua ZhengAuthors Info & Claims

ICMLC '17: Proceedings of the 9th International Conference on Machine Learning and Computing

Pages 211 - 216

https://doi.org/10.1145/3055635.3056604

Published: 24 February 2017 Publication History

Abstract

In the k-NN algorithm, k is the only parameter and often set to a fixed value empirically. However, it is very difficult to choose an appropriate k in practice, and if the choice is not appropriate, the performance of k-NN will be affected greatly. In order to solve this problem, the paper proposes an improved k-NN algorithm, which is denoted as Dk-NN, by using dynamic k in replace of fixed k value. Firstly, a preprocessed step is designed and added to the traditional k-NN algorithm for determining the dynamic k interval. Then, each class's percentage of test sample is calculated within the dynamic k interval. Finally, three criterions are given to determine the class of the test sample according to the variation tendency of the percentage curves. Experimental results on real-world dataset demonstrate that the proposed algorithm is more effective than the k-NN algorithm with fixed k value.

References

[1]

Taneja, S., Gupta, C., Aggarwal, S., and Jindal, V. 2015. MFZ-KNN-A modified fuzzy based K nearest neighbor algorithm. International Conference on Cognitive Computing and Information Processing. (April, 2015), 1--5.

[2]

Dhurandhar, A., and Dobra, A. 2013. Probabilistic characterization of nearest neighbor classifier. Int. J. Mach. Learn. & Cyber. 4, 4 (August, 2013), 259--272.

[3]

Khadim, D., Fleur, M., and Gayo, D. 2016. Large scale biomedical texts classification: a knn and an esa-based approaches. J Biomed Semant. 7, 1 (December, 2016), 1--12.

[4]

Agarwal, S., and Sureka, A. 2015. Using KNN and SVM Based One-Class Classifier for Detecting Online Radicalization on Twitter. 11th International Conference, ICDCIT. (February, 2015), 431--442.

Digital Library

[5]

Cover, T. M., and Hart, P. E. 1967. Nearest neighbor pattern classification. IEEE Trans Inf Theory. 13,1, (1967), 21--27.

Digital Library

[6]

Mary-Huard, T., and Robin, S. 2009. Tailored aggregation for classification. IEEE Trans Pattern Anal Mach Intell. 31, 11 (March, 2009), 2098--105.

Digital Library

[7]

Gong, A., and Liu, Y. 2011. Improved KNN Classification Algorithm by Dynamic Obtaining K. International Conference, ECWAC. (April, 2011), 320--324.

[8]

Lin, S. W., and Chen, S. C. 2011. Parameter tuning, feature selection and weight assignment of features for case-based reasoning by artificial immune system. Applied Soft Computing. 11, 8 (December, 2011), 5042--5052.

Digital Library

[9]

Guyon, I., and Elisseeff, Andre. 2002. An introduction to variable and feature selection. J Mach Learn Res. 3, 6 (March, 2002), 1157--1182.

Digital Library

[10]

Saeys, Y., Inza, I., and Larrañaga, P. 2007. A review of feature selection techniques in bioinformatics. Bioinformatics. 23, 19 (August, 2007), 2507--17.

Digital Library

[11]

Chuang, L. Y., Chang, H. W., Tu, C. J., and Yang, C. H. 2008. Improved binary pso for feature selection using gene expression data. Comput Biol Chem. 32, 1 (February, 2008), 29--38.

Digital Library

[12]

Sahu, B., and Mishra, D. 2012. A novel feature selection algorithm using particle swarm optimization for cancer microarray data. Procedia Engineering. 38, 5 (December, 2012), 27--31.

[13]

Kardan, A. A., Kavian, A., and Esmaeili, A. 2013. Simultaneous feature selection and feature weighting with K selection for KNN classification using BBO algorithm. International Conference, IKT. 28, 4, (May, 2013), 349--354.

[14]

Kalayeh, M. M., Idrees, H., and Shah, M. 2014. NMF-KNN: Image Annotation Using Weighted Multi-view Non-negative Matrix Factorization. IEEE Conference on CVPR. (June, 2014), 184--191.

Digital Library

[15]

Wu, J. L., and Li, I. J. 2010. A SOM-based dimensionality reduction method for KNN classifiers. International Conference on SSE. (August, 2010), 173--178.

[16]

Draszawka, K., Szymański, J., and Guerra, F. 2015. Improving css-KNN Classification Performance by Shifts in Training Data. International Conference on IKC. (January, 2016), 51--63.

Digital Library

[17]

Omranpour, H., and Ghidary, S. S. 2016. A heuristic supervised euclidean data difference dimension reduction for knn classifier and its application to visual place classification. Neural Comput & Applic. (October, 2016), 1867--1881.

Digital Library

[18]

Jing, Y., Gou, H., and Zhu, Y. 2013. An Improved Density-Based Method for Reducing Training Data in KNN. International Conference on ICCIS. (January, 2013), 972--975.

Digital Library

[19]

Pawlovsky, A. P., and Nagahashi, M. 2014. A method to select a good setting for the kNN algorithm when using it for breast cancer prognosis. International Conference on BHI. (June, 2014), 189--192.

[20]

Li, N., Kong, H., Ma, Y., Gong, G., and Huai, W. 2016. Human performance modeling for manufacturing based on an improved knn algorithm. Int J Adv Manuf Technol. 84,1 (February, 2016), 473--483.

[21]

Wang, B., Liao, Q., and Zhang, C. 2013. Weight Based KNN Recommender System. International Conference on IHMSC. 2, (August, 2013), 449--452.

Digital Library

[22]

Zhang, L., Zhang, C., Xu, Q., and Liu, C. 2015. Weigted-KNN and its application on UCI. IEEE International Conference on IA. (August, 2015), 1748--1750.

[23]

Shi, K., Li, L., Liu, H., and He, J. 2011. An improved KNN text classification algorithm based on density. IEEE Proceedings of IEEE CCIS. (September, 2011), 113--117.

[24]

Liu, X., Ren, F., and Yuan, C. 2010. Use relative weight to improve the kNN for unbalanced text category. Proceedings of IEEE NLPKE. (August, 2010), 1--5.

[25]

Haixiang, G., Yijing, L., Yanan, L., Xiao, L., and Jinling, L. 2016. Bpso-adaboost-knn ensemble learning algorithm for multi-class unbalanced data classification. Eng Appl Artif Intel, (March, 2016), 176--193.

Digital Library

[26]

Bhattacharya, G., Ghosh, K., and Chowdhury, A. S. 2015. A probabilistic framework for dynamic k estimation in kNN classifiers with certainty factor. Proceedings of IEEE ICAPR. (January, 2015), 1--5.

[27]

Zhang, S., Zong, M., Sun, K., Liu, Y., and Cheng, D. 2014. Efficient kNN Algorithm Based on Graph Sparse Reconstruction. International Conference on ADMA. (December, 2014), 356--369.

[28]

Hamerly, G., and Speegle, G. 2010. Efficient Model Selection for Large-Scale Nearest-Neighbor Data Mining. International Conference on BNCOD 27. (July, 2010), 37--54.

Digital Library

[29]

Weng, F., Jiang, Q., Chen, L., Hong, Z., and Jiang, Q. S. 2007. Clustering ensemble based on the fuzzy KNN algorithm. International Conference on ACIS 18. (July, 2007), 1001--1006.

Digital Library

[30]

Jiang, L., Cai, Z., Wang, D., and Zhang, H. 2014. Bayesian citation-knn with distance weighting. Int. J. Mach. Learn. & Cyber. 5, 2 (April, 2014), 193--199.

[31]

Kozak, K., Kozak, M., Stapor, K., Kozak, K., Kozak, M., and Stapor, K. 2006. Weighted k-nearest-neighbor techniques for high throughput screening data. Int. J. of Bio & Med Sci. (January, 2006), 1--4.

[32]

Loftsgaarden, D. O., and Quesenberry, C. P. 1965. A nonparametric estimate of a multivariate density function. Ann. Math. Statist. 36, 3 (1965), 1049--1051.

[33]

Mitra, P., Murthy, C. A., and Pal, S. K. 2002. Unsupervised feature selection using feature similarity. IEEE Transactions on PAMI. 24, 3 (March, 2002), 301--312.

Digital Library

[34]

Kosinski, M., Matz, S. C., Gosling, S. D., Popov, V., and Stillwell, D. 2015. Facebook as a research tool for the social sciences: opportunities, challenges, ethical considerations, and practical guidelines. American Psychologist. 70, 6 (2015), 543--556.

[35]

Fernández-Tobíasd, I., and Cantador, I. 2014. Personality-Aware Collaborative Filtering: An Empirical Study in Multiple Domains with Facebook Data. International Conference on EC-Web. (September, 2014), 125--137.

Cited By

Liu WRalescu A(2024)The aggregated model for human target classificationNAECON 2024 - IEEE National Aerospace and Electronics Conference10.1109/NAECON61878.2024.10670639(428-432)Online publication date: 15-Jul-2024
https://doi.org/10.1109/NAECON61878.2024.10670639
Açıkkar MTokgöz S(2024)An improved KNN classifier based on a novel weighted voting function and adaptive k-value selectionNeural Computing and Applications10.1007/s00521-023-09272-836:8(4027-4045)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s00521-023-09272-8
Khumukcham RTakhellambam LUrikhimbam BYambem RHoque N(2023)k-NN-SSc: An Effective Similarity Score for k-NN ClassifierAdvanced Computational and Communication Paradigms10.1007/978-981-99-4284-8_4(43-53)Online publication date: 21-Sep-2023
https://doi.org/10.1007/978-981-99-4284-8_4
Show More Cited By

Recommendations

Persian text classification based on K-NN using wordnet
IEA/AIE'12: Proceedings of the 25th international conference on Industrial Engineering and Other Applications of Applied Intelligent Systems: advanced research in applied artificial intelligence

K-NN is widely used for text classification purpose. Basic K-NN has poor accuracy; other methods should be applied to basic K-NN to improve accuracy and efficiency. In this paper we propose a method that uses wordnet to increase similarity of documents ...
Improved classification with allocation method and multiple classifiers

We propose a new allocation method for building a classification ensemble.Allocation method uses multiple classifiers: the allocator and micro classifiers.Allocator separates the dataset and allocates them to one of micro classifiers.Allocator is based ...
Differentially private nearest neighbor classification

Instance-based learning, and the k-nearest neighbors algorithm (k-NN) in particular, provide simple yet effective classification algorithms for data mining. Classifiers are often executed on sensitive information such as medical or personal data. ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICMLC '17: Proceedings of the 9th International Conference on Machine Learning and Computing

February 2017

545 pages

ISBN:9781450348171

DOI:10.1145/3055635

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

Southwest Jiaotong University

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 February 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

ICMLC 2017

ICMLC 2017: 2017 the 9th International Conference on Machine Learning and Computing

February 24 - 26, 2017

Singapore, Singapore

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
229
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu WRalescu A(2024)The aggregated model for human target classificationNAECON 2024 - IEEE National Aerospace and Electronics Conference10.1109/NAECON61878.2024.10670639(428-432)Online publication date: 15-Jul-2024
https://doi.org/10.1109/NAECON61878.2024.10670639
Açıkkar MTokgöz S(2024)An improved KNN classifier based on a novel weighted voting function and adaptive k-value selectionNeural Computing and Applications10.1007/s00521-023-09272-836:8(4027-4045)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s00521-023-09272-8
Khumukcham RTakhellambam LUrikhimbam BYambem RHoque N(2023)k-NN-SSc: An Effective Similarity Score for k-NN ClassifierAdvanced Computational and Communication Paradigms10.1007/978-981-99-4284-8_4(43-53)Online publication date: 21-Sep-2023
https://doi.org/10.1007/978-981-99-4284-8_4
Zhang CZhong PLiu MSong QLiang ZWang X(2022)Hybrid Metric K-Nearest Neighbor Algorithm and ApplicationsMathematical Problems in Engineering10.1155/2022/82125462022(1-15)Online publication date: 10-Jan-2022
https://doi.org/10.1155/2022/8212546
Sharma MBiswas M(2022)KLT-CRKCN: Hyperspectral Image Classification via Karhunen Loeve Transformation and Collaborative Representation-Based K Closest NeighborWireless Personal Communications: An International Journal10.1007/s11277-021-09292-4123:4(3347-3373)Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1007/s11277-021-09292-4
Robindro KSingh YClinton UTakhellambam LHoque N(2022)CD-KNN: A Modified K-Nearest Neighbor Classifier with Dynamic K ValueApplications of Artificial Intelligence and Machine Learning10.1007/978-981-19-4831-2_62(753-762)Online publication date: 14-Sep-2022
https://doi.org/10.1007/978-981-19-4831-2_62
Papanikolaou MEvangelidis GOugiaroglou S(2021)Dynamic k determination in k-NN classifier: A literature review2021 12th International Conference on Information, Intelligence, Systems & Applications (IISA)10.1109/IISA52424.2021.9555525(1-8)Online publication date: 12-Jul-2021
https://doi.org/10.1109/IISA52424.2021.9555525
Khurana APrakash Verma O(2020)A Fine Tuned Model of Grasshopper Optimization Algorithm with Classifiers for Optimal Text Classification2020 IEEE 17th India Council International Conference (INDICON)10.1109/INDICON49873.2020.9342432(1-7)Online publication date: 10-Dec-2020
https://doi.org/10.1109/INDICON49873.2020.9342432
Mocnik F(2020)An improved algorithm for dynamic nearest-neighbour modelsJournal of Spatial Science10.1080/14498596.2020.173957567:3(411-438)Online publication date: 9-Sep-2020
https://doi.org/10.1080/14498596.2020.1739575
Gou JQiu WYi ZShen XZhan YOu W(2019)Locality constrained representation-based K-nearest neighbor classificationKnowledge-Based Systems10.1016/j.knosys.2019.01.016167:C(38-52)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1016/j.knosys.2019.01.016

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents