酷应用

超级干货：一文读懂关联分析

百家作者：数据分析 2017-08-25 12:12:40

前言

关联分析是数据挖掘中一项基础又重要的技术，是一种在大型数据库中发现变量之间有趣关系的方法。说到数据挖掘的案例，相信很多人都会首先想到沃尔玛超市发现购买尿布的顾客通常也会购买啤酒，于是把啤酒和尿布放在一起销售同时提高了两者的销量的案例。这是关联分析在商业领域应用的一个典型，通过对大量商品记录作分析，提取出能够反映顾客偏好的有用的规则。有了这些关联规则，商家制定相应的营销策来来提高销售量。关联技术不但在商业领域被广泛应用，在医疗，保险，电信和证券等领域也得到了有效的应用。本文将对数据挖掘中的关联分析技术做简要的介绍。

基本概念

为了更好了解关联分析的算法，我们首先要知道关联分析的一些基本概念。
事务库

如同上表所示的二维数据集就是一个购物篮事务库。该事物库记录的是顾客购买商品的行为。这里的TID表示一次购买行为的编号，items表示顾客购买了哪些商品。
事务
事务库中的每一条记录被称为一笔事务。在上表的购物篮事务中，每一笔事务都表示一次购物行为。
项集(T)
包含0个或者多个项的集合称为项集。在购物蓝事务中，每一样商品就是一个项，一次购买行为包含了多个项，把其中的项组合起来就构成了项集。
支持度计数
项集在事务中出现的次数。例如，｛Bread，Milk｝这个项集在事务库中一共出现了3次，那么它的支持度计数就是3，。
支持度(s)
包含项集的事务在所有事务中所占的比例：，这里N是所有事务的数量。上面的例子中我们得到了{Bread，Milk}这个项集的支持度计数是3，事物库中一共有5条事务，那么{Bread，Milk}这个项集的支持度就是。
频繁项集
如果我们对项目集的支持度设定一个最小阈值，那么所有支持度大于这个阈值的项集就是频繁项集。

关联规则

在了解了上述基本概念之后，我们就可以引入关联分析中的关联规则了。
关联规则其实是两个项集之间的蕴涵表达式。如果我们有两个不相交的项集X和Y，就可以有规则X→Y, 例如｛Bread，Milk｝→{Diaper}。项集和项集之间组合可以产生很多规则，但不是每个规则都是有用的，我们需要一些限定条件来帮助我们找到强度高的规则。
支持度(s)
关联规则的支持度定义为：也就是同时包含X和Y这两个项集的事务占所有事务的比例。我们看｛Bread，Milk｝→{Diaper}这个例子，同时包含｛Bread，Milk，Diaper}这个项集的事务一共有2项，因此这个规则的支持度是。
置信度(c)
关联规则的置信度定义为：这个定义确定的是Y在包含X的事务中出现的频繁程度。还是看｛Bread，Milk｝→{Diaper}这个例子，包含｛Bread，Milk｝项的事务出现了2次，包含｛Bread，Milk，Diaper}的事务也出现了2次，那么这个规则的置信度就是1。
对于关联规则定义这两个度量很有意义的。首先，通过对规则支持度支持度的限定滤去没有意义的规则。我们从商家的角度出发，数据挖掘意义是通过挖掘做出相应的战略决策产生价值。如果一个规则支持度很低，说明顾客同时购买这些商品的次数很少，商家针对这个规则做决策几乎没有意义。其次，置信度越大说明这个规则越可靠。
关联规则发现
有了上述两个度量，就可以对所有规则做限定，找出对我们有意义的规则。首先对支持度和置信度分别设置最小阈值minsup和minconf。然后在所有规则中找出支持度≥minsup和置信度≥minconf的所有关联规则。
有一点我们需要注意的是由简单关联规则得出的推论并不包含因果关系。我们只能由A→B得到A与B有明显同时发生的情况，但不能得出A是因，B是果。也就是说我们只能从案例中获得。
3.1 关联规则算法
根据上面对于关联规则的定义，有一个原始而又简单粗暴粗暴的算法就是，找出所有的规则，对每一个规则计算支持度和置信度，然后再从中提取符合条件的规则。但是这个方法存在一个很致命的问题：如果一个数据集有d个项，这个数据包含的规则总数为：

