Abstract: It is proved that solving the minimal reduction of decision table is a NP-hard problem. This paper puts on a heuristic algorithm based on rough set and evidence theory. It gives attribute information entropy by using the concept of equivalence partitioning of rough set, and defines the attribute importance to get the core of the knowledge. It establishes an evidence function for each attribute by the concept of dichotomous mass functions, combining which to get the evidence importance of each attribute. Set the core as the start of the algorithm and make size of attributes importance as heuristic information until it meets the reduction condition. Examples show that it can find the core and reduction quickly, and the reduction used in classification accuracy is higher.

Key words: rough set, reduction of knowledge, dichotomous mass functions, entropy, importance of attributes

摘要： 求解决策表的最小约简已被证明是NP-hard问题，在粗糙集和证据理论的基础上提出了一种知识约简的启发式算法。利用粗糙集等价划分的概念给出属性的信息熵，定义每个属性的熵值重要性并由此确定知识的核。引入二分mass函数对每个属性建立一个证据函数，证据融合得到每个属性的证据重要性。以核为起点，以证据重要性为启发，依次加入属性直至满足约简条件。实例表明，该方法能够快速找到核和相对约简，并且该约简运用到分类上正确率也是较高的。

关键词: 粗糙集, 知识约简, 二分mass函数, 熵, 属性重要性