Question

如果有一些用户按照自己的喜爱程度对商品进行了评分，那么根据这些信息，我们就可以使用之前讨论的方法，取得不错的效果。然而我们有时无法得到这类信息。

购物篮分析 是学习推荐的另一种模式。在这种模式下，我们的数据只含有“哪些物品被一起购买”这样的信息，而不包含任何关于人们是否喜欢某件物品的信息。篮数据的生成是购物行为的一个副产品，通常这类数据比评分信息更容易获得，因为很多用户根本不会提供评分。下面是亚马逊网上War and Peace （LeTolstoy著）这本书的相关截图。这是使用这些结果的一种经典方式：

这种学习模式并不只适用于实际的购物篮。它适用于任何根据已有的多个对象推荐另一个对象的情况。例如，当用户正在Gmail里写电子邮件的时候，可以给他推荐更多的收件人。这个功能可以用类似的技术实现（我们并不知道Gmail内部用的是什么；或许它已经把前面介绍的多种技术融合在一起了）。或者，我们可以用这些方法开发出一个基于浏览历史的网页推荐应用。即使我们正在处理的是交易记录，把某个客户的交易信息分组到“物品是否被一同购买或来自不同交易”的独立篮子里（这取决于交易背景信息），也是有意义的。

注意　啤酒与尿布的故事

在购物篮分析中，一个经常会被提到的故事就是“尿布与啤酒”的故事。它是说，当超市工作人员第一次查看他们的数据的时候，他们发现尿布经常会和啤酒被一同购买。据推测，这是一些孩子的父亲，他们在超市里购买尿布的时候还会挑选一些啤酒。人们对这个假设到底是真实的，还是仅仅是一个城市故事，进行过很多讨论。在这个例子里，它好像是真实的。在20世纪90年代早期，OscDrug发现，在傍晚，啤酒和尿布会被一同购买，这令一些管理者们感到非常惊奇，他们直到那时也从未把这两样商品当做是相似的东西。这并不会导致商店把啤酒摆放在离尿布更近的地方。还有，我们也并不知道父亲到底会不会比母亲（或者祖父母）更容易同时购买啤酒和尿布。

8.2.1　获取有用的预测

并不仅仅是“购买了X的客户也会购买Y”，即便很多在线零售商都这样说（见前面给出的亚马逊网截图）；一个真实系统并不是这样工作的。为什么不是呢？因为这样的系统会被购买频率比较高的物品所愚弄，然后只会简单推荐那些流行的物品，而不带有任何个性化。

例如，在一个超市里，很多客户都购买了面包（比如50%的客户买了面包）。所以，当你关注任何特定物品（比如肥皂），并看哪些物品会经常跟肥皂一起出售的时候，你或许会发现，面包是经常跟肥皂一起出售的。事实上，在某人购买肥皂次数的五成里，他们也同时购买了面包。但是，面包其实会和任何东西一起出售，因为每个人都经常购买面包。

我们真正要寻找的是“相比基准，在统计上更可能购买Y的购买了X的客户 ”。所以如果你购买了肥皂，你可能还会购买面包，但没有比基准的可能性更大。类似的，一个书店如果不管你已经购买了什么书，而只是一味地推荐热销图书，那么它在个性化推荐上就没有做好。

8.2.2　分析超市购物篮

例如，我们来看一下比利时一家超市匿名交易记录的数据集。这个数据集是由哈瑟尔特大学（Hasselt University）的Tom Brijs 所提供的。里面的数据都是匿名的，所以对每个商品我们只有一个编号，而一个购物篮就是一组编号。该数据文件（retail.dat）可以从一些网上资源里（包括本书的网站）下载到。

从读取数据开始，并查看一些统计值：

from collections import defaultdict from itertools import chain # 文件格式是每行一个交易记录 # 形式如“12 34 342 5…” dataset = [[int(tok) for tok in ,line.strip().split()] for line in open('retail.dat')] # 统计每件商品被购买了多少次 counts = defaultdict(int) for elem in chain(*dataset): counts[elem] += 1

