从‘啤酒与尿布’到代码：FP-Growth算法实战，教你用Python挖掘数据中的隐藏关联

超市货架上啤酒和尿布的意外组合，曾是零售业最著名的数据挖掘案例之一。这种看似不合理的搭配背后，隐藏着购物篮分析中关联规则挖掘的智慧。如今，这种分析能力已经渗透到电商推荐、医疗诊断、网络安全等各个领域。本文将带你用Python实现FP-Growth算法，无需深奥的数学公式，只需跟着代码一步步构建属于你的"商品关联地图"。

1. 关联规则挖掘的商业密码

1992年，沃尔玛的分析师发现周五晚上尿布和啤酒的销量存在神秘关联。深入调查后，一个有趣的社会现象浮出水面：年轻父亲们常在周末采购尿布时顺手带走啤酒。这个发现催生了经典的"啤酒尿布"陈列策略，也奠定了关联规则挖掘的商业价值基础。

现代商业场景中，关联规则的应用远比我们想象的广泛：

• 电商平台 ：根据"买了又买"数据推荐组合商品
• 视频网站 ：通过观看记录推荐相关联的内容
• 医疗系统 ：分析药品搭配规律优化处方组合
• 金融服务 ：识别金融产品之间的关联销售机会

传统Apriori算法需要多次扫描数据库，当面对百万级交易记录时效率低下。FP-Growth算法通过构建紧凑的FP树结构，将扫描次数减少到仅两次，大大提升了挖掘效率。

2. FP-Growth算法核心架构

FP-Growth算法的精妙之处在于它将原始交易数据压缩成一棵FP树，同时维护一个头表结构来快速定位树中的节点。这种设计使得算法能够高效地发现频繁项集，而无需生成大量的候选集。

2.1 FP树与头表结构

FP树由以下关键组件构成：

1. 根节点 ：标记为null，作为树的起点
2. 项节点 ：包含项名和支持度计数
3. 节点链接 ：连接同名项的所有节点

头表则记录了每个频繁项及其在FP树中的链表头指针：

项名	支持度计数	节点链表头
牛奶	8	→节点1
面包	6	→节点2
鸡蛋	5	→节点3

构建FP树的关键Python类如下：

class Node:
    def __init__(self, node_name, count, parentNode):
        self.name = node_name  # 节点名称
        self.count = count  # 支持度计数
        self.nodeLink = None  # 节点链接
        self.parent = parentNode  # 父节点
        self.children = {}  # 子节点字典

2.2 构建FP树的两阶段过程

第一阶段：构建头表

def create_header_table(data_set, min_support):
    item_count = {}
    # 第一次扫描：统计各项出现次数
    for transaction in data_set:
        for item in transaction:
            item_count[item] = item_count.get(item, 0) + 1
    
    # 过滤非频繁项，构建头表
    headerTable = {}
    for k in item_count:
        if item_count[k] >= min_support:
            headerTable[k] = [item_count[k], None]  # [计数, 节点链表头]
    
    return headerTable

第二阶段：构建FP树

def update_tree(items, node, headerTable):
    if items[0] in node.children:
        # 已有子节点则计数增加
        node.children[items[0]].count += 1
    else:
        # 创建新节点
        node.children[items[0]] = Node(items[0], 1, node)
        # 更新头表链表
        if headerTable[items[0]][1] is None:
            headerTable[items[0]][1] = node.children[items[0]]
        else:
            update_header(headerTable[items[0]][1], node.children[items[0]])
    
    # 递归处理剩余项
    if len(items) > 1:
        update_tree(items[1:], node.children[items[0]], headerTable)

3. 从FP树挖掘频繁项集

FP-Growth算法采用分治策略，通过构建条件FP树来递归发现频繁项集。这个过程就像剥洋葱一样，一层层地揭示数据中的关联模式。

3.1 寻找条件模式基

条件模式基是FP树中所有以目标项结尾的前缀路径集合。例如，要找到项'e'的条件模式基：

