Frequent Pattern Mining(频繁模式挖掘) - Aprior挖掘算法

Frequent Pattern Mining(频繁模式挖掘) - Aprior挖掘算法

在开始之前,先看一个故事:

故事产生于20世纪90年代的美国沃尔玛超市中，沃尔玛的超市管理人员分析销售数据时发现了一个令人难于理解的现象：在某些特定的情况下，“啤酒”与“尿布”两件看上去毫无关系的商品会经常出现在同一个购物篮中，这种独特的销售现象引起了管理人员的注意，经过后续调查发现，这种现象出现在年轻的父亲身上。因此超市管理人员将啤酒和尿布的货架安排得非常接近，既提高了销售量，又便利了顾客的购买。

这里的啤酒和尿布就是我们需要介绍的频繁模式的一种。叫做频繁项集。就是出现频繁的项目构成的集合，这里有两个项目，因此也可以称之为2项集。

前面的小故事其实就是频繁模式挖掘的一个使用场景了，就是超市货架的摆放问题，还有一个经典的场景就是推荐了，其实在深度学习出现之前，一些数据挖掘算法也可以获得不错的成绩的。

Aprior挖掘算法

直接看例子.

我们把下面这个表格看成是超市的销售数据, 比如第一行表示Tid为10的一个人,买了糖,可乐,米这三样东西.那么这个表格显示有四个人,他们分别买了一些东西.

步骤:

• 对数据进行第一次扫描,得到频繁1项集.看下面的扫描结果你就知道什么是频繁一项集了.这一步就是将所有的商品一个一个拿出来,去掉重复的.

那么后面的数字表示什么意思呢?

数字表示的是支持度(support), 怎么算出来的呢?以糖为例,糖的支持度就是看4个人当中有几个人买了糖,有10和30,那么糖的支持度就是2.那为什么米的颜色不一样了,因为这里有个最小支持度的设置,例子中我们设置最小支持度为2,也就是说支持度小于2的都要去掉.

• 去掉支持度不符合的1项集之后

• 然后进行join和prune操作. join操作很好理解,就是把它们一一组合起来, 这样就得到了候选的2项集.如下.这里不涉及到prune操作,我们先不讲.

• 继续求它们的支持度.如下.

• 去掉支持度不符合的,如下,

• 继续进行join和prune操作,

join操作我们已经了解了,这里涉及了prune操作,我们看一下.

网上数两个图,看到候选2项集有{糖,尿布}这个选项,但是它的支持度不符合被去掉了,prune做的就是之前支持度不符合的项集,往里面加其它item(超项集),他的支持度任然不符合.所示在糖和尿布里面再加入一个啤酒,它仍然是不符合的,这就是剪枝的做法.

• 最后的结果

总结一下步骤:

1. 遍历数据集，得到频繁1-项集
2. 从频繁K-项集中生成候选的（K+1）-项集
3. 再次遍历数据集，测试候选的（K+1）-项集是否是频繁的，由此得到频繁（K+1）-项集
4. 重复2-3步，直到没有候选项集或频繁项集可以生成
5. 从频繁项集中找出强的关联规则

下面我们来看一下第5步是怎么做的,这里说的强的关联规则.

什么是关联规则?其实就是一个形如A->B的式子.

什么是强,这是自己规定的,比如我认为置信度大于70%的就算强.置信度下面再说.

看一下上面例子生成的频繁3项集

步骤:

• 为每一个频繁项集l生成其所有的非空子项集.我们这里l ={啤酒,可乐, 尿布},那么他的所有非空子项集是{啤酒}, {可乐}, {尿布}, {啤酒,可乐}, {啤酒,尿布}, {可乐, 尿布}
• 我们要计算每一个非空子项集s和l-s关联规则的置信度.置信度confidence用下面的式子算.

$confidence(s->(l-s)) = \frac{support(l)}{support(s)}$confidence(s−>(l−s))=support(s)support(l)​

• 计算置信度

• 如果我们规定最小置信度为70%,那么红框里面的关联规则就是强的关联规则.

总结一下步骤:

1. 为每一个频繁项集l生成其所有的非空子项集
2. 对l的每个非空子项集s，如果满足下式

$confidence(s->(l-s)) = \frac{support(l)}{support(s)} >= min\_conf$confidence(s−>(l−s))=support(s)support(l)​>=min_conf
则规则s->(l-s)就是强的关联规则.