Apriori算法研究
Apriori算法是一个挖掘关联规则的算法，是Agrawal等设计的一个基本算法。它采用两阶段挖掘的思想，并且基于多次扫描事务数据库来执行。
1.关联规则
1.1.基本概念
关联规则是形如X →Y 的蕴涵式，表示通过X 可以推导“得到”Y ，其中X 和Y 分别称为关联规则的先导(antecedent 或left-hand-side, LHS) 和后继(consequent 或right-hand-side, RHS)。
关联规则A->B 的支持度support=P(AB) ，指的是事件 A 和事件B 同时发生的概率。
置信度confidence=P(B|A)=P(AB)/P(A), 指的是发生事件 A 的基础上发生事件 B 的概率。
同时满足最小支持度阈值和最小置信度阈值的规则称为强规则。
如果事件 A 中包含k 个元素，那么称这个事件 A 为k 项集，并且事件 A 满足最小支持度阈值的事件称为频繁k 项集。
1.2.挖掘过程
第一，找出所有的频繁项集；其目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集。
第二，由频繁项集产生强规则。其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称为强规则。
通常，频繁项集产生的计算开销远大于产生规则所需的计算开销。
2.Apriori算法思想
Apriori 算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法，k 项集用于探索(k+1) 项集。首先，通过扫描事务（交易）记录，找出所有的频繁1 项集，该集合记做L1 ，然后利用L1 找频繁 2 项集的集合L2 ，L2 找L3 ，如此下去，直到不能再找到任何频繁k 项集。最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。
其中，Apriori 算法具有这样一条性质：任一频繁项集的所有非空子集也必须是频繁的。因为假如P(I)< 最小支持度阈值，当有元素 A 添加到I 中时，结果项集（ A ∩I ）不可能比I 出现次数更多。因此A ∩I 也不是频繁的。
该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最
小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递归的方法。
3.Apriori算法步骤
Apriori算法的设计可以分解为两步骤来执行挖掘：
3.1.挖掘所有频繁项集
从事务数据库（D）中挖掘出所有频繁项集。
支持度大于最小支持度minSup的项集（Itemset）称为频集（Frequent Itemset)。
首先需要挖掘出频繁1-项集；然后，继续采用递推的方式来挖掘频繁k-项集（k>1），具体做法是：在挖掘出候选频繁k-项集（Ck）之后，根据最小置信度minSup来筛选，得到频繁k-项集。最后合并全部的频繁k-项集（k>0）。
挖掘频繁项集的算法描述如下：
1:L1 = find_frequent_1-itemsets(D); // 挖掘频繁1-项集，比较容易
2:for (k=2;Lk-1 ≠Φ;k++) {
3:Ck = apriori_gen(Lk-1 ,min_sup); // 调用apriori_gen方法生成候选频繁k-项集
4:for each transaction t ∈D { // 扫描事务数据库D
5:Ct = subset(Ck,t);
6:for each candidate c ∈Ct
7:++; // 统计候选频繁k-项集的计数
8:}
9:Lk ={c ∈Ck|≥min_sup} // 满足最小支持度的k-项集即为频繁k-项集
10:}
11:return L= ∪k Lk; // 合并频繁k-项集（k>0）
Apriori算法的频繁项集产生的部分有两个重要的特点：第一，它是一个逐层算法，即从频繁1-项集到最长的频繁项集，它每次遍历项集格中的一层；第二，它使用产生-测试策略来发现频繁项集。在每次迭代之后，新的候选项集都由前一次迭代发现的频繁项集产生，然后对每个候选的支持度进行计数，并与最小支持度阈值进行比较。该算法需要的总迭代次数是k max+1，其中k max是频繁项集的最大长度。
3.2.挖掘频繁关联规则
基于第1步挖掘到的频繁项集，继续挖掘出全部的频繁关联规则。
置信度大于给定最小置信度minConf的关联规则称为频繁关联规则（Frequent Association Rule）。在这一步，首先需要从频繁项集入手，首先挖掘出全部的关联规则（或者称候选关联规则），然后根据minConf来得到频繁关联规则。
挖掘频繁关联规则的算法描述如下：
算法挖掘频繁关联规则
1:初始状态：L = ∪k Lk; AR = Φ; // L是频繁项集集合，AR是频繁关联规则集合2:for all λk （λk是L的元素，是一个k-频繁项集，大小为n）{
1.for all αk （αk是λk 的非空真子集）{
i.if(αk →βm的置信度>= minConf) { // 这里，m + k = n，其中α
k →βm是一个关联规则
a)AR = AR ∪(αk →βm);
ii.}
2.}
3:}
4:return AR;
4.Apriori算法计算复杂度
4.1.影响因素
Apriori算法计算复杂度受如下因素影响。
支持度阈值降低支持度阈值通常将导致更多的频繁项集。这给算法的计算复杂度带来不利影响，因为必须产生更多候选集并对其计数。随着支持度阈值的降低，频繁项集的最大长度将增加。而随着频繁项集最大长度的增加，算法需要扫描数据集的次数也将增多。
项数（维度）随着项数的增加，需要更多的空间来存储的支持度计数。如果频繁项集的数目也随着数据维度增加而增长，则由于算法产生的候选项集更多，计算量和I/O开销将增加。
事务数由于Apriori算法反复扫描数据集，因此它的运行时间随着事务数的增加而增加。
事务的平均宽度对于密集数据集，事务的平均宽度可能很大，这将在两个方面影响Apriori算法的复杂度。首先，频繁项集的最大长度随事务平均宽度增加而增加，因而，在候选项产生和支持度计算时必须考察更多候选项集；其次，随着事务宽度的增加，事务中将包含更多的项集，这将增加支持度计数时Hash树的遍历次数。
4.2.时间复杂度
频繁1-项集的产生对于每个事务，需要更新事务中出现的每个项的支持度计数。假定w为事务的平均宽度，则该操作需要的时间为O(Nw)，其中N为事务的总数。
