关联规则挖掘Apriori算法的优化.pdfVIP

计 算 机 系 统 应 用 2010年 第 19卷 第 8期 关联规则挖掘Apriori算法的优化① 王胜和 (安徽公安职业学院 公安科技系 安徽 合肥 230031) 朱玉全 (江苏大学 计算机科学与通信工程学院江苏 镇江 212000) 摘 要： 针对Apriori算法存在的不足，提出了一种新的优化Apriori的方法。该方法通过优化频繁项集修剪 策略，减少无效候选项集的产生；优化连接策略，减少连接次数，避免相同项 目的多次重复比较；结 合事务数据库逐步压缩技术，减少对无用事务的扫描次数。实验结果表明，经过优化的Apriori算法 具有更好的运行效率。 关键词： 关联规则：apriori算法：事务压缩：数据挖掘 OptimizedAprioriAlgorithm forM iningAssociationRules WANGSben {e(DepamnentofPublicSecurityTechnology,AnhuiPoliceProfessionalCollege,Hefei23003l，China) ZHUYu-Quan(SchoolofComputerScienceandCommunicationEngineering,JinagsuUniversity,Zhnejinag 212013，Ct~a) Abstract： ToaddressdisadvantagesoftheApriorialgorithm，anewmethodispresentedtooptimizehteApriori．Itcan reducehtenumberofinvalid cnadidateitem setsthroughoptimizinghtestrategyoffrequenttiem sets prunnig．In ordertore~ cehteconnectionsofitems，avoidrepeated comparisonofhtesameitems，it optimizeshtejoiningstrategy．Anditalsoremoveshteuselesstransactionsfromdatabasestepbystepni ordertoreducehtetimesofscanningtransactions．Theresultsofexperimentshow htathteoptimized algorithm ismoreefficient． Keywords：associationrule；apriorialgorithm；transactionreduction；datamining 1 引言 有 K维候选项集的支持度 ，从而求出K维频繁项集。 数据挖掘是一种从大量数据中提取出隐含的、未 通过对 Apriori算法的分析，可以发现算法存在明显 知的、潜在的和有用的信息的过程。数据挖掘是解决 的不足：(1)算法在连接前，没有排除不可能成为频繁项 当今 “数据爆炸而知识贫乏”的一种有效办法。虽然 集的项 目，将产生巨大的候选项集。(2)算法在连接过 数据挖掘技术的发展仅有短短十余年的历史，但发展 程中，通过模式匹配来决定两项集是否连接 ，重复比 势头却相当迅猛 ，现已在实际领域中得到广泛的应用， 较的项目太多。(3)没有对事务数据库及时压缩，对无 并且产生了良好效果。关联规则是由R．Agrawal等人 用事务重复扫描。针对Apriori算法的不足，一些学 于 1993年提出的，是数据挖掘问题中的一个重要研 者从不同的角度改进了Apriori算法。文献2【】从项集 究内容。Apriori算法1【】是最有影响的挖掘布尔关联规 约简、连接策略优化、事务压缩方面对 Ap