def find_cond_pattern_base(node_name, headerTable):
    treeNode = headerTable[node_name][1]  # 获取第一个节点
    cond_pat_base = {}
    
    while treeNode is not None:
        prefix_path = []
        ascend_tree(treeNode, prefix_path)  # 回溯到根节点获取路径
        if len(prefix_path) > 1:
            # 存储路径(排除项本身)及其计数
            cond_pat_base[frozenset(prefix_path[1:])] = treeNode.count
        treeNode = treeNode.nodeLink  # 处理下一个同名节点
    
    return cond_pat_base

3.2 构建条件FP树

得到条件模式基后，可以构建特定项的条件FP树：

def create_cond_fptree(cond_pat_base, min_support):
    cond_pat_dataset = []
    for itemset in cond_pat_base:
        # 根据计数重复添加事务
        for _ in range(cond_pat_base[itemset]):
            cond_pat_dataset.append(list(itemset))
    
    # 构建条件FP树
    cond_tree, cond_header = create_fptree(cond_pat_dataset, min_support)
    return cond_tree, cond_header

3.3 递归挖掘频繁项集

def mine_fp_tree(headerTable, min_support, prefix, freq_item_list):
    # 按支持度升序排序头表中的项
    sorted_items = [v[0] for v in sorted(headerTable.items(), 
                      key=lambda p: p[1][0])]
    
    for item in sorted_items:
        new_freq_set = prefix.copy()
        new_freq_set.add(item)
        freq_item_list.append(new_freq_set)
        
        # 获取条件模式基并递归挖掘
        cond_pat_base = find_cond_pattern_base(item, headerTable)
        cond_tree, cond_header = create_cond_fptree(cond_pat_base, min_support)
        
        if cond_header is not None:
            mine_fp_tree(cond_header, min_support, new_freq_set, freq_item_list)

4. 实战：用FP-Growth分析购物篮数据

让我们用一个真实场景演示FP-Growth算法的完整应用。假设我们有以下超市交易数据：

dataset = [
    ['牛奶', '面包', '饼干'],
    ['面包', '尿布', '啤酒', '鸡蛋'],
    ['牛奶', '尿布', '啤酒', '可乐'],
    ['面包', '牛奶', '尿布', '啤酒'],
    ['面包', '牛奶', '尿布', '饼干']
]

4.1 参数设置与预处理

min_support = 2  # 最小支持度阈值
min_conf = 0.6   # 最小置信度阈值

# 预处理：去除每笔交易中的重复项
dataset = [list(set(trans)) for trans in dataset]

4.2 构建FP树并挖掘频繁项集

# 构建初始FP树
fp_tree, header_table = create_fptree(dataset, min_support)

# 挖掘所有频繁项集
freq_items = []
mine_fp_tree(header_table, min_support, set(), freq_items)

# 输出结果
print("频繁项集：")
for itemset in freq_items:
    print(itemset)

4.3 生成关联规则

得到频繁项集后，我们可以进一步生成关联规则：

def generate_rules(freq_items, support_data, min_conf):
    rules = []
    for freq_set in freq_items:
        if len(freq_set) > 1:
            for item in freq_set:
                antecedent = freq_set - {item}
                conf = support_data[freq_set] / support_data[antecedent]
                if conf >= min_conf:
                    rules.append((antecedent, {item}, conf))
    return rules

# 计算支持度数据
support_data = {}
for itemset in freq_items:
    support_data[frozenset(itemset)] = count_support(itemset, dataset)

# 生成关联规则
rules = generate_rules(freq_items, support_data, min_conf)

# 按置信度排序输出
rules.sort(key=lambda x: x[2], reverse=True)
for ante, conseq, conf in rules:
    print(f"{ante} => {conseq} 置信度: {conf:.2f}")

5. 性能优化与工程实践

在实际应用中，FP-Growth算法还需要考虑以下优化策略：

5.1 内存优化技巧

