Abstract: When some new objects are added to the decision table, the attribute reduction sets will be changed. To ensure the correctness of the results, it is necessary to update the attribute reduction dynamically. Usually, the important attribute is selected which depends on the quantity of distinguishable elements in discernibility matrix algorithm. The most distinguishable information attribute is merged into reduction set every time, so the time complexity is high. Firstly, this paper proposes the definitions of effective element pair and indistinguishable string, selects the important attribute according to the length of indistinguishable string and proves the effectiveness. Secondly, this paper analyzes the different cases of added object, and updates the attribute reduction of simplified decision table according to the corresponding conditions dynamically. Then this paper designs the incremental updating algorithm based on ordered indistinguishable string. At last, the example analysis and experimental comparison show that the algorithms are feasible and effective.

Key words: attribute reduction, effective element pair, indistinguishable string, incremental updating

摘要： 当有新增对象加入到决策表时，已有的属性约简将会发生变化，为保证约简结果的正确性，需对其进行动态更新。差别矩阵算法通常以可区分元素的多少作为属性重要性的依据，每次选择可区分信息最多的属性加入约简集，导致有较高的时间复杂度。为此，提出了有效比较元素对及不可区分串定义，以不可区分串长短为属性重要性选择的依据，并证明了其有效性；然后分析了增量更新的不同情况，将新增对象加入简化决策表，按相应条件动态变化约简集，由此设计了基于有序不可区分串的增量更新算法；最后通过实验比较和实例分析了增量更新算法的可行性和有效性。

关键词: 属性约简, 有效元素对, 不可区分串, 增量更新