一种基于二进制可辨矩阵的属性约简算法

An Attributes Reduction Algorithm Based on Binary Discernibility Matrix

基于可辨矩阵的属性约简算法都是从信息系统中直接求得约简,提出了分两步求得约简,降低了算法的时间复杂度为O(mn2),第一步计算出近似约简,第二步去掉其中的冗余属性。改变了过去人们认为基于可辨矩阵的特征选择算法的时间复杂度不低于O(m2n2)的观点(其中m为数据集中特征/属性的个数,n为数据集中样本的个数)。最后给出了实验结果。

All of the attributes reduction algorithms work out the reduction sets from datasets directly. In this paper, we calculate the reduction sets within two steps, calculating the approximate resumes firstly, taking out the redundancy reductions secondly. It reduces the time complexity to O(mn2). Before, people think that the time complexity of feature selection algorithm based on Rough sets can not be under O(m2n2) in which m is the number of features, n is the number of samples in datasets. Finally, the experiment and results in UCI are presented.