4、Apriori算法原理（上）：频繁项集的概念、Apriori先验性质、算法核心思想

4.1 从购物篮说起：什么是频繁项集？

我们先从一个最简单的场景开始。你想想看，超市收银台每天会打出成千上万张小票。每张小票上，都记录着顾客买了什么。

比如这张小票：{牛奶, 面包, 鸡蛋}。另一张小票：{牛奶, 尿布, 啤酒}。

那么问题来了——哪些商品组合经常一起出现？

这就是频繁项集要回答的问题。所谓项集，就是一组商品的集合。比如{牛奶, 面包}就是一个2项集，{牛奶, 面包, 鸡蛋}就是一个3项集。

那什么叫频繁呢？说白了，就是某个项集在数据集中出现的次数足够多。这个“足够多”我们用支持度来衡量。

我们通常会设定一个最小支持度阈值，比如0.1（10%）。凡是支持度大于等于这个阈值的项集，就叫做频繁项集。

嗯，这里要注意：频繁项集是关联规则挖掘的第一步，也是最关键的一步。后面的关联规则，都是从频繁项集里推导出来的。

4.2 一个朴素的想法：为什么不能暴力枚举？

你可能会想：这还不简单？把所有可能的商品组合都算一遍支持度，不就行了？

我刚开始学数据挖掘时也是这么想的。直到我在一个项目中，面对一个只有100种商品的超市数据集……

100种商品，所有可能的组合有多少？2的100次方减1，大约是1.27乘以10的30次方。这个数字有多大？比宇宙中的星星还多。你算到天荒地老也算不完。

这就是所谓的组合爆炸问题。暴力枚举在现实中完全不可行。

那怎么办？我们需要一个聪明的算法，能剪枝——也就是提前砍掉那些明显不可能是频繁项集的组合。

4.3 Apriori先验性质：算法的核心武器

Apriori算法之所以高效，靠的就是一条非常简单的性质。我管它叫“一票否决制”。

举个例子：假设{牛奶, 面包}这个2项集的支持度只有5%，低于我们的最小支持度阈值10%。那么{牛奶, 面包, 鸡蛋}这个3项集，支持度只会更低，绝不可能是频繁的。

为什么会这样？你想想看：包含{牛奶, 面包, 鸡蛋}的订单，一定也包含{牛奶, 面包}。所以前者的支持度不可能大于后者。这是数学上铁板钉钉的事。

4.4 算法核心思想：逐层搜索与剪枝

基于上面的先验性质，Apriori算法的核心思想可以概括为四个字：逐层搜索。

具体来说，算法是这样干的：

1. 先找1项集：扫描所有订单，统计每个商品出现的次数，找出所有频繁1项集。
2. 由1项集生成2项集：把频繁1项集两两组合，生成候选2项集。
3. 剪枝：利用先验性质，砍掉那些包含非频繁子集的候选2项集。
4. 扫描数据库：计算剩下的候选2项集的支持度，找出频繁2项集。
5. 重复：由频繁k项集生成候选(k+1)项集，剪枝，扫描，直到无法生成新的频繁项集为止。

这个过程，我习惯把它想象成“筛沙子”。每一层筛子只保留足够大的颗粒，小的直接扔掉。越往下，筛子越细，留下的颗粒越少。

4.5 一个具体的例子：手把手走一遍流程

光说理论太抽象。我们来看一个具体的例子。假设有5笔订单：

订单ID	购买商品
1	牛奶, 面包, 鸡蛋
2	牛奶, 尿布, 啤酒, 鸡蛋
3	面包, 尿布, 啤酒
4	牛奶, 面包, 尿布, 啤酒
5	面包, 鸡蛋

设最小支持度阈值为 0.4（也就是至少出现2次）。

第一步：找频繁1项集

统计每个商品出现的次数：

• 牛奶：3次（订单1,2,4）→ 支持度 3/5 = 0.6 ✅
• 面包：4次（订单1,3,4,5）→ 支持度 0.8 ✅
• 鸡蛋：3次（订单1,2,5）→ 支持度 0.6 ✅
• 尿布：3次（订单2,3,4）→ 支持度 0.6 ✅
• 啤酒：3次（订单2,3,4）→ 支持度 0.6 ✅

所有商品都是频繁的。频繁1项集：{牛奶}, {面包}, {鸡蛋}, {尿布}, {啤酒}

第二步：生成候选2项集

两两组合，得到10个候选：{牛奶,面包}, {牛奶,鸡蛋}, {牛奶,尿布}, {牛奶,啤酒}, {面包,鸡蛋}, {面包,尿布}, {面包,啤酒}, {鸡蛋,尿布}, {鸡蛋,啤酒}, {尿布,啤酒}

