Abstract: Focused on the issue that there are redundant elements in the algorithm based on the discernibility matrix, which leads to the high cost of space storage, an attribute reduction algorithm based on weighted condensed tree is proposed in this paper. The algorithm can further eliminate the redundant elements, compress the information in the discernibility matrix, and consider the effect of attribute importance in the process of constructing the tree structure. The experimental results are compared with the C-Tree and the discernibility information tree algorithm. The proposed algorithm can obtain better attribute reduction results, which can effectively reduce the space complexity.

Key words: rough set, attribute reduction, discernibility matrix, weighted condensed tree, space complexity

摘要： 针对基于分辨矩阵约简算法中存在冗余元素，从而导致空间存储代价高的问题，提出一种基于加权浓缩树的属性约简算法。该算法可以进一步剔除冗余元素，压缩存储分辨矩阵中的信息，并且在构建树结构的过程当中考虑了属性重要度的影响。实验结果与C-Tree及差别信息树算法进行比较，提出的算法可以获得更优的属性约简结果，有效地降低了空间复杂度。

关键词: 粗糙集, 属性约简, 分辨矩阵, 加权浓缩树, 空间复杂度