Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (26): 138-141.DOI: 10.3778/j.issn.1002-8331.2010.26.043

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

Efficient algorithm for computing core attributes

GE Hao1,YANG Chuan-jian2,LI Long-shu3   

  1. 1.Department of Electronic and Information Engineering,Chuzhou University,Chuzhou,Anhui 239012,China
    2.Department of Computer Science,Chuzhou University,Chuzhou,Anhui 239012,China
    3.School of Computer Science,Anhui University,Hefei 230039,China
  • Received:2009-02-24 Revised:2010-03-18 Online:2010-09-11 Published:2010-09-11
  • Contact: GE Hao

一种高效的核属性求解算法

葛 浩1,杨传健2,李龙澍3   

  1. 1.滁州学院 电子信息工程系,安徽 滁州 239012
    2.滁州学院 计算机系,安徽 滁州 239012
    3.安徽大学 计算机学院,合肥 230039
  • 通讯作者: 葛 浩

Abstract: The algorithms for computing core have the following shortcomings:The core acquired from these algorithms is not the core based on positive region in inconsistence decision table;the efficiency of these algorithms is not ideal.Aiming at these problems,a new definition of decision table and property of computing core are provided.It is proved that the core acquired from the property is equivalent to the core based on positive region.Then,the computing core algorithm is designed,its time complexity and space complexity are cut down O(|C|2|U|) and O(|U|).Finally,the experimental results show that the algorithm is effective and efficient.

Key words: rough set, inconsistent decision table, core attribute, positive region

摘要: 求核算法主要存在以下不足:对不相容决策表无法获得与正区域一致的核,求核算法的效率不够理想。针对上述问题,首先给出决策表的新定义和求核性质,并证明由该性质获得的核与正区域的核是一致的。然后,设计快速求核算法,其时间复杂度和空间复杂度分别降低为O(|C|2|U|)和O(|U|)。最后,实验验证该算法的有效性和高效性。

关键词: 粗糙集, 不相容决策表, 核属性, 正区域

CLC Number: