Journal of Computers, Vol 6, No 7 (2011), 1493-1500, Jul 2011
doi:10.4304/jcp.6.7.1493-1500

A Modified Editing k-nearest Neighbor Rule

Ruiqin Chang, Zheng Pei, Chao Zhang

Abstract


Classification of objects is an important area in a variety of fields and applications. Many different methods are available to make a decision in those cases. The k-nearest neighbor rule (k-NN) is a well-known nonparametric decision procedure. Classification rules based on the k-NN have already been proposed and applied in diverse substantive areas. The editing k-NN proposed by Wilson would be an important one. In this rule, editing the reference set is first performed, every sample in the reference set is classified by using the k-NN rule and the set is formed by eliminating it from the reference set. All the samples mistakenly classified are then deleted from the reference set. Afterward, any input sample is classified using the k-NN rule and the edited reference set. Obviously, the editing k-nearest neighbors classifier (EK -NN) consists of the k-nearest neighbor classifier and an editing reference set. However, the editing reference set gained by this method is only a subset of the reference set. This may result in the loss of some important information and decline of classification accuracy. In this paper, we focus on modifying the editing reference set of EK -NN, the new editing set in our method consists of subsets of the reference set and testing set, such subsets are received by classifying every sample in the reference set and testing set by using the k-NN rule and removing misclassified samples from reference set and testing set, respectively. Advantages of our method are to reduce the loss of information and improve the recognition rate. Comparisons and analysis of the experimental results demonstrate the capability of the proposed algorithm.


Keywords


k-nearest neighbors classifier; editing technique; reference set; testing set; training set

References


[1] E. Fix and J. L. Hodges, “Discriminatory analysis, nonparametric discrimination, consistency properties,” U.S. Air Force Sch. Aviation Medicine, Randolf Field, Texas, Project 21-49-004, Contract AF 41(128)-31, Rep. 4, 1951.

[2] D. L. Wilson, “Asymptotic properties of nearest neighbor rules using editing data,” IEEE Trans. Syst., Man, Cybern, vol. SMC-2, Issue. 3, pp. 408-421, 1972.
http://dx.doi.org/10.1109/TSMC.1972.4309137

[3] T. M. Cover, P. E. Hart, “Nearest neighbor pattern classification,” IEEE Transaction on Information Theory, vol. IT-IS, pp. 21-27, 1967.

[4] L. Devroye, “On the asymptotic probability of error in nonparametric discrimination,” Ann. Statist., vol. 9, Issue. 6, pp. 1320–1327, 1981.
http://dx.doi.org/10.1214/aos/1176345648

[5] K. Urahama and T. Nagao, “Analog circuit implementation and learning algorithm for nearest neighbor classifiers,” Pattern Recognit. Lett., vol. 15, pp. 723–730, 1994.
http://dx.doi.org/10.1016/0167-8655(94)90077-9

[6] T. J. Wanger, “Convergence of the nearest neighbor rule,” IEEE Trans. Inform. Theory, vol. 17, pp. 566–571, 1971.
http://dx.doi.org/10.1109/TIT.1971.1054698

[7] H. Yan, “Prototype optimization for nearest neighbor classifiers using a two-layer perception,” Pattern Recognit., vol. 26, pp. 17–324, 1993.
http://dx.doi.org/10.1016/0031-3203(93)90040-4

[8] M. S. Yang, C. H. Chen, “On the Editing Fuzzy k-Nearest Neighbor Rule,” IEEE Trans. Systems, Man, And Cybernetics—Part B: Cybernetics, vol. 28(3), pp. 461–466, 1998.
PMid:18255963

[9] H. Frigui, P. Gader, “Detection and Discrimination of Land Mines in Ground-Penetrating Radar Based on Edge Histogram Descriptors and a Possibilistic k-Nearest Neighbor Classifier,” IEEE Trans. Fuzzy Systems, vol. 17(1), pp. 185–199, 2009.
http://dx.doi.org/10.1109/TFUZZ.2008.2005249

