【手撕算法】【Apriori】关联规则Apriori原理、代码实现_apriori算法代码

1.前言

⭐️ 开箱即食，直接复制，懒人传送门：4.1懒人必备，开箱速食

⭐️ 本文主要从原理、代码实现 理论和实战两个角度来剖析Apriori算法

⭐️ 理论部分主要是关于 什么是 频繁项集、支持度、置信度

⭐️ 懒得写代码的，可以直接跳的第五节，直接安装依赖包：5.懒人必备，开箱速食

2.简介

⭐️ 关联规则挖掘算法通常是无监督学习，通过分析数据集，挖掘出潜在的关联规则，最典型的一个例子是啤酒与尿不湿的故事

⭐️ Apriori 是第一个关联规则挖掘算法，也是最经典的算法，它利用逐层搜索的迭代方法找出数据库中项集的关系，以形成规则，其过程由连接（类矩阵运算）与剪枝（去掉那些没必要的中间结果）组成。

⭐️ 该算法既可以发现频繁项集，又可以挖掘物品（项）之间的关联规则。

⭐️ 该算法采用支持度来量化频繁项集，采用置信度来量化关联规则

3.原理

3.0.示例

我们使用如下交易表格来用嘴来仿真我们的Apriori算法的工作步骤，以及介绍他们的概念和原理

交易记录如下：
1
2
3

3.1.概念介绍

⭐️ 支持度： $P(A\cap B)$，表示既有A又有B的概率。例如，我们总共有5个交易订单，其中同时有啤酒 和 尿不湿的总共有3单，那么 $P(A\cap B)=3/5=0.6$，即支持度为0.6

⭐️ 置信度： $P(B|A)$，表示在A发生的事件中同时发生B的概率 $P(AB)/P(A)$, 他表现的是AB两个事件的相关程度，准确来说是A对B的关联程度，注意并非是B对A的关联程度。例如，我们总共有5个交易订单，其中同时有啤酒 和 尿不湿 的总共有3单， 即$P(AB)=3/5=0.6$，我们含有啤酒的订单有5个交易单，则$P(A)=5/5=1.0$含有尿不湿的为3单，则$P(B)=3/5=0.6$，那么啤酒对尿不湿的关联程度为：$P(B|A)=P(AB)/P(A)=0.6/1.0=0.6$，尿不湿对啤酒的关联程度为：$P(A|B)=P(AB)/P(B)=0.6/0.6=1.0$

⭐️ 频繁k项集： 项集即为项的集合，项可以是商品，那么项集就是商品的集合，频繁项集就是经常（满足最小支持度）在一起的物品的集合，例如尿不湿和啤酒，称之为频繁2项集

3.2.Apriori原理

⭐️ 如果某个项集是频繁的，那么他的所有子集也是频繁的，例如：如果最小支持度为0.5，那么啤酒和尿不湿的支持度为0.6，那么他的子集，啤酒和尿不湿的支持度分别为$1.0$和$0.6$

⭐️ 如果某个项集是非频繁的，那么他的所有超集也是非频繁的，例如：如果最小支持度为0.5，牛奶只有两单，两单分别是和啤酒、尿不湿一起购买。那么牛奶的支持度为$2/5=0.4$，其是小于最小支持度的，所以其是非频繁的。而他们的超集为{啤酒, 牛奶} 和 {尿不湿, 牛奶}。他们的支持度分别为 $2/5=0.4$ 和 $1/5=0.2$， 所以他们都是非频繁的，即牛奶的超集是非频繁的。

3.3.优点

⭐️ 该算法的关联规则关联规则是在频繁项集基础上产生的，这可以保证这些规则的支持度达到指定的水平，具有普遍性和令人信服的水平

⭐️ 算法简单，易于理解，对数据的要求低

3.4.缺点

⭐️ 在每一步产生候选项目集的时候循环产生的组合过多，项数越多，越消耗计算资源，如果不剪枝，其时间复杂度为$O(2^n)$，n为项集个数。假如我们有6个项，有6种类型组合方式（单个组合，两两组合，三三组合等），其数学公式为： $C_6^1+C_6^2+C_6^3+C_6^4+C_6^5+C_6^6=2^6-1$

⭐️ 每次计算项集的支持度的时候，都对数据库中的全部数据进行了一遍扫描比较，I/O负载很大。

3.5.算法步骤

⭐️ 我们使用以下步骤来说明我们的算法

第一步：输入数据集X，对应我们的示例为五个交易记录
第二步：确定数据集X中所包含的项集，不重复，对应我们的示例则为{牛奶，巧克力，尿不湿，啤酒，土豆}
第三步：进行第一次迭代，把每个项集中的项目单独扫描统计（即某个项在多少个交易记录中出现了），将每个项都作
		为候选 1 项集 C1 的成员，并计算每个项的支持度
第四步：设定最小支持度，根据候选 1 项集C1的成员，对比其支持度和最小支持度，大于等于最小支持度的为候选 2 
		项集 C2。
第五步：保持最小支持度不变，重复进行第四部，直到没有满足最小支持度的项集，此时输出最终频繁项集。
第六步：设定最小置信度，根据 k 项集CK 和 k+1项集Ck+1，计算k项集的置信度，满足最小置信度的则筛选存储。
第七步：重复第六步，k值从1开始，直到到最大值，返回具有强相关的关联规则列表。
1
2
3
4
5
6
7
8
9

⭐️ 借用俩图说明我们第1~5步

---

-----------------------以下是我们根据3.0的示例部分进行算法工作步骤的说明----------------------------------
1

⭐️ 准备数据：数据库中的交易数据

---

⭐️ 第一轮：先从数据库中扫描，生成 1 项集 C1

⭐️ 第一轮：调用Scan函数，过滤支持度小于0.5的项集，得到频繁 1 项集 L1

---

⭐️ 第二轮：根据 频繁 1 项集 L1，生成 2 项集 C2

⭐️ 第二轮：调用Scan函数，过滤支持度小于0.5的项集，得到频繁 2 项集 L2

---

⭐️ 第三轮：根据 频繁 2 项集 L2，生成 3 项集 C3

⭐️ 第三轮：调用Scan函数，过滤支持度小于0.5的项集，得到频繁 3 项集 L3 因为L3为空，所以算法到这里结束

---

-------------------------------我们采用以下步骤挖掘我们的强关联规则---------------------------------------
1

⭐️ 第一步：获取所有挖掘出来的规则

⭐️ 第二步：过滤置信度小于0.7的规则，生成强规则