張奕　張永梅　郭莎　降愛(ài)蓮　鄔小燕

摘 要： 在隱藏于歷史軌跡數(shù)據(jù)集的眾多模式中，同現(xiàn)模式的挖掘尤其引人關(guān)注。文章將時(shí)空同現(xiàn)的數(shù)據(jù)挖掘算法與Hadoop平臺(tái)相結(jié)合，實(shí)現(xiàn)了并行處理，對(duì)軌跡數(shù)據(jù)進(jìn)行預(yù)處理，并設(shè)計(jì)了時(shí)空同現(xiàn)模式挖掘算法。實(shí)驗(yàn)結(jié)果表明，該算法能夠挖掘乘客集中地，為出租車司機(jī)提供合理有效的載客路徑。

關(guān)鍵詞： 時(shí)空同現(xiàn)； 并行處理； 出租車軌跡數(shù)據(jù)； 數(shù)據(jù)挖掘

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

時(shí)空同現(xiàn)模式就是在時(shí)空維度下，不同對(duì)象類型子集的實(shí)例在一些時(shí)間段內(nèi)，在空間上是相互鄰近的，或符合某種空間關(guān)系的對(duì)象集合。在許多應(yīng)用領(lǐng)域如：環(huán)境監(jiān)測(cè)、搶險(xiǎn)救災(zāi)、基于位置的服務(wù)等，數(shù)據(jù)都隨著時(shí)間變化而變化。然而，大多數(shù)數(shù)據(jù)庫(kù)都不能有效地處理數(shù)據(jù)的時(shí)間維度。當(dāng)數(shù)據(jù)發(fā)生變化時(shí)，無(wú)法對(duì)數(shù)據(jù)變化的趨勢(shì)進(jìn)行分析，更無(wú)法預(yù)測(cè)未來(lái)的趨勢(shì)。因此，從這些大量的數(shù)據(jù)中挖掘出有價(jià)值的信息變得更加重要，時(shí)空同現(xiàn)模式挖掘成為研究熱點(diǎn)。

隨著移動(dòng)電話、GPS（Global Positioning System，全球定位系統(tǒng)）等具備定位功能的設(shè)備普及，產(chǎn)生了大量基于時(shí)間和空間的移動(dòng)對(duì)象歷史軌跡數(shù)據(jù)。在地理信息系統(tǒng)中，移動(dòng)對(duì)象的歷史位置信息日益重要，在這一背景下，針對(duì)移動(dòng)對(duì)象歷史軌跡的數(shù)據(jù)挖掘研究成為當(dāng)前研究熱點(diǎn)之一[1-2]。與傳統(tǒng)事務(wù)性數(shù)據(jù)集相比，從空間數(shù)據(jù)集中識(shí)別感興趣的模式更為困難和復(fù)雜，因?yàn)榭臻g數(shù)據(jù)集具有復(fù)雜的數(shù)據(jù)類型和關(guān)系，而且數(shù)據(jù)總量龐大。在隱藏于歷史軌跡數(shù)據(jù)集的眾多模式中，同現(xiàn)模式的挖掘尤其引人關(guān)注。空間數(shù)據(jù)集的同現(xiàn)模式直觀地反映了移動(dòng)過(guò)程中移動(dòng)對(duì)象之間相互接觸的情況，所以快速準(zhǔn)確地挖掘時(shí)空數(shù)據(jù)中的同現(xiàn)模式有利于推動(dòng)眾多領(lǐng)域的研究，如生態(tài)、電力系統(tǒng)故障分析、軍事等。

雖然時(shí)空同現(xiàn)模式挖掘已經(jīng)取得了一些令人欣慰的研究成果，但總體來(lái)說(shuō)還處于起步階段。隨著空間數(shù)據(jù)采集效率的提高，空間數(shù)據(jù)逐漸增大。在時(shí)空同現(xiàn)模式挖掘研究領(lǐng)域中，MeteCelik等人提出的混合驅(qū)動(dòng)的時(shí)空同現(xiàn)模式挖掘最具有代表性。為了挖掘時(shí)空同現(xiàn)模式，他們提出了混合時(shí)空同現(xiàn)模式挖掘算法。該挖掘算法是基于連接操作的，會(huì)消耗大量時(shí)間生成候選模式集，隨著對(duì)象類型的增多，需要生成的候選模式集數(shù)量呈指數(shù)級(jí)增長(zhǎng)，這意味著需要消耗的計(jì)算時(shí)間迅速增長(zhǎng)，計(jì)算效率無(wú)法隨著對(duì)象類型的增加而迅速增長(zhǎng)，不能處理龐大的時(shí)空數(shù)據(jù)；同時(shí)該算法是基于內(nèi)存的，無(wú)法處理大量時(shí)空數(shù)據(jù)[3-5]。本文對(duì)出租車軌跡數(shù)據(jù)進(jìn)行分析與挖掘，將時(shí)空同現(xiàn)的數(shù)據(jù)挖掘算法與Hadoop平臺(tái)相結(jié)合，可以有效解決數(shù)據(jù)存儲(chǔ)和運(yùn)行慢的問(wèn)題，同時(shí)又能高效獲取潛在信息。

