郝天鵬　王斌

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

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

1概述

數(shù)據(jù)挖掘技術(shù)用于處理存儲在數(shù)據(jù)倉庫中的非常大量的數(shù)據(jù)數(shù)據(jù)庫，找出所需的有用知識和信息?，F(xiàn)在，許多數(shù)據(jù)挖掘技術(shù)已經(jīng)被提出來了，如關(guān)聯(lián)規(guī)則、決策樹、神經(jīng)網(wǎng)絡(luò)等。并且該技術(shù)已經(jīng)成為人們關(guā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的表達式，其中x是前項，y是結(jié)果。關(guān)聯(lián)規(guī)則表示在x已經(jīng)發(fā)生的條件下，y發(fā)生的次數(shù)的支持度和置信度。這段時間內(nèi)很多生成關(guān)聯(lián)規(guī)則算法被提出來。眾所周知的算法是Apriori算法和FP-growth算法。

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

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

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