第2章
关联规则挖掘
在数据挖掘工具箱中，计量某个模式的频率是一项关键任务。在某些情况下，较频繁出现的模式可能最终成为更加重要的模式。如果我们可以发现经常同时出现的两个或者三个项目，就更为有趣了。
在本章中，我们开始研究频繁项集，然后将其扩展为称作关联规则的一类模式。我们将介绍如下主题：
什么是频繁项集？使用哪些技术找出频繁项集？瓶颈在哪里？如何加速这一过程？
如何将频繁项集扩展为关联规则？
什么是好的关联规则？我们将根据数据库中的支持程度、对规则本身的置信度以及我们找出的规则所增加的价值，学习描述特定关联规则的价值。
为此，我们将编写一个程序，在关于一组软件项目的元数据（事实）公开数据集中寻找频繁项集。然后，学习在用于描述那些项目的标记中寻找频繁项集。接着，将学习通过计算数据库支持度，然后增加概率导向（X蕴含Y）置信区间，将频繁项集扩展为关联规则。最后，将学习如何解读关联规则。具体地说，我们应该理解关联规则说明以及没有说明的情况。
2.1 什么是频繁项集
寻找频繁项集是一种计数活动。但是和从生成数据集中观测到的项目的简单计数（今天我们卖出了80个胡萝卜和100个马铃薯）相比，寻找频繁项集稍有不同。确切地说，为了找出频繁项集，我们要搜索较大的组中共同出现的项集。有时候可以把这些较大的组视为超市交易或者购物篮，整个活动有时候称为市场篮子分析。我们仍然采用超市的类比，在这些篮子中同时出现的物品有时候被视为在超市中购买的产品组合。例如，已知一组超市交易或者篮子，我们可能对篮子中{胡萝卜，马铃薯}的组合是否比{黄瓜、柠檬}的组合更频繁出现感兴趣。
频繁项集挖掘的目的是发现一组交易中共同出现的有趣项目组合。换言之，如果我们发现某些组合在多个篮子中频繁出现，则这种挖掘可能很有实用价值。如果我们发现的频繁项集有些不同寻常或者有些意外，那就更加有趣了。在频繁项集挖掘中令人满意的有趣规则的典范是一再被传颂的都市传奇—“尿布与啤酒”。
2.1.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.1.2 频繁项集挖掘基础知识
出于我们的目的，我们将把尿布和啤酒的故事当做一个有用的隐喻。具体地说，我们可以使用这个故事中的术语，帮助定义市场篮子分析（或者频繁项集挖掘）中的3个突出部分：
首先，为了进行市场篮子分析，我们需要一个市场。在这个隐喻中，市场就是真正的超市。
其次，我们需要一个篮子。在这个例子中，篮子是一次购物交易。有时候，我们使用“篮子”一词，有时候，你也可能听到“交易”一词。
我们还需要商品（项目）。在这个隐喻中，为了购买要把零售商品放入篮子（或者交易）中。
只要我们有市场、篮子和商品的概念，只要这些东西的表现和我们所描述的相同，我们就很可能有一个可供挖掘频繁项集的数据集。
但是，市场分析的故事中还埋藏着几个假设，这些假设将影响我们是否能够拥有可挖掘的数据集。所以，现在要明确这些假设：
商品和篮子之间应该是多对多的关系。篮子由许多商品组成，一件商品可以出现在许多篮子中。
不考虑商品的数量。不管购买的是6包尿布还是1包尿布，相关的事实都是篮子中有尿布。
某件商品可能不出现在任何一个篮子中（我确定大家都想到了不受欢迎的某一件商品），但是任何篮子都包含至少一件商品。空的篮子是不会让人感兴趣的！
篮子中商品的顺序无关紧要。从这个隐喻的角度看，啤酒或者尿布哪一个先放进购物篮并不重要，哪一个放到传送带上、哪一个先进入收银机也是如此。相反，我们将把购买的商品组合起来，比喻成一次交易或者一个篮子，而不管它们在篮子中的位置。
在市场篮子分析的这个阶段，我们最感兴趣的是找出频繁项集，也就是在篮子中频繁同时出现的项目组。在超市中，人们同时购买的某些商品组合很容易用常识猜出，但是有些组合则较为少见。蛋糕粉和糖霜是可预测的商品组合，但是啤酒和尿布这种组合则不同寻常。
有时候，某些组合因为天气、假日或者地区偏好而比其他组合更可能出现。和任何数据挖掘活动一样，重要的是理解你所研究的领域。在购物篮的例子中，由于不同的食物偏好，可能有广泛的地区性差异。例如：
我生活在美国南部，我们商店中有许多在其他地区不太常见的有趣组合。例如，人们常常同时购买香草威化饼干和橡胶，以便制作流行的甜食香蕉布丁。
在我所在的州，新年的常见食物包括豇豆（一种荚果）和羽衣甘蓝（一种叶菜），所以在接近年底时包含这些商品的篮子可能增加。
我所住的地方很少下雪。每当天气预报报告本地区将要下雪，人们都很惊慌，抢购商店中的所有牛奶和面包。虽然不管什么天气，牛奶和面包都是人们经常购买的商品，但是在下雪的日子里，你可能发现牛奶和面包是更常见的频繁项集。
我们可以用集合标记符表示这些项集：
有两个项目的项集称为2-项集或配对，有3个项目的项集称为3-项集（或者三元组），以此类推。有时候，配对和三元组分别称为“双个体集”和“三个体集”。