一种基于关联规则Apriori算法的改进研究

关联规则挖掘Ａｐｒｉｏｒｉ算法的改进作者：朱烨叶高英来源：《现代电子技术》2008年第18期摘要：在介绍Apriori算法原理和实现过程的基础上，针对该算法存在的两个缺陷，即多次扫描事务数据库和产生大量的候选集，提出新的算法NewApriori，该算法改变由低维频繁项目集到高维频繁项目集的多次连接运算，直接从1频繁项目集产生高维频繁项目集，克服了Apriori算法的固有缺点，从而提高了运算效率。

关键词：关联规则挖掘；Apriori算法；频繁项目集；侯选数据集中图分类号：TP311 文献标识码：B 文章编号：1004373X(2008)1807803Improvement of Apriori Algorithm in Association Rule MiningZHU Ye,YE Gaoying(Chengdu University of Information Technology,Chengdu,610225,China)Abstract：In this paper,the principle and performance of Apriori algorithm is introduced,and two defects of Apriori algorithm:scanning database too much and creating excessive candidate itemsets are analyzed.A new Apriori algorithm has been designed for finding out the highest dimension frequent itemsets from frequent 1itemset directly.A great number of linking operations in finding frequent itemsets dimension by dimension are canceled over all.The algorithm is improved efficiently.Keywords：association rule mining;Apriori algorithm;frequent itemset;candidate itemset1 引言数据挖据［1］(Data Mining)是一个多学科交叉研究领域，是从大量数据中提取或“挖掘”出未知的、潜在的、有用的知识。

福建电脑2012年第12期关联规则挖掘Apriori算法的改进王琼，曹奎（河南大学计算机与信息工程学院河南开封475004）【摘要】：关联规则的提取是数据挖掘中重要的研究课题，目的在于挖掘事务数据库中有趣的关联，Apriori算法是挖掘关联规则的经典算法。

该文对Apriori算法进行研究，发现该算法存在着一些缺点，并对其进行改进，用实例说明这些改进能够正确有效的实现该算法。

【关键词】：关联规则；Apriori算法；频繁项集；事务集1、引言在信息时代,计算机内存储有大量的数据,这些数据蕴含了丰富的知识，为了获取这些知识，需要一种能够分析数据、获取有用知识的技术。

数据挖掘能够从大规模数据中集中提取隐含的人们所不知道的潜在的有用知识和信息，近年已经在许多领域得到了应用。

规则关联挖掘是数据挖掘的一个分支，用来发现大量数据中项集之间有趣的关联或相关联系。

从商务事务库发现有趣的关联关系可以有助于制定商务决策，典型的例子是购物篮分析，可以通过分析不同顾客放入购物篮的不同商品之间的联系得到顾客的购物习惯。

关联规则挖掘的核心是寻找频繁项集，Apriori算法是Rakesh Agrawal和Ramakrishnan Skfikant提出的最经典的关联规则提取算法，但是该算法存在着许多的不足，例如产生大量的候选，对一些无用的事务进行重复扫描等等，因此提高算法的效率就成了研究人员的一个重要任务。

2、关联规则的提取设I=(i1,i2,…,i n)是n个不同元素的集合，其中的元素称之为项，相当于商品不同种类的集合。

事务库T是事务（t1，t2…t m）的集合,tj(1≤j≤m)是项的集合且t j哿I，t j包含的内容可以看做每次交易的商品列表。

关联规则的形式是形如X=>Y的蕴含式（X哿I,Y哿I,X∩Y=Φ）,意义为一条交易记录中包含集合X则该交易也包含集合Y。

规则的支持度是指在事务库中同时包含集合X和集合Y的事务所占的比例，记做support（X=>Y），规则的置信度是指在同时包含集合X和集合Y的事务在只包含集合X的事务所占的比例，记做confi-dence(X=>Y)。

收稿日期:2010-05-17;修回日期:2010-07-17。

基金项目:教育部科学研究项目(09yj c870032);重庆市科技攻关计划项目(CSTC2008AC2126;CSTC2009AC2034);重庆市自然科学基金资助项目(CSTC2008BB2065);重庆理工大学科研青年基金资助项目(2010ZQ22)。

