6.2 Apriori算法在线视频

关联规则挖掘的步骤如下

一 找出所有频繁项集

即大于或等于最小支持度阈值的项集

二 由频繁项集产生强关联规则

这些规则必须

大于或等于最小支持度阈值

和最小置信度阈值

发现频繁项集的

最简单的方法就是穷举法

即将所有满足条件的项集找出

构成候选项集

然后根据相应条件筛选出频繁项集

而穷举法中

最具影响力的挖掘频繁项集的算法则是

Apriori算法

即先验算法

本节主要介绍

先验算法的基本思想

根据Apriori算法的结果

得出相应的关联规则

Apriori算法

使用频繁项集性质的先验知识

该算法应用基于支持度的剪枝技术

用来控制候选项集指数增长

其核心思想是

通过候选集生成和向下封闭检测

两个阶段来挖掘频繁项集

Apriori算法

使用一种称为逐层搜索的迭代方法

其中k项集用于搜索(k+1)项集

首先

通过扫描数据库

累计每个项的个数

并收集满足最小支持度的项

找出频繁1项集的集合

该集合记为L1

使用L1找出频繁2项集的集合L2

使用L2找出L3

如此下去

直到不能再找到频繁k项集

找出每一个LK

需要一次数据库的完整扫描

Apriori算法随着k的递增

不断寻找

满足最小支持度阈值的“k项集”

因此它的总迭代次数

是人为设定的频繁项集的极大长度加一次

Apriori算法的第k次迭代

从第k-1次迭代的结果中

查找频繁k项集

每一次迭代都需要对数据库扫描一次

Apriori算法的实现步骤如下

第一步 连接

算法初始设置k=1

使用连接运算

从数据库中找到所有的

k项候选集的集合

然后k增加1

直到k等于频繁项集的最大长度

或频繁项集为空

构造k项候选集的集合CK

k不等于1时

每次连接都使用前一次迭代中的

所有频繁k-1项集的集合Lk-1的

相互连接

来构造频繁k项候选集的集合Ck

即Ck等于Lk-1连接Lk-1

其中Lk-1的元素是可连接的

如果它们前k-2个项是相同的

即两个可连接的元素只有最后一项不同

这样可简单地确保不产生重复

第二步 剪枝

按照先验原理

对得到的k项候选集的集合Cˇk

进行剪枝

以减小因Cˇk较大

而产生较大的计算量

先验性质指出

如果某一k-1项集的

支持度小于最小支持度阈值

那么它的所有真超项集的

支持度都小于最小支持度阈值

所以该k-1项集

和它的所有真超项集

都不是频繁项集

从而可以

在Cˇk中剪掉该k-1项集的真超k项集

在以后的迭代步骤中不予考虑

然后可以根据最小支持度阈值

在剪枝后的k项候选集的

集合Ck中

剪掉支持度小于最小支持度阈值的k项集

生成频繁k项集的集合Lˇk

Apriori算法如下

输入

项集I

事务数据集D

最小支持度计数阈值Min_sup

输出

D中的所有频繁项集的集合L

第一步 求频繁1项集L1

首先通过扫描事务数据集D

找出所有1项集并计算其支持度

作为候选1项集C1

然后从C1中删除

低于最小支持度阈值

Min_sup的项集

得到所有频繁1项集的集合L1

第二步

k从2开始循环

一直到

所规定的极大的循环次数

或频繁项集为空为止

第三步 连接

将Lk-1进行自身连接

生成候选k项集的集合Cˇk

连接方法如下

对于任意p q∈Lk-1

若按字典序有

p={p1,p2,…,pk-2,pk-1}

q={p1,p2,…,pk-2,qk-1}

且满足pk-1

则把p和q连接成k项集

p1,p2,…,pk-2,pk-1,qk-1

作为候选k项集Ck中的元素

（4）剪枝

删除Ck中的非频繁k项集

即当Ck中一个候选k项集的

某个k-1项子集

不是Lk-1中的元素时

则将它从Ck中删除

（5）计算支持数

通过扫描事务数据集D

计算Ck中每个k项集的支持数

（6）求Lk

删除Ck中低于最小支持度阈值

Min_sup的k项集

得到所有频繁k项集的集合Lk

（7）若Lk=Ø

则转第（9）步

（8）END FOR

（9）另L=L1∪L2∪…∪Lk

输出L

例 Apriori算法

假设使用表中的事务数据

该数据库具有9个事务

设最小支持度为2

试使用Apriori算法挖掘

表的事务数据中的频繁项集

挖掘频繁项集的步骤如下

具体过程如图所示

①设置k=1

扫描该数据库

找出所有的k项集

即候选1项集的集合C1

此处C1等于牛奶 支持度是6

面包 支持度7

可乐 支持度6

鸡蛋 支持度2

麦片 支持度4

②对C1进行剪枝

将支持度小于最小支持度2的项集

全部删除

生成频繁1项集的集合L1

此处所有项的支持度都大于等于

最小支持度阈值2

因此所有项都是属于频繁的

L1等于

牛奶 面包 可乐 鸡蛋 麦片

k增加1

第三步

根据L1生成候选2项集的集合C2

C2等于

牛奶 可乐

牛奶 鸡蛋

牛奶 麦片

面包 可乐

面包 鸡蛋

面包 麦片

可乐 鸡蛋

可乐 麦片

鸡蛋 麦片

根据先验原理对C2进行剪枝

此处没有其非空子集不在L1中的2项集

没有项集被剪掉

④扫描数据库

得到每个2项集的支持度计数

将支持度小于最小支持度2的项集

