11.2 关联规则（I）在线视频

大家好

欢迎来到《R语言数据分析》课程

今天继续与大家交流

关联规则的相关内容

关联规则的分析有一个比较通俗的叫法是

购物篮分析

也就说我们要挖出类似于

买了啤酒也购买尿不湿这种规则的话

其实都是

都是购物篮分析一个结果

好 所谓购物篮分析

我们可以这样来看

我这边从韩家炜老师

《数据挖掘：概念与技术》这本书里面

盗了个图过来

我们可以这样看

比如我们在超市里面在结账的时候

有不同的消费者买了不同的商品

每一个消费者购买的一个商品

它的明细其实就是

就是一个购物篮

也就是一个事务

比如说第一个消费者有

面包 牛奶 麦片

第二个消费者有

牛奶 面包 糖 鸡蛋 等等

那其实我们所谓的关联分析

我们首先考虑的问题是

就是哪些商品频繁的

被我们的消费者我们的顾客

同时购买

就是哪些商品是频繁出现的

同时出现

这么一个过程

当然这个购物记录

其实我们也可以换一种形式来表达

就是用右侧这种表达方式

我先将

先将所有的商品我都列出来

先将所有商品列出来

这里面其实每个商品也就是一个项对不对

也就是一个项

假如在这个事务里面

这一个消费者一次购买记录

其实就是一个事务

在这个事务里面

这个商品出现了就为1

假如没有出现的话就为0

就为0

我们借助这种消费记录

这个事务的二元表达

我们来看一看

介绍一下我们具体的关联分析里面

一些基本的概念

刚才我们讲了这个具体商品

我们都视为项

我们现在可以

可以定义一个I这么一个集合

I={i1, i2, ..., id} 是什么呢

就是我们购物篮里面

所有的有可能的商品

把它作为一个集合

那每一个消费者的一次购买记录

也就是一个事务

那毫无疑问我们可以定义

{t1, t2, t3, t4,..., tn}

这是一个事务的集合

定义为T

那好

应该说每个事务

它包含的项集都应该属于

都属于这个I的一个子集

I的一个子集

这是我们关于项

项集 事务的一个

一个最基本的概念

我们所谓关联分析是什么

关联分析就是用于发现

隐藏在大型数据集中有意义的联系

具体这种联系是什么方式表达呢

有两种方式

一个是频繁项集

一个是关联规则

这里面有两个核心的概念

一个叫频繁项集

一个叫频繁项集

一个关联规则

项的话就我们前面讲到的

不同的商品

对不对

不同的商品

那好 项集的话是

就是项的集合

这个概念非常的

直接了当

假如我这个项集里面

有两个商品的话

比如有啤酒 有尿布

或者说有牛奶 有面包

这个时候我就称之为2-项集

包含k个项的项集称之为k-项集

比如现在有假如这个有啤酒有尿布

还有面包的话

这个时候

就是一个3-项集了

毫无疑问

我们的不同的项集

是在不同的消费者购买记录中

有可能多次出现的

这个出现的次数

也就是说

在不同的事务中包含了这个项集

有多个事务包含的话

我计算一下

它究竟有多少个事务包含了这个项集

把这个事务数算出来

这个时候我们就称它为项的这个项集的频度

也称之为支持度的计数

也就是说支持度

支持度是一个比例

就是这个出现的事务中

包含这个项集的数目

再除为除以总的事务数

同样支持度的计数的话

它就

就是我具体的那个频数了

这里面有个区别

就是支持度是一个

比例的概念

一个概率的概念

而支持度计数就是绝对的频数

好 假如我这个项集它的支持度

满足预先定义的最小支持度的阈值的话

就称之为

频繁项集

也就是说这个商品组合是频繁出现的

它可能就代表一种模式

我们前面在做分析

这个关联规则的时候

分析这些个性化推荐的时候

买了某本书

也买另外一本书

或者是看了某篇文章也看另外一篇文章的时候

我们当时提到它至少有两个方面

一个是同时性

一个是

方向性

这里面其实是

