一、真实场景：电商购物篮分析翻车现场

2023年双11后，运营要求分析「用户购买手机后，7天内最常一起买什么配件」。我直接用Apriori跑全量数据（50万订单，每单平均3.2个商品），最小支持度设0.01，结果跑了2小时没出结果。最后发现：数据稀疏导致频繁项集几乎为空，改设0.001后，跑出「手机→手机壳」支持度0.0003，但置信度98%。运营说这结论没用——谁不知道买手机要配壳？

这个坑让我重新审视Apriori：不是算法不行，是参数和场景没匹配好。本文用PHP8.3 + MySQL8.0.35，从零实现Apriori和FP-Growth，对比性能，并给出避坑清单。

二、问题定义：序列模式挖掘要解决什么

给定交易数据库D，每条交易t包含一组商品（项集）。频繁项集挖掘目标是找出所有出现次数≥最小支持度阈值min_sup的项集。关联规则A→B表示：购买A的用户也购买B，用支持度（A和B同时出现的概率）和置信度（购买A的用户中购买B的比例）衡量。

核心挑战：数据量越大，候选集爆炸。Apriori用先验性质（频繁项集的所有非空子集也必须是频繁的）剪枝，但需要多次扫描数据库。FP-Growth用FP树压缩数据，只需两次扫描。

三、方案对比：Apriori vs FP-Growth

3.1 Apriori算法原理

步骤：
1. 扫描数据库，统计每个项的支持度，得到频繁1-项集L1。
2. 连接步：Lk-1自连接生成候选k-项集Ck。
3. 剪枝步：删除Ck中包含非频繁子集的候选。
4. 扫描数据库，计算Ck中每个候选的支持度，得到Lk。
5. 重复2-4直到Ck为空。

时间复杂度：O(2^n)，n为项数。空间复杂度：O(C(n,k))。

3.2 FP-Growth算法原理

步骤：
1. 第一次扫描数据库，统计频繁1-项集，按支持度降序排列。
2. 第二次扫描，构建FP树：每条交易按排序后的频繁项插入树中，共享前缀路径。
3. 从FP树挖掘频繁项集：从支持度最低的频繁项开始，构建条件模式基，递归挖掘。

时间复杂度：O(n)，n为交易总数。空间复杂度：O(树节点数)。

四、完整代码实现

4.1 环境准备

# PHP8.3 + MySQL8.0.35
# 安装PDO扩展
sudo apt install php8.3-mysql
# 创建测试数据库
mysql -u root -p -e "CREATE DATABASE apriori_test;"

4.2 数据表结构

-- 订单表
CREATE TABLE orders (
    order_id INT PRIMARY KEY,
    user_id INT,
    created_at DATETIME
);

-- 订单商品明细表
CREATE TABLE order_items (
    id INT AUTO_INCREMENT PRIMARY KEY,
    order_id INT,
    product_id INT,
    product_name VARCHAR(100),
    FOREIGN KEY (order_id) REFERENCES orders(order_id)
);

-- 生成测试数据：10万订单，每单1-10个商品
INSERT INTO orders (order_id, user_id, created_at)
SELECT seq, FLOOR(RAND()*10000), NOW() - INTERVAL FLOOR(RAND()*365) DAY
FROM seq_1_to_100000;

INSERT INTO order_items (order_id, product_id, product_name)
SELECT o.order_id, 
       FLOOR(RAND()*1000) + 1 AS product_id,
       CONCAT('Product_', FLOOR(RAND()*1000) + 1) AS product_name
FROM orders o
CROSS JOIN seq_1_to_10 s
WHERE s.seq <= FLOOR(RAND()*10) + 1;

4.3 Apriori PHP实现

