导读：大数据相关行业的研究者和从业者都知道这样一个“都市传奇”：
美国中西部的一家连锁超市的数据挖掘团队发现，周四下午5点～7点，男人们频繁地购买尿布和啤酒。该商店将一个小的尿布陈列柜移到啤酒通道中，结果两种产品的销售量同时飙升。
也有很多人对这个“传奇”的真实性表示怀疑，但如今看来，这个传奇已经并不神奇，它只是通过频繁项集进行数据挖掘的一个典型案例而已。
作者：梅甘·斯夸尔
如需转载请联系大数据（ID：hzdashuju）
在数据挖掘工具箱中，计量某个模式的频率是一项关键任务。在某些情况下，较频繁出现的模式可能最终成为更加重要的模式。如果我们可以发现经常同时出现的两个或者三个项目，就更为有趣了。
在本文中，我们开始研究频繁项集，然后将其扩展为称作关联规则的一类模式。我们将介绍如下主题：
- 什么是频繁项集？使用哪些技术找出频繁项集？瓶颈在哪里？如何加速这一过程？
- 如何将频繁项集扩展为关联规则？
- 什么是好的关联规则？我们将根据数据库中的支持程度、对规则本身的置信度以及我们找出的规则所增加的价值，学习描述特定关联规则的价值。
01 什么是频繁项集
寻找频繁项集是一种计数活动。但是和从生成数据集中观测到的项目的简单计数（今天我们卖出了80个胡萝卜和100个马铃薯）相比，寻找频繁项集稍有不同。确切地说，为了找出频繁项集，我们要搜索较大的组中共同出现的项集。
有时候可以把这些较大的组视为超市交易或者购物篮，整个活动有时候称为市场篮子分析。我们仍然采用超市的类比，在这些篮子中同时出现的物品有时候被视为在超市中购买的产品组合。
例如，已知一组超市交易或者篮子，我们可能对篮子中{胡萝卜，马铃薯}的组合是否比{黄瓜、柠檬}的组合更频繁出现感兴趣。
频繁项集挖掘的目的是发现一组交易中共同出现的有趣项目组合。换言之，如果我们发现某些组合在多个篮子中频繁出现，则这种挖掘可能很有实用价值。如果我们发现的频繁项集有些不同寻常或者有些意外，那就更加有趣了。
在频繁项集挖掘中令人满意的有趣规则的典范是一再被传颂的都市传奇——“尿布与啤酒”。
1. 都市传奇“尿布与啤酒”
我记得第一次听到这个故事是在1998年的一个数据挖掘研究生课程上。我的教授试图解释频繁项集和关联规则的实用性，他给我们班上的学生讲了如下故事：
中西部的一家连锁超市欲挖掘频繁项集，以便发现一同购买的有趣商品组合。他们的计划是通过在商店中将这些产品放在一起，优化销售业绩。令他们高兴的是，商店的数据挖掘团队发现，周四下午5点～7点，男人们频繁地购买尿布和啤酒。该商店将一个小的尿布陈列柜移到啤酒通道中，结果两种产品的销售量同时飙升。
我对这个故事表示怀疑，立刻提出了许多问题。
这家商店是如何知道男人购买了这些东西？毕竟，这个故事发生的时候，商店的电子优惠卡或者奖励卡尚未出现。
这家商店怎么可能选择合适的尿布放入啤酒通道中间的小展示柜？毕竟，尿布有5种不同的尺寸，至少有3种品牌，而且（我像一位初为人父的男人一样快速学习）——一时兴起地更换某种尺寸或者品牌不是好主意，那可能会带来灾难性的后果。
其他许多人也表示怀疑，有些人甚至试图追寻这一都市传奇的历史。最好的研究范例包括Dan Powers的新闻稿《DSS Resources》，2001年11月10日的那一期（第3卷第23号）专门描写了寻找这个故事真正来源的经过。
这篇引人入胜的文章的链接：
http://www.dssresources.com/newsletters/66.php
此后，英国的《The Register》于2006年也讲述了一个关于这个都市传奇的故事。
链接：
http://www.theregister.co.uk/ 2006/08/15/beer_diapers
如果你相信这两篇文章讲述的细节，尿布与啤酒的故事则是说明早期数据挖掘可能性的一个示例：使用我们的数据库产品，你可以查询像尿布和啤酒这样不寻常的模式！
这一示例以某种方式扩展成了这个“真实发生”的故事，此后又随着事实的延伸，加入各种不同的细节及讲述者的不同动机而演变成一个都市传奇。在多年的传颂中，这个故事的常见变种包括：
- 沃尔玛进行了这项数据挖掘工作。
- 零售商利用发现的知识，在周四这天提高啤酒的价格。
- 购买啤酒的动机是作为照顾孩子的报酬（购买尿布想必是为了孩子）。
- 零售商对这些模式特别感兴趣，因为尿布是有利可图的商品。
实际上，这一故事的真相并不神奇，但是作为一个励志案例它一直很受欢迎。如果你对频繁项集或者关联规则挖掘进行了研究，就会明白市场篮子分析在现实世界中应用的这个故事是个很恰当的例子。关于关联规则的几乎每本书、每篇文章和每次演示都用到了它。
2. 频繁项集挖掘基础知识
出于我们的目的，我们将把尿布和啤酒的故事当做一个有用的隐喻。具体地说，我们可以使用这个故事中的术语，帮助定义市场篮子分析（或者频繁项集挖掘）中的3个突出部分：
- 首先，为了进行市场篮子分析，我们需要一个市场。在这个隐喻中，市场就是真正的超市。
- 其次，我们需要一个篮子。在这个例子中，篮子是一次购物交易。有时候，我们使用“篮子”一词，有时候，你也可能听到“交易”一词。
- 我们还需要商品（项目）。在这个隐喻中，为了购买要把零售商品放入篮子（或者交易）中。
只要我们有市场、篮子和商品的概念，只要这些东西的表现和我们所描述的相同，我们就很可能有一个可供挖掘频繁项集的数据集。
但是，市场分析的故事中还埋藏着几个假设，这些假设将影响我们是否能够拥有可挖掘的数据集。所以，现在要明确这些假设：
- 商品和篮子之间应该是多对多的关系。篮子由许多商品组成，一件商品可以出现在许多篮子中。
- 不考虑商品的数量。不管购买的是6包尿布还是1包尿布，相关的事实都是篮子中有尿布。
- 某件商品可能不出现在任何一个篮子中（我确定大家都想到了不受欢迎的某一件商品），但是任何篮子都包含至少一件商品。空的篮子是不会让人感兴趣的！
- 篮子中商品的顺序无关紧要。从这个隐喻的角度看，啤酒或者尿布哪一个先放进购物篮并不重要，哪一个放到传送带上、哪一个先进入收银机也是如此。相反，我们将把购买的商品组合起来，比喻成一次交易或者一个篮子，而不管它们在篮子中的位置。
在市场篮子分析的这个阶段，我们最感兴趣的是找出频繁项集，也就是在篮子中频繁同时出现的项目组。在超市中，人们同时购买的某些商品组合很容易用常识猜出，但是有些组合则较为少见。蛋糕粉和糖霜是可预测的商品组合，但是啤酒和尿布这种组合则不同寻常。
有时候，某些组合因为天气、假日或者地区偏好而比其他组合更可能出现。和任何数据挖掘活动一样，重要的是理解你所研究的领域。在购物篮的例子中，由于不同的食物偏好，可能有广泛的地区性差异。例如：
- 我生活在美国南部，我们商店中有许多在其他地区不太常见的有趣组合。例如，人们常常同时购买香草威化饼干和橡胶，以便制作流行的甜食香蕉布丁。
- 在我所在的州，新年的常见食物包括豇豆（一种荚果）和羽衣甘蓝（一种叶菜），所以在接近年底时包含这些商品的篮子可能增加。
- 我所住的地方很少下雪。每当天气预报报告本地区将要下雪，人们都很惊慌，抢购商店中的所有牛奶和面包。虽然不管什么天气，牛奶和面包都是人们经常购买的商品，但是在下雪的日子里，你可能发现牛奶和面包是更常见的频繁项集。
我们可以用集合标记符表示这些项集：
有两个项目的项集称为2-项集或配对，有3个项目的项集称为3-项集（或者三元组），以此类推。有时候，配对和三元组分别称为“双个体集”和“三个体集”。
02 迈向关联规则
频繁项集的内容都很好，但是我们的终极目标是关联规则，那更激动人心。关联规则是从频繁项集中经过一些小曲折形成的。我们对如下关于频繁项集的陈述感兴趣：购买香草威化的人有60%的可能性同时购买香蕉。
换言之，我们需要学习如何计算几个附加指标，首先是被称为“支持度”和“置信度”的两个指标。
1. 支持度
如果你打算寻找频繁项集，那么还需要一种表示在篮子中看到这些组合出现的频繁程度以及这个数量是否可称为“频繁”的手段。如果我看到90%的篮子中有{香草威化，香蕉}这样的组合，可以认为是频繁的吗？50%的篮子呢？5%呢？我们称这一数字为项集的支持度。支持度就是在所有篮子中看到项集的次数。
为了使支持度更有意义，再来谈论“兴趣度”，我们必须设置最小支持阈值。最小支持阈值是对问题领域有意义的百分比（0%～100%）。如果我们将最小支持阈值设置为5%，就意味着如果在所有篮子中至少有5%能发现该项集，则视其为频繁项集。
2-项集的支持度通常用概率标记法书写：
换言之，我们可以将上式读成“X->Y的支持度等于同时包含X和Y的篮子的百分比”。
在本例中，项目X可能是香草威化，Y可能是香蕉。为了计算项集的支持度，我们统计同时包含这两种商品的篮子数量，将结果除以篮子总数。如果项集的支持度超过最小支持阈值，则我们认为该项集可能是有用的。
2. 置信度
一旦发现了频繁项集，我们就可以开始考虑项集中的一个或者多个项目是否引发其他项目的购买。例如，知道在购物篮里放入香草威化的顾客中，有75%的人同时购买香蕉，这是很有用的。
但是，另一方面，在购物篮中包含香蕉的客户中，可能只有1%的人将购买香草威化。为什么？这是因为购买香蕉的人比购买香草威化的人多得多。香蕉较为常见，而香草威化则较为少见。所以，购买关系的方向不一定是对称的。
这就引出了一个关键的概念——置信度。有向关系的置信度写作：
我们可以将上式读成“X导致Y的置信度为已知X的情况下Y的概率”。或者用另一种方式书写为：
X->Y的置信度是同时包含X和Y的篮子的百分比除以只包含X的篮子百分比。
一旦有了支持度和置信度，我们就可以开始将频繁项集扩展为关联规则了。
3. 关联规则
既然我们已经知道如何确定某个项集是否频繁出现，也知道如何设置支持度和置信度，就可以从频繁项集中建立可能的关联规则。
下面是关联规则的一个例子：
香草威化->香蕉，生奶油 [支持度＝1%，置信度＝40%]
我们可以将这条规则读作：在所有篮子中，有1%包含香草威化、香蕉和生奶油的组合；在购买香草威化的客户中，有40%同时购买了香蕉和生奶油。
规则的左侧是确定项，称作先导。右侧是结果项，称作后继。如果我们切换左侧和右侧的项目，则必须计算不同的关联规则，由于香蕉很受欢迎，得到的规则可能是：
香蕉->香草威化，生奶油 [支持度＝0.001%，置信度＝10%]
4. 包含数据的示例
想象我们拥有一家商店，且有下表所示的10个商品篮子。你马上就可以看出有人为的痕迹，因为这家商店中的所有篮子都正好有3件商品，这在真实的商店中不太可能出现。
首先，我们需要计算商店中所有单独商品的支持度。在这10个篮子中共有9种商品：
为了简化例子，我们现在只考虑频繁项集{香草威化，香蕉}。该项集的支持度是同时包含香草威化和香蕉的篮子的百分比。数据中有4个篮子（1、4、7、9）同时包含这两项。因此，香草威化->香蕉或者香蕉->香草威化这两条规则的支持度都是40%，因为10个篮子中有4个同时包含两者。
现在，我们可以使用这些支持度计算提议的两条关联规则的置信度：
香草威化->香蕉 香蕉->香草威化 置信度（香草威化->香蕉）＝支持度（香草威化U香蕉）/支持度（香草威化）＝4/6＝67% 置信度（香蕉->香草威化）＝支持度（香草威化U香蕉）/支持度（香蕉）＝4/8＝50%
写成关联规则，可以得到：
香草威化->香蕉[支持度＝40%，置信度＝67%] 香蕉->香草威化[支持度 ＝40%，置信度＝50%] 规则“香草威化->香蕉”强于（支持度相同，置信度更高）规则“香蕉->香草威化”。
5. 附加值——修复计划中的漏洞
香草威化->香蕉[s＝40%，c＝67%]这样的规则是引人注目、令人满意的。但是，这是一个非常小的数据集，只是为了举例而人为制作的。在某些情况下，关联规则可能很容易引起误导，我们应该小心为之。考虑下面的例子。
想象在一家不同的商店中，香草威化和香蕉的支持度可能是这样的：
- {香草威化}：50%
- {香蕉}：80%
- {香草威化，香蕉}：30%
在这种情况下，商品的单独支持度相当高，但是商品组合的支持度较低。
在这个例子中，香草威化->香蕉的置信度为0.3/0.8＝37.5%。
有什么问题呢？有些商品自身的表现好于作为关联规则后继时的表现。即使规则符合某些最小支持阈值，我们也必须考虑商品在规则之外的表现。
为此，我们计算一个称作关联规则附加值的测度。香草威化->香蕉规则的附加值通过从规则置信度减去香蕉的支持度计算。如果附加值是大的正数，那么规则是好的、有用的。如果附加值接近于0，则这条规则可能是正确的，但是没太大用处。如果附加值是大的负数，那么规则中的商品实际上是负相关的，这时单独使用表现会更好。
我们这样计算附加值：
附加值＝规则置信度-右侧的支持度
使用上表，可以计算出：
- 规则置信度＝0.375
- 右侧（香蕉）的支持度＝0.8
- 附加值＝0.375―0.8＝―0.425
这个数字告诉我们，实际上香蕉自己的表现更好。而且，我们提出的将香蕉展示柜移到香草威化旁边的建议可能是个错误，因为利用香蕉和威化之间关系的尝试没有任何收益。
我们可以稍微改变一下数据，人为生成正面的有用规则：
- {香草威化}：50%
- {香蕉}：30%
- {香草威化，香蕉}：30%
现在，香草威化->香蕉的置信度为0.3/0.3=100%。
- 规则置信度＝1.0
- 香蕉的支持度＝0.3
- 附加值＝1―0.3＝0.7
在这种情况下，商店中的香蕉和香草威化应该放在一起，因为明显没有任何人将香蕉作为唯一商品购买！
计量关联规则兴趣度的方法还有很多，但是这超出了本文的范围。建议感兴趣的读者在谷歌学术上搜索介绍这一主题的最新论文。使用“关联规则兴趣度计量”等搜索词可以找到许多好的信息来源。在这些论文中，对于不同类型的数据和问题，有许多出色的“兴趣度”计量。
6. 寻找频繁项集的方法
目前，我们已经知道，寻找关联规则的基础是首先寻找频繁项集。此后，只需要根据之前找到的计数进行计算。
帮助我们更快找到频繁项集的一条重要原则称为向上闭包属性。向上闭包指的是，只有在项集的所有项目都频繁出现时，该项集才是频繁项集。换言之，如果项集中包含的项目不都是频繁出现的，则计算项集的支持度就毫无意义。
为什么了解闭包原则很重要？因为知道这一原则将节约许多计算可能项集的时间。在拥有数十万种商品的商店中计算每个可能项集的支持度明显不实际！尽可能减少项集的数量对我们绝对有好处。降低项集数量的策略之一是利用向上闭包减少项集数量，构建如下算法：
1）首先，设置一个支持阈值。
2）构建一个1-项集（单例）列表，该列表称为CandidateSingletonList：
- 为此，从每种可能项目的列表开始。这个列表称作CandidateSingletonList。
- 计算CandidateSingletonList中每个单独项目的支持度。
- 仅保留符合支持阈值的单例，并将其加入SingletonList列表。
3）构造一个2-项集列表（双个体集）：
- 为此，从SingletonList入手。
- 建立SingletonList中项目的所有可能配对的列表，这个列表称作Candidate-Doubleton-List。
- 仅保留符合支持阈值的候选二元组，将其添加到列表DoubletonList中。
4）构建3-项集（三个体集）列表：
- 为此，从DoubletonList入手。
- 建立DoubletonList中出现的每个可能单项的列表，将其与DoubletonList中的每个项目匹配，建立三元组。这个列表称为CandidateTripletonList。
- 仅保留符合支持阈值的候选三元组，将其添加到列表TripletonList中。
5）重复第4）步，用前面构建的列表中的单项生成n-项集，直到频繁项集用完。
这个算法称作Apriori算法，1994年Agarwal和Srikant的论文“Fast algorithms for mining association rules in large databases”（挖掘大型数据库中关联规则的快速算法）中率先概述了该算法。
从那时起，人们提出了许多其他算法，对其进行优化，包括利用并行性和更有趣数据结构（如树）的方法。还有用于特种篮子数据的算法；例如，我们的篮子中是有序的项目，或者篮子中包含分类或者层次数据。但是，对于基本的频繁项集生成，Apriori算法是经典的选择。
在实现Apriori算法之前，我们要特别关注生成候选项集的几条重要方针。虽然计算2-项集是很费时的，但这是整个过程中最为密集的工作了。由于前面提到的闭包属性，后续的数据可能构建的项集比之前更少。
本身，减少在二元组阶段需要比较的项目数量对我们肯定有利。为此，我们将设置一个最小支持阈值，但是这个阈值可以根据你所承担项目的需要进行调整。
本文摘编自《Python数据挖掘：概念、方法与实践》，经出版方授权发布。
