一种基于C-Tree的属性约简增量式更新算法

针对以往文献为克服基于差别矩阵的属性约简算法存储代价高的不足而提出的基于浓缩树(C-Tree)的高效属性约简算法仅考虑决策表不变的情况,提出了一种基于C-Tree的属性约简增量式更新算法,主要考虑对象动态增加情况下属性约简的更新问题.该算法可通过快速更新C-Tree,在动态求解核的基础上,利用原有的属性约简有效地进行属性约简的增量式更新.理论分析和实验结果表明,所提出的算法是有效可行的.

An incremental updating algorithm for attribute reduction based onC-Tree

To overcome the disadvantage of those attribute reduction algorithms based on the discernibility matrix with high
space complexity, a compact storage structure called condensing tree(C-Tree) and corresponding efficient algorithms for
attribute reduction are introduced in the existing reference, respectively. However, the mentioned algorithms in the reference
only consider the case of the static decision table. Therefore, an incremental updating algorithm is proposed for attribute
reduction based on C-Tree in the case of inserting, which only needs to modify the related nodes in the corresponding paths
when updating the C-Tree. After dynamically computing a core, attribute reduction can be effectively updated by utilizing
the old attribute reduction. Theoretical analysis and experiments show that the proposed algorithm is effective and feasible.