李 欣

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

?

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

李 欣1,2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(4) 由中心節(jié)點(diǎn)的Reduce運(yùn)算進(jìn)行結(jié)果合并，并計(jì)算每個(gè)類的全局偏離誤差。

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

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

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

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

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

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

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

(1)

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

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

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

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

Entirety_Constraint(Pi)=Entirety_Mean+

(2)

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

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

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

(3)

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

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

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

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

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

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

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

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

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

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

3 試驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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

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

[1] 李德仁,馬軍,邵振峰.論時(shí)空大數(shù)據(jù)及其應(yīng)用[J].衛(wèi)星應(yīng)用,2015(9):7-11.

[2] 鄧敏,劉啟亮,王佳璆，等.時(shí)空聚類分析的普適性方法[J].中國科學(xué)(信息科學(xué)),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].軟件學(xué)報(bào), 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í)空軌跡大數(shù)據(jù)的群體挖掘方法[J].計(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

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

10.13474/j.cnki.11-2246.2017.0224.

2016-10-12；

2017-01-24

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

李 欣(1981—)，男，博士，講師，主要研究方向?yàn)榈乩硇畔⑾到y(tǒng)理論研究與實(shí)踐應(yīng)用。E-mail：lixin992319@163.com

P208

A

0494-0911(2017)07-0061-05