频繁项集其实代表同时性

就这两个不同的项

不同的商品组合

它是同时出现

它超过一定的频次

我们就视之为

频繁出现

也就频繁项集

这是一种关联分析的表达方式

也就说这两个商品经常同时出现的话

那可能就代表一定的模式

表示这两个商品之间有一定的关联关系

有一定的联系

另外一种表达方式

就是关联规则了

关联规则是

关联规则是一个蕴含式 implication

A出现的时候B也出现

或者说B是伴随着A出现的

这里面A和B可以是单个的项

也可以是长度为k的一个项集

但是A和B是不相交的

A和B是不相交的

我们讲了

要挖出一个有意义的关联关系的话

至少要保证它的同时性

同时要保证它的 方向性

我们这个同时性的话

A和B同时出现的话

我们用

用这个支持度来表达它

就是这个P

A和B这个是这两个组合

同时出现

它的概率

或者说就是它的比例

它的比例

置信度它表示方向性的

就当A出现的时候

B才出现

或者说B伴随着A出现的概率

它是一个条件概率

这个条件概率

其实也可以用后面这个公式来把它计算出来

就是A和B同时出现的一个支持度

除以A的支持度

当然也可以换算成这个频数

一个绝对的一个频数

就是支持度计数

这样算也是一样的

我们可以看得出来

所谓的支持度主要是用来减少这个偶然性的

就是我要挖一个关联规则的话

它必须在历史上

在我的已有的数据记录里面是频繁出现

否则的话

假如它数据出现的次数太少的话

可能只是一个偶然事件

可能不代表有

没有真实的含义

而所谓的置信度

它增加这个推断能力

就是A出现的时候

B也出现

B伴随A出现

这么一个推断过程

我们一般讲满足最小支持度

和置信度这个阈值要求的规则

我们称之为强规则

这个时候A⇒B就是一个强规则了

好 我们来看一下

通过一个文氏图

来直观地理解一下

这个支持度和置信度

假如我们现在用红色表达

购买这个尿布的这个事务

这个事务记录

然后用

用这个蓝色来代表

这个购买啤酒的这个事务记录

这个时候

对于关联规则A⇒B

就是购买尿布的同时也购买啤酒的话

它支持度是

支持度有中间这一部分

有中间这部分交集

然后这个规则的置信度是

就是交集除以

除以A的

p(A)对不对

除以p(A)

也就是说这个交集所占这个红色部分

这个重叠部分所占这个红色部分的比例

这就是所谓的支持度和置信度

好

好

我们看得出来

假如我现在已经知道了A和B这是一个频繁项集的话

那好

那我接下来挖这个规则的话

其实我只要计算

只要计算我这个A和B的这个支持度就可以

A和B同时出现的支持度

A的支持度和B的支持度

就可以判断它是否是一个强规则

换句话说

我们一旦获得了A B

以及A和B同时出现的支持度

那我其实是比较容易导出这个关联规则的

关联规则其实在频繁项集的基础之上

分成两个子集

我先拿一个频繁项集

把这频繁项集分成两部分

一个左边一个右边

然后看左边出现的时候

是不是伴随着右边也出现

这就是所谓关联规则挖掘的过程

总结一下关联规则挖掘的话

可以分成两个步骤

首先找出所有的频繁项集

满足这个最小支持度

满足这个最小支持度

也就是说同时出现的

这个“同时性”得到满足

在这个频繁项集的基础之上 怎么样

再产生这个相应的规则

看看是不是满足相应的置信度 (方向性是否满足)

假如置信度要满足的话

这个时候支持度也满足了

置信度也满足了

它就是一条强规则

这就是我们挖关联规则的两个最基本的步骤

咱们先看第一个步骤

就是挖这个频繁项集

挖频繁项集的时候需要用到一个

apriori这个算法

好 我们先把这个概念先简单引一下

apriori这个英文单词它的意义是

是先验的一个法则

先验的一个规则

我们看一下

一个包含k个项的数据集

它可以产生多少

根据我们的排列组合的相关的一些知识