全部剪除

生成频繁2项集的集合L2

L2包含

牛奶 面包 支持度是4

牛奶 可乐 支持度是4

牛奶 麦片 支持度是2

面包 可乐 支持度是4

面包 鸡蛋 支持度是2

面包 麦片 支持度是4

鸡蛋 麦片 支持度是2

k增加1

⑤根据L2生成候选3项集的集合C3

C3 等于

牛奶 面包 可乐

牛奶 面包 麦片

牛奶 可乐 麦片

面包 可乐 鸡蛋

面包 可乐 麦片

面包 鸡蛋 麦片

根据先验原理对C3进行剪枝

因可乐 鸡蛋和可乐 麦片

不在L2中

因此将牛奶 可乐 麦片

面包 可乐 鸡蛋

及面包 可乐 麦片剪掉

形成剪枝后的候选3项集的集合C3

C3包含牛奶 面包 可乐

牛奶 面包 麦片

面包 鸡蛋 麦片

⑥扫描数据集

得到每个3项集的支持度计数

将支持度小于

最小支持度2的项集全部剪除

生成频繁3项集的集合L3

L3包含牛奶 面包 可乐

支持度2

牛奶 面包 麦片

支持度2

面包 鸡蛋 麦片

支持度2

k增加1

⑦根据L3生成候选4项集的集合C4

C4包含牛奶 面包 可乐 麦片

根据先验原理对C4进行剪枝

因面包 可乐 麦片不在L3中

因此

将牛奶 面包 可乐 麦片剪掉

形成剪枝后的候选4项集的集合C4

为空集

因为C4为空集

算法终止

找到的所有频繁项集如下

在事务数据集中找出频繁项集后

就可以直接由它们产生关联规则

继而找出强关联规则

因关联规则是根据频繁项集生成

因此关联规则满足最小支持度

只需要删除置信度

小于最小置信度的关联规则

即可找到强关联规则

关联规则的生成过程包括两个步骤

①对于频繁项集L中的每个频繁项集X

生成X所有的非空真子集Y

②对于X中的每一个非空真子集Y

构造关联规则

如果Y则X-Y

即Y蕴含X-Y

构造出关联规则后

计算每一个关联规则的置信度

如果大于等于最小置信度阈值

则该规则为强关联规则

例如

对于上例中

L中的频繁3项集

牛奶 面包 麦片

可以推导出非空子集

{牛奶}，{面包}，{麦片}

{牛奶，面包}

{牛奶，麦片}

{面包，麦片}

可以构造的关联规则及置信度如下

如果购买牛奶

则购买面包和麦片

置信度为33%

如果购买面包

则购买牛奶和麦片

置信度为29%

如果购买麦片

则购买牛奶和面包

置信度为50%

如果购买牛奶和面包

则购买麦片

置信度为50%

如果购买牛奶和麦片

则购买面包

置信度为100%

如果购买面包和麦片

则购买牛奶

置信度为100%

假设令最小置信度为70%

则得到的强关联规则为以下两个

使用相同方法可根据

其他频繁项集构造其他关联规则

得到更多强关联规则

可以通过枚举频繁项集

生成所有的关联规则

并通过计算关联规则的置信度

来判断该规则是否为强关联规则

但当一个频繁项集包含的项很多时

就会生成大量的候选关联规则

一个频繁项集X能够生成

2^|X|-2个

即除去空集及自身之外的子集

候选关联规则

可以逐层生成关联规则

并利用如下关联规则的性质进行剪枝

以减少关联规则生成的计算工作量

关联规则性质

设X为频繁项集

Y不等于空集

Y是X的真子集

且Y'不等于空集

是Y的真子集

若Y蕴含X-Y不是强关联规则

则Y'蕴含X-Y'也不是强关联规则

首先产生后件只包含一个项的关联规则

然后两两合并关联规则的后件

生成后件包含两个项的候选关联规则

从这些候选关联规则中再找出强关联规则

以此类推

对上例中的频繁项集的集合

L中的频繁3项集

牛奶 面包 麦片

可以推导出其非空真子集

牛奶

面包

麦片

牛奶 麦片

牛奶 麦片

面包 麦片

可以构造的后件

只包含一个项的关联规则及置信度如下

如果购买牛奶 面包

则购买麦片

置信度为50%

如果购买牛奶 麦片

则购买面包

置信度为100%

如果购买面包 麦片

则购买牛奶

置信度为100%

假设令最小置信度为70%

则得到的强关联规则有

生成后件包含两个项的

关联规则及置信度如下

如果买麦片

则买牛奶和面包

置信度为50%

因置信度小于最小置信度阈值

此关联规则不是强关联规则

使用该方法

可减少过程中产生的关联规则数目

使用相同方法

可根据其他频繁项集构造

其他关联规则

得到更多强关联规则

下面总结下

关联规则挖掘中重要的基础理论

1.频繁项集的性质

①如果X是频繁项集

则它的任何非空子集X'也是频繁项集

即频繁项集的子集也是频繁项集

②如果X是非频繁项集

则它的所有真超级都是非频繁项集

即非频繁项集的超集也是非频繁项集

2. 关联规则的性质

①设X为频繁项集

Y是X的子集且不为空集

Y'是Y的子集

且不为空集

若Y'蕴含X-Y'为强关联规则

则Y蕴含X-Y也是强关联规则

②设X为频繁项集

Y是X的真子集且不为空

Y'是Y的真子集且不为空

若Y蕴含X−Y不是强关联规则

则Y'蕴含X-Y′

也不是强关联规则