数据挖掘- 关联分析算法

作者: 花讽院_和狆 | 来源:发表于2020-03-29 22:56 被阅读0次

关联分析，顾名思义就是找出哪几项之间是有关联关系的，举个例子：

TID	购物记录
1	面包、牛奶
2	面包、尿布、啤酒、鸡蛋
3	牛奶、尿布、啤酒、可乐
4	面包、牛奶、尿布、啤酒
5	面包、牛奶、尿布、可乐

以上是五个购物记录，从中我们可以发现，购买了尿布的人其中有3个购买了啤酒，那么久我们可以推测，尿布和啤酒之间有较强的关联关系，尽管他们之间看起来并没有什么联系，也就是能得到规则： ${尿布} \rightarrow {啤酒}$

因为购物分析能较好地描述关联分析，所以又被叫做购物篮分析。
为了较好的描述这个分析的各种名词，我们把上面的表格重新设计一下：

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

把每一个购物订单中，涉及到的商品都变成1，没涉及到的变成0，也就是将各个商品的购买记录二元化。
当然肯定也有多个分类的情况。

那么面包，牛奶这些就叫数据集的项，而他们组合起来的子集就叫做项集。可以为空，空集是不包含任何项的项集，如果一个项集包含k个子项，就叫做k-项集。
订单12345叫做事务，某个项集在所有事务中出现多少次，叫做项集的支持度计数。

在上面的表格中，项集{啤酒、尿布、牛奶}的支持度计数为2，因为有两个事务（3、4）包含这一项集。

关联规则的衡量

用支持度和置信度来衡量，假定存在规则 $X \rightarrow Y$ ，其中X和Y是不相交的项集，则支持度为： $s(X \rightarrow Y) = \frac{\sigma(X \bigcup Y)}{N}$
其中N是数据集中的事务个数，相当于表示该规则在数据集中出现了多少次。
置信度为：
$c(X \rightarrow Y) = \frac{{\sigma(X \bigcup Y)}}{\sigma(X)}$
置信度的意思就是，在出现X的情况下，有多少次同时出现了Y，代表这个关联规则的频繁程度。

注意置信度的分母是 $\sigma(X)$ ，因此这个评价可能会存在一定的问题。

核心目标

关联分析的核心目标就是找出支持度大于等于某个阈值，同时置信度大于等于某个阈值的所有规则，这两个阈值记为 $minsup$ 和 $minconf$ 。

为了更有效率的完成这个过程，通常把关联规则算法分为两步：

频繁项集的产生，目标是发现满足 $minsup$ 的所有项集，这些项集称作频繁项集。
提炼规则，从上一步发现的频繁项集中提取所有高置信度的规则，称作强规则。

可以看出来，首先要求得频繁项集，这步骤的开销很大，但是只需要考虑支持度就可以了，第二步只考虑置信度就可以了。

下面就可以分两步来解析算法：

找到频繁项集

首先我们可以把项集联想成一个树形结构，每层代表着不同的k-项集，依层递增，非叶子节点来自于他的几个父节点的并集，如图：

树形结构

先验原理

我们肯定不能通过传统的方式，遍历这些节点，算出支持度，然后筛选掉不满足最小支持度的那些，这样开销太大，因此我们引入先验原理，来辅助剪枝。

先验原理：如果一个项集是频繁的，那么他的所有子集也一定是频繁的，如果一个项集是非频繁的，那么他的所有超集也一定是非频繁的。

这个原理不难想象，假如一个项集{a,b}是非频繁项集，那么{a,b,c}肯定也是，因为ab是，在{a,b,c}中与之关联的c必须在ab出现之后才存在，因此他的支持度肯定不会大于{a,b}。

频繁的就是支持度大于等于最小支持度的项集，非频繁就是小于的。

我们可以利用这一定理，把非频繁项集的超集一并从树中减去，这样就能大大的降低计算次数，如图：

非频繁剪枝

虚线圈上的，就是在{a,b}确定是非频繁项集之后，剪掉的超集，这些是不用计算的。

根据这个原理，可以说一下Apriori算法。

Apriori算法

