一种适用于不同分类器的样本约简算法

程汝峰，梁永全，刘 彤

(山东科技大学 计算机科学与工程学院，山东 青岛 266590)

一种适用于不同分类器的样本约简算法

程汝峰，梁永全，刘 彤

(山东科技大学 计算机科学与工程学院，山东 青岛 266590)

现有的样本约简算法多数是针对某种分类器设计的，在实际应用中有一定的局限性。结合聚类算法的思想，设计了一种适用于不同分类器的样本约简算法，核心是选取密度高且距离相对较远的样本点。与其他样本约简算法相比较，该算法可以根据需求获得任意大小的样本子集，并适用于多种分类算法；而对包含噪声点的样本集，算法的分类精度和稳定性均有一定程度的提高。

样本约简；准则；密度；样本子集

一般来说，不同样本的重要程度是不同的。一些冗余和噪音数据不仅造成大量的存储耗费，而且还会影响学习精度。因此更倾向于根据一定的性能标准，选择代表性样本形成原样本空间的一个子集，之后在这个子集上进行学习。在保持某些性能的基础上，最大限度地降低时间、空间的耗费。

样本约简算法根据性能的要求大致可分为增强型、保持型和混合类型三类。增强型算法的代表有ENN(edited nearest neighbor)[1]、RENN(repeated ENN)[2]、AKNN(aggregate k nearest neighbor)[3]等；保持型算法的代表有CNN(condensed nearest neighbor)[4]、RNN(reduced nearest neighbor)[5]、MCS(minimal consistent set)[6]、FCNN(fast nearest neighbor condensation)[7]等；混合型算法的代表性工作有ICF(iterative case filtering algorithm)[8]、DROP3(decremental reduction optimization procedure)[9]等。文献[10]和文献[11]对样本约简算法进行了很好的综述。

近几年，研究者尝试用不同的方法来实现样本约简。针对支持向量机，Chen等[12]提出一种可以加速支持向量机训练的样本约简算法；针对贝叶斯分类器，Pabitra等[13]提出一种多尺度的样本约简算法；……