Abstract: For an incomplete information decision table, Huang Bing proposed an attribution reduction algorithm using a tolerance matrix based on tolerance relationship. But the algorithm is time-consuming, and the time complexity of this algorithm is[O(|C|3|U|2)]. For cutting down the time complexity of the attribution reduction algorithm, using the matrix distance as heuristic information, with the characteristics of the conjunctive matrix, a new algorithm is designed, the time complexity of the algorithm is reduced to[O(|C|2|U|2)]. Finally, an example is used to illustrate the new algorithm.

Key words: incomplete decision table, tolerance matrix, matrix distance, attribute reduction

摘要： 针对不完备决策表，黄兵给出一种基于容差关系的相容矩阵的属性约算法，但算法比较费时，其时间复杂度为[O(|C|3|U|2)]。为降低原算法的时间复杂度，以矩阵距离为启发信息，并运用矩阵合取的特性，设计了一个新的属性约简算法，算法时间复杂度降为[O(|C|2|U|2)]。通过实例验证了该算法。

关键词: 不完备决策表, 相容矩阵, 矩阵距离, 属性约简