首页 > 代码库 > Apriori算法
Apriori算法
Apriori算法是一种最有影响的挖掘 0-1 布尔关联规则频繁项集的算法。这种算法利用了频繁项集性质的先验知识（因此叫做priori）。Apriori使用了自底向上的实现方式（如果集合 I 不是频繁项集，那么包含 I 的更大的集合也不可能是频繁项集），k – 1 项集用于探索 k 项集。首先，找出频繁 1 项集的集合( L 1 )， L 1 用于找频繁 2 项集的集合 L 2 ，而 L 2 用于找 L 3 ，如此下去，直到不能找到满足条件的频繁 k 项集。搜索每个 L k 需要一次全表数据库扫描。
我们假设一个很小的交易库：{1,2,3,4}, {1,2}, {2,3,4}, {2,3}, {1,2,4}, {3,4}, {2,4}
首先我们先要计算发生频数（或者叫做support）
| item | support |
|---|---|
| {1} | 3 |
| {2} | 6 |
| {3} | 4 |
| {4} | 5 |
1项集的最低频数是3，我们姑且认为他们都是频繁的。因此我们找到1项集所有可能组合的pairs：
| item | support |
|---|---|
| {1,2} | 3 |
| {1,3} | 1 |
| {1,4} | 2 |
| {2,3} | 3 |
| {2,4} | 4 |
| {3,4} | 3 |
在这里，{1,3}, {1,4} 不满足support大于3的设定（一般support是3/(3 + 6 + 4 + 5)），因此还剩下的频繁项集是：
| item | support |
|---|---|
| {1,2} | 3 |
| {2,3} | 3 |
| {2,4} | 4 |
| {3,4} | 3 |
也就是说，包含{1,3}, {1,4}的项集也不可能是频繁的，这两条规则被prune掉了；只有{2,3,4} 是可能频繁的，但它的频数只有2，也不满足support条件，因此迭代停止。
但我们可以想象，这种算法虽然比遍历的方法要好很多，但其空间复杂度还是非常高的，尤其是 L 1 比较大时， L 2 的数量会暴增。而且每次Apriori都要全表扫描数据库，开销也非常大。
即便如此 apriori 算法在很多场景下也足够用。在R语言中使用 arules 包来实现此算法（封装的是C实现，只要装载的 sparse matrix 可以载入内存，support 设置合理，速度非常快）。
Apriori算法