首页 > 编程语言 >数据挖掘算法之【8k 字详解FpGrowth算法】—— 附加python代码案例

数据挖掘算法之【8k 字详解FpGrowth算法】—— 附加python代码案例

时间：2025-01-05 14:59:26浏览次数：3  
标签：8k 支持 项集 频繁 FpTree 算法 数据挖掘 排序 节点

大家好，我是摇光~，用大白话讲解所有你难懂的知识点

之前用大白话讲了 Apriori算法 ，如果不懂 Apriori算法，可以去看这篇文章：7k 字详解Apriori算法

我们在说 Apriori算法 的时候，讲过他的缺点，因为要对数据库做频繁的遍历，会产品大量的候选项集，增加计算的复杂性。

比如长度为 1 的频繁项集有 10000 个，长度为 2 的候选项集将会超过 1000万，如果生成规则很长，产生的中间元素也很大。

一、背景

FP-Growth算法的提出，就是解决Apriori算法在挖掘长频繁模式时性能低下的问题。

Apriori算法在产生频繁模式完全集前需要对数据库进行多次扫描，同时产生大量的候选频繁集，导致时间和空间复杂度较大。

而FP-Growth算法通过构建频繁模式树（FP-tree）来压缩存储频繁项集，从而高效地挖掘频繁项集。

二、回顾知识点

在正式讲 FP-Growth算法 的时候，我们来回顾一些 Apriori算法 的专用名词，以方便后续讲解 FP-Growth算法 ：

  • 1、项：比如超市有{牛奶、面包、可乐，…}，牛奶就是一个项，面包也是一个项。
  • 2、项集：比如一个订单{牛奶，面包，可乐}，那么他的项集就有{【牛奶】、【面包】、【可乐】、【牛奶、面包】、【牛奶、可乐】、【面包、可乐】、【牛奶、面包、可乐】}
  • 3、关联规则：在计算置信度、提升度的时候，会有个前后的关系，记作：牛奶 => 面包；牛奶是前项，面包是后项
  • 4、支持度：Support(X => Y) = P(X U Y)，比如含有【牛奶、面包】的订单有5个，总共统计的订单有 10个，那么 Support(牛奶 => 面包) = 5/20 = 0.25。
  • 5、频繁项集：如果支持度 >= 最小支持度，就是频繁项集。
  • 6、置信度：Confidence(X => Y) = P(Y | X) = Support(X ∩ Y) / Support(X)，是购买 X 后，购买 Y 的概率。
  • 7、提升度：Lift(X ⇒ Y) = Confidence(X ⇒ Y) / Support(Y)，表示X的出现，对Y有什么影响，积极的影响还是消极的影响。

三、FP-Growth算法

在理解 FP-Growth算法 前，我先来说个定理，这样便于后面的理解。

看不明白没关系，我后面举了一个例子
如果 A是频繁项集（也就是A的支持度大于最小支持度）
那么在包含A的所有项集中，产生的频繁项集，和 A 组合也是频繁项集。

举个例子：

有这样一个项集：{【AB】、【AC】、【ABC】、【BC】、【BCD】}
最小支持度为 0.4，则次数 >= 2 次就是频繁项集。

{【A：3】、【B：4】、【C：4】、【D：1】}
可以看出单项集的频繁项集有 A、B、C

那么包含A 的项集里 {【AB】、【AC】、【ABC】}，这里 B 出现2次，则B是频繁项集。
那么组合【AB】也是频繁项集，因为 AB 出现的次数 = 在A项集中B出现的次数。
所以B是频繁项集，AB也必然是频繁项集。

那么 AB 组合的支持度 Support(AB) = 在A项集里面Support(B) > 最小支持度；则AB是频繁项集。

反正大家记住这个定理就ok了；接下来就写全部的步骤~

1、找出单项的频繁项集，并求出支持度，去除小于最小支持度的。

我也是用一个例子来举例说明，这样更容易理解。

看下图：左边是我们的项集，需要求出左边项集的频繁项集。

在这里插入图片描述

设置最小支持度为：0.2
则项集出现的次数 >= 0.2*15 = 3 次，就是频繁项集。

现在我们先处理数据： （这里先不要问为什么这么处理，看到之后的步骤就知道了。）

  • 1、计算：计算支持度，我们根据下图左边的表格，计算每一项的支持度；这里计算ABCDEFG 的支持度，支持度的计算就是 次数/总次数。
  • 2、单项排序：再根据支持度大小进行排序，下图中间表的 “2、排序”，排序后的顺序为：AEBFDGC
  • 3、删除：删除支持度小于最小支持度的项，C的支持度为：0.13，删除 C，剩余 的项：AEBFDG；在这里就得到单项频繁项集：{A、E、B、F、D、G}
  • 4、项集排序：我们再对每个项集按照刚刚排序的顺序，对每项进行排序。（注意：这里也需要将删除的项在项集中删除。）根据这样AEBFDG 排序，例如左边的是 ABCD，由于C删除，就剩ABD，排序后是：ABD；例如第二行ABE，排序后是：AEB。

