數(shù)據(jù)挖掘（Data Mining）是當(dāng)前數(shù)據(jù)庫(kù)和信息決策領(lǐng)域的前沿研究方向之一,top-rank-k頻繁模式挖掘是數(shù)據(jù)挖掘中挖掘rank不大于k的頻繁模式的方法,可以解決傳統(tǒng)頻繁模式挖掘支持度閾值設(shè)置困難的問(wèn)題。但主流的top-rank-k頻繁模式挖掘算法效率有待提高,且這類算法普遍基于串行設(shè)計(jì),難于突破單機(jī)硬件資源限制,無(wú)力應(yīng)對(duì)“大數(shù)據(jù)”時(shí)代的海量數(shù)據(jù)挖掘任務(wù),因此關(guān)于top-rank-k頻繁模式挖掘算法優(yōu)化及其并行化研究具有重要意義。本文的主要工作如下:（1）針對(duì)當(dāng)前top-rank-k頻繁模式挖掘時(shí)空耗費(fèi)大的問(wèn)題,提出了一種基于混合搜索的top-rank-k頻繁模式挖掘算法HTK（Hybrid-search-based Algorithm of Top-rank-k Frequent Patterns）,其主要思想是:定義名為RSL（Static Doubly-linked List of Top-rank-k）的靜態(tài)雙鏈表存儲(chǔ)top-rank-k頻繁模式,采用1-模式的支持度及其在事務(wù)中后綴項(xiàng)的基數(shù)設(shè)計(jì)了模式區(qū)分方法,把模式區(qū)分為短模式和長(zhǎng)模式。挖掘過(guò)程中,首先利用基于貪心策略... 

【文章來(lái)源】：湖南師范大學(xué)湖南省211工程院校

【文章頁(yè)數(shù)】：67 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

RDD有向無(wú)環(huán)圖

碩士學(xué)位論文12式數(shù)據(jù)集RDD（ResilienntDistributedDatasets）之上，這使得Spark的各個(gè)組件可以無(wú)縫地進(jìn)行集成，能夠在同一個(gè)應(yīng)用程序中完成大數(shù)據(jù)處理。Spark具有比Hadoop更為豐富的操作算子，包含轉(zhuǎn)換（Transformations）和動(dòng)作（Actions）兩類。轉(zhuǎn)換算子完成作業(yè)中間過(guò)程處理，行動(dòng)算子觸發(fā)SparkContext提交Job作業(yè)。轉(zhuǎn)換算子采用的是惰性計(jì)算策略，只有在行動(dòng)算子提交任務(wù)時(shí)才會(huì)被觸發(fā)。原始的RDD經(jīng)過(guò)一系列的轉(zhuǎn)換就形成了一個(gè)有向無(wú)環(huán)圖DAG（DirectedAcyclegraph），如圖2-1所示。圖2-1RDD有向無(wú)環(huán)圖圖2-2所示的是Spark的集群架構(gòu)圖，涵蓋了Spark運(yùn)行流程的主要內(nèi)容：首先SparkContext向ClusterManager注冊(cè)并申請(qǐng)運(yùn)行Executor資源，ClusterManager分配Executor資源；然后，SparkContext構(gòu)建成DAG圖并分解為Task，發(fā)送給TaskScheduler；之后Executor向SparkContext申請(qǐng)Task，TaskScheduler將Task發(fā)放給Executor運(yùn)行，同時(shí)SparkContext將應(yīng)用程序代碼發(fā)放給Executor；最后，Task在Executor上運(yùn)行，運(yùn)行完畢釋放所有資源。圖2-2Spark集群架構(gòu)綜上，Spark對(duì)比于Hadoop的優(yōu)點(diǎn)如下：RDD4RDD3RDD1RDD2RDD7RDD5RDD6SparkContextCacheTaskTaskCacheTaskTaskDriverProgramClusterManagerWorkerNodeWorkerNodeExecutorExecutor

Top-rank-k頻繁模式挖掘算法優(yōu)化及其并行化研究41圖4-3并行計(jì)數(shù)過(guò)程圖4-4數(shù)據(jù)劃分過(guò)程（4）并行挖掘top-rank-k頻繁模式。采用mapPartitions操作分區(qū)執(zhí)行HTK算法。此處的HTK算法略有變化，在Gen_Subsume方法中，當(dāng)兩個(gè)1-模式連接時(shí)，要檢查支持度更大的1-模式是否是本分組內(nèi)的1-模式，如果不是則不能連接。此外，各節(jié)點(diǎn)挖掘的結(jié)果集Stop-k需要將不屬于本分組的其余1-模式刪除。（5）聚合并輸出結(jié)果。利用flatMap及reduceBykey聚合各節(jié)點(diǎn)挖掘結(jié)果，然后sortBy，silce及saveAsTextFile等算子過(guò)濾并輸出top-rank-k頻繁模式。T1={[a],[c],[b],[d]}T2={[b],[a],[c],[f]}T3={[e],[a],[d]}T4={[a],[b]}T5={[c],[b],[a]}T6={[c],[d]}<[a],1>,<[b],1><[c],1>,<[d],1><[a],1>,<[b],1><[c],1>,<[f],1><[a],1>,<[d],1><[a],1>,<[b],1><[b],1>,<[c],1><[a],1>,<[c],1><[d],1><[a],3><[b],2><[c],2><[d],2><[e],1><[f],1><[a],2><[b],2><[c],2><[d],1><[a],5><[b],4><[c],4><[d],3><[e],1><[f],1>textFileflatMapreduceBykeyNode1Node2T1={[a],[b],[c],[d]}T2={[a],[b],[c],[f]}T3={[a],[d],[e]}T4={[a],[b]}T5={[a],[b],[c]}T6={[c],[d]}SortCost_list<[a],log288)><[b],log18)><[c],log8)><[d],log2)><[e],0)><[f],0)>G_list<[a],log288)><[e],0)><[f],0)><[b],log18)><[c],log8)><[d],log2)>T1’={[a]}T2’={[a],[b],[c],[f]}T3’={[a],[d],[e]}T4’={[a]}T5’={[a]}T1’={[a],[b],[c],[d]}T2’={[a],[b],[c]}T3’={[a],[d]}T4’={[a],[b]}T5’={[a],[b],[c]}T6’={[c],[d]}CutdataNode1Node2No

【參考文獻(xiàn)】：
期刊論文
[1]了解中國(guó),從《今日中國(guó)》開(kāi)始[J].   今日中國(guó). 2018(12)
[2]基于Spark的Top-k對(duì)比序列模式挖掘[J]. 張鵬,段磊,秦攀,左劼,唐常杰,元昌安,彭艦.  計(jì)算機(jī)研究與發(fā)展. 2017(07)
[3]FP-growth算法改進(jìn)與分布式Spark研究[J]. 鄧玲玲,婁淵勝,葉楓.  微型電腦應(yīng)用. 2016(05)
[4]A new algorithm for fast mining frequent itemsets using N-lists[J]. DENG ZhiHong ,WANG ZhongHui & JIANG JiaJian Key Laboratory of Machine Perception(Ministry of Education),School of Electronics Engineering and Computer Science,Peking University,Beijing 100871,China.  Science China（Information Sciences）. 2012(09)
[5]基于工業(yè)設(shè)計(jì)的裝備制造業(yè)產(chǎn)品創(chuàng)新開(kāi)發(fā)策略[J]. 虞世鳴.  機(jī)械制造. 2012(08)



本文編號(hào)：3619760