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

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