做完第3步骤，我们可以得到单项频繁项集：{A、E、B、F、D、G}

在这里插入图片描述

2、构建FpTree

这一步，我们要构建一棵树，树的顶点用 root 吧

现在我们针对上图中最右侧的表格，进行每一项扫描。

2.1、首先扫描第一行【ABD】，放入树里面。

这里需要注意，我们需要有一个记录，记录这个项出现几次
所以有 A：1，表示 A 现在出现一次了。

在这里插入图片描述

2.2、再扫描下一行【AEB】，也是按照顺序插入树中。

注意：因为树之前就有 A，所以我们不需要重新插入 A，只需要计数 +1 就ok

在这里插入图片描述

2.3、之后我就不一一列举了，直接写全 FpTree 树。

下图中间就是 FpTree 树。

这个FpTree树，有很多特点：

1、中间FpTree树每一项的次数相加等于右边的项的次数。
2、例如左边的 ABD，在FpTree树中记录了两次 D的计数是 2，就表明这条路径有两个项集。
3、左边表格的每一项都可以从树里恢复出来。

在这里插入图片描述

3、找出每一项的频繁项集

有了上面的FpTree树，我们就能找频繁项集。

我们在第一步就知道了 1项集 {A、E、B、F、B、G} 是频繁项集。
我们现在来对每个 1项集，来求他的频繁项集

例如：我们求包含A的频繁项集，那么就是求包含A的组合
如果组合次数 >= 3，那么这个项集就是频繁项集。

观察整棵树，我们从叶节点开始求取。这里的叶节点有{D、G、F}
注意：这里可以算做循环开始

3.1 先找 G 的频繁项集

我们先找个简单的，先找 G 的频繁项集，先找 2项频繁项集，再找 3项频繁项集。
也就是我想知道 哪些与G组合 的次数 >= 最小支持度。

要想找出 G 相关的频繁项集，肯定我们只看与 G 相关的
从左边的树来看，包含 G 的一共有4条路径，我们将其列出来。

在这里插入图片描述

我们先来从肉眼看，这里面都是包含 G 的。
我们计算一下单项的出现次数： {A：3，E：3，B：2，D：1}
由于这些都是在已有G的基础上计算，是不是也表示：{AG：3，EG：3，BG：2，DG：1}

  • 这里是不是可以联想到我最开始写的那个定理。

那么在这里：（我用次数来表示最小支持度，这样方便讲解。）

  • {B、D}都是 < 3 的，小于最小支持度，表示不是频繁项集。
  • {A、E} >= 3 ，则 A、E 和G的组合 {AG、EG} 就是频繁项集。

上面是通过肉眼看出来的，我们来实际写算法：

第一步：我们先求含有 G 的 2项频繁项集：

我们来针对上面筛选出来的包含 G 的项集来分析。
看下面的图片，是不是很熟悉。

1、计算：计算支持度
2、单项排序 ：再根据支持度大小进行排序，得到：AEBD
3、删除：删除支持度小于最小支持度的项（这里有变动）

  • 在删除后，我们得到了两个 A、E项，是频繁项集。
  • 因为这里是在 G 的基础上，求出频繁项集
  • 所以这里需要组合{AG、EG}，然后就可得到 G 的 2项频繁项集。

4、项集排序：对每一项按照 AE 排序，得到排序后的项集。
5、构建 FpTree树：根据项集排序构建 FpTree树。（为下一次循环做准备）

在这里插入图片描述

从上面的计算，我们得到2个 2项频繁项集：{AG、EG}。

第二步：我们再求含有 G 的 3项频繁项集：

3项频繁项集，肯定是在 2项频繁项集{AG、EG} 的基础上求取。
结合 FpTree树来看，现在树只剩下 root - A:3 - E:3

这里我们需要判断，哪些 2项频繁项集需要求取 3项频繁项集：

  • 我们先看 AG：A 的父节点是 root，所以 AG 没有 3项频繁项集。
    （记住这个重点：循环结束的点是项集上面是根节点，就不再循环。）
  • 再看 EG：由于 E 的父节点为 A，所以需要按照下图步骤进行计算。
    （在下图的第三步时，得到 A项为频繁项集，因为是在 EG 基础上的频繁项集，所以需要与 EG相结合，就得到 3项集{AEG}频繁项集）

