Market Basket Analysis

data-mining

---;

关联规则

假如你是沃尔玛的销售经理，正在与一位刚在商店购买了PC和数码相机的顾客交流，你应该向她推荐什么产品？我们可以通过之前顾客在购买了PC和数码相机之后频繁购买的产品，利用这些信息做出推荐。而实现这种推荐的算法，就是关联规则。

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

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

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

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

先不管这个故事的真实性与否，我们关系的能否利用以往的信息，发现某些特征中的联系，从而制定更好的营销策略。

基本概念

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

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

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

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算法的候选产生-检查方法显著压缩了候选项集的规模，并产生很好的性能。然而，它可能受两种非评分开销的影响：

• 可能仍然需要产生大量候选项集。例如，如果有$10^4$个频繁1项集，则Apriori算法需要产生多达$10^7$个候选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%，将发现以下关联规则：

$$"games"\Rightarrow "videos" \\ [support=40\%, confidence=66\%]$$
规则是强关联规则，因为它的支持度为$\frac{4000}{10000}=40\%$，置信度为$\frac{4000}{6000}=60\%$。然而，规则是误导，因为购买录像的概率是75%，比66%还高，事实上，计算机游戏和录像是负相关的，因为买一种实际上降低了买另一种的可能性。

从关联分析到相关分析

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

提升度（lift）是一种简单的相关性度量，定义如下。项集A的出现独立于项集B的出现，如果$P(A\cup B)=P(A)(B)$；否则，项集A和B是依赖的和相关的，A和B的提升度可以通过计算下式得到：

$$lift(A,B) = \frac{P(A\cup B)}{P(A)(B)} = \frac{P(B|A)}{P(B)} = \frac{conf(A\Rightarrow B)}{sup(B)}$$
如果上式的值小于1，则A的出现与B的出现是负相关的，意味着一个出现可能导致另一个不出现，如果结果大于1，则A和B是正相关的，意味着每一个的出现都蕴涵另一个的出现。如果结果等于1，则A和B是独立的，它们之间没有相关性。
提升度评估一个的出现“提升”另一个出现的程度。

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

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

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

全置信度(all confidence)：

$$all_conf(A,B) = \frac{sup(A\cup B)}{max\{sup(A), sup(B)\}}=min\{P(A|B),P(B|A)\}$$
全置信度(A,B)又称两个关联规则“$A\Rightarrow B$”和“$B\Rightarrow A$”的最小置信度。

最大置信度(max confidence)：

$$max_conf(A,B) =max\{P(A|B),P(B|A)\}$$

Kulczynski度量：

$$Kulc(A,B) = \frac{1}{2}(P(A|B)+P(B|A))$$
它可看作是两个置信度的平均值。

余弦

$$cos(A,B) = \frac{P(A\cup B)}{\sqrt{P(A)\times P(B)}} = \frac{A\cup B}{\sqrt{sup(A)\times sup(B)}} = \sqrt{P(A|B)\times P(B|A)}$$
余弦可以看作调和提升度度量。

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

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

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

---

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

-	$milk$	$\overline{milk}$	$\sum_{row}$
$coffee$	$mc$	$\overline{m}c$	$c$
$\overline{coffee}$	$m\overline{c}$	$\overline{mc}$	$\overline{c}$
$\sum_{col}$	$m$	$\overline{m}$	$\sum$

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

数据集	$mc$	$\overline{m}c$	$m\overline{c}$	$\overline{mc}$	$\chi^2$	提升度	全置信度	最大置信度	$Kluc$	余弦
$D_1$	10000	1000	1000	100000	90557	9.26	0.91	0.91	0.91	0.91
$D_2$	10000	1000	1000	100	0	1	0.91	0.91	0.91	0.91
$D_3$	100	1000	1000	100000	670	8.44	0.09	0.09	0.09	0.09
$D_4$	1000	1000	1000	100000	24740	25.75	0.50	0.50	0.50	0.50
$D_5$	1000	100	10000	100000	8173	9.81	0.09	0.91	0.50	0.29
$D_6$	1000	10	100000	100000	965	1.97	0.01	0.99	0.50	0.10

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

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

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

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

$$IR(A,B) = \frac{|sup(A)-sup(B)|}{sup(A) + sup(B) - sup(A\cup B)}$$
比值越大，不平衡比就越大。这个比率独立于零事务的个数，也独立于事务的总数。

考察数据集$D_4$、$D_5$和$D_6$。对于$D_4$，有$IR(m, c) = 0$，表明数据具有很好的平衡性；对于$D_5$，有$IR(m, c) = 0.89$，是一种很不平衡的情况；对于$D_6$，有$IR(m, c) = 0.99$，是一种很不平衡的情况，因此，在$D_5$和$D_6$中，两个度量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功能真心强大。
这一段摘自

结论

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

参考文档

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