这篇博文主要总结数据挖掘 find frequent item set 的 两个个有趣的算法: Apriori,FP-Growth Tree

introduction

关联规则，简单的说就是在一个数据集中，通常我们如果看见 A，同时也会看见 B。就称他们是关联的，用一个经典例子解释就是:

market-basket,你在超市买东西，通常买面包，同时也会买牛奶。关联规则就是要在一堆数据中找’这种’东西

当然一切问题只有当他有数学描述的时候才好定量衡量，下面就是几个关于关联规则的衡量方法

假设数据是 horizontal 的。

即

TID Items
id1 i1,i2

Support : 集合 $A$ 的支撑，$sp(A):= \# A$

Confidence: $conf(A\rightarrow B) = \Pr(B|A)=\frac{sp(A\cup B)}{sp(A)}$，注意 conf 衡量并不对称

lift: $lift(A\rightarrow B)=\frac{\Pr(A\cup B)}{\Pr(A)\Pr(B)}$

interest: $intere(A\rightarrow B) = |conf(A\rightarrow B) - \Pr(B)|$

可以看到要计算这些东西最核心的问题就是就算suport，也就是考虑集合的计数问题

通常我们需要挖掘的是那些 $sp(S) \ge TH$ 其中 $TH$ 是个常数最小支撑界限

接下来总结两个算法 Apriori 和 FP-Growth

Apriori

这个算法挺简单的，就一个核心思想:

集合偏序的单调性

即如果 $A\subseteq B$, 则 $sp(A)\ge sp(B)$, 换句话说，如果 $A$ 不满足支撑条件，那么 $B$ 也不可能满足从而筛选掉一部分

Apriori 算法描述

  1. 生成 1-frequent item set $L_1={S|sp(S)\ge TH \And |S|=1}$,(需要扫描数据一遍)
  2. 生成候选集合 $C_k={S|S\in L_{k-1}\Join L_{k-1}, |S|=k,\forall s \subseteq S,|s|=k-1,s\in L_{k-1}}$ (这一项用到了单调性的先验知识)
  3. 扫描数据，通过 $C_k$筛选 $L_k$,这里有两种方法，都非常暴力
    1. 对数据集合中的每一项 $t$ ，生成 $k$ 子集，检测是否在 $C_k$ 中 $O(n^k),n=|t|$
    2. 对$C_k$ 中的每一项,检测是否在 $t$ 中(membership test) $O(|C_k|k)$

详细算法描述，可见[2]

同时这里有我的一个简单实现 code

可以看见这个算法非常暴力，通常从 1-> 2 会生成非常多的无用集合,因此相应的优化策略也被提出来了

improve

  1. 对与 3.1 先对$C_k$ 中的每个元素 hash，维护一个hash表，然后仅对每条记录$t$ 在$C_k$ 中的元素生成子集，(我自己的代码中测试的时候这个方法很管用)
  2. hash，每次生成 $L_k$ 的时候，每条记录同时生成 $k+1$ 的子集，hash记录 hash(s) : 的个数，生成 $k+1$ 候选集的时候，去掉 $hash(C_{k+1})\le TH$ 的候选集，这个方法在 1->2 的时候挺管用，不过也挺麻烦(对于spark操作来说)
  3. transaction 减少，如果一条记录在 $k$ 时不没有生成候选集，那么他在k+1时也不可能生成
  4. partition， 就是将数据划分成几个小块，对每一块求frequent itemset($TH'=TH*\frac{N_i}{N}$)这个方法能降低读取数据的次数，在大数据的时候主要开销在 $IO$ 因此这个方法可行

FP-Growth

这个方法挺占用内存的。它的思想挺高明，建造一颗前缀树(trie)

  1. 先找到 $L_1$, 按照 Support 排序
  2. 对于每条记录按照筛选出在 $L_1$ 中的节点，然后在按照suport 排序，够着如图所示的前缀树
  3. 从 $L_1$ 中support 最小的节点开始，找到包含它的合法的子集，具体来说
    1. 找到树根到 $i$ 的所有路径，比如上图中的 I5, 我们能够知道，{I2,I1,I5:1},{I2,I1,I3,I5:1},就能够得到 {I2,I1,I5:2},{I2,I5:2},{I1,I5:2} 几个集合了

这个算法应该还有很多优化的空间，比如最近公共祖先优化。

[code] 待写

reference

  1. Anand Rajaraman, Jure Leskovec, and Jeffrey D. Ullman.Mining of Massive Datasets. ch6.
  2. Data mining : concepts and techniques. ch6. Jiawei Han, Micheline Kamber, Jian Pei.–3rd ed.

版权声明

本作品为作者原创文章，采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

作者: taotao

仅允许非商业转载，转载请保留此版权声明，并注明出处