第三步：剪枝

这一步，所有候选2项集的子集都是频繁1项集，所以没有需要剪掉的。全部保留。

第四步：扫描数据库，计算支持度

我们算几个关键的：

• {牛奶,面包}：出现在订单1和4 → 2次，支持度 0.4 ✅
• {牛奶,鸡蛋}：出现在订单1和2 → 2次，支持度 0.4 ✅
• {牛奶,尿布}：出现在订单2和4 → 2次，支持度 0.4 ✅
• {牛奶,啤酒}：出现在订单2和4 → 2次，支持度 0.4 ✅
• {面包,鸡蛋}：出现在订单1和5 → 2次，支持度 0.4 ✅
• {面包,尿布}：出现在订单3和4 → 2次，支持度 0.4 ✅
• {面包,啤酒}：出现在订单3和4 → 2次，支持度 0.4 ✅
• {鸡蛋,尿布}：只出现在订单2 → 1次，支持度 0.2 ❌
• {鸡蛋,啤酒}：只出现在订单2 → 1次，支持度 0.2 ❌
• {尿布,啤酒}：出现在订单2,3,4 → 3次，支持度 0.6 ✅

频繁2项集：{牛奶,面包}, {牛奶,鸡蛋}, {牛奶,尿布}, {牛奶,啤酒}, {面包,鸡蛋}, {面包,尿布}, {面包,啤酒}, {尿布,啤酒}

第五步：生成候选3项集

从频繁2项集中，找出前k-1个元素相同的进行合并。比如{牛奶,面包}和{牛奶,鸡蛋}可以合并成{牛奶,面包,鸡蛋}。

候选3项集：{牛奶,面包,鸡蛋}, {牛奶,面包,尿布}, {牛奶,面包,啤酒}, {牛奶,鸡蛋,尿布}, {牛奶,鸡蛋,啤酒}, {牛奶,尿布,啤酒}, {面包,鸡蛋,尿布}, {面包,鸡蛋,啤酒}, {面包,尿布,啤酒}

第六步：剪枝

检查每个候选3项集的所有2项子集是否都在频繁2项集中。

比如{牛奶,面包,鸡蛋}的子集有：{牛奶,面包}✅, {牛奶,鸡蛋}✅, {面包,鸡蛋}✅ → 全部在，保留。

比如{牛奶,鸡蛋,尿布}的子集有：{牛奶,鸡蛋}✅, {牛奶,尿布}✅, {鸡蛋,尿布}❌ → {鸡蛋,尿布}不在频繁2项集中，剪掉！

经过剪枝，剩下的候选3项集：{牛奶,面包,鸡蛋}, {牛奶,面包,尿布}, {牛奶,面包,啤酒}, {牛奶,尿布,啤酒}, {面包,尿布,啤酒}

第七步：扫描数据库，计算支持度

• {牛奶,面包,鸡蛋}：出现在订单1 → 1次，支持度 0.2 ❌
• {牛奶,面包,尿布}：出现在订单4 → 1次，支持度 0.2 ❌
• {牛奶,面包,啤酒}：出现在订单4 → 1次，支持度 0.2 ❌
• {牛奶,尿布,啤酒}：出现在订单2和4 → 2次，支持度 0.4 ✅
• {面包,尿布,啤酒}：出现在订单3和4 → 2次，支持度 0.4 ✅

频繁3项集：{牛奶,尿布,啤酒}, {面包,尿布,啤酒}

第八步：生成候选4项集

从频繁3项集中尝试合并。{牛奶,尿布,啤酒}和{面包,尿布,啤酒}的前2个元素不同，无法合并。所以没有候选4项集，算法结束。

4.6 小结：Apriori的精髓

回顾一下，Apriori算法的核心就两件事：

• 生成候选集：由频繁k项集生成候选(k+1)项集
• 剪枝：利用先验性质，提前砍掉不可能频繁的候选集

我个人觉得，Apriori最妙的地方就在于这个“先验性质”。它用一条简单的逻辑，解决了组合爆炸的大问题。虽然现在有更快的算法（比如FP-Growth），但Apriori的思想依然是关联规则挖掘的基石。

下一节，我们会继续深入Apriori算法，看看如何从频繁项集中提取出真正的关联规则，以及如何用置信度和提升度来评估规则的质量。到时候我会分享一个我在电商项目中踩过的坑——关于置信度的陷阱，保证让你印象深刻。