基于差别矩阵的增量式属性约简完备算法

Complete Algorithm of Increment for Attribute Reduction Based on Discernibility Matrix

为了解决基于差别矩阵的属性约简完备算法得不到最小约简的问题,提出了一种改进的属性约简方法.该方法将信息论定义的属性重要性作为启发式信息,并通过构造一个条件信息熵算子对差别集合进行运算,同时利用算子来计算候选属性的剔除次序,采用宽度优先搜索策略使约简集合中含有最重要的属性,这样就解决了完备算法约简率低的问题.结合该方法并在分析对象集增量与差别矩阵关系的基础上,证明了增量约简定理,由此提出了一种增量式约简完备算法(CAIR),当新数据加入决策表时,算法可增量构造差别集合.实验结果表明,所提CAIR在大大缩短计算差别集合时间的同时,约简率比非完备算法提高了20.3%,是同条件下完备算法执行效率的13.2倍.

Aiming at the problem that complete algorithm of attribute reduction based on discernibility matrixcan 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 breadthirst search strategy is utilized to make minimal reduction 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.