FPGrowth關(guān)聯(lián)算法

前言：本站為你精心整理了FPGrowth關(guān)聯(lián)算法范文，希望能為你的創(chuàng)作提供參考價值，我們的客服老師可以幫助你提供個性化的參考范文，歡迎咨詢。

摘要關(guān)聯(lián)規(guī)則挖掘用于從大量數(shù)據(jù)中揭示項集之間的有趣關(guān)聯(lián)或相關(guān)聯(lián)系，是數(shù)據(jù)挖掘的一項重要研究內(nèi)容。本文首先對FP-Growth算法進(jìn)行分析，然后運用該算法分析聚類結(jié)果中的學(xué)生簇與該簇學(xué)生所具有因素的關(guān)聯(lián)關(guān)系，實踐證明了該算法具有較強的實用性。

關(guān)鍵詞數(shù)據(jù)挖掘；關(guān)聯(lián)分析；頻繁模式；FP-Tree

1引言

關(guān)聯(lián)規(guī)則(AssociationRules)挖掘是數(shù)據(jù)挖掘研究領(lǐng)域的一個重要研究方向，它由美國IBMAlmadenResearchCenter的RakeshA-Grawal等人于1993年首先提出，是描述數(shù)據(jù)庫中數(shù)據(jù)項之間存在的一些潛在關(guān)系的規(guī)則。

2關(guān)聯(lián)分析概念

設(shè)I={I1，I2，…，Im}是項的集合，D={T1，T2，…，Tn}是一個事務(wù)數(shù)據(jù)庫，其中每個事務(wù)T是項的集合，使得TI。每個事務(wù)有一個標(biāo)識符，稱為TID。如果I的一個子集X滿足XT，則稱事務(wù)T包含項目集X。一個關(guān)聯(lián)規(guī)則就是形如X=Y的蘊涵式，XI、YI、X∩Y=。

規(guī)則XY在交易數(shù)據(jù)庫中的支持度(support)就是交易集中包含X和Y的交易數(shù)與所有交易數(shù)之比，記為support(XY)，即support(XY)=┃{T：X∪YT，TD}┃/┃D┃。

規(guī)則X=Y在交易數(shù)據(jù)庫中的置信度(confidence)是指包含X和Y的交易數(shù)與包含X的交易數(shù)之比，記為confidence(X=Y)，即confidence(X=Y)=┃{T：X∪YT，T∈D}┃/┃{T：XT，T∈D}┃。

支持度和置信度是描述關(guān)聯(lián)規(guī)則的兩個重要概念，前者用于衡量關(guān)聯(lián)規(guī)則在整個數(shù)據(jù)集中的統(tǒng)計重要性，后者用于衡量關(guān)聯(lián)規(guī)則的可信程度。一般來說，只有支持率和置信度均較高的關(guān)聯(lián)規(guī)則才可能是用戶感興趣、有用的關(guān)聯(lián)規(guī)則。

關(guān)聯(lián)規(guī)則的挖掘是一個兩步的過程：

(1)找出所有的頻繁項集：根據(jù)定義，這些項集出現(xiàn)的頻繁性至少等于預(yù)定義的最小支持度計數(shù)。

(2)由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則：根據(jù)定義，這些規(guī)則必須滿足最小支持度和最小置信度。

在以上兩個步驟中，第二步較容易，挖掘關(guān)聯(lián)規(guī)則的總體性能由第一步?jīng)Q定。

3FP-Growth關(guān)聯(lián)算法分析

針對經(jīng)典關(guān)聯(lián)Apriori算法的固有缺陷，產(chǎn)生了候選挖掘頻繁項集的方法—FP-Growth算法。FP-Growth算法采用分而治之的策略，在經(jīng)過第一遍掃描之后，把數(shù)據(jù)庫中的頻繁項集壓縮到一棵頻繁模式樹(FP-Tree)，同時依然保留其中的關(guān)聯(lián)信息，隨后再將FP-Tree分化成一些條件數(shù)據(jù)庫，每個條件數(shù)據(jù)關(guān)聯(lián)一個頻繁項，然后再分別對這些條件庫進(jìn)行挖掘。FP-Growth算法將發(fā)現(xiàn)長頻繁模式的問題轉(zhuǎn)換為遞歸地發(fā)現(xiàn)一些短模式，然后連接后綴。它使用最不頻繁的項作為后綴，提供了好的選擇性。FP-Growth算法核心思想如下所示：

輸入：事務(wù)數(shù)據(jù)庫D；最小支持度閾值min_sup。

輸出：頻繁模式的完全集。

方法：

(1)構(gòu)造FP-Tree。

①掃描事務(wù)數(shù)據(jù)庫D一次。收集頻繁項的集合F和它們的支持度。對F按支持度降序排序，結(jié)果為頻繁項表L。

②創(chuàng)建FP-Tree的根節(jié)點，以“NULL”標(biāo)記它。對于D中每個事務(wù)Trans，執(zhí)行：選擇Trans的頻繁項，并按照L中的次序排序。設(shè)排序后的頻繁項表為[p|P]，其中p是第一個元素，而P是剩余元素的表。調(diào)用insert_tree([p|P]，T)。該過程執(zhí)行過程如下：如果T有子女N使得N.item-name=p.item-name，則N的計數(shù)增加1，否則創(chuàng)建一個新節(jié)點N，將其計數(shù)設(shè)置為1，鏈接到它的父節(jié)點T，并且通過節(jié)點鏈結(jié)構(gòu)將其鏈接到具有相同item-name的節(jié)點。如果P非空，遞歸地調(diào)用insert_tree(P，N)。

(2)通過調(diào)用FP-Growth(FP-Tree，null)實現(xiàn)FP-Tree的挖掘。該過程實現(xiàn)如下：

