FP-Growth：频繁模式增长算法

可视化演示

可视化展示FP-Growth算法核心机制：FP树构建与路径压缩、条件FP树递归挖掘、FP-Growth与Apriori性能对比，交互切换理解频繁模式挖掘。

核心思想：从“一遍遍翻单”到“建好货架一次成型”

老王过去应对电商老板的追问，靠的是最笨的办法：把所有可能一起买的商品组合都列出来，比如“牛奶+面包”“牛奶+鸡蛋”“面包+鸡蛋”……然后翻遍每一张快递单去数哪个组合出现得多。如果商品有几千种，组合数量会爆炸式增长，老王的仓库伙计们被累得直不起腰。Apriori算法就是这条路：先生成候选集，再反复扫描数据库验证，每多一件商品，候选组合就多一倍。

FP-Growth换了个思路。它把订单看成“标签串”，反正相同前缀的单子（比如都从“牛奶→面包”开头）可以在仓库里共用一个货架区，何必每次从头翻？于是算法先扫第一遍数据库，统计每个商品的“热度”（支持度），剔除冷门商品；扫第二遍时，把每张单子的标签按热度从高到低排序，再逐个挂到一棵树上——这棵树就是FP-Tree（频繁模式树）。树搭好了，所有频繁模式都藏在树枝上，顺着节点往下走就能找到，完全不需要再生成候选集。

说回老王：他现在的仓库不用再堆满候选组合清单，而是先造出一棵“共享货架树”，之后任何“哪些东西常一起卖”的问题，都变成在树上顺藤摸瓜。这正是FP-Growth名字里“频繁模式增长”的由来——频繁项集是从树的路径上“长”出来的。

支持度统计：第一遍扫单，先给商品称重

建树之前，老王要做一件事：给仓库里所有商品“称重”。他让伙计把每一张快递单的商品标签抄下来，遇到一个商品就画一笔“正”字。几天下来，每个商品的累计出现次数就是它的支持度计数。那些只出现过一次两次的冷门商品，比如某个顾客偶然买的“老式收音机”，会被直接扔出局——因为它们几乎不可能和其他商品凑成“热卖组合”。

这一步对应算法中的第一遍数据库扫描：统计全部单项的频率，保留达到最小支持度阈值（min_sup）的项，并按频率从高到低排序。这一步至关重要，因为FP树之所以能共享路径、压缩体积，前提是所有订单都把高频项放在前面。如果第一个商品每次都不同，树的分支就会像孔雀开屏一样散开；而热门商品排前面，大量订单就有了相同前缀。

在老王仓库里，这一遍扫描像给商品“过秤”：不够分量的商品直接剔除，剩下的按重量排好队。这样一来，第二遍建树时每位顾客的订单都按“重货在前”的顺序挂上货架，树的分支自然紧凑，为后续的路径压缩打下了基础。

FP树构建：共享前缀，把重复路径压成一根

现在到了重头戏：老王要布置“共享货架”。规则很简单——所有订单的标签必须先按热度排序，然后从根节点开始，一个一个挂上树。如果某个标签在树上已经有同名的宝贝节点，就顺着它走，节点计数加一；如果树上还没有这个标签，就新建一个分支节点。比如三张订单分别是“牛奶-面包-鸡蛋”“牛奶-面包-黄油”“牛奶-面包”，它们的前缀“牛奶→面包”完全一样，树上只需保留一条路径，计数累加到3即可。

这就是FP树的精髓：路径压缩。FP树节点上存的不再是单件商品本身，而是商品的计数。根节点是空货架起点，每个子节点挂着一个商品标签和它的计数。同时，算法维护一张“项头表”，它就像仓库入口的索引目录，把所有频繁项按热度列出来，并链接到树上所有同名节点——之后挖掘时，想找哪个商品，直接通过索引跳到对应节点，不必全树遍历。

老王指着仓库里那排货架笑道：“以前四张单子里有三张都写着'牛奶→面包'，我从头挂四个牛奶、四个面包；现在只挂一个牛奶、一个面包，计数写个3。共享货架一节省，整棵树就瘦了一大圈。”

条件模式基：从树叶往根回溯“局部清单”

货架建好了，接下来就是挖宝环节。FP-Growth 的挖掘是自底向上的——从支持度最低（也就是货架最底层）的节点开始。老王想查“鸡蛋”都和谁一起卖，他不需要再翻原始单据，只需要在项头表里找到“鸡蛋”的链接，顺着指针找到树上所有“鸡蛋”节点，然后从每个“鸡蛋”节点往父节点回溯，一直走到根，把沿途经过的节点路径记下来。

这条回溯出来的路径就叫做“前缀路径”（prefix path），所有前缀路径的集合就叫“条件模式基”（Conditional Pattern Base，CPB）。每条路径还要带上“鸡蛋”节点的计数，因为路径上的商品真正和“鸡蛋”共现的次数等于这个计数。老王把这些局部清单收集齐，再按支持度过滤，就得到了“鸡蛋的条件模式基”——只属于“鸡蛋”的小数据。

这就好比老王想查“鸡蛋的黄金搭档”，他不再翻整仓库的原始单子，而是顺着“鸡蛋”这条藤蔓，把每个挂着鸡蛋的货架支路单独拍个清单。接下来的工作，都在这叠局部清单里完成。

条件FP树：递归降维，挖出完整的频繁模式

有了“鸡蛋”的条件模式基，老王就有了一个缩小版的数据库。他可以对这份局部清单再做一次FP树的构建：统计前缀路径中各商品的支持度，过滤掉不够格的，再挂成一棵小树——这就是“条件FP树”（Conditional FP-Tree）。在这棵小树上继续递归挖掘，每次递归都锁定一个新的后缀商品，模式就一层层“长”出来。

