Apriori数据挖掘算法.doc

1关联规则的基本概念
假设I={i1,i2,…,im}是所有项的集合,相当于商品的所有种类的集合,D是所有事务的集合,也即数据库中记录的集合,事务T={t1,t2,…,tn},ti∈I,相当于交易中的商品列表.若X、Y是数据项集,X中含有的项数目为K,则称为K-数据项集.
事务集D中的规则XY(其中XI,YI,X∩Y=Φ)是由支持度(support)和确信度(confidence)约束的,支持度表示规则的频度,确信度表示规则的强度.
规则XY在交易数据库D中的支持度是交易集中同时包含XY的交易数与所有交易数之比,记为support(XY)=|{T:X∪YT,T∈D}|/|D|。
规则XY在交易数据库D中的可信度是交易集中同时包含XY的交易数与包含X的交易数之比,记为confidence(XY)=|{T:X∪YT,T∈D}|/|{T:XT,T∈D}|。
给定一个交易集D,挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度(minsupp)和最小确信度(minconf)的关联规则.当规则的确信度和支持度分别大于minsupp、minconf时,我们认为规则是有效的,称为强关联规则.当数据项集X的支持度大于minsupp时,称X为高频数据项集.
2Apriori算法
???Agrawal等在1993年设计了一个基本算法Apriori[4]，为生成所有频繁项集，Apriori使用了递推的方法,其核心思想是：
（1）L1=find_frequent_1-itemsets(D);
（2）for(k=2;Lk-1≠Φ;k++){
（3）Ck=apriori_gen(Lk-1,min_sup);
（4）foreachtransactiont∈D{//scanDforcounts
（5）Ct=subset(Ck,t);//getthesubsetsoftthatarecandidates
（6）foreachcandidatec∈Ct
（7）c.count++;
（8）}
（9）??Lk={c∈Ck|c.count≥min_sup}
（10）}
（11）returnL=∪kLk;
首先扫描一次数据库，产生频繁1项集L1；然后进行循环，在第k次循环中，首先由频繁k-1项集进行自连接和剪枝产生候选频繁k项集Ck，然后使用Hash函数把Ck存储到一棵树上，扫描数据库，对每一个交易T使用同样的Hash函数，计算出该交易T内包含哪些候选频繁k项集，并对这些候选频繁k项集的支持数加1，如果某个候选频繁k项集的支持数大于或等于最小支持数，则该候选频繁k项集为频繁k项集；该循环直到不再产生候选频繁k项集结束。
Apriori算法的缺点：(1)由频繁k-1项集进行自连接生成的候选频繁k项集数量巨大。(2)在验证候选频繁k项集的时候需要对整个数据库进行扫描，非常耗时。
3几种改进的算法思想
虽然Apriori算法自身已经进行了一定的优化，但是在实际的应用中，仍存在不尽人意之处，于是相继出现了一些优化的方法，例如：
a.基于划分的方法.Savasere等提出了一种基于划分(partition)算法,该算法首先将数据库从逻辑上分成几个互不相交的块,每次单独考虑一个分块并生成所有的频集,然后把产生的频集合并,用来生成所有可能的频集,最后计算这些项集的支持度.
b.基于Hash的方法.通过实验可以发现寻找频集主要的计算是在生成频繁2_项集LK上,
Park等利用这一性质引入Hash技术来改进产生频繁2_项集的方法.
c.基于采样的方法.对上一遍扫描得到的信息进行仔细的组合分析,可以得到改进的算法.Toivonen进一步发展了这个思想,他首先使用从数据库中抽取出来的、由采样得到的一些在整个数据库中可能成立的规则,然后用数据库的剩余部分验证这些规则.
d.减少交易的个数.减少用于未来扫描的事务集的大小,其基本原理是：若一个事务不包含长度为k的大项集,则必然不包含长度为k+1的大项集.因此可以将这些事务移去,这样就减少了下一遍扫描中扫描的事务集的个数,这就是Apriori-Tid的基本思想.
下面介绍几个改进算法的思想：
3.1减少数据库内事务的方法
HYPERLINK"http://binaries.spaces.live.com/blog/cns!43D878273D4AB350!136.entry"\t"_blank"从Apriori算法可以看出,对每一Ci均对数据库扫描一次,而这时有些事务已经对频繁项集的生成不产生作用,减少数据库D内不起作用的事务对于算法来说是很有必要的,本算法的基本思想就基于此。文[6]中对此进行了刻划,文[6]的算法是在每次计算Ci支持记数的过程中,给不包含Ci中的任何项集的事务打上删除标记,在以后的扫描计数中不加考虑。其实在C