基于afopt-tree的最大頻繁項(xiàng)集挖掘(20180524132040)

《基于afopt-tree的最大頻繁項(xiàng)集挖掘(20180524132040)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、后來人們陸續(xù)提出了一些技術(shù)對(duì)Apriori算法進(jìn)行了改進(jìn)，但作為作為廣度優(yōu)先策略的頻繁項(xiàng)集挖掘算法，任然無法避免產(chǎn)生候選項(xiàng)集和對(duì)于數(shù)據(jù)庫的多次掃描。因此，后來深度優(yōu)先策略的挖掘算法逐漸成為頻繁項(xiàng)集挖掘的主流算法，F(xiàn)P-Growth算法就是其中最具代表性的算法。2、EP-Growth算法利用FP-Growth算法進(jìn)行頻繁項(xiàng)集挖掘的算法思想主要分為兩步：首先要根據(jù)事物數(shù)據(jù)集創(chuàng)建一棵壓縮的條件模式樹FP-Tree。FP-Tree屮的每一個(gè)結(jié)點(diǎn)都對(duì)疲一個(gè)項(xiàng).樹中每-條從根結(jié)點(diǎn)到某個(gè)子孫結(jié)點(diǎn)的路徑表示一個(gè)項(xiàng)集。每個(gè)結(jié)

2、點(diǎn)都記錄了從根節(jié)點(diǎn)到該結(jié)點(diǎn)項(xiàng)集的支持度，并且每個(gè)結(jié)點(diǎn)還有指向其前驅(qū)結(jié)點(diǎn)和相同結(jié)點(diǎn)的指針域。然后再遞歸的調(diào)用EP-Growth算法進(jìn)行頻繁項(xiàng)集的挖掘。構(gòu)造FP-Trcc的算法過程如下所示：(1)掃描事物數(shù)據(jù)集D，產(chǎn)生頻繁1項(xiàng)集集合F及其計(jì)數(shù)，并將獲得的項(xiàng)集按其計(jì)數(shù)的降序進(jìn)行排列，生成FP-Tree的頭表Header。(2)創(chuàng)建FP-Tree的根節(jié)點(diǎn)T=null，并再次掃描事物數(shù)據(jù)集D，對(duì)事物數(shù)據(jù)集(3)D中的每一項(xiàng)數(shù)據(jù)，根據(jù)頭表中獲得的頻繁1項(xiàng)集集合刪除其中的非頻繁項(xiàng)，然后按照(1)中所獲得頭表順序進(jìn)行排序，

3、假定所得的結(jié)果為［p

4、P］，其中P為頻繁項(xiàng)目的首項(xiàng)，P則為其剩余項(xiàng)目，遞歸調(diào)用過程insert-tree(［p

5、P］，T)。其中insert-tree(［p

6、P］，T)的過程如下：如果T中有子女結(jié)點(diǎn)N使得N.name=p,則將結(jié)點(diǎn)N的計(jì)數(shù)加1;若不存在，則建立一個(gè)新的結(jié)點(diǎn)N,其中N.name=p,N.count=l,并將N結(jié)點(diǎn)的父指針域指向其前驅(qū)結(jié)點(diǎn)T,將N結(jié)點(diǎn)的結(jié)點(diǎn)鏈指向與其相同的結(jié)點(diǎn)。對(duì)于表2-1屮的事務(wù)數(shù)據(jù)集，在最小支持度min_sup為3時(shí)，所創(chuàng)建的FP-Tree如圖2-2所不。頻繁模式樹FP-tr

7、ee構(gòu)造完成以后，就可以利用FP-Growth算法對(duì)其進(jìn)行相應(yīng)的關(guān)聯(lián)規(guī)則挖掘。FP-Growth算法主耍步驟如下：輸入：頻繁模式樹FP-tree，最小支持度min_sup，事務(wù)數(shù)據(jù)集D輸出：D屮的所有頻繁項(xiàng)集FP-Growth(T,h)(1)IFT中只包含唯一路徑P(2)對(duì)P屮所有結(jié)點(diǎn)的每個(gè)組合(記為夕)(1)生成頻繁項(xiàng)目集An/?，其支持度等于當(dāng)中結(jié)點(diǎn)的最小支持度(2)ELSE對(duì)FP-tree頭表中的每個(gè)元素％do(3)生成頻繁模式夕其中/?.S叩=6ZrSUp(4)構(gòu)造0的條件模式基的集合并創(chuàng)建條件模式

