数据挖掘Efficient Pattern Mining Methods

本文要介绍一些高效的数据挖掘方法：

  • The Downward Closure Property of Frequent Patterns
  • The Apriori Algorithm
  • Extensions or Improvements of Apriori
  • Mining Frequent Patterns by Exploring Vertical Data Format
  • FPGrowth: A Frequent Pattern-Growth Approach
  • Mining Closed Patterns

The Downward Closure Property of Frequent Patterns : Aprior

1
首先先介绍一个概念：Frequent Pattern 的Downward Closure 性质 （这个性质应该叫做向下封闭性质吗？what ever..who cares）

狄仁杰大人说：我们先观察，从上一节里面的例子中我们可以观察到 频繁集: {$a1,…,a{50}$} 有很多 子集 ，所有的这些子集也是Frequent的！（元芳!What’s your opinion ?　大人！这背后必有一个惊天的大秘密！！！我们可以一起搞个大新闻！Excited!）

元芳和大人通过观察发现：
如果 {beer,diaper,nuts} 是频繁的，那么 它的子集{beer,diaper}也是频繁的
因为每当出现 {beer,diaper,nuts}的时候，{beer,diaper}也都出现了！（这么奇妙，你每次吃了一碗米饭的时候，你都吃过了一粒米）

The Apriori Algorithm

2
于是敌人节大人和元芳就穿越到1994年，化身为Rakesh Agrawal 和 Srikant,在VLDB发表了论文说：

  • Aprior: Any subset of a frequent itemset must be frequent

这个定理怎么用呢？元芳你怎么看？大人！反着看！这是一把剪枝的好剪刀！，如果任何一个 Itemset S的子集不是频繁的，那么S也不可能频繁，我们就不需要再去挖掘S了，多么痛的领悟！

后来人们基于这个想法，又探索出了2个主要的方法：

  • Aprior
  • Eclat
  • FPgrowth

Apriori wiki 页面

4

Aprior算法可以用伪代码表示如下：

5

Wiki上这么说的：

  • a transaction database $T$
  • a support threshold of $\epsilon$
  • $C_k$ is the candidate set for level $k$
  • $count[c]$ accesses a field of the data structure that represents candidate set $c$存着support

3
下面就上面这个伪代码进行解读：

  • $L_1$$\leftarrow$ $\lbrace large 1-itemsets \rbrace$

    • 这行是初始化让第一层的frequent set是 1-itemsets

  • while $L_{k-1}$ $\neq$ $\emptyset$

    • 这行是说当上一层的frequent sets是空的时候就结束搜索

  • $Ck \leftarrow \lbrace a\cup\lbrace b\rbrace \mid a \in L{k-1} \land b \in \bigcup{L_{k-1} \land b \notin a} \rbrace $

    • 这行是用来生成侯选集的
    • 侯选集是从上一层的频繁集$L{k-1}$中选一个子集 $a \in L{k-1}$，然后再从上一层的频繁集$\bigcup L_{k-1}$中选出一个不在a中($ b \notin a$)的元素 $ b $,然后生成一个itemset : $a \cup \lbrace b \rbrace$ 作为新的侯选集中的一个元素。

  • for transactions t $ \in T $ 对每一条 transaction

    • $C_t \leftarrow \lbrace c \mid c \in C_k \land c \subseteq t \rbrace$ 选出这条transaction 中属于侯选集 $C_k$ 的 每个item
    • count[c] $\leftarrow $ count[c] + 1 把每个item的 support count 加 1

  • $L_k \leftarrow \lbrace c \mid c \in C_k \land count[c] \ge \epsilon \rbrace $ 把侯选集中的support大于阈值minsup的选itemset选出来，作为下一层的 frequent itemset

  • return $ \bigcup_k L_k $ 返回所有的 频繁集

下面这是一个直观的例子

6

实现的技巧

7

  • 如何生成侯选集呢？
    • 首先，$F_k$和自己求并集
    • 然后，剪枝，如何剪枝，如果并集有一个子集不在$F_k$中，就剪枝，例如图中acde的子集cde不在 $F_3$中，所以被剪掉了

7
WIKI 上是这么说的:

Apriori uses a “bottom up” approach, where frequent subsets are extended one item at a time (a step known as candidate generation), and groups of candidates are tested against the data. The algorithm terminates when no further successful extensions are found.

就是说，Aprior算法用了一种自底向上的方法，从上一层的frequent itemsets中（初始化为frequent-1 itemset set）扩展一个item，生成本层的候选集,然后在数据库中测试生成的候选集中的每个itemset是不是frequent的，把本层的候选集中是frequent的那些选为本层的frequent itemset，直到上一层没有frequent itemset为止，然后就返回所有层的 frequent itemsets；

Extensions or Improvements of Apriori

10

  • 由于database存在磁盘上，所以磁盘访问开销很大，所以要减少数据库访问的次数

    • partioning 方法，这是我们接下来要讲的
    • Dynamic itemset counting(Brin 这个作者吊炸天了！他就是谷歌的创始人之一！发表这个论文的第二年98年他就创办了谷歌)

  • 另一种思路是 减少候选集的数量

  • 第3种方法是 使用一些特殊的数据结构
    • 我们要用的是一个 FP tree

下面我们就简要看一下第一种方法 Partioning method:
11

这个方法的发明者观察到了一个非常有趣的现象：TDB中任何一个潜在的频繁集至少在该transaction database 的一个partition里是frequent的；

