FP-Growth：频繁模式树挖掘

可视化演示

动态演示FP-Growth的核心机制，通过采集/分析/决策/反馈四种模式展示关键概念与交互流程。

算法背景：从穷举到建树

老板最初请来一位非常老实的账房先生，他先把所有菜的每一种组合都写在纸条上，再拿着纸条到一摞点菜单里逐一核对。菜单上有 20 道菜，组合纸条就有上百万张；每核一组，就得把整摞菜单翻一遍。餐厅开业不过一个月，账房先生就累垮了。这种“穷举一切组合再反复回库核对”的做法，正是 Apriori 算法的真实写照。

在关联规则分析中，每一张点菜单是一条事务（Transaction），每道菜是一个项（Item），我们想找出经常一起出现、构成“频繁项集”的项。Apriori 用“候选生成—逐层验证”的思路工作：先生成所有可能组合，再逐层扫描数据库验证计数。组合数随项数指数膨胀，且每一层验证都要重新扫描整库，这就是它的致命瓶颈。

支持度（Support）是衡量“频繁”的核心指标：一个项集 X 在全部事务中出现的比例。给定最小支持度阈值 minsup，支持度不低于阈值的就是频繁项集。FP-Growth 的创立者韩家炜提出一个反直觉的思路：与其反复扫描验证候选，不如先把整库压缩成一棵树，让挖掘在树上完成。

所以 FP-Growth 的思路，相当于让主厨亲手来整理后厨：先花一遍功夫数清每道菜被点了几次，排出“人气榜”；再花一遍功夫把每张点菜单按人气榜排好，挂到同一棵树上。此后挖掘再也不碰原始菜单——这便是“以树换扫描、以空间换时间”的智慧。

FP-Tree 结构：会共享前缀的树

要理解这棵“点菜单树”，不妨把它想成餐厅后厨的食材架：最上方是总入口（根节点），每个节点是一道菜，节点旁的数字是这道菜在这条路径上被点过的次数。同一个菜名出现在多个分支上，说明它是多个组合里的常客。整座架子从入口开始层层向下，每一条从根到叶的路径，就是一份被压缩后的点菜单。

FP-Tree 是一棵前缀共享树：不同事务按照统一的顺序插入，相同的前缀只保留一份，用递增的计数代表“有很多客人走了同一条路”。每个节点主要包含四样东西：项名（item）、计数（count）、父节点指针、子节点表；此外每个节点还有一个链指针（node-link），指向树中下一个与自己同名的节点，把散落的同名节点串成一条链。

头表（Header Table）则是树的“索引牌”：每个频繁项一张卡片，按支持度从高到低竖直排列，每张卡片通过 node-link 指向该商品在树中的第一个节点。想挖某个项时，顺着头表就能找到它在树上的所有位置，无需全树搜索。而所有事务统一下来的人气顺序，正是前缀能够共享、树能保持紧凑的前提。

回到厨房：头表就是主厨上衣口袋里的小本子，记着每道热门菜挂在食材架的哪些隔层。有了小本子，后续挖掘“黄金组合”时，提到一道菜，主厨就能瞬间定位它参与过的所有做法，不用满厨房翻找。

建树过程：两遍扫描定乾坤

主厨整理菜单只花两遍功夫。第一遍，他把所有点菜单快速过目，用正字法数清每道菜被点了几次，把低于人气门槛（minsup）的冷门菜直接划掉；剩下的菜按人气从高到低排出正式名单。这一遍的目的，是拿到全局的“人气榜”。

第二遍，他重新拿起每张点菜单，只保留名单上出现的菜，并按人气榜的顺序重排。比如原菜单写“鸡蛋、面包、牛奶”，按名单顺序可能变成“面包、牛奶、鸡蛋”。然后逐张把排好的菜单“挂”到树上：从根节点出发，途中遇到同名的孩子节点就往里走、把计数加一；没有同名孩子，就新建一个节点继续往下走。

例如三条事务 {B,A,E}、{B,C}、{B,A}，过滤排序后为 {B,A}、{B,C}、{B,A}。第一条建出路径 B→A，第二条在 B 下新建 C，第三条走到 B 后沿着既有边到达 A，A 的计数加一。大量事务因此共享前缀路径，树的体积被极大压缩，通常远小于原始数据库。

两遍扫描的意义在于：第一次“探路”摸清人气，第二次“搭架”一次成型。此后无论有多少张新菜单，只要数据不变，树就不会变；所有后续挖掘都在树上完成，那叠厚厚的原始菜单再也不用翻动。

条件模式基：追溯每一条来路

树建好了，怎么挖“黄金组合”呢？主厨的作法是倒着挖：先挑一道菜，顺着小本子（头表）找到它在树上的每一处位置，然后从那些位置一路向上，把沿途经过的菜名抄下来，形成一条条“来历路径”。比如挑中 C，就在树上找到所有标着 C 的节点，从每个节点向上抄到根为止。