[10] Y. Wu, K. Ianakiev, V. Govindaraju, “Improved k-nearest neighbor classification,” Pattern Recognition, vol. 35, pp. 2311–2318, 2002.
http://dx.doi.org/10.1016/S0031-3203(01)00132-7

[11] N. A. Samsudin, A. P. Bradley, “Nearest neighbour group-based classification,” Pattern Recognition, doi: 10.1016/j.patcog. 2010.
http://dx.doi.org/10.1016/j.patcog

[12] K. Hattori, M. Takahashi, “A new editing k-nearest neighbor rule in the pattern classi"cation problem,” Pattern Recognition, vol. 33, pp. 521-528, 2000.
http://dx.doi.org/10.1016/S0031-3203(99)00068-0

[13] G. Rubio, L. J. Herrera, H. Pomares, I. Rojas, A. Guillen, “Design of specific-to-problem kernels and use of kernel weighted K-nearest neighbours for time series modelling”, Neurocomputing, vol. 73, pp. 1965–1975, 2010.
http://dx.doi.org/10.1016/j.neucom.2009.11.029

[14] D. Li, H. Gu, L. Zhang, “A fuzzy c-means clustering algorithm based on nearest-neighbor intervals for incomplete data,” Expert Systems with Applications, vol: 37, pp. 6942–6947, 2010.

[15] H. Seker,M. O. Odetayo, D. Petrovic, and R. N. G. Naguib, “A Fuzzy Logic Based-Method for Prognostic Decision Making in Breast and Prostate Cancers,” IEEE Transactions on Information Technology in Biomedicine, vol. 7, 2003.

[16] R. Ostermark, “A fuzzy vector valued KNN-algorithm for automatic outlier detection,” Applied Soft Computing, vol. 9, pp. 1263–1272, 2009.
http://dx.doi.org/10.1016/j.asoc.2009.03.009

[17] X. Song, Y. Zheng, X. Wu, X. Yang, J. Yang, “A complete fuzzy discriminant analysis approach for face recognition,” Applied Soft Computing, vol. 10, pp: 208–214, 2010.
http://dx.doi.org/10.1016/j.asoc.2009.07.002

[18] S. Rasheed, D. Stashuk, M. Kamel, “Adaptive fuzzy k-NN classifier for EMG signal decomposition,” Med. Eng. Phys., pp. 694–709, 2006.
http://dx.doi.org/10.1016/j.medengphy.2005.11.001

[19] M. Z. Jahromi, E. Parvinnia, R. John, “A method of learning weighted similarity function to improve the performance of nearest neighbor,” Information Sciences, vol. 179, pp: 2964–2973, 2009.
http://dx.doi.org/10.1016/j.ins.2009.04.012

[20] V. Suresh Babua, P. Viswanathb, “Rough-fuzzy weighted k-nearest leader classifier for large data sets,” Pattern Recognition, vol. 42, pp. 1719 – 1731, 2009.
http://dx.doi.org/10.1016/j.patcog.2008.11.021

[21] R. Gil-Pita, X. Yao, “Using a Genetic Algorithm for Editing k-Nearest Neighbor Classifiers,” Springer Verlag Berlin Heideberg, LNCS, vol. 4881, pp. 114-1150, 2007.

[22] M. Govindarajan, RM. Chandrasekaran, “Evaluation of k-Nearest Neighbor classifier performance for direct marketing,” Expert Systems with Applications, vol. 37, pp. 253–258, 2010.
http://dx.doi.org/10.1016/j.eswa.2009.04.055

[23] Ricardo Fraiman, Ana Justel, Marcela Svarc, “Pattern recognition via projection-based k-NN reles,” Computational Statistics & Data Analysis, vol. 54, pp. 257-263, May 2010.
http://dx.doi.org/10.1016/j.csda.2009.12.009


Full Text: PDF


Journal of Computers (JCP, ISSN 1796-203X)

Copyright @ 2006-2012 by ACADEMY PUBLISHER – All rights reserved.