挖掘最大频繁项集的优化方法.pdf

挖掘最大频繁项集的优化方法 1 1 1，2 唐 瑜 ，王 勇 ，杨辉华 （1.桂林电子科技大学，广西 桂林 541004； 2.清华大学 分析中心药物研究所，北京 100084） E-mail：flyfish@ 摘 要：通过对Apriori算法以及已有相关研究工作的分析，从数据库维数压缩、项存储结构以及剪枝几个方面对算法进 行了优化，并从理论与试验两方面验证了优化算法的有效性。 关键词：Apriori算法；频繁项集；关联规则 文章编号：1002-83312（006）31-0171-03 文献标识码：A 中图分类号：TP311 OptimizedMethodforMiningMaximum FrequentItemsets 1 1 1，2 TANGYu，WANGYong，YANGHui-hua （1.GuilinUniversityofElectronicTechnology，Guilin，Guangxi541004，China； 2.AnalysisCenterInstituteofPharmacology，TsinghuaUniversity，Beijing100084，China） Abstract：BasedontheanalysisofApriorialgorithm andtherelativeresearchwork，theauthorspresentseveral optimizationsonthecompressionofdatabasedimension，thestoragestructureofitem andpruning，also，theauthors validatethevalidityoftheoptimizedmethodsonboththeoryandexperiments. Keywords：Apriorialgorithm；frequentitemsets；associationrule [1] 5（） C=subsetC（，T）；/*获取事务T的属于候选集的子集*/ 关联规则是数据挖掘研究的重要模式之一 ，主要用于挖 T K 掘大量数据中项集之间有趣的关联或相关联系。关联规则挖掘 6（） foreachcandidatec∈C do T 过程主要分两步：（1）找出所有的最大频繁项集；2（）由频繁项 7（） c.count++； 集产生强关联规则。由于第一步需要多次扫描数据库而占用大 8（） } 量时间，故关联规则挖掘效率主要取决于最大频繁项集挖掘速 9（） L={c∈C|c.count≥minsup} K K 度，当前许多研究也是对此展开的。Apriori算法是Agrawal等 （10）} （11）retur