证明过程是这样的：

  1. 首先如果一个itemset X在图中六个partition里面的任何一个里不是frequent的
  2. 那么就有 $sup_i$(X) $\lt$ $\sigma$|$TDB_i$| (这是说X的support 小于 sigma 乘以 size($TDB_i$))
    • 这个乘积其实就是阈值 minsup，为什么呢，因为$\sigma$是一个比率，它用来表示在一个itemsets里面满足support大于多少就算是 frequent pattern
  3. 最后把每个partition里的support(X)加起来还是小于总共的TDB里的阈值 $\sum_{i=1}^6 SUP_i(X) \lt \sigma |TDB| $
  4. 也就是说，它在每一个分区里面都不频繁，那么它在整体里面也不可能频繁，所以，只有在至少一个TDB里面 itemset 是frequent的，它才可能在全集里面frequent；

那么具体怎么实现呢呢？需要两次扫描：

  • 第一次： 切分database,怎么切分呢？ Each partition you want them to fit into the main memory.

    • 为什么呢？因为无论你怎么扫描，你不需要进行任何的数据库I/O操作
    • 这样就能生成所有的 local frequent patterns 局部频繁集

  • 第二次： 选出全局的global patterns,怎么选呢？

    • 由于每一个分区里面的frequent pattern 很有称为全局frequent pattern的潜在可能
    • 所以第二遍扫描就count each database combos counts of the global candidate set(把每个分区里面的频繁集count求和）有点类似map-reduce的意思；

这样就保证了这种方法只扫描两次数据库；

##直接散列再剪枝法
12

在生成frequent 1-itemset 的时候，我们可以先为每个transaction 生成所有的frequent 2-itemset ， 把它们都hash到hash表中，并且统计每个bucket 的数量，如果这个数量低于频繁集的阈值，那么这个集合的子集都可以剪枝了。

##Exploring Vertical Data Format
13
这个和搜索引擎的倒排索引是一个道理！
把数据库中的每一个item想象成切分好的词，然后给这个数据表建立倒排索引，就是图中说的把 horizontal Data format 转换成了 vertical Data format;
用这个 tid-list : 可以方便的生成候选集 ；
比如， t(e) = { $T_10,T_20,T_30$ }; t(a) = { $T_10,T_20$ } ; t(ae) = { $T_10,T_20$ },生成 t(ae)的时候就是用 t(e)和t(a)求交集。对于t(ae)如果其中的任何一个item不是frequent那么t(ae)就不是frequent,t(ae)就可以忽略不计了; 如果t(ae)的两个成员都是frequent,那么判断t(ae)也很简单，就看它的size是多大；

FPGrowth: A Pattern Growth Approach

fp1
正如我们看到的，虽然很多时候Aprior生成与测试方法显著地减少了侯选集的大小，使性能得到了很大的提高。但是，这种方法有两种缺点：

  • 它仍然需要生成一个海量的侯选集。例如，如果有$10^4$个frequent 1-itemsets ,Aprior算法需要生成至少$10^7$个 candidate 2-itemsets;
  • 它需要重复扫描扫描全部数据库，并且要检索巨大的侯选集来进行模式匹配。而且每次需要遍历所有数据项才能确定候选pattern的support count，这样耗费太大了;

所以就有人提出，能不能不生成侯选集就挖掘出频繁集呢？于是，Frequent Pattern growth 算法就应运而生了。
FP-growth算法主要使用了分治法。首先，它吧数据库里的频繁集信息用一种压缩的方式表示，这种数据结构叫做FP-tree（类似字典树）。这棵树保存着itemset的关联信息。然后，它把这个压缩后的数据库分成一组conditional
databases（就是一种特殊的投影数据库）,每个conditional database一个frequent item(或者称之为模式片段）,然后分别挖掘这些conditional databases。对每个模式片段来说，只有和他相关的数据集才需要被检测。因此，这个方法用“让被检测模式growth的方式”切实的减少了需要检索的数据集的数量

fp2

FP-growth算法的第一步是：检索数据库一次，生成1-itemset 频繁集，以及统计每个frequent item的support count。然后把频繁集按照support count 从高到低排序；

第二步是生成FP—Tree：先构造一个空的树根root,对每个数据项做下面的操作：
先把每个数据项中的item按照上面的顺序排序，然后选择每一个item，将这个item插入到FP-tree里去 （insert_tree([p|P],T) p是第一个item,P是剩下的item），插入的方法如下：
如果如果这个item跟树中的某个item N 相同，那么就把树中该节点的count+1,否则就生成一个新节点N，并且初始化它的count为1，把它的父节点指针指向T.如果剩下的item不为空的话，就递归的调用insert_tree(P,N);

fp3
为了方便树的遍历，还要构建一个item header table，让table中每一个item，指向它在树中出现的每个节点，用链表连起来。
有了这两个数据结构，我们就把挖掘数据库的任务转化成了挖掘FP-tree的任务。

fp4

FP-tree是这样挖掘的：

  1. 从每一个frequent length 1-pattern （当做一个起始后缀） 开始，把它在树中的所有前缀路径找出来，作为它的conditional pattern base
  2. 然后针对每个conditional pattern base 构建相应的conditional FP-tree
    其实conditional这个词在这里我们可以理解成向贝叶斯公式里面的意义，为什么把前缀叫conditional呢，因为当这个后缀发生的时候，它的前缀已经出现了
  3. 然后递归的挖掘每个conditional FP-tree。
    fp5
    fp6

Comments

⬆︎TOP