基于MAPREDUCE并行處理的軌跡模式挖掘算法的研究

李偉亮　馬傳香　彭茗菁

摘 要：關聯規則算法中FP-Growth算法雖不產生候選集，但由于算法高度依賴于內存空間，阻礙了算法在大數據領域的發揮，因此，改進了經典的FP-Growth算法，首先創建支持度計數表，避免了算法對條件模式基的第一次遍歷，減少了對數據庫的掃描次數；其次利用剪枝策略刪去了大量沉余的非頻繁項集；最后將算法并行化，利用 Hadoop平臺優勢極大提高數據處理的效率，同時解決了算法占用內存的瓶頸問題。實驗結果表明，改進型FP-Growth算法挖掘和預測軌跡的效率明顯高于經典算法。

關鍵詞：改進型FP-Growth；Map-Reduce；Hadoop；軌跡預測

中圖分類號：TP391 文獻標志碼：A 文章編號：2095-1302（2014）10-00-03

0 引 言

隨著我國經濟社會的穩步推進，各大城市的發展取得了令人矚目的成就。與此同時，大城市的機動車保有量與日俱增，交通擁擠的問題日益嚴重。盡管市政和交通管理部門投入了大量的人力、物力和財力建設，但城市交通擁堵現象仍然不能有效解決。要做到合理分布交通流，使單位時間的道路通行量最大且使用效率高，就需要做到合理規劃和預測路網中車輛軌跡和車輛路徑。本文提出基于改進FP-Growth算法的車輛預測方法，利用Map/Reduce編程進行大數據的并行計算，提高了算法效率，解決了交通管理部門監測當前時間車流量信息的目的，為交通管理部門和相關車輛及時發布預警信息提供了決策支持。

1 FP-Growth算法概述

J.W.Han[1，2]等人克服了Apriori算法產生基數龐大的候選集和在計算支持度時多次掃描數據庫的弱點，提出FP-Growth算法。其思想是通過掃描2次數據庫構造FP-Tree和Header Table，從而得到用于頻繁項集挖掘的壓縮的數據庫映射，然后對每個頻繁項構造其條件FP-Tree進行頻繁項集的挖掘，最終得到頻繁項集。與Apriori算法比較FP-Growth算法不產生候選集，采用FP-Tree壓縮所有能夠提供頻繁項信息的項集，節省了時間和空間的消耗，相對Apriori算法的執行速度和內存消耗已經有了一個數量級的改善。

1.1 FP-Growth改進

由于FP-Growth是基于內存駐留的算法，在頻繁項挖掘時遞歸生成大量條件FP-Tree，當數據庫達到一定規模時，基于內存的FP-Tree已經無法有效應對，極容易造成內存溢出，這正是FP-Growth算法的瓶頸所在。因而，FP-Growth算法在挖掘大數據問題上有較大擴展空間。

針對當前交通的大數據背景，傳統FP-Growth算法和以上改進算法的優勢不足以處理大規模交通數據問題。因此，本文就針對交通大數據給出FP-Growth算法改進的解決方案：

（1）建立支持度計數表。在第一次遍歷事務集合T的同時創建二維向量，記錄每個事務中各個項兩兩組合出現的支持度計數；利用遞歸方式創建后綴模式S（ S ≠{Null}）條件下的條件FP子樹，此時，第一次遍歷條件模式基得到支持度計數列表，第二次遍歷條件模式基插入樹節點從而創建FP樹；遍歷條件模式基，創建FP子樹的同時創建新的支持度計數二維向量表。

（2）非頻繁項的剪枝策略。假設項集k在某一個路徑上是非頻繁的；若項集k在 FP-tree 中存在前綴路徑集合A與集合B，并且滿足集合B包含于集合A，那么集合A中的項集k就可以被剪枝與短路徑集合B合并。

1.2 Map-Reduce 并行處理

