基于简化差别矩阵的属性约简算法  

An Attribution Reduction Algorithm Based on Simple Discernibility Matrix

作　　者：高学东[1] 丁军[1] 

机构地区：[1]北京科技大学管理学院,北京100083

出　　处：《系统工程理论与实践》2006年第6期101-107,共7页Systems Engineering-Theory & Practice

摘　　要：为降低基于修正差别矩阵的属性约简算法的时间复杂度和空间复杂度,首先给出了简化差别矩阵的定义,并证明了该矩阵所包含的信息量与修正差别矩阵的信息量等价.其次设计了一个高效的求U/C的算法,其时间复杂度被降为O∑|C|i=1|ki||U|.然后分析了基于修正差别矩阵的属性约简算法的不足,并使用上述高效求U/C的算法,设计了一个基于简化差别矩阵的属性约简算法,证明了该新算法的时间复杂度和空间复杂度分别被降为maxO(|C|2(|Up′os||U/C|)),O∑|C|i=1|ki||U|和max{O|C|(|Up′os||U/C|)),O(|U|)}.最后用一实例说明了新算法的高效性.In order to cut down the time and space complexity of the attribution reduction algorithm based on modificatory discernibility matrix, firstly, we gave the definition of simple discernibility matrix, and proved the simple discernibility matrix contains the same information content as the modificatory discernibility matrix. Secondly, we designed an efficient algorithm for computing U/C, and the time complexity of the algorithm was cut down to 0 （ICI∑i=1｜ki｜｜U｜）. Then we analyzed the shortcomings of attribution reduction algorithm based on medificatory discernibility matrix, using the new efficient algorithm for computing UIC designed an attribution reduction algorithm which is called attribution reduction algorithm based on simple discernibility matrix, and proved that the time and space complexity of the new algorithm are cut down to max{0（｜C｜^2（｜U′pos｜｜U/C｜））,0（｜C｜∑i=1｜ki｜｜U｜} and max {0｜C｜（｜U′pox｜｜U/C｜））,0（｜U｜）}respectively.At the end,an example was used to illustrate the efficiency of the new algorithm.

关 键 词：粗糙集 简化差别矩阵 约简 复杂度 

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