从大规模数据集中寻找物品间的隐含关系被称作关联分析(association analysis) 或者 关联规则学习(association rule learning)
关联分析是在大规模数据集中寻找有趣关系的任务。这些关系可以有两种形式：
- 频繁项集(frequent item sets): 是经常出现在一块儿的物品的集合
- 关联规则(association rules): 暗示两种物品之间可能存在很强的关系
假设目前宠物商店的交易系统中一下表中的几张顾客购物清单
表1 顾客购物清单
| 交易订单号 | 顾客购物清单 |
|---|---|
| 001 | 鸟、鸟笼、鸟食、猫粮、猫砂 |
| 002 | 鱼食、鸟、鸟笼 |
| 003 | 猫粮、狗粮、宠物玩具 |
| 004 | 鸟、鸟笼、鸟食 |
| 005 | 猫粮、猫砂、宠物玩具 |
频繁项集是指那些经常在一起出现的商品的集合，如表1中的集合{葡萄酒,尿布,豆奶}就是一个频繁项集的例子。从这数据集中也可以找到诸如 尿布->葡萄酒的关联规则，即如果有人买尿布，那么他可能也会买葡萄球。
这里用 支持度(Support) 和 置信度或者可信度(Confidence) 来度量这个关系。
一个项集的支持度被定义数据集中包含该项集的记录所占的比例。如表1中，{豆奶}的支持度是4/5，{豆奶，尿布}的支持度是3/5。支持度是针对项集来说的，因此可以定义一个最小支持度，而只保留满足最小支持度的项集。
置信度是针对关联规则来定义的。规则{尿布}->{葡萄酒}的置信度被定义为“支持度({尿布,葡萄酒})/支持度({尿布})”，即P(A|B)=P(AB)/P(B)。 由于{尿布,葡萄酒}的支持度为3/5，尿布的支持度为4/5，所以"尿布➞啤酒"的置信度为3/4。这意味着对于包含"尿布"的所有记录，我们的规则对其中75%的记录都适用。
是最常用的关联规则挖掘算法。Apriori原理是说如果某个项集是频繁的，那么它的所有子集也是频繁的。更常用的是它的逆否命题，即如果一个项集是非频繁的，那么它的所有超集也是非频繁的。
我们的目标是利用过去顾客已购买商品的历史信息作为参考，推荐他们可能感兴趣的其他商品。
因此在这里，宠物商店的管理者经过仔细考虑和讨论，确定只要一个商品组合的购买比例占到订单交易笔数的40%（即支持度），即可认为该商品组合中的商品集合是具有较强的购买关联性。 因此，如果顾客在购物篮中加入了组合其中的一种商品，则系统就会立刻将组合中的其他商品推荐给顾客。
下面模拟Apriori算法完成这项工作：
（1）计算单项商品的频繁项集L[1]
首先要找到单项商品的候选商品频繁项集C[1]，然后过滤掉其中支持度小于40%的商品频繁项集从而得到L[1]，如表2所示。
表2 计算频繁项集L[1]
| 商品频繁项集C[1] | 存在的交易订单号 | 支持度 | 是够保留该商品 |
|---|---|---|---|
| 鸟 | 001，002，004 | 3/5 x 100% > 40% | 是 |
| 鸟笼 | 001，002，004 | 3/5 x 100% > 40% | 是 |
| 鸟食 | 001，004 | 2/5 x 100% = 40% | 是 |
| 猫粮 | 001，003，005 | 3/5 x 100% > 40% | 是 |
| 猫砂 | 001，005 | 2/5 x 100% = 40% | 是 |
| 鱼食 | 002 | 1/5 x 100% < 40% | 否 |
| 狗粮 | 003 | 1/5 x 100% < 40% | 否 |
| 宠物玩具 | 003,005 | 2/5 x 100% = 40% | 是 |
得到频繁项集L[1] = {{鸟}，{鸟笼}，{鸟食}，{猫粮}，{猫砂}，{宠物玩具}}。
（2）根据频繁项集L[1]生成候选频繁项集C[2]
顾名思义。C[2]即为商品数量为2的候选频繁项集，它是由单品频繁项集L[1]中的频繁项集两两组合而来的，这里直接给出结果。 得到候选频繁项集C[2] = {{鸟，鸟笼}，{鸟，鸟食}，{鸟，猫粮}，{鸟，猫砂}，{鸟，宠物玩具}，{鸟笼，鸟食}，{鸟笼，猫粮}，{鸟笼，猫砂}，{鸟笼，宠物玩具}，{鸟食，猫粮}，{鸟食，猫砂}，{鸟食，宠物玩具}，{猫粮，猫砂}，{猫粮，宠物玩具}，{猫砂，宠物玩具}}。
（3）计算单项商品频繁项集L[2] 利用候选频繁项集C[2]进行计算，过滤掉支持度小于40%的商品频繁项集得到L[2]，如表3所示。
表3 计算频繁项集L[2]
| 商品频繁项集C[2] | 存在的交易订单号 | 支持度 | 是否保留该商品 |
|---|---|---|---|
| 鸟，鸟笼 | 001，002，004 | 3/5 x 100% > 40% | 是 |
| 鸟，鸟食 | 001，004 | 2/5 x 100% = 40% | 是 |
| 鸟，猫粮 | 001 | 1/5 x 100% < 40% | 否 |
| 鸟，猫砂 | 001 | 1/5 x 100% < 40% | 否 |
| 鸟，宠物玩具 | 无 | 0/5 x 100% < 40% | 否 |
| 鸟笼，鸟食 | 001，004 | 2/5 x 100% = 40% | 是 |
| 鸟笼，猫粮 | 001 | 1/5 x 100% < 40% | 否 |
| 鸟笼，猫砂 | 001 | 1/5 x 100% < 40% | 否 |
| 鸟笼，宠物玩具 | 无 | 0/5 x 100% < 40% | 否 |
| 鸟食，猫粮 | 001 | 1/5 x 100% < 40% | 否 |
| 鸟食，猫砂 | 001 | 1/5 x 100% < 40% | 否 |
| 鸟食，宠物玩具 | 无 | 0/5 x 100% < 40% | 否 |
| 猫粮，猫砂 | 001，005 | 2/5 x 100% = 40% | 是 |
| 猫粮，宠物玩具 | 003，005 | 2/5 x 100% = 40% | 是 |
| 猫砂，宠物玩具 | 005 | 1/5 x 100% < 40% | 否 |
得到频繁项集L[2] = {{鸟，鸟笼}，{鸟，鸟食}，{鸟笼，鸟食}，{猫粮，猫砂}，{猫粮，宠物玩具}}。
（4）根据频繁项集L[2]生成候选频繁项集C[3] 本步和第二步中C[2]的生成规则是一样的，这里强调一点，在Apriori算法中只允许差异为1的不同项集进行组合。
例如在本次计算C[3]的候选频繁项集时， {鸟，鸟笼}和{鸟，鸟食}之间是可以组合的，而{鸟，鸟笼}和{猫粮，猫砂}由于这两个频繁项集的差异为2（超过了一个元素），则不能进行组合。
得到候选频繁项集C[3] = {{鸟，鸟笼，鸟食}，{猫粮，猫砂，宠物玩具}}。
（5）计算单项商品频繁项集L[3]
表4 计算频繁项集L[3]
| 商品频繁项集C[3] | 存在的交易订单号 | 支持度 |
|---|---|---|
| 鸟，鸟笼，鸟食 | 001，004 | 2/5 x 100% = 40% |
| 猫粮，猫砂，宠物玩具 | 005 | 1/5 x 100% < 40% |
得到频繁项集L[3] = {{鸟，鸟笼，鸟食}}。
（6）循环终结条件及获得最终的商品频繁项集 由于C4应由L[3]中的频繁项集组合而来，但L[3]中目前已没有可供继续连接的频繁项集，因此循环到此结束。
根据Apriori算法，本例中最终的商品频繁项集为L[1] ∪ L[2] ∪ L[3] ={{鸟}，{鸟笼}，{鸟食}，{猫粮}，{猫砂}，{宠物玩具}，{鸟，鸟笼}，{鸟，鸟食}，{鸟笼，鸟食}，{猫粮，猫砂}，{猫粮，宠物玩具}，{鸟，鸟笼，鸟食}}。
根据本例中宠物商店的需求，对客户兴趣度有意义的商品关联数据为{鸟，鸟笼}，{鸟，鸟食}，{鸟笼，鸟食}，{猫粮，猫砂}，{猫粮，宠物玩具}，{鸟，鸟笼，鸟食}。因此，宠物商店可根据以上数据来进行商品推荐。
参考：