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

彭茗菁　馬傳香　李偉亮

摘 要：針對傳統(tǒng)序列模式挖掘算法都是針對單機環(huán)境、靜態(tài)實例以及非連續(xù)軌跡的不足，提出了Map/Reduce系統(tǒng)與經(jīng)過優(yōu)化的PrefixSpan序列模式挖掘算法相結合的改進型算法。該算法在生成投影數(shù)據(jù)庫時，只有當待投影序列的第一個元素和前綴的最后一個元素相同時才會被選中，保證了挖掘出的都是連續(xù)軌跡片段。同時采用并行處理的方法，使用Map函數(shù)構建每個頻繁序列前綴對應的投影數(shù)據(jù)庫，使用Reduce函數(shù)整合所有的中間鍵值對得到需要的結果。

關鍵詞：Map/Reduce模型；改進型PrefixSpan算法；軌跡模式；數(shù)據(jù)挖掘

中圖分類號：TP311 文獻標識碼：A 文章編號：2095-1302（2014）10-00-02

0 引 言

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

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

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

1 MAP/REDUCE模型簡述

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

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

Map函數(shù)生成的中間結果緩存在內存中并會周期性的寫入本地硬盤，在分區(qū)函數(shù)的作用下分成了R個區(qū)塊，并將它們在硬盤中的位置信息發(fā)送給MASTER節(jié)點，MASTER節(jié)點在收到后會將位置信息轉發(fā)給那些承接了Reduce任務的WORKER節(jié)點。然后這些WORKER節(jié)點調用遠程程序從負責Map任務的本地計算機的硬盤里讀取之前緩存的中間鍵值對，當讀取所有緩存完成后，利用中間結果的KEY值進行排序，將具有相同鍵的鍵值對合并，再傳遞給用戶自定的REDUCE函數(shù)，生成R個REDUCE結果。最后MASTER節(jié)點將這R個結果返回應用程序，由應用程序將其合并形成最終結果。

圖1 Map/Reduce執(zhí)行過程

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

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

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

首先將子序列定義改為對序列a=和b=，p≤q，如果存在整數(shù)i，使得a1=bi，a2=bi+1，ap=bi+p-1 ，則稱a是b的子序列，或b包含a，這樣一來就對包含關系進行了限制。

在上面定義的包含關系的基礎上給出了對應的前綴、后綴、投影的概念，給定兩個軌跡序列a=和b=，p≤q，只有當a1=b1，a2=b2，ap=bp時，a才是b的前綴。

對于投影，給定序列a和b（b∈a），只有當b是a'前綴且a'是a的最大子序列時，被稱為b在a上的投影。

根據(jù)上面前綴和投影的定義，設a的投影a'=，前綴b=，可得序列為a對應b的后綴。

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

