INFO

数据挖掘笔记的字体可能看起来怪怪的，是因为部分文字被迫使用 Latex 渲染，而 Latex 渲染的字体和普通字体不一样。

相关性与关联规则

目录

• 目录
• 例子带入
• 概念带入
  • 支持度
  • 置信度
  • 最小支持度和最小支持度：
• 寻找强关联规则
  • 条件独立性
  • 寻找频繁项集
  • 寻找强关联规则
  • 案例计算

例子带入

我们这里有一些关于某家超市购物的数据。

假设有 ABCDE 五种商品，有如下购物数据，每一个集合代表一个顾客的购物清单。

ID | 购物清单
1    {A,B,C}
2    {A,C,D}
3    {A,B,C,D}
4    {B,D,E}
5    {A,B,C,E}
6    {B,C,E}
7    {A,B,E}

数据特征：每一条数据都是一个集合

目标：

1. 找出频繁项集，即经常一起购买的商品，比如 A 和 B 经常一起购买，那么我们就可以把 A 和 B 放在一起卖，这样就可以提高销量。
2. 找出关联规则，即如果买了 A，那么买 B 的概率有多大，比如如果买了 A，那么买 B 的概率是 80%，那么我们就可以把 A 和 B 放在一起卖，这样就可以提高销量。

概念带入

$\mathrm{数}\mathrm{据}\mathrm{库}D=t_1,t_2,...,t_n$

$\mathrm{项}\mathrm{目}\mathrm{集}\mathrm{合}（\mathrm{项}\mathrm{目}\mathrm{集}）I=i_1,i_2,...,i_m$

项目集合是指所有可能出现在数据集中的项目的集合，比如 ABCDE 五种商品的项目集合就是 {A,B,C,D,E} 的所有非空子集，表示用户的所有的选择组合的可能。（包括只有一个数据的，两个数据的）

$\mathrm{事}\mathrm{务}{t}_i$

事务是指数据集中的每一条数据，比如 {A,B,C} 就是一个事务。相当于一个客户购买了 A B C 这三个商品。

支持度

$\mathrm{对}\mathrm{于}\mathrm{一}\mathrm{个}\mathrm{项}\mathrm{目}\mathrm{集}{I}_i，\mathrm{它}\mathrm{在}\mathrm{数}\mathrm{据}\mathrm{集}\mathrm{中}\mathrm{出}\mathrm{现}\mathrm{的}\mathrm{次}\mathrm{数}/\mathrm{数}\mathrm{据}\mathrm{集}\mathrm{的}\mathrm{总}\mathrm{数}，\mathrm{即}：$

$support(I_i)=\frac{I_i\mathrm{在}\mathrm{数}\mathrm{据}\mathrm{集}\mathrm{中}\mathrm{出}\mathrm{现}\mathrm{的}\mathrm{次}\mathrm{数}}{\mathrm{数}\mathrm{据}\mathrm{集}\mathrm{的}\mathrm{总}\mathrm{数}}$

比如{A,B}在数据集中出现了 4 次，数据集的总数是 7，那么$support(A,B)=\frac{4}{7}$

{A}在数据集中出现了 5 次，数据集的总数是 7，那么$support(A)=\frac{5}{7}$

置信度

$\mathrm{对}\mathrm{于}2\mathrm{个}\mathrm{项}\mathrm{目}\mathrm{集}{I}_i\mathrm{和}{I}_j，\mathrm{我}\mathrm{们}\mathrm{定}\mathrm{义}\mathrm{一}\mathrm{个}\mathrm{关}\mathrm{联}\mathrm{规}\mathrm{则}{I}_i=>I_j$

$\mathrm{这}\mathrm{个}\mathrm{关}\mathrm{联}\mathrm{规}\mathrm{则}\mathrm{表}\mathrm{示}\mathrm{是}：\mathrm{如}\mathrm{果}\mathrm{买}\mathrm{了}{I}_i，\mathrm{那}\mathrm{么}\mathrm{买}{I}_j\mathrm{的}\mathrm{概}\mathrm{率}\mathrm{是}\mathrm{多}\mathrm{少}。\mathrm{这}\mathrm{个}\mathrm{概}\mathrm{率}\mathrm{就}\mathrm{是}\mathrm{置}\mathrm{信}\mathrm{度}。$

$confidence(I_i=>I_j)=\frac{support(I_i\cup I_j)}{support(I_i)}=P(I_j|I_i)$

$support(I_i\cup I_j)\mathrm{是}\mathrm{指}{I}_i\mathrm{和}{I}_j\mathrm{同}\mathrm{时}\mathrm{出}\mathrm{现}\mathrm{的}\mathrm{次}\mathrm{数}/\mathrm{数}\mathrm{据}\mathrm{集}\mathrm{的}\mathrm{总}\mathrm{数}$

