能详细说下FP_Growth 算法吗,能有图更好
时间: 2024-05-15 10:19:40 浏览: 30
FP-Growth算法是一种频繁模式挖掘算法,用于发现数据集中的频繁项集。它通过构建一种称为FP树的数据结构,以有效地发现频繁项集。
下面是FP-Growth算法的流程:
1. 构建项头表:遍历数据集,统计每个项的出现频次,并按照频次从高到低排序。将每个项及其对应的频次存储在项头表中。
2. 构建FP树:遍历数据集,对于每个事务,根据项头表中的排序顺序,建立一条从根结点到叶子结点的路径。如果路径中存在相同的项,就沿着该路径向下扩展。如果路径中不存在相同的项,就在该路径上创建一个新的分支。
3. 从FP树中挖掘频繁项集:从项头表中选择一个频繁项,以该项作为末尾,向上遍历FP树,找到所有包含该项的路径。将这些路径上的所有项都合并起来,就得到了一个频繁项集。然后,将该频繁项集作为一个新的事务,重新构建一棵FP树,继续挖掘频繁项集,直到没有更多的频繁项集可以挖掘为止。
下面是一个简单的例子,说明如何使用FP-Growth算法挖掘频繁项集:
假设有以下数据集:
```
Itemset Count
{A, B, C} 3
{A, C, D} 2
{B, C, E} 1
{A, B, C, D} 1
{A, C, D, E} 1
```
首先,构建项头表,按照频次从高到低排序:
```
Item Count
A 4
C 4
B 2
D 2
E 2
```
然后,构建FP树:
![FP树](https://img-blog.csdn.net/20180430113108757)
最后,从FP树中挖掘频繁项集:
1. 挖掘以A为末尾的频繁项集:
![以A为末尾的频繁项集](https://img-blog.csdn.net/20180430113132705)
2. 挖掘以C为末尾的频繁项集:
![以C为末尾的频繁项集](https://img-blog.csdn.net/20180430113156883)
3. 挖掘以B为末尾的频繁项集:
![以B为末尾的频繁项集](https://img-blog.csdn.net/2018043011321523)
4. 挖掘以D为末尾的频繁项集:
![以D为末尾的频繁项集](https://img-blog.csdn.net/20180430113238869)
5. 挖掘以E为末尾的频繁项集:
![以E为末尾的频繁项集](https://img-blog.csdn.net/20180430113301103)
6. 挖掘以AC为末尾的频繁项集:
![以AC为末尾的频繁项集](https://img-blog.csdn.net/20180430113319407)
7. 挖掘以AB为末尾的频繁项集:
![以AB为末尾的频繁项集](https://img-blog.csdn.net/20180430113340659)
8. 挖掘以AD为末尾的频繁项集:
![以AD为末尾的频繁项集](https://img-blog.csdn.net/20180430113359533)
9. 挖掘以CD为末尾的频繁项集:
![以CD为末尾的频繁项集](https://img-blog.csdn.net/20180430113420965)
10. 挖掘以BC为末尾的频繁项集:
![以BC为末尾的频繁项集](https://img-blog.csdn.net/20180430113438453)
11. 挖掘以CE为末尾的频繁项集:
![以CE为末尾的频繁项集](https://img-blog.csdn.net/20180430113456377)
12. 挖掘以ACD为末尾的频繁项集:
![以ACD为末尾的频繁项集](https://img-blog.csdn.net/20180430113512970)
13. 挖掘以ACE为末尾的频繁项集:
![以ACE为末尾的频繁项集](https://img-blog.csdn.net/20180430113530145)
14. 挖掘以ABC为末尾的频繁项集:
![以ABC为末尾的频繁项集](https://img-blog.csdn.net/20180430113546329)
15. 挖掘以ABD为末尾的频繁项集:
![以ABD为末尾的频繁项集](https://img-blog.csdn.net/20180430113606369)
16. 挖掘以ACDE为末尾的频繁项集:
![以ACDE为末尾的频繁项集](https://img-blog.csdn.net/20180430113621549)
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)