算法系列-日志挖掘中的FP-Tree算法

背景

https://blog.csdn.net/hunhun1122/article/details/79699791

https://blog.csdn.net/peiwang245/article/details/79434853?spm=1001.2101.3001.6650.5&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-5.topblog&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-5.topblog&utm_relevant_index=10

FP-Growth(Frequent Pattern Tree，频繁模式树)算法是韩家炜老师提出的关联分析算法，巧妙的将树型结构引入算法中，它采取如下分治策略：提供频繁项集的数据库压缩到一棵频繁模式树（FP-Tree），但仍保留项集关联信息；该算法和Apriori算法最大的不同有两点：
第一，不产生候选集。
第二，只需要两次遍历数据库，大大提高了效率。

流程如下：
1：先扫描一遍数据集，得到频繁项为1的项目集，定义最小支持度（项目出现最少次数），删除那些小于最小支持度的项目，然后将原始数据集中的条目按项目集中降序进行排列。
2：第二次扫描，创建项头表（从上往下降序），以及FP树。
3：对于每个项目（可以按照从下往上的顺序）找到其条件模式基（CPB，conditional patten base）,递归调用树结构，删除小于最小支持度的项。如果最终呈现单一路径的树结构，则直接列举所有组合；非单一路径的则继续调用树结构，直到形成单一路径即可。

问题抽象：

频繁模式(Frequent pattern)

设 $I=\left{a_{1}, a_{2}, \ldots, a_{m}\right}$ 是项目集合，在数据库中存储相关事务 $D B=\left\langle T_{1}, T_{2}, \ldots, T_{n}\right\rangle$, 其中 $T_{i}(i \in[1 \ldots n])$，$T_{i}$为非空集合，集合中元素由项目集合$I$中元素（元素可以重复）构成。例如下面案例：
1
2
3
4
5
6
7
I = {'o', 'e', 'd', 'g', 'h', 'p', 'l', 'j', 'k', 'i', 'a', 'b', 'f', 's', 'c', 'n', 'm'}

T1 = {f,a,c,d,g,i,m,p}
T2 = {a,b,c,f,l,m,o}
T3 = {b,f,h,j,o}
T4 = {b,c,k,s,p}
T5 = {a,f,c,e,l,p,m,n}
n项集

集合中每条数据含有的n个项目。例如集合$I$就是1项集。通常即为Ln。
支持度（support ）

模式集合A的发生频率。
频繁模式（frequent pattern）

对于指定的支持度 $\xi$ ，支持度大于等于 $\xi$ 值的模式集合全体。

由此对于理论抽象，我们有朴素但重要的引理：

引理1：设A、B是模式集合，并且A是B的真子集，如果A的支持度为a，则B的支持度b<=a。

第一部分 Apriori算法

在FP-Tree算法前，关联规则挖掘的经典算法是Apriori算法。找出所有的频繁项集（支持度必须大于等于给定的最小支持度阈值），在这个过程中连接步和剪枝步互相融合，最终得到最大频繁项集L k 算法基本实现流程描述如下：

连接步

的目的是找到K项集。对给定的最小支持度阈值，分别对1项候选集C 1 ，剔除小于该阈值的项集得到1项频繁集L 1 ；下一步由L 1 自身连接产生2项候选集C 2 ，保留C 2 中满足约束条件的项集得到2项频繁集，记为L 2 ；再下一步由L 2 与L 3 连接产生3项候选集C 3 ，保留C 2 中满足约束条件的项集得到3项频繁集，记为L 3 ……这样循环下去，得到最大频繁项集L k
剪枝步：

剪枝步紧接着连接步，在产生候选项C k 的过程中起到减小搜索空间的目的。由于C k 是L k-1 与L 1 连接产生的，根据Apriori的性质频繁项集的所有非空子集也必须是频繁项集，所以不满足该性质的项集不会存在于C k 中，该过程就是剪枝。

2）由频繁项集产生强关联规则：由过程1）可知未超过预定的最小支持度阈值的项集已被剔除，如果剩下这些规则又满足了预定的最小置信度阈值，那么就挖掘出了强关联规则。

Apriori算法的缺点是对于候选项集里面的每一项都要扫描一次数据，从而需要多次扫描数据，I/O操作多，效率低。为了提高效率，提出了一些基于Apriori的算法，比如FPGrowth算法。

并行处理

https://www.cnblogs.com/mstk/archive/2017/07/16/7190179.html

参考文献及资料

[1] Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM sigmod record, 29(2), 1-12.

目录

背景

第一部分 Apriori算法

并行处理

参考文献及资料