在我们的例子中，{A,B}和{C}同时出现了 3 次，{C} 在数据集中出现了 5 次，那么$confidence(A,B=>C)=\frac{3}{5}$

即如果买了 {C} 那么买 {A,B} 的概率是 60%

最小支持度和最小支持度：

一般来说，我们会给定一个最小支持度和最小支持度，比如最小支持度是 0.4，最小支持度是 0.6，那么我们就会找出所有支持度大于 0.4 的项目集，然后再找出所有置信度大于 0.6 的关联规则。

刚好，我们的例子中，{A,B}的支持度是 4/7 > 0.4，{C}的支持度 5/7 > 0.4 ，{A,B} => {C} 的置信度 P(ACB|AB)是 3/4，大于 0.6，所以我们把 {A,B} => {C} 视为一个强关联规则。

寻找强关联规则

我们希望找到所有的强关联规则，而强关联规则需要满足 2 个条件：

1. 支持度大于最小支持度
2. 置信度大于最小支持度

所以我们把寻找强关联规则的过程分为 2 步：

1. 寻找最大频繁项集
2. 在每个最大频繁项集中寻找强关联规则 （最大频繁集中每个元素中产生的关联规则满足最小支持度，但元素间的关联规则一定不满足最小支持度）

$\mathrm{先}\mathrm{找}\mathrm{出}\mathrm{支}\mathrm{持}\mathrm{都}\mathrm{满}\mathrm{足}\mathrm{最}\mathrm{下}\mathrm{支}\mathrm{持}\mathrm{度}\mathrm{的}{I}_i,I_j$$\mathrm{再}\mathrm{去}\mathrm{验}\mathrm{证}{I}_i=>I_j\mathrm{和}{I}_j=>I_i\mathrm{是}\mathrm{否}\mathrm{满}\mathrm{足}\mathrm{最}\mathrm{小}\mathrm{支}\mathrm{持}\mathrm{度}$

条件独立性

需要注意，我们在寻找强关联规则的时候，需要考虑条件独立性。

若 A 和 B 是条件独立的，则 P(AB)=P(A)P(B)

$lift(A,B)=\frac{P(AB)}{P(A)P(B)}$

lift(A,B) 表示 A 和 B 的关联程度，如果 lift(A,B) > 1，那么 A 和 B 是正相关的，如果 lift(A,B) < 1，那么 A 和 B 是负相关的，如果 lift(A,B) = 1，那么 A 和 B 是独立的。

如果发现 A 和 B 是负相关的话，就不要去找 A => B 和 B => A 了。

eg:

事务	项目数量
A	6000
B	7500
买了 A 和 B	4000
总计	10000

B => A 的置信度是 4000/7500 = 0.53

但是 lift(A,B) = 0.53/(6000/10000 * 7500/10000) = 0.88 < 1，所以 A 和 B 是负相关的

寻找频繁项集

对于大量的数据，我们不可能一个一个的去计算支持度，所以我们需要一些算法来帮助我们计算。

最暴力的方法就是，我们把所有的项目集都列出来，然后计算它们的支持度，然后再找出支持度大于最小支持度的项目集。

我们来计算一下这个方法的时间复杂度：

假设记在一个数据集中寻找是否有一个项目集的时间复杂度是 O(1)

假设我们有 n 个项目，那么所有的项目集的数量是 $2^n-1$，数据集的数量是 m，那么我们需要计算的次数是：$O(1)\ast 2^n\ast m$

虽然可能 n<<m ,但是 2^n 的数量级非常大，所以这个方法的时间复杂度是非常高的，比如当 n=100,2^n=10^30，这个数量级是非常大的。

对于 Apriori ，得到 L1 的时间复杂度是 O(nm)

C2 的数量是 $C_2=\frac{L_1(L_1-1)}{2}$ ，计算每一个 C2 的时间复杂度是 O(m)，所以得到 L2 的时间复杂度是 O(L1^2*m)

一般来说 L1 比 C1 小很多，所以这个方法比暴力方法要快很多。

（没有找到介绍 Apriori 算法优化程度的算法）

Apriori 算法

Apriori 算法是用来生产频繁项集的算法

支持 Apriori 算法的核心思想是：

1. 如果一个项目集是频繁的，那么它的所有子集也是频繁的。

   那么如果数据中有 {A,B} {A} {B} 三个频繁集，我们只需要找到 {A,B} 就行，并且不会漏掉任何频繁集。