这些“来历路径”就是条件模式基（Conditional Pattern Base）：对目标项 i 而言，树上所有以 i 结尾的前缀路径的集合。每条路径还附带 i 在该路径末端节点的计数，表示“有多少张点菜单走了这条前缀路径，并且都点了 i”。条件模式基精确描述了“在包含 i 的事务中，其他各项分别出现了多少次”，是下一轮挖掘的原料。

例如挖 C 时，树上有两条通往 C 的路径：root→B→C 与 root→A→C，末端计数分别为 2 与 2，于是 CPB(C) = {B:2, A:2}。接下来用这些前缀路径构造一棵“条件 FP-Tree”：对前缀路径中的各项重新统计频率、筛出频繁项、按频率排序建树，得到一棵规模更小的局部树。整个过程如同“沿着枝条倒走一遍来历”。

条件模式基就像一道菜的历史档案：每一位点过它的客人都留下一条记录，记录里写着那桌同时还点了什么。档案越积越厚，规律就浮现出来——与 C 经常同框的 B 和 A，自然成为下一轮挖掘的焦点。

频繁项集挖掘：递归滚雪球

有了条件 FP-Tree，挖掘就变成一场“滚雪球”：从单道菜出发，每轮在雪球上粘一道新的频繁菜，滚出越来越长的组合。递归的终止条件有两个：其一是条件树为空，没有新的项可粘；其二是条件树退化为一条单路径，此时路径上所有项的组合都能直接枚举，不必再分叉递归。

形式化地说，FP-Growth 对一棵 FP-Tree 与当前前缀 α 递归执行：找出树中所有频繁单项 β，把 β 并入 α，得到频繁项集 α∪{β}；再用 β 的条件模式基构造条件 FP-Tree，带着更大的前缀继续递归。每一个频繁项集都沿着唯一的一条递归路径产生，天然去重。

以 C 为例：先得到 {C}；CPB(C) 中 B、A 都频繁，于是得到 {B,C} 与 {A,C}；再分别以 {B,C}、{A,C} 为前缀继续挖它们的条件树。整个过程中没有任何候选集的生成与验证，而是沿着树结构“定向生长”——这正是 FP-Growth 名字里“Growth（生长）”的含义。

这就像主厨不断追问：“和这道菜一起出现的菜，又常和谁一起出现？”每一问都把范围收窄到一棵局部小树上，答案像滚雪球一样越滚越大，却从不做无用功——没有一张候选清单需要被反复核对。

与 Apriori 对比：树与穷举之争

回到账房先生与主厨的对决。账房先生（Apriori）先找单道菜的常客，再两两组合、三三组合地生成候选清单，每生成一轮都要把整摞菜单重翻一遍核对计数。候选组合数随菜单规模指数爆炸，数据库扫描次数约等于最长频繁项集的长度，菜单一多便寸步难行。

主厨（FP-Growth）则完全不同：他只在开局整理菜单时完整翻两遍，之后所有计数都在树上原地完成。他不需要生成任何候选组合，直接避开“候选爆炸”这个 Apriori 最致命的软肋。这是 FP-Growth 的核心优势——“无候选生成”（candidate-free）的频繁模式挖掘。

从复杂度看，Apriori 的候选总量是全部非空子集数，即指数级 2^|I|-1；而 FP-Growth 把数据库压缩进树后，扫描次数固定为 2，挖掘开销与树的规模成正比，树的规模又通常远小于原始库。当项数多、事务长、支持度阈值低时，FP-Growth 的优势尤其显著。

简单说：Apriori 靠“蛮力枚举 + 反复回库核查”，FP-Growth 靠“一次归档 + 原地查证”。面对同样的菜单，前者让账房先生加班到天亮，后者让主厨气定神闲地端出结论。

实践应用：从黄金组合到智能推荐

“啤酒与尿布”是关联分析最著名的传说：超市发现买尿布的年轻父亲常顺手拿啤酒，于是把两者摆在一起，销量大涨。FP-Growth 正是把这类“黄金组合”从海量收银小票中挖出来的主力算法——先把每张小票按用户会话聚成事务，再建树、挖掘，一气呵成。

挖出频繁项集后，通常需要进一步计算置信度（Confidence）：买了 A 的顾客中，有多少比例也买了 B。高于阈值就形成一条强关联规则 A⇒B，可用于货架摆放、捆绑促销、交叉推荐。置信度回答的是“确定性”问题，与回答“普遍性”问题的支持度互为补充。

现代电商与内容平台面对亿级行为数据时，FP-Growth 提供了一条实用路线：按会话把行为聚成事务 → 用 FP-Growth 挖掘频繁共现 → 用置信度、提升度筛选规则 → 接入推荐系统。Python 生态中的 mlxtend 等库提供了封装好的实现，底层依旧沿用“两遍扫描建树 + 递归挖掘”的本篇思想。

从餐馆点菜单到超市收银小票，从电商购物车到 App 点击流，FP-Growth 干的是同一件事：把散落的事务凝成一棵树，再从树上摘下一串串“黄金组合”。这张“树上的菜单”，正是数据挖掘教给我们的生意密码。