改進后的PrefixSpan算法執(zhí)行順序如下：首先挖掘所有的頻繁-1序列模式，再從所給出的原始序列里將頻繁-1序列后面的所有元素加入到頻繁1序列對應的子集里。然后針對前面所產(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算法和原始算法結果的對比。

表1 改進型算法和原始算法結果對比

改進型算法 原始算法

前綴 頻繁模式

<3> <3，6，7>，<3，8，9> <3，7>，<3，9>，<3，6，7>，<3，8，9>

<2> <2，3，6，7> <2，7>，<2，3，7>，<2，3，6，7>

<5> <5，3，8，9> <5，3，8，9>，<5，3，9>

<6> <6，7> <6，7>

<9> <9> <9>

<1> <1，2，3，6> <1，6>，<1，2，6>，<1，2，3，6>

<4> <4，5，3> <4，9>，<4，5，9>，<4，5，3，9>

<7> <7> <7>

<8> <8，9> <8，9>

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

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

圖2 算法執(zhí)行過程

第二階段開始后，將之前第一階段輸出的所有頻繁-1序列進行分割存儲，交由Map任務分配給空閑worker節(jié)點，每個節(jié)點對應一個頻繁-1序列，并針對每個節(jié)點對應的頻繁-1序列并行構造其投影數(shù)據(jù)庫，即從所給出的原始序列里將以頻繁-1序列為前綴的后續(xù)所有序列加入其中，并計算支持度。Map任務生成的中間鍵值對是以的形式存在，p指的是前綴，support指的是對應的前綴的支持度。Map任務結束后，負責Reduce的節(jié)點會掃描全部的中間鍵值對并按照支持度進行取舍，最后得到全局范圍的頻繁軌跡序列模式。

4 結 語

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

參考文獻

[1]袁和金. 視頻目標軌跡分析的改進PrefixSpan方法[J].計算機工程與應用，2011，47（32）：7-10.

[2]劉騫，陳明.基于Map/Reduce集群上的模式空間劃分的序列模式挖掘[J].微電子學與計算機，2012（9）：149-151.

[3] Pei J，Han J，Mortazavi-Asl B，et al.Mining sequential patterns by pattern-growth：the PrefixSpan approach[J].IEEE Transactions on Knowledge and Data Engineering，2004，16（11）：1424-1440.

[4] JEFFREYD，SANJAYG.Map/Reduce：simplified data processing on large clusters[J].Communications of the ACM，2008，51（1）：107-113.

根據(jù)上面前綴和投影的定義，設a的投影a'=，前綴b=，可得序列為a對應b的后綴。

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

改進后的PrefixSpan算法執(zhí)行順序如下：首先挖掘所有的頻繁-1序列模式，再從所給出的原始序列里將頻繁-1序列后面的所有元素加入到頻繁1序列對應的子集里。然后針對前面所產(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算法和原始算法結果的對比。

表1 改進型算法和原始算法結果對比

改進型算法 原始算法

前綴 頻繁模式

<3> <3，6，7>，<3，8，9> <3，7>，<3，9>，<3，6，7>，<3，8，9>

<2> <2，3，6，7> <2，7>，<2，3，7>，<2，3，6，7>

<5> <5，3，8，9> <5，3，8，9>，<5，3，9>

<6> <6，7> <6，7>

<9> <9> <9>

<1> <1，2，3，6> <1，6>，<1，2，6>，<1，2，3，6>

<4> <4，5，3> <4，9>，<4，5，9>，<4，5，3，9>

<7> <7> <7>

<8> <8，9> <8，9>

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

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

圖2 算法執(zhí)行過程

第二階段開始后，將之前第一階段輸出的所有頻繁-1序列進行分割存儲，交由Map任務分配給空閑worker節(jié)點，每個節(jié)點對應一個頻繁-1序列，并針對每個節(jié)點對應的頻繁-1序列并行構造其投影數(shù)據(jù)庫，即從所給出的原始序列里將以頻繁-1序列為前綴的后續(xù)所有序列加入其中，并計算支持度。Map任務生成的中間鍵值對是以的形式存在，p指的是前綴，support指的是對應的前綴的支持度。Map任務結束后，負責Reduce的節(jié)點會掃描全部的中間鍵值對并按照支持度進行取舍，最后得到全局范圍的頻繁軌跡序列模式。

4 結 語

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

參考文獻

[1]袁和金. 視頻目標軌跡分析的改進PrefixSpan方法[J].計算機工程與應用，2011，47（32）：7-10.

[2]劉騫，陳明.基于Map/Reduce集群上的模式空間劃分的序列模式挖掘[J].微電子學與計算機，2012（9）：149-151.

[3] Pei J，Han J，Mortazavi-Asl B，et al.Mining sequential patterns by pattern-growth：the PrefixSpan approach[J].IEEE Transactions on Knowledge and Data Engineering，2004，16（11）：1424-1440.

[4] JEFFREYD，SANJAYG.Map/Reduce：simplified data processing on large clusters[J].Communications of the ACM，2008，51（1）：107-113.

根據(jù)上面前綴和投影的定義，設a的投影a'=，前綴b=，可得序列為a對應b的后綴。

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

改進后的PrefixSpan算法執(zhí)行順序如下：首先挖掘所有的頻繁-1序列模式，再從所給出的原始序列里將頻繁-1序列后面的所有元素加入到頻繁1序列對應的子集里。然后針對前面所產(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算法和原始算法結果的對比。

表1 改進型算法和原始算法結果對比

改進型算法 原始算法

前綴 頻繁模式

<3> <3，6，7>，<3，8，9> <3，7>，<3，9>，<3，6，7>，<3，8，9>

<2> <2，3，6，7> <2，7>，<2，3，7>，<2，3，6，7>

<5> <5，3，8，9> <5，3，8，9>，<5，3，9>

<6> <6，7> <6，7>

<9> <9> <9>

<1> <1，2，3，6> <1，6>，<1，2，6>，<1，2，3，6>

<4> <4，5，3> <4，9>，<4，5，9>，<4，5，3，9>

<7> <7> <7>

<8> <8，9> <8，9>

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

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

圖2 算法執(zhí)行過程

第二階段開始后，將之前第一階段輸出的所有頻繁-1序列進行分割存儲，交由Map任務分配給空閑worker節(jié)點，每個節(jié)點對應一個頻繁-1序列，并針對每個節(jié)點對應的頻繁-1序列并行構造其投影數(shù)據(jù)庫，即從所給出的原始序列里將以頻繁-1序列為前綴的后續(xù)所有序列加入其中，并計算支持度。Map任務生成的中間鍵值對是以的形式存在，p指的是前綴，support指的是對應的前綴的支持度。Map任務結束后，負責Reduce的節(jié)點會掃描全部的中間鍵值對并按照支持度進行取舍，最后得到全局范圍的頻繁軌跡序列模式。

4 結 語

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

參考文獻

[1]袁和金. 視頻目標軌跡分析的改進PrefixSpan方法[J].計算機工程與應用，2011，47（32）：7-10.

[2]劉騫，陳明.基于Map/Reduce集群上的模式空間劃分的序列模式挖掘[J].微電子學與計算機，2012（9）：149-151.

[3] Pei J，Han J，Mortazavi-Asl B，et al.Mining sequential patterns by pattern-growth：the PrefixSpan approach[J].IEEE Transactions on Knowledge and Data Engineering，2004，16（11）：1424-1440.

[4] JEFFREYD，SANJAYG.Map/Reduce：simplified data processing on large clusters[J].Communications of the ACM，2008，51（1）：107-113.