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

An Efficient Attribute Reduction Algorithm Based on Discernibility Object Pair Set

给出区分对象对集的定义和基于区分对象对集的属性约简的定义，证明该定义与基于正区域的属性约简定义等价．由于求区分对象对集时，要求出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.