Attribute reduction can simplify condition attributes in the decision table, while the simplified decision table has same functionality with that before simplification. Based on the introduction of basic attribute reduction algorithm based on discriminability matrix, the paper presented a kind of improved attribute reduction algorithm based on discriminability matrix. The algorithm utilized the frequency of attribute in the matrix as determination basis for the importance of attributes and proposed the heuristic attribute reduction algorithm, so as to improve efficiency of attribute reduction. The specific attribute reduction example shows that the algorithm use heuristic method to determine the second-best. It can significantly reduce complexity in time and spatial in solving and improve efficiency.