针对近邻法分类需要大量计算和存储的缺点,提出了一种改进的样本挑选算法(different iterative case filtering,DICF).该算法首先评价每个样本的分类能力,据此不断删除分类能力弱的样本,迭代执行此过程,直到压缩子集不再变小为止. 经分析得出DICF算法时间复杂度为O(n~2). 在真实数据库上的实验结果表明,通过DICF算法得到的压缩集在压缩比、分类精度上均优于MCS,ICF, ENN等经典算法.
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.
[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).
