关联规则挖掘算法研究
发布时间：2015-07-04 09:23
摘 要 apriori算法是发现频繁项目集的经典算法，但是该算法需反复扫描数据库，因此效率较低。本文介绍了apriori算法的思想，并分析了该算法的性能瓶颈。在此基础上，针对apriori算法提出了一种改进方法，该方法采用转置矩阵的策略，只扫描一次数据库即可完成所有频繁项目集的发现。与其他经典的算法相比，本文提出的算法在项目集长度较大时，性能明显提高。
关键字 关联规则，支持度，置信度，apriori
1 引言
关联规则挖掘就是在海量的数据中发现数据项之间的关系，是数据挖掘领域中研究的热点问题。1993年agrawal等人[1]首先提出了交易数据库中不同商品之间的关联规则挖掘，并逐渐引起了专家、学者的重视。关联规则挖掘问题可以分为：发现频繁项目集和生成关联规则两个子问题，其中发现所有的频繁项目集是生成关联规则的基础。近年来，发现频繁项目集成为了关联规则挖掘算法研究的重点，在经典的apriori算法的基础上提出里大量的改进算法。savasere等[2]设计了基于划分(partition)的算法，该算法可以高度并行计算，但是进程之间的通信是算法执行时间的主要瓶颈；park等[3]通过实验发现寻找频集主要的计算是在生成频繁2-项集上，利用这个性质park等引入杂凑（hash）技术来改进产生频繁2-项集的方法，该算法显著的提高了频繁2-项集的发现效率；mannila等[4]提出：基于前一遍扫描得到的信息，对此仔细地作组合分析，可以得到一个改进的算法了。针对mannila的思想toivonen[5]进一步提出：先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。toivonen的算法相当简单并显著地减少了i/o代价，但是一个很大的缺点就是产生的结果不精确，存在数据扭曲(data skew)。 上述针对经典apriori算法的改进算法在生成频繁项目集时都需要多次扫描数据库，没有显著的减少i/o的代价。本文在分析了经典的apriori算法的基础上，给出了一种改进的方法，该方法采用转置矩阵的策略，只扫描一次数据库即完成频繁项目集的发现，在项目集长度较大时，性能明显提高。2 apriori算法
2.1 基本概念
设i={i1, i2,…, im}是二进制文字的集合，其中的元素称为项(item)。定义交易(transaction)t为项的集合，并且tíi，定义d为交易t的集合。设x是i中若干项的集合，如果xít，那么称交易t包含x。项目集中包含项的个数成为项目集长度。 关联规则是形如xþy的蕴涵式，这里xìi, yìi，并且xçy=f。 规则xþy在交易数据库d中的支持度（support）是交易集合中包含x和y的交易数与所有交易数之比，记为support(xþy)，即support(xþy)=|{t:xèyít，tîd}|/|d|。 规则xþy在交易集中的置信度（confidence）是指包含x和y的交易数与包含x的交易数之比，记为confidence(xþy)，即confidence(xþy)=|{t: xèyít，tîd}|/|{t:xít，tîd}|。给定一个交易集d，挖掘关联规则就是找出支持度和置信度分别大于用户给定的最小支持度(minsup)和最小置信度(minconf)的关联规则。2.2 基本思想
1994年agrawal等人在项目集格空间理论的基础上提出了用于发现频繁项目集的apriori算法。该算法采用“逐层搜索”的迭代方法，用k-项集生成(k+1)-项集。首先，扫描数据库计算出频繁1-项集的集合（记为：l1）；然后，执行下面的迭代过程计算频繁k-项集，直到生成频繁k-项集的集合（记为：lk）为空： ①连接：lk-1进行自连接运算,生成候选k-项集的集合（记为：c k）。所有的频繁k-项集都包含在c k集合中。 ②剪枝：①生成的c k是lk的超集，扫描数据库计算c k中每个候选项目集的支持度，支持度大于用户给定最小支持度的候选k-项目集就是频繁k-项目集。 通过上述的迭代过程，可以发现项目集i在给定数据库d中满足最小支持度的所有频繁项目集。2.3 算法分析
apriori算法在执行“连接-剪枝”的迭代过程中，需要多次扫描数据库，如果生成的频繁项目集中含有10-项集，则需要扫描10遍数据库，增大了i/o负载。并且在迭代过程中，候选项目集合ck是以指数速度增长的，lk-1自连接会产生大量的候选k-项目集，例如有104个1-项集，自连接后就可以产生大约107个候选2-项集。这些都严重影响了apriori算法的效率。3 改进的apriori算法
3.1 改进思想
apriori算法在迭代过程中多次扫描数据库和产生大量的候选项目集形成了算法的性能瓶颈。为了提高算法的效率本文进行如下改进： 数据库d中每个交易t都有一个唯一的编号tid。定义k-项集rk=<xk，tids(xk)>，其中xk=(ij1, ij2, …, ijk)，ij1, ij2, …, ijk îi，j1<j2< …<jk，tids(xk)是数据库中所有包含xk的交易t的编号tid的集合，即为：tids(xk)={tid : xkít，<tid,t> îd}。根据上面的定义k-项目集rk的支持度可以表示为：support(rk)=|tids(xk)|/|d|=|{tid : xkít，<tid,t> îd}| / |d|。rk的支持数supnum(rk)=support(rk)*|d|=|tids(xk)|。l’k表示k-项集的集合。 改进的apriori算法依然采用“逐层搜索”的迭代方法，迭代过程的“连接-剪枝”运算定义如下： ①连接：设两个(k-1)-项集：l’ k-1 (i)=< xk-1，tids(xk-1) >î l’k-1，l’ k-1 (j)=< yk-1，tids(yk-1) >î l’k-1，i<j。如果xk-1和yk-1的前k-2项相等，即：xk-1[k-2] ≡yk-1[k-2]，则(k-1)-项集连接：l’ k-1 (i)∞l’ k-1 (j)= < xk-1∪yk-1, tids(xk-1) ∩tids(yk-1)>= <xk，tids(xk)>=rkî l’k；否则，不进行连接运算，因为产生的结果不是重复，就是非频繁项目集，这样可减少计算量。 ②剪枝：计算k-项集的支持数，根据上面的定义supnum(rk)=|tids(xk)|，该计算过程不需要再扫描数据库，避免了i/o操作，提高了算法的效率。如果supnum(rk)≥minsupnum，则< xk , |tids(xk)|> î l；否则，从集合l’k中删除rk。