改進(jìn)的FP—growth關(guān)聯(lián)規(guī)則挖掘算法

郝天鵬　王斌

摘要：數(shù)據(jù)挖掘技術(shù)被廣泛用于處理存儲(chǔ)在數(shù)據(jù)庫中的大量數(shù)據(jù)，以提取所需的信息。其有多種獲取數(shù)據(jù)的技術(shù)，關(guān)聯(lián)規(guī)則挖掘是其中最有效的數(shù)據(jù)挖掘技術(shù)之一。它從大量數(shù)據(jù)中發(fā)現(xiàn)隱藏的所需數(shù)據(jù)模式。在現(xiàn)有技術(shù)中的頻繁模式生長(zhǎng)（FP-growth）算法是找到期望關(guān)聯(lián)規(guī)則的最有效的算法，它只需掃描數(shù)據(jù)庫兩次進(jìn)行處理。但FP-growth算法的問題是在大規(guī)模數(shù)據(jù)環(huán)境下它生成大量的條件Fp樹，造成挖掘效率低下的問題。在提出算法中，我們?cè)O(shè)計(jì)了一種新技術(shù)，它挖掘出所有的頻繁項(xiàng)集，而不產(chǎn)生條件Fp樹。與傳統(tǒng)FP-growth算法不同，它僅掃描數(shù)據(jù)庫一次，這降低了算法的時(shí)間效率。并且找出頻繁項(xiàng)集合的頻率，以獲取所需的關(guān)聯(lián)規(guī)則。實(shí)驗(yàn)證明，改進(jìn)FP-growth算法的效率較傳統(tǒng)FP-growth算法有很大提高。

關(guān)鍵詞：FP樹；關(guān)聯(lián)規(guī)則；頻繁項(xiàng)集；數(shù)據(jù)挖掘

1概述

數(shù)據(jù)挖掘技術(shù)用于處理存儲(chǔ)在數(shù)據(jù)倉庫中的非常大量的數(shù)據(jù)數(shù)據(jù)庫，找出所需的有用知識(shí)和信息?，F(xiàn)在，許多數(shù)據(jù)挖掘技術(shù)已經(jīng)被提出來了，如關(guān)聯(lián)規(guī)則、決策樹、神經(jīng)網(wǎng)絡(luò)等。并且該技術(shù)已經(jīng)成為人們關(guān)注的焦點(diǎn)。數(shù)據(jù)挖掘中最著名的技術(shù)之一便是關(guān)聯(lián)規(guī)則挖掘。這是最高效的數(shù)據(jù)挖掘技術(shù)。它從大型數(shù)據(jù)庫中發(fā)現(xiàn)隱藏模式，并找到數(shù)據(jù)中不同屬性之間的關(guān)系。

關(guān)聯(lián)規(guī)則首先被R.Agrawal等人提出。規(guī)則用于得到用戶輸入數(shù)值的支持度和置信度。關(guān)聯(lián)規(guī)則通常是形式x-y的表達(dá)式，其中x是前項(xiàng)，y是結(jié)果。關(guān)聯(lián)規(guī)則表示在x已經(jīng)發(fā)生的條件下，y發(fā)生的次數(shù)的支持度和置信度。這段時(shí)間內(nèi)很多生成關(guān)聯(lián)規(guī)則算法被提出來。眾所周知的算法是Apriori算法和FP-growth算法。

Apriori算法是用于關(guān)聯(lián)規(guī)則挖掘的最熟知的算法之一。R.Agrawal提出了Apfiofi算法來挖掘數(shù)據(jù)集中的頻繁模式，算法搜索過程是由連接和剪枝兩部分組成，利用一層一層搜索的迭代方法來找出數(shù)據(jù)庫中項(xiàng)目集的關(guān)系來形成規(guī)則。但由于該算法有反復(fù)掃描數(shù)據(jù)庫和產(chǎn)生大量候選項(xiàng)集的缺點(diǎn)。于是提出FP-growth算法，該算法的優(yōu)勢(shì)表現(xiàn)為挖掘全部頻繁項(xiàng)集卻不產(chǎn)生大量候選集。晏杰，亓文娟提出的基于Apriori&FP-growth算法的研究。對(duì)Apriori算法和FP-growth具體執(zhí)行過程進(jìn)行了展示，并提出各自算法的優(yōu)缺點(diǎn)，最后通過實(shí)驗(yàn)展示性能上的差別。

FP-growth（頻繁模式增長(zhǎng)）使用前綴樹（FP-tree）結(jié)構(gòu)的壓縮方式存儲(chǔ)數(shù)據(jù)庫數(shù)據(jù)。FP-growth算法采用分治的策略分兩步來查找數(shù)據(jù)庫的頻繁項(xiàng)集。首先將數(shù)據(jù)庫中的項(xiàng)以及關(guān)聯(lián)關(guān)系壓縮到FP樹中，然后它將FP樹分割成更小的條件FP樹然后單獨(dú)挖掘出每個(gè)子樹的頻繁項(xiàng)集。但是隨著大規(guī)模數(shù)據(jù)的產(chǎn)生，F(xiàn)P-growth算法也存在著缺陷，算法將事務(wù)數(shù)據(jù)庫中的所有記錄壓縮進(jìn)一棵樹中（FP-tree）。如果數(shù)據(jù)庫很大時(shí)，構(gòu)造基于內(nèi)存的FP-tree是不現(xiàn)實(shí)的。因此，F(xiàn)P-growth算法在挖掘大型數(shù)據(jù)集時(shí)可能導(dǎo)致失敗。對(duì)此缺點(diǎn)Krishna等人提出了并行處理數(shù)據(jù)庫辦法，通過對(duì)數(shù)據(jù)庫數(shù)據(jù)進(jìn)行分割，各個(gè)分割點(diǎn)單獨(dú)進(jìn)行挖掘，最后將結(jié)果合并。但該算法對(duì)挖掘頻繁模式過程中存在性能瓶頸并沒有改進(jìn)，因此馬月坤等人又提出了改進(jìn)的FP-Growth算法及其分布式并行實(shí)現(xiàn)，他們對(duì)FP-Growth算法進(jìn)行改進(jìn)，通過基于頻繁閉模式項(xiàng)集策略對(duì)完備模式樹進(jìn)行剪枝進(jìn)而減少空間搜索，達(dá)到提高算法挖掘效率。

針對(duì)海量數(shù)據(jù)的挖掘問題，本文提出了改進(jìn)的FP-growth關(guān)聯(lián)規(guī)則挖掘算法。這個(gè)算法的主要優(yōu)點(diǎn)是可以較為容易的得到所有頻繁項(xiàng)目集。其主要特點(diǎn)是僅掃描數(shù)據(jù)庫一次就生成頻繁項(xiàng)集，而不生成任何條件FP樹。