摘要
针对二进制可分辨矩阵属性约简方法在处理大数据集时的不足,首先给出两种二进制可分辨矩阵属性约简的定义,并证明这两个属性约简定义与正区域的属性约简定义是等价的;然后,给出对二进制可分辨矩阵按条件属性垂直划分后进行属性约简的方法;为了进一步降低空间开销,提出将垂直分解的二进制可分辨矩阵存于外部介质中,在约简过程中,仅将所需部分调入内存,由此设计启发式属性约简算法,其时间和空间复杂度的上界分别为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.
出处
《控制与决策》
EI
CSCD
北大核心
2013年第4期563-568,573,共7页
Control and Decision
基金
安徽省自然科学基金项目(090412054)
安徽省高等学校自然科学研究项目(KJ2012A212
KJ2011Z276)
安徽省高等学校优秀青年人才基金项目(2011SQRL123)
滁州学院科学研究项目(2010kj014B
2011kj003Z)
关键词
粗糙集
可分辨矩阵
二进制可分辨矩阵
属性约简
rough set
discernibility matrix
binary discernibility matrix
attribute reduction