[啤酒与尿不湿]之关联规则

Posted by Qing on June 10, 2018

沃尔玛一家分店的营销经理对超市的销售数量进行设定跟踪,有一次他发现了一个>很奇怪的现象:啤酒与尿不湿的销量在周末总会出现成比例增长。他们立即对这个> 现象进行了分析和讨论,并且派出专门的人员在卖场内进行全天候的观察。他们发现这些顾客有几个共同的特点:

  • 一般是周末出现这种情况
  • 购买者以已婚男士为主
  • 他们家中有孩子且不到两岁,有尿不湿的刚需
  • 他们喜欢看体育比赛节目,并且喜欢边喝啤酒边看,顾客有喝啤酒的需求
  • 周末是体育比赛扎堆的日子,所以出现这种关联销售多在周末的时候

这位营销经理从中受到启发,他对超市的物品摆放进行了调整,将卖场内原来相隔很远的妇婴用品区与酒类饮料区的空间距离拉近,减少顾客的行走时间,将啤酒与尿不湿摆放在一起,同时将牛肉干等一些简便的下酒食品也摆放在一起,这样全年下来,营业额增加了几百万美元。

先不管这个故事的真实性与否,我们关心的能否利用以往的信息,发现某些特征中的联系,从而做出推荐,而实现这种推荐的算法,就是关联规则。

关联规则是反映一个事物与其他事物之间的相互依存性和关联性,常用于实体商店或在线电商的推荐系统:通过对顾客的购买记录数据库进行关联规则挖掘,最终目的是发现顾客群体的购买习惯的内在共性,例如购买产品A的同时也连带购买产品B的概率,根据挖掘结果,调整货架的布局陈列、设计促销组合方案,实现销量的提升,最经典的应用案例莫过《啤酒和尿布》。

基本概念

在讲解算法之前,先了解几个简单的概念:

  • 事务库(Transaction Database):存储着二维结构的记录集。定义为:D 就好比一份超市销售记录,列是商品ID,行是每个人的购买记录,每个格子中存的是这个人是否购买了该商品。
  • 事务(Transaction):在事务库里的某一笔事务。定义为:T,T ∈ D 举例来说就是某一位客户的购买记录。
  • 支持度(Support):定义为 ,反应规则的有用性。 比如啤酒的支持度为3%,意思就是在该资料库中有3%的顾客购买了啤酒。
  • 置信度(Confidence/Strength): 定义为 , 反应规则的确定性。例如C(啤酒->尿布)=40%,意思就是在购买啤酒的顾客中,有40%的人同时也购买了尿布。
  • 最小支持度阈值(Minimum Support):由用户定义衡量支持度的一个阈值,表示项目集统计意义上的最低重要性。
  • 项集(Itemset):项的集合称为项集。包含k个项的项集称为k-项集。集合{啤酒,尿布}是一个2项集,项集出现的频率是包含项集的事务数,简称支持度计数。
  • 频繁项集(frequent itemset):如果项集的支持度满足预定的最小支持度阈值,则是频繁项集。

一般而言,关联规则的挖掘是一个两步的过程:

  1. 找出所有的频繁项集:根据定义,这些项集的每一个项的出现概率至少与预定的最小支持度阈值一致。
  2. 由频繁项集产生强关联规则:根据定义,这些规则必须满足最小支持度和最小置信度。

那么假设我们现在有一个最小支持度和最小置信度,如何才能快速地找到所有满足阈值条件的规则呢?

Apriori算法

如果一个事务数据集中包含5个{a},{b},{c},{d},{e}不同的数据项,则该问题的解空间包含25个候选项集,如下图所示。

为了计算该解空间中每一个候选项集的支持度,Brute-force方法通过扫描事务数据集,将所有候选项集与事务逐一比较。如果事务中包含该候选项集,则增加候选项集的支持度。该过程如下图所示。

从而,可知Brute-force方法的时间复杂度约为O(NMw),其中N是事务数据集的大小,M是候选项集的数量,w是平均事务的长度。由于M=2k,k是数据项的数量,因此,该方法的时间复杂度是指数级别。这种方法效率太低,有没有其他效率更高的方法呢?

Apriori算法([‘eɪprɪ’ɔ:rɪ] adj. 先验的),是一种发现关联规则的基本算法,由Agrawal和R. Srikant于1994年提出的。正如其名字,该算法基于这样的事实:算法使用频繁项集性质的先验知识。Apriori算法利用以下两条定律实现快速挖掘频繁项集:

  • 如果一个集合是频繁项集,则它的所有子集都是频繁项集。举例:假设一个集合{A,B}是频繁项集,即A、B同时出现在一条记录的次数大于等于最小支持度,则它的子集{A},{B}出现次数必定大于等于最小支持度,即它的子集都是频繁项集。
  • 如果一个集合不是频繁项集,则它的所有超集都不是频繁项集。举例:假设集合{A}不是频繁项集,即A出现的次数小于最小支持度,则它的任何超集如{A,B}出现的次数必定小于最小支持度,因此其超集必定也不是频繁项集。

