時空同現(xiàn)挖掘算法及應(yīng)用研究

張奕　張永梅　郭莎　降愛蓮　鄔小燕

摘 要： 在隱藏于歷史軌跡數(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