引言

近些年，隨著傳感器技術(shù)在功能、體積和數(shù)據(jù)傳輸方式上的不斷革新，已得到廣泛應(yīng)用，現(xiàn)在人們身邊隨處可見各種傳感設(shè)備在收集信息，一些大型企業(yè)和國有單位日收集信息量都已接近TB級。這些收集起來的海量數(shù)據(jù)中蘊含了很多對企業(yè)和社會有巨大價值的信息，如何及時準(zhǔn)確地挖掘出這些有利信息成為了一項極富挑戰(zhàn)的課題。

首先是如何進行分類和預(yù)處理，這些數(shù)據(jù)資源規(guī)模龐大且以指數(shù)級形式進行動態(tài)變化，對此傳統(tǒng)的單一節(jié)點的計算能力已捉襟見肘，擴展性差，使得數(shù)據(jù)挖掘系統(tǒng)的挖掘能力受到了極大的限制。此時需要依靠并行處理，旨在提高整個系統(tǒng)的處理能力，將耗費大量計算資源的計算分散到網(wǎng)絡(luò)中的多個節(jié)點上進行并行處理，處理能力隨著節(jié)點數(shù)目的增長可以近乎無限的擴充。其次是挖掘算法，其關(guān)鍵在于如何從給定的軌跡中挖掘出目標(biāo)的典型運動模式，目前已有的序列模式挖掘算法并不能滿足軌跡模式挖掘的要求，因為其只對序列的前后順序敏感，無法保證挖掘出的頻繁序列是挨個連續(xù)的。

本文從MAP/REDUCE并行處理的角度出發(fā)，結(jié)合經(jīng)過改進的PrefixSpan算法，提出一種基于并行計算的頻繁軌跡模式挖掘算法。

1MAP/REDUCE模型簡述

MAP/REDUCE是Google開發(fā)的一種并行分布式編程模型，已在處理海量數(shù)據(jù)領(lǐng)域取得了廣泛應(yīng)用，它通過運用Map/Reduce將輸入的整片數(shù)據(jù)以鍵/值對的形式進行分割和處理，其中Map負責(zé)將整片數(shù)據(jù)拆分為數(shù)據(jù)片段，并將每一個片段分配給一個計算節(jié)點運行產(chǎn)生中間鍵值對，Reduce則相反，負責(zé)將散布在大量不同節(jié)點上的數(shù)據(jù)片段整合，按鍵來合并鍵值對，最后匯總并輸出。在Map/Reduce模型中，每個計算節(jié)點可同時運行Map任務(wù)和Reduce任務(wù)，它將所承接的計算任務(wù)均勻分散到網(wǎng)絡(luò)中大量計算機組成的計算池中，使模型上運行的應(yīng)用程序能及時得到足夠的存儲空間和計算能力來完成相應(yīng)任務(wù)。

Map/Reduce的核心思想是將要執(zhí)行的問題進行分割并以鍵值對的方式來處理數(shù)據(jù)。Map/Reduce的執(zhí)行由master和worker兩種不同類型的節(jié)點負責(zé)，worker負責(zé)數(shù)據(jù)處理,master負責(zé)掌控全局的任務(wù)調(diào)度及不同節(jié)點之間的數(shù)據(jù)共享,執(zhí)行過程如圖1所示。數(shù)據(jù)被分割成大小相等的M個任務(wù)，每一個任務(wù)為大小16?64MB的片段，并在集群里其他節(jié)點上隨機執(zhí)行數(shù)據(jù)片段的備份，這樣可以解決在集群挖掘中普遍存在的存儲容量擴展和服務(wù)器突發(fā)故障所產(chǎn)生的數(shù)據(jù)丟失問題。隨后主節(jié)點master負責(zé)找到狀態(tài)為閑置的worker節(jié)點并為它們分配子任務(wù)（一共有M個Map子任務(wù)和R個Reduce子任務(wù)）。若某個worker節(jié)點被分配Map子任務(wù)，則輸入已分割好的文件片段，處理成鍵值對（KEY/VALUE）并調(diào)用用戶自定的Map函數(shù)將輸入的鍵值對轉(zhuǎn)換成中間結(jié)果（鍵值對）。

Map函數(shù)生成的中間結(jié)果緩存在內(nèi)存中并會周期性的寫入本地硬盤，在分區(qū)函數(shù)的作用下分成了R個區(qū)塊，并將它們在硬盤中的位置信息發(fā)送給MASTER節(jié)點，MASTER節(jié)點在收到后會將位置信息轉(zhuǎn)發(fā)給那些承接了Reduce任務(wù)的WORKER節(jié)點。然后這些WORKER節(jié)點調(diào)用遠程程序從負責(zé)Map任務(wù)的本地計算機的硬盤里讀取之前緩存的中間鍵值對,當(dāng)讀取所有緩存完成后，利用中間結(jié)果的KEY值進行排序,將具有相同鍵的鍵值對合并，再傳遞給用戶自定的REDUCE函數(shù)，生成R個REDUCE結(jié)果。最后MASTER節(jié)點將這R個結(jié)果返回應(yīng)用程序，由應(yīng)用程序?qū)⑵浜喜⑿纬勺罱K結(jié)果。主控節(jié)點[|worker|”勺輸出T~|worker|輸出2

2連續(xù)軌跡模式挖掘算法

在以往關(guān)于序列模式挖掘的問題上，考慮到性能和效率,普遍采用的是Han等人提出的PrefixSpan算法，但這種序列模式挖掘算法并不能直接運用到軌跡模式挖掘中，本文里使用袁和金提出的改進型PrefixSpan算法。

Han等人在2004年發(fā)表了基于前綴投影的PrefixSpan算法。該算法的核心思路是：首先掃描一次序列數(shù)據(jù)庫，得到頻繁1項集，并產(chǎn)生對應(yīng)的投影數(shù)據(jù)庫，然后每個投影數(shù)據(jù)庫進行單獨的遞歸挖掘。算法構(gòu)造前綴模式，它與后綴模式相連得到頻繁模式，從而避免生成候選項集，但是該算法允許挖掘出的頻繁項在其序列里是跳躍、非連續(xù)的。對此，改進型的PrefixSpan算法修改了子序列、前綴、后綴、投影的定義。

首先將子序列定義改為對序列a=<a1，a2,…，%>和b=<b1，b2,bp>，pWq，如果存在整數(shù)i，使得a^b，

af1，ap=bg1,則稱a是b的子序列，或b包含a，這樣一來就對包含關(guān)系進行了限制。

在上面定義的包含關(guān)系的基礎(chǔ)上給出了對應(yīng)的前綴、后綴、投影的概念，給定兩個軌跡序列a=<a1，a2，…，a*和b=<b],if2，■■■，bp>，pWq，只,有當(dāng)aj—b],a-=b2,a?=bpH寸,a