根据上面说的先验原理，Apriori算法先从项集宽度最低的1开始，遍历所有的项集支持度，找出频繁项集（因为第一层在找出支持度之前），之后根据先验原理，挑选任意两个频繁项集组成2-频繁项集（很简单，如果挑非频繁的，那组成的项集就不是频繁项集了），再用2-项集挑选3-项集，直到挑选不出更高层次的项集为止，把这些项集作为候选项集，如图：

挑选候选项集

图中1-项集中，啤酒，面包，尿布，牛奶的支持度大于等于3（设 $minsup$ 为3），则由他们组成2-项集，继续筛选满足支持度不小于3的项集，再由2-项集生成3-项集，这就是Apriori算法筛选频繁项集的基本步骤。总结如下：

初始化，遍历数据集，确定每个项的支持度，之后根据 $minsup$ 筛选频繁1-项集 $F_1$

接下来使用上一次迭代发现的频繁(k-1)项集（k>=2），产生新的候选k-项集，具体如何产生下面会说。

再次遍历数据集，确定候选k-项集的支持度计数，这里需要使用子集函数确定包含在每一个事务t中的所有候选k-项集。

筛选支持度不小于 $minsup$ 的项集，作为下一次迭代的候选项集。循环到第二步，循环迭代。

当没有新的频繁项集产生时，算法完成。

如何产生更高层的候选项集

上面提到了用k-1项集生成k-项集，那么如何才能最有效率的产生k-项集呢，这里用了 $\boldsymbol{F_{k-1}} * \boldsymbol{F_{k-1}}$ 的方法，也就是找到一对（k-1）-项集，当他们的前（k-2）项都相同时，进行合并，合并之后的结果就是{ ${a_1,a_2,a_3...a_{k-2},a_{k-1},b_{k-1}}$ }，因为前k-2项是相同的。
举个例子：

image.png
可以看到，在2-项集中，只有{面包、尿布}和{面包、牛奶}是可以合并的，因此我们就能得到3-项集{面包、尿布、牛奶}。
需要注意的是，这种算法必须保证所有的（k-1）-项集都是频繁的，而且是有序的。

如何确定支持度计数

上面说了如何产生候选项集，接下来就是如何更有效率的确定支持度计数了，同样，如果遍历一个一个查的话效率是很低的，我们可以用枚举的方法遍历每个事务包含的项集，以查找3-项集为例，如图：

某个事务的项集分解

因为我们要查3-项集，因此树状结构就分到3-项集为止。
因为3-项集的开头第一个项肯定在1，2，3之间，我们就设定这三个数为三个分支，无论到哪个节点，都严格按照这个来分（1在左，2在中，3在右），在下面的层次中如何碰到比123更大的，则再向右分，就可以得到图中的关于事务t的所有3-项集。

有了所有项集的列表，我们可以用候选项集去匹配这些项集，从而看t中是否包含候选项集，如果包含，则支持度+1。

可以使用Hash树来进行匹配，从而实现支持度计数。
如下图，就是一个Hash树的例子，每个内部节点都使用Hash函数 $h(p) = p mod 3$ 来确定应当沿着当前节点的哪个分支向下，所以1，4，7就到了同一分支。

Hash树

我们对于单个事务，可以遍历Hash树，设事务为t，则保证所有包含属于事务t的候选3-项集的叶节点至少访问一次。

由于我们之前已经通过树的方式枚举出了t中所有的3-项集，那么我们跟这个Hash一走分支，找到对应3-项集的就+1支持度，即可算出每个候选项集的支持度。

提取规则

提取规则相应的比较简单，设有频繁项集Y，我们忽略前件为空和后件为空的规则，每个频繁项集能产生 $2^k - 2$ 个关联规则，提取方法就是将Y划分为两个非空的子集X和Y-X，使得 $X \rightarrow Y-X$ 满足置信度阈值也就是最小置信度。

规则提取的基础一定是频繁项集已经寻找完成，因此不需要考虑支持度的问题。

同样的，提取规则也有一个原理：

如果规则 $X \rightarrow Y-X$ 不满足置信度阈值，则形如 $X' \rightarrow Y-X'$ 的规则也一定不满足置信度阈值，其中 $X'$ 是 $X$ 的子集。

参考频繁项集的寻找过程，我们可以利用树形结构对规则进行剪枝。
树的每层对应规则后件中的项数，如图：

