6.1 频繁模式概述在线视频

随着人民生活水平的提高

互联网和电子商务领域的不断发展

政府和企业

对于顾客购买行为的研究愈加重视

为了最大限度地实现销售增长

企业需要增加

顾客购买次数和顾客购物车商品件数

因此除了提高商品质量外

挖掘出顾客购买信息中的频繁模式

可使企业深入了解顾客的实时需求

并根据得到的频繁模式

对商品数量

种类

商品摆放位置

促销手段等销售方式进行改变

企业可以以此获得更大利润

本章介绍频繁模式

关联规则的相关概念

并通过实例介绍常用的频繁模式挖掘算法

Apriori和FP-growth

然后引入解决频繁项集过大的问题的方法

最后介绍

对所得到的关联模式进行评估的方法

在美国

著名的沃尔玛超市发现

啤酒与尿布总是共同出现在购物车中

于是沃尔玛超市经过分析发现

许多美国年轻的父亲下班之后

经常要去购买婴儿的尿布

而在购买尿布的同时

他们往往会顺手购买一些啤酒

因此

沃尔玛超市将啤酒与尿布放在相近的位置

方便顾客购买

同时也明显提高了销售额

上述就是一个典型的频繁模式的案例

频繁模式是指频繁出现在数据集中的模式

这些模式

包括项集

子序列和子结构等

研究频繁模式的目的

是得到关联规则和其他的联系

并在实际中应用这些规则和联系

此图是另一个购物车的例子

购物车中包括了油

牛奶

沙丁鱼酱

面包

香蕉

葡萄

洗衣液等商品

展示了顾客会同时购买哪些商品

看了顾客购买的这些商品

我们可能会问：

面包和牛奶共同出现在购物车中

这代表了什么？

购买了油

牛奶

面包

香蕉

葡萄

洗衣液

还应该有哪些商品？

买了这么多的鱼子酱

是因为促销吗？

能挖掘出哪些有趣的模式呢？

每个顾客在不同的时间

不同的地点所购买的商品组成的购物车

包含了许多信息

而分析无数个类似于此图中的购物车之后

能够得到频繁出现在

顾客购物车中的商品组合

进而挖掘出有趣的模式

频繁模式将多次重复出现的关联

从繁杂的数据中提取出来

而购物车分析

信用卡分析

银行产品分析

保险索赔分析和患者就诊分析

则是频繁模式最广泛的应用

例 购物车分析

此表给出了某商店的事务数据

其中每行对应一个事务

每一行的Items

所包含的内容则是一组商品

在一次购物中同时购买的组合

从表中可以发现

牛奶 面包 麦片

牛奶 面包

牛奶 麦片

麦片 面包组合

组合出现3次

糖 鸡蛋组合出现2次

其他的组合都只出现1次

如果认定出现3次或者3次以上的组合

是比较频繁的组合

那么可以得出

如果一位顾客购买了面包

那他很有可能会购买牛奶

或者

如果一位顾客购买了牛奶

那他很有可能会购买面包

这样的关联规则

根据这些关联规则

商业企业就可以

将面包和牛奶摆放得近一些

以便顾客可以方便购买该商品组合

或者将面包和牛奶

摆放在商品架的两端

以便使顾客购买商品架中的其他商品

下面介绍一些基本概念

1 项集

包含0个或者多个项的集合称为项集

任何给定的事务数据都包含许多项集

而项集有时会提供相当多的规则

如果一个项集包含k个项

则称它为k项集

例如

对于上表中的事务数据

TID=1的事务

牛奶 面包 麦片} 组合为3项集

TID=2的事务

牛奶 面包 麦片 鸡蛋 组合

为4项集

2 支持度

项集的支持度分为

绝对支持度和相对支持度

绝对支持度是指项集的出现频度

即包含项集的事务数

如2项集

牛奶 面包的绝对支持度是3

相对支持度是指项集出现的百分比

如2项集

牛奶 面包 的相对支持度是50%

3 频繁项集

如果某一个项集I的支持度满足了

预定的最小支持度阈值