我们可以知道

它又可以产生 2^k-1 个频繁项集

有可能产生这么多个

假如我们是野蛮搜索的话

需要对这 2^k-1 个频繁项集

每一个频繁项集都进行

进行计数

你究竟在以前的事务里面出现了多少次

它出现的比例是多少

是不是频繁的

那这个时候搜索的空间

它是指数规模增长的对不对

为了避免这种野蛮的搜索

为了避免这个搜索规模

我们需要利用下面这个先验的性质

是什么呢

频繁项集的所有非空子集一定是频繁的

它逆否命题是

就是非频繁项集的超集

必定是非频繁

这里面这两个先验性质其实非常简单

非常直接

什么意思

就每一个项集的支持度

它肯定不会超过它的子集的支持度

比如说我们现在有两个商品

A和B假如A都已经是不频繁的

都已经是非频繁的

那毫无疑问

A和B同时出现的话

它的次数肯定不可能超过A出现的次数

对不对

也就是说非频繁项集的超集

它必定是

必定是非频繁

利用这个性质

我们可以大大的减少这个搜索的次数

我们来看一下

通过一个实际例子看一看

假定我们现在有这么四个项

有这个牛奶

有啤酒

有米饭

有鸡腿

那我们根据前面这个计算方法

它总共应该是有多少

应该是2^k-1

这个K等于4

总的应该是有15个可能的

频繁项集

15个可能频繁项集

那好

假定我知道了这个

牛奶它就是非频繁的

它在我们的购物记录里面出现得比较少的话

那毫无疑问

包含这个牛奶的二项集

比如说这个牛奶和啤酒

牛奶和米饭

牛奶和这个鸡腿

它毫无疑问肯定都是非频繁的

因为它出现的次数肯定不可能多于

不可能多于这个牛奶

这三个2-项集是非频繁的

那相应的

那相应的

包含这三个2-项集的3-项集

它肯定也是

肯定也是非频繁的

相应的下面这个4-项集也是非频繁

那好

只要知道这一个是非频繁的话

那其实我搜索的时候

就是由这个15个可能的频繁项集的候选

直接变成多少个变成7个了

这整个左下角这8个全都剪掉了

假如说我现在所有的1-项集都是频繁的

但是有一个2-项集是非频繁的

假如有一个2-项集是非频繁的

也就是说这个牛奶和这个鸡腿是非频繁的话

毫无疑问

那接下来这个包含这个2-项集的3-项集

肯定也是

非频繁的

那最下面这个4-项集也是非频繁的

这个时候也可以减少一些相应的搜索量

当然假如说1-项集2-项集都是频繁的

但是只有一个3-项集是非频繁的话

那这个时候它只能

把它以及包含它的4-项集

判断为非频繁的

经过这些分析

其实我们可以得出一条

我们在搜索这些项集的时候

计算它项集的那个出现的频次的时候

我应该计算一个顺序

是不是

我并不是把这15个可能的项集

我都一次性进行搜索

把它放在同一个

拉平在同一个平面上进行搜索

而是什么

而是应该有个方向性对不对

我应该先搜索什么

我要先搜索这个1-项集

再搜索2-项集

再搜索3-项集

最后才是4-项集

因为只要我1-项集知道它是非频繁的

那我后面的很多2-项集3-项集

我都能知道它是非频繁的

也就说有这么一个方向性

看完了这个图之后

其实我们这个apriori的这个算法

基本也就呼之欲出了

我们来看一看怎么通过一个具体算法

来实现我们刚才讲的这个搜索的过程

如何搜索

如何生成这个频繁项集

这个算法

首先毫无疑问怎么样

我是k=1

也就是我这个项集的长度

我的这个项集里面只包含

一个项

先把1-项集

频繁的1-项集先找到

对每一个项目都计算一个频次

找到什么

找到它的频繁的1-项集

在生成频繁的1-项集的基础之上

我再一层一层的往下走

对不对

由频繁的k-1项集生成

频繁的k-项集

咱们看看这个过程

这个时候毫无疑问

