Leveraging k-NN for generic classification boosting

被引:13
作者
Piro, Paolo [1 ]
Nock, Richard
Nielsen, Frank [2 ,3 ,4 ]
Barlaud, Michel [1 ]
机构
[1] Univ Nice Sophia Antipolis, CNRS, Nice, France
[2] Ecole Polytech, LIX, F-91128 Palaiseau, France
[3] Ecole Polytech, Comp Sci Lab, F-91128 Palaiseau, France
[4] Ecole Polytech, CS Dept, F-91128 Palaiseau, France
关键词
Boosting; k-NN classification; Surrogate risks; NEAREST-NEIGHBOR CLASSIFICATION; ALGORITHMS;
D O I
10.1016/j.neucom.2011.07.026
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Voting rules relying on k-nearest neighbors (k-NN) are an effective tool in countless many machine learning techniques. Thanks to its simplicity, k-NN classification is very attractive to practitioners, as it enables very good performances in several practical applications. However, it suffers from various drawbacks, like sensitivity to "noisy" instances and poor generalization properties when dealing with sparse high-dimensional data. In this paper, we tackle the k-NN classification problem at its core by providing a novel k-NN boosting approach. Namely, we propose a supervised learning algorithm, called Universal Nearest Neighbors (UNN), that induces a leveraged k-NN rule by globally minimizing a surrogate risk upper bounding the empirical misclassification rate over training data. Interestingly, this surrogate risk can be arbitrary chosen from a class of Bregman loss functions, including the familiar exponential, logistic and squared losses. Furthermore, we show that UNN allows to efficiently filter a dataset of instances by keeping only a small fraction of data. Experimental results on the synthetic Ripley's dataset show that such a filtering strategy is able to reject "noisy" examples, and yields a classification error close to the optimal Bayes error. Experiments on standard UCI datasets show significant improvements over the current state of the art. (C) 2011 Elsevier B.V. All rights reserved.
引用
收藏
页码:3 / 9
页数:7
相关论文
共 15 条
[1]  
[Anonymous], 2007, P INT C MACH LEARN I
[2]  
ASUNCION A, 2007, UCI REPOSITORY
[3]   Convexity, classification, and risk bounds [J].
Bartlett, PL ;
Jordan, MI ;
McAuliffe, JD .
JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 2006, 101 (473) :138-156
[4]   Advances in instance selection for instance-based learning algorithms [J].
Brighton, H ;
Mellish, C .
DATA MINING AND KNOWLEDGE DISCOVERY, 2002, 6 (02) :153-172
[5]   NEAREST NEIGHBOR PATTERN CLASSIFICATION [J].
COVER, TM ;
HART, PE .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1967, 13 (01) :21-+
[6]   A Bayesian Reassessment of Nearest-Neighbor Classification [J].
Cucala, Lionel ;
Marin, Jean-Michel ;
Robert, Christian P. ;
Titterington, D. M. .
JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 2009, 104 (485) :263-273
[7]   CONDENSED NEAREST NEIGHBOR RULE [J].
HART, PE .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1968, 14 (03) :515-+
[8]   Likelihood inference in nearest-neighbour classification models [J].
Holmes, CC ;
Adams, NM .
BIOMETRIKA, 2003, 90 (01) :99-112
[9]   Bregman Divergences and Surrogates for Learning [J].
Nock, Richard ;
Nielsen, Frank .
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2009, 31 (11) :2048-2059
[10]  
Quinlan J. R., 1986, Machine Learning, V1, P81, DOI 10.1007/BF00116251