Email this article A Novel Weighted Voting for K-Nearest Neighbor Rule
Abstract
K-nearest neighbor rule (KNN) is the well-known non-parametric technique in the statistical pattern classification, owing to its simplicity, intuitiveness and effectiveness. In this paper, we firstly review the related works in brief and detailedly analyze the sensitivity issue on the choice of the neighborhood size k, existed in the KNN rule. Motivated by the problem, a novel dual weighted voting scheme for KNN is developed. With the goal of overcoming the sensitivity of the choice of the neighborhood size k and improving the classification performance, the proposed classifier mainly employs the dual weighted voting function to reduce the effect of the outliers in the k nearest neighbors of each query object.
To verify the superiority of the proposed classifier, the experiments are conducted on one artificial data set and twelve real data sets, in comparison with the other classifiers. Experimental results suggest that our proposed classifier is an effective algorithm for the classification tasks in many practical situations, owing to its satisfactory classification performance and robustness over a wide range of k.
Keywords
References
[1]E. Fix, and J. L. Hodges, “Discriminatory analysis, nonparametric discrimination: Consistency properties,” Technique Report No. 4, U.S. Air Force School of Aviation Medicine, Randolf Field Texas, 1951
[2]T. M. Cover, and P. E. Hart, “Nearest neighbor pattern classification,” IEEE Transactions on Information Theory, Vol. 13(1), pp. 21-27, 1967.
doi:10.1109/TIT.1967.1053964
[3]T. Wagner, “Convergence of the nearest neighbor rule,” IEEE Transactions on Information Theory, Vol. 17(5), pp. 566-571, 1971.
doi:10.1109/TIT.1971.1054698
[4]T. Hastie, R. Tibshirani and J. Friedman, “The elements of statical learning,” Springer, New York, NY, USA, 2001.
[5]S. A. Dudani, “The Distance-weighted k-Nearest Neighbor Rule,” IEEE Transactions on System, Man, and Cybernetics, Vol. SMC-6, pp. 325-327, 1976.
doi:10.1109/TSMC.1976.5408784
[6]X. D. Wu, V. Kumar et al., “Top 10 algorithms in data mining,” Knowl Inf Syst, Vol. 14, pp. 1-37, 2008.
doi:10.1007/s10115-007-0114-2
[7]Y. Mitani, and Y. A. Hamamoto, “local mean-based nonparametric classifier,” Pattern Recognition Letters, Vol. 27, pp. 1151-1159, 2006 .
doi:10.1016/j.patrec.2005.12.016
[8]Y. Zeng, Y. Yang and L. Zhao, “Pseudo nearest neighbor rule for pattern classification,” Expert Systems with Applications, Vol. 36, pp. 3587-3595, 2009.
doi:10.1016/j.eswa.2008.02.003
[9]J. Wang, P. Neskovic and L. N. Cooper, “Neighborhood size selection in the k-nearest-neighbor rule using statistical confidence,” Pattern Recognition, Vol. 39, pp. 417-423, 2006.
doi:10.1016/j.patcog.2005.08.009
[10]P. Kang and S. Cho, “Locally linear reconstruction for instance-based learning,” Pattern Recognition, Vol. 41, pp. 3507-3518, 2008.
doi:10.1016/j.patcog.2008.04.009
[11]H. G. Lewis, M. Brown and A. R. L. Tatnall, “Incorporating Uncertainty in Land Cover Classification from Remote Sensing Imagery,” Advances in Space Research, Vol. 26(7), pp. 1123-1126, 2000.
doi:10.1016/S0273-1177(99)01128-X
[12]R. N. Shepard, “Toward a universal law of generalization for psychological science,” Science, Vol. 237, pp.1317-1323, 1987.
doi:10.1126/science.3629243
PMid:3629243
[13]J. E. S. Macleod, A. Luk and D. M. Titterington, “A re-examination of the distance-weighted k-nearest neighbor classification rule,” IEEE Transactions on System, Man, and Cybernetics, Vol. 17(4), pp. 689-696, 1987.
doi:10.1109/TSMC.1987.289362
[14]J. Zavrel, “An empirical re-examination of weighted voting for K-NN,” In: Daelemans W, Flach P, van den Bosch A (eds) Proceedings of the 7th Belgian-Dutch Conference on Machine Learning, Tilburg, pp 139-148, 1997.
[15]K. Fukunaga, “Introduction to Statistical Pattern Recognition,” second ed. Academic Press, 1990.
[16]A. Frank and A. Asuncion, UCI Machine Learning Repository. Irvine, CA: University of California, School of Information and Computer Science, 2010.
[17]R. O. Duda, P. E. Hart and D. G. Stork, “Pattern classification,” 2ed edition, A Wiley-Interscience Publication, New York, NY, USA, 2001.
Full Text: PDF