AI 应用场景

Python 演示

# -*- coding: utf-8 -*-"""FP-Growth 频繁模式树挖掘: 从超市小票中发现"黄金组合" """ from collections import defaultdict  class FPNode:    """FP-Tree 节点: item 商品名, count 计数, parent 父节点"""    def __init__(self, item, count, parent):        self.item = item        self.count = count        self.parent = parent        self.link = None          # 头表链: 下一个同名节点        self.children = {}        # 子节点字典  def build_tree(records, min_sup):    """两遍扫描建树: 第一遍统计频率, 第二遍逐条插入"""    freq = defaultdict(int)    for rec in records:        for item in set(rec):            freq[item] += 1    freq = {k: v for k, v in freq.items() if v >= min_sup}    if not freq:        return None, {}, []    order = sorted(freq, key=lambda k: freq[k], reverse=True)   # 人气榜    header = {}    root = FPNode(None, 0, None)    for rec in records:        items = [it for it in order if it in set(rec)]          # 过滤加排序        cur = root        for item in items:            if item not in cur.children:                cur.children[item] = FPNode(item, 0, cur)                if item in header:                              # 挂入头表链表                    tail = header[item]                    while tail.link:                        tail = tail.link                    tail.link = cur.children[item]                else:                    header[item] = cur.children[item]            cur = cur.children[item]            cur.count += 1    return root, header, order  def mine_frequent(header, min_sup, prefix):    """递归挖掘: 从条件模式基出发, 逐层长出频繁项集"""    result = []    for item in sorted(header, key=lambda k: header[k].count):        new_prefix = prefix + [item]        result.append(new_prefix)        # 收集 item 的所有前缀路径(条件模式基)        paths, node = [], header[item]        while node:            path, parent = [], node.parent            while parent and parent.item is not None:                path.append(parent.item)                parent = parent.parent            if path:                paths.append((path, node.count))            node = node.link        if not paths:            continue        # 用条件模式基统计局部频率, 构建条件 FP-Tree        local_freq = defaultdict(int)        for path, cnt in paths:            for it in path:                local_freq[it] += cnt        sub_order = [it for it, c in local_freq.items() if c >= min_sup]        sub_order.sort(key=lambda it: local_freq[it], reverse=True)        if not sub_order:            continue        sub_root = FPNode(None, 0, None)        sub_header = {}        for path, cnt in paths:            cur = sub_root            for it in sub_order:                if it not in path:                    continue                if it not in cur.children:                    cur.children[it] = FPNode(it, 0, cur)                    if it in sub_header:                        tail = sub_header[it]                        while tail.link:                            tail = tail.link                        tail.link = cur.children[it]                    else:                        sub_header[it] = cur.children[it]                cur = cur.children[it]                cur.count += cnt        result.extend(mine_frequent(sub_header, min_sup, new_prefix))    return result  def fp_growth(records, min_sup):    """入口: 返回所有频繁项集"""    root, header, order = build_tree(records, min_sup)    return mine_frequent(header, min_sup, [])  if __name__ == '__main__':    records = [        ['牛奶', '面包', '鸡蛋'],        ['面包', '啤酒'],        ['面包', '黄油'],        ['牛奶', '面包', '啤酒'],        ['牛奶', '黄油'],        ['面包', '黄油'],        ['牛奶', '黄油'],        ['牛奶', '面包', '鸡蛋'],    ]    min_sup = 2    print('== FP-Growth 频繁项集, 最小支持度 = %d ==' % min_sup)    for itemset in fp_growth(records, min_sup):        sup = sum(1 for rec in records if set(itemset).issubset(set(rec)))        print('{%s}  支持度 = %d' % ('+'.join(itemset), sup))

1. freq = {k: v for k, v in freq.items() if v >= min_sup}第一遍扫描后，把点单次数低于阈值的冷门菜全部过滤掉
2. order = sorted(freq, key=lambda k: freq[k], reverse=True)按支持度从高到低排出“人气榜”，它是所有事务统一的插入顺序
3. items = [it for it in order if it in set(rec)]每条事务只保留人气榜上的菜，并按同一顺序重排
4. if item not in cur.children:有同名孩子就走老路，没有才新建节点，这正是“共享前缀”的实现
5. tail.link = cur.children[item]把新节点挂进头表的单向链，便于挖掘时快速找到所有同名位置
6. paths.append((path, node.count))顺着链收集每条前缀路径和末端计数，得到条件模式基
7. sub_order.sort(key=lambda it: local_freq[it], reverse=True)条件树同样按局部频率降序排列，继续复用建树逻辑
8. result.extend(mine_frequent(sub_header, min_sup, new_prefix))每找到一个频繁项就并入前缀，再递归挖掘条件树，像滚雪球一样生长
9. sup = sum(1 for rec in records if set(itemset).issubset(set(rec)))展示时回原始小票核对支持度，验证挖掘结果

常见误区

面试题