FPGrowth關(guān)聯(lián)算法應(yīng)用研究

1、FP-Growth關(guān)聯(lián)算法應(yīng)用研究摘要關(guān)聯(lián)規(guī)那么挖掘用于從大量數(shù)據(jù)中提醒項(xiàng)集之間的有趣關(guān)聯(lián)或相關(guān)聯(lián)絡(luò)，是數(shù)據(jù)挖掘的一項(xiàng)重要研究?jī)?nèi)容。本文首先對(duì)FP-Grth算法進(jìn)展分析，然后運(yùn)用該算法分析聚類結(jié)果中的學(xué)生簇與該簇學(xué)生所具有因素的關(guān)聯(lián)關(guān)系，理論證明了該算法具有較強(qiáng)的實(shí)用性。關(guān)鍵詞數(shù)據(jù)挖掘；關(guān)聯(lián)分析；頻繁形式；FP-Tree1引言關(guān)聯(lián)規(guī)那么(AssiatinRules)挖掘是數(shù)據(jù)挖掘研究領(lǐng)域的一個(gè)重要研究方向，它由美國(guó)IBAladenResearhenter的RakeshA-Graal等人于1993年首先提出，是描繪數(shù)據(jù)庫中數(shù)據(jù)項(xiàng)之間存在的一些潛在關(guān)系的規(guī)那么。2關(guān)聯(lián)分析概念設(shè)I=I1，I2，I是

2、項(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包含工程集X。一個(gè)關(guān)聯(lián)規(guī)那么就是形如X=Y的蘊(yùn)涵式，XI、YI、XY=。規(guī)那么XY在交易數(shù)據(jù)庫中的支持度(supprt)就是交易集中包含X和Y的交易數(shù)與所有交易數(shù)之比，記為supprt(XY)，即supprt(XY)=T：XYT，TD/D。規(guī)那么X=Y在交易數(shù)據(jù)庫中的置信度(nfidene)是指包含X和Y的交易數(shù)與包含X的交易數(shù)之比，記為nfidene(X=Y)，即nfidene(X=Y)=T：XYT，TD/T：XT，TD。支持度和置信度

3、是描繪關(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-Grth關(guān)聯(lián)算法分析針對(duì)經(jīng)典關(guān)聯(lián)Apriri算法的固有缺陷，產(chǎn)生了候選挖掘頻繁項(xiàng)集的方法FP-Grth算法。FP-

4、Grth算法采用分而治之的策略，在經(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-Grth算法將發(fā)現(xiàn)長(zhǎng)頻繁形式的問題轉(zhuǎn)換為遞歸地發(fā)現(xiàn)一些短形式，然后連接后綴。它使用最不頻繁的項(xiàng)作為后綴，提供了好的選擇性。FP-Grth算法核心思想如下所示：輸入：事務(wù)數(shù)據(jù)庫D；最小支持度閾值in_sup。輸出：頻繁形式的完全集。方法：(1)構(gòu)造FP-Tree。掃描事務(wù)數(shù)據(jù)庫D一次。搜集頻繁項(xiàng)的集合F和它們的支持度。對(duì)F按支持度降序排序，結(jié)果為頻

5、繁項(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.ite-nae=p.ite-nae，那么N的計(jì)數(shù)增加1，否那么創(chuàng)立一個(gè)新節(jié)點(diǎn)N，將其計(jì)數(shù)設(shè)置為1，鏈接到它的父節(jié)點(diǎn)T，并且通過節(jié)點(diǎn)鏈構(gòu)造將其鏈接到具有一樣ite-nae的節(jié)點(diǎn)。假如P非空，遞歸地調(diào)用insert_tree(P，N)。(2)通過調(diào)用FP-Grth(FP-Tree，null)實(shí)現(xiàn)FP-Tree的挖

6、掘。該過程實(shí)現(xiàn)如下：PredureFP-Grth(Tree，)ifTree含單個(gè)途徑Pthenfr途徑P中節(jié)點(diǎn)的每個(gè)組合(記作)產(chǎn)生形式，其支持度supprt=中節(jié)點(diǎn)的最小支持度；elsefreahi在Tree的頭部產(chǎn)生一個(gè)形式=i，其支持度supprt=i.supprt；構(gòu)造的條件形式基，然后構(gòu)造的條件FP-Tree；ifTreethen調(diào)用FP-Grth(Tree，)；對(duì)FP-Tree方法的性能研究說明：對(duì)于挖掘長(zhǎng)和短的頻繁形式，它都是有效和可伸縮的，并且比Apriri方法快了1個(gè)數(shù)量級(jí)。4應(yīng)用實(shí)現(xiàn)本文主要是將FP-Grth算法應(yīng)用到我校學(xué)生成績(jī)數(shù)據(jù)庫中，在學(xué)生成績(jī)聚類的根底上對(duì)學(xué)生成績(jī)的

7、聚類簇與學(xué)生的內(nèi)外部因素進(jìn)展關(guān)聯(lián)分析。4.1關(guān)聯(lián)分析目的目前我校面對(duì)的教務(wù)處學(xué)生成績(jī)數(shù)據(jù)庫是一個(gè)多維的關(guān)系數(shù)據(jù)庫，我們急迫需要從這些海量數(shù)據(jù)中發(fā)現(xiàn)潛在的有用信息來幫助教學(xué)部門掌握更多的學(xué)生信息?；诖?，根據(jù)學(xué)生的成績(jī)信息對(duì)學(xué)生聚類，這些聚類信息反映了學(xué)生學(xué)習(xí)成績(jī)的升降起伏等學(xué)習(xí)情況，結(jié)合學(xué)生的聚類信息與學(xué)生因素調(diào)查表信息，采用關(guān)聯(lián)挖掘技術(shù)分析每一類學(xué)生的學(xué)生成績(jī)與其內(nèi)外部因素間的關(guān)聯(lián)信息，進(jìn)而分析得到影響學(xué)生學(xué)習(xí)的因素。轉(zhuǎn)貼于論文聯(lián)盟.ll.4.2算法實(shí)現(xiàn)定義頻繁節(jié)點(diǎn)構(gòu)造，用以構(gòu)造頻繁一次項(xiàng)的降序排列Itede；4.3挖掘結(jié)果為了深化理解學(xué)生所處的內(nèi)外部因素對(duì)學(xué)生成績(jī)的影響，將分別對(duì)每個(gè)簇的學(xué)

8、生所處的內(nèi)外部因素進(jìn)展關(guān)聯(lián)挖掘，以獲取每個(gè)簇學(xué)生所處內(nèi)外部因素間的關(guān)聯(lián)關(guān)系，分別對(duì)每個(gè)簇學(xué)生的內(nèi)外部因素采用FP-Grth改良算法進(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完畢語對(duì)該算法的研究和應(yīng)用可以看出算法具有很強(qiáng)的實(shí)用性。本文對(duì)關(guān)聯(lián)挖掘中支持度、置信度的選擇沒有進(jìn)展深化的研究，因?yàn)閷?duì)于一組給定的樣本，由于缺乏經(jīng)歷或詳細(xì)的問題域不同等其它原因?qū)е率孪炔荒芎侠淼貙?duì)聚類數(shù)目K、支持度、置信度的取值，這是一個(gè)比擬棘手的問題，目前關(guān)于這方面研究的資料文獻(xiàn)較少，因此將此問題作為下一步研究的方向具有重要的現(xiàn)實(shí)意義。參考文獻(xiàn)1加JiaEiHanihelineKaber，范明，孟小峰等譯.