• 分块处理 ：当数据太大无法装入内存时，可以将数据集分块处理
• 投影数据库 ：只保留与当前挖掘相关的数据列
• 压缩存储 ：使用更高效的数据结构存储FP树

class CompactNode:
    __slots__ = ['name', 'count', 'nodeLink', 'parent', 'children']
    # 使用__slots__减少内存占用

5.2 并行化实现

FP-Growth的条件FP树生成天然适合并行处理：

from concurrent.futures import ThreadPoolExecutor

def parallel_mine(headerTable, min_support):
    with ThreadPoolExecutor() as executor:
        futures = []
        for item in headerTable:
            future = executor.submit(
                mine_conditional_tree, item, headerTable, min_support)
            futures.append(future)
        
        results = []
        for future in futures:
            results.extend(future.result())
    
    return results

5.3 实时更新策略

对于流式数据，可以采用以下策略维护FP树：

1. 滑动窗口 ：只保留最近N个事务的数据
2. 衰减计数 ：给旧事务的计数赋予较小权重
3. 增量更新 ：只更新受新事务影响的部分树结构

def update_fp_tree_incrementally(new_transactions, fp_tree, header_table, min_support):
    for trans in new_transactions:
        # 更新头表计数
        for item in trans:
            if item in header_table:
                header_table[item][0] += 1
            else:
                header_table[item] = [1, None]
        
        # 过滤非频繁项
        trans = [item for item in trans if header_table[item][0] >= min_support]
        trans.sort(key=lambda x: header_table[x][0], reverse=True)
        
        # 更新FP树
        update_tree(trans, fp_tree.root, header_table)
    
    # 清理不再频繁的项
    for item in list(header_table.keys()):
        if header_table[item][0] < min_support:
            del header_table[item]

6. 超越购物篮：FP-Growth的现代应用

FP-Growth算法早已不再局限于零售分析，它在诸多领域展现了强大的模式发现能力：

6.1 网络安全异常检测

通过分析网络日志中的事件共现模式，可以发现潜在的攻击特征：

# 示例网络日志数据
log_data = [
    ['登录失败', '密码尝试', '非常用IP'],
    ['登录失败', '密码尝试', '非常用IP', '异常时间'],
    ['权限提升', '新设备注册'],
    ['登录失败', '密码尝试']
]

# 挖掘频繁事件组合
fp_tree, header = create_fptree(log_data, min_support=2)
mine_fp_tree(header, min_support, set(), [])

6.2 医疗诊断辅助

分析病症与检查结果的关联，辅助诊断决策：

medical_records = [
    ['发热', '咳嗽', '肺炎'],
    ['头痛', '发热', '流感'],
    ['咳嗽', '呼吸困难', '肺炎'],
    ['头痛', '肌肉酸痛', '流感']
]

# 发现病症组合模式
patterns = find_frequent_patterns(medical_records, min_support=2)

6.3 金融反欺诈

识别欺诈交易中的特征组合模式：

transaction_features = [
    ['大额', '深夜', '跨境'],
    ['小额', '高频', '同商户'],
    ['大额', '新设备', '密码重置']
]

# 构建反欺诈特征规则
fraud_rules = generate_association_rules(transaction_features, min_support=2)

7. 算法对比与选型指南

当面临关联规则挖掘需求时，如何选择合适的算法？下表对比了主流算法的特性：

特性	Apriori	FP-Growth	Eclat
扫描数据库次数	多次	2次	2次
候选集生成	需要	不需要	不需要
内存使用	中等	较高	较低
适合数据集规模	中小型	中大型	中小型
实现复杂度	简单	中等	中等
并行化难度	较易	较难	中等

选择建议：

• 数据量小 ：Apriori简单直接
• 数据量大 ：FP-Growth效率更高
• 内存受限 ：Eclat可能是更好选择
• 需要实时更新 ：考虑FP-Growth的增量版本

FP-Growth特别适合以下场景：

• 事务数据库中存在大量共享前缀
• 需要快速发现长频繁模式
• 数据维度相对稳定，更新不频繁