我们可以画出如下所述的柱状图：

# 购买次数	# 产品个数
只有1次	2224
2次或3次	2438
4到7次	2508
8到15次	2251
16到31次	2182
32到63次	1940
64到127次	1523
128到511次	1225
512次或更多	179

有很多商品只被购买过几次。例如，有33%的商品只出售过4次或更少次数。然而，这个数量只代表了1%的购买量。这种很多商品只被购买过少数几次的现象，有时称作“长尾”现象。由于互联网让囤积和销售商品更为廉价，这种现象也变得越来越突出。为了能为这些商品提供推荐，我们需要更多的数据。

虽然网上有一些购物篮分析算法的开源实现，但没有一个能很好地整合scikit-learn或其他我们正在使用的程序库。因此，我们将会自己实现一个经典算法，那就是Apriori 算法。它有一点年头了（由Rakesh Agrawal 和Ramakrishnan Srikant 发表于1994年），但仍然能够工作（当然，算法永远都不会停止工作；它们只会被更好的想法取代）。

在形式上，Apriori会将一些集合（这里指的是购物篮）当做输入，并返回这些集合中出现频率非常高的子集（这是说，一起出现在很多购物篮中的商品）。

这个算法是以自底向上的方式工作的：从最小的候选集合开始（只包含一个元素），然后每次加入一个元素，并且不断增大。在这里我们需要定义一下我们所要寻找的最小支持度：

minsupport = 80

支持度就是商品被一起购买的次数。Apriori的目标就是寻找一个高支持度的项集（itemset）。从逻辑上讲，任何具有最小支持度的项集，里面每个物品都至少具有该最小支持度：

valid = set(k for k,v in counts.items() if (v >= minsupport))

我们的初始项集是单例（只有一个元素）。而频繁项集就是所有至少具有最小支持度的单例：

itemsets = [frozenset([v]) for v in valid]

现在遍历非常简单，如下所示：

new_itemsets = [] for iset in itemsets: for v in valid: if v not in iset: # 我们创建一个新的候选集合 # 它和之前的一样 # 只是多了v newset = (ell|set([v_])) # 在数据集中遍历，并统计newset出现的次数 # 这一步比较慢 # 并没有使用较好的实现 c_newset = 0 for d in dataset: if d.issuperset(c): c_newset += 1 if c_newset > minsupport: newsets.append(newset)

这样做是正确的，但速度很慢。一个更好的实现需要利用更多的基础设施，以便避免在所有数据集中遍历来统计c_newset 。值得一提的是，我们可以追踪哪些购物篮包含哪些频繁项集。这将使循环加速，但会让代码更加难懂。因此，我们就不在这里给出了。像往常一样，你可以在本书的网站上找到这两种实现。那段代码还被包含在一个函数里，可以应用于其他数据集。

Apriori算法所返回的频繁项集，就是一些没有用任何具体数值来量化（代码中的minsupport ）的微小购物篮。

8.2.3　关联规则挖掘

频繁项集本身并不是很有用处。下一步是构建关联规则 （association rule）。由于这是最终目标，因此整个购物篮分析领域有时又叫做关联规则挖掘 （association rule mining）。

一个关联规则就是形如“如果X则Y”这样的一种陈述；例如，如果顾客购买了War and Peace ，那么他们还会购买Anna Karenina 。 注意，规则并不是确定性的（并不是所有顾客购买了X之后都会购买Y），总把这些都陈述出来也是相当麻烦的。所以，关联规则的意思是说，如果一个顾客购买了X，相对于基线，他将更可能购买Y；我们所说的“如果X则Y ”，是从概率意义上说的。

有趣的是，规则的前项和结论是可以包含多个对象的：购买X、Y和Z的顾客还购买了A、B和C。多前项的条件可以允许你做出更为具体的预测。

