关联规则挖掘——Apriori算法

前言
大二的时候，一个老师为了勾起我们对数据挖掘的兴趣，老是问我们这个问题：你们知道超市为什么要把啤酒跟尿布放在一起吗？但是从来没告诉我们答案。现在，很多人都听过这个问题，觉得很平常，但是那时的我真觉得挺神奇的。直到后来，了解了关联规则挖掘，学习了关联规则挖掘的代表性算法Apriori，才终于知道了答案。关联规则挖掘，就是找出那些经常同时出现的事物，比如啤酒和尿布。接下来，我们进入正题。

基本知识
关联规则挖掘通过形式化的语言表述如下：
设集合
I=i1,i2,...,im
是一个项目（Item）集合,
T=t1,t2,...,tn
是一个事务（Transaction）集合，其中，每个事物
ti
是一个项目集合，并满足
ti?I
，项目就是类似前言中所说的啤酒和尿布的东西，事务就是同时出现的几个项目的集合。
一个关联规则是一个如下形式的蕴涵关系：

X→Y，其中，X?I,Y?I且X?Y=?

X(或Y)是一个项目的集合，称为项集(Itemset),X称为前件，Y称为后件。
如果项集X是事物
ti∈T
的一个子集,则称
ti
包含X,或称X覆盖
ti
。X在T中的支持计数（表示位
X.count
）是T中包含X的事物的数目。
对于关联规则
X→Y
，有

支持度=(X?Y).countn,其中，n是事物数目


置信度=(X?Y).countX.count

支持度用于衡量一条规则出现得有多频繁，只有出现得足够频繁的规则对我们才有用，比如
啤酒→尿布
。置信度用于衡量从前件推出后件的可行度，类似于概率
P(Y|X)
。值得注意的是，只要一条规则的支持度达到用户要求的最小支持度(minsup)时，我们才去考虑这条规则从前件到后件的置信度。
关联规则挖掘的目标就是，找出事物集合T中所有满足支持度和置信度分别高于用户指定的最小支持度和最小置信度(minconf)的规则。Apriori算法帮我们实现这个目标。

Apriori算法
Apriori算法分为两步：
(1)生成所有频繁项目集：一个频繁项目集(Frequent Itemset)是一个支持度高于minsup的项集。
(2)从频繁项目集中生成所有可信关联规则：一个可信关联规则(Confident Association Rule)是置信度大于minconf的规则。
一个包含k个项目的项集称为k-项集,一个包含k个项目的频繁项目集成为k-频繁项目集。
向下封闭属性：频繁项目集的任何非空子集也是频繁项目集。这个属性很重要，但是很好理解：包含频繁项目集的非空子集的事务数目大于等于包含频繁项目集本身的事务数目。
接下来具体介绍Apriori算法的两步。

频繁项目生成
Apriori算法假定I中的项目都采用字典序排列。在算法中涉及的每个项集也都假定始终保持这个顺序。
算法伪代码如下：

其中，
Ck
是候选k-频繁项目集集合，
Fk
是频繁项目集集合，
?kFk
指所有频繁项目集集合的并集。其中，
candidate?gen(Fk?1)
的伪代码如下：

candidate?gen(Fk)
中需要说明的地方是由
Fk?1
生成
Ck
的方式：两个(k-1)-频繁项目集的前k-2个元素都是一样，只有最后一个元素不同，两个频繁项目集的并集组成一个候选k-频繁项目集。为什么这是可行的？由向下封闭属性可知，如果一个k-项目集是频繁项目集，那么它的任意(k-1)项目子集必定也是频繁项目集，也就是说，它的只有最后一个元素不同的两个(k-1)-频繁项目集必定在
F(k?1)?频繁项目集
中，于是，通过这种方式生成的候选k-频繁项目集包含了所有的k-频繁项目。为什么要选这两个集合呢?可以看到，这样选，容易使得项集保持有序。

关联规则生成
从频繁项目集f中抽取所有关联规则，需要找出f的所有非空子集，然后以使得前件不为空的非空子集作为后件，生成一条关联规则。我们要从这些关联规则找到这样的关联规则：

(f?a)→a，满足置信度=f.count(f?a).count≥minconf

可以看出，当以a为后件时，如果规则满足最小置信度，那么以a的任何非空子集为后件的规则也必定满足最小置信度，因为分母变小了。这也是向下封闭属性。
生成关联规则算法的伪代码如下：

参考资料： 《Web数据挖掘》第2版，Bing Liu 著， 俞勇 译