On kernel difference-weighted k-nearest neighbor classification
Tóm tắt
Nearest neighbor (NN) rule is one of the simplest and the most important methods in pattern recognition. In this paper, we propose a kernel difference-weighted k-nearest neighbor (KDF-KNN) method for pattern classification. The proposed method defines the weighted KNN rule as a constrained optimization problem, and we then propose an efficient solution to compute the weights of different nearest neighbors. Unlike traditional distance-weighted KNN which assigns different weights to the nearest neighbors according to the distance to the unclassified sample, difference-weighted KNN weighs the nearest neighbors by using both the correlation of the differences between the unclassified sample and its nearest neighbors. To take into account the effective nonlinear structure information, we further extend difference-weighted KNN to its kernel version KDF-KNN. Our experimental results indicate that KDF-WKNN is much better than the original KNN and the distance-weighted KNN methods, and is comparable to or better than several state-of-the-art methods in terms of classification accuracy.
Tài liệu tham khảo
Aha DW, Kibler D, Albert MK (1991) Instance-based learning algorithms. Mach Learn 6:37–66
Atiya AF (2005) Estimating the posterior probabilities using the K-nearest neighbor rule. Neural Comput 17:731–740
Bailey T, Jain AK (1978) A note on distance-weighted k-nearest neighbor rules. IEEE Trans Syst Man Cybern 8:311–313
Beygelzimer A, Kakade S, Langford J (2006) Cover trees for nearest neighbor. In: International conference on machine learning
Blake CL, Merz CJ (1998) UCI repository of machine learning databases, Department of Information and Computer Sciences, University of California, Irvine. http://www.ics.uci.edu/mlearn/MLRepository.html
Dasarathy BV (1991) Nearest neighbor (NN) norms: NN pattern classification techniques. IEEE Computer Society Press, Los Alamitos
Demšar J (2006) Statistical comparisons of classifiers over multiple data sets. J Mach Learn Res 7:1–30
Domeniconi C, Peng J, Gunopulos D (2002) Locally adaptive metric nearest neighbor classification. IEEE Trans Pattern Anal Mach Intell 24:1281–1285
Duda RO, Hart PE, Stork DG (2001) Pattern classification, 2nd edn. Wiley, London
Dudani SA (1976) The distance-weighted k-nearest-neighbor rule. IEEE Trans Syst Man Cybern 6:325–327
Fix E, Hodges JL (1951) Discriminatory analysis:nonparametric discrimination:consistency properties. USAF School of Aviation Medicine, Project 21-49-004, Report No. 4:261–279
Fukunaga K, Flick TE (1984) An optimal global nearest neighbor metric. IEEE Trans Pattern Anal Mach Intell 6:314–318
Hastie T, Tibshirani R (1996) Discriminant adaptive nearest neighbor classification. IEEE Trans Pattern Anal Mach Intell 18:607–616
Hastie T, Tibshirani R, Friedman J (2001) The elements of statistical learning: data mining, inference, and prediction. Springer, New York
Herrero JR, Navarro JJ (2007) Exploiting computer resources for fast nearest neighbor classification. Pattern Anal Appl 10:265–275
Keller JM, Gray MR, Givens Jr. JA (1985) A fuzzy k-nearest neighbor algorithm. IEEE Trans Syst Man Cybern 15:580–585
Kuncheva LI, Bezdek JC (1998) Nearest prototype classification clustering, genetic algorithms, or random search. IEEE Trans Syst Man Cybern C 28:160–164
Kuncheva LI, Bezdek JC (1999) Presupervised and postsupervised prototype classifier design. IEEE Trans Neural Netw 10:1142–1152
Lam W, Keung CK, Liu D (2002) Discovering useful concept prototypes for classification based on filtering and abstraction. IEEE Trans Pattern Anal Mach Intell 24:1075–1090
Macleod JES, Luk A, Titterington DM (1987) A re-examination of the distance-weighted k-nearest neighbor classification rule. IEEE Trans Syst Man Cybern 17:689–696
Morin RL, Raeside DE (1981) A reappraisal of distance-weighted k-nearest neighbor classification for pattern recognition with missing data. IEEE Trans Syst Man Cybern 11:241–243
Müller KR, Mika S, Rätsch G, Tsuda K, Schölkopf B (2001) An introduction to kernel-based learning algorithms. IEEE Trans Neural Netw 12:181–202
Paredes R, Vidal E (2006) Learning prototypes and distances: a prototype reduction technique based on nearest neighbor error minimization. Pattern Recognit 39:180–188
Paredes R, Vidal E (2006) Learning weighted metrics to minimizing nearest-neighbor classification error. IEEE Trans Pattern Anal Mach Intell 28:1100–1110
Peng J, Heisterkamp DR, Dai H (2004) Adaptive quasiconformal kernel nearest neighbor classification. IEEE Trans Pattern Anal Mach Intell 26:656–661
Ricci F, Avesani P (1999) Data compression and local metrics for nearest neighbor classification. IEEE Trans Pattern Anal Mach Intell 21:380–384
Roweis ST, Saul LK (2000) Nonlinear dimensionality reduction by locally linear embedding. Science 290:2323–2326
Saul LK, Roweis ST (2003) Think globally, fit locally: unsupervised learning of low dimensional manifolds. J Mach Learn Res 4:119–155
Shakhnarovich G, Darrell T, Indyk P (2006) Nearest-neighbor methods in learning and vision: theory and practice. MIT press, Cambridge
Sheskin DJ (2004) Handbook of parametric and nonparametric statistical procedures, 3rd edn. Chapman & Hall/CRC, Boca Raton
Short RD, Fukunaga K (1984) The optimal distance measure for nearest neighbor classification. IEEE Trans Inf Theory 27:622–627
Toh KA, Tran QL, Srinivasan D (2004) Benchmarking a reduced multivariate polynomial pattern classifier. IEEE Trans Pattern Anal Mach Intell 26(6):740–755
Tran QL, Toh KA, Srinivasan D, Wong KL, Low SQ (2005) An empirical comparison of nine pattern classifiers. IEEE Trans Syst Man Cybern B 35:1079–1091
Vapnik VN (1998) Statistical learning theory. Wiley, New York
Zar JH (1999) Biostatistical analysis, 4th edn. Prentice Hall, Upper Saddle River
Zavrel J (1997) 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