一種基於Spark平臺的並行序列模式挖掘方法與流程

2023-08-09 23:25:26

本發明屬於序列模式挖掘
技術領域：
：，特別是涉及一種基於spark平臺的並行序列模式挖掘方法。
背景技術：
：：(1)序列模式挖掘技術[文獻1]最早提出序列模式挖掘的概念。序列模式挖掘就是挖掘序列資料庫中頻繁出現的有序事件或子序列。序列模式挖掘作為數據挖掘研究領域中重要的研究內容之一，有著很廣泛的應用需求，比如用戶購買行為分析、生物序列分析、計程車頻繁軌跡模式發現、人類移動行為模式分析。[文獻2]提出了採用冗餘候選模式的剪除策略和哈希樹來實現候選模式快速訪存的gsp算法。[文獻3]提出了基於垂直數據表示的spade算法。[文獻4]提出了基於投影資料庫的prefixspan算法。這些傳統的串行化算法雖然隨著數據結構的優化和挖掘機制的改變，在性能上有一定提高，但在面對大規模數據集時算法的處理速度往往達不到人們的要求。直到20世紀初，計算機硬體的急速發展極大的推動了並行序列模式挖掘算法的研究。國內外學者相繼提出了各種分布式序列模式挖掘算法。[文獻5]提出了基於樹投影技術的兩種不同的並行化算法來解決分布內存並行計算機的序列模式發現問題。[文獻6]提出了通過語法序列樹減少數據傳輸量的dmgsp算法。[文獻7]提出了快速挖掘全局最大頻繁項目集的fmgsp算法。但是由於分布式內存系統或網格計算系統這些並行平臺並未提供容錯機制，所以在這些並行平臺上面實現的並行序列模式挖掘算法不具備容錯性。此外，在這些平臺上開發並行算法需要程式設計師具備大量的並行算法開發經驗。雲計算平臺的出現為實現並行算法提供了新的方法和途徑，使得高效低成本的從海量數據中進行序列模式挖掘成為可能。由apache基金會所開發的hadoop雲計算平臺由於其開源性、可擴展性、高容錯性、使不具備豐富並行算法開發經驗的程式設計師可以在hadoop平臺上輕鬆的開發並行程序，因此很多學者提出了基於hadoop平臺的並行序列模式挖掘算法。[文獻8]提出了基於hadoop的並行增量序列模式挖掘算法dpsp算法。[文獻9]提出了基於hadoop的並行閉序列挖掘算法-bide-mr算法。[文獻10]提出了基於hadoop的spamc算法。[文獻11]提出了基於hadoop的並行prefixspan算法。[文獻12]提出了基於事務分解思想的基於hadoop的prefixspan並行算法。[文獻13]提出了基於資料庫切分的基於hadoop的dgsp算法。文獻[8][9][10][11]提出的基於迭代式mapreduce任務的並行序列模式挖掘算法需要執行多個需要從hdfs中讀取序列資料庫的mapreduce任務，會產生很大的io開銷。文獻[12][13]提出的基於非迭代式mapreduce任務的並行序列模式挖掘算法並不能有效的將計算任務均勻的分派到各個計算節點，造成了負載不均衡。(2)map-reduce編程框架map-reduce是一種編程框架，採用了概念"map(映射)"和"reduce(歸約)"，用於大規模數據集(大於1tb)的並行運算，在[文獻14]中提出。用戶只需編寫兩個稱作map和reduce的函數即可，系統能夠管理map或reduce並行任務的執行以及任務之間的協調，並且能夠處理上述某個任務失敗的情況，並且同時能夠保障對硬體故障的容錯性。基於map-reduce的計算過程如下：1)用戶程序中的map-reduce庫首先將輸入文件分成m個數據分片,每個分片的大小一般從16到64mb(用戶可以通過可選的參數來控制每個數據片段的大小)，然後map-reduce庫在機群中創建大量的程序副本。2)這些程序副本有一個特殊的程序-主控程序,副本中其它的程序都是由主控程序分配任務的工作程序。有m個map任務和r個reduce任務將被分配，主控程序將一個map任務或reduce任務分配給一個空閒的工作程序。3)被分配了map任務的工作程序讀取相關的輸入數據片段，從輸入的數據片段中解析出鍵-值(key,value)對，然後把鍵-值對傳遞給用戶自定義的map函數，map函數將產生的中間臨時鍵-值對保存在本地內存緩存中。4)緩存中的鍵-值對通過分區函數分成r個區域，之後周期性的寫入到本地磁碟上。緩存的鍵-值對在本地磁碟上的存儲位置將被回傳給主控程序，由主控程序負責把這些存儲位置再傳給被分配了reduce任務的工作程序。5)當被分配了reduce任務的工作程序接收到主控程序發來的數據存儲位置信息後，使用遠程過程調用(remoteprocedurecalls)從被分配了map任務的工作程序所在主機的磁碟上讀取這些緩存數據。當被分配了reduce任務的工作程序讀取了所有的中間數據後，通過對鍵進行排序後使得具有相同鍵的數據聚合在一起。由於許多不同的鍵會映射到相同的reduce任務上，因此必須進行排序。如果中間數據太大無法在內存中完成排序，那麼就要在外部進行排序。6)被分配了reduce任務的工作程序遍歷排序後的中間數據，對於每一個唯一的中間鍵-值對,被分配了reduce任務的工作程序將這個鍵和它相關的中間值的集合傳遞給用戶自定義的reduce函數。reduce函數的輸出被追加到所屬分區的輸出文件。7)當所有的map和reduce任務都完成之後,主控程序喚醒用戶程序.在這個時候,在用戶程序裡的對map-reduce調用才返回。(3)spark雲計算平臺spark是由ucberkeleyamp實驗室開發的開元通用並行雲計算平臺，spark基於mapreduce思想實現的分布式計算，擁有hadoopmapreduce所具有的優點；但是不同地方是運算中間輸出結果能存儲在內存中，從而不在需要讀寫分布式文件系統(hdfs)，因此spark能更好的運行數據挖掘與機器學習等需要迭代的mapreduce算法。spark啟用了內存分布數據集，它可以提供交互式查詢，除此之外還可以將數據集緩存在內存中，提高數據集讀寫速率。實現計算過程中的數據集的重用，優化迭代工作負載。spark底層可使用多種分布式文件系統如hdfs文件系統存放數據，不過更多的是與資源調度平臺mesos和yarn一起合作出現。rdd(彈性分布式數據集)是spark的核心，rdd是分布於各個計算節點存儲於內存中的數據對象集合，rdd允許用戶在執行多個查詢時顯式地將工作集緩存在內存中，後續的查詢能夠重用工作集，這極大地提升了查詢速度。rdd分布在多個節點上，並可以對其進行並行處理。rdd是可擴展、彈性的，在運算過程中，內存小於rdd時，可以轉存到磁碟上，確保內存足夠繼續運算。rdd是已被分區、只讀的、不可變的並能夠被並行操作的數據集合，只能通過在其它rdd執行確定的轉換操作(如map、join、filter和groupby)而創建，然而這些限制使得實現容錯的開銷很低。與分布式共享內存系統需要付出高昂代價的檢查點和回滾不同，rdd通過lineage來重建丟失的分區：一個rdd中包含了如何從其它rdd衍生所必需的相關信息，從而不需要檢查點操作就可以重構丟失的數據分區。儘管rdd不是一個通用的共享內存抽象，但卻具備了良好的描述能力、可伸縮性和可靠性，並能夠廣泛適用於數據並行類應用。有關文獻：[文獻1]agrawalr,srikantr.miningsequentialpatterns:the11thinternationalconferenceondataengineering[c].taipei:ieeecomputersociety,1995:3-141.[文獻2]srikantr,agrawalr.miningsequentialpattern:generationsandperformanceimprovement[c]//proceedingsofthe5thinternationalconferenceextendingdatabasetechnology.avignon:lecturenotesincomputerscience,1996:.3-17.[文獻3]zakim.spade:anefficientalgorithmforminingfrequentsequences[j].machinelearning,2001.41(2):31-60.[文獻4]peij,hanj,pintoh.prefixspanminingsequentialpatternsefficientlybyprefix-projectedpatterngrowth[c]//proceedingsofthe17thinternationalconferenceondataengineering.washington,ieeetransactionsondataengineering,2004.16(1):1424-1440.[文獻5]gurainikv,gargn,vipink.paralleltreeprojectionalgorithmforsequencemining[c]//proceedingsofthe7thinternationaleuropeanconferenceonparallelprocessing.london,2001:310-320.[文獻6]龔振志，胡孔法，達慶利，張長海.dmgsp:一種快速分布式全局序列模式挖掘算法[j].東南大學學報，2007.16(04):574-579.[文獻7]zhangchanghai,hukongfa,liuhaidong.fmgsp:anefficientmethodofminingglobalsequentialpatterns[c].//proceedingsofthe4thinternationalconferenceonfuzzysystemsandknowledgediscovery.losalanitosieeecomputersociety.2007:761-765.[文獻8]j.huang,s.lin,m.chen,「dpsp:distributedprogressivesequentialpatternminingonthecloud,」lecturenotesincomputerscience,pp.27-34,2010.[文獻9]d.yu,w.wu,s.zheng,z.zhu,「bide-basedparallelminingoffrequentclosedsequenceswithmapreduce,」in:proceedingsofthe12thinternationalconferenceonalgorithmsandarchitecturesforparallelprocessing,pp.177-1862012.[文獻10]chun-chiehchen,chi-yaotseng,chi-yaotseng,「highlyscalablesequentialpatternminingbasedonmapreducemodelonthecloud,」in2013ieeeinternationalcongressonbigdata,pp.310–317,2013.[文獻11]p.n.sabrina,「miltiplemapreduceandderivativeprojecteddatabase:newapproachforsupportingprefixspanscalability,」ieee,pp.148-153,nov.2015.[文獻12]x.wang,「parallelsequentialpatternminingbytranscationdecompostion,」ieeefuzzysystemsandknowledgediscovery(fskd),2010seventhinternationalconferenceon,vol.4,pp.1746-1750.[文獻13]x.yu,j.liu,c.ma,b.li,「amapreducreinforeceddistirbutedsequentialpatternminingalgorithm,」algorithmsandarchitecturesforparallelprocessing,vol.9529,pp.183-197,dec.2015.[文獻14]jeffreydeanandsanjayghemawat.map-reduce:simplifieddataprocessingonlargecluster[c]//proceedingsofthe6thconferenceonsymposiumonoperatingsystemsdesignandimplementation.newyork:acmpress,2004:137-149.技術實現要素：針對現有的串行化序列模式挖掘算法在處理海量數據時計算能力低效的問題和現有的基於hadoop的並行序列模式挖掘算法具有高io開銷和負載不平衡的問題，本發明提供了一種基於spark平臺的並行序列模式挖掘方法。本發明所採用的技術方案是：一種基於spark平臺的並行序列模式挖掘方法，其特徵在於，包括以下步驟：步驟1：資料庫切分；將序列資料庫切分成相同大小的資料庫分片，分片數根據集群中的工作節點數來確定，使每個資料庫分片中的序列總長度近乎相等；步驟2：資料庫準備；利用一個mapreduce任務產生所有的1-序列模式；步驟3：資料庫挖掘；迭代利用mapreduce任務發現所有k-序列模式，k>1。本發明設計了合理的序列資料庫分解策略，最大限度的解決了負載不平衡的問題。在此基礎上根據mapreduce編程框架的特性，對原始gsp算法進行了並行化，利用spark雲計算平臺的大規模並行計算能力提高了海量數據序列模式挖掘效率。本發明的技術方案具有簡單、快速的特點，能夠較好地提高序列模式挖掘的效率。附圖說明圖1為本發明實施例的流程圖；圖2為本發明實施例的序列資料庫切分示意圖；圖3為本發明實施例的序列資料庫切分結果示意圖；圖4為本發明實施例的資料庫準備執行過程的示意圖；圖5為本發明實施例的資料庫挖掘第一個maprduce任務執行過程的示意圖；圖6為本發明實施例的資料庫挖掘第二個maprduce任務執行過程的示意圖。具體實施方式為了便於本領域普通技術人員理解和實施本發明，下面結合附圖及實施例對本發明作進一步的詳細描述，應當理解，此處所描述的實施示例僅用於說明和解釋本發明，並不用於限定本發明。本發明設計的基於spark平臺的序列模式挖掘算法的流程見附圖1，所有步驟可由本領域技術人員採用計算機軟體技術實現流程自動運行。實施例具體實現過程如下：步驟1，資料庫切分；將序列資料庫切分成相同大小的資料庫分片(分片數根據集群中的工作節點數來確定)，使每個資料庫分片中的序列總長度近乎相等。請見圖2，序列資料庫切分的具體步驟如下：(1)資料庫中所有的序列以序列長度降序形式排序。(2)最前面的n個序列組成了初始的n個資料庫分片，每個資料庫分片包含一條序列模式。每個資料庫分片的總序列長度初始化為其包含的這一條序列的長度。(3)基於n個資料庫分片的總序列長度構建一個最小堆ψ＝{d1,d2,d3,…,dn},其中d1為最小堆根節點，是被分配了最短的序列的序列資料庫分片。(4)獲取最小堆根節點di，將在未被分配的序列中序列長度最大的序列加入di，調整最小堆。(5)重複步驟(4)，直至所有的序列都被分配到序列資料庫片段中。如圖3，本實施例設定將原始序列資料庫劃分為n＝3個子序列資料庫。原始序列資料庫內容如下表1：表1序列號序列s1s2s3s4s5s6首先將資料庫進行排序得到排序後的資料庫：s2s1s6s4s5s3。取前面的三條序列建立初始堆結構，調整建立初始堆。此時三個子序列資料庫及其包含的序列為：子資料庫p1：s2，長度為5；子資料庫p2：s1，長度為4；子資料庫p3：s6，長度為4。其中最小堆根節點為p2。然後依次讀取排序後的序列資料庫。首先讀取序列s4，加入p2，此時p3長度為6。調整最小堆，此時最小堆根節點為p3。讀取序列s5，加入p3，此時p3長度為6。調整最小堆，此時最小堆根節點為p1。讀取序列s3，加入p1，此時p1長度為6。至此序列讀取完畢，資料庫切分步結束。實施例中切分結果保證了每個序列資料庫分片中的序列總長度相同。劃分得到的子序列資料庫1、2、3分別如下表2、3、4：表2序列號序列s2s3表3序列號序列s1s4表4序列號序列s6s5若spark平臺中map節點的個數為q，建議子序列資料庫的個數等於map節點的個數，即n＝q。若nq，在運行該方法時，在沒有任務失敗的情況下n-q個子路徑序列資料庫需要在q個map節點處理完前q個子路徑序列資料庫後才會得到處理，處理效率不高。因此n＝q能夠同時滿足節點利用率和處理效率。步驟2，資料庫準備；在這一步中，利用一個mapreduce任務產生所有的1-序列模式。該步首先調用第一個flatmap函數從序列資料庫片段中讀取每條序列，其中序列以鍵值對的形式存儲。隨後調用另一個flatmap函數將序列切分為項，產生鍵值對。擁有相同鍵的鍵值對被合併傳遞給reduce節點，reduce節點調用reducebykey函數計算鍵值對的支持度，輸出支持度大於等於設定的最小支持度的鍵值對。這些鍵值對的鍵即為1-序列模式，值即為該1-序列模式的支持度計數。實施例設定最小支持度為2，準備步的具體執行過程參見圖4，map節點對資料庫分片1產生鍵值對結果如下表5：表5輸出結果map節點對資料庫分片2產生鍵值對結果如下表6：表6輸出結果map節點對資料庫分片3產生鍵值對結果如下表7：表7輸出結果reduce節點合併具有相同的鍵的鍵值對，輸出支持度大於等於2的鍵值對的結果如下表8：表8序列模式支持度a3c4g4h2步驟3，資料庫挖掘；這一步迭代的利用mapreduce任務發現所有k-序列模式(k>1)。在準備步中產生的1-序列模式存入rdd中而不是hdfs中，以減小io開銷。在第k個mapreduce任務中,每一個map節點首先從rdd中讀取(k-1)-序列模式,通過候選序列模式產生步來產生候選的k-序列模式(ck)。然後調用一個map函數讀取資料庫片段中每條序列s，並判斷候選的k-序列模式c是否是該序列的子序列，如果是子序列則產生鍵值對。擁有相同鍵的鍵值對被合併傳遞給reduce節點。最後,每一個reduce節點調用reducebykey函數計算鍵值對的支持度，輸出支持度大於等於設定的最小支持度的鍵值對，即為最後的k-序列模式(lk)。本實施例設定最小支持度為2，挖掘步中的第1個mapreduce任務具體執行過程參見圖5，map節點1對資料庫分片1產生鍵值對結果如下表9：表9輸出結果map節點2對資料庫分片2產生鍵值對結果如下表10：表10輸出結果map節點3對資料庫分片3產生鍵值對結果如下表11：表11輸出結果reduce節點合併所有的map節點產生的鍵值對，輸出支持度大於等於設定的最小支持度的鍵值對如下表12：表12挖掘步中的第2個mapreduce任務具體執行過程參見圖6，由於每個map節點從rdd中讀取2-序列模式，通過候選序列模式產生步，沒有候選的3-序列模式生成，因此map節點1對資料庫分片1、map節點2對資料庫分片2、map節點3對資料庫分片3均沒有輸出鍵值對，reduce節點合併所有的map節點產生的鍵值對，發現所有的map節點沒有輸出，因此程序終止。本文中所描述的具體實施例僅僅是對本發明精神作舉例說明。本發明所屬
技術領域：
：的技術人員可以對所描述的具體實施例做各種各樣的修改或補充或採用類似的方式替代，但並不會偏離本發明的精神或者超越所附權利要求書所定義的範圍。當前第1頁12當前第1頁12