关联规则中FP树算法的研究与改进

刘冲 陈晓辉 宋小小

桂林理工大学信息科学与工程学院 广西 541004

0 引言

关联规则是一个重要的知识发现(KDD)研究课题，它反映了大量数据中项目集之间有趣的关联或相关联系，经过十多年的发展，目前已经形成了一些较为有影响的挖掘算法，其中以Apriori算法，FP-树算法为代表。Apriori算法通过产生候选频繁项集来挖掘关联规则，人们对其改进做了许多研究工作。2000年左右，J.Han等人提出了一种不产生候选项集的挖掘方法，即FP-树算法。但是，该算法也有一些不足。

传统的FP-树算法主要缺点：(1)建树和挖掘过程都需要占用大量的内存。当数据库很大或者数据库中的频繁1-项集的数目很大时，运行速度将大为降低；更有甚者，可能由于无法构造基于内存的FP树，该算法将不能有效地工作。(2)挖掘大型数据库时，运算速度慢。本文在深入研究 FP-树算法的基础上，提出了一种改进的 FP树算法，新颖的分解方法分解数据库，然后对分解后得到的各个数据库子集进行约束频繁项挖掘来挖掘关联规则的新算法。

1 基本概念

设I={il,i2,……,in}是项的集合，D是数据库事务的集合，其中每一个事务T是项的集合，使得T⊆I。每一个事务有一个标识符，称作 TID。设A是一个项集，事务 T包含A当且仅当A⊆T。关联规则是形如A⇒B的蕴含式，A⊆I，B⊆I，并且A∩B=空集。规则A⇒B在事务集D中成立，具有支持度s，其中s是D中事物包含A∪B的百分比。它是概率P(A∪B)规则A⇒B在事物集D中具有置信度c，如果D中包含A的事务同时也包含B的百分比c。这是条件概率P(B|A)。既是：

s= support(A⇒B)= P(A∪B);

c= confidence(A⇒B)= P(B|A)

同时满足最小支持度阈值(min＿sup)和最小置信度阈值(min＿conf)的规则称为强规则。

项的集合称为项集(itemset)。包含k个项的项集称为k-项集。项集的出现频率是包含项集的事务数，简称为项集的频率，支持度计数或计数。项集满足最小支持度min＿sup，如果项集的出现频率大于或等于min＿sup与D中事务总数的乘积。如果项集满足最小支持度，则称它为频繁项集。频繁k-项集的集合通常计作Lk。

2 FP-树算法

FP-树的主要思想是首先将代表频繁物品集的数据库压缩成一个FP-树，在FP-树中包含了物品的关联信息，然后再将这个被压缩了的数据库分割成一组条件数据库(一类特殊的工程数据库)，每一个条件数据库与一个频繁物品相关联，对每一个这样的数据库进行单独的挖掘。

FP-树算法的发现过程可以总结如下：①对事务数据库D进行第一次扫描，得到项目数为l的频繁集L，同时以该频繁集的支持行数为标准对其进行降序排序；②构造 FP树；③对 FP-树进行数据挖掘，从中挖掘出关联规则。其中，在构造FP-树的过程中，是对D进行第二次扫描，由其中的每一个事务产生一个分枝，而在对每一个事务中的项目进行处理的过程中，是按L的正向顺序进行处理的，而在对FP-树进行数据挖掘的过程中对事务的每一个项目的处理是按L的逆向顺序进行的。

3 改进的FP-树算法

FP-树算法是当前挖掘频繁项集算法中应用最广，并且不需要候选集的一种关联规则挖掘算法。针对该算法的不足，本文在 FP-树算法的基础上提一种采用分解方法分解数据库，然后对分解后得到的各个数据库子集进行约束频繁项挖掘来挖掘关联规则改进的FP-树算法。

改进的FP-树算法是在FP-树算法的基础上提出来的。它的主要思想是在继承 FP-树算法不需要产生侯选项集的优点的基础上，将数据库进行频繁1-项集的项总数次扫描，每次扫描分别得到各个频繁1-项集的项的数据库子集。然后分别对各项数据库子集使用 FP-树算法进行约束频繁项挖掘，得到含有各个频繁1-项集的项的频繁项集，最后将这些频繁项集合并起来便得到整个数据库的所有频繁项集。

3.1 改进的FP-树算法发掘过程

改进的 FP-树算法对数据库分解，约束项挖掘以及频繁项合并的具体过程如下:

输入：事务数据库D；最小支持度阈值min＿sup。

输出：D中的频繁项集。

算法：

(1) 扫描数据库D，找出候选1-项集的集合，并得到它们的支持度计数(频繁性)。然后，按照支持度计数递减排列候选1-项集的各项，得到候选1-项集的集合F。将F中支持度小于最小支持度的项删除，得到频繁 1-项集的集合 L。设L={Im,Im-1,…,13,12,I1}，其中Im的支持度最高，I1的支持度最小。

(2) 再次扫描数据库 D，将支持度小于最小支持度的项从各事务中删除，然后按照各项的支持度计数递减地将各事务中的项进行重新排列，得到数据库为D′。

(3) 根据频繁1-项集L中的各项的支持度计数，按照以下规则由小到大依次构造各项的数据库子集，并利用 FP-树算法对其进行约束频繁项挖掘：

对于L中的每个项Ii(i=m,m-1,…,1)：

第一步：扫描数据库D′，从中提取所有含项Ii的事务，然后，删除这些事务中支持度小于该项的支持度的项，所得事务集合便为项Ii的数据库子集Di。

第二步：对数据库子集D′，利用FP-树算法进行包含项Ii的约束频繁项集挖掘，其挖掘过程如下：