你可以通过尝试所有可能的X蕴含Y组合，从频繁集合中得到一条规则。要生成很多集合是很容易的。然而，你想要的只是有价值的规则。因此，我们需要衡量每个规则的价值。一个经常使用的衡量标准叫做提升度 （lift）。提升度就是规则和基线所得到的概率之间的比值：

在前面这个公式里，P （Y ）就是所有交易记录中包含Y 的比例，而P (Y |X )就是交易记录中同时包含Y 和X 的比例。使用提升度可以帮你避免推荐热销商品；对于一个热销商品，P (Y )和P (X |Y )都会很大。因此，如果提升度接近1，那么这条规则就会被认为是很不相关的。在实践中，我们希望这个值至少是10，或甚至是100。

参考下面这段代码：

def rules_from_itemset(itemset, dataset): itemset = frozenset(itemset) nr_transactions = float(len(dataset)) for item in itemset: antecendent = itemset-consequent base = 0.0 # account : 前项的计数 acount = 0.0 # ccount : 后项的计数 ccount = 0.0 for d in dataset: if item in d: base += 1 if d.issuperset(itemset): ccount += 1 if d.issuperset(antecedent): acount += 1 base /= nr_transactions p_y_given_x = ccount/acount lift = p_y_given_x / base print('Rule {0} -> {1} has lift {2}' .format(antecedent, consequent,lift))

这是一段运行得比较慢的代码：我们在整个数据集上重复迭代。一个更好的实现方式是把统计值缓存起来。你可以从本书的网站上下载到一个类似的代码，它的运行速度相对快一点。

其中一些结果在下面这个表中列出：

前项	后项	后项的计数	前项的计数	前项和后项的计数	提升度
1378、13791、1380	1269	279（0.3%）	80	57	255
48、41、976	117	1026（1.1%）	122	51	35
48、41、16011	16010	1316（1.5%）	165	159	64

这里的计数就是交易次数，它们包括如下几项：

条件后项（这是说，商品被购买的基准比例）；

条件前项中的所有项；

条件前项和后项中的所有项。

我们可以看到，例如，在80个交易中，1378、13791和1380被一起购买。在这当中，有57个交易包含1269，所以估算出的条件概率就是57/80≈71%。与所有交易中只有0.3%包含1269这个事实相比，它得到了255的提升度。

我们在计数中需要有相当多的交易记录，才能得到相对稳固的推论。这就是必须首先挑选频繁项集的缘故。如果从一个非频繁项集中生成规则，那么这些计数将会非常小；因此，这个相对数值便会毫无意义（或者受到大误差线的影响）。

注意，从这个数据集里已经找到了很多关联规则；一共有1030个规则，具有最小支持度80以及最小提升度5。和现在的互联网比起来，这仍然是一个小规模数据集；当你进行上百万次交易的时候，你可以生成成千上万甚至百万的规则。

然而，具体到每一个客户，在任何时间里都只有一小部分是跟他们有关的，所以每个客户只会收到少量推荐信息。

8.2.4　更多购物篮分析的高级话题

在购物篮分析中还有很多其他算法要比Apriori运行得更快。我们之前看到的代码比较简单，但对我们而言已经足够好了，因为我们大约只有10万个交易数据。如果你有上百万的数据，那么就值得使用更快的算法（尽管对多数应用来说，学习关联规则的过程可以在线下运行）。

还有一些方法会利用时间信息，把购买的顺序也考虑进来。可以用一个极端例子来解释这样做的用处。比如某人正在购买一个大型聚会所需的用品，买完聚会用品后，他可能会意识到还要买一些垃圾袋。因此如果在他第一次购物的时候就给他提供垃圾袋，这是说得通的。但是，为每个购买垃圾袋的人都提供聚会用品，却是毫无道理的。

你可以在Python开源实现（一种新的BSD许可证，跟Scikit-learn一样）中找到一个叫做pymining 的程序包。这个包是由Barthelemy Dagenais 开发的，在https://github.com/bartdag/pymining 可以获取到。