1. 首页
  2. 自学中心
  3. 理论
  4. 机器学习

Apriori算法

Apriori 算法是数据挖掘中一种挖掘关联规则的频繁项集算法。其核心是基于两阶段频集思想的递推算法。

先来了解下关联规则挖掘:

发现事务数据库,关系数据 ,  或其它信息库中项或数据对象集合间的频繁模式。关联,相关,或因果关系结构。

频繁模式:在数据库中频繁出现的模式 ( 项集 ,  序列 ,  等 ) 。

动机是发现数据中的规律性。

如:

购物篮分析:哪些产品更经常一起购买 ?   啤酒 和 尿布 ?!

购买了 PC 后 ,  哪些将相继购买 ?

什么类型的  DNA  对新药敏感 ?

我们能自动地对 Web 文档分类吗 ?

再来看看几个概念:

支持度 :s (support) ,事 务包含  X ∪ Y  的 概率。

置信度 :c (confidence) , 事务含  X  也包含  Y  的 条件概率p(Y|X)。

频繁项集 : I, 项集 I 的相对支持度满足预定义的最小支持度阈值

e48310bae04b1adfd3b5dca533a3e28c

Apriori 算法 :

Apriori 算法的核心是使用候选项集寻找频繁项集。 Apriori 使用一种称为逐层搜索的迭代方法, k- 项集用于搜索( k+1 ) – 项集。首先,找出所有频繁 1- 项集 L1 ,然后用 L1 寻找 L2 ,用 L2 寻找 L3, 如此,直至不能找到频繁 k- 项集为止。

Apriori 性质 :

频繁项集的所有非空子集肯定也是频繁的。

如 :

每个包含  {beer, diaper, nuts} 的事务 也包含  {beer, diaper}

如果  {beer, diaper, nuts}  是频繁的 , {beer, diaper} 也是

转换一下思维,如果一个子集是非频繁的,那么它的超集也一定是非频繁的。这在Apriori 算法里面很重要。

利用 Apriori 性质,我们在使用频繁 (k-1)- 项集 L(k-1) 寻找频繁 k- 项集 L(k) 时分两个过程:连接步和剪枝步。

连接步 

L(k-1) 与其自身进行连接,产生候选项集 C(k) 。 L(k-1) 中某个元素与其中另一个元素可以执行连接操作的前提是它们中游 (k-2) 个项是相同的。也就是只有一个项是不同的。

如:项集 {I1,I2} 与 {I1,I5} 连接之后产生的项集是 {I1,I2,I5} ,而项集 {I1,I2} 与 {I3,I4}不能进行连接操作。

剪枝步 :

候选集 C(k) 中的元素可以是频繁项集,也可以不是。但所有的频繁 k- 项集一定包含在 C(k) 中,所以, C(k) 是 L(k) 的超集。扫描事物集 D ,计算 C(k) 中每个候选项出现的次数,出现次数大于等于最小支持度与事务集 D 中事务总数乘积的项集便是频繁项集(这里的最小支持度指的是概率,实际中我们经常直接将最小支持度看成乘积后的结果),如此便可确定频繁 k- 项集 L(k) 了。

但是,由于 C(k) 很大,所以计算量也会很大。为此,需要进行剪枝。即压缩 C(k),删除其中肯定不是频繁项集的元素,依据就是前面提到的 Apriori 性质:如果一个子集是非频繁的,那么它的超集也一定是非频繁的。这在 Apriori 算法里面很重要。如此,如果一个候选 (k-1)- 子集不在 L(k-1) 中,那么该候选 k- 项集也不可能是频繁的,可以直接从 C(k) 中删除。

这里看一个例子就可以理解了:

83fa1ccee1aff5afb8008053c156c645

所以,满足条件的所有频繁项集有 {A} 、 {B} 、 {C} 、 {E} 、 {A 、 C} 、 {B 、 C}、 {B 、 E} 、 {C 、 E} 、 {B 、 C 、 E}

算法伪代码 :

C[k]: 长度为 k的候选项集
L[k] : 长度为k的频繁项集

L[1] = {频繁项};
for (k = 1; L[k] !=∅; k++) do begin
    C[k+1] = 由 L[k]产生的候选;
    for each 数据库中的事务t  do
      增加包含在t 中的所有候选C[k+1]的计数
    L[k+1] = C[k+1]中满足 min_support的候选
    end
return   L[1..k];

原文:http://blog.csdn.net/epluguo/article/details/27800625

原创文章,作者:xsmile,如若转载,请注明出处:http://www.17bigdata.com/apriori%e7%ae%97%e6%b3%95/

联系我们

在线咨询:点击这里给我发消息

邮件:23683716@qq.com

跳至工具栏