pdo = $pdo;
        $this->minSupport = $minSupport;
        $this->minConfidence = $minConfidence;
    }
    
    /**
     * 从数据库加载交易数据
     */
    public function loadTransactions(int $limit = 100000): void {
        $stmt = $this->pdo->prepare("
            SELECT o.order_id, GROUP_CONCAT(oi.product_id ORDER BY oi.product_id) AS items
            FROM orders o
            JOIN order_items oi ON o.order_id = oi.order_id
            GROUP BY o.order_id
            LIMIT :limit
        ");
        $stmt->bindParam(':limit', $limit, PDO::PARAM_INT);
        $stmt->execute();
        
        while ($row = $stmt->fetch(PDO::FETCH_ASSOC)) {
            $this->transactions[] = explode(',', $row['items']);
        }
    }
    
    /**
     * 获取频繁项集
     */
    public function getFrequentItemsets(): array {
        $totalTransactions = count($this->transactions);
        $minCount = ceil($totalTransactions * $this->minSupport);
        
        // 统计单个项的支持度
        $itemCounts = [];
        foreach ($this->transactions as $transaction) {
            foreach ($transaction as $item) {
                $itemCounts[$item] = ($itemCounts[$item] ?? 0) + 1;
            }
        }
        
        // 过滤得到频繁1-项集
        $frequentItems = [];
        foreach ($itemCounts as $item => $count) {
            if ($count >= $minCount) {
                $frequentItems[$item] = $count;
            }
        }
        
        // 按项ID排序
        ksort($frequentItems);
        $frequentItemsets = [];
        $currentLevel = array_keys($frequentItems);
        
        // 迭代生成更大项集
        $k = 1;
        while (!empty($currentLevel)) {
            // 记录当前层频繁项集
            foreach ($currentLevel as $itemset) {
                $itemsetArr = explode(',', $itemset);
                sort($itemsetArr);
                $key = implode(',', $itemsetArr);
                $frequentItemsets[$key] = $itemCounts[$key] ?? 0;
            }
            
            // 生成候选集
            $candidates = $this->generateCandidates($currentLevel);
            if (empty($candidates)) break;
            
            // 剪枝：删除包含非频繁子集的候选
            $candidates = $this->pruneCandidates($candidates, $currentLevel);
            if (empty($candidates)) break;
            
            // 计算候选集支持度
            $candidateCounts = [];
            foreach ($this->transactions as $transaction) {
                $transactionSet = array_unique($transaction);
                sort($transactionSet);
                $transactionStr = implode(',', $transactionSet);
                
                foreach ($candidates as $candidate) {
                    $candidateArr = explode(',', $candidate);
                    if ($this->isSubset($candidateArr, $transactionSet)) {
                        $candidateCounts[$candidate] = ($candidateCounts[$candidate] ?? 0) + 1;
                    }
                }
            }
            
            // 过滤得到下一层频繁项集
            $nextLevel = [];
            foreach ($candidateCounts as $candidate => $count) {
                if ($count >= $minCount) {
                    $nextLevel[] = $candidate;
                    $itemCounts[$candidate] = $count;
                }
            }
            
            $currentLevel = $nextLevel;
            $k++;
        }
        
        return $frequentItemsets;
    }
    
    /**
     * 生成候选k+1-项集
     */
    private function generateCandidates(array $frequentItemsets): array {
        $candidates = [];
        $n = count($frequentItemsets);
        
        for ($i = 0; $i < $n; $i++) {
            $itemset1 = explode(',', $frequentItemsets[$i]);
            for ($j = $i + 1; $j < $n; $j++) {
                $itemset2 = explode(',', $frequentItemsets[$j]);
                
                // 检查前k-1项是否相同
                $prefix1 = array_slice($itemset1, 0, -1);
                $prefix2 = array_slice($itemset2, 0, -1);
                
                if ($prefix1 === $prefix2) {
                    // 合并生成新候选
                    $newItemset = array_merge($itemset1, [end($itemset2)]);
                    sort($newItemset);
                    $candidates[] = implode(',', $newItemset);
                }
            }
        }
        
        return array_unique($candidates);
    }
    
    /**
     * 剪枝：删除包含非频繁子集的候选
     */
    private function pruneCandidates(array $candidates, array $frequentItemsets): array {
        $frequentSet = array_flip($frequentItemsets);
        $pruned = [];
        
        foreach ($candidates as $candidate) {
            $items = explode(',', $candidate);
            $valid = true;
            
            // 检查所有k-1子集是否频繁
            for ($i = 0; $i < count($items); $i++) {
                $subset = $items;
                array_splice($subset, $i, 1);
                sort($subset);
                $subsetKey = implode(',', $subset);
                
                if (!isset($frequentSet[$subsetKey])) {
                    $valid = false;
                    break;
                }
            }
            
            if ($valid) {
                $pruned[] = $candidate;
            }
        }
        
        return $pruned;
    }
    
    /**
     * 检查数组A是否是数组B的子集
     */
    private function isSubset(array $a, array $b): bool {
        return count(array_intersect($a, $b)) === count($a);
    }
    
    /**
     * 生成关联规则
     */
    public function generateRules(array $frequentItemsets): array {
        $rules = [];
        $totalTransactions = count($this->transactions);
        
        foreach ($frequentItemsets as $itemset => $supportCount) {
            $items = explode(',', $itemset);
            if (count($items) < 2) continue;
            
            // 生成所有非空真子集作为前件
            $subsets = $this->getAllSubsets($items);
            
            foreach ($subsets as $antecedent) {
                $consequent = array_diff($items, $antecedent);
                if (empty($consequent)) continue;
                
                sort($antecedent);
                sort($consequent);
                $antecedentKey = implode(',', $antecedent);
                $consequentKey = implode(',', $consequent);
                
                // 计算置信度
                $antecedentSupport = $frequentItemsets[$antecedentKey] ?? 0;
                if ($antecedentSupport === 0) continue;
                
                $confidence = $supportCount / $antecedentSupport;
                
                if ($confidence >= $this->minConfidence) {
                    $rules[] = [
                        'antecedent' => $antecedentKey,
                        'consequent' => $consequentKey,
                        'support' => $supportCount / $totalTransactions,
                        'confidence' => $confidence,
                        'lift' => $confidence / ($frequentItemsets[$consequentKey] / $totalTransactions)
                    ];
                }
            }
        }
        
        // 按置信度降序排列
        usort($rules, function($a, $b) {
            return $b['confidence'] <=> $a['confidence'];
        });
        
        return $rules;
    }
    
    /**
     * 获取数组的所有非空真子集
     */
    private function getAllSubsets(array $items): array {
        $subsets = [];
        $n = count($items);
        
        for ($i = 1; $i < (1 << $n) - 1; $i++) {
            $subset = [];
            for ($j = 0; $j < $n; $j++) {
                if ($i & (1 << $j)) {
                    $subset[] = $items[$j];
                }
            }
            $subsets[] = $subset;
        }
        
        return $subsets;
    }
}