Apriori算法利用上述定律,使用一种称为逐层搜索的迭代方法,其中K项集用于搜索K+1项集,其核心步骤描述如下:

  1. 找出所有频繁1项集的集合,该集合记作L[1],令k=1;
  2. 连接步:在L[k]的基础上,通过向下合并得到候选k+1项集,记作C[k+1];
  3. 剪枝步:在C[k+1]中,任一项集的所有非空子集也必须是频繁的,剔除不符合的,得到L[k+1];
  4. 令k=k+1,重复2->3,直到不能生成更大的频繁集为止。

看起来有点抽象,下面举一个具体的例子。 有如下购物清单,假设最小支持度为30%:

顾客 购物清单
A 牛奶,面包,尿布
B 尿布,啤酒,面包
C 牛奶,面包,尿布
D 牛奶,尿布,面包,啤酒
E 牛奶,鸡蛋,可乐
F 啤酒,可乐

算法图解如下:

上面的图演示了Apriori算法的过程,注意看由二级频繁项集生成三级候选项集时,没有{牛奶,面包,啤酒},那是因为{面包,啤酒}不是二级频繁项集,这里利用了Apriori定理。最后生成三级频繁项集后,没有更高一级的候选项集,因此整个算法结束,{牛奶,面包,尿布}是最大频繁子集。由最后得到的频繁项集,可以通过组合子集得到对应的关联规则。

频繁模式增长(Frequent-Pattern Growth, FP-growth)

在许多情况下,Apriori算法的候选产生-检查方法显著压缩了候选项集的规模,并产生很好的性能。然而,它可能受两种非评分开销的影响:

  • 可能仍然需要产生大量候选项集。例如,如果有个频繁1项集,则Apriori算法需要产生多达个候选2项集。
  • 需要重复地扫描整个数据库。检查真个数据库中每个事务来确定候选集支持度的开销很大。

那么,可以设计一种方法,挖掘全部频繁项集而无需这种代价昂贵的候选产生过程吗?频繁模式增长(Frequent-Pattern Growth, FP-growth)就是这样一种比Apriori更高效的频繁项挖掘方法。它采取如下分治策略:

  • 首先,将代表频繁项集的数据库压缩到一颗频繁模式树(FP树),该树仍保留项集的关联信息。
  • 然后,把这种压缩后的数据库划分成一组条件数据库,每个数据库关联一个频繁项或“模式段”,并分布挖掘每个条件数据库。对于每个“模式片段”,只需靠察与它相关联数据集。

该算法只需要扫描项目表2次。其中第1次扫描获得当个项目的频率,去掉不符合支持度要求的项,并对剩下的项排序。第2遍扫描是建立一颗FP-Tree树。接下来的工作就是在FP-Tree上进行挖掘。 举个例子: 对应的FP-树如下: 这个算法的思路详见数据挖掘概念与技术这本书第6章,这里就不再赘述了。

规则评估方法

使用支持度-置信度框架可能会产生一些无趣甚至是误导的规则,强规则不一定是有趣的,比如下面的例子:

假设我们对分析涉及购买计算机和录像的事务感兴趣,设game表示包含计算机游戏的事务,而video表示包含路线的事务。在所分析的10000个事务中,数据显示6000个顾客事务包含计算机游戏,7500个事务包含录像,而4000个事务同时包含计算机游戏和录像。运用关联规则进行数据挖掘时,使用最小支持度30%,最小置信度60%,将发现以下关联规则:

规则是强关联规则,因为它的支持度为,置信度为。然而,规则是误导,因为购买录像的概率是75%,比66%还高,事实上,计算机游戏和录像是负相关的,因为买一种实际上降低了买另一种的可能性。

从关联分析到相关分析

支持度和置信度不足以过滤掉无趣的关联规则,为了处理这个问题,可以使用相关性度量来扩充评估方法。

提升度(lift)是一种简单的相关性度量,定义如下。项集A的出现独立于项集B的出现,如果;否则,项集A和B是依赖的和相关的,A和B的提升度可以通过计算下式得到:

如果上式的值小于1,则A的出现与B的出现是负相关的,意味着一个出现可能导致另一个不出现,如果结果大于1,则A和B是正相关的,意味着每一个的出现都蕴涵另一个的出现。如果结果等于1,则A和B是独立的,它们之间没有相关性。 提升度评估一个的出现“提升”另一个出现的程度。

除了使用提升度,还能用进行相关性的度量,统计分析得到的结果一般与提升度相一致。

全置信度、最大置信度、Kulczynski和余弦

使用更多的规则度量如全置信度、最大置信度、Kulczynski和余弦,常常可以揭示更多的模式内在联系。

全置信度(all confidence)

全置信度(A,B)又称两个关联规则“”和“”的最小置信度。

最大置信度(max confidence)

Kulczynski度量

它可看作是两个置信度的平均值。

余弦

余弦可以看作调和提升度度量。

上述4中度量都具有如下性质:

  • 度量值仅受支持度的影响,或者说是条件概率的影响,而不受事务总个数的影响
  • 每个度量值取值都在0~1之间,取值越大,A和B的联系越紧密

