数据挖掘十大经典算法(4)：Apriori算法

本文所采用图片均来自清华大学计算机系王建勇老师的课程《数据挖掘：原理与算法》

http://dbgroup.cs.tsinghua.edu.cn/wangjy/DM/DataMining.html

(Agrawal & Srikant, VLDB'94)

Apriori算法的基本过程是：扫描一遍数据库，得到一阶频繁项；用一阶频繁项构造二阶候选项；扫描数据库对二阶候选项进行计数，删除其中的非频繁项，得到二阶频繁项；然后构造三阶候选项，以此类推，直到无法构造更高阶的候选项，或到达频繁项集的最大长度限制。Apriori算法的示意流程如下图所示：

如何从k阶的频繁项集生成k+1阶候选项集：自连接+裁剪（若k+1阶候选项的k阶子集中至少有一个不存在于k阶频繁项集中，则裁剪——Apriori裁剪规则，又称向下闭合特性）。

如何扫描数据库对候选项集进行计数：利用数据结构哈希树提高效率。

PS：哈希树简介（以三阶候选项集哈希树为例）

哈希函数：根据键值找到存储地址的函数

哈希树的构造：当一个节点存放的候选项集超过3时，将其裂解为3个子节点，包含的候选项集按照哈希函数进行分配，哈希函数的键值为候选项集的第i个项值，i为被裂解节点在哈希树中的层数（根节点层数为1）。

哈希树的遍历：若当前节点的上层节点的哈希函数针对的键值是transcation的第i个项值，则对transaction的第i个项后的每个项通过哈希函数递归地执行这个搜索过程。

遍历至数据库中的某一个transaction时，进行一次哈希树遍历即可完成该transaction的计数。
哈希树的原理如下图所示：

Apriori算法的缺点：需要多次扫描数据库；生成大量备选项集；计数工作量太大。

Apriori算法的改进

1. 减少扫描数据库次数

- 基于分割数据库的算法(Savasere,et al. VLDB'95)

- 动态生成候选项集的算法(Brin, et al. SIGMOD'97)

2. 减少候选项集

在Apriori裁剪规则基础上引进哈希表裁剪规则，使候选项集的裁剪量增多-DHP算法(Park, et al.SIGMOD'95)

Apriori算法Python2实现

参考：http://pythoner.net/code/33/