在这里插入图片描述

我们通过上面的就得到了含有 G 的三项集频繁项集{ AEG }。

第三步：我们再求含有 G 的 4项频繁项集：

4项频繁项集肯定是在 3项频繁项集的基础上进行。

我们对 FpTree 进行判断，{ AEG }的 A 的父节点是不是root，如果是root就终止循环，如果不是，就结束循环；这里A的父节点是root，所以终止循环。

为什么要通过判断父节点是不是 root ？
因为父节点不是 root，那么就可能形成组合，就需要判断组合是不是 频繁项集。
如果父节点是 root，那么就没办法形成组合，就不需要再进行下一步计算了。

上面整个就是求一个单项 G 的频繁项集，在这里进行了：三次循环。

  • 第一次求出了 G 的2项频繁项集，第二次求出了 G 的3项频繁项集。第三次判断不能求得 4项频繁项集

  • 求得结果：含有 G 的频繁项集：{G、AG、EG、AEG}。

  • 这里我们值得注意的是：循环结束的标志是判断需要求的项集，FpTree 父节点是不是 root 节点。

总结一下，循环的步骤是：

  • 1、判断：判断是否有必要求更高一项的频繁项集
  • 2、计算：计算包含频繁项集的项集的项的支持度
  • 3、单项排序：根据支持度进行单项排序
  • 4、删除：删除支持度小于最小支持度的项，得到单项频繁项集
    • 这里需要与组合（频繁项集）和（单项频繁项集），得到更高一项的频繁项集。
  • 5、项集排序：针对项集的每一项进行排序
  • 6、构建 FpTree

讲完 G 的频繁项集，如果大家懂了，就可以不用看下面求 D 的频繁项集。
如果还是不懂，可以再往下看。

3.2 求含 D 的频繁项集

（可能我会尽量简短一点的讲述，不过该有的步骤都不会省。）

1、先找出 FpTree 含D的路径，并得到项集

注意：ABD是有两次，取的是叶节点的次数。

在这里插入图片描述

2、找包含 D 的 2项频繁项集

找出 D 的2项频繁项集，就需要利用上面第一步计算得到的项集。

六步：

1、判断：判断 D 的父节点是否有除 root 节点以外的节点，若有，就继续，若无，就终止循环。
2、计算：计算支持度，大于最小支持度的有：{A、E、B、F}
3、单项排序 ：这里对 {A、E、B、F} 排序
4、删除：删除支持度小于最小支持度的项，这里没有小于最小支持度的。（支持度都 >= 最小支持度）得到在 D 的基础上的单项频繁项集： {A、E、B、F}

  • 这里需要组合{AD、ED、BD、FD}，得到 2项 频繁项集。
  • 所以 G 的 2项频繁项集为 {AD、ED、BD、FD}

5、项集排序：针对 删除D的项集再重新排序。
6、构建 FpTree树：根据步骤 4 的数据进行FpTree构建，为下次循环做准备。

在这里插入图片描述

在上面五步中，第三步就可以得到包含 D的 2项频繁项集： {AD、ED、BD、FD}

还得到一个表和树，之后找 3项频繁项集，就是以这个为基础查找。
在这里插入图片描述

3、找包含 D 的 3项频繁项集

这里需要增加 1 步，其实也是之前做过的步骤，只是没有写到那 6 步里面。

七步：

1、判断：判断是否需要求频繁项集，如果项集的父节点是根节点，就不需要进行下面的计算，如果不是根节点，就需要进行下面的计算。 {AD、ED、BD、FD} 进行一一判断。

  • AD 的 A 的父节点是根节点，所以 AD 没有 3 项项集。
  • ED 的 E 的父节点有A，所以 ED 需要进行下面计算，找到 3项频繁项集
  • BD 的 B 的父节点有A、E，所以 BD 需要进行下面计算，找到 3项频繁项集
  • FD 的 F 的父节点有B、E，所以 FD 需要进行下面计算，找到 3项频繁项集

2、找出前缀项集：我们需要在排序后的项集中找出想要前缀项集。
3、计算：计算支持度
4、单项排序 ：对每个单项进行排序
5、删除：删除支持度小于最小支持度的项

  • 记住这里要组合，就可求得高一项的频繁项集。

6、项集排序：对项集进行排序
7、构建 FpTree树：根据步骤 4 的数据进行FpTree构建，为下次循环做准备

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

值得注意的点是：我们每次左上角的表格是取的所求项集的前缀，一定要注意。

在上面图片看出可以得到 D的 3项频繁项集： {ABD、AED、EFD}

4、找包含 D 的 4项频繁项集

