首页 » 机器学习实战 » 机器学习实战全文在线阅读

《机器学习实战》11.1 关联分析

关灯直达底部

Apriori算法

优点:易编码实现缺点:在大数据集上可能较慢适用数据类型:数值型或者标称型数据

关联分析是一种在大规模数据集中寻找有趣关系的任务。这些关系可以有两种形式:频繁项集或者关联规则。频繁项集(frequent item sets)是经常出现在一块的物品的集合,关联规则(association rules)暗示两种物品之间可能存在很强的关系。下面会用一个例子来说明这两种概念。图11-1给出了某个杂货店的交易清单。

图11-1 一个来自Hole Foods天然食品店的简单交易清单

频繁项集是指那些经常出现在一起的物品集合,图11-1中的集合{葡萄酒,尿布, 豆奶}就是频繁项集的一个例子(回想一下,集合是由一对大括号“{ }”来表示的)。从下面的数据集中也可以找到诸如尿布 ➞葡萄酒的关联规则。这意味着如果有人买了尿布,那么他很可能也会买葡萄酒。使用频繁项集和关联规则,商家可以更好地理解他们的顾客。尽管大部分关联规则分析的实例来自零售业,但该技术同样可以用于其他行业,比如网站流量分析以及医药行业。

尿布与啤酒?

关联分析中最有名的例子是“尿布与啤酒”。据报道,美国中西部的一家连锁店发现,男人们会在周四购买尿布和啤酒。这样商店实际上可以将尿布与啤酒放在一块,并确保在周四全价销售从而获利。当然,这家商店并没有这么做*。

* DSS News, “Ask Dan! What is the true story about data mining, beer and diapers?” http://www.dssresources.com/newsletters/66.php, retrieved March 28, 2011.

应该如何定义这些有趣的关系?谁来定义什么是有趣?当寻找频繁项集时,频繁(frequent)的定义是什么?有许多概念可以解答上述问题,不过其中最重要的是支持度和可信度。

一个项集的支持度(support)被定义为数据集包含该项集的记录比例。从图11-1中可以得到,{豆奶}的支持度为4/5。而在5条交易记录中有3条包含{豆奶,尿布},因此{豆奶,尿布}的支持度为3/5。支持度是针对项集来说的,因此可以定义一个最小支持度,而只保留满足最小支持度的项集。

可信度或置信度(confidence)是针对一条诸如{尿布} ➞ {葡萄酒}的关联规则来定义的。这条规则的可信度被定义为“支持度({尿布, 葡萄酒})/支持度({尿布})”。从图11-1中可以看到,由于{尿布, 葡萄酒}的支持度为3/5,尿布的支持度为4/5,所以“尿布 ➞ 葡萄酒”的可信度为3/4=0.75。这意味着对于包含“尿布”的所有记录,我们的规则对其中75%的记录都适用。

支持度和可信度是用来量化关联分析是否成功的方法。假设想找到支持度大于0.8的所有项集,应该如何去做?一个办法是生成一个物品所有可能组合的清单,然后对每一种组合统计它出现的频繁程度,但当物品成千上万时,上述做法非常非常慢。下一节会详细分析这种情况并讨论Apriori原理,该原理会减少关联规则学习时所需的计算量。