張奕 張永梅 郭莎 降愛蓮 鄔小燕
摘 要: 在隱藏于歷史軌跡數(shù)據(jù)集的眾多模式中,同現(xiàn)模式的挖掘尤其引人關(guān)注。文章將時空同現(xiàn)的數(shù)據(jù)挖掘算法與Hadoop平臺相結(jié)合,實現(xiàn)了并行處理,對軌跡數(shù)據(jù)進行預(yù)處理,并設(shè)計了時空同現(xiàn)模式挖掘算法。實驗結(jié)果表明,該算法能夠挖掘乘客集中地,為出租車司機提供合理有效的載客路徑。
關(guān)鍵詞: 時空同現(xiàn); 并行處理; 出租車軌跡數(shù)據(jù); 數(shù)據(jù)挖掘
中圖分類號:TP311 文獻標(biāo)志碼:A 文章編號:1006-8228(2016)11-05-02
Spatiotemporal co-occurrence mining algorithm and the application
Zhang Yi1, Zhang Yongmei2, Guo Sha2, Jiang Ailian3, Wu Xiaoyan2
(1. College of Software, Taiyuan University of Technology, Shanxi, Taiyuan 030600, China; 2. College of Computer, North China University of Technology; 3. College of Computer Science and Technology, Taiyuan University of Technology)
Abstract: Among the many modes hidden in the historical trajectory data set, mining the co-occurrence modes is particularly concerned. In this paper, combining the spatiotemporal co-occurrence data mining algorithm with Hadoop platform, the parallel processing is realized to pre-process the trajectory data, and the spatiotemporal co-occurrence mining algorithm is designed. The experiment results show that the algorithm can mining concentrated areas of passengers, and provide reasonable and effective paths for taxi drivers.
Key words: spatiotemporal co-occurrence; parallel processing; taxi trajectory data; data mining
0 引言
時空同現(xiàn)模式就是在時空維度下,不同對象類型子集的實例在一些時間段內(nèi),在空間上是相互鄰近的,或符合某種空間關(guān)系的對象集合。在許多應(yīng)用領(lǐng)域如:環(huán)境監(jiān)測、搶險救災(zāi)、基于位置的服務(wù)等,數(shù)據(jù)都隨著時間變化而變化。然而,大多數(shù)數(shù)據(jù)庫都不能有效地處理數(shù)據(jù)的時間維度。當(dāng)數(shù)據(jù)發(fā)生變化時,無法對數(shù)據(jù)變化的趨勢進行分析,更無法預(yù)測未來的趨勢。因此,從這些大量的數(shù)據(jù)中挖掘出有價值的信息變得更加重要,時空同現(xiàn)模式挖掘成為研究熱點。
隨著移動電話、GPS(Global Positioning System,全球定位系統(tǒng))等具備定位功能的設(shè)備普及,產(chǎn)生了大量基于時間和空間的移動對象歷史軌跡數(shù)據(jù)。在地理信息系統(tǒng)中,移動對象的歷史位置信息日益重要,在這一背景下,針對移動對象歷史軌跡的數(shù)據(jù)挖掘研究成為當(dāng)前研究熱點之一[1-2]。與傳統(tǒng)事務(wù)性數(shù)據(jù)集相比,從空間數(shù)據(jù)集中識別感興趣的模式更為困難和復(fù)雜,因為空間數(shù)據(jù)集具有復(fù)雜的數(shù)據(jù)類型和關(guān)系,而且數(shù)據(jù)總量龐大。在隱藏于歷史軌跡數(shù)據(jù)集的眾多模式中,同現(xiàn)模式的挖掘尤其引人關(guān)注??臻g數(shù)據(jù)集的同現(xiàn)模式直觀地反映了移動過程中移動對象之間相互接觸的情況,所以快速準(zhǔn)確地挖掘時空數(shù)據(jù)中的同現(xiàn)模式有利于推動眾多領(lǐng)域的研究,如生態(tài)、電力系統(tǒng)故障分析、軍事等。
雖然時空同現(xiàn)模式挖掘已經(jīng)取得了一些令人欣慰的研究成果,但總體來說還處于起步階段。隨著空間數(shù)據(jù)采集效率的提高,空間數(shù)據(jù)逐漸增大。在時空同現(xiàn)模式挖掘研究領(lǐng)域中,MeteCelik等人提出的混合驅(qū)動的時空同現(xiàn)模式挖掘最具有代表性。為了挖掘時空同現(xiàn)模式,他們提出了混合時空同現(xiàn)模式挖掘算法。該挖掘算法是基于連接操作的,會消耗大量時間生成候選模式集,隨著對象類型的增多,需要生成的候選模式集數(shù)量呈指數(shù)級增長,這意味著需要消耗的計算時間迅速增長,計算效率無法隨著對象類型的增加而迅速增長,不能處理龐大的時空數(shù)據(jù);同時該算法是基于內(nèi)存的,無法處理大量時空數(shù)據(jù)[3-5]。本文對出租車軌跡數(shù)據(jù)進行分析與挖掘,將時空同現(xiàn)的數(shù)據(jù)挖掘算法與Hadoop平臺相結(jié)合,可以有效解決數(shù)據(jù)存儲和運行慢的問題,同時又能高效獲取潛在信息。
1 時空同現(xiàn)挖掘算法的設(shè)計及實現(xiàn)
1.1 并行處理方法的實現(xiàn)
本文采用云計算理念,促進資源管理和高效利用,提升系統(tǒng)構(gòu)建的速度和靈活性。構(gòu)建基于云計算的數(shù)據(jù)環(huán)境,改善傳統(tǒng)的應(yīng)用與硬件綁定、不易維護、難以擴展等問題。大數(shù)據(jù)批處理需求主要針對復(fù)雜分布式編程,通過先存儲后計算的模式,允許對存儲單元的內(nèi)容進行多次操作,從而為復(fù)雜計算提供支撐。當(dāng)前,大數(shù)據(jù)批處理計算技術(shù)主要包括MapReduce、Dryad和spark等。
MapReduce是Google開發(fā)的一種簡潔抽象的分布式計算模型,在處理T級別以上巨量數(shù)據(jù)的業(yè)務(wù)上具有明顯優(yōu)勢。在MapReduce中,應(yīng)用的原始數(shù)據(jù)被劃分為多個用于并行計算的數(shù)據(jù)分片split,以顯式地挖掘應(yīng)用中的并行性。為了更好地描述問題的并行求解,split 被定義為數(shù)據(jù)域、屬性域和狀態(tài)描述域三部分。MapReduce 運行時系統(tǒng)是無狀態(tài)的,各個split保存自身狀態(tài)信息,便于將來checkpoint等功能的實現(xiàn)。MapReduce還提供了對數(shù)據(jù)分片的map和reduce計算。MapReduce已有多種實現(xiàn),最著名的是Hadoop,Hadoop靈活易用、可靠高效,已成為目前分布式海量數(shù)據(jù)處理的首選工具。
本文選擇Apache的Hadoop作為整個系統(tǒng)的底層計算平臺,主要使用Hadoop的分布式文件存儲系統(tǒng)HDFS和并行計算系統(tǒng)MapReduce。Hadoop環(huán)境搭建在vmware安裝好ubuntu的條件下。本文采用HDFS分布架構(gòu)系統(tǒng),把需處理的任務(wù)分布到多個計算機上,把一臺計算機作為NameNode結(jié)點,再選另外幾臺計算機作為DataNode,提高運算效率,同時也采用了MapReduce,利用它的并行處理功能,提高運算速度。
1.2 數(shù)據(jù)的預(yù)處理方法
本文采用的數(shù)據(jù)是網(wǎng)上下載的軌跡數(shù)據(jù),該數(shù)據(jù)是微軟亞洲研究院在Geolife 項目中收集的北京市出租車軌跡數(shù)據(jù),收集時間段:2008年2月2日-2月8日。數(shù)據(jù)平均采樣間隔約177秒,距離約623米。本文的數(shù)據(jù)預(yù)處理主要包括:計算速度、出租車??奎c的分析。計算速度是根據(jù)數(shù)據(jù)文件里所給的同一車輛在不同時間點上處于不同的經(jīng)緯度,經(jīng)過轉(zhuǎn)換和計算獲得兩點間的歐氏距離,利用距離除以相隔時間,得到在每個時間間隔內(nèi)的出租車速度。出租車??奎c的分析是結(jié)合出租車速度和時間空間,進行出租車??奎c的分析,即篩選出出租車載客的地點,過濾掉造成干擾的點。
1.3 時空同現(xiàn)模式挖掘算法具體步驟及實現(xiàn)
本文根據(jù)空間鄰近距離R計算出所有時間槽內(nèi)的空間鄰近模式,對于所有時間槽內(nèi)的空間鄰近模式計算各模式的實例支持度,與空間頻繁閾值進行比較,挖掘出滿足閾值的空間同位模式集,再縱向考慮所有時間槽,統(tǒng)計各個空間同位模式的時間頻繁度,找出滿足時間頻繁閾值的時空同現(xiàn)模式,進行時空同現(xiàn)模式的挖掘計算。時空同現(xiàn)模式挖掘算法具體步驟如下。
⑴ 初始化各個時間槽實例之間的空間關(guān)系,對時空數(shù)據(jù)集建立時空網(wǎng)絡(luò)模型STCOPG;
⑵ 設(shè)置k=1;
⑶ 根據(jù)STCOPG圖,生成k+1元候選時空同現(xiàn)模式;
⑷ 通過查詢STCOPG獲得候選時空同現(xiàn)模式的實例集,計算時空頻繁度,生成k+l元時空同現(xiàn)模式;
⑸ 重復(fù)生成候選同現(xiàn)模式操作,直到無新的候選同現(xiàn)模式或新的時空同現(xiàn)模式生成,算法結(jié)束;
⑹ 合并得到所有符合時空閾值的時空同現(xiàn)模式集。
根據(jù)大量實驗結(jié)果,本文的時空鄰近距離、空間頻繁閾值、時間頻繁閾值分別為4km、0.5和0.4。圖1給出了2008年2月4日下午2點出租車位于北京交通大學(xué),相對于出租車所處位置來說,在空間上鄰近的時空同現(xiàn)挖掘結(jié)果。
在圖1中,出租車位于北京交通大學(xué),也就是標(biāo)識為TAXI的位置,相對于出租車所處位置來說,在空間上鄰近的一些熱點的分布圖,也就是出租車司機在下午2點時,開車去如圖1所示的熱點分布的地方最容易載到乘客。
2 結(jié)束語
時空同現(xiàn)模式挖掘從其產(chǎn)生至今,就一直受到各界研究人員的關(guān)注。挖掘時空模式是非常有意義的,并且具有挑戰(zhàn)性,它可以應(yīng)用于軍事、道路的交通管制、災(zāi)情分析、案件偵破、國防、生態(tài)等領(lǐng)域。本文研究了時空同現(xiàn)挖掘算法及應(yīng)用,可以有效挖掘乘客集中地,為出租車司機提供合理有效的載客路徑。進一步需要研究時空鄰近距離、空間頻繁閾值、時間頻繁閾值的自適應(yīng)選取。
參考文獻(References):
[1] 齊林.基于GPS數(shù)據(jù)的出租車交通運行特性研究及應(yīng)用[D].
哈爾濱工業(yè)大學(xué)碩士學(xué)位論文,2013.
[2] 叢湘香.大數(shù)據(jù)下時空同現(xiàn)模式挖掘算法研究[D].華東理工
大學(xué)碩士學(xué)位論文,2012.
[3] 陳延平.基于局部時空共現(xiàn)特征的人體行為識別方法研究[D].
廈門大學(xué)碩士學(xué)位論文,2012.
[4] 黃照鶴,戴健.基于時空同現(xiàn)挖掘技術(shù)的FNRB-Tree[J].小型
微型計算機系統(tǒng),2012.33(12):2636-2641
[5] 許強,羅澤,魏穎,閻保平.一種檢測時空數(shù)據(jù)中重要同現(xiàn)模式的
快速算法[J].科研信息化技術(shù)與應(yīng)用,2013.4(3):23-31