Journal of Frontiers of Computer Science and Technology ›› 2015, Vol. 9 ›› Issue (1): 14-23.DOI: 10.3778/j.issn.1673-9418.1407038

Previous Articles     Next Articles

Fast Reduction Algorithm Research Based on k-Nearest Neighbor Fuzzy Rough Set

ZHANG Zhaoxing1,2, FAN Xingqi1,2, ZHAO Suyun1+, CHEN Hong1,2, LI Cuiping1,2, SUN Hui1,2   

  • Online:2015-01-01 Published:2014-12-31


张照星1,2,范星奇1,2,赵素云1+,陈  红1,2,李翠平1,2,孙  辉1,2   

  1. 1. 中国人民大学 数据工程与知识工程教育部重点实验室,北京 100872
    2. 中国人民大学 信息学院,北京 100872

Abstract: Now a lot of generalized models of rough set are proposed by introducing some parameters to deal with the problems with noise. Traditional reduction algorithms are designed to find the minimum subset which keeps the information invariant. However, there is an obvious weakness that the algorithms have to be executed from the beginning on different parameters. This paper introduces the theoretical results of nested structure into the robust fuzzy rough set (i.e., k-nearest neighbor fuzzy rough sets), and then designs a fast reduction algorithm based on given reduction by using the nested structure. The main contribution of the proposed algorithm is that it can quickly find a reduction on different parameters when one reduction on certain parameter is already given. The numerical experiments verify that the executing time can be significantly saved through using fast reduction algorithm and demonstrate that the proposed algorithm is feasible and effective.

Key words: k-nearest neighbor fuzzy rough set, attribute reduction, nested structure

摘要: 目前有很多粗糙集的推广模型通过引入参数的方法处理含有噪音的实际问题。基于粗糙集推广模型的约简算法可以发现保持信息含量不变的最小属性子集,但是其明显的不足是计算不同参数上的约简时,每次都要从头开始执行。将嵌套结构的理论结果应用于k-近邻模糊粗糙集的快速约简算法设计中,并利用嵌套结构,设计了一个基于已有约简的快速约简算法。该算法的特点是在参数改变时,不必重新运行经典的算法,而是利用已有的约简来计算新的约简。数值实验验证了快速约简算法可以显著地节省运行时间,表明了该算法的可行性和有效性。

关键词: k-近邻模糊粗糙集, 属性约简, 嵌套结构