ProcedureFP-Growth(Tree，α)

①ifTree含單個路徑Pthen

②for路徑P中節(jié)點的每個組合(記作β)

③產(chǎn)生模式β∪α，其支持度support=β中節(jié)點的最小支持度；

④elseforeachαi在Tree的頭部{

⑤產(chǎn)生一個模式β=αi∪α，其支持度support=αi.support；

⑥構(gòu)造β的條件模式基，然后構(gòu)造β的條件FP-Treeβ；

⑦ifTreeβ≠then

⑧調(diào)用FP-Growth(Treeβ，β)；}

對FP-Tree方法的性能研究表明：對于挖掘長和短的頻繁模式，它都是有效和可伸縮的，并且比Apriori方法快了1個數(shù)量級。

4應(yīng)用實現(xiàn)

本文主要是將FP-Growth算法應(yīng)用到我校學(xué)生成績數(shù)據(jù)庫中，在學(xué)生成績聚類的基礎(chǔ)上對學(xué)生成績的聚類簇與學(xué)生的內(nèi)外部因素進(jìn)行關(guān)聯(lián)分析。

4.1關(guān)聯(lián)分析目標(biāo)

目前我校面對的教務(wù)處學(xué)生成績數(shù)據(jù)庫是一個多維的關(guān)系數(shù)據(jù)庫，我們急切需要從這些海量數(shù)據(jù)中發(fā)現(xiàn)潛在的有用信息來幫助教學(xué)部門掌握更多的學(xué)生信息。基于此，根據(jù)學(xué)生的成績信息對學(xué)生聚類，這些聚類信息反映了學(xué)生學(xué)習(xí)成績的升降起伏等學(xué)習(xí)情況，結(jié)合學(xué)生的聚類信息與學(xué)生因素調(diào)查表信息，采用關(guān)聯(lián)挖掘技術(shù)分析每一類學(xué)生的學(xué)生成績與其內(nèi)外部因素間的關(guān)聯(lián)信息，進(jìn)而分析得到影響學(xué)生學(xué)習(xí)的因素。4.2算法實現(xiàn)

定義頻繁節(jié)點結(jié)構(gòu)，用以構(gòu)造頻繁一次項的降序排列

typedefstructItemCode//SortItem

{

intCount；//頻繁度

intPosition；//排序位置

ItemCode*Next；//下一個節(jié)點的地址

CStringData；//節(jié)點值

}ItemCode；

ItemCode*GetItem(CStringTableName，intSupport，intNumber，intCluNum)；//由數(shù)據(jù)庫得到未排序頻繁一項集節(jié)點鏈，并返回首節(jié)點；

voidGetSortItem(ItemCode*pHeadItem)；//對頻繁一項集排序；

voidCreateFPTree(CStringTableName，CTreeCtrl&TempTree，CTreeCtrl&TreeCopy，boolSort，intNumber，intCluNum)；//按照頻繁項排序建立FP-Tree；

voidGetFPItem(CTreeCtrl&TempTree，CListBox&LBox，intSupport，intNumber，intCluNum)；//按Support的支持度對TempTree的FP-Tree進(jìn)行關(guān)聯(lián)分析，得到頻繁項顯示在LBox；

voidSaveResultToDB()；//保存頻繁項集結(jié)果到數(shù)據(jù)庫；

voidComputeAssociate(intNumber，intCluNum)；//計算關(guān)聯(lián)結(jié)果的相關(guān)分析值；

voidShowInChart(CActiveFrmChart&Chart，intNumber，intCluNum，intIndex)；//將挖掘結(jié)果顯示在Chart中；

4.3挖掘結(jié)果

為了深入了解學(xué)生所處的內(nèi)外部因素對學(xué)生成績的影響，將分別對每個簇的學(xué)生所處的內(nèi)外部因素進(jìn)行關(guān)聯(lián)挖掘，以獲取每個簇學(xué)生所處內(nèi)外部因素間的關(guān)聯(lián)關(guān)系，分別對每個簇學(xué)生的內(nèi)外部因素采用FP-Growth改進(jìn)算法進(jìn)行關(guān)聯(lián)挖掘，因為支持度計數(shù)是與問題域相關(guān)的，用戶可選擇不同的支持度計數(shù)實驗，我們在這里支持度計數(shù)選取為5。

部分簇構(gòu)造FP-Tree如圖1所示，因篇幅有限，只列舉有代表意義的關(guān)聯(lián)項。

圖1生成的FP-Tree(灰色是頻繁項)

5結(jié)束語

對該算法的研究和應(yīng)用可以看出算法具有很強的實用性。本文對關(guān)聯(lián)挖掘中支持度、置信度的選擇沒有進(jìn)行深入的研究，因為對于一組給定的樣本，由于缺乏經(jīng)驗或具體的問題域不同等其它原因?qū)е率孪炔荒芎侠淼貙垲悢?shù)目K、支持度、置信度的取值，這是一個比較棘手的問題，目前關(guān)于這方面研究的資料文獻(xiàn)較少，因此將此問題作為下一步研究的方向具有重要的現(xiàn)實意義。

參考文獻(xiàn)

[1][加]JiaweiHanMichelineKamber，范明，孟小峰等譯.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機械工業(yè)出版社，2001.

[2]顏躍進(jìn)，李舟軍，陳火旺.基于FP-Tree有效挖掘最大頻繁項集[J].軟件學(xué)報，2005，16(2)：215-222.

[3]易彤，徐寶文，吳方君.一種基于FP樹的挖掘關(guān)聯(lián)規(guī)則的增量更新算法[J]計算機學(xué)報2004.5

[4]胡向前，基于FP-Tree的多層關(guān)聯(lián)規(guī)則挖掘算法研究[D]重慶大學(xué)碩士學(xué)位論文2005.5