8、子樹(5)IFFP-tree0(6)遞歸調(diào)用FP-Growth(FP-tree^h)FP-Growth算法將數(shù)據(jù)集中與關(guān)聯(lián)規(guī)則挖掘相關(guān)的信息壓縮保存在了FP-tree中，只需要掃描W次數(shù)據(jù)庫，避免了產(chǎn)生候選項(xiàng)集的問題，減少了算法的I/O消耗；并且算法利用遞歸的方式將頻繁項(xiàng)集的挖掘轉(zhuǎn)化為對(duì)一些較短的頻繁項(xiàng)集再加上其后綴的挖掘過程，具有良好的選擇性，提升丫算法的運(yùn)行效率。相比Apriori及其改進(jìn)算法，F(xiàn)P-Growth算法的性能有了巨大的提高。但是當(dāng)最小支持度較小，或者當(dāng)數(shù)據(jù)集中的長(zhǎng)數(shù)據(jù)項(xiàng)較多時(shí)，算法在運(yùn)行過

9、程中會(huì)產(chǎn)生大量的條件模式子樹，產(chǎn)生巨大的系統(tǒng)開銷，并且影響算法的運(yùn)行效率。2.3最大頻繁項(xiàng)集挖掘2.3.1頻繁項(xiàng)集的分類傳統(tǒng)的頻繁項(xiàng)集挖掘算法獲取的是事務(wù)數(shù)據(jù)集屮所有的頻繁項(xiàng)集，即完全頻繁項(xiàng)集。但是隨著信息產(chǎn)業(yè)尤其是互聯(lián)網(wǎng)行業(yè)的不斷發(fā)展，人們需要處理的信息越來越多，而數(shù)據(jù)挖掘所需要處理的數(shù)據(jù)集也越來越大，獲取信息中所有的關(guān)聯(lián)知識(shí)變得越來越困難，并且在通常情況下也沒有必耍;所以，人們提出了頻繁閉項(xiàng)集和最大頻繁項(xiàng)集的概念，來簡(jiǎn)化關(guān)聯(lián)規(guī)則挖掘所獲取的關(guān)聯(lián)信息頻繁閉項(xiàng)集和最大頻繁項(xiàng)集的具體定義如下：定義4當(dāng)且僅當(dāng)：

10、(1)sup(C)>min_sup；(2)對(duì)于任意的頻繁項(xiàng)集X都有當(dāng)CczX則sup(C)〉sup(Y)，稱C為事物數(shù)據(jù)集D上的頻繁閉項(xiàng)集。定義5當(dāng)且僅當(dāng)：(1)sup(A/)>min_sup；(2)對(duì)于事物數(shù)據(jù)庫中的任意項(xiàng)集X都有當(dāng)McX則sup(X)

11、集，當(dāng)支持度較小時(shí)，頻繁閉項(xiàng)集的規(guī)模也非常龐大,因此自從1998年提出最大頻繁項(xiàng)集的概念以后，最大頻繁項(xiàng)集的挖掘也越來越受到人們的關(guān)注。最大頻繁項(xiàng)集挖掘算法中，最具影響力的算法就是Grahne等人提出的FP-max算法心FP-max算法是一種基于FP-tree的深度優(yōu)先搜索的最人頻繁項(xiàng)集挖掘算法。在算法對(duì)條件模式樹進(jìn)行遍歷時(shí)，不僅保存了遍歷結(jié)點(diǎn)在搜索空間樹中的路徑信息，同時(shí)也對(duì)遍歷過的結(jié)點(diǎn)的條件模式基，即搜索空間