关联规则挖掘算法：Apriori

? ? ?所谓的关联规则（Association Rule）主要是指数据中的并发关系，最典型的的应用就是对购物篮的分析，发现所有的老爸买尿布的时候都会买啤酒。

? ? 关联规则挖掘中有一些容易混淆的术语，详见http://blog.sina.com.cn/s/blog_4d8d6303010009kb.html?，这里有两个很重要的概念：支持度和置信度。通俗的说，支持度就是所有的顾客中有多少顾客买了尿布和啤酒（支持度过低，说明该规则实际中较少出现，没有应用价值）；置信度就是所有买了尿布的顾客中有多少买了啤酒的（置信度过低，说明买尿布就会买啤酒这条规则不太可靠）

? ? Apriori算法的实质十分简单：首先找出所有只包含一个项目的规则，然后合成包含两个项目的规则（中间需要进行剪枝），以此类推。

? ? Aprior算法流程图： ? ?

? ?

?Candidate-gen函数流程图：

? ? 接下来我将用一个实际的例子来描述Apriori算法的过程：

? ? 假设我们要求的最小支持度minsup=30%，最小置信度mincond=80%。再次介绍两个十分重要的术语：

? ? k项频繁集（包含k个项目的支持度公安与minsupde 项目集合）。

? ? 向下闭包属性（Downward Closure Property）这个属性是算法的一个核心，即如果一个项集为频繁项目集，那么它的所有非空子集也是频繁项目集；很明显，若集合{1,2}是频繁项集，那么{1},{2}肯定也是频繁项集（因为包含1,2的交易一定包含1，但包含1的交易不一定包含1,2）。

??

? Apriori算法的第一个主要步骤是使用前一轮产生的频繁项集Fk-1(一般初始化为只含一个项目的频繁集)，通过candidate-gen函数来生成候选项集Ck。这里来介绍一下candidate-gen函数。该函数主要包含合并和剪枝两个步骤。

? ? 合并：就是使用两个(k-1)频繁项集生成k频繁项集，首先注意每个项集里的项目都是按一定顺序排序的，这里要求两个频繁项集的前k-2个项要相同只有最后一个不同。具体来说就是频繁集{1,3}和{1,5}合成{1,3,5}。你一定要问了{1,3}和{3,5}能合成{1,5}吗？答案是不能，因为根据向下闭包原则，如果{1,5}是频繁集那么{1,3}{1,5}{3,5}都是频繁集，想想如果{1,5}是频繁集的话，那么就可以直接用{1,5}来合成{1,5}了，没必要使用{3,5}，所以这里的合并必须要求前k-2项是相同的，只有最后一项是不同的。

? ? 剪枝：就是检查所有候选集Ck的子集是否是频繁集，如果有一个子集不是，则删除Ck。例如前面通过{1,5}产生的{1,5}，如果{3,5}不是频繁集则{1,5}肯定也不是频繁集。

? ? Apriori算法的最后一步就是检查新的候选集合中所有项集的支持度，符合要求的就进行下一轮筛选。

? ?

? 最后讲讲如何根据生成的频繁项集来生产规则。根据Apriori算法生成了频繁项目集f，那么所有的关联规则都可以表示为(f-a) -> a,并且可以继续推断(f-b(b为a的子集）) -> b，必然成立。因为置信度=f.count/(f-a).count，其中a集合越小，f-a集合越大，(f-a).count越小，总的置信度也越大，这就是所谓的数据稀疏原理（越是大的数据集合在实际中出现的次数越小）。生成规则的过程类似于Apriori算法，首先找出频繁集f的所有后件为1的规则，然后利用candidate-gen函数类推，只不过里面是将支持度检验换为置信度检验即可。

? Apriori的一个具体实现的例子：http://www.voidcn.com/article/p-fegckqpk-ub.html