分布式增量機制下的交通流大數(shù)據(jù)聚類分析

李 欣

(1. 河南財經(jīng)政法大學中原經(jīng)濟區(qū)“三化”協(xié)調(diào)發(fā)展河南省協(xié)同創(chuàng)新中心，河南 鄭州 450046; 2. 河南財經(jīng)政法大學資源與環(huán)境學院，河南 鄭州 450046)

?

分布式增量機制下的交通流大數(shù)據(jù)聚類分析

李 欣1,2

(1. 河南財經(jīng)政法大學中原經(jīng)濟區(qū)“三化”協(xié)調(diào)發(fā)展河南省協(xié)同創(chuàng)新中心，河南 鄭州 450046; 2. 河南財經(jīng)政法大學資源與環(huán)境學院，河南 鄭州 450046)

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

時空數(shù)據(jù)；大數(shù)據(jù)；聚類分析；增量聚類；時空鄰域

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

1 國內(nèi)外聚類分析研究現(xiàn)狀

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

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

2 聚類分析關(guān)鍵技術(shù)研究

2.1 分布式增量交通流大數(shù)據(jù)聚類分析流程

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

2.1.1 歷史全集數(shù)據(jù)聚類階段

首次聚類是針對所有節(jié)點歷史數(shù)據(jù)全集進行聚類分析的階段。首先對分布節(jié)點中的數(shù)據(jù)進行分塊，基于MapReduce中的Map運算完成數(shù)據(jù)塊的中間聚類，再使用Combine運算完成分布節(jié)點中間聚類結(jié)果合并，傳輸?shù)街行墓?jié)點后由Reduce運算完成分布節(jié)點聚類結(jié)果的合并，實現(xiàn)首次聚類分析。其基本思路是：

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

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

(3) 由Combine運算完成M個中間聚類結(jié)果的合并，并傳輸?shù)街行墓?jié)點。

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

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

2.1.2 周期增量數(shù)據(jù)聚類階段

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

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

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

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

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

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

2.2 時空數(shù)據(jù)聚類算法

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

2.2.1 時空數(shù)據(jù)聚集趨勢預(yù)分析

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

2.2.2 時空數(shù)據(jù)聚類算法

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

(1)

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

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

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

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

Entirety_Constraint(Pi)=Entirety_Mean+

(2)

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

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

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

(3)

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

圖2 基于距離約束Delaunay三角網(wǎng)的空間鄰近關(guān)系

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

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

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

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

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

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

2.2.3 時空數(shù)據(jù)聚類結(jié)果評價

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

3 試驗結(jié)果分析

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

本文對比了3種時空大數(shù)據(jù)聚類方法：

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

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

(3) 廣域網(wǎng)分布增量時空數(shù)據(jù)聚類方法(簡稱DICP方法)。該方法基于WGCP方法執(zhí)行，首次聚類完成之后，后續(xù)多個時間周期利用增量方式完成聚類，既可保證周期內(nèi)數(shù)據(jù)量較為穩(wěn)定，又可以通過迭代完成聚類結(jié)果的優(yōu)化。

試驗結(jié)果見表1—表3。

表1 LGCP時空數(shù)據(jù)聚類方法結(jié)果

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

表2 WGCP時空數(shù)據(jù)聚類方法結(jié)果

表3 DICP時空數(shù)據(jù)聚類方法結(jié)果

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

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

表4 DICP時空數(shù)據(jù)聚類方法結(jié)果

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

4 結(jié) 語

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

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

[1] 李德仁,馬軍,邵振峰.論時空大數(shù)據(jù)及其應(yīng)用[J].衛(wèi)星應(yīng)用,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局部最優(yōu)性的高效聚類算法[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] 楊杰,李小平,陳湉. 基于增量時空軌跡大數(shù)據(jù)的群體挖掘方法[J].計算機研究與發(fā)展,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

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

10.13474/j.cnki.11-2246.2017.0224.

2016-10-12；

2017-01-24

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

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

P208

A

0494-0911(2017)07-0061-05