1 時(shí)空同現(xiàn)挖掘算法的設(shè)計(jì)及實(shí)現(xiàn)

1.1 并行處理方法的實(shí)現(xiàn)

本文采用云計(jì)算理念，促進(jìn)資源管理和高效利用，提升系統(tǒng)構(gòu)建的速度和靈活性。構(gòu)建基于云計(jì)算的數(shù)據(jù)環(huán)境，改善傳統(tǒng)的應(yīng)用與硬件綁定、不易維護(hù)、難以擴(kuò)展等問(wèn)題。大數(shù)據(jù)批處理需求主要針對(duì)復(fù)雜分布式編程，通過(guò)先存儲(chǔ)后計(jì)算的模式，允許對(duì)存儲(chǔ)單元的內(nèi)容進(jìn)行多次操作，從而為復(fù)雜計(jì)算提供支撐。當(dāng)前，大數(shù)據(jù)批處理計(jì)算技術(shù)主要包括MapReduce、Dryad和spark等。

MapReduce是Google開(kāi)發(fā)的一種簡(jiǎn)潔抽象的分布式計(jì)算模型，在處理T級(jí)別以上巨量數(shù)據(jù)的業(yè)務(wù)上具有明顯優(yōu)勢(shì)。在MapReduce中，應(yīng)用的原始數(shù)據(jù)被劃分為多個(gè)用于并行計(jì)算的數(shù)據(jù)分片split，以顯式地挖掘應(yīng)用中的并行性。為了更好地描述問(wèn)題的并行求解，split 被定義為數(shù)據(jù)域、屬性域和狀態(tài)描述域三部分。MapReduce 運(yùn)行時(shí)系統(tǒng)是無(wú)狀態(tài)的，各個(gè)split保存自身狀態(tài)信息，便于將來(lái)checkpoint等功能的實(shí)現(xiàn)。MapReduce還提供了對(duì)數(shù)據(jù)分片的map和reduce計(jì)算。MapReduce已有多種實(shí)現(xiàn)，最著名的是Hadoop，Hadoop靈活易用、可靠高效，已成為目前分布式海量數(shù)據(jù)處理的首選工具。

本文選擇Apache的Hadoop作為整個(gè)系統(tǒng)的底層計(jì)算平臺(tái)，主要使用Hadoop的分布式文件存儲(chǔ)系統(tǒng)HDFS和并行計(jì)算系統(tǒng)MapReduce。Hadoop環(huán)境搭建在vmware安裝好ubuntu的條件下。本文采用HDFS分布架構(gòu)系統(tǒng)，把需處理的任務(wù)分布到多個(gè)計(jì)算機(jī)上，把一臺(tái)計(jì)算機(jī)作為NameNode結(jié)點(diǎn)，再選另外幾臺(tái)計(jì)算機(jī)作為DataNode，提高運(yùn)算效率，同時(shí)也采用了MapReduce，利用它的并行處理功能，提高運(yùn)算速度。

1.2 數(shù)據(jù)的預(yù)處理方法

本文采用的數(shù)據(jù)是網(wǎng)上下載的軌跡數(shù)據(jù)，該數(shù)據(jù)是微軟亞洲研究院在Geolife 項(xiàng)目中收集的北京市出租車軌跡數(shù)據(jù)，收集時(shí)間段：2008年2月2日-2月8日。數(shù)據(jù)平均采樣間隔約177秒，距離約623米。本文的數(shù)據(jù)預(yù)處理主要包括：計(jì)算速度、出租車停靠點(diǎn)的分析。計(jì)算速度是根據(jù)數(shù)據(jù)文件里所給的同一車輛在不同時(shí)間點(diǎn)上處于不同的經(jīng)緯度，經(jīng)過(guò)轉(zhuǎn)換和計(jì)算獲得兩點(diǎn)間的歐氏距離，利用距離除以相隔時(shí)間，得到在每個(gè)時(shí)間間隔內(nèi)的出租車速度。出租車停靠點(diǎn)的分析是結(jié)合出租車速度和時(shí)間空間，進(jìn)行出租車?？奎c(diǎn)的分析，即篩選出出租車載客的地點(diǎn)，過(guò)濾掉造成干擾的點(diǎn)。