才是b的前綴。

對于投影，給定序列a和b(bea),只有當(dāng)b是d前綴且a是a的最大子序列時，被稱為b在a上的投影。

根據(jù)上面前綴和投影的定義，設(shè)a的投影d=<a,a?…,a?>,前綴b=<b1，b2，…，b?>,可得序列<a?+1，am+2,…，a?>為a對應(yīng)b的后綴。

在以上新定義的基礎(chǔ)上，設(shè)a是一個軌跡模式，那么a-投影數(shù)據(jù)庫為以a為前綴的軌跡序列對應(yīng)a的后綴組成的集合?？梢钥闯?，加入了這個新定義后，只有當(dāng)待投影序列的第一個元素和前綴的最后一個元素相同時才會被投影數(shù)據(jù)庫選中，這樣就能保證挖掘出的都是連續(xù)軌跡片段。

改進后的 PrefixSpan 算法執(zhí)行順序如下：首先挖掘所有的頻繁 -1 序列模式，再從所給出的原始序列里將頻繁 -1 序列后面的所有元素加入到頻繁 1 序列對應(yīng)的子集里。然后針對前面所產(chǎn)生的所有子集，用基于改進后的子序列及前、后綴的定義來遞歸的投影和模式增長進行挖掘，直到不能增長出更長的頻繁序列為止。舉例來說，給定原始序列數(shù)據(jù)庫 SD={<1，2，3，6，7>，<2，3，6，7>，<4，5，3，8，9>，<1，2，3，6>，<4，5，3，9>，<5，3，8，9>}，其中 1 到 9 是項的集合，最小支持度是 2/6=33%，表 1 是使用改進型 PrefixSpan 算法和原始算法結(jié)果的對比。

3基于Map/Reduce的改進PrefixSpan算法。

整個算法分成兩個階段，第一階段用戶給定目標(biāo)序列數(shù)據(jù)庫SD和最小支持度minimum_s,Master節(jié)點將數(shù)據(jù)庫SD分割成n個塊，并交由負責(zé)Map任務(wù)的節(jié)點將所有塊完整遍歷一次，輸出的中間鍵值對的形式是<a,1>,a指的是SD中任意一個項，1指的是出現(xiàn)了一次。Map任務(wù)每掃描一個項,就輸出一個對應(yīng)的<a,1>。在遍歷結(jié)束后，Reduce節(jié)點將所有的中間結(jié)果鍵值對匯總、統(tǒng)計，生成形式為<a,ri>的鍵值對,n指的是匯總后項a出現(xiàn)的全部次數(shù)。與此同時Reduce節(jié)點將n小于minimun_s的鍵值對丟棄，最后輸出的結(jié)果就是頻繁-1序列，至此第一階段結(jié)束。整體過程如圖2所示。

第二階段開始后，將之前第一階段輸岀的所有頻繁-1序列進行分割存儲，交由Map任務(wù)分配給空閑worker節(jié)點，每個節(jié)點對應(yīng)一個頻繁-1序列，并針對每個節(jié)點對應(yīng)的頻繁-1序列并行構(gòu)造其投影數(shù)據(jù)庫，即從所給出的原始序列里將以頻繁-1序列為前綴的后續(xù)所有序列加入其中，并計算支持度。

Map任務(wù)生成的中間鍵值對是以<p,support>的形式存在,p指的是前綴，support指的是對應(yīng)的前綴的支持度。Map任務(wù)結(jié)束后，負責(zé)Reduce的節(jié)點會掃描全部的中間鍵值對并按照支持度進行取舍，最后得到全局范圍的頻繁軌跡序列模式。

4結(jié)語

本文針對傳統(tǒng)串行數(shù)據(jù)挖掘方法無法滿足現(xiàn)今海量數(shù)據(jù)的缺點，提出了一種將Map/Reduce與經(jīng)過修改的傳統(tǒng)數(shù)據(jù)挖掘相結(jié)合的新型并行算法，理論上可通過擴充數(shù)據(jù)節(jié)點的數(shù)量來增強單位時間的處理能力。今后的研究方向是將本文的算法進行優(yōu)化，使效率更高，以及如何對海量數(shù)據(jù)在進行數(shù)據(jù)挖掘前進行必要的預(yù)處理。

20211223_61c35e59b69ff__基于MAP