改进的FP—growth关联规则挖掘算法

郝天鹏　王斌

摘要：数据挖掘技术被广泛用于处理存储在数据库中的大量数据，以提取所需的信息。其有多种获取数据的技术，关联规则挖掘是其中最有效的数据挖掘技术之一。它从大量数据中发现隐藏的所需数据模式。在现有技术中的频繁模式生长（FP-growth）算法是找到期望关联规则的最有效的算法，它只需扫描数据库两次进行处理。但FP-growth算法的问题是在大规模数据环境下它生成大量的条件Fp树，造成挖掘效率低下的问题。在提出算法中，我们设计了一种新技术，它挖掘出所有的频繁项集，而不产生条件Fp树。与传统FP-growth算法不同，它仅扫描数据库一次，这降低了算法的时间效率。并且找出频繁项集合的频率，以获取所需的关联规则。实验证明，改进FP-growth算法的效率较传统FP-growth算法有很大提高。

关键词：FP树；关联规则；频繁项集；数据挖掘

1概述

数据挖掘技术用于处理存储在数据仓库中的非常大量的数据数据库，找出所需的有用知识和信息。现在，许多数据挖掘技术已经被提出来了，如关联规则、决策树、神经网络等。并且该技术已经成为人们关注的焦点。数据挖掘中最著名的技术之一便是关联规则挖掘。这是最高效的数据挖掘技术。它从大型数据库中发现隐藏模式，并找到数据中不同属性之间的关系。

关联规则首先被R.Agrawal等人提出。规则用于得到用户输入数值的支持度和置信度。关联规则通常是形式x-y的表达式，其中x是前项，y是结果。关联规则表示在x已经发生的条件下，y发生的次数的支持度和置信度。这段时间内很多生成关联规则算法被提出来。众所周知的算法是Apriori算法和FP-growth算法。

Apriori算法是用于关联规则挖掘的最熟知的算法之一。R.Agrawal提出了Apfiofi算法来挖掘数据集中的频繁模式，算法搜索过程是由连接和剪枝两部分组成，利用一层一层搜索的迭代方法来找出数据库中项目集的关系来形成規则。但由于该算法有反复扫描数据库和产生大量候选项集的缺点。于是提出FP-growth算法，该算法的优势表现为挖掘全部频繁项集却不产生大量候选集。晏杰，亓文娟提出的基于Apriori&FP-growth算法的研究。对Apriori算法和FP-growth具体执行过程进行了展示，并提出各自算法的优缺点，最后通过实验展示性能上的差别。

FP-growth（频繁模式增长）使用前缀树（FP-tree）结构的压缩方式存储数据库数据。FP-growth算法采用分治的策略分两步来查找数据库的频繁项集。首先将数据库中的项以及关联关系压缩到FP树中，然后它将FP树分割成更小的条件FP树然后单独挖掘出每个子树的频繁项集。但是随着大规模数据的产生，FP-growth算法也存在着缺陷，算法将事务数据库中的所有记录压缩进一棵树中（FP-tree）。如果数据库很大时，构造基于内存的FP-tree是不现实的。因此，FP-growth算法在挖掘大型数据集时可能导致失败。对此缺点Krishna等人提出了并行处理数据库办法，通过对数据库数据进行分割，各个分割点单独进行挖掘，最后将结果合并。但该算法对挖掘频繁模式过程中存在性能瓶颈并没有改进，因此马月坤等人又提出了改进的FP-Growth算法及其分布式并行实现，他们对FP-Growth算法进行改进，通过基于频繁闭模式项集策略对完备模式树进行剪枝进而减少空间搜索，达到提高算法挖掘效率。

针对海量数据的挖掘问题，本文提出了改进的FP-growth关联规则挖掘算法。这个算法的主要优点是可以较为容易的得到所有频繁项目集。其主要特点是仅扫描数据库一次就生成频繁项集，而不生成任何条件FP树。