摘要
由于基于老差别矩阵的属性约简的定义与基于正区域的属性约简的定义是不一致的,给出一个简化差别矩阵和相应的属性约简的定义,并证明了该定义与基于正区域的属性约简的定义是一致的。由于在简化差别矩阵中,要先求出IND(C),故设计了一个较好的求IND(C)的算法,其复杂度被降为O(|C‖U|)。在此基础上设计了一个完备属性约简算法,其时间复杂度和空间复杂度分别被降为max{O(|C|2(|U′pos‖U/C|)),O(|C‖U|)}和max{O(|U|),O(|C|(|U′pos‖U/C|))}。
Because the definition of attribution reduction inition of attribution reduction based on positive region,a attribution reduction are provided.At the same time,it is same as the definition of attribution reduction based on based on old discernibility matrix is not the same as the defsimple discernibility matrix and the corresponding definition of proved that the above definition of attribution reduction is the positive region.For first computing IND(C) in the simple discernibility matrix,a good algorithm for computing IND(C) is designed,it's time complexity is cut down to O(|C || U|). On this condition,a complete attribution reduction algorithm is designed,tlme complexity and space complexity of the new algorithm are cut down to max{O(|C|2(|U'pos|| U/C|)),O(|C || U|)}and max{O(|U|),O(|C|(|Upos || U/C|))} respectively.
出处
《计算机工程与应用》
CSCD
北大核心
2006年第26期167-169,197,共4页
Computer Engineering and Applications
关键词
粗糙集
差别矩阵
简化差别矩阵
属性约简
完备算法
复杂度
rough set,dieernibility matrix,simple discernibility matrix,attribution reduction,complete algorithm,complexlty