关联规则中改进FP-tree的最大频繁模式挖掘算法.pdfVIP

计算机工程与设计 ComputerEngineeringandDesign 2010 ，31(21) 4635 ·软件与算法 · 关联规则中改进FP．tree的最大频繁模式挖掘算法 钱雪忠， 惠 亮 (江南大学信息工程学院，江苏 无锡 214122) 摘 要：关联规则挖掘是数据挖掘领域中重要 的研究 内容 ，最大频繁模式挖掘又是关联规则挖掘 中的关键 问题之一。针对 已有的最大频繁模式挖掘算法存在的问题 ，通过对FP—Growth、FP—Max算法的分析，提 出了基于改进FP—tree的最大频繁模式 挖掘算法DFP—Max。该算法使用预测 、剪枝的策略减少条件FP—tree个数，采用数字集匹配代替项集匹配的方式，减少超集检 验的次数，并且避免了中间结果的组合连接 ，从而使 算法达到较高的效率。实验结果表明，在支持度相对较小情况下，DFP— Max的效率是同类算法的2～5倍 关键词：关联规则；数据挖掘；FP—tree；最大频繁项集；超集检验 中图法分类号：TP311 文献标识码：A 文章编号：1000—7024(2OLO)214635．04 Miningalgorithm ofmaximalfrequentpatternbasedonimprovedFP—treeinassociationrules QIANXue-zhong， HUILiang (SchoolofInformationEngineering，JiangnanUniversity,Wuxi214122，China) Abstract：Miningassociationrulesisanimportantmatterindatamining， inwhichminingmaximalrfequentpatternisakeyproblem inminingassociationurles．Aimedattheproblem oftheexistingalgorithms，analgoritmh ofminingmaximalfrequentpattems— — DFP—Maxalgorithm basedonimprovedFP—treeisputforwardafterthealgorithmsofFP—Growt handFP—Maxisanalyzed．Thisalgoritmh usesthestrategyofpredictionnadpruningtoreducethenumberofgeneratedconditionFP—tree，whichcannotonlyreducethechecking timesbutalsoavoidthecombinationconnectionofintermediateresultsbyusingdigitalsetmatchinginsteadofthetestingstrateyg ofitem- setsmatching．TheexperimentshowshtathteefficiencyofDFP—Maxistwotofivetimesasmuchasthatofthesimilaralgoritmh snihte caseofarelativelysmallsupport． Keywords：associationrules；datamining；FP—tree；maximalrfequentitemsets； supersetchecking 鉴于 目前的算法中以基于FP-rtee的挖掘算法效果较好， 0 引 言 故综合考虑 以上各算法 ，提高挖掘最大频繁项集的效率，可 以 在关联规则挖掘中，频繁项集的挖掘是数据挖掘任务的基 从以下几个方面做工作：①减少或不生成条件FPrtee；②如果 础 。其挖掘算法 的效率直接关系到挖掘任务能否高效