不完备决策表中基于对象矩阵属性约简算法  

Attribute Reduction Algorithm Based on Object Matrix in Incomplete Decision Table

作　　者：王炜[1] 徐章艳[1] 李晓瑜[1] 

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

出　　处：《计算机科学》2012年第4期201-204,共4页Computer Science

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

摘　　要：基于差别矩阵的属性约简是粗糙集属性约简中最常用的方法。对通常给出的以存储条件属性为基础差别矩阵进行比较后,给出一种对象矩阵的定义。对象矩阵从相容类内对象的决策值与条件属性的关系出发,存储的是对象集。给出对象矩阵的属性约简定义,证明了属性约简与基于正区域的属性约简的等价性。给出一个启发式的属性约简算法,其时间复杂度为max(O(|C|2|Upos||U|),O(|C||U|2)),空间复杂度为O(|C||U|2);通过实例说明方法的可行性。Attribute reduction based on discernibility matrix is the most common methods in rough set attribute reduction.Compared with discernibility matrix based on storage condition attribute,object matrix was defined in this paper.This object matrix uses the relationship between the decision value of the objects in tolerance class and condition attribute,and what it stores is object set.Then the definition of attribute reduction based on object matrix was given.It is proved that the attribute reduction acquired from this new method is equivalent to that based on positive region in incomplete information system.A heuristic algorithm for attribute reduction was presented which time complexity is max（O（｜C｜2｜Upos｜｜U｜）,O（｜C｜｜U｜2））,and space complexity is O（｜C｜｜U｜2）.An example was used to illustrate the feasibility of this new algorithm.

关 键 词：差别矩阵 属性约简 对象矩阵 正区域 约简算法 

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