FPGrowth關聯(lián)算法應用研究

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

2、項的集合，D=T1，T2，Tn是一個事務數(shù)據(jù)庫，其中每個事務T是項的集合，使得TI。每個事務有一個標識符，稱為TID。假如I的一個子集X滿足XT，那么稱事務T包含工程集X。一個關聯(lián)規(guī)那么就是形如X=Y的蘊涵式，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、是描繪關聯(lián)規(guī)那么的兩個重要概念，前者用于衡量關聯(lián)規(guī)那么在整個數(shù)據(jù)集中的統(tǒng)計重要性，后者用于衡量關聯(lián)規(guī)那么的可信程度。一般來說，只有支持率和置信度均較高的關聯(lián)規(guī)那么才可能是用戶感興趣、有用的關聯(lián)規(guī)那么。關聯(lián)規(guī)那么的挖掘是一個兩步的過程：(1)找出所有的頻繁項集：根據(jù)定義，這些項集出現(xiàn)的頻繁性至少等于預定義的最小支持度計數(shù)。(2)由頻繁項集產生強關聯(lián)規(guī)那么：根據(jù)定義，這些規(guī)那么必須滿足最小支持度和最小置信度。在以上兩個步驟中，第二步較容易，挖掘關聯(lián)規(guī)那么的總體性能由第一步決定。3FP-Grth關聯(lián)算法分析針對經典關聯(lián)Apriri算法的固有缺陷，產生了候選挖掘頻繁項集的方法FP-Grth算法。FP-

4、Grth算法采用分而治之的策略，在經過第一遍掃描之后，把數(shù)據(jù)庫中的頻繁項集壓縮到一棵頻繁形式樹(FP-Tree)，同時仍然保存其中的關聯(lián)信息，隨后再將FP-Tree分化成一些條件數(shù)據(jù)庫，每個條件數(shù)據(jù)關聯(lián)一個頻繁項，然后再分別對這些條件庫進展挖掘。FP-Grth算法將發(fā)現(xiàn)長頻繁形式的問題轉換為遞歸地發(fā)現(xiàn)一些短形式，然后連接后綴。它使用最不頻繁的項作為后綴，提供了好的選擇性。FP-Grth算法核心思想如下所示：輸入：事務數(shù)據(jù)庫D；最小支持度閾值in_sup。輸出：頻繁形式的完全集。方法：(1)構造FP-Tree。掃描事務數(shù)據(jù)庫D一次。搜集頻繁項的集合F和它們的支持度。對F按支持度降序排序，結果為頻

5、繁項表L。創(chuàng)立FP-Tree的根節(jié)點，以“NULL標記它。對于D中每個事務Trans，執(zhí)行：選擇Trans的頻繁項，并按照L中的次序排序。設排序后的頻繁項表為p|P，其中p是第一個元素，而P是剩余元素的表。調用insert_tree(p|P，T)。該過程執(zhí)行過程如下：假如T有子女N使得N.ite-nae=p.ite-nae，那么N的計數(shù)增加1，否那么創(chuàng)立一個新節(jié)點N，將其計數(shù)設置為1，鏈接到它的父節(jié)點T，并且通過節(jié)點鏈構造將其鏈接到具有一樣ite-nae的節(jié)點。假如P非空，遞歸地調用insert_tree(P，N)。(2)通過調用FP-Grth(FP-Tree，null)實現(xiàn)FP-Tree的挖

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

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

8、生所處的內外部因素進展關聯(lián)挖掘，以獲取每個簇學生所處內外部因素間的關聯(lián)關系，分別對每個簇學生的內外部因素采用FP-Grth改良算法進展關聯(lián)挖掘，因為支持度計數(shù)是與問題域相關的，用戶可選擇不同的支持度計數(shù)實驗，我們在這里支持度計數(shù)選取為5。局部簇構造FP-Tree如圖1所示，因篇幅有限，只列舉有代表意義的關聯(lián)項。圖1生成的FP-Tree(灰色是頻繁項)5完畢語對該算法的研究和應用可以看出算法具有很強的實用性。本文對關聯(lián)挖掘中支持度、置信度的選擇沒有進展深化的研究，因為對于一組給定的樣本，由于缺乏經歷或詳細的問題域不同等其它原因導致事先不能合理地對聚類數(shù)目K、支持度、置信度的取值，這是一個比擬棘手的問題，目前關于這方面研究的資料文獻較少，因此將此問題作為下一步研究的方向具有重要的現(xiàn)實意義。參考文獻1加JiaEiHanihelineKaber，范明，孟小峰等譯.