何鎮(zhèn)宏_基于spark的分布式頻繁項(xiàng)集挖掘算法研究

1、1分類號(hào)：TP391單位代碼：10636密級(jí)：公開學(xué)號(hào)：20151301003碩士學(xué)位論文中文論文題目中文論文題目:并行頻繁項(xiàng)集挖掘算法研究并行頻繁項(xiàng)集挖掘算法研究英文論文題目英文論文題目:ResearchonParallelFrequentItemsetsMiningAlgithm論文作者：何鎮(zhèn)宏指導(dǎo)教師：楊軍專業(yè)名稱：計(jì)算機(jī)應(yīng)用技術(shù)研究方向：并行頻繁項(xiàng)集挖掘算法所在學(xué)院：計(jì)算機(jī)科學(xué)學(xué)院論文提交日期：2018年5月17日論文答辯日期：

2、2018年5月27日并行關(guān)聯(lián)規(guī)則頻繁項(xiàng)集挖掘算法研究I并行頻繁項(xiàng)集挖掘算法研究并行頻繁項(xiàng)集挖掘算法研究作者:何鎮(zhèn)宏指導(dǎo)老師:楊軍摘要摘要頻繁項(xiàng)集挖掘用來(lái)發(fā)現(xiàn)數(shù)據(jù)項(xiàng)集中的頻繁模式，在商品關(guān)聯(lián)分析和超市促銷策略決策中有著廣泛的應(yīng)用。但是，傳統(tǒng)的頻繁項(xiàng)集挖掘算法的時(shí)間復(fù)雜度較高，因此許多國(guó)內(nèi)外的學(xué)者們致力于提高相關(guān)算法的性能。隨著大數(shù)據(jù)時(shí)代的到來(lái)，傳統(tǒng)的頻繁項(xiàng)集挖掘算法往往受限于單臺(tái)計(jì)算機(jī)有限的計(jì)算能力和存儲(chǔ)容量，無(wú)法滿足用戶對(duì)于處理更大規(guī)模

3、的頻繁項(xiàng)集挖掘問題的迫切需求。隨著大數(shù)據(jù)技術(shù)的發(fā)展，基于Hadoop平臺(tái)的頻繁項(xiàng)集挖掘算法在時(shí)間效率上相比于單機(jī)算法有了很大的提高。最新的內(nèi)存計(jì)算框架Spark相比于Hadoop平臺(tái)具有并行計(jì)算，Spark已成為目前工業(yè)界搭建分布式計(jì)算平臺(tái)的主流框架。因此，本文將Spark框架和頻繁項(xiàng)集挖掘算法相結(jié)合，研究在Spark平臺(tái)下實(shí)現(xiàn)并行頻繁項(xiàng)集挖掘算法，以提高頻繁項(xiàng)集挖掘算法的時(shí)間效率。本文的主要工作包含如下幾個(gè)方面。(1)學(xué)習(xí)研究了經(jīng)典的

4、頻繁項(xiàng)集挖掘算法，包括Aprii算法，DHP算法，F(xiàn)PGrowth算法。(2)針對(duì)Aprii算法由K頻繁項(xiàng)集生成K1頻繁項(xiàng)集的過程中，需要多次重復(fù)檢測(cè)項(xiàng)集中的二項(xiàng)子集是否頻繁的問題，提出了一種基于二維表的Aprii改進(jìn)算法，用一個(gè)二維表記錄二項(xiàng)子集是否頻繁，從而減少了判斷二項(xiàng)子集是否頻繁需要多次掃描事務(wù)數(shù)據(jù)庫(kù)的時(shí)間。實(shí)驗(yàn)結(jié)果表明，本文所提出的改進(jìn)Aprii算法比原Aprii算法相比，可以明顯減少算法的運(yùn)行時(shí)間。(3)學(xué)習(xí)研究了Spark

5、框架的相關(guān)技術(shù)，基于Linux操作系統(tǒng)，運(yùn)用Java結(jié)合Scala開發(fā)語(yǔ)言，搭建了基于Spark平臺(tái)的分布式開發(fā)環(huán)境，用于實(shí)現(xiàn)所提出的并行頻繁項(xiàng)集挖掘算法。(4)針對(duì)DHP在第一次統(tǒng)計(jì)桶中項(xiàng)集數(shù)目時(shí)，會(huì)生成許多重復(fù)的候選項(xiàng)集，提出了基于Spark單節(jié)點(diǎn)的壓縮DHP算法，該算法用形象地?cái)?shù)字形式代替重復(fù)的項(xiàng)集數(shù)，并且在第一次掃描事務(wù)數(shù)據(jù)庫(kù)時(shí)就實(shí)施，通過實(shí)際的試驗(yàn)證明，提出的這個(gè)壓縮改進(jìn)算法在時(shí)間復(fù)雜度上明顯比沒有采用壓縮DHP的單節(jié)點(diǎn)DHP