分布式增量機制下的交通流大數據聚類分析

李 欣

(1. 河南財經政法大學中原經濟區“三化”協調發展河南省協同創新中心，河南 鄭州 450046; 2. 河南財經政法大學資源與環境學院，河南 鄭州 450046)

?

分布式增量機制下的交通流大數據聚類分析

李 欣1,2

(1. 河南財經政法大學中原經濟區“三化”協調發展河南省協同創新中心，河南 鄭州 450046; 2. 河南財經政法大學資源與環境學院，河南 鄭州 450046)

時空聚類分析是對時空大數據進行利用的一種有效手段。本文提出了一種分布式增量大數據聚類分析方法，利用分布增量機制不但可以減少重復計算和遷移拷貝次數，而且可以持續對聚類結果進行修正，能夠在保持聚類準確性的條件下提升整體運算效率。而聚類算法本身通過數據聚集趨勢預分析、聚類算法和結果評價3個步驟，構建了一體化時空鄰域，在時間和空間維度保證了聚類結果的準確性。經過試驗證明該方法可以實現時空大數據的快速高效信息挖掘。

時空數據；大數據；聚類分析；增量聚類；時空鄰域

當今城市中越來越多的傳感器正在產生各種與人類活動相關的時空位置數據，可以稱之為時空大數據[1]。作為分析和利用時空大數據的重要手段，數據聚類分析是地理信息相關學科的重要研究課題[2]。目前在大數據環境下的聚類分析方法雖然已經產生不少研究成果，但要么聚類效率無法適應海量時空數據，要么沒有解決時空數據的耦合性、關聯性、異質性問題。因此，本文擬研究一種適應大數據環境的交通流大數據聚類分析方法，為數據挖掘研究及相關實際應用提供參考依據。

1 國內外聚類分析研究現狀

目前國內外的時空聚類方法主要包括：①基于劃分的方法：Bagirov[3]提出的全局K-Means算法，雷小鋒[4]提出的K-MeanSCAN算法。②基于模型的方法：Gaffney[5]的回歸混合軌跡聚類模型，Chudova[6]的地理實體時空軌跡漂移聚類方法，Alon[7]的地理實體簇臨位轉換馬爾科夫模型。③基于密度的方法：Li[8]的交通熱點路線的聚類算法，Birant[9]的ST-DBSCAN時空聚類算法。④基于大數據的方法：Bose[11]提出的增量并行數據挖掘方法，Laptev[13]的樣本抽樣放回方法，Zhao[12]提出的基于邊結構相似度的聚類方法等。以上研究成果，或是未適應大數據的廣域多源特點，或是使用抽樣降維方法減少數據量，降低復雜度[14]，仍然無法滿足大數據環境下聚類分析的需求。

本文的研究策略是在顧及大數據處理效率的條件下，研究一種分布式增量交通流大數據聚類分析流程(distributed incremental clustering process，DICP)，該流程在聚類過程中引入分布和增量機制，在分布節點完成大量聚類運算，最終在中心節點完成聚類結果合并，能在較大程度上提高聚類分析的運算效率。對于交通流聚類算法本身，本文研究了一種改進的時空數據聚類算法(the improved method of spatio-temporal data cluster analysis，IMSTDCA)，通過時空數據聚集趨勢預分析、聚類算法和聚類結果評價3個步驟，完成時空自回歸移動平均模型[15](space-time autoregressive integrated moving average，STARIMA)中一體化時空鄰域的構建，實現聚類信息的高效挖掘。

2 聚類分析關鍵技術研究

2.1 分布式增量交通流大數據聚類分析流程

本文研究的DICP聚類分析流程，按照多個連續的時間周期，對網絡中分布節點和中心節點中的數據進行增量聚類，經過首次歷史全集數據聚類和后期多個周期增量數據聚類階段，可以在滿足運算效率的前提下完成較為準確的聚類分析。

2.1.1 歷史全集數據聚類階段

