基于Skowron分明矩阵的有效属性约简算法

秦奕青^1,2，杨炳儒²，徐章艳^2,3

1. 北京信息科技大学计算机学院2. 北京科技大学信息工程学院3. 广西师范大学计算机系

摘 要：为降低基于Skowron分明矩阵属性约简算法的复杂度,提出了简化分明矩阵及其相应属性约简的定义,并证明了基于简化分明矩阵的属性约简与基于原分明矩阵的属性约简等价.在简化决策表的基础上,定义了一个函数,该函数能度量条件属性在简化分明矩阵中出现的频率,并给出了计算该函数的快速算法,其时间和空间复杂度均为O（|U/C|）.用该函数设计了一个有效的基于原分明矩阵属性约简算法,算法的时间复杂度降为O（|C||U|）+O（|C|2|U/C|）,空间复杂度降为O（|U|）;并用实例证明了算法的有效性.

关键词：粗糙集;分明矩阵;属性约简;复杂度;