则称I为频繁项集

一个频繁项集的所有子集也都是频繁的

当数据集很大时

通常会挖掘出大量的频繁项集

计算和存储起来就比较困难

例 频繁项集

对于表中的事务数据

设最小支持度阈值为30%

那么项集

面包 麦片 的支持度为50%

大于30%

所以该项集是频繁项集

4 关联规则

设 I 等于iˇ1,iˇ2,iˇ3,...,iˇn

是事务数据中所有项的集合

T等于tˇ1,tˇ2,tˇ3,...,tˇn

是所有事务的集合

其中每个事务 tˇi

都有一个独一无二的标识符TID

关联规则是形如

如果A则B的蕴含式

其中A称为规则前件

B称为规则后件

并且A

AB满足

AB是I的真子集

并且A和B的交集为空集

例 关联规则

对于

如果一个顾客购买了面包

那他很有可能会购买牛奶

这样的表述

可以得出关联规则

购买面包则购买牛奶

支持度=50% 置信度=100%

关联规则的支持度是指

事务中同时包含集合A和集合B的百分比

支持度揭示了A与B同时出现的概率

如果A与B同时出现的概率小

说明A与B关系不大

如果A与B同时出现非常频繁

则说明A与B相关

关联规则的支持度公式如下所示

A蕴含B 的支持度

等于

A并B的概率

即A和B同时出现的概率

最小支持度则是

由用户定义衡量支持度的一个阈值

表示该规则统计意义上

必须满足支持度的最低重要性

5 置信度

置信度是指

事务中同时包含集合A与B的事务数

与包含集合X的事务数的百分比

置信度公式如下所示

A蕴含B的置信度

等于

条件概率

在A条件下B的概率

置信度揭示了A出现时

B也出现的可能性大小

如果置信度为100%

则说明A与B完全相关

如果置信度太低

则说明A的出现与B是否出现关系不大

最小置信度则是

由用户定义衡量置信度的一个阈值

表示该规则统计意义上

必须满足置信度的最低重要性

在典型情况下

如果关联规则满足

最小支持度阈值和最小置信度阈值

关联规则被认为是有用的

6 强关联规则

此图

是项集I等于a,b,c,d,e

的项集格

可以看出

项集探索空间可能是指数规模

通常一个包含k个项的项集

可能产生2^k-1 个频繁项集

可能产生

3^k-2^(k+1)+1 个规则

即使对于小数据来说

产生的频繁项集和规则都相当多

其中大部分规则可能是低效或者无用的

因此

关联分析需要从大量可能的规则中

按条件挑选出最好的少量的规则

传统的关联分析度量包括支持度

置信度和提升度

而从事务集合中挖掘出

同时满足

最小支持度和最小置信度阈值要求的

所有关联规则被称为强关联规则

例 强关联规则

假设最小置信度阈值为30%

最小置信度阈值为70%

而关联规则

如果购买面包则购买牛奶

支持度是50%

置信度是100%

它的支持度和置信度

都满足条件

则该规则为强关联规则

为了得到有用的关联规则

大多数关联规则挖掘算法

采用的策略是将之分解为

以下三个子任务

①根据最小支持度阈值

找出数据集中所有的频繁项集

②挖掘出频繁项集中

满足最小支持度和最小置信度阈值

要求的规则

得到强关联规则

③对产生的强关联规则进行剪枝

找出有用的关联规则

通常

产生频繁项集所需的计算开销

远大于产生规则所需的计算开销

因此需要降低频繁项集的计算复杂度

而先验性质就是一种不用计算

支持度而删除某些候选项集的有效方法

先验原理

如果一个项集是频繁的

那么它的所有非空子集

也是频繁的

在图中

假设

项集{a,b,c}是频繁项集

那么包含它的事务也包含它的子集

{a,b},{a,c},{b,c}

{a},{b},{c}

而它的子集的支持度

大于等于它本身的支持度

所以它的所有子集也是频繁的

反之

如果{a,b,c} 不是频繁项集

那么所有包含{a,b,c} 的项集

一定不是频繁的