Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (29): 146-149.DOI: 10.3778/j.issn.1002-8331.2008.29.041

• 数据库、信号与信息处理 • Previous Articles     Next Articles

Efficient attribute reduction algorithm based on ordered discernibility set

YANG Chuan-jian1,GE Hao2   

  1. 1.Department of Computer Science,Chuzhou University,Chuzhou,Anhui 239012,China
    2.Department of Electronic and Information Engineering,Chuzhou University,Chuzhou,Anhui 239012,China
  • Received:2008-04-23 Revised:2008-07-21 Online:2008-10-11 Published:2008-10-11
  • Contact: YANG Chuan-jian

基于有序差别集的高效属性约简算法

杨传健1,葛 浩2   

  1. 1.滁州学院 计算机系,安徽 滁州 239012
    2.滁州学院 电子信息工程系,安徽 滁州 239012
  • 通讯作者: 杨传健

Abstract: The algorithm for attribute reduction based on discernibility matrix needs a lot of memory space,and many elements of discernibility matrix are not unnecessary for reduction.The efficiency of the algorithm is not good when the scale of problem is very large.For the above deficiency,an attribute reduction algorithm based on ordered discernibility set is put forward.The algorithm is not need to create the discernibility matrix and generate redundant elements,so it can cut down the storing and the computing capacity greatly,and the efficiency of the algorithm is improved.The time complexity and space complexity of the algorithm are cut down to max{O(|C|2|U/C|2),O(|C|2|MsCount|)} and O(|MsCount|).The experimental results show that the algorithm is effective and efficient.

Key words: rough set, attribute reduction, ordered discernibility set, discernibility matrix

摘要: 基于可分辨矩阵的属性约简算法需要占用大量的存储空间,可分辨矩阵中许多元素项对约简是多余的;并且随着问题规模的增大,该类算法的效率并不理想。针对上述不足,提出一种基于有序差别集的属性约简算法,该算法不需要创建可分辨矩阵和生成多余的元素项,大大降低了存储量和计算量,从而提高了属性约简效率,使算法的时间复杂度和空间复杂度分别降为max{O(|C|2
|U/C|2),O(|C|2|MsCount|)}和O(|MsCount|)。实验表明该算法是有效的、高效的。

关键词: 粗糙集, 属性约简, 有序差别集, 可分辨矩阵