深入理解机器学习——关联规则挖掘：基础知识

分类目录《深入理解机器学习》总目录

许多商业企业在日复一日的运营中积聚了大量的数据。例如食品商店的收银台每天都收集大量的顾客购物数据。下图给出一个这种数据的例子通常称作购物篮事务（Market Basket Transaction。表中每一行对应一个事务包含一个唯一标识TID和给定顾客购买的商品的集合。零售商对分析这些数据很感兴趣以便了解他们的顾客的购买行为。可以使用这种有价值的信息来支持各种商务应用如市场促销库存管理和顾客关系管理等。

关联规则挖掘系列文章主要是介绍一种称作关联分析（Association Analysis的方法用于发现隐藏在大型数据集中的有意义的联系。所发现的联系可以用关联规则（Association Rule或频繁项集的形式表示。例如从上图数据中可以提取出如下规则

尿布 → 啤酒

该规则表明尿布和啤酒的销售之间存在着很强的联系因为许多购买尿布的顾客也购买啤酒。零售商们可以使用这类规则帮助他们发现新的交叉销售商机。

除了购物篮数据外关联分析也可以应用于其他领域如生物信息学、医疗诊断、网页挖掘和科学数据分析等。例如在地球科学数据分析中关联模式可以揭示海洋、陆地和大气过程之间的有趣联系。这样的信息能够帮助地球科学家更好地理解地球系统中不同的自然力之间的相互作用。尽管这里提供的技术一般可以都用于更广泛的数据集但是为了便于解释讨论将主要集中在购物篮数据上。

在对购物篮数据进行关联分析时需要处理两个关键的问题第一从大型事务数据集中发现模式可能在计算上要付出很高的代价第二所发现的某些模式可能是虚假的因为它们可能是偶然发生的。

二元表示

购物篮数据可以用下图所示的二元形式来表示其中每行对应一个事务而每列对应一个项。项可以用二元变量表示如果项在事务中出现则它的值为1否则为0。因为通常认为项在事务中出现比不出现更重要因此项是非对称（Asymmetric二元变量。或许这种表示是实际购物篮数据极其简单的展现因为这种表示忽略数据的某些重要的方面如所购商品的数量和价格等。

项集和支持度计数

令 I = { i 1 , i 2 , ⋯   , i d } I=\{i_1, i_2, \cdots, i_d\} I={i1​,i2​,⋯,id​}是购物篮数据中所有项的集合而 T = { t 1 , t 2 , ⋅ , t N } T=\{t_1, t_2, \cdot, t_N\} T={t1​,t2​,⋅,tN​}是所有事务的集合。每个事务$t_i$包含的项集都是$I$的子集。在关联分析中包含0个或多个项的集合被称为项集（Itemset。如果一个项集包含$k$个项则称它为$k$-项集。例如{啤酒尿布牛奶}是一个3-项集而空集是指不包含任何项的项集。

事务的宽度定义为事务中出现项的个数。如果项集$X$是事务$t_j$的子集则称事务$t_j$包括项集$X$。例如在上图中第二个事务包括项集{面包尿布}但不包括项集{面包牛奶}。项集的一个重要性质是它的支持度计数即包含特定项集的事务个数。数学上项集$X$的支持度计数$\sigma (X)$可以表示为
σ ( X ) = ∣ { t i ∣ X ⊆ t i , t i ∈ T } ∣ \sigma(X)=|\{t_i|X\subseteq t_i, t_i\in T\}| σ(X)=∣{ti​∣X⊆ti​,ti​∈T}∣

其中符号$|\cdot |$表示集合中元素的个数。在上图显示的数据集中项集{啤酒尿布牛奶}的支持度计数为2因为只有2个事务同时包含这3个项。

关联规则（Association Rule

关联规则是形如$X\to Y$的蕴涵表达式其中$X$和$Y$是不相交的项集即$X\cap Y=\varnothing$。关联规则的强度可以用它的支持度（Support和置信度`（Confidence度量。支持度确定规则可以用于给定数据集的频繁程度而置信度确定$Y$在包含$X$的事务中出现的频繁程度。支持度$s$和置信度$c$这两种度量的形式定义如下
$$\begin{array}{rl}s(X\to Y)& =\frac{\sigma (X\cup Y)}{N}\\ c(X\to Y)& =\frac{\sigma (X\cup Y)}{\sigma (X)}\end{array}$$

考虑规则{牛奶尿布} → {啤酒}由于项集{牛奶尿布啤酒}的支持度计数是2而事务的总数是5所以规则的支持度为$\frac{2}{5}=0.4$。置信度是项集{牛奶尿布啤酒}的支持度计数与项集{牛奶尿布}支持度计数的商。由于存在3个事务同时包含牛奶和尿布所以该规则的置信度为$\frac{2}{3}=0.67$。

支持度是一种重要度量因为支持度很低的规则可能只是偶然出现。从商务角度来看低支持度的规则多半也是无意义的因为对顾客很少同时购买的商品进行促销可能并无益处。因此支持度通常用来删去那些无意义的规则。此外支持度还具有一种期望的性质可以用于关联规则的有效发现。另一方面置信度度量通过规则进行推理具有可靠性。对于给定的规则$X\to Y$置信度越高$Y$在包含$X$的事务中出现的可能性就越大。置信度也可以估计$Y$在给定$X$下的条件概率。

应当小心解释关联分析的结果。由关联规则作出的推论并不必然蕴涵因果关系。它只表示规则前件和后件中的项明显地同时出现。另一方面因果关系需要关于数据中原因和结果属性的知识并且通常涉及长期出现的联系。

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

控据关联规则的一种原始方法是计算每个可能规则的支持度和置信度。但是这种方法的代价很高令人望而却步因为可以从数据集提取的规则的数目达指数级。更具体地说从包含$d$个项的数据集提取的可能规则的总数为
$$R=3^d+2^{d+1}+1$$

提高关联规则挖掘算法性能的第一步是拆分支持度和置信度要求。由前文可知规则$X\to Y$的支持度仅依赖于其对应项集$X\cup Y$的支持度。例如{啤酒尿布}$\to${牛奶}和{啤酒牛奶}$\to${尿布}有相同的支持度因为它们涉及的项都源自同一个项集{啤酒尿布牛奶}。

如果项集{啤酒尿布牛奶}是非频繁的则可以立即剪掉所有相关的候选规则（如{啤酒尿布}$\to${牛奶}、{啤酒牛奶}$\to${尿布}、{尿布牛奶}$\to${啤酒}等而不必计算它们的置信度值。

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

• 频繁项集产生其目标是发现满足最小支持度阀值的所有项集这些项集称作频繁项集（Frequent Itemset。
• 规则的产生其目标是从上一步发现的频繁项集中提取所有高置信度的规则这些规则称作强规则（Strongrule。

通常频繁项集产生所需的计算开销远大于产生规则所需的计算开销。频繁项集和关联规产生的有效技术将在后续文章中讨论。

参考文献
[1] Pang-NingTan, MichaelSteinbach, VipinKumar. 数据挖掘导论[M]. 人民邮电出版社, 2006.