由于 AED、ABD、EFD 形成的 FpTree ，A和E的父节点是root，所以循环结束。

上面就是求 D 的频繁项集全步骤，求得结果：

  • 1项频繁项集：{D}
  • 2项频繁项集：{AD、ED、BD、FD}
  • 3项频繁项集：{ABD、AED、EFD}

以上的步骤都是求叶节点，其实求中间节点也是一样。
我接下来讲一下求中间节点 B 的频繁项集。

3.3 求含 B 的频繁项集

怕大家忘了，我先把树拿出来。
在这里插入图片描述
这里其实也还是7步，我们来一一解析：

1、判断：判断B节点的父节点是不是 root，B节点父节点有：A、E、root，所以存在可能存在 2项频繁项集。
2、找出前缀项集：采用后序遍历树，可以得到 B 的前缀的项集。
3、计算：计算每个项的支持度
4、单项排序 ：按照计算的支持度排序
5、删除：删除 < 最小支持度的项

  • 注意这里需要组合。

6、项集排序：根据“单项排序”的结果，对每一个项集进行排序
7、构建 FpTree树：根据上面的排序结果构建树

在这里插入图片描述

由于A 的父节点是 root，所以不需要求 AB 的 3项频繁项集。

在这里插入图片描述

通过上面 3个案例计算，我们就知道其实 FpGrowth算法就这几步。
我们来总结一下。

四、总结

前言：简单通俗一点解释一下：项 -> 是指商品种类，项集 -> 客户购买的订单。

步骤：

  • 1、遍历求单项：遍历第一遍数据，取得每一项的次数，并求出每一项的支持度
  • 2、单项排序：对求得的支持度排序
  • 3、求出1项频繁项集：筛选出 >= 最小支持度的项，得到 1 项频繁项集。
  • 4、项集排序：对每一个项集按照单项排序的顺序进行排序
  • 5、构建 FpTree：根据上面排序的结果，构建FpTree
  • 6、循环：对每项求2项、3项、4项…频繁项集
  • 6.1 判断：根据 Fptree判断，所求项集的父节点是否是 root
  • 6.2 找出前缀项集：后序遍历树，找到前缀项集
  • 6.3 计算：计算每项支持度
  • 6.2 单项排序：按照计算支持度排序
  • 6.2 删除：删除 < 最小支持度的项，并与所求项集组合得到高一项的频繁项集
  • 6.2 项集排序：根据“单项排序”的结果，对每一个项集进行排序
  • 6.2 构建 FpTree：根据上面排序结果构件树

五、FpGrowth算法的应用（python语言）

这里我没有解析FpGrowth算法的python源码，而是使用 mlxtend库的FpGrowth算法。

如果需要解析源码，可以评论@我，之后可以出一期~

import pandas as pd
from mlxtend.frequent_patterns import fpgrowth
from mlxtend.preprocessing import TransactionEncoder

# 模拟的超市购物数据集
transactions = [
    ['A', 'B', 'C', 'D'],
    ['A', 'B', 'E'],
    ['F', 'B', 'E'],
    ['A', 'E', 'F', 'D'],
    ['B', 'A', 'E', 'G'],
    ['A', 'B', 'C'],
    ['F', 'E', 'D'],
    ['A', 'E', 'G'],
    ['B', 'A', 'E', 'F', 'D'],
    ['A', 'B', 'E', 'F'],
    ['A', 'E', 'D', 'G'],
    ['B', 'A', 'D'],
    ['A', 'B', 'E'],
    ['F', 'B', 'G'],
    ['A', 'E', 'F'],
    # 可以继续添加更多事务以构成更复杂的数据集
]

# 将事务数据集转换为适合FP-Growth算法的格式
# 使用TransactionEncoder将列表形式的事务数据转换为适合机器学习模型的格式
te = TransactionEncoder()
te_ary = te.fit(transactions).transform(transactions)
df = pd.DataFrame(te_ary, columns=te.columns_)

# 设置最小支持度阈值
min_support = 0.20  # 这里设置为0.2，表示频繁项集至少需要出现在20%的事务中

# 使用FP-Growth算法挖掘频繁项集
frequent_itemsets = fpgrowth(df, min_support=min_support, use_colnames=True)

# 打印频繁项集及其支持度
print(frequent_itemsets)

结果：

在这里插入图片描述

以上就是完整的一套从理论到实践的 FpGrowth算法 。

如果有什么不对的地方，欢迎指正~

我会竭尽全力用大白话讲解你们难懂的知识。

标签：8k,支持,项集,频繁,FpTree,算法,数据挖掘,排序,节点
From： https://blog.csdn.net/qq_41877371/article/details/144631972

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99