Abstract: For an incomplete decision table, the definition of discernibility object pair set and the corresponding definition of attribute reduction are introduced. It is proved that the definition of attribute reduction is equivalent to the one based on generalized decision-making. Under this condition, an algorithm based on the definition of discernibility object pair set is proposed. Through discernibility degree [K(ci)] and complete degree [P(ci)] as heuristic information, combining with quick sorting, the time complexity of the new algorithm is cut down to [O(|C||U|2)]. Compared with the traditional algorithm[O(|C|3|U|2)] and [O(|C|2|U|2)], the time complexity is effectively reduced. An example is used to illustrate the advantage and convenience of the new algorithm.

Key words: rough set, incomplete decision table, discernibility object pair set, attribute reduction

摘要： 对于不完备决策表，给出了区分对象对集和基于区分对象对集约简的定义，并证明出基于区分对象对集的属性约简定义等价于基于广义决策的属性约简定义。在此基础上，提出一种基于区分对象对集的新算法。新算法以区分度[K(ci)]和完备度[P(ci)]为启发信息，结合基数排序，使得算法最终时间复杂度为[O(|C||U|2)]，相比传统的算法时间复杂度[O(|C|3|U|2)]和[O(|C|2|U|2)]，时间复杂度有效降低。通过实例说明了新算法的正确性和有效性。

关键词: 粗糙集, 不完备决策表, 区分对象对集, 属性约简