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

彭茗菁　馬傳香　李偉亮

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

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

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

0 引 言

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

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

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

1 MAP/REDUCE模型簡述

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

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

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

圖1 Map/Reduce執行過程

2 連續軌跡模式挖掘算法

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

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

首先將子序列定義改為對序列a=和b=，p≤q，如果存在整數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上的投影。

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

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

改進后的PrefixSpan算法執行順序如下：首先挖掘所有的頻繁-1序列模式，再從所給出的原始序列里將頻繁-1序列后面的所有元素加入到頻繁1序列對應的子集里。然后針對前面所產生的所有子集，用基于改進后的子序列及前、后綴的定義來遞歸的投影和模式增長進行挖掘，直到不能增長出更長的頻繁序列為止。舉例來說，給定原始序列數據庫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算法。

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

圖2 算法執行過程

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

4 結 語

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

參考文獻

[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.

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

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

改進后的PrefixSpan算法執行順序如下：首先挖掘所有的頻繁-1序列模式，再從所給出的原始序列里將頻繁-1序列后面的所有元素加入到頻繁1序列對應的子集里。然后針對前面所產生的所有子集，用基于改進后的子序列及前、后綴的定義來遞歸的投影和模式增長進行挖掘，直到不能增長出更長的頻繁序列為止。舉例來說，給定原始序列數據庫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算法。

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

圖2 算法執行過程

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

4 結 語

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

參考文獻

[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.

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

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

改進后的PrefixSpan算法執行順序如下：首先挖掘所有的頻繁-1序列模式，再從所給出的原始序列里將頻繁-1序列后面的所有元素加入到頻繁1序列對應的子集里。然后針對前面所產生的所有子集，用基于改進后的子序列及前、后綴的定義來遞歸的投影和模式增長進行挖掘，直到不能增長出更長的頻繁序列為止。舉例來說，給定原始序列數據庫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算法。

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

圖2 算法執行過程

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

4 結 語

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

參考文獻

[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.