彭茗菁　馬傳香　李偉亮

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

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

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：2095-1302（2014）10-00-02

0 引 言

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

首先是如何進(jìn)行分類和預(yù)處理，這些數(shù)據(jù)資源規(guī)模龐大且以指數(shù)級形式進(jìn)行動(dòng)態(tài)變化，對此傳統(tǒng)的單一節(jié)點(diǎn)的計(jì)算能力已捉襟見肘，擴(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ù)目的增長可以近乎無限的擴(kuò)充。其次是挖掘算法，其關(guān)鍵在于如何從給定的軌跡中挖掘出目標(biāo)的典型運(yùn)動(dòng)模式，目前已有的序列模式挖掘算法并不能滿足軌跡模式挖掘的要求，因?yàn)槠渲粚π蛄械那昂箜樞蛎舾?，無法保證挖掘出的頻繁序列是挨個(gè)連續(xù)的。

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

1 MAP/REDUCE模型簡述

MAP/REDUCE是Google開發(fā)的一種并行分布式編程模型，已在處理海量數(shù)據(jù)領(lǐng)域取得了廣泛應(yīng)用，它通過運(yùn)用Map/Reduce將輸入的整片數(shù)據(jù)以鍵/值對的形式進(jìn)行分割和處理，其中Map負(fù)責(zé)將整片數(shù)據(jù)拆分為數(shù)據(jù)片段，并將每一個(gè)片段分配給一個(gè)計(jì)算節(jié)點(diǎn)運(yùn)行產(chǎn)生中間鍵值對，Reduce則相反，負(fù)責(zé)將散布在大量不同節(jié)點(diǎn)上的數(shù)據(jù)片段整合，按鍵來合并鍵值對，最后匯總并輸出。在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ì)算能力來完成相應(yīng)任務(wù)。

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

Map函數(shù)生成的中間結(jié)果緩存在內(nèi)存中并會(huì)周期性的寫入本地硬盤，在分區(qū)函數(shù)的作用下分成了R個(gè)區(qū)塊，并將它們在硬盤中的位置信息發(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ī)的硬盤里讀取之前緩存的中間鍵值對，當(dāng)讀取所有緩存完成后，利用中間結(jié)果的KEY值進(jìn)行排序，將具有相同鍵的鍵值對合并，再傳遞給用戶自定的REDUCE函數(shù)，生成R個(gè)REDUCE結(jié)果。最后MASTER節(jié)點(diǎn)將這R個(gè)結(jié)果返回應(yīng)用程序，由應(yīng)用程序?qū)⑵浜喜⑿纬勺罱K結(jié)果。

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

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

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

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

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

在上面定義的包含關(guān)系的基礎(chǔ)上給出了對應(yīng)的前綴、后綴、投影的概念，給定兩個(gè)軌跡序列a=和b=，p≤q，只有當(dāng)a1=b1，a2=b2，ap=bp時(shí)，a才是b的前綴。

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

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

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

改進(jìn)后的PrefixSpan算法執(zhí)行順序如下：首先挖掘所有的頻繁-1序列模式，再從所給出的原始序列里將頻繁-1序列后面的所有元素加入到頻繁1序列對應(yīng)的子集里。然后針對前面所產(chǎn)生的所有子集，用基于改進(jìn)后的子序列及前、后綴的定義來遞歸的投影和模式增長進(jì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是項(xiàng)的集合，最小支持度是2/6=33%，表1是使用改進(jìn)型PrefixSpan算法和原始算法結(jié)果的對比。

表1 改進(jìn)型算法和原始算法結(jié)果對比

改進(jìn)型算法 原始算法

前綴 頻繁模式

<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的改進(jìn)PrefixSpan算法。

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

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

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

4 結(jié) 語

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

參考文獻(xiàn)

[1]袁和金. 視頻目標(biāo)軌跡分析的改進(jìn)PrefixSpan方法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（32）：7-10.

[2]劉騫，陳明.基于Map/Reduce集群上的模式空間劃分的序列模式挖掘[J].微電子學(xué)與計(jì)算機(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ù)上面前綴和投影的定義，設(shè)a的投影a'=，前綴b=，可得序列為a對應(yīng)b的后綴。

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

改進(jìn)后的PrefixSpan算法執(zhí)行順序如下：首先挖掘所有的頻繁-1序列模式，再從所給出的原始序列里將頻繁-1序列后面的所有元素加入到頻繁1序列對應(yīng)的子集里。然后針對前面所產(chǎn)生的所有子集，用基于改進(jìn)后的子序列及前、后綴的定義來遞歸的投影和模式增長進(jì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是項(xiàng)的集合，最小支持度是2/6=33%，表1是使用改進(jìn)型PrefixSpan算法和原始算法結(jié)果的對比。

表1 改進(jìn)型算法和原始算法結(jié)果對比

改進(jìn)型算法 原始算法

前綴 頻繁模式

<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的改進(jìn)PrefixSpan算法。

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

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

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

4 結(jié) 語

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

參考文獻(xiàn)

[1]袁和金. 視頻目標(biāo)軌跡分析的改進(jìn)PrefixSpan方法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（32）：7-10.

[2]劉騫，陳明.基于Map/Reduce集群上的模式空間劃分的序列模式挖掘[J].微電子學(xué)與計(jì)算機(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ù)上面前綴和投影的定義，設(shè)a的投影a'=，前綴b=，可得序列為a對應(yīng)b的后綴。

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

改進(jìn)后的PrefixSpan算法執(zhí)行順序如下：首先挖掘所有的頻繁-1序列模式，再從所給出的原始序列里將頻繁-1序列后面的所有元素加入到頻繁1序列對應(yīng)的子集里。然后針對前面所產(chǎn)生的所有子集，用基于改進(jìn)后的子序列及前、后綴的定義來遞歸的投影和模式增長進(jì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是項(xiàng)的集合，最小支持度是2/6=33%，表1是使用改進(jìn)型PrefixSpan算法和原始算法結(jié)果的對比。

表1 改進(jìn)型算法和原始算法結(jié)果對比

改進(jìn)型算法 原始算法

前綴 頻繁模式

<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的改進(jìn)PrefixSpan算法。

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

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

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

4 結(jié) 語

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

參考文獻(xiàn)

[1]袁和金. 視頻目標(biāo)軌跡分析的改進(jìn)PrefixSpan方法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（32）：7-10.

[2]劉騫，陳明.基于Map/Reduce集群上的模式空間劃分的序列模式挖掘[J].微電子學(xué)與計(jì)算機(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.