一种改进的迭代样本挑选算法

doi:10.3969/j.issn.1000-1565.2009.06.022

河北大学学报(自然科学版) ›› 2009, Vol. 29 ›› Issue (6): 653-657.DOI: 10.3969/j.issn.1000-1565.2009.06.022

一种改进的迭代样本挑选算法

刘春荣,吴博

河北大学,数学与计算机学院,河北,保定,071002

出版日期:2009-11-25 发布日期:2009-11-25
基金资助:
河北省教育厅科学研究计划支持项目

A New Iterative Algorithm Based for Sample Selection

LIU Chun-rong,WU Bo

Online:2009-11-25 Published:2009-11-25

摘要/Abstract

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

关键词: 近邻法, iterative case filtering, minimal consistent set

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

中图分类号:

TP312

刘春荣,吴博. 一种改进的迭代样本挑选算法[J]. 河北大学学报(自然科学版), 2009, 29(6): 653-657.

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.

参考文献

[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).

一种改进的迭代样本挑选算法

A New Iterative Algorithm Based for Sample Selection

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价