vlambda博客
学习文章列表

关联规则是数据分析与挖掘中常用的一类技术。关联规则最经典的一个应用例子是“啤酒与尿布”的故事，想必大家在学习这类方法的时候都听过。而在实际使用中，关联规则最常见的算法主要包括三种：Apriori算法、FP-growth算法和Eclat算法，下面对这三类算法进行介绍。

1、Apriori算法

（1）概念：Apriori算法是一种通过频繁项集来挖掘关联规则的算法。该算法既可以发现频繁项集，又可以挖掘物品之间关联规则。分别采用支持度和置信度来量化频繁项集和关联规则。其核心思想是通过候选集生成和情节的向下封闭检验检测两个阶段来挖掘频繁项集。

其最常见的改进算法为AprioriTid算法，该改进算法与原算法的主要区别在于对数据集的更新方式不一样。当数据量较大时，使用改进算法得到的新数据集会比原始数据集小很多，这样在进行遍历的时候就节省了很多时间。

（2）特点

[1] 该算法的关联规则关联规则是在频繁项集基础上产生的，这可以保证这些规则的支持度达到指定的水平，具有普遍性和令人信服的水平；

[2] 每次计算项集的支持度的时候，都对数据库中的全部数据进行了一遍扫描比较，I/O负载很大。

（3）算法流程

Step 1 输入数据集X；

Step 2 确定数据集X中所包含的项集，并具体化到每一个数据点（即每一个中所包含的变量示性情况）；

Step 3 进行第一次迭代，把每个项集中的项目单独扫描统计（即某个项在多少个数据点中出现了），将每个项都作为候选1-项集的成员，并计算每个项的支持度；

Step 4 设定最小支持度，根据候选1-项集的成员、支持度和最小支持度，采用扫描过滤的方式得候选2-项集，候选项集需满足所有真子集的支持度都≥最小支持度；

Step 5 保持最小支持度不变，重复进行第四步，直到没有办法再合并（即候选项集无法满足条件），形成新的候选项集，此时输出最终的频繁项集结果，并给出关联规则。

2、FP-growth算法

（1）概念：FP-growth算法是将数据集存储在一个特定的称作FP树的结构，然后从FP树中发现频繁项集。FP-growth算法比Apriori算法效率更高，在整个算法执行过程中，只需遍历数据集2次，就能够完成频繁项集的发现。FP-tree是一种特殊的前缀树，由频繁项头表和项前缀树构成。FP-Growth算法基于以上的结构可以加快整个挖掘过程。

（2）特点

[1] 在使用FP-growth算法时，只能用来发现频繁项集，不能用来寻找关联规则；

[2] 对于FP-growth算法来说，其发现频繁集的效率比较高，而Apriori算法要对于每个潜在的频繁项集都会扫描数据集来判定是否频繁，FP-growth算法只需要对数据集进行两次扫描。这种算法的执行速度要快于Apriori，通常性能要好两个数量级以上；

[3] 该算法基于Apriori算法构建，在完成相同任务的时候采用了一些不同技术。

（3）算法流程

Step 1 先扫描一遍数据集，得到频繁项为1的项目集，定义最小支持度（项目出现最少次数），删除那些小于最小支持度的项目，然后将原始数据集的条目按项目集中降序进行排列； 

Step 2 第二次扫描，创建项头表（从上往下降序），以及FP树；

Step 3 对于每个项目（可以按照从下往上的顺序）找到其条件模式基并递归调用树结构，删除小于最小支持度的项。如果最终呈现单一路径的树结构，则直接列举所有组合，非单一路径的则继续调用树结构，直到形成单一路径即可。

3、Eclat算法

（1）概念：Eclat算法是一种深度优先算法。Eclat算法不同于关联规则中的Apriori和FP-growth算法，后两者所采用的的是从TID项集格式的事物集中挖掘频繁项集的水平数据结构的方式，而Eclat算法采用了垂直数据表示的方法，将数据按照项集存储。该储存中，每条记录包括一个项集标识和包含它的事务标识。这样k+1阶项集的支持度可以直接由它的两个k阶子集的交易标识的集合运算得到。Eclat算法最大的特点便是倒排思想，也就是生成一个统计每一个项在哪些事务中出现过的倒排表，表中的每一行由项和它对应的TID集组成，TID集即包含此项目的所有事务的集合。

（2）特点

[1] 采用了与传统挖掘算法不同的垂直数据库结构，由于这样只要扫描两次数据库，大大减少了挖掘规则所需要的时间，从而提高了挖掘关联规则的效率；

[2] 该算法没有对产生的候选集进行删减操作，若项目出现的频率非常高，频繁项集庞大，进行交集操作时会消耗系统大量的内存，影响算法的效率。

（3）算法流程

Step 1 通过扫描一次数据集，把水平格式的数据转换成垂直格式；

Step 2 根据分析的要求，设定项集的支持度计数；

Step 3 从k=1开始，可以根据先验性质，使用频繁k项集来构造候选k+1项集；

Step 4 通过取频繁k项集的TID集的交，计算对应的k+1项集的TID集；

Step 5 重复该过程，直到不能再找到频繁项集或者候选项集。

4、实际应用选择

（1）数据集较小且需要产生明确的关联规则：使用Apriori算法。

（2）数据集较小且只需要挖掘频繁项集：使用FP-growth算法。

（3）数据集较大：使用Eclat算法。

广告区↓