Difference between revisions of "Efficient kNN Classification with Different Numbers of Nearest Neighbors"
Y52wen (talk | contribs)
(→‎Reconstruction)
J27ni (talk | contribs)
(→‎Experiments)
Traditional model-based approaches for classification problem requires to train a model on training observations before predicting test samples. In contrast, the model-free k-Nearest Neighbors (KNNs) method classifies observations with a majority rule approach, labeling each piece of test data based on its k closest training observations (neighbors), meaning normalizing the training data can improve its accuracy a lot. This method has become very popular due to its relatively robust performance given how simple it is to implement. It is robust because the predicted value is only depend on the label of the closest data and that is not significantly affected by outliers.
\end{aligned}$$
<math>l_2</math> regularization is the most commonly used to reduce overfitting for regression, and it is called ridge regression which has a close-form solution where <math>W = (X^TX+\rho I)^{-1}X^TX</math>. However, this objective function with <math>l_2</math> regulairzation does not provide a sparse result. With the goal of increaseing computational efficieny, we Follow the literature and adopt <math>l_1</math> regularization instead:
<math>l_2</math> regularization is the most commonly used to reduce overfitting for regression, and it is called ridge regression which has a close-form solution where <math>W = (X^TX+\rho I)^{-1}X^TX</math>. However, this objective function with <math>l_2</math> regulairzation does not provide a sparse result. With the goal of increaseing computational efficieny, we follow the literature and adopt the <math>l_1</math> regularization instead:
$$\begin{aligned}
The paper contains a lot of efficient plots. There is a set of plots in section Experimental Results on Different Sample Sizes, which not only provide a dynamic change of the effect of feature number on accuracy with different algorithms. With a range of feature number from 10 to 10000, S-kNN and GS-kNN are the two algorithms with highest accuracy in most cases. Also, there is another set of plots which demonstrate the running cost with respect to iterations using different algorithms with different feature numbers. Generally speaking, k*Tree is very stable because its curve does not have too much fluctuation. It can also be discovered that S-kNN's running cost can be pretty tedious given certain iteration and feature number. That is, the performance is not as stable as other algorithms.
== Conclusion ==
This paper introduced two novel approaches for kNN classification algorithms that can determine optimal k-values for each test sample. The proposed kTree and k*Tree methods can classify the test samples efficiently and effectively with a designed training step that reduces the run time of the test stage and thus enhances the performance. Based on the experimental results for varying sample sizes and differing feature numbers, it was observed that the proposed methods outperformed existing ones in terms of running cost while still achieving similar or better classification accuracies. More future areas of investigation could focus on the improvement of kTree and k*Tree for high-dimensional data.
== Critiques ==
*The paper only assessed classification accuracy through cross-validation accuracy. However, it would be interesting to investigate how the proposed methods perform using different metrics, such as AUC, precision-recall curves, or in terms of holdout test data set accuracy.
*The paper only assessed classification accuracy through cross-validation accuracy. However, it would be interesting to investigate how the proposed methods perform using different metrics, such as AUC, precision-recall curves, or in terms of holdout test data set accuracy. In addition, the differences between different methods in classification error vary only by a small amount.
* The authors addressed that some of the UCI datasets contained imbalanced data (such as the Climate and German data sets) while others did not. However, the nature of the class imbalance was not extreme, and the effect of imbalanced data on algorithm performance was not discussed or assessed. Moreover, it would have been interesting to see how the proposed algorithms performed on highly imbalanced datasets in conjunction with common techniques to address imbalance (e.g. oversampling, undersampling, etc.).
*While the authors contrast their kTree and k*Tree approach with different kNN methods, the paper could contrast their results with more of the approaches discussed in the Related Work section of their paper. For example, it would be interesting to see how the kTree and k*Tree results compared to Góra and Wojna varied optimal k method.
* It would be better if the author had provided several paragraphs discussing the complexity of these models. It seems like the highlight of kTree is that it offers similar performance at a significantly lower cost.
* The author should compare the complexity of several different algorithms that gets the optimum k value, and discuss the pros and cons of each approach
* It might be difficult to say k Tree classification is better than kNN. It might require a larger dataset and perform hyperparameter tuning on both methods.
[math]l_2[/math] regularization is the most commonly used to reduce overfitting for regression, and it is called ridge regression which has a close-form solution where [math]W = (X^TX+\rho I)^{-1}X^TX[/math]. However, this objective function with [math]l_2[/math] regulairzation does not provide a sparse result. With the goal of increaseing computational efficieny, we follow the literature and adopt the [math]l_1[/math] regularization instead:
The paper only assessed classification accuracy through cross-validation accuracy. However, it would be interesting to investigate how the proposed methods perform using different metrics, such as AUC, precision-recall curves, or in terms of holdout test data set accuracy. In addition, the differences between different methods in classification error vary only by a small amount.
The author should compare the complexity of several different algorithms that gets the optimum k value, and discuss the pros and cons of each approach
It might be difficult to say k Tree classification is better than kNN. It might require a larger dataset and perform hyperparameter tuning on both methods.