一种不完备决策表的属性约简算法

摘要

对于不完备决策表,给出了区分对象对集和基于区分对象对集约简的定义,并证明出基于区分对象对集的属性约简定义等价于基于广义决策的属性约简定义.在此基础上,提出一种基于区分对象对集的新算法.新算法以区分度K(ci)和完备度P(Ci)为启发信息,结合基数排序,使得算法最终时间复杂度为O(|C||U|2),相比传统的算法时间复杂度O(|C|3|U|2)和O(|C|2|U|2),时间复杂度有效降低.通过实例说明了新算法的正确性和有效性.%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(c,) and complete degree P(c,) as heuristic informa- -tion, combining with quick sorting, the time complexity of the new algorithm is cut down to 0QC||[/f). Compared with the traditional algorithm OflCf |C/|2) an^ OflCf Uf), the time complexity is effectively reduced. An example is used to illustrate the advantage and convenience of the new algorithm.