关键词: 粗糙集,差别矩阵,二叉树,属性约简 中图法分类号TP18文献标识码A

Abstract: Discernibility matrix and binary discernibility matrix method is easy to understand and design,hich has aroused great concern by many scholar.But the two methods produce a large number of repeated and useless elements (if A is the subset of B,B is the useless element of A) on the fly.These repeated and useless elements occupy a lot of space and will affect the efficiency of the algorithm.Attribute reduction based on discernibility matrix methods exist the high cost of storage problem in previous literatures.This paper propose a attribute reduction algorithm based on compressed storage in the thought of combining the binary discernibility matrix with the binary tree (B_Tree) .The algorithm store the binary discernibility matrix attribute sets in the binary tree (B_Tree).The algorithm effectively reduce the time and space efficiency by storage while pruning(pruning is a thought,which delete those repeated and useless attribute sets from binary tree on the same path).Finally the analysis of example proves the feasibility and effectiveness of the new algorithm.

Key words: Rough set,Discernibility-matrix,Binary tree,Attribute Reduction