① 利用数据库子集Di，构造FP-树，并创建项头表HT。在这里构造 FP-树时，该数据库子集中各事务项，按照频繁1-项集L中的次序处理。因此，项头表HT中的最后一项所标示就是项Ii的支持度计数及其节点链信息。

② 用项头表HT中的最后一项所标示的信息，构造该项的条件模式基，然后构造其条件 FP-树，就能在该条件 FP-树上挖掘出包含该项的频繁项集CLi，完成在数据库子集Di上的约束频繁项集挖掘。

(4) 当 L中所有的项的约束频繁项集 CLi，被依次挖掘出来后，合并这些约束频繁项集，即取这些约束频繁项集CLi的并集，便可得到数据库D的所有频繁项集，结束挖掘过程。

3.2 实例说明

为了更好地描述该算法，本文通过一个实例来说明改进的FP-树算法的挖掘过程。该实例基于表1所示的事务数据库。该数据库中共有10个事务。设最小支持度为3，即min＿support=30%。

表1 数据库D

首先，对该数据库D进行第一次扫描，找出候选1-项集F的集合及其支持计数。将F中支持度小于最小支持度3的项(I7和I6)删除，得到频繁1-项集L：I3，I2，I4，I5，I1；然后，重新排列该数据库，得到数据库D′如表2所示。

表2 重新得到的数据库D′

其次，根据L中的各项的支持度计数，由小到大构造各项的数据库子集。以L中的项I5为例，项E的数据库子集由含项 I5的四个事务{Tl，T6，T8，T10}组成，且 T6，T8中的最后一个项I1由于其支持度小于项I5的支持度而被删除。项I5和L中其它各项的数据库子集如下所示：

项 I1 的子集：I3，I2，I1；I3，I5，I1；I2，I5，I1

项 I5 的子集：I3，I2，I5；I3，I5；I2，I5；I3，I2，I4，I5

项 I4 的子集：I3，I4；I2，I3，I4；I2，I4；I3，I4；I3，I2，I4；I3，I2，I4

项 I2 的子集：I3，I2；I3，I2；I3，I2；I2；I2；I3，I2；I3，I2；

项I3的子集：I3；I3；I3；I3；I3；I3；I3；I3

再其次，对分解得到的各个子数据集利用 FP-树算法进行约束频繁项挖掘。利用各项的项头表中的最后一项所标示的信息，构造各项的条件模式基，然后构造其条件 FP-树，就能在该条件 FP-树上挖掘出包含各项的约束频繁项集。从实例数据库中挖掘出来的频繁项集及其支持度如表3所示。

表3 挖掘数据库D所得到的频繁项集(min＿support=30%)

4 实验结果及分析

为了进一步验证算法在挖掘大型数据库方面的有效性，实验在 Windows XP的环境，后台数据库采用 SQL Server2O00下进行，并用C#编程分别实现FP-树算法和改进的FP-树算法。表4是从大型通用数据库WebDocs中随机抽取了512M，60万条左右的数据分别在支持度为10%，20%，30%，40%，50%的情况下进行测试所得到的结果。

表4 不同支持度下两种算法挖掘时间

图1 不同支持度下两种算法挖掘时间对比图

由图1和表4分析知，在支持度为10%的时候FP-树算法无法有效挖掘数据库 WebDocs，但改进的 FP-树算法却能成功地挖掘数据库。这是因为 FP-树算法的挖掘过程是将数据库压缩到一棵频繁式树，但仍保留项集关联信息；然后，将这种压缩后的数据库分成一组条件数据库，每个关联一个频繁项，并分别挖掘每个数据库。其优点：算法的运算过简单；对小型数据库行挖掘时，运算速。其缺点：建树时占用内存大大；对大型数据进行挖掘时，FP-树算法无法构造基于内存的FP-树，从而导致挖掘失败。而改进的 FP-树算法的挖掘过程是对数据库进行频繁1-项集项总数次扫描，每次扫描分别得到各个项的数据库子集。然后分别对各项数据库子集使用 FP-树算法进行约束频繁项挖掘，得到含有各个频繁1-项集的项的频繁项集。最后，将这些频繁项集合并起来便得到整个数据库的所有频繁项集。其优点：占用内存小；对大型数据进行挖掘时，运算速度比 FP-树算法快。其缺点：算法的运算过程比较复杂；对小型数据进行发掘时会比FP-树慢；创建子集的开销时间大。

5 结束语

本文在FP-树算法的基础上提出了一种新的适合于大型数据库的关联规则挖掘新算法。新算法采用数据库分解方法将数据库分解，然后对分解得到的各个数据库子集用FP-树算法进行约束频繁项集挖掘。当最小支持度较小，或者数据库很大时，DFP算法由于所采用的数据库划分策略缓解了FP-树算法单独使用时对内存的巨大需求，占用内存小。因而，挖掘速度比FP树算法快，更适合于大型数据库的关联规则挖掘算法。

[1] J.Han,M.Kamber.数据挖掘-概念与技术(影印版).[M]-高等教育出版社.2001.

[2] Jiawei Han,Micheline Kamber.范明,孟小峰等译.数据挖掘概念与技术[M] (第2版).北京.机械工业出版社.2001.

[3] 刘喜苹.基于FP-growth算法的关联规则挖掘算法研究和应用.湖南大学.2006.

[4] 李志云,周国祥.一种基于 MFP树的快速关联规则挖掘算法.计算机技术与发展.2007.

[5] 毛国君,段立娟等.数据挖掘原理与算法.清华大学出版社.2005.

[6] 李志云,周国祥.基于 FP-Growth的关联规则挖掘算法研究.全国第18届计算机科学与技术应用学术会议论文集.2007.