关联模式的评估

约 3156 字大约 11 分钟

2024-05-30

虽然先验原理大大减少了候选项集的指数搜索空间, 但是关联分析算法仍然具备大量的潜在模式. 如何从数以百万计的模式中挑选出人们真正感兴趣的模式成为一个艰巨的任务, 而由于"感兴趣"是一个主观的标准, 因此建立一组广泛接受的评价关联模式质量的标准是非常重要的.

兴趣度的客观度量

客观度量是一种评估关联模式质量的数据驱动方法. 它不依赖于领域, 只需要用户设置阈值来过滤低质量的模式. 客观度量常常基于列联表中列出的频度计数来计算.

下面是一对二元变量 $A$ 和 $B$ 的列联表, $f_{ii}$ 表示频度计数.

	$B$	$\bar{B}$
$A$	$f_{11}$	$f_{10}$	$f_{1+}$
$\bar{A}$	$f_{01}$	$f_{00}$	$f_{0+}$
	$f_{+1}$	$f_{+0}$	$N$

表 5.1

支持度-置信度框架的局限性

经典的关联规则挖掘算法依赖支持度和置信度来去除没有意义的模式. 支持度的缺点在于许多潜在有意义的模式由于包含支持度小的项而被删去. 置信度的缺点更加复杂, 我们用下面的例子进行说明.

假定希望分析爱喝咖啡和爱喝茶的人之间的关系.使用下表来评估关联规则 {茶} $\rightarrow$ {咖啡}.

	咖啡	$\overline{\text{咖啡}}$
茶	150	50	200
$\overline{\text{茶}}$	650	150	800
	800	200	1000

表5.2

如果我们看表格的第一行, 似乎可以发现喜欢喝茶的人也喜欢喝咖啡(一共 200 人中有 150 人符合该情况), 该规则的支持度(15%)和置信度(75%)都相当高. 但是在所有人中, 不管他是否喝茶, 喝咖啡的人比例为 80%, 而喝咖啡的人中喝茶的人却只占 75%. 也就是说, 一个人如果喝茶, 那么他喝咖啡的可能性从 80% 减到了 75%. 因此规则 {茶} $\rightarrow$ {咖啡} 的置信度虽然很高, 但是却是误导的.

我们同样来考虑一个类似的问题, 希望分析喝茶和在饮料中加蜂蜜的人之间的关系. 使用下表来评估关联规则 {茶} $\rightarrow$ {蜂蜜}.

	蜂蜜	$\overline{\text{蜂蜜}}$
茶	100	100	200
$\overline{\text{茶}}$	20	780	800
	120	880	1000

表5.3

根据上表, 我们发现该规则的置信度仅仅为 50%, 这在计算中很可能会被一个正常的置信度阈值所过滤掉, 比如 70%. 然而在使用蜂蜜的人中, 无论他们是否喝茶, 他们的总数都只占 12%(120 / 1000 = 12%). 因此一个人喝茶会使得他使用蜂蜜的概率从 12% 显著增加到 50%. 显然这种规则不应该被过滤掉, 但是如果将置信度用作评估度量这个规则则不会被保留.

我们可以从统计学的角度上来理解这个例子中的偏差. 一个变量的支持度度量了其发生的概率, 而一对变量 A 和 B 的支持度 $s(A,B)$ 度量了两个变量一起发生的概率. 因此, 联合概率 $P(A, B)$ 可写为:

\tag{5.1} P(A,B) = s(A,B)=\frac{f_{11}}{N}

如果 A 和 B 是统计独立的, 即发生 A 和发生 B 之间不存在任何联系, 则 $P(A,B)=P(A) \times P(B)$ . 因此在独立假设下, A和B的支持度 $s_{indep}(A,B)$ 可写为:

\tag{5.2} s_{indep}(A,B) = s(A) \times s(B)=\frac{f_{1+}}{N} \times \frac{f_{+1}}{N}

如果两个变量 $s(A,B)$ 之间的支持等于 $s_{indep}(A,B)$ , 那么可以认为 A 和 B 之间不相关, 但是如果 $s(A,B)$ 和 $s_{indep}(A,B)$ 有很大不同, 则认为A和B可能是互相依赖的. 由于置信度值考虑了 $s(A,B)$ 和 $s(A)$ 之间的偏差, 而不是和 $s(A)\times s(B)$ 之间的偏差, 因此不能解释后件(即 $s(B)$ )的支持度, 这就导致了前面例子中的伪模式.

