基于MAPREDUCE并行處理的軌跡模式挖掘算法的研究
掃描二維碼
隨時(shí)隨地手機(jī)看文章
引言
隨著我國(guó)經(jīng)濟(jì)社會(huì)的穩(wěn)步推進(jìn),各大城市的發(fā)展取得了 令人矚目的成就。與此同時(shí),大城市的機(jī)動(dòng)車(chē)保有量與日俱增, 交通擁擠的問(wèn)題日益嚴(yán)重。盡管市政和交通管理部門(mén)投入了大 量的人力、物力和財(cái)力建設(shè),但城市交通擁堵現(xiàn)象仍然不能 有效解決。要做到合理分布交通流,使單位時(shí)間的道路通行 量最大且使用效率高,就需要做到合理規(guī)劃和預(yù)測(cè)路網(wǎng)中車(chē) 輛軌跡和車(chē)輛路徑。本文提出基于改進(jìn)FP-Growth算法的車(chē) 輛預(yù)測(cè)方法,利用Map/Reduce編程進(jìn)行大數(shù)據(jù)的并行計(jì)算, 提高了算法效率,解決了交通管理部門(mén)監(jiān)測(cè)當(dāng)前時(shí)間車(chē)流量信 息的目的,為交通管理部門(mén)和相關(guān)車(chē)輛及時(shí)發(fā)布預(yù)警信息提供 了決策支持。
1 FP-Growth算法概述
J.W.Han等人克服了 Apriori算法產(chǎn)生基數(shù)龐大的候 選集和在計(jì)算支持度時(shí)多次掃描數(shù)據(jù)庫(kù)的弱點(diǎn),提出FP- Growth 算法。其思想是通過(guò)掃描2次數(shù)據(jù)庫(kù)構(gòu)造FP-Tree和 Header Table,從而得到用于頻繁項(xiàng)集挖掘的壓縮的數(shù)據(jù)庫(kù)映 射,然后對(duì)每個(gè)頻繁項(xiàng)構(gòu)造其條件FP-Tree進(jìn)行頻繁項(xiàng)集的 挖掘,最終得到頻繁項(xiàng)集。與Apriori算法比較FP-Growth算 法不產(chǎn)生候選集,采用FP-Tree壓縮所有能夠提供頻繁項(xiàng)信息 的項(xiàng)集,節(jié)省了時(shí)間和空間的消耗,相對(duì)Apriori算法的執(zhí)行 速度和內(nèi)存消耗已經(jīng)有了一個(gè)數(shù)量級(jí)的改善。
FP-Growth 改進(jìn)
由于FP-Growth是基于內(nèi)存駐留的算法,在頻繁項(xiàng)挖掘 時(shí)遞歸生成大量條件FP-Tree,當(dāng)數(shù)據(jù)庫(kù)達(dá)到一定規(guī)模時(shí),基于內(nèi)存的FP-Tree已經(jīng)無(wú)法有效應(yīng)對(duì),極容易造成內(nèi)存溢出, 這正是FP-Growth算法的瓶頸所在。因而,F(xiàn)P-Growth算法 在挖掘大數(shù)據(jù)問(wèn)題上有較大擴(kuò)展空間。
針對(duì)當(dāng)前交通的大數(shù)據(jù)背景,傳統(tǒng)FP-Growth算法和以 上改進(jìn)算法的優(yōu)勢(shì)不足以處理大規(guī)模交通數(shù)據(jù)問(wèn)題。因此, 本文就針對(duì)交通大數(shù)據(jù)給出FP-Growth算法改進(jìn)的解決方案:
建立支持度計(jì)數(shù)表。在第一次遍歷事務(wù)集合T的同 時(shí)創(chuàng)建二維向量,記錄每個(gè)事務(wù)中各個(gè)項(xiàng)兩兩組合出現(xiàn)的支 持度計(jì)數(shù);利用遞歸方式創(chuàng)建后綴模式S ( S夭{Null})條件 下的條件FP子樹(shù),此時(shí),第一次遍歷條件模式基得到支持度 計(jì)數(shù)列表,第二次遍歷條件模式基插入樹(shù)節(jié)點(diǎn)從而創(chuàng)建FP樹(shù); 遍歷條件模式基,創(chuàng)建FP子樹(shù)的同時(shí)創(chuàng)建新的支持度計(jì)數(shù)二 維向量表。
非頻繁項(xiàng)的剪枝策略。假設(shè)項(xiàng)集k在某一個(gè)路徑上 是非頻繁的;若項(xiàng)集k在FP-tree中存在前綴路徑集合A與集 合B,并且滿足集合B包含于集合A,那么集合A中的項(xiàng)集k 就可以被剪枝與短路徑集合B合并。
Map-Reduce 并行處理
Map-Reduce最初是由Google提出的,它是一種可以處 理海量數(shù)據(jù)的并行編程模型。該模型把所有的數(shù)據(jù)問(wèn)題抽象 成Map和Reduce兩個(gè)函數(shù)。以可靠的并行方式處理大規(guī)模 數(shù)據(jù)集,其中Map函數(shù)把問(wèn)題進(jìn)行分解,Reduce函數(shù)負(fù)責(zé)把 分解的任務(wù)進(jìn)行規(guī)約處理。
利用Map-Reduce編程模型,經(jīng)統(tǒng)計(jì)頻繁1-項(xiàng)和遞歸挖 掘頻繁項(xiàng)集的兩次并行處理,對(duì)改進(jìn)后的FR-Growth算法步 驟并行化。其描述為:首先,對(duì)頻繁1-項(xiàng)集的頻率統(tǒng)計(jì);再 利用頻繁1-項(xiàng)集的頻率統(tǒng)計(jì)結(jié)果建立一個(gè)哈希表,按照哈希表對(duì)數(shù)據(jù)進(jìn)行分組,把數(shù)據(jù)分成了若干個(gè)部分;然后對(duì)分解 后的數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘;最后,匯總最終的頻繁模式。
2基于模式匹配的軌跡預(yù)測(cè)
根據(jù)基于Map/Reduce的頻繁軌跡挖掘得到的序列模式 進(jìn)行軌跡預(yù)測(cè)。通過(guò)Map/Reduce并行計(jì)算獲得頻繁模式集 合后,就可以計(jì)算出與查詢軌跡最為相似的頻繁模式,用該 模式就可以預(yù)測(cè)軌跡的未來(lái)走向。
對(duì)于移動(dòng)對(duì)象數(shù)據(jù)庫(kù)D,存儲(chǔ)的是海量移動(dòng)對(duì)象在各 時(shí)間采樣點(diǎn)的位置信息。位置信息在時(shí)間上的有序集合為軌 跡,用D={Ti,T2,…,T.)表示,則|D|表示數(shù)據(jù)庫(kù)中包含的 軌跡數(shù)量。在三維XXYXT空間里,軌跡T是移動(dòng)對(duì)象在空 間內(nèi)位置信息的有序組合,可以表示為T(mén)= (ti,xi,yi),J X2, 乃),…,(tn,x?,yn)?其中t表示時(shí)間戳,(Xj,y)表示移動(dòng)對(duì) 象的空間位置坐標(biāo)。
軌跡匹配,是從頻繁模式中找出與查詢軌跡片段匹配權(quán) 重最高的模式。假設(shè)用戶的查詢軌跡片段為Q = <gq1,gq2,…, gq,>,軌跡頻繁模式為P = <gp1,gp2, -,gps>,則Q的預(yù)測(cè)由 Q和P' =<gp1,gp2,…,gp?>的匹配程度進(jìn)行反映。軌跡 片段在時(shí)間上最靠近當(dāng)前的元素是優(yōu)先考慮的,當(dāng)i<j時(shí),gqj 的權(quán)重要小于gq,這里將Wi+1=k*W, k>1, W1默認(rèn)為1,因此 軌跡Q、P的相似度計(jì)算公式為:
如查詢軌跡片段Q=<b, c,d>,頻繁模式為P<a, c, d, f>, Q和P的公共元素有<c, d>, c和d的權(quán)重分別 是100和10,假設(shè)k=10,因此Q和P似度為Sim (Q, P) =10+100/1+10+100,表明f極有可能為軌跡Q的未來(lái)軌跡。
3算法與實(shí)驗(yàn)
本文實(shí)驗(yàn)環(huán)境采用4臺(tái)PC機(jī)做分布式環(huán)境。操作系統(tǒng) 為 Ubuntu 14.04 -32bit, Hadoop 2.4.0, CPU 為 Inter Core i7 處理器,主頻2.1 GHz,單機(jī)內(nèi)存為512 MB。
3.1頻繁1-項(xiàng)統(tǒng)計(jì)
其Map-Reduce算法偽代碼如下:
map (key, value) { //value 為事務(wù) T
for each ki (E Ti do
output<ki, 1> ;
end
}
reduce( key, value) {//key 為一個(gè) 1-項(xiàng)集,value 為其支持?jǐn)?shù)列表[1,
1,…,1]
C=0 ;
for each v in value do
C+=1;
end
ifC/|D| minsup then
output<key, C> ; //輸出頻繁1-項(xiàng)集及其支持?jǐn)?shù)
end
}
FP-Growth 并行化
其Map-Reduce算法偽代碼如下:
map (key, value) { //value 為事務(wù) T}
insert_build_fptree (LFPTree, Ti) ; // 更新局部 FP 樹(shù) LFPTree
}
cleanup() {
LocalFPGrowth (LFPTree, LFPSet) ; // 將局部頻繁項(xiàng)目集及其 支持?jǐn)?shù)放入LFPSet中
for each lfp ( LFPSet do
output<lfp, sup (lfp) > ; //sup (lfp)為局部頻繁項(xiàng)目集 lfp 的支 持?jǐn)?shù)
end
}
reduce (key, value) {//key為項(xiàng)目集,value為其支持?jǐn)?shù)列表
C=0 ;
for each vi in value do
C+=vi ;
end
if C/|D| > minsup then
output<key, C> ; //輸出全局頻繁項(xiàng)目集及其支持?jǐn)?shù)
else if
write key into a distribute file ; //若暫不確定是否全局頻繁,則將 其寫(xiě)入分布式文件
end
}
4結(jié)語(yǔ)
本文結(jié)合歷史車(chē)輛軌跡數(shù)據(jù)利用改進(jìn)型的關(guān)聯(lián)規(guī)則算法 FP-Growth挖掘出軌跡模式索引,并提出基于Map/Reduce算 法的軌跡預(yù)測(cè)方案。在路網(wǎng)中利用索引樹(shù)對(duì)車(chē)輛未來(lái)軌跡進(jìn) 行預(yù)測(cè),預(yù)判出車(chē)流趨勢(shì),為交通管理部門(mén)及時(shí)做出交通疏 導(dǎo)方案的決策提供了支持。
20211223_61c363739aca5__基于MAPREDUCE并行處理的軌跡模式挖掘算法的研究