Aiming at the problem that complete algorithm of attribute reduction based on discernibility matrix can not find approximately minimal reduction

an improved attribute reduction method is proposed based on the original algorithm

and the attribute importance defined from the viewpoint of information theory is regarded as heuristic information. The discriminated set is operated by constructing an operator of conditional information entropy

and the excluding order of candidate attributes is calculated as the algorithm is iterated. Meanwhile

the breadth-first search strategy is utilized to make minimalreduction set contain the most important attribute. Thus

the method can resolve the problem that complete algorithm is of low reduction rate. On the basis of the analysis of the relation between the objects increase and discernibility matrix

a theorem of the increment reduction is proved

and then a complete algorithm for increment reduction(CAIR)is presented. When new data are added into the decision table

the discernibility set can be constructed incrementally. The experimental results show that the computation time of the discernibility set is significantly reduced by CAIR

the reduction rate is 20.3% higher than that of incomplete algorithm

and the execution efficiency is enhanced by 13.2 times compared to the complete algorithm under same conditions.