基于冲突域的不完备决策表求核算法  

CORE COMPUTING ALGORITHM IN INCOMPLETE DECISION TABLE BASED ON COLLISION DOMAIN

作　　者：章晨光[1] 徐章艳[1] 周建华[1] 

机构地区：[1]广西师范大学计算机科学与信息工程学院,广西桂林541004

出　　处：《计算机应用与软件》2013年第10期45-48,80,共5页Computer Applications and Software

基　　金：国家自然科学基金项目(60963008);广西自然科学基金项目(2011GXNSFA018163)

摘　　要：求核是粗糙集理论中的重要研究之一。近年来在不完备决策表中的求核算法相对较少。通过对葛浩引入冲突域的概念进行研究,设计一种在不完备决策表中的新的求核算法。该算法主要是在容差关系下以冲突域中冲突对象数目的变化为衡量标准来判断核属性,并且通过理论证明了基于冲突域所求出的核属性与基于正区域求出的核属性是等价的。通过对新算法的分析,其时间复杂度为O(|K||C|2|U|)(|K|=max{|T C(x)||x∈U}),空间复杂度为O(|U|)。最后通过实例和仿真实验说明该算法是正确和高效的。Core computing is one of the important researches in rough set theory. In recent years,the algorithms of core computing in in- complete decision tables are relatively few. By studying the notion of collision domain given by Ge Hao, we design a new core computing algo- rithm in incomplete decision table. The algorithm distinguishes the core attribute mainly using the change of the number of colliding objects in collision domain as the measurement criterion in tolerance relation, and proves through theory that the core attribute calculated based on colli- sion domain is equivalent to that calculated based on positive region. By analysing the new algorithm, its time complexity is known as D（｜KI｜CI^2｜IU）（｜K｜=max{｜Tc（x）｜｜x∈U}）, and the space complexity is O （ ｜ U ｜）. At last, the example and simulation experiment are used to illustrate that the proposed algorithm is correct and efficient.

关 键 词：不完备决策表 容差关系 冲突域 核属性 

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