数据挖掘Apriori算法简介
Apriori算法是一种用于关联规则挖掘（Association rule mining）的代表性算法，它同样位居十大数据挖掘算法之列。关联规则挖掘是数据挖掘中的一个非常重要的研究方向，也是一个由来已久的话题，它的主要任务就是设法发现事物之间的内在联系。
关联规则
在介绍Apriori算法之前，我们先分析一下关联规则。
关联规则即 X->Y 的蕴涵表达式。当 X 成立时，Y也会成立。而验证关联规则是否有效，或者成立的关键点在于支持度和置信度。
支持度，置信度概念：http://blog.****.net/xinan_zxy/article/details/78994611
支持度表示规则在给定数据集中的频繁程度，置信度表示在前提成立的情况下，规则成立的频繁程度。
因此，一般来说，对于大部分关联规则挖掘的算法，可分为两部分：
（1）频繁项集的产生：发现能够满足最小支持度阈值的所有项集，这些项集称作频繁项集；
（2）规则的产生：从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称作强规则。
对于频繁项集的产生所需的时间一般要高于规则的产生。
最直接，最简单的方法就是 暴力搜索。
- List all possible association rules（列出全部可能的规则）
- Compute the support and confidence for each rule（计算规则的支持度和置信度）
- Prune rules that fail the minsup and minconf thresholds（删去低于最小支持度阈值和最小置信度阈值的规则）
然而暴力搜索的计算代价非常大，所以在实际情况下，暴力搜索并不实际。
如下图所示为L={a,b,c,d,e}的项集格。一般来说，排除空集后，一个包含k个项的数据集可能产生2^k−1个频繁项集。由于在实际应用中k的值可能非常大，需要探查的项集可能是指数规模的。
而鉴于频繁项集的产生，就需要有一种行之有效的方法来处理，Apriori算法是目前来说比较有效的方法之一，亦是2006年12月召开的 IEEE 数据挖掘国际会议上指出的当时的十大机器学习算法之一。
Apriori算法
Apriori算法有定律：
1. 如果集合是频繁项集，则它的子集都是频繁项集；
2. 如果集合不是频繁项集，则它的超集都不是频繁项集；
即在L={a,b,c,d,e}的项集格中，当我们发现集合{A，B}不是频繁项集，这关于它的超集都不是频繁项集，则不需要再对其进行计算。
例子说明
下面，我们举一个例子来说明算法。
一个数据集 TDB 如图所示，我们设置最小支持度阈值 Sup = 2。接着从k项的集合，往k+1项集合拓展。
首先，我们从1项的集合开始，得到相关的集合支持度表C1，除去不符合{D}得到L1。接着根据L1中的两两项合成新的项，得到C2，除去不符合的{A，B}、{A，E}得到L2，以此类推，得到L3。
在我们判断一个k项集合（例如{A，B，C…..K}）是否为频繁项集时，为了节约计算，可以采用一下步骤：
- 根据Apriori定律2，判断k项集合的k个k-1项子集是否存在于L(k-1)中，例如判断C3中的{B，C，E}是否为频繁项集，可以判断3个2项子集（例如{B，C}、{B，E}、{C，E}）是否在L2中；
- 如果存在某个k-1项子集不存在L(k-1)中，则该项不是频繁项集，因为该k-1项子集不是频繁子集；
- 如果全部子集都存在于L(k-1)中，则需要遍历给出的数据集，确定支持度来判断该k项集合是否为频繁项集。
OK，That`s all. Thanks!