由一层到下一层的时候

这里面要怎么样

k=k+1

我先由

先由已经知道的频繁的k-1项集

先生成候选

有可能的频繁的k-项集

假如我已经得到这个频繁的k-项集的候选的话

那好

那我就对每一个事务

就是我们刚才看到的

我们每一个顾客的购买记录

那我每个事务怎么样

我都看看

有哪一些候选的这个k-项集

是属于我这个事务的

假如找到的话

找到这个

属于我这个事务的一个子集的话怎么样

我都要每个子集里面

这个k项集都要怎么样

都要进行一个计数

你出现了在某一个事务里面出现一次

那我就增加1 (在事务记录中)出现两次增加2

也就说这个支持度计数

就按照你这个具体的在多少次事务里面出现了

我就增加多少次

增加完之后进行了这个支持度计数之后

我最后计算一下

究竟哪一些这个候选的k-项集里面

它确实已经达到了

我这个最小支持度的要求

也就是说最小支持度

乘以我这个事务总数

一旦是这个条件满足的话

毫无疑问我就要把它视为

把它作为一个频繁的k-项集

在频繁k-项集生成完之后

我再进入下一轮迭代

怎么样

由频繁的k-项集生成频繁的k+1项集

这就是一个层层递进的过程

或者说我们刚才在图里面

层层往下深入的过程

我们在讲这个算法的时候

发现里面有一个非常关键的地方是

从频繁的k-1项集生成

频繁的k项集(的候选)

或者说频繁的k项集

生成频繁的k+1项集的候选

这么一过程是非常非常关键的

那怎么由这个频繁的k-1项集生成

候选的 可能的频繁的k-项集

这里面有几种方法

至少有三种

第一种是蛮力方法

把所有的k项集都看成可能的候选集

然后进行剪枝

这个相对来说它计算的复杂度是比较高的

然后稍微好一点的是

频繁的k-1项集已经拿到了

我再和频繁的1-项集进行连接

这个时候也能生成什么

也能生成一个频繁的k-项集的候选

但是效率最高的下面这种

就是有两个频繁的k-1项集

基于这两个频繁的k-1项集 来连接

生成一个频繁的k-项集

这是一个什么过程

咱们看一下这个算法

也就是说我现在有了一个

找到了所有的频繁的k-1项集

我将其中的一个和另外一个

频繁的k-1项集拿出来

假如它满足

从第1个项到k-2个项

它都相同的话

只有最后的第k-1项

不相同的话

那这个时候我就可以把它连接起来

毫无疑问

前面是k-2项对不对

在这是相同的

再加上第一个频繁的k-1项集

里面的最后一项

再加上第二个频繁的k-1项集

里面最后一个

这毫无疑问总共多少项

总共是k项

把它连接完之后

有可能是一个

一个频繁的k项集的一个候选

但是这个连接过程 连接完之后

并不是说就已经找到

这个频繁的k项集的候选

不是这样的

为什么呢

我必须找到

看看这个刚才连接的结果

这个k项集是否包含非频繁的子集

也就是非频繁的k-1项集

因为我们刚才讲了

有这么一个规则

就是所有的非频繁的项集

它的超集都是都是非频繁的

我们刚才有个先验法则

apriori这个先验法则已经表明

假如我有子集是非频繁的话

毫无疑问我本身也是非频繁的

毫无疑问我本身也是非频繁的

所以我是要做一个验证对不对

要做个验证

对验证的过程也是

就把我所有可能的k-1项集

它的子集都拿过来

看看它是否是属于

我这个频繁的k-1项集

假如都是的话

那好

这个时候我才将这个连接的结果作为

作为一个候选的频繁的k项集

这也是前面我们讲了一下

这个apriori算法

如何产生这个频繁项集的过程

看那个算法的话相对还是有点抽象

咱们再来一个实际的例子

来看看具体的一个

这个算法的一个产生的过程

我们现在假定有这么9个事务

也就有9个购物记录(购物清单)

这是第一个购物者

第一个购物记录里面包含 I1 I2 I5

