Source-linked AI summary
Solving the Problem of the K Parameter in the KNN Classifier Using an Ensemble Learning Approach
Ahmad Basheer Hassanat, Mohammad Ali Abbadi, Ghada Awad Altarawneh, Ahmad Ali Alhasanat
TL;DR
KNN lacks a universally suitable neighbor count because performance varies with K and data sets favor different values. The paper proposes an ensemble of KNN classifiers using different neighbor counts up to √n and combining their decisions. Experiments report superiority over traditional KNN, competitiveness with other classifiers, and linear time compared with IINC.
Problem
KNN performance varies with K, and different data sets favor different numbers of neighbors, making a universally suitable K difficult to choose.
Method
The proposed method ensembles traditional KNN classifiers using different odd K values from 1 through √n and selects the class receiving the most votes.
Results
The proposed method outperformed all classifiers on 8 data sets, while IINC did so on 9; both had almost the same overall performance.
Takeaways & Limitations
The proposed method avoids selecting a specific K, is competitive with IINC and other classifiers, and has linear time compared with IINC’s logarithmic-linear time.
Abstract
from arXiv · showhide
This paper presents a new solution for choosing the K parameter in the k-nearest neighbor (KNN) algorithm, the solution depending on the idea of ensemble learning, in which a weak KNN classifier is used each time with a different K, starting from one to the square root of the size of the training set. The results of the weak classifiers are combined using the weighted sum rule. The proposed solution was tested and compared to other solutions using a group of experiments in real life problems. The experimental results show that the proposed classifier outperforms the traditional KNN classifier that uses a different number of neighbors, is competitive with other classifiers, and is a promising classifier with strong potential for a wide range of applications.
I. INTRODUCTION
KNN is a simple and efficient classifier, but its performance depends on the distance metric and on selecting a dataset-specific number of neighbors. This study addresses the limited work on removing the need to choose a specific k.
- KNN assigns an unlabelled example the majority label among its k-nearest training examples.Its similarity calculation depends on a specific distance metric.
- The classifier is widely used because it is simple and efficient across pattern recognition, machine learning, text categorization, data mining, and object recognition.Its use of every training example creates memory and time-complexity limitations.
- KNN has no trained output model and uses all training examples for each test, giving it linear time complexity O(n).
- Classification performance depends on choosing an optimal k, and the suitable number of neighbors differs from one data sample to another.
- Prior work mainly addressed KNN’s computational burden by reducing the stored training set through methods such as CNN and RNN.Hashing techniques were also used to increase classification speed.
- The study targets the less-explored problem of eliminating the need to use a specific k with KNN.
II. RELATED WORK
Related work shows that KNN performance varies with k, distance metric, and data distribution, making a universally optimal neighbor count difficult to determine. Existing approaches avoid or reduce this sensitivity through adaptive grouping, informativeness, bootstrap sampling, large k values, or all-neighbor weighting.
- Choosing an optimal K is difficult because KNN performance changes with K and distance metric, especially when examples are not uniformly distributed.
- Guo et al.’s KNN Model groups similar examples and uses each group’s point count as a local optimal k, removing the need to choose one global k.Their experiments used six data sets and also reduced the training-data size.
- LI-KNN and GI-KNN use query-based informativeness as a distance metric and were less sensitive to parameter changes than conventional KNN on 10 data sets.
- Bootstrap-based nearest-neighbor classification outperformed conventional KNN mainly when tested examples were high-dimensional.
- Using large k values such as 30, 45, and 60 was reported as making KNN more stable, but the evidence was associated with text-categorization data sets.The authors caution that this observation cannot be generalized to other data sets and classification problems.
- IINC uses all training-set neighbors, rewarding nearer and penalizing farther neighbors, and was reported to outperform several classifiers in most of 24 benchmark tasks.Its class probabilities are calculated from summed inverted indexes after sorting distances.
III. THE PROPOSED WORK
The proposed classifier combines KNN classifiers using different odd K values up to √n, weighting nearer-neighbor decisions more strongly. It aims to avoid choosing a single K while maintaining approximately linear time complexity and addressing limitations identified in IINC.
- Addressed limitations: The method retains three stated IINC limitations: it cannot reduce the training set, can favor larger classes, and requires sorting distances in at least O(nlogn) time.These limitations motivate the proposed method’s use of only the square root of the nearest neighbors and its compatibility with training-set reduction methods.
- Ensemble design: The method ensembles KNN classifiers with odd K values from 1 through √n and combines their votes using a weighted sum rule.The maximum K follows a rule of thumb based on the square root of the training-set size, while limiting computation.
- Weighting strategy: The weighted sum gives greater influence to classifiers using nearer neighbors through an inverted logarithmic weighting function.The paper reports that this weighting function was selected empirically, and Figure 1 illustrates it.
- Classification procedure: For a test example, the algorithm computes distances, retains the √n nearest classes, accumulates class weight sums across odd K values, and predicts the class with the maximum sum.Algorithm 1 initializes class weight sums and updates them for each odd K and each included neighbor.
- Classification procedure: The illustrative example uses 1-NN, 3-NN, and 5-NN within the ensemble and predicts the unknown point as class 1.The example contains 25 training points in a two-dimensional feature space and one test point.
- Complexity: The proposed classifier is approximated as O(n), whereas IINC is reported as O(n log n), because the proposed method uses only the first √n nearest distances.The paper notes that a naïve repeated search for minimum distances would instead cost O(n√n).
IV. RESULTS AND DISCUSSION
Experiments on 28 UCI real-life classification data sets show that the proposed method generally performs better than the compared classifiers while avoiding a fixed k choice. Its performance is close to IINC overall, with lower time complexity and compatibility with training-set reduction methods.
- Experimental setup: 28 UCI data sets were used to compare the proposed classifier with nine alternatives, including traditional KNN choices and IINC.Each data set used 30% randomly selected test examples, and each experiment was repeated 10 times.
- K selection: No single k value performed best across all data sets, supporting the need to combine classifiers using different neighbor counts.The experiments found that each data set favored a specific number of neighbors.
- K selection: Using k = √n as a rule of thumb did not yield excellent results, and large values such as k = 30, 45, and 60 did not improve accuracy in these experiments.The authors caution that findings about large k values from text categorization data sets may not generalize to other classification problems.
- Overall performance: The proposed method generally performed better than the other classifiers and did not require selecting a specific k.The paper attributes this performance to ensemble learning that combines weak classifiers into a stronger one.
- Overall performance: The proposed classifier outperformed all classifiers on 8 data sets, while IINC did so on 9 data sets.Despite this difference, the two methods had almost the same performance overall.
- Computational considerations: The proposed method has linear time complexity versus IINC’s logarithmic-linear complexity and can benefit from CNN or RNN training-set reduction.IINC requires sorting distances and using all training examples, whereas the proposed method uses only the square root of the nearest neighbors.
V. CONCLUSION AND FUTURE WORK
The proposed classifier uses an ensemble of KNN classifiers with different neighbor counts to avoid selecting a single K value. Experiments on real-life datasets showed superiority over traditional KNN, competitiveness with other classifiers, and an opportunity for future complexity improvements.
- The method combines traditional KNN classifiers using different numbers of neighbors to determine the final decision.
- Experiments on varied real-life datasets demonstrated superiority over traditional KNN classifiers using different k values.
- The proposed method was competitive with other classifiers, including the IINC classifier.
- The proposed method had linear-time speed, reported as better than IINC's logarithmic linear time.
- Future work could enhance the proposed method's time complexity using KD-trees or hashing techniques.