Efficient kNN Classification With Different Numbers of Nearest Neighbors
Open accessThe DOI matches its Crossref record; 68 of the 68 references it cites were found in a registry or an index.
Abstract
nearest neighbor (kNN) method is a popular classification method in data mining and statistics because of its simple implementation and significant classification performance. However, it is impractical for traditional kNN methods to assign a fixed value (even though set by experts) to all test samples. Previous solutions assign different values to different test samples by the cross validation method but are usually time-consuming. This paper proposes a kTree method to learn different optimal values for different test/new samples, by involving a training stage in the kNN classification. Specifically, in the training stage, kTree method first learns optimal values for all training samples by a new sparse reconstruction model, and then constructs a decision tree (namely, kTree) using training samples and the learned optimal values. In the test stage, the kTree fast outputs the optimal value for each test sample, and then, the kNN classification can be conducted using the learned optimal value and all training samples. As a result, the proposed kTree method has a similar running cost but higher classification accuracy, compared with traditional kNN methods, which assign a fixed value to all test samples. Moreover, the proposed kTree method needs less running cost but achieves similar classification accuracy, compared with the newly kNN methods, which assign different values to different test samples. This paper further proposes an improvement version of kTree method (namely, k*Tree method) to speed its test stage by extra storing the information of the training samples in the leaf nodes of kTree, such as the training samples located in the leaf nodes, their kNNs, and the nearest neighbor of these kNNs. We call the resulting decision tree as k*Tree, which enables to conduct kNN classification using a subset of the training samples in the leaf nodes rather than all training samples used in the newly kNN methods. This actually reduces running cost of test stage. Finally, the experimental results on 20 real data sets showed that our proposed methods (i.e., kTree and k*Tree) are much more efficient than the compared methods in terms of classification tasks.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“The machine learning-based QC algorithm enables the establishment of non-linear relationships between multi-source data and QC outcomes, facilitating the identification of potentially effective features [24,32,33].”
From A Machine Learning-Based Quality Control Algorithm for Heavy Rainfall Using Multi-Source Data (2025) · cites this paper as [33]
Citations
Cites
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
Top 10 algorithms in data mining
Wu, X., Kumar, V., Ross Quinlan, J., Ghosh, J., Yang, Q., Motoda, H., McLachlan, G. J., Ng, A., Liu, B., Yu, P. S., et al. (2008) · Knowledge and Information Systems · doi:10.1007/s10115-007-0114-2 · Cited by 5,667
Locality Preserving Projections
He, X., & Niyogi, P. (2003) · Cited by 4,119
A survey of decision tree classifier methodology
Safavian, S. R., & Landgrebe, D. (1991) · IEEE Transactions on Systems, Man, and Cybernetics · doi:10.1109/21.97458 · Cited by 3,808
Face recognition using Laplacianfaces
He, X., Yan, S., Hu, Y., Niyogi, P., & Zhang, H.-J. (2005) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2005.55 · Cited by 3,264
Ensemble Methods: Foundations and Algorithms
Zhou, Z.-H. (2012) · doi:10.1201/b12207 · Cited by 2,534
KNN Model-Based Approach in Classification
Guo, G., Wang, H., Bell, D., Bi, Y., & Greer, K. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-39964-3_62 · Cited by 2,099
Ensemble Methods: Foundations and Algorithms
Zhou, Z. (2012) · Cited by 2,051
Tao, D., Tang, X., Li, X., & Wu, X. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.134 · Cited by 879
Self-citationA Nearest Neighbor Bootstrap For Resampling Hydrologic Time Series
Lall, U., & Sharma, A. (1996) · Water Resources Research · doi:10.1029/95wr02966 · Cited by 774
Efficient kNN classification algorithm for big data
Deng, Z., Zhu, X., Cheng, D., Zong, M., & Zhang, S. (2016) · Neurocomputing · doi:10.1016/j.neucom.2015.08.112 · Cited by 603
Self-citationLearning k for kNN Classification
Zhang, S., Li, X., Zong, M., Zhu, X., & Cheng, D. (2017) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/2990508 · Cited by 576
Self-citationNearest neighbor selection for iteratively kNN imputation
Zhang, S. (2012) · Journal of Systems and Software · doi:10.1016/j.jss.2012.05.073 · Cited by 496
Self-citationRobust Joint Graph Sparse Coding for Unsupervised Spectral Feature Selection
Zhu, X., Li, X., Zhang, S., Ju, C., & Wu, X. (2017) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2016.2521602 · Cited by 339
Self-citationBlock-Row Sparse Multiview Multilabel Learning for Image Classification
Zhu, X., Li, X., & Zhang, S. (2016) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2015.2403356 · Cited by 324
Self-citationFeature Learning for Image Classification Via Multiobjective Genetic Programming
Shao, L., Liu, L., & Li, X. (2014) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2013.2293418 · Cited by 324
Self-citationNearest Neighbor Classification of Remote Sensing Images With the Maximal Margin Principle
Blanzieri, E., & Melgani, F. (2008) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2008.916090 · Cited by 288
Missing Value Estimation for Mixed-Attribute Data Sets
Zhu, X., Zhang, S., Jin, Z., Zhang, Z., & Xu, Z. (2011) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2010.99 · Cited by 286
Self-citationLinear cross-modal hashing for efficient multimedia search
Zhu, X., Huang, Z., Shen, H. T., & Zhao, X. (2013) · Proceedings of the 21st ACM international conference on Multimedia · doi:10.1145/2502081.2502107 · Cited by 282
Self-citationLi, X., Pang, Y., & Yuan, Y. (2010) · IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) · doi:10.1109/tsmcb.2009.2035629 · Cited by 271
Self-citationAn adaptive k-nearest neighbor algorithm
Sun, S., & Huang, R. (2010) · 2010 Seventh International Conference on Fuzzy Systems and Knowledge Discovery · doi:10.1109/fskd.2010.5569740 · Cited by 225
A Sparse Embedding and Least Variance Encoding Approach to Hashing
Zhu, X., Zhang, L., & Huang, Z. (2014) · IEEE Transactions on Image Processing · doi:10.1109/tip.2014.2332764 · Cited by 220
Self-citationIKNN: Informative K-Nearest Neighbor Pattern Classification
Song, Y., Huang, J., Zhou, D., Zha, H., & Giles, C. L. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-74976-9_25 · Cited by 211
K-Local Hyperplane and Convex Distance Nearest Neighbor Algorithms
Vincent, P., & Bengio, Y. (2001) · neural information processing systems · Cited by 206
Zhu, X., Suk, H.-I., & Shen, D. (2014) · NeuroImage · doi:10.1016/j.neuroimage.2014.05.078 · Cited by 202 · cited 1×
“In future, we will focus on improving the performance of the proposed methods on high-dimensional data [11], [66]–[68].”
Self-citationNearest neighbors by neighborhood counting
Wang, H. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.126 · Cited by 151
Single Image Super-Resolution With Multiscale Similarity Learning
Zhang, K., Gao, X., Tao, D., & Li, X. (2013) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2013.2262001 · Cited by 139
Self-citationSelf-taught dimensionality reduction on the high-dimensional small-sized data
Zhu, X., Huang, Z. H., Yang, Y., Shen, H. T., Xu, C., & Luo, J. (2012) · Pattern Recognition · doi:10.1016/j.patcog.2012.07.018 · Cited by 135
Self-citationA Novel Template Reduction Approach for the $K$-Nearest Neighbor Method
Fayed, H. A., & Atiya, A. F. (2009) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2009.2018547 · Cited by 132
Shell-neighbor method and its application in missing data imputation
Zhang, S. (2010) · Applied Intelligence · doi:10.1007/s10489-009-0207-6 · Cited by 130
Self-citationSparse hashing for fast multimedia search
Zhu, X., Huang, Z. H., Cheng, H., Cui, J., & Shen, H. T. (2013) · ACM Transactions on Information Systems · doi:10.1145/2457465.2457469 · Cited by 125
Self-citationkNN Algorithm with Data-Driven k Value
Cheng, D., Zhang, S., Deng, Z., Zhu, Y., & Zong, M. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-14717-8_39 · Cited by 123
Self-citationNoisy data elimination using mutual k-nearest neighbor for classification mining
Liu, H., & Zhang, S. (2011) · Journal of Systems and Software · doi:10.1016/j.jss.2011.12.019 · Cited by 120
Self-citationNeighborhood size selection in the k-nearest-neighbor rule using statistical confidence
Wang, J., Neskovic, P., & Cooper, L. N. (2005) · Pattern Recognition · doi:10.1016/j.patcog.2005.08.009 · Cited by 118
Semi-parametric optimization for missing data imputation
Qin, Y., Zhang, S., Zhu, X., Zhang, J., & Zhang, C. (2007) · Applied Intelligence · doi:10.1007/s10489-006-0032-0 · Cited by 115
Self-citationEnsembling Local Learners Through Multimodal Perturbation
Zhou, Z., & Yu, Y. (2005) · IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics) · doi:10.1109/tsmcb.2005.845396 · Cited by 111
A Novel Weighted Voting for K-Nearest Neighbor Rule
Gou, J., Xiong, T., & Yin, K. (2011) · Journal of Computers · doi:10.4304/jcp.6.5.833-840 · Cited by 106
An empirical analysis of the probabilistic K-nearest neighbour classifier
Manocha, S. K., & Girolami, M. (2007) · Pattern Recognition Letters · doi:10.1016/j.patrec.2007.05.018 · Cited by 99
A Unified Learning Framework for Single Image Super-Resolution
Yu, J., Gao, X., Tao, D., Li, X., & Zhang, K. (2014) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2013.2281313 · Cited by 96
Self-citationThe Nearest Neighbor Algorithm of Local Probability Centers
Li, B., Chen, Y. W., & Chen, Y. Q. (2008) · IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics) · doi:10.1109/tsmcb.2007.908363 · Cited by 95
An Adaptable $k$-Nearest Neighbors Algorithm for MMSE Image Interpolation
Ni, K. S., & Nguyen, T. Q. (2009) · IEEE Transactions on Image Processing · doi:10.1109/tip.2009.2023706 · Cited by 95
Liu, D., Chen, H., Yang, B., Lv, X.-E., Li, L., & Liu, J. (2011) · Journal of Medical Systems · doi:10.1007/s10916-011-9815-x · Cited by 91
Matrix-Similarity Based Loss Function and Feature Selection for Alzheimer's Disease Diagnosis
Zhu, X., Suk, H., & Shen, D. G. (2014) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2014.395 · Cited by 91
Self-citationAn Improved k-Nearest Neighbor Algorithm for Text CategorizationPreprint
Li, B., Yu, S., & Lu, Q. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0306099 · Cited by 85
A Novel Locally Linear KNN Method With Applications to Visual Recognition
Liu, Q., & Liu, C. (2017) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2016.2572204 · Cited by 83
Biologically Inspired Features for Scene Classification in Video Surveillance
Huang, K., Tao, D., Yuan, Y., Li, X., & Tan, T. (2010) · IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics) · doi:10.1109/tsmcb.2009.2037923 · Cited by 82
Self-citationMajority voting combination of multiple case-based reasoning for financial distress prediction
Li, H., & Sun, J. (2008) · Expert Systems with Applications · doi:10.1016/j.eswa.2008.05.019 · Cited by 70
Clustering-based Missing Value Imputation for Data Preprocessing
Zhang, C., Qin, Y., Zhu, X., et al. (2006) · 2022 IEEE 20th International Conference on Industrial Informatics (INDIN) · doi:10.1109/indin.2006.275767 · Cited by 61
Self-citationParimputation: From Imputation and Null-Imputation to Partially Imputation
Zhang, S. (2008) · OPUS - Open Publications of UTS Scholars (University of Technology Sydney) · Cited by 61
Self-citationRanking Graph Embedding for Learning to Rerank
Pang, Y., Ji, Z., Jing, P., & Li, X. (2013) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2013.2253798 · Cited by 57
Self-citationTargeting Accurate Object Extraction From an Image: A Comprehensive Study of Natural Image Matting
Zhu, Q., Shao, L., Li, X., & Wang, L. (2014) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2014.2369426 · Cited by 56
Self-citationLearning Instance Correlation Functions for Multilabel Classification
Liu, H., Li, X., & Zhang, S. (2016) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2016.2519683 · Cited by 56
Self-citationMulti-modality Canonical Feature Selection for Alzheimer’s Disease Diagnosis
Zhu, X., Suk, H., & Shen, D. G. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-10470-6_21 · Cited by 52
Self-citationFeature Combination and the kNN Framework in Object Classification
Hou, J., Gao, H., Xia, Q., & Qi, N. (2015) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2015.2461552 · Cited by 51
Consensus of k-NNs for Robust Neighborhood Selection on Graph-Based Manifolds
Premachandran, V., & Kakarala, R. (2013) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2013.209 · Cited by 51
Effective Feature Extraction in High-Dimensional Space
Pang, Y., Yuan, Y., & Li, X. (2008) · IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics) · doi:10.1109/tsmcb.2008.927276 · Cited by 45
Self-citationGóra, G., & Wojna, A. (2002) · Lecture notes in computer science · doi:10.1007/3-540-36755-1_10 · Cited by 44
Cost-sensitive classification with inadequate labeled data
Wang, T., Qin, Z., Zhang, S., & Chengqi Zhang, B. (2011) · Information Systems · doi:10.1016/j.is.2011.10.009 · Cited by 43
Self-citationSpatiochromatic Context Modeling for Color Saliency Analysis
Zhang, J., Wang, M., Zhang, S., Li, X., & Wu, X. (2015) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2015.2464316 · Cited by 40
Self-citationEfficient kNN Algorithm Based on Graph Sparse Reconstruction
Zhang, S., Zong, M., Sun, K., Liu, Y., & Cheng, D. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-14717-8_28 · Cited by 38
Self-citationSahigara, F., Ballabio, D., Todeschini, R., et al. (2014) · Current Computer - Aided Drug Design · doi:10.2174/1573409910666140410110241 · Cited by 34
A Novel Multi-relation Regularization Method for Regression and Classification in AD Diagnosis
Zhu, X., Suk, H., & Shen, D. G. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-10443-0_51 · Cited by 29
Self-citationRobust Sparse Coding for Mobile Image Labeling on the Cloud
Tao, D., Cheng, J. S., Gao, X., Li, X., & Deng, C. D. (2016) · IEEE Transactions on Circuits and Systems for Video Technology · doi:10.1109/tcsvt.2016.2539778 · Cited by 29
Self-citationClustering with the Fisher Score
Tsuda, K., Kawanabe, M., Müller, K., et al. (2003) · Cited by 26
Tailored Aggregation for Classification
Mary‐Huard, T., & Robin, S. S. (2009) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2009.55 · Cited by 26
Cost-sensitive imputing missing values with ordering
Zhu, X., Zhang, S., Zhang, J., et al. (2007) · Cited by 25
Self-citationLarge scale data mining based on data partitioning
Zhang, S., & Wu, X. (2001) · Applied Artificial Intelligence · doi:10.1080/088395101750065732 · Cited by 18
Self-citationNonnegative correlation coding for image classification
Dong, Z., Liang, W. G., Wu, Y., Pei, M., & Jia, Y. (2015) · Science China Information Sciences · doi:10.1007/s11432-015-5289-7 · Cited by 17
Research works printed but not linked: 1
- bahety, 2014, Extension and Evaluation of ID3—Decision Tree Algorithm, Entropy, 2, 1
Cited by
Investigating the impact of data normalization on classification performance
Singh, D., & Singh, B. (2020) · Applied Soft Computing · doi:10.1016/j.asoc.2019.105524 · Cited by 1,726
Halder, R. K., Uddin, M. N., Uddin, M. A., Aryal, S., & Khraisat, A. (2024) · Journal of Big Data · doi:10.1186/s40537-024-00973-y · Cited by 520
Ağbulut, Ü., Gürel, A. E., & Biçen, Y. (2021) · Renewable and Sustainable Energy Reviews · doi:10.1016/j.rser.2020.110114 · Cited by 424
Belete, D. M., & Huchaiah, M. D. (2022) · International Journal of Computers and Applications · doi:10.1080/1206212x.2021.1974663 · Cited by 423
Deep Learning: A Rapid and Efficient Route to Automatic Metasurface Design
Qiu, T., Shi, X., Wang, J., Li, Y., Qu, S., Cheng, Q., Cui, T., & Sui, S. (2019) · Advanced Science · doi:10.1002/advs.201900128 · Cited by 421
Metadata
- Authors
- Zhang, S., Li, X., Zong, M., Zhu, X., & Wang, R.
- Affiliations
- Guangxi Normal University (CN)
- Chinese Academy of Sciences (CN)
- Massey University (NZ)
- Venue
- IEEE Transactions on Neural Networks and Learning Systems
- Published
- 2018-05
- Volume
- 29
- Issue
- 5
- Pages
- 1774-1785
- ISSN
- 2162-237X (ISSN-L)
- 2162-2388
- OpenAlex
- W2606436201
- Cited by
- 1,378
- References
- 68
- Citations by year
- 2026: 91 · 2025: 176 · 2024: 208 · 2023: 216 · 2022: 204 · 2021: 157 · 2020: 132 · 2019: 103 · 2018: 69
- FWCI
- 52.12
- Type
- journal article
- Language
- en
- Open access
- green
- ir.opt.ac.cn
- Locations
- IEEE Transactions on Neural Networks and Learning Systems (publishedVersion)
- PubMed (publishedVersion)
- Institutional Repository of Xi'an Institute of Optics and Fine Mechanics, Chinese Academy of Sciences (Xian Institute of Optics and Precision Mechanics) (submittedVersion, cc-by-nc-sa)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Data Classification
- Physical Sciences › Computer Science › Information Systems › Data Mining and Machine Learning Applications
- Physical Sciences › Computer Science › Artificial Intelligence › Text and Document Classification Technologies
- Keywords
- k-nearest neighbors, sparse reconstruction, decision tree, k-trees
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.