# FP-growth

**Repository Path**: mileschan/FP-growth

## Basic Information

- **Project Name**: FP-growth
- **Description**: 使用FP-growth算法来高效发现频繁项集
- **Primary Language**: Python
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 1
- **Created**: 2022-06-17
- **Last Updated**: 2022-06-17

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

#FP-growth
本章将介绍一个非常好的发现频繁项集的算法---FP-growth算法。该算法的速度比Apriori算法要快。它基于Apriori构建，但在完成任务时采用了不同的技术。FP-growth算法将数据集存储在一个特定的被称作“FP树”的结构中，从构建的FP树中挖掘频繁项集以及该频繁项集所对应的条件FP树。在发现频繁项集构建FP树时，FP-growth只需对数据集进行两次扫描，而Apriori算法为了判断给定模式是否频繁对于每个潜在的频繁项集都会扫描数据集，因此FP-growth算法的执行要快于Apriori，通常性能要好两个数量级以上。

FP-growth算法将数据存储在一中称为FP树的紧凑数据结构中。一颗FP树看上去与计算机科学中的其他树结构类似，但是它通过链接（link）来连接相似元素，被连起来的元素项可以被看成一个链表。
同搜索树不同的是，一个元素项可以再一颗FP树中出现多次。FP树会存储项集出现的频率，而每个项集会以路径的方式存储在树中。存在相似元素的集合会共享树的一部分。只有当集合之间完全不同时，树才会分叉。树节点上给出集合中的单个元素及其在序列中的出现次数和相似项之间的链接。相似项之间的链接用于快速发现相似项的位置。
###  **工作流程** 
1. 构建FP树
2. 从FP树中挖掘频繁项集

首先构建FP树，然后利用它来挖掘频繁项集。

为构建FP树，需要对原始数据集扫描两遍。第一遍对所有元素项的出现次数进行计数，根据Apriori原理（如果某元素是不频繁的，那么包含该元素的超集也是不频繁的，所以就不需要考虑这些超集），剔除不频繁元素。在第二遍扫描时，构造只含有频繁项集的FP树。

挖掘频繁项集，首先从在头指针表中的单个频繁元素项开始，对于每一个元素项，获得其对应的条件模式基（条件模式基指的是以说查找元素项为结尾的路径集合，即介于说查找元素项与树根节点之间的所有内容）。然后利用条件模式基构建一个条件FP树。最后，递归地发现频繁项、发现条件模式基，以及发现另外的条件树，知道条件树中没有元素为止。

###  **程序fpGrowth-test.py的运行结果**
```
step-0：构造一个简单数据集
simpDat: [['r', 'z', 'h', 'j', 'p'], ['z', 'y', 'x', 'w', 'v', 'u', 't', 's'], ['z'], ['r', 'x', 'n', 'o', 's'], ['y', 'r', 'x', 'z', 'q', 't', 'p'], ['y', 'z', 'x', 'e', 'q', 's', 't', 'm']]

step-1：将数据集包装为frozenset型的数据
initSet: {frozenset({'t', 'e', 'q', 'm', 'y', 'x', 'z', 's'}): 1, frozenset({'z'}): 1, frozenset({'t', 'y', 'x', 'w', 'z', 'u', 's', 'v'}): 1, frozenset({'t', 'r', 'q', 'p', 'y', 'x', 'z'}): 1, frozenset({'n', 'r', 'o', 's', 'x'}): 1, frozenset({'p', 'r', 'z', 'h', 'j'}): 1}

step-2：创建FP树
myHeaderTab: {'t': [3, <fpGrowth.treeNode object at 0x010D2330>], 'r': [3, <fpGrowth.treeNode object at 0x010D24B0>], 'y': [3, <fpGrowth.treeNode object at 0x010D2430>], 'x': [4, <fpGrowth.treeNode object at 0x010D22F0>], 'z': [5, <fpGrowth.treeNode object at 0x010D22D0>], 's': [3, <fpGrowth.treeNode object at 0x010D2410>]}
   Null Set   1
     z   5
       r   1
       x   3
         t   3
           r   1
             y   1
           s   2
             y   2
     x   1
       r   1
         s   1

step-3：递归查找所有满足条件的频繁项集，并展示其条件树
conditional tree for:  {'t'}
   Null Set   1
     z   3
       x   3
conditional tree for:  {'t', 'x'}
   Null Set   1
     z   3
conditional tree for:  {'y'}
   Null Set   1
     t   3
       z   3
         x   3
conditional tree for:  {'z', 'y'}
   Null Set   1
     t   3
conditional tree for:  {'x', 'y'}
   Null Set   1
     t   3
       z   3
conditional tree for:  {'z', 'x', 'y'}
   Null Set   1
     t   3
conditional tree for:  {'s'}
   Null Set   1
     x   3
conditional tree for:  {'x'}
   Null Set   1
     z   3

示例：从新闻网站点击流中挖掘
步骤一：导入数据集kosarak.dat
步骤二：对初始集合格式化
步骤三：构建FP树，并从中寻找那些至少被10万人浏览过的新闻报道
步骤四：从FP树中发掘那些受人关注的新闻报道之间的关联规则
conditional tree for:  {'1'}
   Null Set   1
     6   107404
conditional tree for:  {'3'}
   Null Set   1
     11   9718
     6   186289
       11   117401
conditional tree for:  {'11', '3'}
   Null Set   1
     6   117401
conditional tree for:  {'11'}
   Null Set   1
     6   261773
 
``` 
FP-growth算法的速度很快，在普通的笔记本电脑上，扫描100万行的数据集、构建树并完成挖掘只需要几秒钟。

###  **示例：从新闻网站点击流中挖掘** 

在项目中有一个kosarak.dat文件，它包含了将近100万条记录。该文件中的每一行包含某个用户浏览过的新闻报道（新闻报道被编码成整数）。一些用户只看过一篇报道，而有些用户看过2498篇报道。通过FP-growth算法，可以迅速得中这100万条记录中挖掘出那些受人关注的新闻报道之间的关联关系。

根据运行程序fpGrowth-test.py发现，只要有人阅读了新闻1或者新闻3或者新闻11后，他就很有可能同时阅读了新闻6；并且如果有人阅读了新闻3，那么他除了很有可能阅读到新闻6以外，他还很可能阅读了新闻11。