fpgrowth算法案例

FP-growth算法是一种用于频繁项集挖掘的算法。它通过构建一棵FP树来实现这一目标，从而避免了频繁项集挖掘中的多次扫描事务数据库的问题，因此具有较高的效率。

下面以一个购物篮分析的例子来介绍FP-growth算法的应用。

假设我们有以下的购物篮数据：

| 购物篮 | 商品 |
| ------ | ------ |
| 1 | A, B, C, D |
| 2 | A, C, D, E |
| 3 | A, C, E |
| 4 | B, E |

我们要找出其中的频繁项集，即在多个购物篮中经常出现的商品组合。

首先，我们需要构建FP树。对于每个购物篮，我们将其中的商品按照频率排序后插入FP树中。例如，对于第一篮购物，我们依次插入A、B、C、D：

  null
   |
   A
 / | \
B  C  D

对于第二篮购物，我们依次插入A、C、D、E，我们先找到A的位置，然后从A开始插入C、D、E：

  null
   |
   A
 / | \
B  C  D
   |
   E

对于第三篮购物，我们依次插入A、C、E，与第二篮购物类似，从A开始插入C、E：

  null
   |
   A
 / | \
B  C  D
   | \
   E  E

最后，对于第四篮购物，我们依次插入B、E，从B开始插入E：

  null
   |
   A
 / | \
B  C  D
   | \
   E  E
     |
     B

这样，我们就构建了一棵FP树。接下来，我们从FP树中挖掘频繁项集。

首先，我们从最小的频繁项集开始，即单个商品。从FP树的叶子节点开始，向上遍历FP树，记录每个商品在FP树中的出现次数。例如，B在FP树中出现了2次，E在FP树中出现了3次，C和D各出现了2次，A出现了3次。这样，我们就得到了每个商品的支持度。

接下来，我们构建条件模式基。对于每个频繁项，我们找到其在FP树中的所有路径，去掉其中的频繁项后，得到的剩余路径就是条件模式基。例如，对于频繁项B，我们找到其在FP树中的所有路径：B->E->A、B->E，去掉其中的B，得到的剩余路径就是E->A和E。这样，我们就得到了所有频繁项的条件模式基。

最后，我们用条件模式基继续构建FP树，重复上述过程，直到不能再构建出新的频繁项为止。最终，我们就得到了所有的频繁项集。例如，在本例中，我们得到的频繁项集包括：{A}、{B}、{C}、{D}、{E}、{A, C}、{A, E}、{C, E}和{A, C, E}。