现在,加上提升度和,一共有6种统计评估度量,那么对于评估规则发现,哪个度量更好呢?下面在一个典型数据集上回答这个问题。


牛奶和咖啡两种商品的关系可以通过汇总在如下列联表中来考察:

~

下表使用不同数据集比较6种度量方法

数据集 提升度 全置信度 最大置信度 余弦
10000 1000 1000 100000 90557 9.26 0.91 0.91 0.91 0.91
10000 1000 1000 100 0 1 0.91 0.91 0.91 0.91
100 1000 1000 100000 670 8.44 0.09 0.09 0.09 0.09
1000 1000 1000 100000 24740 25.75 0.50 0.50 0.50 0.50
1000 100 10000 100000 8173 9.81 0.09 0.91 0.50 0.29
1000 10 100000 100000 965 1.97 0.01 0.99 0.50 0.10

新介绍的4个度量在这两个数据集上都产生了度量值0.91,显示m和c是强正关联的。然后,由于对敏感,提升度和产生了显著不同的度量值。事实上,在许多实际情况下,通常都很大并且不稳定。因此,好的度量不应该受不包含感兴趣项的事务影响,否则会产生不稳定的结果。

类似地,在,4个新度量都正确地表明m和c是强负相关的,因为mc和c之比等于mc与m之比,即100/1000=9.1%。然而,提升度和都错误地与此相悖。

“为什么提升度和识别上述事务数据集中的模式关联关系的能力这么差?”为了回答这个问题,我们必须考虑零事务。零事务(null-transaction)指的是不包含任何考察项集的事务。在上面的例子中,表示零事务的个数。提升度和很难识别有趣的模式关联关系,因为它们都受到的影响很大。例如,零事务可能大大超过个体购买的个数,因为,许多人既不购买牛奶也不购买咖啡。新的4个度量都是有趣的模式关联很好的指示器,因为它们的定义消除了的影响。如果一个度量值独立于零事务的个数,我们称其具有零不变性,在上面的6种度量种,只有提升度和不是零不变度量。

对于发现关联规则,全置信度、最大置信度、Kulczynski和余弦哪个最好? 这里引进“不平衡比(Imbalance Ratio, IR)”,评估规则蕴涵式种两个项集A和B的不平衡程度,它定义为:

比值越大,不平衡比就越大。这个比率独立于零事务的个数,也独立于事务的总数。

考察数据集。对于,有,表明数据具有很好的平衡性;对于,有,是一种很不平衡的情况;对于,有,是一种很不平衡的情况,因此,在中,两个度量Kluc和IR一起,对数据提供了清晰的度量。

总之,仅使用支持度和置信度来挖掘关联规则可能产生大量规则,其中大部分规则是用户不感兴趣的。我们可以用附加的度量减少所产生规则的数量,除了这里介绍的一些度量方法外,文献里面还有许多其他的度量方法。由于大型数据集常常具有许多零事务,因此在进行相关分析选择合适的兴趣度量时,考虑零不变性是非常重要的。这里提到的4个零不变的度量(全置信度、最大置信度、Kulczynski和余弦),数据挖掘概念与技术的作者推荐Kluc与不平衡比配合使用。

使用SAS进行关联分析

SAS发布的Visual Data Mining and Machine Learning on SAS Viya能够很方便的进行关联分析,并进行数据可视化。 下面以如下数据进行演示,这个数据记录着一家超市在过去一年内的购买记录。Customer是交易ID,Time是购买量, Product 是购买的物品. 想要直接进行分析,数据的存储必须是纵向的——每个人每次商品一行。

数据准备好之后,可以直接使用MBANALYSIS Procedure进行分析。 这里通过指定pctsupport=1,限定最小支持度为1%。 运行之后,输出结果如下 输出结果包括支持度,置信度,提升值 对于输出里面的第一条规则,可以看到coke和ice cream在交易里面一起出现了220次,提升度为2.37,意味着购买coke之后让购买ice cream的概率翻倍。

虽然上面给出了明确的关联规则,但是文字格式让探索这些规则变得困难。解决这个问题的方法是通过绘制网络图,可视化这些关系。下面的sql程序进行绘制网络图的数据准备。 整理后的数据格式如下,T1_ITEM是“Source”,而ITEM2是“Target”,使用“Lift”值去链接source 和 target 变量。 然后使用下面的程序绘制网络图 得到如下输出: 太酷了!SAS功能真心强大。 这里摘自Market basket analysis in SAS viya(没有高大上的SAS visual analytics,无法亲身测试)。

结论

关联规则在零售、电商等领域具有比较成熟的应用,其算法也是比较直观容易理解。但在具体应用中,算法产生的关联规则可能并没有实际的意义,或者说是不对的,此时需要结合商业知识以及其他规则评估方法,对规则的实际价值进行判断,做出正确的选择。

参考文档

『啤酒与尿不湿』之关联规则
数据挖掘概念与技术
深入机器学习系列9-关联规则