A New Iterative Algorithm Based for Sample Selection

doi:10.3969/j.issn.1000-1565.2009.06.022

Abstract

Abstract: To overcome the drawbacks that nearest neighbour classification requires huge computation and memory storage, this paper proposes a improved algorithm (different iterative case filtering,DICF). In this algorithm, a set of samples with the poor classification ability is removed from the training set in each iteration until the training set is no longer getting smaller. It can be seen from analysis that time complexity of DICF is O (n~2). The experimental results on some real data sets demonstrate the effectiveness and the feasibility of the proposed algorithm. Compared to traditional methods, such as MCS,ICF and ENN, the condensed sets obtained by DICF is superior in storage and classification accuracy.

Key words: nearest neighbor, iterative case filtering, minimal consistent set

CLC Number:

TP312

LIU Chun-rong,WU Bo. A New Iterative Algorithm Based for Sample Selection[J]. Journal of Hebei University (Natural Science Edition), 2009, 29(6): 653-657.

References

[1] 张鸿宾, 孙广煜, ZHANG Hong-bin, SUN Guang-yu. 近邻法参考样本集的最优选择 [J]. 电子学报 2000.doi:10.3321/j.issn:0372-2112.2000.11.005
[2] Dasarathy B.V.. Minimal consistent set (MCS) identification for optimal nearest neighbor decision systems design [J]. IEEE transactions on systems, man, and cybernetics 1994, 3(3).
[3] DASARATHY B V. Nearest neighbor (NN) norms:NN pattern classification techniques [M]. Los Alamitos.CA:IEEE Computer Society Press 1991.
[4] HART P E. The condensed nearest neighbor rule [J]. IEEE Transactions on Systems Man and Cybernetics 1968, IT214(03).
[5] GATES G W. The reduced nearest neighbor rule [J]. IEEE Transactions on Information theory 1972, IT218(03).
[6] WILSON D L. Asymptotic properties of nearest neighbor rules using edited data [J]. IEEE Transactions on Systems Man and Cybernetics 1972, SMC-2(03).
[7] SWONGER C W. Sample set condensation for a condensed nearest neighbor decision rule for pattern recognition [J]. Frontiers of Pattern Recognition 1972, 8(02).
[8] ULLMANN J R. Automatic selection of reference data for use in a nearest neighbor method of pattern classification [J]. IEEE Transactions on Information theory 1974, IT-20(04).
[9] CHANG C L. Finding prototypes for nearest neighbor classifiers [J]. IEEE Transaction on Computer 1974, c223(11).
[10] RITTER G L, WOODRUFF H B, LOWRY S R. An algorithm for a selective nearest neighbor decision Rule [J]. IEEE Transactions on Information theory 1975, IT-21(06).
[11] TOMEK I. Two modifications of CNN [J]. IEEE Transactions on Systems Man and Cybernetics 1976, SMC-6(11).
[12] GOWDA K C, KRISHNA G. The condensed nearest neighbor rule using the concept of mutual nearest neighborhood [J]. IEEE Transactions on Systems Man and Cybernetics 1979, IT-25(04).
[13] Bezdek J.C., Reichherzer T.R.. Multiple-prototype classifier design [J]. IEEE transactions on systems, man and cybernetics, Part C. Applications and reviews: A publication of the IEEE Systems, Man, and Cybernetics Society 1998, 1(1).
[14] Henry Brighton, Chris Mellish. Advances in Instance Selection for Instance-Based Learning Algorithms [J]. Data mining and knowledge discovery 2002, 2(2).
[15] Cano, J.R., Herrera, F., Lozano, M.. Using evolutionary algorithms as instance selection for data reduction in KDD: an experimental study [J]. IEEE transactions on evolutionary computation 2003, 6(6).
[16] ANGIULLI F. Fast condensed nearest neighbor rule [A]. BONN, GERMANY 2005.
[17] Angiulli Fabrizio. Fast Nearest Neighbor Condensation for Large Data Sets Classification [J]. IEEE Transactions on Knowledge and Data Engineering 2007, 11(11).