挖掘最大频繁项集的改进蚁群算法

ComputerEngineeringandApplications计算机工程与应用2011，47（13）161

挖掘最大频繁项集的改进蚁群算法

黄红星，王秀丽，黄习培

HUANGHongxing，WANGXiuli，HUANGXipei

福建农林大学计算机与信息学院，福州350002

CollegeofComputerandInformation，FujianAgricultureandForestryUniversity，Fuzhou350002，China

HUANGHongxing，WANGXiuli，HUANGXipei.Modifiedantcolonyoptimizationforminingmaximalfrequentitemsets.ComputerEngineeringandApplications，2011，47（13）：161-165.

Abstract：MiningMaximalFrequentItemsets（MFI）istofindamaximalsubsetthatappearsfrequentlyindatasets.TherearemanyalgorithmstoeffectivelysolveMFI.AntColonyOptimization（ACO）isanewmethodtosolveMFI.However，therearetwobottlenecks：TheACOalgorithmtakestoomuchtimeandsolvesimpreciselyforMFI.AnovelACOalgorithmwithmax-minantsystemandassociationgraphisproposed.Thetourgraphisconstructed.Antcolonyconstructslocalmaximalfre-quentitemsetsundertheinstructionofdynamicpheromoneandheuristicfactor.Itdiscoversglobalmaximalfrequentitemsetsbynewlocalandglobalupdatemechanism.Comparedexperimentsshowthatthisalgorithmisfastandeffective.

Keywords：datemining；maximumfrequentitemsets；antcolonyoptimization；max-minantsystem；associationgraph

摘要：最大频繁项集挖掘用于发现频繁地出现在数据集中的最大子集，目前已经有许多有效的算法。应用蚁群算法挖掘最大频繁项集是一种新的方法，但是该算法往往迭代次数多，提取率低。结合频繁项集关联图和最大最小蚂蚁系统，提出一种新的蚁群算法。算法构造蚁群路径图，蚁群在动态的信息素和启发式因子指导下构造局部最大频繁项集，通过新的局部更新和全局更新机制发现全局最大频繁项集。对比实验表明，算法挖掘速度快，提取率高。

关键词：数据挖掘；最大频繁项集；蚁群优化；最大最小蚂蚁系统；关联图

DOI：10.3778/j.issn.1002-8331.2011.13.046文章编号：1002-8331（2011）13-0161-05文献标识码：A中图分类号：TP3011引言最大频繁项集问题抽象为带约束条件的子集问题，并应用蚁

Agrawal等于1993年首先提出了挖掘顾客交易数据库中群系统（AntColonySystem，ACS）[15]求解，有效地提高了挖掘项集间的频繁项集问题[1]，并设计了经典的Apriori算法[2]。算的效率。该算法将信息素放在项上，没有路径的概念，蚂蚁根法中计算项集的支持数是发现频繁项集中最耗时的工作，占据项上的信息素和启发式因子依次进行选择，但是这种方法据整个计算量的大部分，因此，降低候选项集的数量是减小开的信息素增减对蚂蚁影响的无序性和蚂蚁选择项的有序性之销的最好手段。由于最大频繁项集中已经隐含了所有频繁项间存在矛盾，被增强信息素项的个数与对蚂蚁影响次数可能集，且其数量远低于所有的频繁项集的个数，所以可把频繁项不同，即信息素的增减对蚂蚁的影响具有不确定性[16]。目集挖掘问题转化为最大频繁项目集挖掘问题。目前已有的因此，结合频繁项集关联图和最大最小蚂蚁系统（Max-最大频繁集挖掘算法根据搜索空间的遍历策略分为宽度优先算MinAntSystem，MMAS）[17]思想，给出挖掘最大频繁项集新法，如Max-Miner[3]、Pincer-Search[4]、DMFI[5]和DMFIA[6]，深度的蚂蚁算法。该算法只需要扫描一次数据库，然后构建蚂蚁优先算法，如DepthProject[7]、MAFIA[8]、GenMax[9]、MinMax[10]、路径图，根据新的动态信息素和启发式信息构造最大频繁项SmartMiner[11]和FPMax[12]。但是这些精确型算法往往复杂度集，采用与问题紧密相关的局部更新和全局更新机制。实验高，不具有可扩展性，当项集较多较长时消耗时间和空间是不结果表明该算法加速了运行时间和提高了项集提取率，对于可承受的，并且最终容易导致无意义的频繁项集。因此设计大型数据库的最大频繁项集的挖掘是高效智能的。一种既能提高算法效率，又能找到有意义的频繁项集的智能

算法，具有重大意义。2最大频繁项集的基本概念与性质

蚁群优化（AntColonyOptimization，ACO）算法是通过模最大频繁项集（MaximalFrequentItemsets，MFI）挖掘用于拟蚁群部落的群体行为而得出的一种仿生算法，并成功用于发现频繁地出现在数据集中的最大子集。设I={I1I2求解旅行商问题（TravelingSalesmanProblem，TSP）[13]。文IjIn}是数据集中所有项（Item）的集合，I中的任何非空子献[14]首次给出了挖掘最大频繁项集的蚁群算法ACS-MFI，将集称为项集（Itemsets）。设数据库D是事务（Transaction）的集作者简介：黄红星（1979—），男，讲师，主要研究方向为智能计算与数据挖掘等；王秀丽（1963—），女，教授；黄习培（1977—），男，讲师。E-mail：

hhx825@126.com

收稿日期：2009-08-11；修回日期：2009-10-19