关联规则挖掘频繁项算法的应用

（徐州医药高等职业学校，江苏徐州，221116）

关联规则挖掘频繁项算法的应用

吕淑玲

（徐州医药高等职业学校，江苏徐州，221116）

关联规则在数据挖掘中是一种简单但很实用的规则，Apriori算法和FP-Growth算法是关联规则中的典型算法，本文介绍了关联规则和两种典型算法的概念，利用实例对比两种算法在挖掘频繁项集中的区别，分析算法的优劣，从而确定算法的应用。

关联规则；频繁项；Aprior算法；FP-Growth算法

关联规则挖掘是在海量数据上进行的。频繁项集的产生需要访问数据库中所存储的大量数据，用什么算法迅速高效地在数据集中找出所有的频繁项集是数据挖掘的核心问题。现给定一个任务用两种算法举例对比：

例：事务数据库中，包含有十个事务，已知最小支持度为30%，根据支持度的定义得到，最小支持数=事务数×最小支持度=10×30%=3。

1 Apriori法举例，过程如下

（1）对数据库进行浏览，计算每个1-项集的支持数，得到候选1-项集C1，将候选1-项集的支持数与最小支持数3比较，将大于或等于3的项集保留，得到频繁1-项集F1

（2）对频繁1-项集进行自连接和剪枝运算，得到候选2-项集。

①连接：项集{A}分别与{B}、{C}、{D}、{E}连接后组成新的项集；项集{B}分别与{C}、{D}、{E}连接后组成新的项集；项集{C}分别与{D}、{E}连接后组成新的项集；项集{D}与{E}连接后组成新的项集。

②剪枝：依据频繁项集的所有子集都是频繁的，对产生的每个项集进行判断，本例中所得到的所有项集都满足此要求。

（3）浏览事务数据库，得出每个候选2-项集的支持数。

（4）与最小支持数3比较，保留支持数大于或等于3的频繁项集，去掉支持数小于3的非频繁项集，得到频繁2-项集F2。

（5）对频繁2-项集F2进行自连接和剪枝运算，得到候选3-项集。

自连接：为了避免重复，将项集中的内容按字典顺序排序，当两个项集中前面的项都相同，而只有最后一项不同时，才进行连接。例如，项集{A,B}和项集{A,C}，第一项相同（都是A），而第二项却不同，这时将两项连接后组成一个新的3-项集{A,B,C}。但是项集{A,B}和{B,C}的第一项不同，就不进行连接，这样可以避免产生重复项集{A,B,C}。对频繁2-项集进行自连接后，得到结果。

2 FP-Growth算法举例，过程如下

（1）扫描事务数据库，得到频繁1-项集，并将频繁1-项集按支持数从大到小排序，对于支持数相同的按字典顺序排序。

（2）构造FP树

①建立树的根结点，用null代表。

②读入第一个事分T01,按DBCAE的次序对事务中所包含的项进行排序，得到{D,B,C,A},创建标记为D、B、C、A的结点，形成路径null→D→B→C→A,将路径上结点的计数值设为1。

③读入第二个事务T02，对各项进行排序，得到{D,B,C},由于路径null→D→B→C与第一个事务的路径前部分相同，所以，这里不再增加新结点，而是将D、B、C各个结点的计数值自动加1进行更新。

依次读入第十个事务T10，得到与事务数据库对应的FP树。

（3）利用FP树得到全部的频繁项集

对构造的FP树，采用分而治之的策略，根据项集支持数从小到大的顺序，依次对E、A、C、B、D构造条件FP树，从而找到全部的频繁项集。

①首先，发现以E结尾的频繁项集。

a.收集包含E的所有路径，这些路径称为前缀路径。

b.遍历E结点，对支持数进行累加，得到E的支持数5，5大于等于最小支持数3成立，所以{E}是频繁项集。

c.构造E的条件FP树。

更新前缀路径上的支持数，因为某些计数中包含有那些不含项E的事务，因此，必须将该路径上的结点D、B、C的计数信息进行修改，以反映真实的事务数。给出了修改了支持数之后包含E的前缀路径。

②删除结点E，修剪前缀路径，因为发现以AE、CE、BE、DE结尾的频繁项集的问题不再需要E的信息。

③结点C只出现2次，它的支持数为2，说明只有2个事物包含CE。由于最小支持数为3，因此{C、E}是非频繁的。因为以CE结尾的项集一定也是非频繁的，所在以其后的分析中可以忽略C。这样得到E的条件FP树。

（4）利用E的条件FP树，得到以E结尾的频繁项集。

为了发现以AE结尾的频繁项集，从E的条件FP树中得到结点A的所有前缀路径，此时与E的条件FP树相同，通过把与结点A相关联的计数值累加求和，得到{A、E}的支持数3，该值大于等于最小支持数3的要求，所以{A、E}是频繁项集。按照前面介绍的方法，更新支持度计数，去掉结点A，并删除非频繁项B之后，得到AE的条件FP树。在AE的条件FP树中，只包含一个结点D，且支持数3满足最小支持数的要求，所以{D、A、E}是频繁项集。

先从E的条件FP树中得到B的所有前缀路径，得到频繁项集{B、E}，再构造BE的条件FP树，得到频繁项集{D、B、E}。最后，发现以DE结尾的频繁项集{D、E}。

至此，我们已经得到了以E结尾的所有频繁项集。同样，我们可以得到A、C、B、D的频繁项集。

为了避免重复，Apriori采用了自连接和剪枝技术；为了提高访问数据库的效率，又采用了Hash树求解候选项集的支持数。尽管如此对海量数据库来说，这个算法还存在不尽人意的地方。

FP-Growth算法即频繁模式树增长算法（frequent pattern tree growth），是一种新的挖掘频繁项集的算法。该算法中引入FP树和条件FP树的概念，利用FP树将事务数据库中的所有事物实现压缩存储，利用条件FP树得到频繁项集。在FP-Growth算法中只需要对数据库进行两次扫描，一次是为了得到频繁1-项集，一次是为了建立FP树。扫描数据库的次数要远远小于Apriori算法。与Apriori算法通过候选项集来产生频繁项集不同，FP算法并不产生候选项集，而是利用了条件FP树直接生成频繁项集，在大数据挖掘中，大大提高了工作效率。

Association rule mining algorithm for frequent item Applications

Lv Shuling
（Xuzhou pharmaceutical higher vocational schools，Xuzhou，Jiangsu，221116）

The association rule in data mining is a simple but very practical rule,Apriori algorithm and FP-Growth algorithm is a typical association rules algorithm, this paper introduces the concept of association rules and two typical algorithms,use two examples contrast algorithms in mining frequent item set difference, the pros and cons analysis algorithm to determine the application of the algorithm.

association rule；frequent item；Aprior algorithm；FP-Growth algorithm

吕淑玲（1974-），女，硕士，讲师，研究方向关联规则算法的应用。