// 使用示例
$pdo = new PDO('mysql:host=127.0.0.1;dbname=apriori_test;charset=utf8mb4', 'root', 'password');
$pdo->setAttribute(PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION);

$apriori = new Apriori($pdo, 0.01, 0.6);
$apriori->loadTransactions(10000);

$startTime = microtime(true);
$frequentItemsets = $apriori->getFrequentItemsets();
$endTime = microtime(true);

echo "频繁项集数量: " . count($frequentItemsets) . PHP_EOL;
echo "耗时: " . round($endTime - $startTime, 2) . "秒" . PHP_EOL;

$rules = $apriori->generateRules($frequentItemsets);
echo "关联规则数量: " . count($rules) . PHP_EOL;
foreach (array_slice($rules, 0, 10) as $rule) {
    echo "{$rule['antecedent']} -> {$rule['consequent']} (支持度: {$rule['support']}, 置信度: {$rule['confidence']})" . PHP_EOL;
}

4.4 FP-Growth PHP实现

item = $item;
            $this->count = 1;
            $this->parent = $parent;
            $this->next = null;
        }
    }
    
    public function __construct(PDO $pdo, float $minSupport = 0.01, float $minConfidence = 0.5) {
        $this->pdo = $pdo;
        $this->minSupport = $minSupport;
        $this->minConfidence = $minConfidence;
    }
    
    public function loadTransactions(int $limit = 100000): void {
        $stmt = $this->pdo->prepare("
            SELECT o.order_id, GROUP_CONCAT(oi.product_id ORDER BY oi.product_id) AS items
            FROM orders o
            JOIN order_items oi ON o.order_id = oi.order_id
            GROUP BY o.order_id
            LIMIT :limit
        ");
        $stmt->bindParam(':limit', $limit, PDO::PARAM_INT);
        $stmt->execute();
        
        while ($row = $stmt->fetch(PDO::FETCH_ASSOC)) {
            $this->transactions[] = explode(',', $row['items']);
        }
    }
    
    /**
     * 构建FP树
     */
    private function buildFPTree(array $transactions, array $headerTable): FPNode {
        $root = new FPNode('root');
        
        foreach ($transactions as $transaction) {
            // 过滤非频繁项并按支持度降序排列
            $filtered = [];
            foreach ($transaction as $item) {
                if (isset($headerTable[$item])) {
                    $filtered[] = $item;
                }
            }
            usort($filtered, function($a, $b) use ($headerTable) {
                return $headerTable[$b]['count'] <=> $headerTable[$a]['count'];
            });
            
            // 插入树中
            $currentNode = $root;
            foreach ($filtered as $item) {
                if (!isset($currentNode->children[$item])) {
                    $newNode = new FPNode($item, $currentNode);
                    $currentNode->children[$item] = $newNode;
                    
                    // 更新头表链表
                    $newNode->next = $headerTable[$item]['node'];
                    $headerTable[$item]['node'] = $newNode;
                } else {
                    $currentNode->children[$item]->count++;
                }
                $currentNode = $currentNode->children[$item];
            }
        }
        
        return $root;
    }
    
    /**
     * 从FP树挖掘频繁项集
     */
    private function mineFPTree(FPNode $node, array $prefix, array &$frequentItemsets, int $minCount): void {
        // 从头表底部开始处理
        $headerItems = array_keys($this->headerTable);
        rsort($headerItems); // 按支持度降序排列，从最低的开始
        
        foreach ($headerItems as $item) {
            $newPrefix = array_merge($prefix, [$item]);
            sort($newPrefix);
            $key = implode(',', $newPrefix);
            
            // 计算条件模式基的支持度
            $supportCount = 0;
            $currentNode = $this->headerTable[$item]['node'];
            while ($currentNode !== null) {
                $supportCount += $currentNode->count;
                $currentNode = $currentNode->next;
            }
            
            if ($supportCount >= $minCount) {
                $frequentItemsets[$key] = $supportCount;
                
                // 构建条件模式基
                $conditionalPatterns = [];
                $currentNode = $this->headerTable[$item]['node'];
                while ($currentNode !== null) {
                    $path = [];
                    $parent = $currentNode->parent;
                    while ($parent !== null && $parent->item !== 'root') {
                        $path[] = $parent->item;
                        $parent = $parent->parent;
                    }
                    if (!empty($path)) {
                        $path = array_reverse($path);
                        for ($i = 0; $i < $currentNode->count; $i++) {
                            $conditionalPatterns[] = $path;
                        }
                    }
                    $currentNode = $currentNode->next;
                }
                
                if (!empty($conditionalPatterns)) {
                    // 递归挖掘条件FP树
                    $conditionalHeader = $this->buildHeaderTable($conditionalPatterns, $minCount);
                    if (!empty($conditionalHeader)) {
                        $conditionalTree = $this->buildFPTree($conditionalPatterns, $conditionalHeader);
                        $this->mineFPTree($conditionalTree, $newPrefix, $frequentItemsets, $minCount);
                    }
                }
            }
        }
    }
    
    /**
     * 构建头表
     */
    private function buildHeaderTable(array $transactions, int $minCount): array {
        $itemCounts = [];
        foreach ($transactions as $transaction) {
            foreach ($transaction as $item) {
                $itemCounts[$item] = ($itemCounts[$item] ?? 0) + 1;
            }
        }
        
        $headerTable = [];
        foreach ($itemCounts as $item => $count) {
            if ($count >= $minCount) {
                $headerTable[$item] = ['count' => $count, 'node' => null];
            }
        }
        
        // 按支持度降序排列
        uksort($headerTable, function($a, $b) use ($headerTable) {
            return $headerTable[$b]['count'] <=> $headerTable[$a]['count'];
        });
        
        return $headerTable;
    }
    
    /**
     * 获取频繁项集
     */
    public function getFrequentItemsets(): array {
        $totalTransactions = count($this->transactions);
        $minCount = ceil($totalTransactions * $this->minSupport);
        
        // 第一次扫描：统计项支持度
        $itemCounts = [];
        foreach ($this->transactions as $transaction) {
            foreach ($transaction as $item) {
                $itemCounts[$item] = ($itemCounts[$item] ?? 0) + 1;
            }
        }
        
        // 构建头表
        $this->headerTable = $this->buildHeaderTable($this->transactions, $minCount);
        
        // 构建FP树
        $fpTree = $this->buildFPTree($this->transactions, $this->headerTable);
        
        // 挖掘频繁项集
        $frequentItemsets = [];
        $this->mineFPTree($fpTree, [], $frequentItemsets, $minCount);
        
        return $frequentItemsets;
    }
    
    /**
     * 生成关联规则（与Apriori相同）
     */
    public function generateRules(array $frequentItemsets): array {
        // 实现与Apriori相同，略
        return [];
    }
}