光是一个6个项的数据集产生的规则就有602条，随着项数量的增加，原始算法的复杂度将成级数增长。下面这个格结构常常用来枚举所有规则的可能性。

因此为了控制需要计算支持度和置信度的规则数量，目前关联规则的挖掘过程大致可以总结为两步：
找出所有频繁项集
由频繁项集产生规则，从中提取置信度高的规则
3.2 Apriori算法
Apriori算法是第一个关联规则的挖掘算法，它开创性的使用了基于支持度的剪枝技术来控制候选项集的指数级增长。Apriori算法产生频繁项集的过程有两步：第一，逐层找出当前候选项集中的所有频繁项集：第二，用当前长度的频繁项集产生长度加1的新的候选项集。
首先我们来看一下Apriori算法用到的核心原理用到的两个重要性质：
如果一个项集是频繁的，那么它的所有子集都是频繁的。
如果一个项集是非频繁的，那么它的所有超集都是非平凡的。
如果一个项集是非频繁项集，那么这个项集的超集就不需要再考虑了。因为如果这个项集是非频繁的，那么它的所有超集也一定都是非频繁的。在项集的超集是指，包含这个项集的元素且元素个数更多的项集。在购物篮事务库中{Milk,Beer}就是{Milk}的其中一个超集。这个原理很好理解，如果{Milk}出现了3次，{Milk,Beer}一起出现的次数一定小于3次。所以如果一个项集的支持度小于最小支持度这个阈值了，那么它的超集的支持度一定也小于这个阈值，就不用再考虑了。
伪代码：

（source：数据挖掘导论第六章）
对这段伪代码做一下解读，可以将Apriori算法分为以下步骤:
初始时，每个项都被看作长度为1的候选项集（1-项集），通过计算支持度，滤去非频繁项集得到长度为1的频繁项集的集合
在上一次迭代得到长度为k-1的频繁项集的集合基础上，产生长度为k的候选集
在长度为k的候选集中，除去k-1非频繁项集的候选集
在当前获得的长度为k的候选集中，计算支持度得到所有频繁项集的集合
重复上述2-4 步，直到没有新的候选集可以产生。
下面简单描述购物蓝事物库例子中，所有频繁项集是如何通过Apriori算法找出的。

首先，我们限定最小支持度计数为3。遍历长度为1的项集，发现{Coke}和｛Eggs｝不满足最小支持度计数，将它们除去。用剩余4个长度为1的频繁项集产生＝6个长度为2的候选集。再次基础上重新计算支持度计数，发现{Bread, Milk}和{Milk, Beer}这两个项集是非频繁，将它们除去之后再产生长度为3的候选集。这里需要注意的是不需要再产生{Milk, Beer, Diaper}这个候选集了，因为它的其中一个子集{Milk, Beer}是非频繁的，根据先验原理这个项集本身一定是非频繁的。
优缺点评价:
Apriori算法的优点是可以产生相对较小的候选集，而它的缺点是要重复扫描数据库，且扫描的次数由最大频繁项目集中项目数决定，因此Apriori适用于最大频繁项目集相对较小的数据集中。
用hash树结构提高Apriori算法产生候选集的效率:
在上述的Apriori算法中我们已经知道了这个算法需要不断的进行从频繁项集中产生候选集的过程。首先找到中包含的事务的所有元素，然后在产生长度的候选集。这个过程效率是很低的，为了提高找出所有候选集的效率就要用到哈希树了。
3.3 FP-tree算法
下面介绍一种使用了与Apriori完全不同的方法来发现频繁项集的算法FP-tree。FP-tree算法在过程中没有像Apriori一样产生候选集，而是采用了更为紧凑的数据结构组织tree, 再直接从这个结构中提取频繁项集。FP-tree算法的过程为：
首先对事务中的每个项计算支持度，丢弃其中非频繁的项，每个项的支持度进行倒序排序。同时对每一条事务中的项也按照倒序进行排序。
根据每条事务中事务项的新顺序，依此插入到一棵以Null为根节点的树中。同时记录下每个事务项的支持度。这个过程完成之后，我们就得到了棵FP-tree树结构。
对构建完成的FP-tree，从树结构的上方到下方对每个项，将先前的路径转化为条件FP-tree。
根据每棵条件FP-tree，找出所有频繁项集。
这个对FP-tree算法过程的描述比较抽象，我们通过下面这个例子具体地了解一下FP-tree算法是如何找到频繁项集的。

