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

Attribute reduction of vertically partitioned binary discernibility matrix

作　　者：杨传健[1] 葛浩[2,3] 李龙澍[4] 

机构地区：[1]滁州学院计算机与信息工程学院,安徽滁州239012 [2]滁州学院机械与电子工程学院,安徽滁州239012 [3]安徽大学计算智能与信号处理教育部重点实验室,合肥230039 [4]安徽大学计算机科学与技术学院,合肥230039

出　　处：《控制与决策》2013年第4期563-568,573,共7页Control and Decision

基　　金：安徽省自然科学基金项目(090412054);安徽省高等学校自然科学研究项目(KJ2012A212;KJ2011Z276);安徽省高等学校优秀青年人才基金项目(2011SQRL123);滁州学院科学研究项目(2010kj014B;2011kj003Z)

摘　　要：针对二进制可分辨矩阵属性约简方法在处理大数据集时的不足,首先给出两种二进制可分辨矩阵属性约简的定义,并证明这两个属性约简定义与正区域的属性约简定义是等价的;然后,给出对二进制可分辨矩阵按条件属性垂直划分后进行属性约简的方法;为了进一步降低空间开销,提出将垂直分解的二进制可分辨矩阵存于外部介质中,在约简过程中,仅将所需部分调入内存,由此设计启发式属性约简算法,其时间和空间复杂度的上界分别为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.

关 键 词：粗糙集 可分辨矩阵 二进制可分辨矩阵 属性约简 

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