相容矩阵的高效属性约简算法  

An Efficiency Attribute Reduction Algorithm of Tolerance Matrix

作　　者：张清国[1] 郑雪峰[1] 

机构地区：[1]北京科技大学计算机与通信工程学院,北京100083

出　　处：《小型微型计算机系统》2012年第9期1944-1947,共4页Journal of Chinese Computer Systems

基　　金：国家科技基础条件平台项目(2005DKA43600)资助

摘　　要：给出完备决策表和不完备决策表的定义并说明相容关系.给出了相容矩阵及其属性约简的定义,同时也给出差别矩阵及其属性约简的定义,证明了基于相容矩阵的属性约简与关于差别矩阵的属性约简定义是等价的,给出了一个计算条件属性的频率的公式,该公式不必计算差别矩阵,而是直接从决策表中计算出各条件属性在差别矩阵中出现的频率.设计一个快速计算条件属性频率的快速算法,在此基础上,设计了一个高效求基于相容矩阵的属性约简算法,并通过实例对该算法进行了验证.实践证明:算法的复杂度都得以降低,该算法的时间复杂度为O(|C|2|U|),空间复杂度为O(|U|).该方法为计算其他的属性约简算法提供了一条新思路.In this paper, the definitions of complete decision table and incomplete decision table were given, furthermore, this paper described the tolerance relation of them. Also, we made the definition of discernibility matrix and its attribute reduction definition, we described the definition of tolerance matrix and its attribute reduction definition, we also described the definition of discernibility ma- trix and its attribute reduction definition. After that we first have proved that the attribute reduction definition based on tolerance ma- trix is the same as that based on discernibility matrix. Then we proposed a formula for computing the frequency of the conditional at- tribute. It does not compute the discernibility matrix in this formula,but it directly computes all condition attributes＇ frequency in dis- cemibility matrix from decision talbe.. Then an efficiency algorithm for computing the formula is proposed. On this condition, finally an efficiency algorithm for computing the attribute reduction based on tolerance matrix is designed, we use an example to validate this algorithm. We reach a conclusion： the complexity is reduced, finally this algorithm＇s time complexity isO （｜ C ｜^2{ U｜ ）, and its space time complexity is O（ ｜ U｜）. This gives a new way which will be used in other attribution reduction models.

关 键 词：粗糙集 不完备决策表 相容矩阵 差别矩阵 算法 

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