時空同現挖掘算法及應用研究

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

摘 要： 在隱藏于歷史軌跡數據集的眾多模式中，同現模式的挖掘尤其引人關注。文章將時空同現的數據挖掘算法與Hadoop平臺相結合，實現了并行處理，對軌跡數據進行預處理，并設計了時空同現模式挖掘算法。實驗結果表明，該算法能夠挖掘乘客集中地，為出租車司機提供合理有效的載客路徑。

關鍵詞： 時空同現； 并行處理； 出租車軌跡數據； 數據挖掘

中圖分類號：TP311 文獻標志碼：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 引言

時空同現模式就是在時空維度下，不同對象類型子集的實例在一些時間段內，在空間上是相互鄰近的，或符合某種空間關系的對象集合。在許多應用領域如：環境監測、搶險救災、基于位置的服務等，數據都隨著時間變化而變化。然而，大多數數據庫都不能有效地處理數據的時間維度。當數據發生變化時，無法對數據變化的趨勢進行分析，更無法預測未來的趨勢。因此，從這些大量的數據中挖掘出有價值的信息變得更加重要，時空同現模式挖掘成為研究熱點。

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

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

1 時空同現挖掘算法的設計及實現

1.1 并行處理方法的實現

本文采用云計算理念，促進資源管理和高效利用，提升系統構建的速度和靈活性。構建基于云計算的數據環境，改善傳統的應用與硬件綁定、不易維護、難以擴展等問題。大數據批處理需求主要針對復雜分布式編程，通過先存儲后計算的模式，允許對存儲單元的內容進行多次操作，從而為復雜計算提供支撐。當前，大數據批處理計算技術主要包括MapReduce、Dryad和spark等。

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

本文選擇Apache的Hadoop作為整個系統的底層計算平臺，主要使用Hadoop的分布式文件存儲系統HDFS和并行計算系統MapReduce。Hadoop環境搭建在vmware安裝好ubuntu的條件下。本文采用HDFS分布架構系統，把需處理的任務分布到多個計算機上，把一臺計算機作為NameNode結點，再選另外幾臺計算機作為DataNode，提高運算效率，同時也采用了MapReduce，利用它的并行處理功能，提高運算速度。

1.2 數據的預處理方法

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

1.3 時空同現模式挖掘算法具體步驟及實現

本文根據空間鄰近距離R計算出所有時間槽內的空間鄰近模式，對于所有時間槽內的空間鄰近模式計算各模式的實例支持度，與空間頻繁閾值進行比較，挖掘出滿足閾值的空間同位模式集，再縱向考慮所有時間槽，統計各個空間同位模式的時間頻繁度，找出滿足時間頻繁閾值的時空同現模式，進行時空同現模式的挖掘計算。時空同現模式挖掘算法具體步驟如下。

⑴ 初始化各個時間槽實例之間的空間關系，對時空數據集建立時空網絡模型STCOPG；

⑵ 設置k=1；

⑶ 根據STCOPG圖，生成k+1元候選時空同現模式；

⑷ 通過查詢STCOPG獲得候選時空同現模式的實例集，計算時空頻繁度，生成k+l元時空同現模式；

⑸ 重復生成候選同現模式操作，直到無新的候選同現模式或新的時空同現模式生成，算法結束；

⑹ 合并得到所有符合時空閾值的時空同現模式集。

根據大量實驗結果，本文的時空鄰近距離、空間頻繁閾值、時間頻繁閾值分別為4km、0.5和0.4。圖1給出了2008年2月4日下午2點出租車位于北京交通大學，相對于出租車所處位置來說，在空間上鄰近的時空同現挖掘結果。

在圖1中，出租車位于北京交通大學，也就是標識為TAXI的位置，相對于出租車所處位置來說，在空間上鄰近的一些熱點的分布圖，也就是出租車司機在下午2點時，開車去如圖1所示的熱點分布的地方最容易載到乘客。

2 結束語

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

參考文獻（References）：

[1] 齊林.基于GPS數據的出租車交通運行特性研究及應用[D].

哈爾濱工業大學碩士學位論文，2013.

[2] 叢湘香.大數據下時空同現模式挖掘算法研究[D].華東理工

大學碩士學位論文，2012.

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

廈門大學碩士學位論文，2012.

[4] 黃照鶴，戴健.基于時空同現挖掘技術的FNRB-Tree[J].小型

微型計算機系統，2012.33（12）：2636-2641

[5] 許強，羅澤，魏穎，閻保平.一種檢測時空數據中重要同現模式的

快速算法[J].科研信息化技術與應用，2013.4（3）：23-31