关联规则剪枝

假设规则{ $bcd$ } $\rightarrow$ { $a$ }不满足置信度阈值的要求，那么可以丢弃后件包含{a}的所有规则，如上图所示。

至此我们经历了寻找频繁项集和提取规则的过程，基本Apriori算法就算完成了，不过还有一些需要考虑的细节。

频繁项集的紧凑表示

在实际应用过程中，往往频繁项集产生的数量可能很大，所以很难表示，我们需要寻找一种方法，找到一些有代表性的频繁项集，以保证其描述性。

通常有如下两种方法：

极大频繁项集

所有超集都不是频繁项集的项集叫做极大频繁项集.

如图：

极大频繁项集
图中灰色的是非频繁项集，白的是频繁项集，加粗的是极大频繁项集，很明显能看出，加粗的{}，他的超集（也就是树中他的下一层跟他关联的节点）都是非频繁项集，因此{}就是个极大频繁项集。

这种表示很明显降低了需要表示项集的个数，我们需要别的候选项集，直接取极大频繁项集的子集就行，任意一个肯定都是。

但是这么做，表示不出他们子集的支持度，所以就需要再遍历数据集，确定非极大频繁项集的支持度，不是很方便。

所以我们还可以用闭频繁项集来表示。

闭频繁项集

先来看闭项集的概念：

项集X是闭的，如果他的直接超集都不具有和他相同的支持度计数。

那么闭频繁项集的概念就很好理解了：

一个项集是闭频繁项集，如果他是闭的，并且他的支持度大于等于最小支持度阈值。

如图，我们假设 $minsup$ 是40%。

闭频繁项集
则深色的就是闭频繁项集，支持度大于等于40%，而且他的超集支持度跟他都不一样。

这种做法可以保证支持度和描述性。

多分类属性的处理

之前举的例子都是二元分类的，要么1要么0，下面看多分类的，我们很容易想到可以用独热编码解决这个问题，把所有分类二元化，但是这样就存在一个问题，有的属性值可能会不够频繁，没办法成为频繁项集。
所以最好是把多分类的项根据实际情况进行分类化，不要针对每个属性都设置独热编码。

或者将不太频繁的属性值合并为一个称作其他的类别。

所以面对多分类属性，我们要做的就是：
独热编码二元化-针对这些值进行一定的合并，或者分类或者并为其他 - 删除冗余的项 - 避免包含多个来自同一属性的项的候选集（例如{ $州 = X_1, 州 = X_2$ }，被写到了一个候选集中，但是实际上这种情况不可能发生，由于独热编码进行的二元化而产生了这种情况，需要避免。）

二元化

处理连续属性

我们也会遇到一些连续属性，可以通过以下几种方式处理：

图中的年龄和年收入就是连续属性

离散化，比较常用，根据实际情况使用等宽，等频率或者聚类等算法把数据分类，达到离散化的目的，再进行关联分析。

这种做法有一个问题就是分类的效果取决于区间的个数和跨度，如果取不好很难得到理想的结果。

图中的年龄就是离散化的

基于统计学的方法
为了产生基于统计学的关联规则，需要指定用于刻画有趣总体段特性的目标属性，保留目标属性，对其他分类属性和连续属性二元化（注意包括其他的连续属性）。
从二元化数据中提取频繁项集。
之后用总体段的统计特征（均值、中位数、方差、绝对偏差）等对目标属性在每个段的分布进行汇总。

如果要验证统计出的值是否具有统计意义，可以参考假设检验中针对不同比较的不同公式，这里不再举例。

非离散化方法
这种方法适用于文档关联分析，具有低支持度的特点，可以用mini-Apriori的方法来分析，在这种方法中，给定文档中词之间的关联通过取他们的规范化频率的最小值得到。
mini-Apriori中定义的支持度有如下期望性质：
支持度随词的规范化频率增加而单调递增。
支持度随包含盖茨的文档个数增加而单调递增。
支持度具有反单调性。

把mini-Apriori算法中的支持度代入到Apriori算法的支持度中即可。

举个例子：

规范化的文档-词矩阵
我们想发现这些词的关系，首先我们要把支持度规范化，保证得到的支持度值是0，1之间的数，如果我们要求第一个词和第二个词的mini-Apriori支持度，就是取他们的规范化频率的最小值。则有：
这就是第一个词和第二个词的支持度。

