基于区分对象对集的高效属性约简算法  

An Efficient Attribute Reduction Algorithm Based on Discernibility Object Pair Set

作　　者：徐章艳[1] 杨炳儒[1] 宋威[1] 

机构地区：[1]北京科技大学信息工程学院

出　　处：《模式识别与人工智能》2006年第5期572-577,共6页Pattern Recognition and Artificial Intelligence

摘　　要：给出区分对象对集的定义和基于区分对象对集的属性约简的定义，证明该定义与基于正区域的属性约简定义等价．由于求区分对象对集时，要求出U／C，故设计一个高效的求U／C的算法，其时间复杂度降为O（｜C｜｜U｜）．进而提出一个基于区分对象对集的高效属性约简算法，其时间和空间复杂度分别降为O（｜C｜｜U｜）＋O（｜C｜｜U／C｜^2）和O（｜U｜）＋O（｜U／C｜^2）．用1实例说明该算法的高效性．The definition of discernibility object pair set and the corresponding definition of attribute reduction are introduced. It is proved that the definition of attribute reduction is equivalent to the one based on positive region. Since U/C is important for computing the discernibility object pair set, an algorithm for computing U/C is designed, whose time complexity is cut down to O（ ｜ C ｜｜ U ｜ ）. Under this condition, an efficient attribute reduction algorithm is proposed, whose time and space complexity are cut down to O（ ｜ C ｜｜ U ｜ ） ＋O（ ｜ C ｜ （ ｜ U/C｜^2 ）） and O（ ｜ U ｜ ） ＋O（ ｜ U/C ｜^2 ） respectively. Finally, an example is used to illustrate the efficiency of the new algorithm.

关 键 词：粗糙集 修正的差别矩阵 属性约简 区分对象对集 复杂度 

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