伴隨著數(shù)據(jù)的幾何式增長,大數(shù)據(jù)時代如約而至。大數(shù)據(jù)時代最重要的任務是收集數(shù)據(jù)和整理數(shù)據(jù),數(shù)據(jù)挖掘是重要的一步,也是最基本的一步。其中在海量數(shù)據(jù)中挖掘頻繁項集是數(shù)據(jù)挖掘中最基本的一項工作,深受廣大國內(nèi)外研究者們的重視與研究。目前,頻繁項集挖掘算法的改進,基本都是基于經(jīng)典的Apriori算法與FP-Growth算法進行的改進。FP-Growth算法存在如下缺點:掃描第一遍數(shù)據(jù)集只統(tǒng)計1-項集的支持度,而對數(shù)據(jù)集的掃描消耗時間較多;FP-Tree只是簡單的將具有相同前綴進行合并,沒有考慮路徑上的項集是否可能構成頻繁項集,沒有控制FP-Tree的深度、寬度和結點個數(shù),在數(shù)據(jù)量增大時內(nèi)存消耗過多;條件FP-Tree的規(guī)模較大,使得遞歸挖掘的深度增加。因此,本文提出了基于頻繁項集挖掘2FP-Forest算法并定義了2FP-Tree和2FP-Forest數(shù)據(jù)結構。2FP-Forest算法在遍歷第一遍數(shù)據(jù)集時,統(tǒng)計所有1-項集和2-項集的支持度,并進行剪枝。本文在2FP-Forest中,充分利用2-項集的剪枝作用,在構建過程中進行充分的剪枝和合并結點等操作,使得2FP-Forest中不存在非潛在候選3... 

【文章來源】：長春工業(yè)大學吉林省

【文章頁數(shù)】：54 頁

【學位級別】：碩士

【部分圖文】：

基本剪枝策略1示例

枝策略是基本剪枝策略 1 的基礎上的擴充，它也是基于 Apriori 性節(jié)點{1，2}，按詞典序子集枚舉樹的定義，它的侯選擴展項集為展下一級節(jié)點時，必須計算項集{1，2，3}和{1，2，4}的支持度，行擴展時，已經(jīng)得到項集{1，3}為非頻繁項集，由 Apriori 性質(zhì)可知頻繁項集，因此重復計算項集{1，2，3}的支持度沒有任何意義。限定節(jié)點 N 的侯選擴展集CX(N)來自于 N 的父節(jié)點P 的頻繁擴展對已知非頻繁項集合重復進行頻度計算，可以有效的提高頻繁項集同樣，對于采用深度優(yōu)先策略算法挖掘較長的頻繁項集時，可以較空間，效果更好。圖 2.2 是基本剪枝策略 2 的例子，我們可以看到行下一級擴展時，它的候選擴展集為{4}，避免了重復計算項集{繁項集挖掘算法riori 算法

遍數(shù)據(jù)庫之后，利用得到的頻繁 1-項集對事務記錄重排序的事務構建 FP-Tree。構建 FP-Tree 時，首重排序的事務插入到樹中。如果在樹中存在要插入果添加項不存在樹中，則在樹中重新開一個分支。程如下：事務 ID 事務中的元素 過濾和重排序001 r,z,h,j,p z,r002 z,y,x,w,v,u,t,s z,x,y,003 z z004 r,x,n,o,s x,s,005 y,r,x,z,q,t,p z,x,y,006 y,z,x,e,q,s,t,m z,x,y,表 2-3 過濾事務與原事務元素比較

【參考文獻】：
期刊論文
[1]基于Spark的并行FP-Growth算法優(yōu)化與實現(xiàn)[J]. 陸可,桂偉,江雨燕,杜萍萍.  計算機應用與軟件. 2017(09)
[2]一種基于Spark框架的并行FP-Growth挖掘算法[J]. 張穩(wěn),羅可.  計算機工程與科學. 2017(08)
[3]轉(zhuǎn)換時間數(shù)據(jù)流的加權FP-Tree挖掘算法[J]. 宋軍,陳瀟君.  江蘇大學學報(自然科學版). 2017(03)
[4]基于Hadoop的FP-Growth關聯(lián)規(guī)則并行改進算法[J]. 厙向陽,張玲.  計算機應用研究. 2018(01)
[5]基于排序樹的頻繁項集挖掘算法[J]. 王紅梅,黨源源,胡明,劉大有.  吉林大學學報(工學版). 2016(04)
[6]基于MapReduce和矩陣的頻繁項集挖掘算法[J]. 周國軍,龔榆桐.  微電子學與計算機. 2016(05)
[7]基于MapReduce的并行關聯(lián)規(guī)則增量更新算法[J]. 程廣,王曉峰.  計算機工程. 2016(02)
[8]NB-MAFIA:基于N-List的最長頻繁項集挖掘算法[J]. 沈戈暉,劉沛東,鄧志鴻.  北京大學學報(自然科學版). 2016(02)
[9]MapReduce編程模型下的約束頻繁模式挖掘算法[J]. 閆曉嫵,張繼福,荀亞玲,趙旭俊.  小型微型計算機系統(tǒng). 2015(10)
[10]壓縮FP-Tree的改進搜索算法[J]. 吳倩,羅健旭.  計算機工程與設計. 2015(07)

碩士論文
[1]基于Hadoop的改進的并行Fp-Growth算法[D]. 周詩慧.山東大學 2013



本文編號：3387273