首次聚類是針對所有節點歷史數據全集進行聚類分析的階段。首先對分布節點中的數據進行分塊，基于MapReduce中的Map運算完成數據塊的中間聚類，再使用Combine運算完成分布節點中間聚類結果合并，傳輸到中心節點后由Reduce運算完成分布節點聚類結果的合并，實現首次聚類分析。其基本思路是：

(1) 對N個分布節點的數據全集進行切塊，分為M個數據塊。

(2) 對于每個數據塊構建一個Map運算，并利用IMSTDCA聚類算法完成中間聚類運算，生成M個中間聚類結果。

(3) 由Combine運算完成M個中間聚類結果的合并，并傳輸到中心節點。

(4) 在由中心節點使用Reduce運算完成所有聚類結果的二次合并，計算歷史全集數據聚類中心。

(5) 若達到最大迭代次數或聚類結果收斂，則完成聚類；否則，計算下一次迭代的比較參數，從步驟(2)開始進行下一次迭代。

2.1.2 周期增量數據聚類階段

周期增量階段是在首次聚類基礎上，比較增量數據與已有聚類中心的時空距離，利用分布式的優勢完成增量數據的快速并行聚類運算。其基本思想是：

(1) 對N個分布節點周期增量數據集合進行切塊，分為ΔM個增量數據塊。

(2) 對每個增量數據塊構建Map運算，并利用IMSTDCA時空距離度量聚類中心與增量數據的時空距離，將增量數據記錄合并到小于規定閾值的時空距離最小的類中。

(3) 在分布節點Combine運算中參照聚類中間結果進行偏離誤差計算，得到聚類中心在某個分布節點的局部偏離誤差，并傳輸到中心節點。

(4) 由中心節點的Reduce運算進行結果合并，并計算每個類的全局偏離誤差。

(5) 若所有全局偏離誤差小于閾值，則完成本次周期聚類；若某個全局偏離誤差大于閾值，則解體該類，按照歷史全集階段方法重新對未分類數據和解體數據記錄進行聚類運算。

2.2 時空數據聚類算法

時空數據聚類分析算法是影響整個聚類分析準確性和高效性的關鍵因素。本文研究IMSTDCA時空數據聚類分析方法，包括數據聚集趨勢預分析、聚類算法和結果評價3個步驟。IMSTDCA聚類分析方法流程如圖1所示。

2.2.1 時空數據聚集趨勢預分析

時空數據聚集趨勢預分析是對數據相關性和異質性進行分析判斷，計算地理實體之間是否存在相關性和聚集現象，從而判斷進行聚類的可行性，避免大量無謂的聚類分析運算。實際計算中可以利用文獻[16]中的Geary’C指數、Moran’I指數、變差函數等方法[16]進行計算，若地理實體空間不相關，則認為其不包含聚集趨勢，聚類分析運算沒有實際意義。

2.2.2 時空數據聚類算法

通過時空數據聚集趨勢預分析可以獲得時空平穩的數據集合，可以利用經過改進的STARIMA時間延遲算子對數據集的時空鄰域進行判斷。時空自回歸移動平均模型STARIMA公式如下

(1)

式中，k為時間延遲；h為空間間隔；p為時間自回歸延遲；mk為第k個時間自回歸項的空間間隔；?kh為時間延遲為k并且空間間隔為h的自回歸參數；q為移動時間平均延遲；nl為第l個時間移動平均項的空間間隔；θlh為時間延遲為l并且空間間隔為h的移動平均參數；ε(t)為隨機誤差。式(1)中的時間延遲k可以代表實體在時間維度的距離，可以通過時空偏相關函數[17]和時空自相關函數[18]計算獲得。

在聚類分析過程中，從時間維度分析，前一時間段內的時空實體會對當前時刻的某個時空實體產生影響，而當前時刻的時空實體也會對后一時間段內的時空實體產生影響。因此應該以某一時刻為中心的時間半徑作為聚類分析的時間窗口，即將STARIMA模型中的時間延遲k擴展為時間半徑。

從空間維度分析，要實現實體之間的空間距離定量化計算才能確定聚類分析中的鄰近關系。使用Delaunay三角網是判斷鄰近關系的經典方法，但若三角網未經任何處理，則在邊緣部分會產生一定誤差，如圖2(a)所示。