作者简介:崔贯勋(1978-),男,河南鄢陵人,实验师,硕士,主要研究方向:数据库; 李梁(1964-),男,重庆人,副教授,主要研究方向:软件工程; 王柯柯(1977-),女,四川南充人,讲师,硕士,主要研究方向:软件工程; 苟光磊(1980-),男,重庆人,实验师,硕士,主要研究方向:人工智能; 邹航(1979-),男,重庆人,实验师,硕士,主要研究方向:数据挖掘。

文章编号:1001-9081(2010)11-2952-04关联规则挖掘中Apri ori 算法的研究与改进崔贯勋,李 梁,王柯柯,苟光磊,邹 航(重庆理工大学计算机科学与工程学院,重庆400054)(cgxy @vi p .qq .co m )摘 要:经典的产生频繁项目集的Apr i o ri 算法存在多次扫描数据库可能产生大量候选及反复对候选项集和事务进行模式匹配的缺陷,导致了算法的效率较低。

为此,对A prior i 算法进行以下3方面的改进:改进由k 阶频繁项集生成k +1阶候选频繁项集时的连接和剪枝策略;改进对事务的处理方式,减少A pr i or i 算法中的模式匹配所需的时间开销;改进首次对数据库的处理方法,使得整个算法只扫描一次数据库,并由此提出了改进算法。

实验结果表明,改进算法在性能上得到了明显提高。

关键词:数据挖掘;关联规则;A pr i or i 算法;频繁项集;候选项集中图分类号:T P311.13 文献标志码:AR esearch and i m prove m ent on Apriori algorith m of associ ati on rule m i ni ngC U I Guan -xun ,L I L iang ,WANG Ke -ke ,GOU Guang -le,i ZOU H ang(S c h ool of C o mpu ter S cience and Eng i n e ering,Chongqing Un i v e rsit y of T ec hnolo gy,Ch ong qi ng 400054,Ch i na )Abstract :T he c lassic Apr i o ri algor it h m for discovering frequent ite m sets scans the database m any ti m es and the pa ttern m atch i ng bet w een cand i date ite m sets and transacti ons is used repea ted l y ,so a large nu m ber of candida te ite m sets w ere produced ,w hich results i n l ow e fficiency o f the a l gor ith m.The i m proved A prior i a l gor it hm i m proved it from t hree aspects :firstly ,the strategy o f the jo i n step and the prune step w as i m proved when cand i da te frequent (k +1)-i te m setsw ere generated from frequent k -ite m se ts ;second l y ,t he m ethod of dea li ng w it h transacti on w as i m proved to reduce the ti m e of pattern m atch i ng to be used i n the Apr i o ri a l gor it hm ;i n the end ,t he me t hod o f deali ng w ith da tabase w as i m proved ,wh ich lead to only once scann i ng o f t he da tabase dur i ng the w ho le course of the a l go rith m.A cco rding to these i m prove m ents ,an i m proved algor it h m was i ntroduced .The effic i ency of A pri o ri algor it h m got i m prove m ent both i n ti m e and i n space .T he experi m ental results o f the i m proved a l gor ith m show that t he i m proved a l go rith m is mo re e fficient than the orig i na.lK ey words :data m i ning ;asso ciati on ru le ;A priori a l go rith m;frequent ite m sets ;candida te i te m se t0 引言关联规则挖掘作为数据挖掘的重要研究内容之一,主要研究事务数据库、关系数据库和其他信息存储中的大量数据项之间隐藏的、有趣的规律。

Apriori算法的改进及实例
Apriori算法是一种数据挖掘中经典的关联规则挖掘方法。

它被广泛用于挖掘大量数据中的隐式关联，从而发现购物篮（market basket）分析中的频繁项集和关联规则。

随着数据处理能力和分析能力的不断提升，Apriori算法也不断出现改进版本，使其在实际的商业领域中有更好的应用和发挥。

1. 算法模型的改进
Apriori算法在计算复杂度方面有一定的缺陷。

