基于粗糙集技术的压缩近邻规则

摘要：

近邻(Nearest Neighbor,NN)算法是一种简单实用的监督分类算法.但NN算法在分类未知类标的样例时,需要存储整个训练集,还要计算该样例到训练集中每一个样例之间的距离,所以NN算法的计算复杂度非常高.为了克服这一缺点,P.Hart提出了压缩近邻(Condensed Nearest Neighbor,CNN)规则算法,即从整个训练集中找原样例集的一致子集(一致子集是能正确分类训练集中其他样例的子集).其计算复杂度依然比较高,特别是对于大型数据库,寻找其一致子集是非常耗费时间的.针对这一问题,提出了基于粗糙集技术的压缩近邻规则算法.该算法分为3步,首先利用粗糙集方法求属性约简(特征选择),以将冗余的属性去掉.然后选取靠近边界域的样例,以将冗余的样例去掉.最后从选出的样例中计算一致子集.该算法能同时沿垂直方向和水平方法进行数据约简.实验结果显示,所提出的方法是行之有效的.

关键词：近邻规则、一致集、样例选择、粗糙集、边界域

所属期刊栏目：39

分类号：TP181(自动化基础理论)

资助基金：国家自然科学基金项目60903088;河北省自然科学基金项目及河北省高校科技重点基金项目F2010000323,ZD2010139

在线出版日期：2012-04-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：236-239