本文使用了整體和局部距離約束對空間實體原始Delaunay三角網構建的鄰近關系進行修正。針對三角網中頂點Pi的整體距離約束條件公式如下

Entirety_Constraint(Pi)=Entirety_Mean+

(2)

式中，Entirety_Mean為所有邊長的均值；Mean(Pi)為頂點Pi的所有鄰接邊的邊長均值；Entirety_Variance為所有邊長的方差。

針對三角網中頂點Pi的局部距離約束條件公式如下

Locality_Constraint(Pi)=Locality_Mean(Pi)+2×

(3)

式中，Locality_Mean(Pi)為Pi點的鄰近邊長均值；Locality_Variance(Pi)表為頂點Pi的鄰近邊長方差；N為三角網所有頂點總數。

圖2 基于距離約束Delaunay三角網的空間鄰近關系

利用式(2)和式(3)的約束條件邊長判斷閾值，刪除長度大于整體和局部距離約束條件的邊，即可得到圖2(b)和(c)中的結果，此時的Delaunay三角網可作為判斷空間鄰近關系的依據。

通過時間維度和空間維度的鄰域分析，即可確定某個地理實體的時空鄰域，基于此鄰域時空聚類流程如下：

(1) 選取某個實體作為時空中心，判斷其時間和空間鄰域內的其他實體是否與其滿足鄰接條件，若滿足則標記其為初始時空中心。

(2) 以該初始時空中心為核心，計算鄰域內所有實體與中心的時空距離，將距離最近的實體加入聚類簇，第一個聚類集合開始生成。

(3) 重復利用步驟(2)對聚類集合進行擴展，將每個已加入聚類簇的實體作為擴展中心，在時空鄰域中判斷實體的時空距離，滿足鄰接條件即可加入聚類簇，所有滿足條件的實體都加入后，即完成了一個聚類集合的生成。

(4) 繼續對剩余時空實體重復步驟(1)至步驟(3)進行判斷，即可生成多個時空實體聚類結合，若某個實體不滿足任何鄰接條件，則將其標記為孤立點，聚類運算完成。

2.2.3 時空數據聚類結果評價

本文中有兩個影響時空數據聚類算法復雜度的因素：一是構建時空鄰域并在其中檢索鄰接目標；二是聚類簇的生成。設數據集全中包含n個時空實體，則本文構建時空鄰域方法的復雜度約為O(nlog2n)，低于ST-DBSCAN[8]方法的復雜度O(n2)，而聚類簇簇生成時的復雜度與ST-DBSCAN方法相當。因此本文時空數據聚類算法的復雜度約為O(nlog2n)。

3 試驗結果分析

試驗數據基于智能交通綜合管理平臺獲取，該平臺是一套提供了采集評估、交通指揮、智能誘導和聯網監控等功能的綜合管理平臺，目前已經在河南多個地市實現了部分應用。試驗提取了系統采集的交通流大數據作為數據源，驗證本文設計的分布式增量IMSTDCA時空數據聚類分析方法。

本文對比了3種時空大數據聚類方法：

(1) 局域網集中存儲全集時空數據聚類方法(簡稱LGCP方法)。將分布節點交通流數據抽取，并傳輸到中心節點，由中心節點對幾種存儲的數據全集進行Map和Reduce運算，得到聚類結果。

(2) 廣域網分布存儲全集時空數據聚類方法(簡稱WGCP方法)。對分布節點本地存儲的交通流數據執行Map和Combine運算，在分布節點計算得到中間結果后，傳輸到中心節點，在中心節點完成結果合并，得到聚類結果。

(3) 廣域網分布增量時空數據聚類方法(簡稱DICP方法)。該方法基于WGCP方法執行，首次聚類完成之后，后續多個時間周期利用增量方式完成聚類，既可保證周期內數據量較為穩定，又可以通過迭代完成聚類結果的優化。

試驗結果見表1—表3。

表1 LGCP時空數據聚類方法結果