这么三个商品

第二个有 I2 I4 这两个商品

同样总共有9个这么商品(清单)

我们现在找到满足最小支持度计数为2的

这么一个频繁的项集

咱们来看一看具体是如何实现的

通过这个apriori的这个算法

首先我们根据这个算法首先算

先算频繁的1-项集

这里面项的话只有

I1 I2 I3 I4 I5

这么五项

我们对每一项进行计数

比如I1在这边出现了一次

在这个T4里面出现了

T5里面出现了

在这个T7里面出现了

T8

T9

总共是1 2 3 4 6

6次

毫无疑问

它的支持度计数是超过2的

所以它应该是一个频繁的1-项集

同样我们可以对I2 I3 I4 I5分别进行计算

它分别是7 6 2 2

所以所有的项它其实都是频繁的

都是频繁的

第二个步骤就是怎么样

我由这个频繁的1-项集

生成频繁的2-项集

频繁的1-项集生成频繁2-项集的话

首先怎么样

我先生成就个候选生成一个候选

也是I1 I2 I3 I4 I5 分别组合

生成一个

2-项集的一个可能的候选

生成完之后

我们再对这个候选怎么样

分别进行计数

再来扫描这个数据记录

比如{I1, I2}

我们看一下

这里面出现了

{I1, I2}出现一次

出现两次

再出现第三次

出现第四次

这个时候{I1, I2}毫无疑问

它的支持度计数

或者说它出现的频次总共是多少

4次

我们再看

比如{I1, I4}的话

这个时候

只能找到这一条记录是包含{I1, I4}的

其它记录都包含不了

所以它计数的话只有1

同样我们可以对其它的所有的2-项集

都进行一个支持度计数

记完数之后发现

这里面已经有

好几个这个组合

是非频繁的

也就说我们找到了频繁的2-项集

频繁的2-项集

咱们再来看一看

由频繁的2-项集生成频繁的3-项集的候选

3-项集的候选

好 这个时候我们是需要注意一下的

{I1, I2}

{ I1, I3}

{ I1, I5}

都是什么

都是频繁的2-项集

那好我由k-项集生成k+1项集的时候

这个候选的时候应该怎么样

我除了最后一项不相同之外前面都应该相同

那{I1, I2} {I1, I3}

这两个不相同

那我有可能是

{I1, I2, I3}有可能是

是频繁的

但是我必须确定

