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

Quick Attribution Reduction Algorithm Based on Incomplete Decision Table

目前,关于不完备决策表的属性约简算法已有不少,其中在很多算法中,其时间复杂度为O(|C|3|U|2).为有效地降低算法的时间复杂度,给出一个差别矩阵的定义和基于差别矩阵属性约简的定义,并证明了该属性约简与基于正区域的属性约简是等价的.生成的差别矩阵无需比较Uneg之间的对象,使差别矩阵得到有效地简化,进一步降低算法的存储空间.在此基础上,利用简化的差别矩阵设计一个快速计算不完备决策表的属性约简的算法,其时间复杂度降为max{O(|C|2|Upos||U|),O(K|C||U|)}.(其中K=max{|TC(xi)|,xi∈U}).最后用实例仿真说明了新算法的有效性.

At present, some scholars provided the attribution reduction algorithms of incomplete decision table. The time complexity of many algorithms are O（｜C｜^3｜U｜^2）. To cut down the time complexity of the algorithms for computing attribution reduction, the definition of discernibility matrix based on positive region and the corresponding definition of the attribution reduction are provided. At the same time, it is proved that the attribution reduction is equivalent to the attribution reduction based on the positive region. The discernibility matrix is simplified for not comparing the objects between Uneg. On this condition, a quick algorithm for computing attribution reduction is designed with the simplified dicernibility matrix, whose time complexity is max{O（｜C｜^2｜Upos｜｜U｜） ,O（K｜C｜｜U｜）}（K = max{｜Tc（x1）｜,x1∈U}）.At last, an emulate example is used to illustrate the efficiency of the new algorithm. Key words：rough set; incomplete decision table; positive region; discernibility matrix; attribution reduction; algorithm complexity