垂直划分二进制可分辨矩阵的属性约简

Attribute reduction of vertically partitioned binary discernibility matrix

针对二进制可分辨矩阵属性约简方法在处理大数据集时的不足,首先给出两种二进制可分辨矩阵属性约简的定义,并证明这两个属性约简定义与正区域的属性约简定义是等价的;然后,给出对二进制可分辨矩阵按条件属性垂直划分后进行属性约简的方法;为了进一步降低空间开销,提出将垂直分解的二进制可分辨矩阵存于外部介质中,在约简过程中,仅将所需部分调入内存,由此设计启发式属性约简算法,其时间和空间复杂度的上界分别为O(∣C∣∣U∣2)和O(∣U∣2);最后,理论分析和实验结果验证了该算法的正确性和高效性.

Abstract： Attribute reduction algorithms based on binary discernibility matrix are disadvantageous to the larger database sets. To overcome above shortcoming, firstly, the two definitions of attribute reduction based on binary discernibility matrix are proposed. It is proved that attribute reductions acquired from the definitions are all equivalent to the attribute reduction based on positive region. Then the method of attribute reduction is present, which is based on the vertically partitioned binary discernibility matrix. In order to decrease the express of space, the partitioned binary attribute columns are all stored on the external space. ＇In the process of reduction, essential part is transferred into the memory merely. Based above, a heuristic attribute reduction algorithm is designed, in which upper bounds of the time and space complexity are O（∣C∣∣U∣2） and O（∣U∣2） respectively. Finally, both of theoretical analysis and experimental results show that the algorithms are correct and efficient.