Apriori算法详解

1Apriori算法详解之【一、相关概念和核心步骤】Apriori算法核心步骤感谢红兰整理的PPT，简单易懂，现在将其中精彩之处整理，与大家分享。一、Apriori算法简介：Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。Apriori（先验的，推测的）算法应用广泛，可用于消费市场价格分析，猜测顾客的消费习惯；网络安全领域中的入侵检测技术；可用在用于高校管理中，根据挖掘规则可以有效地辅助学校管理部门有针对性的开展贫困助学工作；也可用在移动通信领域中，指导运营商的业务运营和辅助业务提供商的决策制定。二、挖掘步骤：1.依据支持度找出所有频繁项集（频度）2.依据置信度产生关联规则（强度）三、基本概念对于A-B①支持度：P(A∩B)，既有A又有B的概率②置信度：P(B|A)，在A发生的事件中同时发生B的概率p(AB)/P(A)例如购物篮分析：牛奶⇒面包例子：[支持度：3%，置信度：40%]2支持度3%：意味着3%顾客同时购买牛奶和面包置信度40%：意味着购买牛奶的顾客40%也购买面包③如果事件A中包含k个元素，那么称这个事件A为k项集事件A满足最小支持度阈值的事件称为频繁k项集。④同时满足最小支持度阈值和最小置信度阈值的规则称为强规则四、实现步骤Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法Apriori使用一种称作逐层搜索的迭代方法，“K-1项集”用于搜索“K项集”。首先，找出频繁“1项集”的集合，该集合记作L1。L1用于找频繁“2项集”的集合L2，而L2用于找L3。如此下去，直到不能找到“K项集”。找每个Lk都需要一次数据库扫描。核心思想是：连接步和剪枝步。连接步是自连接，原则是保证前k-2项相同，并按照字典顺序连接。剪枝步，是使任一频繁项集的所有非空子集也必须是频繁的。反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从CK中删除。简单的讲，1、发现频繁项集，过程为（1）扫描（2）计数（3）比较（4）产生频繁项集（5）连接、剪枝，产生候选项集重复步骤（1）~（5）直到不能发现更大的频集2、产生关联规则，过程为:根据前面提到的置信度的定义，关联规则的产生如下：（1）对于每个频繁项集L，产生L的所有非空子集；（2）对于L的每个非空子集S，如果3P（L）/P（S）≧min_conf则输出规则“SàL-S”注：L-S表示在项集L中除去S子集的项集一、Apriori算法伪代码实现：[plain]viewplaincopy1.伪代码描述：2.//找出频繁1项集3.L1=find_frequent_1-itemsets(D);4.For(k=2;Lk-1!=null;k++){45.//产生候选，并剪枝6.Ck=apriori_gen(Lk-1);7.//扫描D进行候选计数8.Foreach事务tinD{9.Ct=subset(Ck,t);//得到t的子集10.Foreach候选c属于Ct11.c.count++;12.}13.//返回候选项集中不小于最小支持度的项集14.Lk={c属于Ck|c.count=min_sup}15.}16.ReturnL=所有的频繁集；17.第一步：连接（join）18.Procedureapriori_gen(Lk-1:frequent(k-1)-itemsets)19.Foreach项集l1属于Lk-120.Foreach项集l2属于Lk-121.If((l1[1]=l2[1])&&(l1[2]=l2[2])&&……&&(l1[k-2]=l2[k-2])&&(l1[k-1]l2[k-1]))22.then{23.c=l1连接l2//连接步：产生候选24.//若k-1项集中已经存在子集c则进行剪枝25.ifhas_infrequent_subset(c,Lk-1)then26.deletec;//剪枝步：删除非频繁候选27.elseaddctoCk;28.}529.ReturnCk;30.第二步：剪枝（prune）31.Procedurehas_infrequent_sub(c:candidatek-itemset;Lk-1:frequent(k-1)-itemsets)32.Foreach(k-1)-subsetsofc33.Ifs不属于Lk-1then34.Returntrue;35.Returnfalse;二Apriori算法例子：6三、总结：①Apriori算法的缺点：(1)由频繁k-1项集进行自连接生成的候选频繁k项集数量巨大。(2)在验证候选频繁k项集的时候需要对整个数据库进行扫描，非常耗时。②网上提到的频集算法的几种优化方法：1.基于划分的方法。2.基于hash的方法。3.基于采样的方法。4.减少交易的个数。我重点看了“基于划分的方法”改进算法，现在简单介绍一下实现思想：基于划分(partition)的算法，这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。其中，partition算法要注意的是分片的大小选取，要保证每个分片可以被放入到内存。当每个分片产生频集后，再合并产生产生全局的候选k-项集。若在多个处理器分片，可以通过处理器之间共享一个杂凑树来产生频集。看这个图基本再对照伪代码，基本就可以看懂了~简单明了。