摘要： 在不一致决策表中定义了k阶分配序约简，给出了k阶分配序一致集的判定定理。通过定义k阶分配序区分矩阵，给出了求k阶分配序约简的区分矩阵法。为了克服区分矩阵法时间复杂度过高的缺陷，通过定义属性的相对重要性，提出了一种求k阶分配序约简的启发式算法，分析得到该算法的时间复杂度是多项式的结论。实例验证了算法的有效性。

关键词: 信息系统, 粗糙集, 不一致决策表, k阶分配序约简, 区分矩阵

Abstract: Knowledge reduction is one of the most important tasks in rough set theory. The k-ordered assignment reduction is defined in inconstant decision tables, which maintains the first k membership orders of the equivalence classes determined by attributes set to the decision classes determined by decision attributes set. The judgment theorem and discernibility matrix with respect to consistent ordered assignment set are obtained, by means of which, the method of k-ordered assignment reduction is presented. To overcome the disadvantage of ordered assignment reduction based on discernibility matrix because the time complexity is exponential, a heuristic algorithm based on the significance of attributes is proposed, which aims at acquiring one of the minimal k-ordered assignment reduction. The time complexity of the algorithm is analyzed. The experimental result shows that the algorithm is valid.

Key words: Information systems, Rough sets, Inconstant decision table, k-ordered assignment reduction, Discernibility matrix