一步步教你轻松学关联规则Apriori算法
（白宁超 2018年10月22日09:51:05）
摘要：先验算法（Apriori Algorithm）是关联规则学习的经典算法之一，常常应用在商业等诸多领域。本文首先介绍什么是Apriori算法，与其相关的基本术语，之后对算法原理进行多方面剖析，其中包括思路、原理、优缺点、流程步骤和应用场景。接着再通过一个实际案例进行语言描述性逐步剖析。至此，读者基本了解该算法思想和过程。紧接着我们进行实验，重点的频繁项集的生成和关联规则的生成。最后我们采用综合实例进行实际演示。（本文原创，转载必须注明出处.）
理论介绍 算法概述维基百科
在计算机科学以及数据挖掘领域中，先验算法（Apriori Algorithm）是关联规则学习的经典算法之一。先验算法的设计目的是为了处理包含交易信息内容的数据库（例如,顾客购买的商品清单，或者网页常访清单。）而其他的算法则是设计用来寻找无交易信息（如Winepi算法和Minepi算法）或无时间标记（如DNA测序）的数据之间的联系规则。
先验算法采用广度优先搜索算法进行搜索并采用树结构来对候选项目集进行高效计数。它通过长度为\( k-1 \)的候选项目集来产生长度为 k 的候选项目集，然后从中删除包含不常见子模式的候选项。根据向下封闭性引理,该候选项目集包含所有长度为 k 的频繁项目集。之后，就可以通过扫描交易数据库来决定候选项目集中的频繁项目集。
数据挖掘十大算法
Apriori 算法是一种最有影响力的挖掘布尔关联规则的频繁项集算法，它是由Rakesh Agrawal 和RamakrishnanSkrikant 提出的。它使用一种称作逐层搜索的迭代方法，k- 项集用于探索（k+1）- 项集。首先，找出频繁 1- 项集的集合。该集合记作L1。L1 用于找频繁2- 项集的集合 L2，而L2 用于找L3，如此下去，直到不能找到 k- 项集。每找一个 Lk 需要一次数据库扫描。为提高频繁项集逐层产生的效率，一种称作Apriori 性质用于压缩搜索空间。其约束条件：一是频繁项集的所有非空子集都必须也是频繁的，二是非频繁项集的所有父集都是非频繁的。
基本概念关联分析
关联分析是一种在大规模数据集中寻找相互关系的任务。 这些关系可以有两种形式:
频繁项集（frequent item sets）: 经常出现在一块的物品的集合。
关联规则（associational rules）: 暗示两种物品之间可能存在很强的关系。
相关术语
关联分析（关联规则学习): 下面是用一个 杂货店简单交易清单的例子来说明这两个概念，如下表所示:
交易号码 商品0 豆奶，莴苣
1 莴苣，尿布，葡萄酒，甜菜
2 豆奶，尿布，葡萄酒，橙汁
3 莴苣，豆奶，尿布，葡萄酒
4 莴苣，豆奶，尿布，橙汁
频繁项集: {葡萄酒, 尿布, 豆奶} 就是一个频繁项集的例子。
关联规则: 尿布 -> 葡萄酒 就是一个关联规则。这意味着如果顾客买了尿布，那么他很可能会买葡萄酒。
支持度: 数据集中包含该项集的记录所占的比例。例如上图中，{豆奶} 的支持度为 4/5。{豆奶, 尿布} 的支持度为 3/5。
可信度: 针对一条诸如 {尿布} -> {葡萄酒} 这样具体的关联规则来定义的。这条规则的 可信度 被定义为 支持度({尿布, 葡萄酒})/支持度({尿布})，支持度({尿布, 葡萄酒}) = 3/5，支持度({尿布}) = 4/5，所以 {尿布} -> {葡萄酒} 的可信度 = 3/5 / 4/5 = 3/4 = 0.75。
支持度 和 可信度 是用来量化 关联分析 是否成功的一个方法。 假设想找到支持度大于 0.8 的所有项集，应该如何去做呢？ 一个办法是生成一个物品所有可能组合的清单，然后对每一种组合统计它出现的频繁程度，但是当物品成千上万时，上述做法就非常非常慢了。 我们需要详细分析下这种情况并讨论下 Apriori 原理，该原理会减少关联规则学习时所需的计算量。
k项集
如果事件A中包含k个元素，那么称这个事件A为k项集，并且事件A满足最小支持度阈值的事件称为频繁k项集。
由频繁项集产生强关联规则
K维数据项集LK是频繁项集的必要条件是它所有K-1维子项集也为频繁项集，记为LK-1
如果K维数据项集LK的任意一个K-1维子集Lk-1，不是频繁项集，则K维数据项集LK本身也不是最大数据项集。
Lk是K维频繁项集，如果所有K-1维频繁项集合Lk-1中包含LK的K-1维子项集的个数小于K，则Lk不可能是K维最大频繁数据项集。
同时满足最小支持度阀值和最小置信度阀值的规则称为强规则。
算法原理 Apriori 思想算法思想