// 使用示例
$fpGrowth = new FPGrowth($pdo, 0.01, 0.6);
$fpGrowth->loadTransactions(10000);

$startTime = microtime(true);
$frequentItemsets = $fpGrowth->getFrequentItemsets();
$endTime = microtime(true);

echo "FP-Growth频繁项集数量: " . count($frequentItemsets) . PHP_EOL;
echo "FP-Growth耗时: " . round($endTime - $startTime, 2) . "秒" . PHP_EOL;

五、效果数据对比

测试环境：Intel i7-12700H, 32GB DDR5, PHP8.3, MySQL8.0.35, 数据量10万订单。

结论：FP-Growth在性能上碾压Apriori，尤其当支持度阈值降低时。但Apriori实现简单，适合小数据集（<1万订单）或教学场景。

六、避坑指南

坑1：最小支持度设置不当

问题：设0.01，结果频繁项集只有单个商品，没有组合。设0.001，结果全是「手机→手机壳」这种常识规则。

解决方案：先用统计方法确定合理阈值。计算所有商品的平均出现频率，取中位数作为初始值。对于稀疏数据（每单商品数少），支持度应设低（0.001-0.005）；对于稠密数据（每单商品数多），设高（0.01-0.05）。

坑2：数据稀疏导致候选集爆炸