回到“鸡蛋”的例子：假设“鸡蛋”的支持度为2，向下递归时以“面包”为新的后缀，会发现“面包→鸡蛋”出现2次，于是频繁模式{面包，鸡蛋}诞生。再递归一层，可能得到{牛奶，面包，鸡蛋}。整个挖掘过程就像剥洋葱——每次递归剥掉一层，把后缀锚点不断加长，直到条件FP树只剩一个分支或为空为止。

老王把这套递归戏法称作“俄罗斯套娃”：每挖一层，货架就会变小一圈，但每次都会带出一个更长的组合。等所有套娃都打开，仓库里所有“热卖组合”清单就整整齐齐地摆在桌上了。

性能优势：不猜组合，所以快得吓人

Apriori之所以慢，是因为它要“猜组合”：先生成所有候选集，再一遍遍扫数据库验证。候选组合的数量随着商品种类呈指数级增长——10种商品就有1024种组合，20种商品就超过100万种。而FP-Growth只扫两遍数据库：第一遍统计单项频率，第二遍建树。之后所有挖掘都在内存中的FP树上完成，不再触碰原始数据库。

从复杂度上看，FP-Growth的代价主要取决于订单的平均长度和订单数量，呈线性关系；而Apriori的候选集生成阶段是组合数爆炸。树结构还天然做了路径压缩，内存占用也远低于Apriori反复装载的候选集。尤其是面对稀疏数据（每张订单商品少但种类多）时，FP-Growth的优势更加明显。

老王总结道：“Apriori 像一个个去敲门问'你们家有没有牛奶面包'，FP-Growth 则是把全楼的邮箱钥匙全配好，一次进门，之后想找谁就找谁。”

并行化扩展：把货架拆给多个仓库同时干

订单量太大怎么办？老王开了三家分店。他按快递单的编号把数据切成多份，每家分店领到一份订单子集，各自独立构建局部的FP树、独立挖掘频繁模式——这就是“数据划分并行”。因为FP树的构建是可以并行的，每台机器只需要处理自己的那部分订单，互不干扰。

但并行不是免费的午餐。不同的切分方式会导致各分店工作负载严重不均：如果某家分店恰好分到了大量“牛奶面包”订单，它的树必然又高又粗，构建时间远长于其他分店。所以并行化FP-Growth的关键在于负载均衡——要么按商品哈希分组让各节点数据更均匀，要么采用动态任务调度的方式让空闲节点主动领活。最后还需要一个结果合并阶段，把各分店挖出的局部频繁模式汇总，再做一次全局过滤，确保不遗漏全局频繁项。

老王看着三家分店的数据汇总说：“分店越多是越快，但最后合并数据、统一口径这一步省不掉。想要真正跑得快，就得让三家分店干得一样多，别让一家累死三家闲死。”

AI 应用场景

Python 演示

class FPNode:    def __init__(self, item, parent):        self.item = item        self.count = 1        self.parent = parent        self.children = {}        self.link = None  class FPGrowth:    def __init__(self, transactions, min_sup):        self.tx_list = transactions        self.min_sup = min_sup        self.root = FPNode(None, None)        self.header_map = {}        self.order_map = {}        self.link_map = {}     def build(self):        freq = {}        for tx in self.tx_list:            for it in tx:                freq[it] = freq.get(it, 0) + 1        self.header_map = {k: v for k, v in freq.items() if v >= self.min_sup}        self.order_map = {k: i for i, k in enumerate(            sorted(self.header_map, key=lambda x: -self.header_map[x]))}        self.link_map = {k: [] for k in self.header_map}        for tx in self.tx_list:            items = [it for it in tx if it in self.order_map]            items.sort(key=lambda x: self.order_map[x])            cur = self.root            for it in items:                if it not in cur.children:                    node = FPNode(it, cur)                    cur.children[it] = node                    self.link_map[it].append(node)                else:                    cur.children[it].count += 1                cur = cur.children[it]     def prefix_paths(self, item):        paths = []        for node in self.link_map[item]:            path = []            p = node.parent            while p and p.item is not None:                path.append(p.item)                p = p.parent            paths.append((path, node.count))        return paths     def mine(self):        patterns = []        for item in sorted(self.header_map, key=lambda x: -self.header_map[x]):            for path, count in self.prefix_paths(item):                patterns.append((tuple(path) + (item,), count))        return patterns  if __name__ == "__main__":    orders = [        ["牛奶", "面包", "鸡蛋", "果酱"],        ["牛奶", "面包", "鸡蛋"],        ["牛奶", "面包"],        ["牛奶", "果酱", "鸡蛋"],        ["面包", "果酱"]    ]    fp = FPGrowth(orders, min_sup=2)    fp.build()    for pat, cnt in fp.mine():        print(pat, cnt)

1. self.header_map = {k: v for k, v in freq.items() if v >= self.min_sup}第一遍扫描后按最小支持度过滤冷门商品，相当于把不够分量的商品剔除出货架。
2. self.order_map = {k: i for i, k in enumerate(sorted(self.header_map, key=lambda x: -self.header_map[x]))}按热度降序给频繁项编号，保证后续上树时高频项排在路径前面。
3. items.sort(key=lambda x: self.order_map[x])每个事务先按热度排序再插入，这样不同订单才能共享前缀路径。
4. if it not in cur.children: ... else: cur.children[it].count += 1树上已有同名节点就计数加一，否则新建节点，这是路径压缩的核心逻辑。
5. self.link_map[it].append(node)维护项头表与树节点的链接，让后续挖掘能快速定位所有包含某商品的路径。
6. while p and p.item is not None: path.append(p.item)从节点向上回溯父链，提取前缀路径形成条件模式基。

常见误区

面试题