定义：

Apriori 是一种用于频繁项集挖掘和关联规则学习交易数据库的算法。它通过识别数据库中的频繁个体项目，并将其扩展到更大和更大的项目集，只要这些项目集在数据库中出现得足够多。由Apriori确定的频繁项目集可用于确定突出数据库中总体趋势的关联规则：这在诸如市场篮子分析等领域中有应用。*

减少候选项的数目

Apriori principle

如果一个项目集市频繁的，那么它的所有子项目集一定是频繁的。
Apriori原则由以下支持度关系维持：

- 一个项目集的支持度绝对不会超过它的子集的支持度
- 这被称为支持度的反单调性

Apriori 算法

方法：

1. 让k=1
2. 生成长度为1的项目集
3. 重复以下步骤知道没有新的频繁项目集产生
   
   • 从长度为k的项目集中生成长度为(k+1)的候选项目集
   • 剪去子集的长度为k的非频繁的候选项目集
   • 通过扫描数据库计算每一个候选项的支持度
   • 淘汰非频繁的候选项，剩下频繁的项目集

Apriori: A Candidate Generation & Test Approach

剪枝原则

如果任何一个项目集，它是非频繁的，那么他的超集就应该不能被生成/测试
(Agrawal & Srikant @VLDB’94, Mannila, et al. @ KDD’ 94)

方法

1. 初始，扫描数据库一次获得频繁的1-itemset(项目个数为1的项目集)
2. 从长度为k的频繁项目集中生成长度为(k+1)的候选项目集
3. 根据数据库测试候选项
4. 当没有频繁项目集或者候选项生成时终止

例子

对于C2——
1. 连接 C2=L1×L1={{A,B},{A,C},{A,E},{B,C},{B,E},{C,E}}
2. 剪枝 频繁项集的所有子集必须是频繁的。对候选项C2，我们可以删除其子集为非频繁的选项：
{A,B}的1项子集是{A}{B},它们都是频繁的；{A,C},{A,E},{B,C},{B,E},{C,E}的1项子集都是频繁的，因此都保留。
3. 剪枝后得到 {{A,B},{A,C},{A,E},{B,C},{B,E},{C,E}}

对于C3——
1. 连接：C3=L2×L2= {{A,C},{B,C},{B,E}{C,E}} {{A,C},{B,C},{B,E}{C,E}} = {{A,B,C},{A,C,E},{B,C,E}}
2. 使用Apriori性质剪枝：频繁项集的所有子集必须是频繁的，对候选项C3，我们可以删除其子集为非频繁的选项：
{A,B,C}的2项子集是{A,B},{A,C},{B,C}，其中{A,B}不是L2的元素，所以删除这个选项；
{A,C,E}的2项子集是{A,C},{A,E},{C,E}，其中{A,E} 不是L2的元素，所以删除这个选项；
{B,C,E}的2项子集是{B,C},{B,E},{C,E}，它的所有2－项子集都是L2的元素，因此保留这个选项。
3. 这样，剪枝后得到C3={{B,C,E}}

减少比较的次数

候选项计数

• 扫描存放事务的数据库，确定每一个候选项的支持度
• 为了减少比较次数，将候选项存储在哈西结构中hash structure。 将在哈希桶hash bucket中的候选项与事务进行匹配，而不是将每一个事务与每一个候选项匹配。

使用哈希树进行子集操作

生成哈希树Hash Tree

作用：哈希树可以生成一个事务的所有固定某个长度的子集。
目的：计算出各个候选项集的支持度

假设现在有长度为3的15个候选项
{1 4 5}, {1 2 4}, {4 5 7}, {1 2 5}, {4 5 8}, {1 5 9}, {1 3 6}, {2 3 4}, {5 6 7}, {3 4 5}, {3 5 6}, {3 5 7}, {6 8 9}, {3 6 7}, {3 6 8}
现需要：
- 哈希函数
- 最大叶子尺寸：存储在叶子节点的最大项目集数量（如果候选项目集的数量超过了最大叶子尺寸，则拆分这个节点）

子集操作

给定一个事务，那么它可能的尺寸为3的子集有哪些？

使用哈希树对事务进行遍历，进而对每一个事务进行其子集操作能够找出所有固定长度的项目集

比较哈希树结点中的k-项集与每一个事务t中的k-项集，如果有相同的就增加该k-项集的支持度计算。

根据事务{1,2,3,5,6}找到的长度为3的符合要求的项目集有{1,2,5},{4,5,8},{1,5,9},{1,3,6},{2,3,4},{5,6,7},{3,5,6},{3,5,7},{6,8,9},且他们的支持度均需加上1。

影响复杂度的因素

1. 最小值支持度的选择
   
   • 降低最小值尺度会导致更多的频繁项目集
   • 这可能会增加候选项的数目以及频繁项目集的最大长度
2. 数据集的维度(项目的个数)
   
   • 需要更多的空间去存储每个项目的支持数
   • 如果频繁项目的个数增加，计算量和I/0代价也将增加
3. 数据库的大小
   
   • 由于Apriori会多次运行，算法的运行时间可能随着事务数量的增加而增加
4. 平均事务宽度
   
   • 事务宽度会随着数据集的厚度增加而增加
   • 这可能会增加频繁项目集的最大长度，以及哈希树的遍历(事务中子集的个数会随着事务的宽度增加而增加)

频繁项集的压缩compact表示

一些项目集是冗余的，因为它们具有与其超集相同的支持度

频繁项目集的数量=

需要压缩表示

最大频繁项目集

定义：如果一个项目集的直接超集都是不频繁的，则该项目集是最大频繁项目集

封闭项目集

定义：如果一个项目集的直接超集与该项目集的支持度不相同，则该项目集是封闭项目集

最大频繁vs封闭项目集

最大频繁项目集和封闭项目集的关系

Apriori的缺点

1. 处理大量的候选集耗时(在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素)
2. 反复扫描数据库并检查候选模式很乏味(每次计算项集的支持度时，都对数据库D中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求更好性能的算法。)

改进Apriori算法

方法1：基于hash表的项集计数
将每个项集通过相应的hash函数映射到hash表中的不同的桶中，这样可以通过将桶中的项集技术跟最小支持计数相比较先淘汰一部分项集。
方法2：事务压缩（压缩进一步迭代的事务数）
不包含任何k-项集的事务不可能包含任何(k+1)-项集，这种事务在下一步的计算中可以加上标记或删除
方法3：划分
挖掘频繁项集只需要两次数据扫描
D中的任何频繁项集必须作为局部频繁项集至少出现在一个部分中。
第一次扫描：将数据划分为多个部分并找到局部频繁项集
第二次扫描：评估每个候选项集的实际支持度，以确定全局频繁项集。
方法4：选样（在给定数据的一个子集挖掘）
基本思想：选择原始数据的一个样本，在这个样本上用Apriori算法挖掘频繁模式
通过牺牲精确度来减少算法开销，为了提高效率，样本大小应该以可以放在内存中为宜，可以适当降低最小支持度来减少遗漏的频繁模式
可以通过一次全局扫描来验证从样本中发现的模式
可以通过第二此全局扫描来找到遗漏的模式
方法5：动态项集计数
在扫描的不同点添加候选项集，这样，如果一个候选项集已经满足最少支持度，则在可以直接将它添加到频繁项集，而不必在这次扫描的以后对比中继续计算。

参考资料：
数据挖掘十大算法–Apriori算法
博客的内容都是老师上课课件的反馈，我之后还会参考其他资料对该方法进行更为清晰的总结