关联分析(上)

1. 背景

许多商业企业在常年累月的运营中积累了大量的数据。例如,电子商务网站每天都会记录大量的顾客购物数据。下面的表给出一个这种数据的例子,通常称作购物篮事务(market basket transaction)。表中每一行对应一个事务,包含一个唯一标识TID和给定顾客购买的商品的集合。零售商对分析这些数据很感兴趣,以便了解他们的顾客的购买行为。可以使用这种有价值的信息来支持各种商务应用,如市场促销,库存管理和顾客关系管理等。

TID 项集
1 {面包,牛奶}
2 {面包,尿布,啤酒,鸡蛋}
3 {牛奶,尿布,啤酒,可乐}
4 {面包,牛奶,尿布,啤酒}
5 {面包,牛奶,尿布,可乐}

本文主要是介绍一种称作关联分析(association analysis)的方法,用于发现隐藏在大型数据集中的有意义的联系。所发现的联系可以用关联规则(association rule)或频繁项集的形式表示。例如,从上面的表中可以提取出如下规则:


{尿布}->{啤酒}

该规则表明尿布和啤酒的销售之间存在着很强的联系,因为许多购买尿布的顾客也购买啤酒。电子商务网站和零售商们可以使用这类规则,帮助他们发现新的交叉销售商机,进行商品组合推荐等。

2. 问题定义

2.1 二元表示

上面的购物篮数据可以用如下的二元形式来表示,其中每行对应一个事务,每列对应一个项。项可以用二元变量表示,如果项在事务中出现,则它的值为1,否则为0。

TID 面包 牛奶 尿布 啤酒 鸡蛋 可乐
1 1 1 0 0 0 0
2 1 0 1 1 1 0
3 0 1 1 1 0 0
4 1 1 1 1 0 0
5 1 1 1 0 0 1

2.2 项集和支持度计数

令$I=\{i_1,i_2,\cdots,i_d\}$是购物篮数据中所有项的集合,而$T=\{t_1,t_2,\cdots,t_N\}$是所有事务的集合。每个事务$t_i$包含的项集都是$I$的子集。在关联分析中,包含0个或多个项的集合被称为[项集](itemset)。如果一个项集包含$k$个项,则称它为k-项集。例如,{啤酒,尿布,牛奶}是一个3-项集。空集是指不包含任何项的项集。

事务的宽度定义为事务中出现项的个数。如果项集$X$是事务$t_j$的子集,则称事务$t_j$包括项集$X$。记为
$$
X \subset t_j
$$
例如,第二个事务为{面包,尿布,啤酒,鸡蛋},包括项集{面包,尿布},但不包括项集{面包,牛奶}。

项集的一个重要性质是它的[支持度计数],即包含特定项集的事务个数。对于上面的购物篮数据,项集{啤酒,尿布,牛奶}的支持度计数为2,因为只有2个事务同时包含这3个项,即第3和第4个事务。

在数学上,项集$X$的支持度计数$\sigma(X)$可以表示为
$$
\sigma(X) = |{t_i}: X \subset t_i, t_i \in T|
$$
其中,符号$|\cdot|$表示集合中元素的个数。

2.3 关联规则(association rule)

关联规则是形如$X \rightarrow Y$的蕴涵表达式,其中$X$和$Y$是不相交的项集,即$X \cap Y = \emptyset$。关联规则的强度可以用它的支持度(support)和置信度(confidence)度量。

支持度确定规则可以用于给定数据集的频繁程度,而置信度确定$Y$在包含$X$的事务中出现的频繁程度。支持度(s)和置信度(c)这两种度量的形式定义如下
$$
s(X \rightarrow Y) = \frac{\sigma(X \cup Y)}{N} \\
c(X \rightarrow Y) = \frac{\sigma(X \cup Y)}{\sigma(X)}
$$

可以看到,支持度表示$X$和$Y$同时出现的概率,而置信度表示在$X$出现的情况下,$Y$也出现的概率,即条件概率$P(Y|X)$

例如,考虑规则$\{牛奶,尿布\} \rightarrow \{啤酒\}$,由于项集{牛奶,尿布,啤酒}的支持度计数是2,而事务的总数是5,所以规则的支持度为2/5=0.4。由于项集{牛奶,尿布}的支持度是3,因此该规则的置信度为2/3=0.67。

2.4 为什么使用支持度和置信度

支持度是一种重要度量,因为支持度很低的规则可能只是偶然出现。从商务角度看,低支持度的规则多半也是无意义的,因为对顾客很少同时购买的商品进行促销可能并无益处。因此,支持度通常用来删去那些无意义的规则

另一方面,置信度度量通过规则进行推理具有可靠性。对于给定的规则$X \rightarrow Y$,置信度越高,$Y$在包含$X$的事务中出现的可能性就越大。置信度也可以估计在给定$X$的情况下,$Y$出现的条件概率

3. 关联规则挖掘

关联规则的挖掘问题可以形式地描述如下:
给定事务的集合$T$,[关联规则发现]是指找出支持度大于等于minsup并且置信度大于等于minconf的所有规则,其中minsup和minconf是对应的支持度和置信度阈值

挖掘关联规则的一种原始方法是:计算每个可能规则的支持度和置信度。但是这种方法的代价很高,因为可以从数据集中提取的规则的数目达指数级。更具体地说,从包含$d$个项的数据集中提取的可能规则的总数为:
$$
R = 3^d - 2^{d+1}+1
$$
提高关联规则挖掘算法性能的第一步是拆分支持度和置信度要求。由支持度公式可以看出,规则$X \rightarrow Y$仅依赖于其对应项集$X \cup Y$的支持度。例如,下面的规则具有相同的支持度,因为它们涉及的项都源自同一个项集{啤酒,尿布,牛奶}:
$$
\{啤酒,尿布\} \rightarrow \{牛奶\}, \{啤酒,牛奶\} \rightarrow \{尿布\}, \\
\{尿布,牛奶\} \rightarrow \{啤酒\}, \{啤酒\} \rightarrow \{尿布,牛奶\}, \\
\{牛奶\} \rightarrow \{啤酒,尿布\}, \{尿布\} \rightarrow \{啤酒,牛奶\}. \\
$$
如果项集{啤酒,尿布,牛奶}是非频繁的,则可以立即剪掉这6个候选规则,而不必计算它们的置信度值。

因此,大多数关联规则挖掘算法通常采用的一种策略是,将关联规则挖掘任务分解为如下两个主要的子任务。

  • 频繁项集的产生:其目标是发现满足最小支持度阈值的所有项集,这些项集称作频繁项集(frequent itemset);
  • 关联规则的产生:其目标是从上一步发现的频繁项集中提取所有高置信度的规则,这些规则称作强规则(strong rule)。

通常,生成频繁项集所需的计算开销大于生成关联规则所需的计算开销。频繁项集和关联规则产生的方法请见下一篇博文。

4. 参考资料

  • 数据挖掘导论,Pang-Ning Tan 等著,范明 等译