一种基于属性重要性的启发式约简算法

Heuristic Algorithm for Reduction Based on the Significance of Attributes

属性约简是知识发现中的关键问题之一.为了能够有效地获取决策表中条件属性集的最小相对约简,本文首先利用代数方法描述决策表中的属性的重要性,提出了限制正域的概念,得到了关于限制正域的若干结果,并据此提出一种改进的属性约简算法,即以属性核为起点并结合算子,通过向属性核不断添加重要程度最大的属性,并利用已求得的正区域和限制正域使处理数据的范围不断缩小从而减少求约简的时间.该算法能够节省得到决策表的最小约简的时间并能得到所有相对约简.实例分析也验证了该算法的有效性.

Reduction of attributes is one of the key problems in the knowledge discovery. In order to achieve the minimal relative reduction of attribute effectively in the decision table, firstly, this paper describes the significance of attributes defined from the algebraic theory as heuristic information, then proposes the concept of restrictive positive region and gets some results about restrictive positive region. As a result, a improved algorithm of reduction of attributes is proposed, i.e. it makes use of the positive region and restrictive positive region to reduce the range of dealing datas, and reduces the time of acquiring reduction by appending the most significance of attributes to core of attributes from original set of core attributes and combining with operator. This algorithm can save some time of acquiring the least reduction in the decision table and gets all of the relative reductions. Finally, the experimental results show that this algorithm was proved effectively in attributes reduction of decision tables.