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

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

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

1引言

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

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

設(shè)I={I1，I2，…，Im}是項(xiàng)的集合，D={T1，T2，…，Tn}是一個(gè)事務(wù)數(shù)據(jù)庫，其中每個(gè)事務(wù)T是項(xiàng)的集合，使得TI。每個(gè)事務(wù)有一個(gè)標(biāo)識(shí)符，稱為TID。如果I的一個(gè)子集X滿足XT，則稱事務(wù)T包含項(xiàng)目集X。一個(gè)關(guān)聯(lián)規(guī)則就是形如X=Y的蘊(yùn)涵式，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ī)則的兩個(gè)重要概念，前者用于衡量關(guān)聯(lián)規(guī)則在整個(gè)數(shù)據(jù)集中的統(tǒng)計(jì)重要性，后者用于衡量關(guān)聯(lián)規(guī)則的可信程度。一般來說，只有支持率和置信度均較高的關(guān)聯(lián)規(guī)則才可能是用戶感興趣、有用的關(guān)聯(lián)規(guī)則。

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

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

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

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

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

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

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

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

方法：

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

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

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

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

ProcedureFP-Growth(Tree，α)

①ifTree含單個(gè)路徑Pthen

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

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

④elseforeachαi在Tree的頭部{

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

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

⑦ifTreeβ≠then

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

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

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

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

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

目前我校面對(duì)的教務(wù)處學(xué)生成績數(shù)據(jù)庫是一個(gè)多維的關(guān)系數(shù)據(jù)庫，我們急切需要從這些海量數(shù)據(jù)中發(fā)現(xiàn)潛在的有用信息來幫助教學(xué)部門掌握更多的學(xué)生信息?；诖?，根據(jù)學(xué)生的成績信息對(duì)學(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算法實(shí)現(xiàn)

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

typedefstructItemCode//SortItem

{

intCount；//頻繁度

intPosition；//排序位置

ItemCode*Next；//下一個(gè)節(jié)點(diǎn)的地址

CStringData；//節(jié)點(diǎn)值

}ItemCode；

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

voidGetSortItem(ItemCode*pHeadItem)；//對(duì)頻繁一項(xiàng)集排序；

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

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

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

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

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

4.3挖掘結(jié)果

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

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

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

5結(jié)束語

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

參考文獻(xiàn)

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

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

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

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