# FP-growth

FP-growth 的主要目的是破解 candidate generation 所引起的 bottleneck

所以 FP-growth 將不會用到任何 candidate generation

並且在 main memory 實作，進而減少對 database 的 scans

FP-growth 主要的概念是 divide-and-conquer

並且利用了 suffix tree 的概念

## Suffix Tree

### Keyword Trees

* 將 keywords 儲存在 rooted labeled tree
* 每個從 root 到 leaf 的 path 都會對應一個 keyword

![](/files/-Lq9iPvf9wDRt2ImYjBX)

* 利用 "threading" 技巧 traverse 文章找出 keywords
* 每當我們 reach 到 leaf node 時代表找到 keyword

### Suffix Tree

* 運用 keyword tree 的概念
* 利用 text 的 suffixes 來建立一種 trie data structure
* Suffix tree 的 leaves 會是每個 suffix 在文章的 start position

![](/files/-Lq9iPvklMQjmRA2yZjl)

* Suffix tree 可以掌握所有 text 的 suffixes
* 並且在 $$O(\text{length})$$ 的時間就可以建好 tree
* 例如底下是一個將基因序列 index 成 suffix tree 的例子

![](/files/-Lq9iPvmJ4TmVeBfAMYb)

## FP-Growth Algorithm

1. Construct FP-Tree (Frequent pattern tree)
2. FP-Growth (Frequent pattern growth)
   1. 根據不同 frequent item 將 FP-tree 分裂成 Conditional FP-Tree
   2. 針對每一個 conditional FP-Tree 進行 mining

### FP-Trees Construction

1. 一樣先 scan 所有 1-itemset 的 support ，但要 sort 成 descending order
   * Descend 可以改變 transaction 結構，幫助我們用更少 nodes 來建樹

![](/files/-Lq9iPvo4DgMVPA3ldUu)

![](/files/-Lq9iPvqvHraKYrhgmv3)

1. 將 ordered 的 itemset 建立成 FP-tree，建立方法如下
   * 從第一筆開始建樹
   * 一樣的 character 就 + 1
   * 不一樣的 character 就建立分支

![](/files/-Lq9iPvsATCMkgzd-l8h)

1. 最後將 tree 中相同 character 從 header table 串連起來

![](/files/-Lq9iPvusUWqBBNx5bEJ)

### FP-Growth

接續上面產生的 FP-Tree

![](/files/-Lq9iPvwjDA_hGPlxBBf)

1. 先從每一個 1-item 來建立 **Conditional Pattern Base** (由下往上)
   * p 可以從 fcam (2次) 接過來
   * p 也可從 cb (1次) 接過來
2. 接著從 conditional pattern base 建立出 **Conditional FP-Tree**
   * 找出在 conditional pattern base 有相同 prefix 的 items
   * 並且可以符合 minsup
   * 例如 p 的 fcam 跟 cb 代表 $$c \rightarrow p$$ 共有出現 3 次
3. 最後我們將 conditional FP-Tree 找到的 items 各自拆開與原本的 item 結合
   * 例如 $$c \implies (c \rightarrow p)$$

{% hint style="info" %}
[Here is a complete FP-Growth Example](https://drive.google.com/file/d/18XxvzPmSFWpnDQ-Mfd_ekEsw64fUTJ5z/view)
{% endhint %}

### FP-Growth Adventages

* Divide-and-Conquer
  * Decompose mining and DB
* No candidate required
* Compressed DB (FP-Tree)
* No repeated scan of DB
* No pattern searching and matching


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://sejkai.gitbook.io/academic/ncku-data-mining/fp_growth.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.