正是因为支持度-置信度框架有着局限性, 又提出了许多客观度量来捕获 $s(A,B)$ 和 $s(A)$ 之间的偏差. 下面对这些度量进行一一介绍.

兴趣因子

兴趣因子也被称为 提升度(Lift), 定义如下:

\tag{5.3} I(A,B)=\frac{s(A,B)}{s(A) \times s(B)}= \frac{N f_{11}}{f_{1+}f_{+1}}

由于 $s(A)\times s(B)=s_{indep}(A,B)$ , 所以可以看出兴趣因子度量了模式 $s(A,B)$ 的支持度与在统计独立性假设下计算出的基准支持度 $s_{indep}(A,B)$ 的比值. 运用公式(5.2) 和公式(5.3) 可以对度量进行如下解释:

\tag{5.4} I(A,B)= \begin{cases} =1, \ \text{A和B是独立的;}\\ >1, \ \text{A和B是正相关的;}\\ <1, \ \text{A和B是负相关的;} \end{cases}

对于表 5.2 中的例子, $I=\frac{0.15}{0.2 \times 0.8}=0.9375$ , 这表明饮茶的人和喝咖啡的人之间稍微负相关. 同样, 对于表 5.3 中的例子, $I=\frac{0.1}{0.12 \times 0.2}=4.1667$ , 这表明饮茶者和在饮料中使用蜂蜜的人之间存在较强的正相关.

PS(Piatesky-Shapiro)度量

PS 度量不计算 $s(A,B)$ 和 $s_{indep}(A,B)$ 之间的比值, 而是采用如下方法来考虑 $s(A,B)$ 和 $s_{indep}(A,B)$ 之间的差异:

\tag{5.5} PS=s(A,B)-s(A)\times s(B)=\frac{f_{11}}{N}-\frac{f_{1+} f_{+1}}{N_2}

同样我们可以得知 PS 值与 A,B 变量之间的关系为:

\tag{5.6} PS= \begin{cases} =0, \ \text{A 和 B 是独立的;}\\ >0, \ \text{A 和 B 是正相关的;}\\ <0, \ \text{A 和 B 是负相关的;} \end{cases}

IS 度量

IS 是捕获 $s(A,B)$ 和 $s_{indep}(A,B)$ 之间关系的另一种度量. 定义如下:

\tag{5.8} IS(A,B)=\sqrt{I(A,B)\times s(A,B)} = \frac{s(A,B)}{\sqrt{s(A)s(B)}}=\frac{f_{11}}{f_{1+}f_{+1}}

IS 是兴趣因子和模式支持度的几何平均. 所以, 当兴趣因子和支持度都很大时, IS 也会很大. 如果两种模式的兴趣因子相同, 则 IS 选择具有较高支持度的模式. 此外, IS 在数学上等同于二元变量的余弦度量值, 因此 IS 的取值范围为 0~1. IS = 0 表示两个变量不共现, IS = 1 表示完全关系.

在先前的例子中, 规则 {茶} $\rightarrow$ {咖啡} 的 IS = 0.375, 而规则 {茶} $\rightarrow$ {蜂蜜} 的 IS = 0.6455, 这与我们先前对这两个规则的理解也是一致的.

常用客观度量表

度量(符号)	定义
相关性( $\phi$ )	$\frac{Nf_{11}-f_{1+}f_{+1}}{\sqrt{f_{1+}f_{+1}f_{0+}f_{+0}}}$
比值比( $\alpha$ )	$\frac{f_{11}f_{00}}{f_{10}f+{01}}$
Kappa( $\kappa$ )	$\frac{Nf_{11}+Nf_{00}-f_{1+}f_{+1}-f_{0+}f_{+0}}{N^2-f_{1+}f_{+1}-f_{0+}f_{+0}}$
兴趣因子( $I$ )	$\frac{Nf_{11}}{f_{1+}f_{+1}}$
余弦(IS)	$\frac{f_{11}}{\sqrt{f_{1+}f_{}+1}}$
Piatesky-Shapiro(PS)	$\frac{f_{11}}{N}-\frac{f_{1+}f_{+1}}{N^2}$
集体强度( $S$ )	$\frac{f_{11}+f_{00}}{f_{1+}f_{+1}+f_{0+}f_{+0}}\times\frac{N-f_{1+}f_{+1}-f_{0+}f_{+0}}{N-f_{11}-f_{00}}$
Jaccard( $\xi$ )	$\frac{f_{11}}{f_{1+}+f_{+1}-f_{11}}$
全置信度( $h$ )	$min\left[\frac{f_{11}}{f_{1+}}, \frac{f_{11}}{f_{+1}}\right]$

