New Algorithm for Computing Tolerance Matrix

Rough set theory is emerging as a powerful tool for reasoning about data. Attribute reduction is one of important topics in the research on the rough set theory. The classical rough set theory based on equivalence relation has made a great progress, while the equivalence relation is too harsh to meet and is extended to tolerance relation in real world. It is important to investigate rough computational methods for rough set theory, which is one of the bottleneck problems in the development of rough set theory. Matrix computation based on tolerance relation is one of effective method for computing attribute reduction of incomplete decision table. The time complexity of the existed attribute reduction algorithm designed by tolerance matrix method is O(|C|3|U|2), and the algorithm has many repeated computations. To lower the time complexity, we first analyzed the shortcoming of those algorithms. Then we provided a new algorithm for computing the tolerance matrix. At last, we used the above algorithm to design an algorithm of attribute reduction based on tolerance matrix. It’s time complexity is O(|C|2|U|2).