基于修正差别矩阵的高效属性约简算法

为降低基于修正差别矩阵的属性约简算法的复杂度,给出了基于修正差别矩阵的简化差别矩阵,证明了基于该简化差别矩阵的属性约简定义与基于原修正差别矩阵的属性约简定义是等价的.在此基础上设计了一个基于简化差别矩阵的属性约简算法,其空间和时间复杂度分别被降为O(|C|(|U′pos||U/C|))和max{O(|C|2(|Up′os||U/C|)),O(|C||U|log|U|)}.实例说明:用新算法进行属性约简,不仅减少了计算量,而且减少了存储空间,因而是一种高效的属性约简算法.

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

给出区分对象对集的定义和基于区分对象对集的属性约简的定义，证明该定义与基于正区域的属性约简定义等价．由于求区分对象对集时，要求出U／C，故设计一个高效的求U／C的算法，其时间复杂度降为O（｜C｜｜U｜）．进而提出一个基于区分对象对集的高效属性约简算法，其时间和空间复杂度分别降为O（｜C｜｜U｜）＋O（｜C｜｜U／C｜^2）和O（｜U｜）＋O（｜U／C｜^2）．用1实例说明该算法的高效性．