一、概述

如何发现数据中内在的规律？

哪些产品经常被一起购买？
买了 PC 之后接着都会买些什么？
哪些 DNA 对这种新药敏感？

「关联挖掘」（Association Analysis）用于发现隐藏在大型数据集中令人感兴趣的，频繁出现的模式、关联和相关性。

关联挖掘是数据挖掘中最活跃的研究内容之一，也是无监督学习系统挖掘本地模式的最普遍的形式。

关联分析最早由 R.Agrawal 等人针对超市购物篮分析问题提出的，其目的是为了发现超市交易数据中不同商品之间的关联关系

一个典型的关联规则的例子：70% 购买了牛奶的顾客将倾向于同时购买面包
发现这样的关联规则可以为市场预测、决策和策划等方面提供依据

二、基本概念与解决方法

假设某超市销售的商品包括：bread, bear, cake, cream, milk 和 tea，交易数据如下

交易号 TID	顾客购买商品 Items
T1	`bread`, `cream`, `milk`, `tea`
T2	`bread`, `cream`, `milk`
T3	`cake`, `milk`
T4	`milk`, `tea`
T5	`bread`, `cake`, `milk`
T6	`bread`, `tea`
T7	`beer`, `milk`, `tea`
T8	`beer`, `tea`
T9	`bread`, `cream`, `milk`, `tea`
T10	`bread`, `milk`, `tea`

例如，对于数据集，指定

TID	item
1	C,D
2	A,B
3	A,B,C
4	A,B,C

频繁项集

频繁闭项集

极大频繁项集

注意到，然而可以显著减少模式数量，保持了频繁项集的完整信息，由频繁闭项集可获得所有的频繁项集和他们的支持度，因此挖掘闭项集是一个好的选择。

三、经典算法

关联规则挖掘包含以下两个步骤。首先，找出所有频繁集，其次，由频繁集产生强关联规则。

两个关联挖掘的经典算法为Apriori 算法

1. Apriori 算法

2. FP-growth 算法

J.Han 等人提出了一种不产生候选集来挖掘频繁集的方法——「FP-growth 算法」。FP-growth 算法在扫描两遍数据集之后，利用一棵频繁模式树来表示频繁集，进而再明确相应的强关联规则。

「频繁模式增长」（Frequent Pattern Growth, FP-growth）算法使用一种比称为 FP-tree 的数据结构，并且采用分而治之的策略，无需产生候选频繁集（）就能得到全部的频繁集

再经过第一遍扫描之后，把数据库中的频繁集压缩进一颗频繁模式树，同时依然保留其中的关联信息
将 FP-tree 分化成一些条件库，每个库和一个长度为 1 的频繁集相关，然后对这些条件库分别进行挖掘。

频繁模式树 FP-tree 是一个树形结构，包括

一个频繁项组成的头表
一个标记为 null 的跟节点
字节点为一个项前缀子树的集合

如果单个项目的支持度大于

「频繁项头表」（Head Table）的每个表项都由三个域组成，项目名称，出现次数和指针，和倒排索引中的词典蕾丝

每个P项前缀子树

模式

根据一个数据集，建立一棵 FP-tree 树。

扫描一遍数据集，得到 1-频繁项集和每个频繁项的支持度。并将按支持度递减排序，存入列表中
第二部
1. 创建树的根节点，用 null 标记

挖掘

由长度为 1 的频繁模式开始，构造它的条件模式基（一个“子数据库”，由 FP 树中与后缀模式一起出现的前缀路径集组成）
构造该初始后缀模式的条件 FP 树，并递归地在该树上实现挖掘。模式增长通过后缀模式与条件 FP

例如从项头表开始挖掘，由频率低的节点开始，沿每个频繁项的连接来遍历 FP 树，通过积累该项的前缀

对每个条件模式基

为基中的每一项累计技术
为模式基中的频繁项构建 FP 树

对于每个条件模式基，都可以构建一个相应的 FP 树。这个过程类似于构建原始 FP 树，只不过数据集变成了条件模式基。

好处：

完整性
- 不会打破任何事务数据中的长模式
- 为频繁模式的挖掘保留了完整的信息
紧凑型
- 减少了不相关的信息——非频繁的项被删除
- 按频率递减排列——使得更频繁的项更容易在树结构中被共享
- 数据量比原始数据库要小

多层关联规则

数据项中经常会出现概念分层，底层的数据项，其支持度也往往较低。这意味着挖掘底层数据项之间的关联规则必须定义不同的支持度。

在适当的等级挖掘出来的数据项之间的关联规则可能是非常有用的。事务数据库中的数据一般是根据维和概念分层来进行存储的。这为从事物数据库中挖掘不同层次的关联规则提供了可能。

子啊多个抽象层挖掘

通常，多层关联规则的挖掘还是使用置信度——支持度框架，可采用自顶向下策略。

注意：在概念分层中，一个节点的支持度肯定不小于该节点的任何子节点的支持度
由概念层 1 开始向下，到较低的更特定的概念层，对每个概念层的频繁项计算累加计数。
每一层的关联规则挖掘可以使用 Apriori 等多种方法。

一致支持度：对所有层都适用一致的最小支持度

优点：搜索时容易采用优化策略，即一个项如果不满足最小支持度，它的所有子项都可以不用搜索。

递减支持度

在浇地岑使用递减的最小支持度，每一层都有自己的一个独立的最小支持度。抽象层越低，对应的最小支持度越小

使用递减支持度，可以解决使用一致支持度时在最小支持度值上设定的困难

基于分组的支持度

用户和专家清楚哪些分组比其他分组更加重要，在挖掘多层关联规则时，使用用户指定的基于项或基于分组的最小支持度阈值。

对于 laptop_computer 或者 flash_drives 设置特别低的支持度阈值，以便特别关注这类商品的管理模式。

挖掘多层关联规则时，由于项间的祖先关系，有些发现的规则是冗余的。例如规则 1 是规则 2 的祖先，如果规则 2 中的项用它在概念分层中的祖先代替，能得到 1，而且 1 的支持度和置信度都接近期望值，则 2 不是有趣的。

关联规则的兴趣度度量

挖掘了关联规则后，哪些规则是用户感兴趣的？强关联规则是否就是有趣的？

客观度量：通常采用两个流行的度量指标
- 支持度
- 置信度
主观度量：最终，只有用户才能确定一个规则是否有趣，而且这种判断是主观的，因不同的用户而异；通常认为一个规则是有趣的，如果
- 它是出人意料的
- 可行动的

强关联规则往往未必有趣，例如下面的数据

	打篮球	不打篮球	合计
喝麦片	2000	1750	3750
不喝麦片	1000	250	1250
合计	3000	2000	5000

然而，规则 $打篮球喝麦片$ 是错误的，因为全部学生中喝麦片粥的比率是，比打篮球学生中喝麦片粥的要高。

$打篮球不喝麦片$ 比上一条要精确，尽管支持度和置信度都更低。由此可见，支持度和置信度有欺骗性，它只是给出两项的条件概率的估计，而不度量两者之间蕴藏的实际强度。

从关联分析到相关分析

我们需要一种度量事件之间的相关性或是依赖性的指标，称为「提升度」，定义为

当项集的出现独立于项集的出现时，，即，表明与无关；，表明 A 和 B 正相关；若。则说明 A 和 B 负相关。