版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、精選優(yōu)質(zhì)文檔-傾情為你奉上FP-Growth算法實(shí)驗(yàn)報(bào)告一、算法介紹數(shù)據(jù)挖掘是從數(shù)據(jù)庫中提取隱含的、未知的和潛在的有用信息的過程,是數(shù)據(jù)庫及相關(guān)領(lǐng)域研究中的一個(gè)極其重要而又具有廣闊應(yīng)用前景的新領(lǐng)域. 目前,對數(shù)據(jù)挖掘的研究主要集中在分類、聚類、關(guān)聯(lián)規(guī)則挖掘、序列模式發(fā)現(xiàn)、異常和趨勢發(fā)現(xiàn)等方面,其中關(guān)聯(lián)規(guī)則挖掘在商業(yè)等領(lǐng)域中的成功應(yīng)用使它成為數(shù)據(jù)挖掘中最重要、最活躍和最成熟的研究方向. 現(xiàn)有的大多數(shù)算法均是以Apriori 先驗(yàn)算法為基礎(chǔ)的,產(chǎn)生關(guān)聯(lián)規(guī)則時(shí)需要生成大量的候選項(xiàng)目集. 為了避免生成候選項(xiàng)目集,Han等提出了基于FP 樹頻繁增長模式(Frequent-Pattern Growth,F(xiàn)
2、P-Growth)算法。FP 樹的構(gòu)造過程可描述為: 首先創(chuàng)建樹的根結(jié)點(diǎn), 用“null”標(biāo)記. 掃描交易數(shù)據(jù)集DB ,每個(gè)事務(wù)中的項(xiàng)目按照支持度遞減排序,并對每個(gè)事務(wù)創(chuàng)建一個(gè)分枝. 一般地,當(dāng)為一個(gè)事務(wù)考慮增加分枝時(shí),沿共同前綴上的每個(gè)結(jié)點(diǎn)的計(jì)數(shù)值增加1 ,為跟隨在前綴之后的項(xiàng)目創(chuàng)建結(jié)點(diǎn)并鏈接. 為方便樹的遍歷,創(chuàng)建一個(gè)頻繁項(xiàng)目列表,使得每個(gè)項(xiàng)目通過一個(gè)結(jié)點(diǎn)頭指針指向它在樹中的位置. FP 樹挖掘過程可描述為:由長度為1 的頻繁項(xiàng)目開始,構(gòu)造它的條件項(xiàng)目基和條件FP樹,并遞歸地在該樹上進(jìn)行挖掘. 項(xiàng)目增長通過后綴項(xiàng)目與條件FP 樹產(chǎn)生的頻繁項(xiàng)目連接實(shí)現(xiàn). FP-Growth 算法將發(fā)現(xiàn)大頻繁
3、項(xiàng)目集的問題轉(zhuǎn)換成遞歸地發(fā)現(xiàn)一些小頻繁項(xiàng)目,然后連接后綴.它使用最不頻繁的項(xiàng)目后綴,提供了好的選擇性。算法:FP-Growth。使用FP樹,通過模式增長挖掘頻繁模式。輸入:n D:事物數(shù)據(jù)庫n min_sup:最小支持度閾值輸出:頻繁模式的完全集。方法:1. 按一下步驟構(gòu)造FP樹:(a)掃描數(shù)據(jù)庫D一次。手機(jī)頻繁項(xiàng)的集合F和它們的支持度計(jì)數(shù)。對F按支持度計(jì)數(shù)降序排序,結(jié)果為頻繁項(xiàng)列表L。(b)創(chuàng)建FP樹的根節(jié)點(diǎn),以“null”標(biāo)記它。對于D中每個(gè)事物Trans,執(zhí)行:選擇Trans中的頻繁項(xiàng),并按L中的次序排序。設(shè)Trans排序后的頻繁項(xiàng)列表為p|P,其中p是第一個(gè)元素,而P是剩下的元素列表。
4、調(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. FP樹的挖掘通過調(diào)用FP-growth(FP_tree,null)實(shí)現(xiàn)。該過程實(shí)現(xiàn)如下。Procedure FP_growth(Tree,)(1)if Tree包含單個(gè)路徑P then(2)for 路徑P中結(jié)點(diǎn)的每個(gè)組合(記作)(3)產(chǎn)生模式,其中支持度計(jì)數(shù)supp
5、ort_count等于中結(jié)點(diǎn)的最小支持度計(jì)數(shù);(4)else for Tree的表頭中的每一個(gè)i(5)產(chǎn)生一個(gè)模式=i,其中支持度計(jì)數(shù)support_count=i.support_count;(6)構(gòu)造的調(diào)減模式基然后構(gòu)造的條件FP樹Tree;(7)if Tree then(8)調(diào)用FP_growth(Tree,);二、算法實(shí)現(xiàn)及實(shí)驗(yàn)結(jié)果 本實(shí)驗(yàn)有兩個(gè)測試集合:小數(shù)據(jù)集A:50條事物集,10個(gè)不同的項(xiàng)大數(shù)據(jù)集合B:5670事物集,100個(gè)不同項(xiàng)1.對數(shù)據(jù)集合A進(jìn)行min_sup=8%計(jì)數(shù)產(chǎn)生的頻繁項(xiàng)集結(jié)果如下:專心-專注-專業(yè)表1. 頻繁一項(xiàng)集項(xiàng)集支持度計(jì)數(shù)支持度1I3 3570%2I9 6
6、12%3I6 510%4I1 )1734%5I4 1428%6I71122%7I2 3468%8I8 1122%9I5 1632%表2. 頻繁二項(xiàng)集項(xiàng)集支持度計(jì)數(shù)支持度1I2 I6510%2I3 I9 48%3I2 I9 48%4I1 I7 48%5I2 I7 714%6I3 I7 816%7I2 I8 612%8I3 I8 816%9I2 I4 1122%10I2 I5 1122%11I3 I5 1326%12I3 I1 1020%13I2 I1 1122%14I3 I2 2142%表3. 頻繁三項(xiàng)集項(xiàng)集支持度計(jì)數(shù)支持度1I2 I5 I7510%2I3 I5 I7612%3I3 I2 I75
7、10%4I3 I2 I8510%5I2 I5 I8510%6I3 I5 I8 612%7I2 I1 I4510%8I3 I1 I5510%9I2 I1 I5 612%10I3 I2 I5 816%11I3 I2 I148%表4. 頻繁四項(xiàng)集項(xiàng)集支持度計(jì)數(shù)支持度1I3 I2 I5 I7510%2I3 I2 I5 I8510%3I3 I2 I1 I548%2對數(shù)據(jù)集B進(jìn)行不同支持度實(shí)驗(yàn)時(shí)間消耗結(jié)果如下:圖1.數(shù)據(jù)集B消耗時(shí)間三、算法的優(yōu)缺點(diǎn)分析1. FP-Growth算法的優(yōu)點(diǎn):(1)一個(gè)大數(shù)據(jù)庫能夠被有效地壓縮成比原數(shù)據(jù)庫小很多的高密度結(jié)構(gòu),避免了重復(fù)掃描數(shù)據(jù)庫的開銷(2)該算法基于FP-Tre
8、e的挖掘采取模式增長的遞歸策略,創(chuàng)造性地提出了無候選項(xiàng)目集的挖掘方法,在進(jìn)行長頻繁項(xiàng)集的挖掘時(shí)效率較好。(3)挖掘過程中采取了分治策略,將這種壓縮后的數(shù)據(jù)庫DB分成一組條件數(shù)據(jù)庫Dn,每個(gè)條件數(shù)據(jù)庫關(guān)聯(lián)一個(gè)頻繁項(xiàng),并分別挖掘每一個(gè)條件數(shù)據(jù)庫。而這些條件數(shù)據(jù)庫Dn要遠(yuǎn)遠(yuǎn)小于數(shù)據(jù)庫DB。2. FP-Growth算法的缺點(diǎn)及改進(jìn)方法(1)該算法采取增長模式的遞歸策略,雖然避免了候選項(xiàng)目集的產(chǎn)生。但在挖掘過程,如果一項(xiàng)大項(xiàng)集的數(shù)量很多,并且由原數(shù)據(jù)庫得到的FP-Tree的分枝很多,而且分枝長度又很長時(shí),該算法需要構(gòu)造出數(shù)量巨大的conditional FP-Tree,不僅費(fèi)時(shí)而且要占用大量的空間,挖掘
9、效率不好,而且采用遞歸算法本身效率也較低。改進(jìn)策略:FA算法-FP-Growth算法與Apriori算法的結(jié)合在原數(shù)據(jù)庫得到的FP-Tree的基礎(chǔ)上,采用Apriori算法的方法進(jìn)行挖掘,挖掘過程中不構(gòu)造conditional FP-Tree。挖掘過程仍然采用分治的策略,即將壓縮后的數(shù)據(jù)庫D分成一組條件數(shù)據(jù)庫,每個(gè)條件數(shù)據(jù)庫關(guān)聯(lián)一個(gè)頻繁項(xiàng)。假設(shè)有n個(gè)一項(xiàng)大項(xiàng)集,則數(shù)據(jù)庫D可被分割成n個(gè)條件數(shù)據(jù)庫Di(i=1,n),而數(shù)據(jù)庫Di是關(guān)聯(lián)一項(xiàng)大項(xiàng)集Ii的條件數(shù)據(jù)庫。然后分別采用Apriori算法挖掘每一個(gè)條件數(shù)據(jù)庫Di,得到所有以Ii為尾的大項(xiàng)集。實(shí)現(xiàn)方法是,仍然采用FP-Growth算法的方法構(gòu)造
10、一棵FP-Tree,不過在每個(gè)項(xiàng)前綴子樹的節(jié)點(diǎn)中增加一個(gè)域:con-count。在對條件數(shù)據(jù)庫Di進(jìn)行挖掘時(shí),該域記錄了所在路徑代表的交易(transaction)中達(dá)到此節(jié)點(diǎn)的并且包括Ii的交易個(gè)數(shù)。而為了找出所有包含Ii的大項(xiàng)集,首先沿著頻繁項(xiàng)頭表中項(xiàng)Ii的鏈域找到item-name為Ii的每個(gè)項(xiàng)前綴子樹的節(jié)點(diǎn)Pi,再沿著每個(gè)Pi的父指針往上走直到根節(jié)點(diǎn),使該路徑上經(jīng)過的每個(gè)項(xiàng)前綴子樹節(jié)點(diǎn)的con-count域都增加Pi.count,根節(jié)點(diǎn)不增加。同時(shí)增加一個(gè)臨時(shí)頻繁項(xiàng)頭表lTable,每個(gè)表項(xiàng)(entry)由三個(gè)域組成:(1)item-name;(2)node-link;(3) con-
11、count。若某個(gè)項(xiàng)前綴子樹節(jié)點(diǎn)的con-count域增加了Pi.count,另外假如lTable中沒有一個(gè)表項(xiàng)的item-name與Pi.item-name相同,則在lTable中增加一個(gè)表項(xiàng),使它的item-name,與con-count都與Pi的相同,同時(shí)node-link指向該項(xiàng)前綴子樹節(jié)點(diǎn)的Pi的地址。如果lTable中存在一個(gè)表項(xiàng),它的item-name與Pi.item-name相同,則只要對該表項(xiàng)的con-count域增加Pi. count就行了。然后再對lTable中的每一個(gè)表項(xiàng)的con-count域進(jìn)行統(tǒng)計(jì),若它的con-count域大于預(yù)先給定的最小支持度,則保留該表項(xiàng),否
12、則刪除該表項(xiàng)1。(2)由于海量的事物集合存放在大型數(shù)據(jù)庫中,經(jīng)典的FP-Growth算法在生成新的FP-Tree時(shí)每次都要遍歷調(diào)減模式基兩次,導(dǎo)致系統(tǒng)需要反復(fù)申請本地以及數(shù)據(jù)庫服務(wù)器的資源查詢相同內(nèi)容的海量數(shù)據(jù),一方面降低了算法的效率,另一方面給數(shù)據(jù)庫服務(wù)器產(chǎn)生高負(fù)荷,不利于數(shù)據(jù)庫服務(wù)器正常運(yùn)作。改進(jìn)策略:針對 FP-Growth 算法的缺點(diǎn),對經(jīng)典算法進(jìn)行改進(jìn),提出使用支持度計(jì)數(shù)二維表的方法,從而省去經(jīng)典算法對條件模式基的第一次遍歷,具體算法描述為: 在第一次遍歷事務(wù)集合 T 的同時(shí)創(chuàng)建二維向量,記錄每個(gè)事務(wù)中各個(gè)項(xiàng)兩兩組合出現(xiàn)的支持度計(jì)數(shù)。如有事務(wù) “A,B,C,D”,則二維向量表中(A,B)、(A,C)、(A,D)、(B,C)、(B,D)、 (C,D)項(xiàng)都需要加 1。其中向量(C,B)和(B,C)是兩個(gè)不同的向量。 利用遞歸方式創(chuàng)建 條件下(Null)的條件 FP 子樹時(shí),無需兩次遍歷條件模式基(其中第一次遍歷條件模式基可得到支持度計(jì)數(shù)列表,第二次遍歷條件模式基可插入樹節(jié)點(diǎn)從而創(chuàng)建 FP 樹)。支持度計(jì)數(shù)列表可以從支持度計(jì)數(shù)二維向量列表中獲得。抽取二維向量表中的與 Ei 相關(guān)的
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- DB51T 1622-2013 政務(wù)服務(wù)中心 窗口工作人員輪換規(guī)范
- DB51T 1598.1-2023 低壓線路電氣火災(zāi)原因認(rèn)定 第1部分:必要條件
- DB51T 1031-2010 茶葉中稀土的測定方法電感耦合等離子體原子發(fā)射光譜法
- 先天性腸旋轉(zhuǎn)異常病因介紹
- 精制C5項(xiàng)目立項(xiàng)申請報(bào)告
- (施工建設(shè))油氣分離器項(xiàng)目可行性研究報(bào)告
- 紅光激光器生產(chǎn)加工項(xiàng)目可行性研究報(bào)告
- 母料項(xiàng)目立項(xiàng)申請報(bào)告
- 2024-2030年新版中國金晶米黃人造崗石項(xiàng)目可行性研究報(bào)告
- 2024-2030年撰寫:中國聚乙二醇三甲基壬基醚行業(yè)發(fā)展趨勢及競爭調(diào)研分析報(bào)告
- 舞蹈演出編導(dǎo)排練合同模板
- 滬科版2024-2025學(xué)年七年級數(shù)學(xué)上冊計(jì)算專題訓(xùn)練專題18期末復(fù)習(xí)-四大必考題型總結(jié)(學(xué)生版+解析)
- 路燈安裝工程項(xiàng)目實(shí)施重點(diǎn)、難點(diǎn)和解決方案
- 2024年產(chǎn)品技術(shù)秘密保護(hù)協(xié)議版B版
- 社會(huì)學(xué)概論-第一次形成性考核-國開(SC)-參考資料
- 南京審計(jì)大學(xué)《計(jì)量經(jīng)濟(jì)學(xué)》2021-2022學(xué)年第一學(xué)期期末試卷
- 2024-2025學(xué)年廣東省深圳市羅湖區(qū)翠園中學(xué)九年級(上)期中語文試卷
- 新媒體營銷對企業(yè)品牌傳播的影響與對策8700字【論文】
- 期末測試-2024-2025學(xué)年語文六年級上冊統(tǒng)編版
- 建筑施工安全知識培訓(xùn)
- 山東省2024年冬季普通高中學(xué)業(yè)水平合格考試語文仿真模擬卷01(考試版)
評論
0/150
提交評論