{I1, I2,

{I1, I2, I3}的时候必须确定

{I1, I2}

{I1, I3}

还要确定

{I2, I3}也必须是频繁的

否则的话我应该把它划掉

这时候我们看{I2, I3}也是频繁的

所以这一条应该作为

频繁的3-项集的一个候选

好 咱们再看后面这个

比如说这个

{I1, I2} {I1, I5}可以生成一个

{I1, I2, I5}

同样我们可以发现

{I1, I2}

{I1, I5}

{I2, I5}

都出现我们在频繁的2-项集里面

所以这个也是一个频繁的3-项集的候选

咱们来看一下

{I1, I3}

{I1, I5}

虽然说这后面两个不相同

前面都相同

我们按理说应该有一个

{I1, I3, I5}这么一个候选对不对

但是

除了 {I1,I3} { I1,I5} 之外

{I3, I5}

这个2-项集

它的子集是没有出现在

我们这个频繁的2-项集里面的

大家注意到没有

那所以{I1,I3,I5}它就不能作为

就不能作为频繁的3-项集的候选

同样像{I2, I3, I4}

{I2, I3, I5}

{I2, I4, I5}

都不能作为频繁3-项集的候选

也就是说最后频繁3-项集的候选只有两个

{I1， I2， I3}

{I1, I2, I5}

这个时候

我就由这个频繁的2-项集

生成频繁的3-项集(的候选)

我可以计算一下那个具体的

{I1, I2, I3}

{I1, I2, I5}

是否出现了两次以上

这个时候我们可以看得出来

确实它都出现两次以上

当然我们虽然这两个频繁的3-项集里面

它前两项都相同

最后一项确实不相同

但是我们还需要继续往下计算

{I1, I2, I3, I5}

这个4-项集吗

不需要

为什么

{I2, I3, I5}

这个3-项集其实已经是非频繁的

毫无疑问

那{I1, I2, I3, I5}就肯定是非频繁的

我们就不需要再往下继续生成了

也就到此为止

其实我们已经找到了所有的频繁的1-项集

频繁的2-项集

频繁的3-项集

频繁的4-项集就是没有的

更不用说频繁的5-项集了

所以整个这个搜索过程我们可以看得出来

我们真正列入候选的其实数量并不多

也就是说这个apriori的这个算法

其实可以大大的减少

我们这个频繁项集的搜索的过程

这也是个算法比较巧妙的地方

回到我们前面这个关联规则

两个步骤

第一步是找出所有的频繁项集

咱们刚才这个算法已经实现这个功能了

第二步是什么

由频繁项集产生这个关联规则

将这个频繁项集分成两部分

左边一部分右边部分

看看它的置信度怎么样

假如置信度也满足要求的话

那怎么样

那就是可以继续生成

由频繁项集继续生成关联规则了

在我们前面讲这个频繁项集的生成过程中

我们是利用了一个

基于支持度对候选集进行剪枝

就是利用了这个先验法则

先验的性质

同样在生成这个关联规则过程中

我们也可以利用

置信度对这个规则进行剪枝

也并不需要搜索所有的规则

咱们来看一看具体过程是什么样的

好 我们先来看看这个基于置信度如何剪枝

现在我已经知道了

Y是一个频繁项集

我现在所要通过频繁项集生成关联规则的时候

就是将这个频繁项集分成两部分

一个是X这一部分

一个是Y-X这一部分

假如我这条关联规则

这条规则已经不满足置信度阈值的要求了

就是右边这一部分是比较多的时候

已经不满足要求了

那右边这部分比较少的时候

它肯定更不可能符合这个置信度的要求

也就说这个X’是X的真子集的时候

那后面这条规则

肯定是不可能满足置信度要求的

为什么呢

我们看一下置信度的话

毫无疑问我们就是A和B同时出现的时候

它的支持度 毫无疑问

这两条规则上面这个support(Y)都是一样的

主要看这个分母

分母的话

X’的支持度和X的支持度

毫无疑问应该是这个子集的支持度更大一点

对不对

那子集支持度更大的话

毫无疑问它作为分母的话

它这个置信度肯定

肯定是更小了

当我后面这个这条规则的置信度

都已经小于最小的这个置信度的要求了

我们这条规则怎么样

它肯定不可能满足要求

所以就利用这么一个性质

我们可以对这个规则进行剪枝

我们来看一下具体过程

比如说我现在已经知道

abcd是一个频繁项集的话

那好

我先怎么样

我第一个层级

我先把左侧它的项的数量多一点

比如说BCD到A对不对

就BCD出现的时候

A是不是也同时出现

假如这个都已经

不满足我这个置信度要求

那毫无疑问

这一条这一条以及这一条怎么样

都不满足我的置信度要求

假如前面这三条不满足我这个置信度要求的话

那接下来下面这三条

肯定也不满足置信度的要求

也就是说

这个时候可以一次性将这些规则都剪掉

都不用再计算了

所以同样的我们可以

基于这个置信度对规则进行剪枝

这个算法具体过程我们就在此就省略了

咱们简单来总结一下

所谓这个apriori的这个算法

它其实里面的过程是相对比较简单的

我们利用到了在讲这个算法过程中

其实无非是

搜索 匹配 计数 求比例

就这么一些过程

但这个算法本身是平凡的

同时又是比较美好的

怎么说

我们这里面利用到了

支持度的剪枝

置信度的剪枝

大大减少了我的

频繁项集的搜索过程

也减少了我这个

关联规则的搜索过程

所以整个这种算法本身不难理解

但是我们也要体会

这个算法本身在设计过程中它的巧妙地方

本次课到此结束

谢谢大家