最大频繁项集挖掘中搜索空间的剪枝策略ISSN1010-0054CN11-2223/N清华大学学报(自然科学版)JTsinghuaUniv(Sci&Tech),2005年第45卷第S1期2005,Vol.45,No.S15/391748-1752最大频繁项集挖掘中搜索空间的剪枝策略马志新,陈晓云,王雪,李龙杰(兰州大学信息科学与工程学院,兰州730000)收稿日期:2005-05-20基金项目:国家自然科学基金资助项目(60473095)作者简介:马志新(1973-),男(汉),甘肃,副教授。E-mail:mazhx@lzhttps://www.sodocs.net/doc/85128781015.html摘要:最大频繁项集挖掘可以广泛应用在多种重要的Web挖掘工作中。为了有效地削减搜索空间,提出了一种新的最大频繁项集挖掘中的搜索空间剪枝策略。这种策略基于深度优先遍历词典序子集枚举树,利用树中子节点与父节点扩展集中相同项的扩展支持度相等的特性,对搜索空间进行剪枝。应用该策略,对MAFIA算法进行改进优化。实验结果表明,该剪枝策略可以有效削减搜索空间,尤其在稀疏但包含长频繁项集的数据集上,搜索空间削减掉2/3,算法的时间效率比原MAFIA算法提高3～5倍。关键词:Web挖掘;最大频繁项集;剪枝策略;搜索空间中图分类号:TP311文献标识码:A文章编号:1010-0054(2005)S1-1748-05PruningstrategyforminingmaximalfrequentitemsetsMAZhixin,CHENXiaoyun,WANGXue,LILongjie(SchoolofInformationScienceandEngineering,LanzhouUniversity,Lanzhou730000,China)Abstract:Miningmaximalfrequentitemsetsisafundamentalprobleminmanypracticalwebminingapplications.ThispaperpresentsESEquivPS(extensionsupportequivalencypruningstrategy),anewsearchspacepruningstrategyforminingmaximalfrequentitemsetstoeffectivelyreducethesearchspace.ESEquivPSwasbasedonadepth-firsttraversaloflexicographicsubsetenumerationtreeandusesequivalencyofitem'sextensionsupportstoprunesearchspace.Furthermore,theMAFIA(maximalfrequentitemsetalgorithm)wasimprovedbyusingESEquivPS.TheexperimentalresultsshowthatESEquivPScanefficientlyreducethesearchspace.Especiallyonsparsedatasetwithlongeritemsets,thesizeofsearchspacecanbetrimmedoffby2/3andnewalgorithmrunsaroundthreetofivetimesfasterthanpreviousMAFIAalgorithm.Keywords:webmining;maximalfrequentitemsets;pruningstrategy;searchspace频繁项集挖掘是一类重要的数据挖掘问题,可以广泛应用在客户行为模式分析、网页关联分析、日志分析和网络入侵检测等重要的Web挖掘工作中。该问题描述如下:给定事务数据库D,项目集合I和用户指定的支持度阈值,频繁项集挖掘是在D中找出支持度大于或等于阈值的所有项集。典型的频繁项集挖掘算法是Apriori以及在此基础上的各种改进算法[1],该类算法采用自底向上广度优先的思想,依次计算出所有的频繁1项集,频繁2项集,直到找出所有的频繁项集。当出现大量长的频繁项集时,该类算法代价很高,需要多次扫描数据库并且产生大量的候选项集,对于长度为m的频繁项集需要枚举出所有可能的2m-2个子集,出现组合问题,导致算法效率低下或无法计算。因此,最大频繁项集挖掘和封闭频繁项集挖掘方法受到该研究领域的重视,先后提出多种重要的最大频繁项集挖掘算法和封闭频繁项集挖掘算法[27]。如何有效地进行搜索空间剪枝是最大频繁项集挖掘研究工作的一个核心[6]。本文提出了一种新的搜索空间剪枝策略:扩展支持度相等性剪枝策略ESEquivPS(extensionsupportequivalencypruningstrategy),该策略基于词典序子集枚举树,利用树中子节点与父节点的扩展集中相同项的扩展支持度相等的特性,对搜索空间进行削减。该策略可以方便的应用到各种最大频繁项集挖掘算法中,大幅度提高算法的效率。本文结合ESEquivPS对MAFIA算法进行了优化改进,并在不同特征的Web数据集上进行了实验验证。实验结果表明,该剪枝策略可以有效削减搜索空间,改进后的算法效率明显优于原有的MAFIA算法。1最大频繁项集挖掘与搜索空间剪枝策略最大频繁项集挖掘问题具体描述如下。本文来源：网络收集与整理，如有侵权，请联系作者删除，谢谢！