蚁群算法在面向属性的数据约简中的应用

Application Ant Colony Algorithm in Attribute-oriented Data Reduction

粗糙集作为一种新的数学工具可用于数据挖掘中的面向属性的数据约简,但随着信息系统中信息量的不断膨胀,属性组合的不断增长,单独使用粗糙集寻找最小属性集已证明是个NP难的问题。蚁群算法是一种新型的模拟进化算法,在求解复杂的组合优化问题中获得成功并表现出良好的性能。文中将属性约简的过程视为一个特殊的"寻优"过程:把属性视为节点,而要寻找的是这些节点的"最少"组合,使得其能代替原来的属性节点而不改变原有属性的分类粗糙度。在此基础上,提出一种新的组合算法,利用蚁群算法在寻优方面的优势,结合粗糙集算法,用于最小属性集的寻找。最后通过一个具体的例子,证明了此算法的有效性和可行性。

As a new mathematic tool,rough set can be used in attribute -oriented data reduction in data mining. However, as the real world databases tend to increase in size, combinations of attributes grow more and more. Using only rough set to find the minimal attribute set becomes a N -P hard problem. Ant colony algorithm is a new algorithm which simulates evolution. It has succeeded in solving complex problem of combinatorial optimizaiton and displayed good performance. In this paper, the reduction of attributes is considered as a special ＂optimization＂ process： an attribute is considered as a node and the destination is to find the ＂least＂ combination of these nodes which can take place in all attribute nodes but not change the degree of classified roughness . Based on these points, the paper proposes a new combinatorial algorithm to find the mimimal attribute set, making full use of the advantage of ant colony algorithm in optimization with rough set algorithm. At last, the effectivity and feasibility of this algorithm have been proved through a specific example.