问题：10万订单，每单平均3个商品，但商品种类1000种。Apriori在k=3时候选集达到C(1000,3)=1.6亿，内存直接爆。

解决方案：
- 对商品做聚类或分类，先挖掘类别级规则，再深入具体商品。
- 限制最大项集大小（如k≤5）。
- 使用FP-Growth替代Apriori。

坑3：关联规则太多，无法落地

问题：最小置信度0.6，生成8932条规则，运营根本看不过来。

解决方案：
- 引入提升度（Lift）过滤：只保留Lift>1的规则（正相关）。
- 按业务价值排序：例如只关注高客单价商品的关联。
- 使用Kulczynski度量或不平衡比（Imbalance Ratio）过滤冗余规则。

坑4：时间序列被忽略

问题：Apriori只考虑「同时购买」，不考虑「先后顺序」。但实际场景中，用户先买手机，3天后才买手机壳。

解决方案：
- 使用序列模式挖掘算法（如GSP、PrefixSpan），考虑时间窗口。
- 在数据预处理阶段，按用户ID和时间排序，将同一用户7天内的购买合并为一条序列。

坑5：性能优化不到位

问题：PHP实现Apriori，10万订单跑47秒，但线上要求实时推荐（<1秒）。

解决方案：
- 离线挖掘：每天凌晨跑一次，结果存入Redis。
- 增量更新：只处理新增订单，用FP-Growth的增量版本。
- 改用C++/Go实现核心算法，PHP只做API调用。

七、总结

Apriori是关联规则挖掘的经典算法，但实战中必须注意数据稀疏性、参数调优和性能瓶颈。FP-Growth是更好的工程选择。无论用哪种，都要先理解业务场景：是发现常识（手机→手机壳）还是挖掘隐藏关联（啤酒→尿布）。

最后，别迷信算法。我见过最成功的案例是：运营手动分析1000条订单，发现「购买高端奶粉的用户，80%也买了婴儿湿巾」，然后直接上架组合套餐，转化率提升15%。算法只是工具，业务洞察才是核心。