频繁项集算法分析

一、 什么是频繁项集
项集是指事项的集合，而频繁项集就是频繁出现在数据集中的项集，说白了就在数据集中“出现次数足够多”的项集。
其中，项集的出现频度是指包含项集的事务的数量，简称为项集的频度、支持度计数。如果项集I的支持度计数满足预定义的最小支持度计数阈值，则I是频繁项集。之前提到的“出现次数足够多”的衡量标准就是最小支持度计数阈值。如果频繁项集中共含有k个事项，则称该项集为频繁k项集，频繁k项集的集合通常记为Lk。
这里需要解释一下，事项、项集和事物的区别。已在商场中购物为例，事项代表一个个的商品，项集代表一个或几个商品的集合，而事物代表一次的购物记录。可以发现，项集是由一个或多个事项组成的，事物是由一个或多个项集组成的；事物一定真实发生，但是项集不一定发生，可能只是所在事物中包含的某些事项的集合。
关于频繁项集的一个经典例子是购物篮分析。该过程通过发现顾客放入“购物篮”中的商品之间的关联，分析顾客的购物习惯，以帮助零售商了解哪些商品频繁地被顾客同时购买，从而帮助他们制定更好的营销策略，提高销售量。一个真实的成功案例就是大型超市沃尔玛通过购物篮分析，发现啤酒和尿布常常同时被顾客购买，故将两者摆放在一起进行销售，极大的提高了两者的销售量。
二、 Apriori算法
既然频繁项集如此重要，那怎样找到所有的频繁项集呢？
方法有多种，其中最经典的算法当属1994年Agtawal和R.Srikant提出的Apriori算法，它是一种最有影响的挖掘布尔关联规则频繁项集的算法，算得上是频繁项集挖掘算法的鼻祖，后续很多的改进算法也是基于Apriori算法。
算法原理：Apriori算法使用一种逐层搜索的迭代方法，其中k项集用于搜索（k+1）项集。为了提高频繁项集逐层产生的效率，使用一种称为先验性质（Apriori property，这也是该算法的命名原因）的重要性质，用于压缩搜索空间。它使用的先验形式是：频繁项集的所有非空子集也一定是频繁的，即若P(I)<min_sup，则P(I∪A)<min_sup。
算法步骤：
第一，确定频繁1项集。通过扫描数据库，累计每个项的计数，收集满足最小支持度计数的项，找出频繁1项集的集合L1。
第二，连接步。将Lk-1与自身进行连接，产生候选k项集的集合Ck 。若两个（k-1）项集的前（k-2）个项相同，则Lk-1的元素是可连接的。
第三，剪枝步。使用先验性质，压缩Ck：任何非频繁的（k-1）项集都不是频繁k项集的子集，也就是删除任一子集不在Lk-1的候选项集。然后扫描数据库，确定中Ck每个候选项集的计数，筛选出频繁k项集的集合Lk。
第三步的目的是删除频度小于最小支持度计数阈值的项集，需要扫描数据库，确定每个候选k项集的计数，这个开销会很大，所以先使用先验性质去除部分不合要求的候选项集，提高算法的效率，这就是Apriori算法的最主要的特点。
下面用一个具体的例子详细介绍算法的过程。
假设有个数据库D，其中有4个事务记录，分别表示为：

假设最小支持度计数为2，即min_sup=2。



由L3产生的C4为空，算法终止，我们找到了所有的频繁项集。
从算法的运行过程中，可以看到Apriori算法的优缺点：
优点：简单、易理解、数据要求低
缺点：(1)在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素;(2)每次计算项集的支持度时，都对数据库D中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系统的I/O开销。
三、 算法改进
1. FP-growth算法
一种不产生候选模式而采用频繁模式增长的方法挖掘频繁模式的算法。FP树挖掘由两个阶段组成:第一阶段建立FP树，即将数据库中的事务构造成一棵FP树；第二阶段为挖掘FP树，即针对FP树挖掘频繁模式和关联规则。它将发现长频繁模式的问题转换成在较小的条件数据库中递归地搜索一些较短的模式，然后连接后缀。
2. 使用垂直数据格式挖掘频繁项集
由水平数据格式等价变换为垂直数据格式，水平数据格式表示每个事务对应其包含的具体的项，垂直数据格式表示为每个具体的项集对应包含该项集的事务。如下图：

垂直数据格式有利于使用先验性质，因为每个项集的计数就是包含该项集的事务的个数，即右侧栏目数据的个数，所以不需要扫描数据库来确定（k+1）项集的支持度，提高运算效率。

参考文献：
[1]范明，孟小峰译.数据挖掘概念与技术第三版[M].机械工业出版社,2014,157-170.
[2]晏 杰, 亓文娟.基于Aprior & FP-growth 算法的研究. 计算机系统应用22.5 (2013): 120-125.
[3] http://blog.csdn.net/viewcode/article/details/9122789