1.关联规则综述

在数据挖掘的知识模式中，关联规则模式是比较重要的一种。关联规则的概念由Agrawal、Imielinski、Swami提出，是数据中一种简单但实用的规则。关联规则模式属于描述型模式，发现关联规则的算法属于无监督学习的方法。

1.1关联规则的基本概念

关联规则（Association Rules）用于描述多个变量之间的联系，如果两个或多个变量之间存在一定的关联，那么其中一个变量的状态就能通过其他变量进行预测。自然界中某个事件发生时其他事件也会发生，则这种联系称之为关联。反映事件之间依赖或关联的知识称之为关联型知识（又称依赖关系），顾名思义，关联规则就是发现数据背后存在的某种规则或者联系。关联股则是数据挖掘的一个重要技术，用于从大量数据中挖掘出有价值的数据项之间的相关关系。

1.2关联规则的分类

按照不同情况，关联规则可以进行如下分类。

1.2.1基于规则中处理的变量的类别

基于规则中处理的变量的类别关联规则可以分为布尔型和数值型。布尔型关联规则处理的值显示这些变量之间的关系，一般都是离散的、种类化的；而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态地分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。例如，学历=“本科”=>职业=“数据开发工程师”，是布尔型关联规则；学历=“本科”=>平均收入=7300，涉及的收入是数值类型，则是一个数值型关联规则。

1.2.2基于规则中数据的抽象层次

基于规则中数据的抽象层次可以分为单层关联规则和多层关联规则。在单层的关联规则中，所有的变量考虑到现实的数据是单个层次的；而在多层次的关联规则中，对数据的多层性已经进行了充分的考虑。例如，联想笔记本电脑=>小米打印机，是一个单层关联规则；笔记本电脑=>小米打印机，是一个较高层次和细节层次之间的多层关联规则。

1.2.3基于规则中涉及的数据的维数

基于规则中涉及的数据的维数关联规则可以分为单维的和多维的。在单维的关联规则中，只涉及数据的一个维，如用户购买的物品；而在多维的关联规则中，要处理的数据将会涉及多个维。简单来说，单维关联规则是处理单个属性中的一些关系；多维关联规则是处理多个属性之间的某些关系。例如，啤酒=>尿布，这条规则只涉及用户购买的物品，是单维关联规则；性别=“女”=>职业=“秘书”，这条规则就涉及两个属性的信息，是多维关联规则。

2.关联规则挖掘常用算法

关联规则算法有4类常见的划分方式：基于变量类型的方法、基于抽象层次的方法、基于数据维度的方法、基于时间序列的方法。典型算法有R.Agrawal等人提出的Apriori算法，A.Savasere等人提出的Partition算法、J.Park等人提出的DHP算法、刘兵等人提出的MSApriori算法、韩嘉炜等人提出的FP-Growth算法。其中最为经典的是Apriori算法，其他算法都是根据Apriori算法演变而来。

2.1Apriori算法

Apriori算法是第一个关联规则的挖掘算法，是一种最有影响的挖掘布尔关联规则频繁项集的算法，其核心是基于两阶段频集思想的推进算法。该关联规则在分类上属于单维、单层、布尔关联规则，在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。

2.1.1Apriori算法概述

Apriori算法的基本思想是：首先找到所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小置信度。然后使用前一步找到的频集产生期望的规则，产生只包含集合的项的所有规则，一旦这些规则被生成，那么只有那些大于用户给定的最小置信度的规则才被留下来。为了生成所有频集，使用了递推的方法。可能产生大量的候选集，以及可能需要重复扫描数据库，是Apriori算法的两大缺点。
Apriori算法是一种“先验”算法，通过该算法可以对数据集做关联分析，也就是可以在大规模的数据中寻找有趣关系的任务。这些关系可以有两种形式，分别是频繁项集和关联规则。在这里，频繁项集指经常出现在一块的物品的集合，关联规则指暗示两种物品之间可能存在很强的关系。

2.1.2Apriori算法原理及步骤

Apriori算法的原理：如果某个项集是频繁项集，那么它所有的子集也是频繁的。即如果{0，1}是频繁的，那么{0}{1}也一定是频繁的。反之亦然，也就是说如果一个项集是非频繁项集，那么它的所有超集也是非频繁项集。
如图中可以看到，已知灰色部分{2，3}非频繁项集，利用上面的原理，{0，2，3}{1，2，3}{0，1，2，3}都是非频繁的。也就是说，计算出{2，3}的支持度，知道它是非频繁的之后，就不需要再计算{0，2，3}{1，2，3}{0，1，2，3}的支持度，因为这些集合不满足要求。使用该原理就可以避免项集数目的指数增长，从而在合理的时间内计算出频繁项集。

Apriori算法的步骤。
（1）收集数据：首先描述数据库，找出项数为1的频繁项集（即频繁的单项集），此时k=1。
（2）准备数据：从k频繁项集中生成k+1候选频繁项集。
（3）分析数据：扫描数据集，计算出每个候选频繁项集的支持度。
（4）训练数据：根据最小支持度要求，从中筛选出k+1频繁项集为空。
（5）测试算法：直到k+1达到用户指定的最大项数，或者k+1频繁项集为空。
（6）使用算法：用于发现频繁项集以及物品之间的关联规则。

例

以下是Apriori算法的具体步骤，给定事务数据库D，设最小支持度为2。

TID	I（项集）
001	B,C,E
002	A,C
003	A,C,E
004	A,C
005	B,D,E
006	A,B,C
007	A,B,D,E
008	A,B,C
009	B,C

首先找到1项候选集的集合C1

项集	支持度
A	6
B	7
C	6
D	2
E	4

生成频繁1项集的集合L1

项集	支持度
A	6
B	7
C	6
D	2
E	4

找到2项候选集的集合C2

项集	支持度
A,B	4
A,C	4
A,D	1
A,E	2
B,C	4
B,D	2
B,E	4
C,D	0
C,E	1
D,E	2

筛选出支持度大于2的频繁2项集的集合L2

项集	支持度
A,B	4
A,C	4
A,E	2
B,C	4
B,D	2
B,E	4
D,E	2

找到3项候选集的集合C3

项集	支持度
A,B,C	2
A,B,E	2
B,D,E	2

筛选出支持度大于等于2的3项集的集合L3

项集	支持度
A,B,C	2
A,B,E	2
B,D,E	2

从以上例子中可以发现，L3中的频繁项集{A,B,E}的非空子集为{{A}，{B}，{E}，{A,B}，{A,E}，{B,E}}，那么关联规则{A,B}到{E}的置信度为2/4=0.5=50%，{A,E}到{B}的置信度为4/4=1=100%，{B,E}到{A}的置信度为4/4=1=100%。假设最小置信度为70%，那么{A,E}到{B}，{B,E}到{A}是强关联规则，{A,B}到{E}则不是强关联规则。

2.1.3Apriori算法的特点

（1）Apriori算法优点在于易编码实现，缺点是在大数据集上有可能较慢，适用数据类型为数值型或者标称型数据。
（2）对数据库的扫描次数过多，每次计算项集的支持度时，都对数据库中的全部记录进行了一遍扫描比较，这种扫描比较会大大增加计算机系统的I/O开销。
（3）会产生大量的中间项集，在每一步产生候选项集时循环产生的组合过多，没有排除不应该参与组合的元素。