A Novel Template Reduction Approach for the K-Nearest Neighbor Method

被引:104
作者
Fayed, Hatem A. [1 ]
Atiya, Amir F. [2 ]
机构
[1] Cairo Univ, Dept Engn Math & Phys, Cairo 12613, Egypt
[2] Cairo Univ, Dept Comp Engn, Cairo 12613, Egypt
来源
IEEE TRANSACTIONS ON NEURAL NETWORKS | 2009年 / 20卷 / 05期
关键词
Condensing; cross validation; editing; K-nearest neighbor (KNN); template reduction; INSTANCE SELECTION; CLASSIFICATION;
D O I
10.1109/TNN.2009.2018547
中图分类号
TP18 [人工智能理论];
学科分类号
140502 [人工智能];
摘要
The K-nearest neighbor (KNN) rule is one of the most widely used pattern classification algorithms. For large data sets, the computational demands for classifying patterns using KNN can be prohibitive. A way to alleviate this problem is through the condensing approach. This means we remove patterns that are more of a computational burden but do not contribute to better classification accuracy. In this brief, we propose a new condensing algorithm. The proposed idea is based on defining the so-called chain. This is a sequence of nearest neighbors from alternating classes. We make the point that patterns further down the chain are close to the classification boundary and based on that we set a cutoff for the patterns we keep in the training set. Experiments show that the proposed approach effectively reduces the number of prototypes while maintaining the same level of classification accuracy as the traditional KNN. Moreover, it is a simple and a fast condensing algorithm.
引用
收藏
页码:890 / 896
页数:7
相关论文
共 27 条
[1]
Combined 5 x 2 cv F test for comparing supervised classification learning algorithms [J].
Alpaydin, E .
NEURAL COMPUTATION, 1999, 11 (08) :1885-1892
[2]
[Anonymous], 2003, Statistical pattern recognition
[3]
Decision boundary preserving prototype selection for nearest neighbor classification [J].
Barandela, R ;
Ferri, FJ ;
Sánchez, JS .
INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE, 2005, 19 (06) :787-806
[4]
BHATTACHARYA BK, 1984, P 16 S INT COMP SCI, P97
[5]
Advances in instance selection for instance-based learning algorithms [J].
Brighton, H ;
Mellish, C .
DATA MINING AND KNOWLEDGE DISCOVERY, 2002, 6 (02) :153-172
[6]
Using evolutionary algorithms as instance selection for data reduction in KDD: An experimental study [J].
Cano, JR ;
Herrera, F ;
Lozano, M .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2003, 7 (06) :561-575
[7]
Devijver P. A., 1980, Proceedings of the 5th International Conference on Pattern Recognition, P72
[8]
Approximate statistical tests for comparing supervised classification learning algorithms [J].
Dietterich, TG .
NEURAL COMPUTATION, 1998, 10 (07) :1895-1923
[9]
Duch W, 2000, CONTROL CYBERN, V29, P937
[10]
Duda R. O., 2000, Pattern classification