2. 如果一个项目集是非频繁的，那么它的所有超集也是非频繁的。

   那么如果我们发现数据集中 {B} 是非频繁的，那么我们就不需要再去找 {A,B} {A,B,C} 这些超集了，因为它们肯定也是非频繁的。

我们将从 C1 开始，逐步发掘世界的真相生成频繁项集。

Apriori 算法生成频繁项集的过程

候选集 C ：可能是频繁项集的集合

频繁项集 L ：由候选集经过验证后得到的满足最小支持度的集合

1. 扫描数据集，得到所有的 1-项集，即 C1
2. 由 C1 生成 L1（也叫 频繁1-项集，注意区别 1-项集 ），即 C1 中的所有项目集中支持度大于最小支持度的项目集（进行第一步扫描的时候就可以记录每个项目集的支持度）
3. 根据算法由 L1 生成 C2
4. 扫描数据集，得到所有的 2-项集，即 C2
5. 根据算法由 Lk-1 生成 Ck
6. 扫描数据集，得到所有的 k-项集，即 Ck
7. 重复 5-6，直到 Lk 为空

这里有个问题，如何用如何用 Lk-1 生成 Ck 呢？

输入：Lk-1
输出：Ck

对于Lk-1中的任意2个项目集，如果它们的前k-2个项目相同，
那么它们的并集就是Ck中的一个项目集。

比如：{A,B,C}和{A,B,D}的并集是{A,B,C,D}
{A,B,C}和{A,B,E}的并集是{A,B,C,E}，{A,B,D}和{A,B,E}的并集是{A,B,D,E}。

> 生成 ABCE 而不是 ABEC ，请保持顺序不变

OK，我们已经得到了所有 x-项集，并可以由此生成最大频繁项集了。

最大频繁项集：如果一个频繁项集的所有超集都是非频繁项集，那么这个频繁项集就是最大频繁项集。

EG：根据 L1 L2 L3 得到最大频繁项集是

{{A,B,C},{B,E}}

例题

data:
1   3 4
  2 3 4 5
1   3   5   7
  2     5
1 2   4     6
  2   4     6
support = 40%(3)

C1 = 1 2 3 4 5 6
L1 = 1 2 3 4 5
C2 = 1,2 1,3 1,4 1,5 2,3 2,4 2,5 3,4 3,5 4,5
L2 = 2,4

Apriori 算法的优化

Apriori 算法的缺点：

1. 生成的候选集很多，计算量大，比如 10^4 的 Lk-1，可能会生成 10^7 的 Ck
2. 多次扫描数据集，效率低

基于散列的频繁项集生成

参考资料：

• 安全系列之——主流 Hash 散列算法介绍和使用 | 知乎

Apriori 算法的问题：

Apriori 算法会生成很多无用的候选集，比如吸尘器和红酒，这两个项目集的并集{吸尘器和红酒}很大概率上不会出现，但是 Apriori 算法还是会生成这个候选集并在之后的过程去验证支持度。类似的候选集 Apriori 算法还会生成很多。

我们可以使用散列的方法来避免生成这些无用的候选集。

散列的方法中，候选集是在扫描数据集的时候生成的，生成到对应的散列桶中，然后再计算支持度。

EG:寻找数据中的频繁2-项集
ABE BD BC ABD AC
BC AC ABCE ABC

寻找2-项集：
寻找每个数据中的2-项集，然后放到对应的散列桶中

ABE:
AB | AE | BE

设ABCDE对于12345

AB => (10*x+7)mod7 => 5 => 5号桶
AE => (10*x+5)mod7 => 1 => 1号桶
BE => (10*x+5)mod7 => 4 => 4号桶

BD:
BD => (10*x+4)mod7 => 3 => 3号桶

。。。

统计每个桶中的数据，得到支持度

一个散列桶中可能会有不同的候选集，比如 5 号桶中可能有 AB 和 AE，这和我们的散列函数 (10*x+7)mod7 有关，我们可以通过调整散列函数来减少这种情况。

事务压缩

给不含任何频繁项集的事务标记，在扫描的时候忽略这些事务。

数据划分（Parition）

将数据集划分为多个子集，每个子集只包含数据集的一部分，分别求出每个子集的最大频繁集，做为全局的最大频繁集的候选集，然后再求出全局的最大频繁集。

基于采样的频繁项集生成（Sampling）

对数据集进行采样，然后求出采样数据集的最大频繁集，做为全局的最大频繁集的候选集，然后再求出全局的最大频繁集。

会损失一些频繁项集，在扫描采样数据集的时候可以降低支持度，找出更多的频繁项集，然后在全局的数据集上验证。

FP-Growth 算法

FP Tree 算法原理总结 | 博客园

FP-Growth 算法是用来生产频繁项集的算法，只需要扫描数据库两次。使用了 FP-Tree 数据结构。

