第3讲 Apriori算法在线视频

同学们好

欢迎来到

互联网大规模数据分析技术课堂

我是这节课的主讲教师张蕊

来自武汉理工大学

这节课我们一起来了解一下

Apiori算法

上一节课

我们了解了频繁项集

和关联规则的基本概念

这一节课我们来了解一下

怎样去挖掘关联规则

也就是了解相关的算法

发现关联规则的算法可以分为两步

第一步发现所有的频繁项集

第二步

从频繁项集产生强关联规则

现在先考虑第二步

产生强关联规则

如果我们已经有了频繁项集

那我们怎么去产生强关联规则呢

假定我们有一个频繁项集L

那我们可以产生它的所有的非空子集

对它的任意一个非空子集S来说

我们试图产生这样的规则S->（L-S）

这个规则是否是强关联规则呢

首先它一定满足最小支持度阈值

为什么呢

因为

规则左部S并规则右部L-S的结果就是L

L的出现概率

显然要大于等于最小支持度阈值

不然它就不是频繁项集了

那接下来的问题就是

它的可信度应该是多少呢

根据可信度的定义

也就是要知道s出现的情况下

L出现的条件概率是多少

那么

规则左部S和规则右部L-S同时出现的概率

除以S出现的概率就是答案

我们已经找出了频繁项集

知道l和s的支持度了

那么可信度计算最后就变成了

L的支持度除以S的支持度

如果这个值大于等于

最小支持度阈值的话

那它一定是强关联规则

从这里可以看出

已经得到频繁项集的情况下

生成关联规则并不是那么困难

相对来说

如何得到频繁项集

面临的挑战更大

那么如何得到频繁项集呢

下面给大家介绍下历史悠久的Apriori算法

它是频繁项集挖掘的经典算法之一

在提出后的几十年内不断被改进

在了解Apriori算法之前

我们先来看这样一个性质

任何频繁项集的子集一定是频繁的

当然这里的子集不包括空集

是不是这样呢

我们可以考虑啤酒尿布坚果这个3项集

如果他是频繁的

就是说他的出现次数

大于等于给定的支持度阈值

那可以想象，它的子集

比如

啤酒尿布的出现次数

肯定是大于等于

啤酒、尿布、坚果共同出现的次数

因此一定是频繁的

为什么呢

因为只要包含了啤酒尿布坚果的事务

一定包含了啤酒和尿布

因此

一个项集的任何非空子集

出现的次数只会多

不会少于该项集

所以任何频繁项集的非空子集

一定是频繁的

这个，又叫做Apriori性质

也有研究者认为这具有反单调性

所谓反单调性是指

如果一个集合不能通过测试

则它的所有超集也不能通过相同的测试

Apriori算法

应用Apriori性质来进行剪枝

怎样进行剪枝呢

就是如果一个项集是非频繁的

那么它的超集不需要生成或测试

Apiori算法大致可以分为四步

第一步

扫描数据库来得到所有的频繁1-项集

第二步

由长度为k的频繁项集

生成长度为k+1的候选项集

第三步

扫描数据库来测试候选项集

得到长度为k+1的频繁项集

第二步和第三步连接起来进行迭代

直到没有频繁项集或者是

候选项集可以生成才停止

我们来看一个小例子

假定我们有一个

含有四条事务的事务数据库

并且取最小支持度阈值为2

首先，第一次扫描数据库

得到所有的候选1-项集c1

c代表candidate，1代表长度是1

这里候选1-项集

就是A B C D E这些单个的项

并且得到这些单个项目的计数分别是

A出现了两次，B出现了3次

C出现了3次，D出现了1次，E出现了3次

因为最小支持度阈值是2

那么除了D以外都满足

所以频繁1-项集L1应该是：A B C E

这里的L代表的是Large

这里其实不是大，而是频繁

不过由于历史原因

约定俗成由L来表示频繁项集

然后我们由频繁1项集生成

候选2项集C2

注意，这里我们不需要考虑D

因为根据Apriori性质

D是非频繁的

那么

包含D的所有其他集合都是非频繁的

因此由频繁项集A B C E生成了

6个候选2-项集:AB AC AE BC BE CE

再次扫描数据库

得到了所有项集的计数

分别是AB 1次，AC 2次，AE 1次，

BC 2次，BE 3次，CE 2次

然后去掉低于最小支持度的AB和AE

得到频繁2-项集L2为AC BC BE CE

接下来按同样的方式生成候选3-项集

这里

你认为候选3-项集应该是什么呢

是AC和BC连接生成ABC

AC和CE连接生成ACE

BC和BE连接生成BCE吗

实际上，在Apriori算法里

这里只有BCE

原因等下我们来讨论

第三次扫描数据库

得到频繁3-项集BCE

然后

因为没有办法继续生成候选4-项集

所以算法停止

现在我们一起来看一下

Apriori算法的形式化描述

算法的输入是事务数据库和最小支持度

输出是频繁项集

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

然后最外面的for循环迭代

找出所有的频繁项集

对于每次迭代

先由频繁k项集生成所有的候选k+1项集

接下来的那个双重for循环

进行候选项集计数

当无法生成频繁k-项集时算法停止

并返回所有找出的频繁项集

这里需要注意的是怎样由频繁k项集

生成所有的候选k+1项集

大家还记得刚才的那个小例子吧

由频繁2-项集L2的AC BC BE CE

我们只生成了一个候选3-项集 BCE

这是为什么呢

实际上

Apriori算法在这里有约束

要求连接的两个k项集l1和l2

必须按同样的顺序有序排列

然后，前k-1个项l1和l2相同

最后一个项l1小于l2

大家想想

按照这个约束

AC BC BE CE是不是只能生成BCE了

因为AC和BC、AC和CE都不满足这个约束

所以不能连接

最后

只由BC和BE连接生成了BCE

但为什么要这样约束呢

这样难道不会失去一些可能的

频繁项集吗

实际上

的确也有其他算法是按我们之前的思路

如果只有一个项不同

就连接生成候选项集

但Apriori算法这样约束是有道理的

它不会丢掉频繁项集

为什么

例如还是刚才的这个例子

我们来思考下

AC和BC不加约束的话可以生成ABC

现在按Apriori算法它们没有生成

但我们可以断言

如果ABC是频繁的

它可以由其他项集连接生成

如果ABC不是频繁的

不连接生成正好压缩了候选项集的大小

这就具有一定的优势

那为什么如果ABC是频繁的

它就可以由其他项集连接生成呢

因为如果ABC是频繁的

那么根据Apriori性质

AB和AC肯定是频繁的

所以ABC可以由AB和AC生成

本节课的内容到此结束

谢谢大家的观看