若数据集是大量的，则计算费时会变得很长。

而如何加快Apriori算法的运算，也成为学习者所探讨的问题之一。

改进的Apriori算法通过层次划分处理数据，来加快其处理速度，从而增强其在实际应用中的可行性。

2. Apriori算法的改进实例
例如，若采用层次划分的Apriori算法来挖掘购物篮（market basket）分析中的频繁项集和关联规则，首先可以将数据集根据项数进行划分。

具体而言，若某个项集有n个项，则可以将其划分为n个子集，每个子集的项数均小于n。

然后，用Apriori算法计算每个子集中的支持度，再综合其结果，用Apriori算法得出最终的结果。

这样，可以大大提高Apriori算法的运算效率，从而加快关联规则的挖掘过程。

此外，其他对Apriori算法的改进还包括增加处理噪声数据等方法。

比如，人们可以使用深度学习和模式发现方法在做Apriori算法改进时，来处理杂讯和非结构型数据，以便找出更准确的频繁项集和关联规则。

如果能够成功地完成这项改进，将更加方便地挖掘大规模的市场数据，使得购买者与销售者之间的贴合度更加接近，以便更有效地挖掘出商业价值。

爨塑：笠凰．基于关联规则的A pr i or i挖掘算法改进辛文(南昌理工学院计算机学院，江西南昌330063)j。

j?j?一jj j j睛蜀关联援剥挖掘是—种主要的也是用途最广的数掘挖掘方法。

本文首先对关联授剧挖掘缓其经典A pri o一算法作了介绍，然后针对；A pfi of i算法的缺陷．提出了一种瑰进的关联规则挖掘算法，充分地证明了改进算法的性能优势。

：j陕键词】数撇；关嬲4；Apfiofi’，7，-。

J』』‘随着数据库技术的快速发展，全球范围内的数据存储量急骤上升，激增的数据背后隐藏着许多潜在的信息，然而，缺乏了对数据进行深层次分析的技术，导致了“数据丰富但知识贫乏。

的现象。

如何理解已有的历史数据并用以预测未来的行为，如何从这些海量数据中发现信息，变波动的数据为主动的知识，如何快速、准确地获得有价值的信息，指导政府和企业决策，获取更大的经济效益和更好的社会效益，都迫使人们去寻找新的、更为有效的数据分析手段对各种“数据矿藏”进行有效的挖掘以发挥其应用潜能。

面对这—挑战，数据挖掘技术应运而生。

1关联规则挖掘经典算法A pn od数据挖掘中，关联规则的挖掘是一个重要的问题。

关联规则发现最初的形式是零售商的货篮分析，货篮分忻是通过发现顾客放入其货篮中的不同商品，即不同项之间的关联，这种关联的发现可以帮助零售商制定营销策略。

货篮分析的典型应用是可以帮助经理设计不同的商品布局。

关联规则就是从大量的数据中挖掘出有价值描述数据项之间相互联系的有关知识。

随着收集和存储在数据库中的数据规模越来越大，人们对从这些数据中挖掘相应的关联知识越来越有兴趣。

挖掘关联规则主要包含以下两个步骤：首先发现所有的频繁项集，根据定义，这些项集的频度至少应等于最小支持频度。

然后根据所获得的频繁项集，产生相应的强关嬲Ijo根据定义这些规则必须满足最／J睢泊接。

A pri or i算法简介Input：D at abas eD，m i ns u【帅i ni m um s uppor t t h r es ho l cD；O ut put：L，f r equent i t em set s i n D．1)L，=0ar ge1-i t em set s}；2)f or a(=2；L hT≠D；k++)do begi n3)C,=A pr i or i—gen(Lk．)；／／新的侯选集4)for al l t r a nsa ct i on s t E D do begi n5)C产s ubs eH C01}；，，事务t中包含的候选集6)for al l ca nd i da t e s C E c f do7)c count++；8)e nd9)￡．砖∈C,l c．count>一m i nsu@10)end”)A nsw er=U“2A D r br i算法的改进现在我们来讨论一下具体的改进算法。