一种不完备决策表的属性约简算法  

One attribute reduction algorithm for incomplete decision table

作　　者：王帅[1] 徐章艳[1] 曾艳燕[1] 

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

出　　处：《计算机工程与应用》2012年第14期130-133,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(No.60963008);广西自然科学基金(No.2011GXNSFA018163);广西研究生教育创新计划项目

摘　　要：对于不完备决策表,给出了区分对象对集和基于区分对象对集约简的定义,并证明出基于区分对象对集的属性约简定义等价于基于广义决策的属性约简定义。在此基础上,提出一种基于区分对象对集的新算法。新算法以区分度K(ci)和完备度P(ci)为启发信息,结合基数排序,使得算法最终时间复杂度为O(|C||U|2),相比传统的算法时间复杂度O(|C|3|U|2)和O(|C|2|U|2),时间复杂度有效降低。通过实例说明了新算法的正确性和有效性。For an incomplete decision table,the definition of discernibility object pair set and the corresponding definition of attribute reduction are introduced.It is proved that the definition of attribute reduction is equivalent to the one based on generalized decision-making.Under this condition,an algorithm based on the definition of discernibility object pair set is proposed.Through discernibility degree K（ci） and complete degree P（ci） as heuristic information,combining with quick sorting,the time complexity of the new algorithm is cut down to O（｜C｜｜U｜2）.Compared with the traditional algorithm O（｜C｜3｜U｜2） and O（｜C｜2｜U｜2）,the time complexity is effectively reduced.An example is used to illustrate the advantage and convenience of the new algorithm.

关 键 词：粗糙集 不完备决策表 区分对象对集 属性约简 

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