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

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