基于蚁群算法的分类规则挖掘算法.pdf

基于蚁群算法的分类规则挖掘算法

吴正龙王儒敬滕明贵许梅生
(解放军炮兵学院，合肥230021)
(中国科学院合肥智能机械研究所，合肥230021)
E—mail：[e-mail]

摘要提出了一种基于蚁群算法的分类规则挖掘算法。算法实质上是一种序列覆盖算法：蚁群搜索一个规则，移去它
覆盖的样例，再重复这一过程，从而得到共同覆盖样例的一组规则。针对蚁群算法计算时间长的缺点，提出了一种变异算
子。对两个公用数据的实验及其与C4、5和Ant—Miner的对比表明，算法能够发现更好的分类规则，包括预测能力更强，
有更少规则的规则集，以及形式更简单则。实验同时显示变异算子有效节省了计算时间。

关键词蚁群算法分类规则变异算子

文章编号1002—8331一(2004)20—0030—04文献标识码A中图分类号TP181；TP182

MiningGlassificationRuleBasedonColonyAlgorithm
WuZhenglong’WangRujingTengMingguiXuMeisheng
(ArtilleryAcademyofPLA。Herei230021)
(InstituteofIntelligentMachines，CAS，Hefei230021)
Abstract：Thepaperproposesanalgorithm，whichisbasedonantcolonyalgorithm，forminingclassificationrulefrom

categoricaldatabase．Amutationoperatorisappliedtothealgorithmforthepurposeofshorteningthecomputingtime，

whichis．usuallytoolonginsimpleantcolonyalgorithm、Experimentsontwopublicdatasetshowthatcomparedwith

C4．5，afamousdecisiontreelearningalgorithm，andAnt—Miner，thealgorithmcandiscoverbetterclassificationrule，in—

cludingrulesetwithbetterpredictiveaccuracyrateandfewerrule，simplerrulewithfewerterms、Experimentsalsoshow
thatthemutationoperatorsavesthecomputingtimeefectively．

Keywords：antcolonyalgorithm，classificationrule，mutationoperator

1前言异算子，有效节省了计算时间。文章组织如下，第2节介绍了算
分类是一项重要的数据挖掘任务。决策树学习能很好地发法，第3节给出实验结果及与C4、5和Ant—Miner的详细对比，
现分类规则。从树的根节点到叶节点的每一条路径表示一条分第4节总结并提出下一步的研究方向。
类规则，路径中的每个节点代表了对样例的某个属性的测试。
在构造决策树的过程中，属性的选择至关重要。属性按照其单2基于蚁群算法的分类规则挖掘算法
独分类样例集的能力大小被选择，而增加测试后产生的新样例定义路径为属性节点和类标号节点的连线，其中每个属性
集的纯度(purity)得以提高。节点最多只出现一次且必须有类标号节点。图1中给出了两个
蚁群算法(AntColonyAlgorithm)是20世纪90年代初由可能的路径。每个路径对应着一条分类规则，分类规则的挖掘
意大利学者M．Dorigo、V．Maniezzo、A．Colorui等人提出并逐渐引可以看成对路径的搜索。利用蚂蚁寻找食物形成最短路径的原
起研究者的注意，被用于TSP问题求解、合作求解、网络路由[31、理，蚁群算法可以用来进行分类规则的挖掘，只不过这里搜索
分配问题[21、数据聚类、组合优化【等问题，取得了一系列较好的不是最短路径，而是最优路径。最优路径表示了最优的分类
的实验和应用结果。文献『1Ol提出基于蚁群算法的数据挖掘系规则。可以用路径对应规则的分类能力(有效性)和长短(简洁
统Ant—Miner，它可以挖掘分类规则。虽然蚁群算法的研究刚刚性)来衡量路径的优劣。
起步，蚁群现象本身很多问题还缺乏严格的理论基础，但上述蚂蚁构造规则的过程体现为构造一条路径，分为三个阶
研究显示其在求解复杂优化问题，特别是离散优化问题上具有段。首先从一条空路径开始重复选择路径节点增加到路径上
独特优越性，是一种很有发展前景的方法。(模仿蚂蚁的爬行过程)