关联模式的评价

想要衡量模型的好与坏，肯定要有一个评估指标，我们可以根据业务实际去评价，这是主管评价，叫做主观兴趣度度量，这个显然要结合业务，所以我们要看看一些客观指标。

指标的评价往往依赖于相依表，这个相依表有点类似于混淆矩阵：

项	B	!B
A	$f_{11}$	$f_{10}$	f_{1+}
!A	$f_{01}$	$f_{00}$	f_{0+}
	$f_{+1}$	$f_{+0}$	N

其中A，B代表在事务中出现，!A,!B代表没有在事务中出现，空列空行例如 $f_{1+}$ 代表A的支持度计数， $f_{01}$ 表示包含B但是不包含A的事务的个数。

客观指标

最基本的就是置信度和支持度了，但是这两种指标都很难做到客观评价模型，会受到多种因素的影响。

我们可以用兴趣因子来衡量模型：
首先我们引入提升度的概念，它用于计算规则置信度和规则后件中项集的支持度之间的比率， $lift(A \rightarrow B) = \frac{c(A \rightarrow B)}{s(B)}$

对于二元变量，提升度等价于另一种称作兴趣因子的客观度量，定义为： $I(A,B) = \frac{{s(A,B)}}{s(A)*s(B)} = \frac{Nf_{11}}{f_{1+}f_{+1}}$
其中N是事务个数。
如果 $A和B互相独立，则I = 1$
$A和B正相关，则I > 1$
$A和B负相关，则I < 1$

但是兴趣因子有一定局限性，看上图，{p,q}和{r,s}的兴趣因子分别为1.02和4.08，虽然p和q同时出现在88%的文档中，但是他们的兴趣因子接近于1，表明他们相互独立，另一方面，{r,s}的兴趣因子闭{p,q}的高，但是r和s很少出现在一个文档中，这种情况下，置信度要比兴趣因子更可信，置信度表明p和q之间的联系94.6%远高于r和s之间。

另外还可以引入相关系数，逻辑类似于向量的相关系数：
$\phi = \frac{{f_{11}f_{00} - f_{01}f_{10}}}{\sqrt{f_{1+}f_{+1}f_{0+}f_{+0}}}$
相关度的值从-1到1，如果变量相互独立，则Φ=0。

他的局限性在于在食物中把同时出现和同时不出现视为同等重要，这往往不符合实际规律，同时对于倾斜的变量很难度量。

IS度量可以用于处理非对称二元变量，定义如下： $IS(A,B) = \sqrt{I(A,B) * s(A,B)} = \frac{{s(A,B)}}{\sqrt{s(A)s(B)}}$
IS数学上等价于二元变量的余弦度量。
但是IS取决于A和B的支持度，所以存在与置信度度量类似的问题——即使是不相关或者负相关的模式，度量值也可能相当大。

多个二元变量的度量

支持度，全置信度，可以应用于较大的项集，兴趣因子，IS、PS、Jaccard系数等使用多维相依表中的频率，可以扩展到多个变量。

倾斜支持度分布的影响

针对大多数项具有较低或中等的频率，但是少数项具有很高频率的数据集。

image.png
针对这种数据集，我们可以采用全置信度来评价。

交叉支持模式是一个项集 $X = \{i_1,i_2,i_3...,i_k\}$ ，他的支持度比率是： $r(X) = \frac{{min[s(i_1),s(i_2),...,s(i_k)]}}{{max[s(i_1),s(i_2),...,s(i_k)]}}$
小于用户指定的阈值 $h_c$ 。

需要保证全置信度小于上面的支持度比率，而全置信度是： $\frac{{s(\{i_1,i_2,i_3,...,i_k\})}}{{max[s(i_1), s(i_2), ...,s(i_k)]}}$
其中 $s(i_j) =max[i_1,i_2, ...i_k]$ .

全置信度能够确保项集中的项之间是强关联的，例如，假定一个项集X的全置信度是80%，如果X中的一个项出现在某个事物中，则X中其他的项至少也有80%的几率属于同一个事务，这种强关联模式又称超团模式。