Map-Reduce最初是由Google提出的，它是一種可以處理海量數據的并行編程模型。該模型把所有的數據問題抽象成Map和Reduce兩個函數。以可靠的并行方式處理大規模數據集，其中Map函數把問題進行分解，Reduce函數負責把分解的任務進行規約處理。

利用Map-Reduce編程模型，經統計頻繁1-項和遞歸挖掘頻繁項集的兩次并行處理，對改進后的FR-Growth算法步驟并行化。其描述為：首先，對頻繁1-項集的頻率統計；再利用頻繁1-項集的頻率統計結果建立一個哈希表，按照哈希表對數據進行分組，把數據分成了若干個部分；然后對分解后的數據進行關聯規則挖掘；最后，匯總最終的頻繁模式。

圖1 Map-Reduce任務處理流程

圖2 基于Map-Reduce的頻繁軌跡挖掘

2 基于模式匹配的軌跡預測

根據基于Map/Reduce的頻繁軌跡挖掘得到的序列模式進行軌跡預測。通過Map/Reduce并行計算獲得頻繁模式集合后，就可以計算出與查詢軌跡最為相似的頻繁模式，用該模式就可以預測軌跡的未來走向。

對于移動對象數據庫D，存儲的是海量移動對象在各時間采樣點的位置信息。位置信息在時間上的有序集合為軌跡，用D={T1，T2，…，Tn）表示，則|D|表示數據庫中包含的軌跡數量。在三維X×Y×T空間里，軌跡T是移動對象在空間內位置信息的有序組合，可以表示為T=（t1，x1，y1），（t2，x2，y2），…，（tn，xn，yn）。其中ti表示時間戳，（xi，yi）表示移動對象的空間位置坐標。

軌跡匹配，是從頻繁模式中找出與查詢軌跡片段匹配權重最高的模式。假設用戶的查詢軌跡片段為Q=，軌跡頻繁模式為P=，則Q的預測由Q和P=的匹配程度進行反映。軌跡片段在時間上最靠近當前的元素是優先考慮的，當i1，w1默認為1，因此軌跡Q、P的相似度計算公式為：

如查詢軌跡片段Q=，頻繁模式為P，Q和P的公共元素有，c和d的權重分別是100和10，假設k=10，因此Q和P似度為Sim（Q，P）=10+100/1+10+100，表明f極有可能為軌跡Q的未來軌跡。

3 算法與實驗

本文實驗環境采用4臺PC機做分布式環境。操作系統為Ubuntu 14.04 -32bit，Hadoop 2.4.0，CPU為Inter Core i7處理器，主頻2.1 GHz，單機內存為512 MB。

3.1 頻繁1-項統計

其Map-Reduce算法偽代碼如下：

map（key，value）{ //value為事務Ti

for each ki∈Ti do

output；

end

}

reduce（key，value）{//key為一個1-項集，value為其支持數列表[1，1，…，1]

C=0；

for each v in value do

C+=1；

end

ifC/|D|minsup then

output；//輸出頻繁1-項集及其支持數

end

}

3.2 FP-Growth并行化

其Map-Reduce算法偽代碼如下：

map（key，value）{ //value為事務Ti

insert_build_fptree（LFPTree，Ti）；//更新局部FP樹LFPTree

}

cleanup（）{

LocalFPGrowth（LFPTree，LFPSet）；//將局部頻繁項目集及其支持數放入LFPSet中

for each lfp∈LFPSet do

output；//sup（lfp）為局部頻繁項目集lfp的支持數

end

}

reduce（key，value）{//key為項目集，value為其支持數列表

C=0；

for each vi in value do

C+=vi；

end

if C/|D|≥minsup then

output；//輸出全局頻繁項目集及其支持數

else if

write key into a distribute file；//若暫不確定是否全局頻繁，則將其寫入分布式文件

end

}

4 結 語

本文結合歷史車輛軌跡數據利用改進型的關聯規則算法FP-Growth挖掘出軌跡模式索引，并提出基于Map/Reduce算法的軌跡預測方案。在路網中利用索引樹對車輛未來軌跡進行預測，預判出車流趨勢，為交通管理部門及時做出交通疏導方案的決策提供了支持。

參考文獻

[1] J.W.Han， JianPen， Yin YiWen.Mining frequent patterns without candidate generation[C].In the proceedingsof ACM SIGMOD International Conference on Management of Data，Dallas， Texas：2000：1-12.

[2] J. G.LEE， J. W.HAN， WHANG K. Y. Trajectory clustering： a partition-and-group framework [A]. ICMD2007：Proceedings of the ACM SIGMOD International Conference on Management ofData[C]. Beijing， China， 2007， 593-604.

[3]袁冠，夏士雄，張磊. 基于結構相似度的軌跡聚類算法[J]. 通信學報.2011（9）：103-110.

[4]趙越，劉衍珩，余雪崗，等. 基于模式挖掘與匹配的移動軌跡預測方法[J]. 吉林大學學報. 2008，38（5）：1125-1130.

[5]章志剛，吉根林. 一種基于FP-Growth的頻繁項目集并行化挖掘算法[J]. 計算機工程與應用2014，50（2）：107-110.

[6] CHEN L.， LV M. Q.， CHEN G. C. A system for destination and future route prediction based on trajectory mining[J]. Journal of Pervasive and Mobile Computing， 2010，6（6）：657-676.

[7] ZhouLe， LiJunjie， HuangZhexue， FengShenzhong. Balanced Parallel FP-Growth withMapReduce[J]. Bulletin of advanced technology reseach，2011（6）：47-50.

3 算法與實驗

本文實驗環境采用4臺PC機做分布式環境。操作系統為Ubuntu 14.04 -32bit，Hadoop 2.4.0，CPU為Inter Core i7處理器，主頻2.1 GHz，單機內存為512 MB。

3.1 頻繁1-項統計

其Map-Reduce算法偽代碼如下：

map（key，value）{ //value為事務Ti

for each ki∈Ti do

output；

end

}

reduce（key，value）{//key為一個1-項集，value為其支持數列表[1，1，…，1]

C=0；

for each v in value do

C+=1；

end

ifC/|D|minsup then

output；//輸出頻繁1-項集及其支持數

end

}

3.2 FP-Growth并行化

其Map-Reduce算法偽代碼如下：

map（key，value）{ //value為事務Ti

insert_build_fptree（LFPTree，Ti）；//更新局部FP樹LFPTree

}

cleanup（）{

LocalFPGrowth（LFPTree，LFPSet）；//將局部頻繁項目集及其支持數放入LFPSet中

for each lfp∈LFPSet do

output；//sup（lfp）為局部頻繁項目集lfp的支持數

end

}

reduce（key，value）{//key為項目集，value為其支持數列表

C=0；

for each vi in value do

C+=vi；

end

if C/|D|≥minsup then

output；//輸出全局頻繁項目集及其支持數

else if

write key into a distribute file；//若暫不確定是否全局頻繁，則將其寫入分布式文件

end

}

4 結 語

本文結合歷史車輛軌跡數據利用改進型的關聯規則算法FP-Growth挖掘出軌跡模式索引，并提出基于Map/Reduce算法的軌跡預測方案。在路網中利用索引樹對車輛未來軌跡進行預測，預判出車流趨勢，為交通管理部門及時做出交通疏導方案的決策提供了支持。

參考文獻

[1] J.W.Han， JianPen， Yin YiWen.Mining frequent patterns without candidate generation[C].In the proceedingsof ACM SIGMOD International Conference on Management of Data，Dallas， Texas：2000：1-12.

[2] J. G.LEE， J. W.HAN， WHANG K. Y. Trajectory clustering： a partition-and-group framework [A]. ICMD2007：Proceedings of the ACM SIGMOD International Conference on Management ofData[C]. Beijing， China， 2007， 593-604.

[3]袁冠，夏士雄，張磊. 基于結構相似度的軌跡聚類算法[J]. 通信學報.2011（9）：103-110.

[4]趙越，劉衍珩，余雪崗，等. 基于模式挖掘與匹配的移動軌跡預測方法[J]. 吉林大學學報. 2008，38（5）：1125-1130.

[5]章志剛，吉根林. 一種基于FP-Growth的頻繁項目集并行化挖掘算法[J]. 計算機工程與應用2014，50（2）：107-110.

[6] CHEN L.， LV M. Q.， CHEN G. C. A system for destination and future route prediction based on trajectory mining[J]. Journal of Pervasive and Mobile Computing， 2010，6（6）：657-676.

[7] ZhouLe， LiJunjie， HuangZhexue， FengShenzhong. Balanced Parallel FP-Growth withMapReduce[J]. Bulletin of advanced technology reseach，2011（6）：47-50.

3 算法與實驗

本文實驗環境采用4臺PC機做分布式環境。操作系統為Ubuntu 14.04 -32bit，Hadoop 2.4.0，CPU為Inter Core i7處理器，主頻2.1 GHz，單機內存為512 MB。

3.1 頻繁1-項統計

其Map-Reduce算法偽代碼如下：

map（key，value）{ //value為事務Ti

for each ki∈Ti do

output；

end

}

reduce（key，value）{//key為一個1-項集，value為其支持數列表[1，1，…，1]

C=0；

for each v in value do

C+=1；

end

ifC/|D|minsup then

output；//輸出頻繁1-項集及其支持數

end

}

3.2 FP-Growth并行化

其Map-Reduce算法偽代碼如下：

map（key，value）{ //value為事務Ti

insert_build_fptree（LFPTree，Ti）；//更新局部FP樹LFPTree

}

cleanup（）{

LocalFPGrowth（LFPTree，LFPSet）；//將局部頻繁項目集及其支持數放入LFPSet中

for each lfp∈LFPSet do

output；//sup（lfp）為局部頻繁項目集lfp的支持數

end

}

reduce（key，value）{//key為項目集，value為其支持數列表

C=0；

for each vi in value do

C+=vi；

end

if C/|D|≥minsup then

output；//輸出全局頻繁項目集及其支持數

else if

write key into a distribute file；//若暫不確定是否全局頻繁，則將其寫入分布式文件

end

}

4 結 語

本文結合歷史車輛軌跡數據利用改進型的關聯規則算法FP-Growth挖掘出軌跡模式索引，并提出基于Map/Reduce算法的軌跡預測方案。在路網中利用索引樹對車輛未來軌跡進行預測，預判出車流趨勢，為交通管理部門及時做出交通疏導方案的決策提供了支持。

參考文獻

[1] J.W.Han， JianPen， Yin YiWen.Mining frequent patterns without candidate generation[C].In the proceedingsof ACM SIGMOD International Conference on Management of Data，Dallas， Texas：2000：1-12.

[2] J. G.LEE， J. W.HAN， WHANG K. Y. Trajectory clustering： a partition-and-group framework [A]. ICMD2007：Proceedings of the ACM SIGMOD International Conference on Management ofData[C]. Beijing， China， 2007， 593-604.

[3]袁冠，夏士雄，張磊. 基于結構相似度的軌跡聚類算法[J]. 通信學報.2011（9）：103-110.

[4]趙越，劉衍珩，余雪崗，等. 基于模式挖掘與匹配的移動軌跡預測方法[J]. 吉林大學學報. 2008，38（5）：1125-1130.

[5]章志剛，吉根林. 一種基于FP-Growth的頻繁項目集并行化挖掘算法[J]. 計算機工程與應用2014，50（2）：107-110.

[6] CHEN L.， LV M. Q.， CHEN G. C. A system for destination and future route prediction based on trajectory mining[J]. Journal of Pervasive and Mobile Computing， 2010，6（6）：657-676.

[7] ZhouLe， LiJunjie， HuangZhexue， FengShenzhong. Balanced Parallel FP-Growth withMapReduce[J]. Bulletin of advanced technology reseach，2011（6）：47-50.