當前位置:首頁 > 物聯(lián)網(wǎng) > 《物聯(lián)網(wǎng)技術》雜志
[導讀]摘 要:關聯(lián)規(guī)則算法中FP-Growth算法雖不產生候選集,但由于算法高度依賴于內存空間,阻礙了算法在大數(shù)據(jù)領域的 發(fā)揮,因此,改進了經(jīng)典的FP-Growth算法,首先創(chuàng)建支持度計數(shù)表,避免了算法對條件模式基的第一次遍歷,減少了對數(shù)據(jù) 庫的掃描次數(shù);其次利用剪枝策略刪去了大量沉余的非頻繁項集;最后將算法并行化,利用Hadoop平臺優(yōu)勢極大提高數(shù)據(jù) 處理的效率,同時解決了算法占用內存的瓶頸問題。實驗結果表明,改進型FP-Growth算法挖掘和預測軌跡的效率明顯高于 經(jīng)典算法。

引言

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

1 FP-Growth算法概述

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

FP-Growth 改進

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

針對當前交通的大數(shù)據(jù)背景,傳統(tǒng)FP-Growth算法和以 上改進算法的優(yōu)勢不足以處理大規(guī)模交通數(shù)據(jù)問題。因此, 本文就針對交通大數(shù)據(jù)給出FP-Growth算法改進的解決方案:

建立支持度計數(shù)表。在第一次遍歷事務集合T的同 時創(chuàng)建二維向量,記錄每個事務中各個項兩兩組合出現(xiàn)的支 持度計數(shù);利用遞歸方式創(chuàng)建后綴模式S ( S夭{Null})條件 下的條件FP子樹,此時,第一次遍歷條件模式基得到支持度 計數(shù)列表,第二次遍歷條件模式基插入樹節(jié)點從而創(chuàng)建FP樹; 遍歷條件模式基,創(chuàng)建FP子樹的同時創(chuàng)建新的支持度計數(shù)二 維向量表。

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

Map-Reduce 并行處理

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

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

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

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

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

對于移動對象數(shù)據(jù)庫D,存儲的是海量移動對象在各 時間采樣點的位置信息。位置信息在時間上的有序集合為軌 跡,用D={Ti,T2,…,T.)表示,則|D|表示數(shù)據(jù)庫中包含的 軌跡數(shù)量。在三維XXYXT空間里,軌跡T是移動對象在空 間內位置信息的有序組合,可以表示為T= (ti,xi,yi),J X2, 乃),…,(tn,x?,yn)?其中t表示時間戳,(Xj,y)表示移動對 象的空間位置坐標。

軌跡匹配,是從頻繁模式中找出與查詢軌跡片段匹配權 重最高的模式。假設用戶的查詢軌跡片段為Q = <gq1,gq2,…, gq,>,軌跡頻繁模式為P = <gp1,gp2, -,gps>,則Q的預測由 Q和P' =<gp1,gp2,…,gp?>的匹配程度進行反映。軌跡 片段在時間上最靠近當前的元素是優(yōu)先考慮的,當i<j時,gqj 的權重要小于gq,這里將Wi+1=k*W, k>1, W1默認為1,因此 軌跡Q、P的相似度計算公式為:

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

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

3算法與實驗

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

3.1頻繁1-項統(tǒng)計

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

map (key, value) { //value 為事務 T

for each ki (E Ti do

output<ki, 1> ;

end

}

reduce( key, value) {//key 為一個 1-項集,value 為其支持數(shù)列表[1,

1,…,1]

C=0 ;

for each v in value do

C+=1;

end

ifC/|D| minsup then

output<key, C> ; //輸出頻繁1-項集及其支持數(shù)

end

}

FP-Growth 并行化

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

map (key, value) { //value 為事務 T}

insert_build_fptree (LFPTree, Ti) ; // 更新局部 FP 樹 LFPTree

}

cleanup() {

LocalFPGrowth (LFPTree, LFPSet) ; // 將局部頻繁項目集及其 支持數(shù)放入LFPSet中

for each lfp ( LFPSet do

output<lfp, sup (lfp) > ; //sup (lfp)為局部頻繁項目集 lfp 的支 持數(shù)

end

}

reduce (key, value) {//key為項目集,value為其支持數(shù)列表

C=0 ;

for each vi in value do

C+=vi ;

end

if C/|D| > minsup then

output<key, C> ; //輸出全局頻繁項目集及其支持數(shù)

else if

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

end

}

4結語

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

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

本站聲明: 本文章由作者或相關機構授權發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點,本站亦不保證或承諾內容真實性等。需要轉載請聯(lián)系該專欄作者,如若文章內容侵犯您的權益,請及時聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或將催生出更大的獨角獸公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關鍵字: 阿維塔 塞力斯 華為

加利福尼亞州圣克拉拉縣2024年8月30日 /美通社/ -- 數(shù)字化轉型技術解決方案公司Trianz今天宣布,該公司與Amazon Web Services (AWS)簽訂了...

關鍵字: AWS AN BSP 數(shù)字化

倫敦2024年8月29日 /美通社/ -- 英國汽車技術公司SODA.Auto推出其旗艦產品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時1.5...

關鍵字: 汽車 人工智能 智能驅動 BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務能7×24不間斷運行,同時企業(yè)卻面臨越來越多業(yè)務中斷的風險,如企業(yè)系統(tǒng)復雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務連續(xù)性,提升韌性,成...

關鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報道,騰訊和網(wǎng)易近期正在縮減他們對日本游戲市場的投資。

關鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產業(yè)博覽會開幕式在貴陽舉行,華為董事、質量流程IT總裁陶景文發(fā)表了演講。

關鍵字: 華為 12nm EDA 半導體

8月28日消息,在2024中國國際大數(shù)據(jù)產業(yè)博覽會上,華為常務董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權最終是由生態(tài)的繁榮決定的。

關鍵字: 華為 12nm 手機 衛(wèi)星通信

要點: 有效應對環(huán)境變化,經(jīng)營業(yè)績穩(wěn)中有升 落實提質增效舉措,毛利潤率延續(xù)升勢 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務引領增長 以科技創(chuàng)新為引領,提升企業(yè)核心競爭力 堅持高質量發(fā)展策略,塑強核心競爭優(yōu)勢...

關鍵字: 通信 BSP 電信運營商 數(shù)字經(jīng)濟

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺與中國電影電視技術學會聯(lián)合牽頭組建的NVI技術創(chuàng)新聯(lián)盟在BIRTV2024超高清全產業(yè)鏈發(fā)展研討會上宣布正式成立。 活動現(xiàn)場 NVI技術創(chuàng)新聯(lián)...

關鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會上,軟通動力信息技術(集團)股份有限公司(以下簡稱"軟通動力")與長三角投資(上海)有限...

關鍵字: BSP 信息技術
關閉