Abstract: A new improved algorithm for the simplified discernibility-matrix was proposed on the subject of attribute re- duction in rough set theory. Discernibility-matrix is being simplified without being sorted and at fewer cost of traver- sing. I}his can notably raise the speed of being simplified discernibility-matrix and ultimately obtain the ordered and sim- plified discernibility set. The comparative experiments on computational efficiency show that this new algorithm is more efficient than the homogeneous ones. A new criterion of significance of attribute was put forward based on the three as- pects which arc the weight of element containing the attribute, the frequency and the absorptive ability of the attribute in the discernibility set. Therefore a new method for attribute reduction was introduced on the basis of the above two points, the theoretical analysis proves that the worst time complexity of the new method is less than the other ones based on discernibility-matrix. In addition, lots of comparative experiments in attribute reduction display that this new method is effective and can largely find out a minimal attribute reduction.

Key words: Rough set, Attribute reduction, Simplified discernibifity-atrix, Discernibifity set, Significance of attribute