FP-Growth 算法的思想是：

1. 生成 FP-Tree
2. 从 FP-Tree 中挖掘频繁项集

遍历数据集，统计每个 1-项集的支持度，然后删除不满足最小支持度的 1-项集，得到 L1。

将 1-项集按照支持度从大到小排序，得到项头表。

项头表

1-项集	支持度	链表
A	5
B	6
C	5
D	3
。。。

链表用于连接生成的 FP-Tree 上对应的 1-项集的节点。

遍历数据集，对于每个事务，删除项头表中不存在的项目（即支持度不足的项目），然后按照支持度从大到小排序，得到新的事务。

至此，数据处理已经完毕，下面开始生成 FP-Tree。

FP-Tree 的根节点是空节点。

遍历数据集，对于每个事务，从根节点开始，如果根节点的子节点中有这个项目，那么就把这个项目的支持度加一，然后继续遍历这个项目的子节点，如果没有这个项目，那么就在根节点的子节点中新建一个节点，这个节点的项目是这个项目，支持度是 1，然后继续遍历这个项目的子节点。

这里的子节点是指，如果一个事务是{A,B,C}，那么 A 是根节点的子节点，B 是 A 的子节点，C 是 B 的子节点。

下一个事务是{A,B,D}，那么 A 是根节点的子节点，B 是 A 的子节点，D 是 B 的子节点。

生成的 FP-Tree 如下：

<null - A:2 - B:2 - C:1>

              \ D:1>

emm: 树这种东西在 markdown 中画起来好麻烦啊，还是看上面的链接吧。

寻找强关联规则

我们已经得到了最大频繁项集，并可以以此为依据，寻找强关联规则。

对于最大频繁项集中的每个元素，对于这个元素的所有子集，我们都可以生成一个关联规则。

{{A,B,C},{B,E}}

{ABC}:
{A}=>{BC} | {B}=>{AC} | {C}=>{AB}
{BC}=>{A} | {AC}=>{B} | {AB}=>{C}

# ABC=>BC这种关联规则的置信度必然是100%不需要计算

{BE}:
{B}=>{E} | {E}=>{B}

# 注意，{A,B,C}=>{BE}这样的规则是不成立的，因为{ABCE}不是频繁项集
# 所以不会去考虑最大频繁项集中的元素之间以及元素的子集之间的关联规则。

针对生成的每一个关联规则，我们都知道它满足最小支持度，但是我们不知道它是否满足最小支持度。

所以我们需要计算每一个关联规则的置信度，然后再判断是否满足最小支持度。

{A}=>{BC}:P(BC|A)=support(ABC)/support(A)=3/5
...

由此，我们就得到了所有的强关联规则。

案例计算

我们定义最小支持度是 0.4(3)，最小置信度是 0.6

ID | 购物清单
1    {A,B,C}
2    {A,C,D}
3    {A,B,C,D,F}
4    {B,D,E}
5    {A,B,C,E}
6    {B,C,E}
7    {A,B,E}
8    {E,F}


C1：{A,B,C,D,E}
{A} 5
{B} 6
{C} 5
{D} 3
{E} 5
{F} 2 ×

L1：{A,B,C,D,E}

C2：{{A,B},{A,C},{A,D},{A,E},{B,C},{B,D},{B,E},{C,D},{C,E},{D,E}}

{A,B} 4
{A,C} 4
{A,D} 2 ×
{A,E} 2 ×
{B,C} 4
{B,D} 2 ×
{B,E} 3
{C,D} 2 ×
{C,E} 2 ×
{D,E} 1 ×

L2：{{A,B},{A,C},{B,C},{B,E}}

C3：{{A,B,C},{A,B,E},{A,C,E},{B,C,E}}

{A,B,C} 3
{A,B,E} 2 ×
{A,C,E} 1 ×
{B,C,E} 2 ×

L3：{{A,B,C}}

C4：{}

# L4 为空，结束

根据 L1 L2 L3 得到最大频繁项集是

{{A,B,C},{B,E}}

根据最大频繁项集得到关联规则

AB=>AC | AC=>AB
AB=>BC | BC=>AB
AB=>A | A=>AB
AB=>B | B=>AB
AB=>C | C=>AB
AC=>BC | BC=>AC
AC=>A | A=>AC
AC=>B | B=>AC
AC=>C | C=>AC
BC=>A | A=>BC
BC=>B | B=>BC
BC=>C | C=>BC
A=>B | B=>A
A=>C | C=>A
B=>C | C=>B

B=>E | E=>B
(你妈的怎么这么多)

依次计算置信度，得到强关联规则是：
xxx（不算了）