1.3 時(shí)空同現(xiàn)模式挖掘算法具體步驟及實(shí)現(xiàn)

本文根據(jù)空間鄰近距離R計(jì)算出所有時(shí)間槽內(nèi)的空間鄰近模式，對(duì)于所有時(shí)間槽內(nèi)的空間鄰近模式計(jì)算各模式的實(shí)例支持度，與空間頻繁閾值進(jìn)行比較，挖掘出滿足閾值的空間同位模式集，再縱向考慮所有時(shí)間槽，統(tǒng)計(jì)各個(gè)空間同位模式的時(shí)間頻繁度，找出滿足時(shí)間頻繁閾值的時(shí)空同現(xiàn)模式，進(jìn)行時(shí)空同現(xiàn)模式的挖掘計(jì)算。時(shí)空同現(xiàn)模式挖掘算法具體步驟如下。

⑴ 初始化各個(gè)時(shí)間槽實(shí)例之間的空間關(guān)系，對(duì)時(shí)空數(shù)據(jù)集建立時(shí)空網(wǎng)絡(luò)模型STCOPG；

⑵ 設(shè)置k=1；

⑶ 根據(jù)STCOPG圖，生成k+1元候選時(shí)空同現(xiàn)模式；

⑷ 通過(guò)查詢STCOPG獲得候選時(shí)空同現(xiàn)模式的實(shí)例集，計(jì)算時(shí)空頻繁度，生成k+l元時(shí)空同現(xiàn)模式；

⑸ 重復(fù)生成候選同現(xiàn)模式操作，直到無(wú)新的候選同現(xiàn)模式或新的時(shí)空同現(xiàn)模式生成，算法結(jié)束；

⑹ 合并得到所有符合時(shí)空閾值的時(shí)空同現(xiàn)模式集。

根據(jù)大量實(shí)驗(yàn)結(jié)果，本文的時(shí)空鄰近距離、空間頻繁閾值、時(shí)間頻繁閾值分別為4km、0.5和0.4。圖1給出了2008年2月4日下午2點(diǎn)出租車位于北京交通大學(xué)，相對(duì)于出租車所處位置來(lái)說(shuō)，在空間上鄰近的時(shí)空同現(xiàn)挖掘結(jié)果。

在圖1中，出租車位于北京交通大學(xué)，也就是標(biāo)識(shí)為TAXI的位置，相對(duì)于出租車所處位置來(lái)說(shuō)，在空間上鄰近的一些熱點(diǎn)的分布圖，也就是出租車司機(jī)在下午2點(diǎn)時(shí)，開(kāi)車去如圖1所示的熱點(diǎn)分布的地方最容易載到乘客。

2 結(jié)束語(yǔ)

時(shí)空同現(xiàn)模式挖掘從其產(chǎn)生至今，就一直受到各界研究人員的關(guān)注。挖掘時(shí)空模式是非常有意義的，并且具有挑戰(zhàn)性，它可以應(yīng)用于軍事、道路的交通管制、災(zāi)情分析、案件偵破、國(guó)防、生態(tài)等領(lǐng)域。本文研究了時(shí)空同現(xiàn)挖掘算法及應(yīng)用，可以有效挖掘乘客集中地，為出租車司機(jī)提供合理有效的載客路徑。進(jìn)一步需要研究時(shí)空鄰近距離、空間頻繁閾值、時(shí)間頻繁閾值的自適應(yīng)選取。

參考文獻(xiàn)（References）：

[1] 齊林.基于GPS數(shù)據(jù)的出租車交通運(yùn)行特性研究及應(yīng)用[D].

哈爾濱工業(yè)大學(xué)碩士學(xué)位論文，2013.

[2] 叢湘香.大數(shù)據(jù)下時(shí)空同現(xiàn)模式挖掘算法研究[D].華東理工

大學(xué)碩士學(xué)位論文，2012.

[3] 陳延平.基于局部時(shí)空共現(xiàn)特征的人體行為識(shí)別方法研究[D].

廈門大學(xué)碩士學(xué)位論文，2012.

[4] 黃照鶴，戴健.基于時(shí)空同現(xiàn)挖掘技術(shù)的FNRB-Tree[J].小型

微型計(jì)算機(jī)系統(tǒng)，2012.33（12）：2636-2641

[5] 許強(qiáng)，羅澤，魏穎，閻保平.一種檢測(cè)時(shí)空數(shù)據(jù)中重要同現(xiàn)模式的

快速算法[J].科研信息化技術(shù)與應(yīng)用，2013.4（3）：23-31