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

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

2、60;  關(guān)鍵詞  數(shù)據(jù)挖掘；關(guān)聯(lián)分析；頻繁模式；FP-Tree 1  引言    關(guān)聯(lián)規(guī)則(Association Rules)挖掘是數(shù)據(jù)挖掘研究領(lǐng)域的一個重要研究方向，它由美國IBM Almaden Research Center 的Rakesh A-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。每個

3、事務(wù)有一個標識符，稱為TID。如果I的一個子集X滿足XT，則稱事務(wù)T包含項目集X。一個關(guān)聯(lián)規(guī)則就是形如X=Y的蘊涵式，XI、YI、XY= 。    規(guī)則X Y在交易數(shù)據(jù)庫中的支持度(support)就是交易集中包含X和Y的交易數(shù)與所有交易數(shù)之比，記為support (X Y)，即support(X Y)=T：XY T，T D/D。    規(guī)則X=Y在交易數(shù)據(jù)庫中的置信度(confidence)是指包含X和Y的交易數(shù)與包含X的交易數(shù)之比，記為confidence(X=Y)，即confidence(X=Y)= T：XY T，TD/T：X

4、T， 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ī)則必須滿足最小支持度和最小置信度。  &

5、#160; 在以上兩個步驟中，第二步較容易，挖掘關(guān)聯(lián)規(guī)則的總體性能由第一步?jīng)Q定。3  FP-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)一個頻繁項，然后再分別對這些條件庫進行挖掘。FP-Growth算法將發(fā)現(xiàn)長頻繁模式的問題轉(zhuǎn)換為遞歸地發(fā)現(xiàn)一些短模式，然后連接后綴。

6、它使用最不頻繁的項作為后綴，提供了好的選擇性。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”標記它。對于D中每個事務(wù)Trans，執(zhí)行：

7、選擇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)如下： 

8、0;  Procedure FP-Growth(Tree，)    if Tree 含單個路徑P then    for 路徑P中節(jié)點的每個組合(記作)    產(chǎn)生模式，其支持度support = 中節(jié)點的最小支持度；    else for each i在Tree的頭部    產(chǎn)生一個模式 = i，其支持度support =i.support；    構(gòu)造的條件模式基，然后構(gòu)造的條件FP-Tree；

9、60;   if Tree 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)外部因素進行關(guān)聯(lián)分析。4.1  關(guān)聯(lián)分析目標    目前我校面對的教務(wù)處學(xué)生成績數(shù)據(jù)庫是一個多維的關(guān)系數(shù)據(jù)庫，我們急切需要從這些海量數(shù)