【数据挖掘】关联分析之先验(Apriori)原理与Apriori算法

本是古典何须时尚 2022-01-14 04:55 344阅读 0赞

阅读本文之前建议先理解[关联分析的基本概念与术语][Link 1]。[传送门][Link 1]

本文简单介绍关联分析中的先验(Apriori)原理与Apriori算法，持续更新与补充。

### 先验(Apriori)原理 ###

**原理简介：**  
如果一个项集是频繁的，则它的所有子集一定也是频繁的。相反，如果一个项集是非频繁的，则它所有的超集也是非频繁的。  
此原理基于**支持度的反单调性(anti-monotone)**：一个项集的支持度绝不会超过它的子集的支持度。  
基于此原理，我们就能对项集进行 **基于支持度的剪枝(support-based pruning)**，不用计算支持度就能删除掉某些非频繁项集。  
于是便出现了基于先验原理的Apriori算法。

### Apriori算法 ###

Apriori算法是第一个关联规则挖掘算法，它开创性地使用基于支持度的剪枝技术，系统地控制候选项集指数增长。  
对于文章开头表 6-1 中所示的事务，下图 6-5 给出Apriori算法频繁项集产生部分的一个示例。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]  
初始时每个项都被看作 候选1-项集。对它们的支持度计数之后，候选项集 \{可乐\} 和 \{鸡蛋\} 被丢弃。  
在下一次迭代中，就只需使用 频繁1-项集 来产生 候选2-项集 ，由于只有4个 频繁1-项集，因此算法产生的 候选2-项集 的数目为  C ( 4 , 2 ) = 6 C(4, 2) = 6 C(4,2)=6 个。计算它们的支持度之后，发现4个候选项集是频繁的，因此用此4个来产生候选3-项集。  
通过此例子可以看出先验剪枝策略的有效性。枚举所有项集到3-项集的暴力策略过程将产生  
 C ( 6 , 1 ) + C ( 6 , 2 ) + C ( 6 , 3 ) = 6 + 15 + 20 = 41 C(6, 1) + C(6, 2) + C(6, 3)=6+15+20=41 C(6,1)\+C(6,2)\+C(6,3)=6\+15\+20=41 个候选项；而使用Apriori算法，只产生  
 C ( 6 , 1 ) + C ( 6 , 2 ) + 1 = 13 C(6, 1) + C(6, 2) + 1 = 13 C(6,1)\+C(6,2)\+1=13 个候选。候选项集的数目降低了68%。

##### . #####

##### Apriori算法伪代码： #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]  
其中， C k C\_k Ck为 候选k-项集， F k F\_k Fk为 频繁k-项集。

*  该算法初始通过单遍扫描数据集，确定每个项的支持度。产生 频繁1-项集 的集合 F 1 F\_1 F1。（步骤1,2）
 *  然后，该算法将使用上一次产生的 频繁(k-1)-项集，产生新的 候选k-项集（步骤5）。
 *  为了计算新候选项集的支持度，**算法需要再次扫描一遍数据集**（步骤6-10）。使用子集函数发现事务t包含了哪些候选项集。
 *  完成支持度计算后，算法将删去支持度小于支持度阈值minsup的所有候选项集，生成频繁k-项集。  
    当没有新的频繁项集或候选项集产生时，算法结束。

Apriori算法的重要特点：

1.  它是一个逐层 ( level-wise ) 算法,即从频繁1-项集到最长的频繁项集，它每次遍历项集格中的一层；
2.  它使用产生-测试 ( generate-and-test ) 策略来发现频繁项集。在每次迭代之后，新的候选项集都由前一次迭代发现的频繁项集产生，然后对每个候选的支持度进行计数，并与最小支持度阈值进行比较。该算法的总迭代次数是 k m a x + 1 k\_\{max\} + 1 kmax\+1，其中 k m a x k\_\{max\} kmax是频繁项集的最大长度。

[Link 1]: https://steve.blog.csdn.net/article/details/92191884
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: /images/20220114/5fcdebb60d6342c284c23e1b253ee65c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]: /images/20220114/13184d732e4845db8f9e751d978b3937.png