关联规则挖掘Apriori算法的改进

福建电脑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)。关联规则挖掘的目的是寻找给出事务集合里满足最小支持度与最小置信度关联规则,这些规则称为强关联规则。

关联规则的挖掘问题可以分解为两个子问题:

(1)寻找事务库里所有支持度不小于用户给定的最小支持度的项集。

(2)根据找到的项集和用户指定的最小置信度生成规则。

3、Apriori算法

Apriori算法生成频繁项目集的过程如下:在第一次遍历事务库的过程中,计算事务库中所有的单个项的支持度,生成长度为1的频繁项集L1。由L1自链接产生长度为2的候选项集C2,对于事务库里的每一个事务t求出该事务包含在候选项集的子集,并对子集里面的成员计数。事务库扫描完成后将支持度大于最小支持度的所有候选加入集合L2,接下来重复这个过程直到没有新的频繁项集的生成,最后在所有的频繁项集里产生强关联规则。算法通过多次扫描事务数据库来发现所有的频繁项集,在每次扫描过程中只考虑同一种长度的项集。

由于事务库规模通常非常大,对每次生成的候选项集进行支持度计数是非常耗时的,Apriori 算法利用频繁项集的所有子集一定是频繁项集,非频繁项集的任何超集不可能为频繁项集的性质来对不可能成为频繁项集的候选项集进行裁剪,以减少对数据库进行不必要的扫描进而提高算法的效率。但是算法还有一些可以进行改进的地方:(1)算法生成的候选项集的数目仍然很大。(2)每次计算候选项集支持度的时候需要对事务库进行扫描,Apriori算法每次扫描的数据库事务量不变,有些事务对后续扫描没有作用。

4、Apriori算法的改进

84

相关推荐
相关主题
热门推荐