(source: 数据挖掘：概念与技术Jiawei, Han)
首先对实务中的所有项集计算支持度，然后按照倒序排序，如下图中的绿表所示。然后对每条事务中的项也按照这个倒序，重新排列。例如，对T100这个事务，原来是无序的Ⅰ1, Ⅰ2, Ⅰ5, 但因为Ⅰ2的支持度按照倒序排列在Ⅰ1之前，因此重新排序之后的顺序为Ⅰ2,Ⅰ1,Ⅰ5。经过重新排序后的事务的项集如下表中的第三列所示。

重新扫描事务库，按照重新排序的项集的顺序依次插入以NULL为根节点的树中。对事务T100, 依次创建Ⅰ2,Ⅰ1,Ⅰ5三个结点，然后可以形成一条NULL→Ⅰ2→Ⅰ1→Ⅰ5的路径，该路径上所有结点的频度计数记为1。对事务T200，FP-tree中已经存在了结点Ⅰ2，于是形成一条NULL→Ⅰ2→Ⅰ4的路径，同时创建一个Ⅰ4的节点。此事，Ⅰ2结点上的频度计数增加1，记为2，同时结点Ⅰ4的频度计数记为1。按照相同的过程，扫描完库中的所有事务之后可以得到下图的树结构。

对于构建完成的FP-tree，从树的底部开始依次构建每个项的条件FP-tree。首先我们在上图中找到节点Ⅰ5，发现能够达到Ⅰ5的路径有两条{ Ⅰ2，Ⅰ1，Ⅰ5 :1}和{ Ⅰ2，Ⅰ1，Ⅰ3，Ⅰ5 :1}。
基于这两天路径来构造Ⅰ5的条件tree如同下图所示，其中Ⅰ3要被舍去，因为这里Ⅰ3的计数为1不能满足频繁项集的条件。然后用Ⅰ5的前缀{ Ⅰ2，Ⅰ1：2}列举所有与后缀Ⅰ5的组合，最终得到{Ⅰ2，Ⅰ5 }，{ Ⅰ2，Ⅰ1 }和{Ⅰ2，Ⅰ1，Ⅰ5 }三个频繁项集。

对所有项执行上述步骤，我们可以得到所有项产生的频繁项集：

优缺点评价：
FP-tree算法相对于Apriori算法，时间复杂度和空间复杂都有了显著的提高。但是对海量数据集，时空复杂度仍然很高，此时需要用到数据库划分等技术。

关联模式评价

在之前的分析中，我们已经知道了在由频繁项集产生的规则上，通过限定置信读来获得有意义的规则。然而通过置信度来筛选规则存在具有误导作用的缺点。我们通过一个二元相依表的例子来说明这个置信度的显著缺点。
相依表
下表是一个二元相依表，表中列出了两个项集所产生的四种情况的二元相依表。其中X表示项集X在事务中出现，表示项集X不再事务中出现。

置信度的局限：
下表是一项对爱喝咖啡的人喝爱喝茶的人之间关系的分析。

通过表中所给的信息可以用支持度和置信度评估关联规则{tea}→{coffee}。

从这个规则75%的高置信度，我们似乎可以推断喜欢喝茶的人也喜欢喝咖啡这条规则。但是所有人中喜欢喝咖啡的人的比例高达80%，这样一对比发现如果一个人喜欢喝茶那么他喜欢喝咖啡的可能性将从80%下降到75%。因此如果仅凭置信度就推断出规则是有缺陷的，之所以有这样的误导现象是因为置信度这个度量没有考虑规则后见中项集的支持度。
其它客观度量：
提升度:

兴趣因子：