從聚類效率方面對比3種方法：LGCP方法將數據從分布節點提取到中心節點時，由于數據量大，耗費時間較長，聚類整體效率較低；WGCP方法有效將分布節點計算能力利用起來，但隨著系統持續運行，數據全集容量越來越大，聚類時間也會越來越長；DICP方法在首次聚類運算時，參與計算的數據量較小，而后每個時間周期的數據量相對穩定，而且后續周期僅針對增量數據進行運算，可以在較大程度上提高整體計算效率。

表2 WGCP時空數據聚類方法結果

表3 DICP時空數據聚類方法結果

從聚類準確率方面對比3種方法，由表1—表3的準確率可以看出，數據量對于聚類結果的準確程度起著非常重要的作用，隨著數據量的增加，聚類準確率不斷提高。因此考慮到聚類準確率，以往的抽樣降維方法會導致大量原始數據被篩除，進而影響聚類結果的準確率。而DICP方法采用的分布式增量策略避免了有效數據被篩除，在減小每個時間周期的數據量的基礎上，能夠保證聚類的準確程度。

從多個時間周期聚類分析得到的集合數量和被解體的集合數量分析，具體見表4。

表4 DICP時空數據聚類方法結果

從表4可以看出，新的時間周期都會利用增量數據將原有的一些聚類簇解體，進而生成新的聚類簇，得到更為準確的修正結果。因此，DICP方法更加適合在大數據環境下使用，利用增量解體方式不斷修正聚類結果，是保證增量聚類質量的有效手段。

4 結 語

本文研究了一種基于分布式增量的交通大數據聚類分析方法，并在廣域網分布式試驗環境中進行了驗證。分布式增量聚類流程DICP在分布節點完成大量聚類運算，最終在中心節點完成聚類結果合并，不但可以減少重復計算和遷移拷貝次數，而且可以通過增量機制持續對聚類結果進行修正，能夠在保持聚類準確性的條件下提升整體運算效率。其不足之處在于，本文試驗數據雖然已經達到一定規模，但分布節點有限，而隨著分布節點的增加，中心節點的傳輸和運算負載會急劇增加，導致計算效率下降，因此為了緩解中心節點壓力，可以在今后的試驗中設計多層分布式結構，經過分中心的多層聚類，不斷合并最終完成全局聚類。

IMSTDCA時空數據聚類方法通過數據聚集趨勢預分析、聚類算法和結果評價3個步驟，構建了一體化時空鄰域，在考慮時空數據相關性、耦合性與異質性的同時，在時間和空間維度保證了聚類結果的準確性，經過試驗證明該方法的聚類結果可靠有效。但本文研究的IMSTDCA聚類方法僅針對交通流時空數據進行了驗證，地理實體的時空尺度比較局限，因此在下一步的工作中，還應該對其他類型的地理實體聚類問題進行研究，為預測和決策提供更為有效的數據挖掘方法和工具。

[1] 李德仁,馬軍,邵振峰.論時空大數據及其應用[J].衛星應用,2015(9):7-11.

[2] 鄧敏,劉啟亮,王佳璆，等.時空聚類分析的普適性方法[J].中國科學(信息科學),2012,42(1):111-124.

[3] BAGIROV A M. Modified Global K-means Algorithm for Minimum Sum-of-squares Clustering Problems[J]. Pattern Recognition, 2008, 41(10): 3192-3199.

[4] 雷小鋒,謝昆青,林帆.一種基于K-Means局部最優性的高效聚類算法[J].軟件學報, 2008,19(7): 1683-1692.

[5] GRAFFNEY S, SMYTH P. Trajectory Clustering with Mixtures of Regression Models[C] ∥Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM,1999:63-72.

[6] CHUDOVA D, GAFFNEY S， MJOLSNESS E, et al. Translation—invariant Mixture Models for Curve Clustering[C]∥Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM,2003:79-88.

[7] ALON J,SCLAROFF S,KOLLIOS G,et a1.Discovering Clusters in Motion Time-series Data[C] ∥Proceedings of the 2003 IEEE Conference on Computer Vision and Pattern Recognition. Los Alamitos, CA:IEEE Computer Society,2003:375-381.

