基于MAP/REDUCE的移動(dòng)目標(biāo)連續(xù)軌跡模式挖掘的研究

引言

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

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

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

1MAP/REDUCE模型簡(jiǎn)述

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

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

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

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

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

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

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

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

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

才是b的前綴。

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

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

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

改進(jìn)后的 PrefixSpan 算法執(zhí)行順序如下：首先挖掘所有的頻繁 -1 序列模式，再?gòu)乃o出的原始序列里將頻繁 -1 序列后面的所有元素加入到頻繁 1 序列對(duì)應(yīng)的子集里。然后針對(duì)前面所產(chǎn)生的所有子集，用基于改進(jìn)后的子序列及前、后綴的定義來(lái)遞歸的投影和模式增長(zhǎng)進(jìn)行挖掘，直到不能增長(zhǎng)出更長(zhǎng)的頻繁序列為止。舉例來(lái)說(shuō)，給定原始序列數(shù)據(jù)庫(kù) 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 是項(xiàng)的集合，最小支持度是 2/6=33%，表 1 是使用改進(jìn)型 PrefixSpan 算法和原始算法結(jié)果的對(duì)比。

3基于Map/Reduce的改進(jìn)PrefixSpan算法。

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

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

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

4結(jié)語(yǔ)

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

20211223_61c35e59b69ff__基于MAP