基于区分对象对集的快速求核算法  

Quick algorithm for computing core based on discernibility object pair set

作　　者：徐章艳[1] 杨炳儒[2] 宋威[2] 袁鼎荣[1] 

机构地区：[1]广西师范大学计算机系,广西桂林541004 [2]北京科技大学信息工程学院,北京100083

出　　处：《系统工程与电子技术》2008年第4期731-734,共4页Systems Engineering and Electronics

基　　金：国家自然科学基金(60463003);广西省教育厅科研基金(200626)资助课题

摘　　要：为降低基于正区域求核算法的时间复杂度,首先给出了简化决策表和简化差别矩阵及其核的定义。然后给出了简化决策表中条件属性的区分对象对集的定义,并得出区分对象对集与决策表核属性的关系,证明了求决策表的核可以转化到求条件属性的区分对象对集上。再结合简化差别矩阵的核的性质,设计了一个基于区分对象对集的快速求核算法。该算法的时间复杂度优于同类算法的时间复杂度。最后用实例说明了新算法的有效性。For cuting down the time complexity of the algorithm for computing core based on the positive region, the definitions of simplified decision table and simplifed discernibility matrix and the core correspond to simplifed discernibility matrix based on the positive region are first provided. Then the definition of discernibility object pair set of condition attribute in simplified decision table is proposed. At the same time, the relationship between the discernibility object pair set and the core of decision table is obtained. Acoording to this relationshp, it is proved that computing the core of decision table is equal to computing the discernibility object pair set. By considering the property of the core correspond to simplified discernibility matrix, a new algorithm for computing core based on the discernibility object pair set is designed. Its time complexity is better than the time complexity of the same kind of algorithms. Finally, an example is used to illustrate the effectiveness of the new algorithm.

关 键 词：粗糙集 正区域 核 区分对象对集 复杂度 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]