关联规则算法——FP-Growth算法

深碍√TFBOYSˉ_ 2023-09-28 10:44 21阅读 0赞

### **1.关联规则的名词解释** ###

**项集**：数据库中的数据项构成的非空集合

**事务**：一个事务包含了一个或多个项集

**支持度**：包含项集x的事务数量与全部事务数量的百分比

**置信度**：同时包含数据项x和数据项y的事务数量与事务x（或事务y）出现的次数之比

**最小支持度与最小置信度**：关联规则必须满足的最低要求，由用户设定

**频繁项集**：大于等于最小支持度的项集称为频繁项集

**最大频繁项集**：不被其它频繁项集包含的频繁项集称为最大频繁项集

**强关联规则**：大于等于最小支持度和最小置信度称为强关联规则（频繁项集的基础上大于等于最小置信度）

### 2.FP-Growth算法概况和步骤 ###

FP-Growth不会产生候选项集，它采用分而治之的基本思想，将数据库中的频繁项集压缩到一棵频繁模式树中，同时保持项集之间的关联关系。然后将这棵压缩后的频繁模式树分成一些条件子树，每个条件子树对应一个频繁项，从而获得频繁项集，最后进行关联规则挖掘

1.扫描事务数据库，生成频繁1项集L1

2.将频繁1项集L1按照支持度递减顺序排序，根据降序结果调整事务数据库

3.构造FP树

4.FP树挖掘生成频繁项集

（1）按频率从低到高遍历，构造各个节点的条件模式基（头部链表中某一节点的前缀路径组合）

（2）构造条件FP树（条件：支持度大于等于最小支持度）

（3）条件FP树与叶子节点组合得到频繁项集

![1ce768c0a34e4e7e92e46bc891f38b5b.png][]

### 3.FP-Growth算法演示 ###

第一步：

![df04ef3223314652ad43ed901a96d721.png][]

第二步：

![381db123e7c24cca8f136e8496caee98.png][]

第三步：

![6872d326e1c54186a21e60cd0b62897c.png][]

第四步：

FP树挖掘生成频繁项集 ，按频率从低到高遍历，即I5,I4,I3,I1,I2

![64f90671437e4802933cc5768c6970bc.png][]

构造I5条件FP数

![105d1bdbd7a94d67b7d97c684c34edfc.png][]

然后继续构造I4,I3,I1,I2条件FP数。。。。

结论：

![d0b1dd9fd7d24791a50b23659fd8550a.png][]

[1ce768c0a34e4e7e92e46bc891f38b5b.png]: https://img-blog.csdnimg.cn/1ce768c0a34e4e7e92e46bc891f38b5b.png
[df04ef3223314652ad43ed901a96d721.png]: https://img-blog.csdnimg.cn/df04ef3223314652ad43ed901a96d721.png
[381db123e7c24cca8f136e8496caee98.png]: https://img-blog.csdnimg.cn/381db123e7c24cca8f136e8496caee98.png
[6872d326e1c54186a21e60cd0b62897c.png]: https://img-blog.csdnimg.cn/6872d326e1c54186a21e60cd0b62897c.png
[64f90671437e4802933cc5768c6970bc.png]: https://img-blog.csdnimg.cn/64f90671437e4802933cc5768c6970bc.png
[105d1bdbd7a94d67b7d97c684c34edfc.png]: https://img-blog.csdnimg.cn/105d1bdbd7a94d67b7d97c684c34edfc.png
[d0b1dd9fd7d24791a50b23659fd8550a.png]: https://img-blog.csdnimg.cn/d0b1dd9fd7d24791a50b23659fd8550a.png