[8] LI X,HAN J, LEE J G, et al. Traffic Density-based Discovery of Hot Routes in Road Networks[C] ∥Proceedings of the 10th International Conference on Advances in Spatial and Temporal Databases. Berlin: Springer,2007:441-459.

[9] BIRANT D,KUT A.ST-DBSCAN:An Algorithm for Clustering Spatial-temporal Data[J].Data & Knowledge Engineering,2007,60(1):208-221.

[10] ZHENG K, ZHENG Y, YUAN N J, et al. On Discovery of Gathering Patterns from Trajectories[C]∥IEEE 29th International Conference on Data Engineering. [S.l.]:IEEE,2013:242-253.

[11] BOSE J H,ANDRZEJAK A, HOGQVIST M. Beyond Online Aggregation: Parallel and Incremental Data Mining with Online Map-Reduce[C]∥Proceedings of Workshop on Massive Data Analytics on the Cloud. New York:ACM,2010.

[12] LAPTEV N, ZENG K, ZANIOLO C. Very Fast Estimation for Result and Accuracy of Big Data Analysis:The EARL System[C]∥Proceedings of ICDE.Piscataway,NJ:IEEE,2013:1296-1299.

[13] ZHAO W Z, MARTHA V S, XU X W. PSCAN: A Parallel Structural Clustering Algorithm for Big Networks in MapReduce[C]∥Proceedings of AINA.Piscataway,NJ:IEEE,2013:862-869.

[14] 楊杰,李小平,陳湉. 基于增量時空軌跡大數據的群體挖掘方法[J].計算機研究與發展,2014, 51:76-85.

[15] MARTIN R L, OEPPEN J E. The Identification of Regional Forecasting Models Using Space-time Correlation Functions[J]. Transactions of the Institute of British Geographers, 1975, 66: 95-118.

[16] HAINING R P.Spatial Data Analysis:Theory and Practice[M]. Cambridge: Cambridge University Press, 2003：183-201.

[17] KAMARIANAKIS Y, PRASTACOS P. Space-time Modeling of Traffic Flow[J]. Computers & Geosciences, 2005, 31(2)：119-133.

[18] BEZDEK J C, PAL N R. Some New Indexes of Cluster Validity[J]. IEEE Transactions on Systems Man & Cybernetics Part B, 1998, 28: 301-315.

Traffic Flow Big Data Clustering Analysis Method Based on Distributed Incremental Mechanism

LI Xin1,2

(1. Collaborative Innovation Center of Three-aspect Coordination of Central Plain Economic Region, Henan University of Economics and Law, Zhengzhou 450046， China; 2. College of Resource and Environment, Henan University of Economics and Law, Zhengzhou 450046， China)

Spatio-temporal clustering analysis is an effective way of using spatio-temporal big data. This paper proposes a distributed incremental big data clustering analysis method. The incremental distribution mechanism can not only reduce the repeated calculation and the number of copies, but also can modify the clustering results continuously. And it is able to improve the operational efficiency under the condition of keeping in clustering accuracy. The clustering algorithm includes three steps: data aggregation trend analysis, clustering algorithm and result evaluation. It constructs an integrated spatio-temporal neighborhood, which guarantees the accuracy of clustering results in time and space. The experiments show that this method can realize the fast and efficient information mining of spatio-temporal big-data.

spatio-temporal data；big data；cluster analysis；incremental clustering；spatio-temporal neighborhood

李欣.分布式增量機制下的交通流大數據聚類分析[J].測繪通報，2017(7)：61-65.

10.13474/j.cnki.11-2246.2017.0224.

2016-10-12；

2017-01-24

國家自然科學基金(41501178)；河南財經政法大學博士科研啟動基金(800257)

李 欣(1981—)，男，博士，講師，主要研究方向為地理信息系統理論研究與實踐應用。E-mail：lixin992319@163.com

P208

A

0494-0911(2017)07-0061-05