apriori推荐算法

ゝ一纸荒年。 2022-08-09 11:58 200阅读 0赞

Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。

概念

（1）支持度（Support）：定 义为 supp(X) = occur(X) / count(D) = P(X)（有绝对支持度（个数）和相对支持度（百分比）之分）。

（2）频集：支持度大于最小支持度的项集称为频繁项集，简称频集，表示为L\[k\]。频繁集的子集一定是频繁集。

（3）候选集（Candidate itemset）：通过向下合并得出的项集。定义为C\[k\]。

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

光看概念太抽象，看下面这个例子就明白是怎么回事了。

Apriori寻找频繁项集的过程是一个不断迭代的过程，每次都是两个步骤，产生候选集Ck（可能成为频繁项集的项目组合）；基于候选集Ck计算支持度，确定Lk。  
Apriori的寻找策略就是从包含少量的项目开始逐渐向多个项目的项目集搜索。  
数据如下：

![20151022205941803][]

会员100购买了 1 3 4三种商品，那么对应的集合形式如右边的图所示。那么基于候选集C1，我们得到频繁项集L1，设定的支持度为2，支持度大于或者等于指定的支持度的最小阈值就成为L1了，这里\{4\}没有成为L1的一员。因此，我们认定包含4的其他项集都不可能是频繁项集，后续就不再对其进行判断了。

![20151022210152384][]

此时我们看到L1是符合最低支持度的标准的，那么下一次迭代我们依据L1产生C2（4就不再被考虑了），此时的候选集如右图所示C2（依据L1\*L1的组合方式）确立。C2的每个集合得到的支持度对应在我们原始数据组合的计数，如下图左所示。

![20151022210213984][]

此时，第二次迭代发现了\{1 2\} \{1 5\}的支持度只有1，低于阈值，故而舍弃，那么在随后的迭代中，如果出现\{1 2\} \{1 5\}的组合形式将不被考虑。

![20151022210246061][]

如上图，由L2得到候选集C3，那么这次迭代中的\{1 2 3\} \{ 1 3 5\}哪去了？如刚才所言，\{1 2\} \{1 5\}的组合形式将不被考虑，因为这两个项集不可能成为频繁项集L3，此时L4不能构成候选集L4，即停止。  
如果用一句化解释上述的过程，就是不断通过Lk的自身连接，形成候选集，然后在进行剪枝，除掉无用的部分。

上面看明白了下面这张图你就能看懂了。

![20151022210330317][]

算法伪代码

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\];

[探索推荐引擎内部的秘密，第 1 部分: 推荐引擎初探][1 _]

[ALS矩阵分解推荐模型][ALS]

[隐性反馈行为数据的协同过滤推荐算法][Link 1]

[20151022205941803]: /images/20220731/346ede7bacc24f7c90a6a8b0a2100f33.png
[20151022210152384]: /images/20220731/4f0e1f2098b94d15865c90092409b8e0.png
[20151022210213984]: /images/20220731/6aba329254904e80ac7c0b433e8a1fe5.png
[20151022210246061]: /images/20220731/cb4698dc2315424787bf5e9f912f6c41.png
[20151022210330317]: /images/20220731/60d0832e872e4014b034d8051b82e234.png
[1 _]: http://www.ibm.com/developerworks/cn/web/1103_zhaoct_recommstudy1/index.html
[ALS]: http://blog.csdn.net/lingerlanlan/article/details/44085913
[Link 1]: http://blog.csdn.net/lingerlanlan/article/details/46917601