客观度量的一致性

在给定许多可用的度量后出现一个问题: 当这些度量同时应用到一组关联模式时, 是否可用产生相同的有序结果.

这个问题的答案是肯定的: 不能.

事实上, 不存在一个度量对所有应用都是最好的. 可能Lift值排得靠前的规则, $\Phi$ 系数排得很后.

客观度量的性质

下面我们将描述度量的一些性质, 而这些性质在决定度量是否适用于特定应用时起着重要作用.

反演性

反演操作即将二元向量中的每个值进行反转, 0 变 1, 1 变 0.

反演性

如果交换频度计数 $f_{11}$ 和 $f_{00}$ 、 $f_{10}$ 和 $f_{01}$ 后值保持不变, 则客观度量 $M$ 在反演操作下是不变的.

缩放性

缩放性不变性

令 $T$ 是频度计数为 $[f_{11};\ f_{10};\ f_{01};\ f_{00}]$ 的列联表. $T'$ 是转换后的列联表, 所犯高频度计数为 $[k_1k_3f_{11};\ k_2k_3f_{10};\ k_1k_4f_{01};\ k_2k_4f_{00}]$ , 其中 $k_1, k_2, k_3, k_4$ 是用于缩放 $T$ 中两行或两列的正常量. 如果 $M(T)=M(T')$ , 则客观度量 $M$ 在行/列缩放操作下是不变的.

零加性

对于客观度量 $M$ , 如果增加 $f_{00}$ 而保持列联表中所有其他频度不变并不影响 $M$ 的值, 则 $M$ 在零加操作下是不变的.

非对称的兴趣度度量

如果对于度量 $M$ 以积极变量A和B, A和B的顺序不重要, 即 $M(A,B)=M(B,A)$ , 称这种度量为对称的度量. 如果度量 $M$ 取决于变量顺序, 即 $M(A,B) \neq M(B,A)$ , 则称这种度量为非对称度量.

多个二元变量的度量

前面常用客观度量表中我们讨论的度量都是针对二元变量定义的. 其实使用多维列联表中的频率可用将度量扩展到多个变量. 例如下面的表, 每个表目 $f_{ijk}$ 都表示包含项 a, b 和 c 的某种组合的事务数.

c	b	$\bar{b}$
a	$f_{111}$	$f_{101}$	$f_{1+1}$
$\bar{a}$	$f_{011}$	$f_{001}$	$f_{0+1}$
	$f_{+11}$	$f_{+01}$	$f_{++1}$

$\bar{c}$	b	$\bar{b}$
a	$f_{110}$	$f_{100}$	$f_{1+0}$
$\bar{a}$	$f_{010}$	$f_{000}$	$f_{0+0}$
	$f_{+10}$	$f_{+00}$	$f_{++0}$

给定一个 k-项集 $\{i_1,i_2, \dots , i_k\}$ , 统计独立性条件可用定义如下:

\tag{5.9} f_{i_1i_2\dotsi_k}=\frac{f_{i_1+\dots+}\times f_{+i_2+} \times \dots \times f_{++\dots i_k}}{N^{k-1}}

利用该定义, 可用扩展基于背离统计独立性的客观度量到多个变量:

\tag{5.10} I=\frac{N^{k-1} \times f_{i_1i_2\dotsi_k} }{f_{i_1+\dots+}\times f_{+i_2+} \times \dots \times f_{++\dots i_k}}

\tag{5.11} PS=\frac{f_{i_1i_2\dotsi_k}}{N} - \frac{f_{i_1+\dots+}\times f_{+i_2+} \times \dots \times f_{++\dots i_k}}{N^{k}}

辛普森悖论

辛普森悖论是指: 在某些情况下, 由于隐藏变量(即, 未被包括在分析中的变量)的影响, 会导致观察到的一对变量之间的关联消失或方向发生逆转. 其数学的解释如下.

假设:

\tag{5.12} \frac{a}{b} < \frac{c}{d} \ \ AND \ \ \frac{p}{q}< \frac{r}{s}

其中 $\frac{a}{b}$ 和 $\frac{p}{a}$ 是规则 $A \rightarrow B$ 在两个不同层^[1]下的置信度, $\frac{c}{d}$ 和 $\frac{r}{s}$ 是规则 $\bar{A} \rightarrow B$ 在不同层下的置信度. 当数据汇集到一起的时候, 在组合书籍中这些规则的置信度值分别为 $\frac{a+p}{b+q}$ 和 $\frac{c+r}{d+s}$ . 当满足公式: