李 欣,孟德友

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

時空大數(shù)據(jù)分布式增量IMSTDCA聚類方法研究

李 欣1,2,孟德友1,2

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

時空聚類分析是對時空大數(shù)據(jù)進行利用的一種有效手段，目前傳統(tǒng)聚類算法存在著大規(guī)模分布數(shù)據(jù)難以處理，海量數(shù)據(jù)處理時間較長，確定參數(shù)困難，聚類質(zhì)量較差等缺陷。因此，提出一種分布式增量聚類流程DICP，利用廣域網(wǎng)分布增量聚類方法，避免大量數(shù)據(jù)的傳輸拷貝，有效提升聚類運算效率。對于DICP流程中的時空數(shù)據(jù)聚類算法本身，研究了一種大數(shù)據(jù)環(huán)境下的IMSTDCA時空數(shù)據(jù)聚類算法，借助密度聚類的思想，通過時空數(shù)據(jù)的聚集趨勢預(yù)分析、時空數(shù)據(jù)聚類算法，以及時空數(shù)據(jù)聚類結(jié)果評價3個步驟完成聚類分析，實現(xiàn)時空大數(shù)據(jù)的快速高效信息挖掘。

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

在當(dāng)代社會發(fā)展中，互聯(lián)網(wǎng)和傳感器網(wǎng)正在產(chǎn)生越來越多的和時空位置有關(guān)的社會活動數(shù)據(jù)，這些海量多元數(shù)據(jù)稱為時空大數(shù)據(jù)[1]。

時空數(shù)據(jù)挖掘是利用時空大數(shù)據(jù)最為有效的一種手段，其中的時空聚類分析是地理信息科學(xué)與云計算交叉學(xué)科的一個重點研究課題[2]。目前已經(jīng)產(chǎn)生了很多對于時空大數(shù)據(jù)進行管理分析的研究成果，但針對大數(shù)據(jù)環(huán)境下的時空聚類分析方法研究，仍然沒有解決分布式海量數(shù)據(jù)挖掘效率的問題，以及很好地適應(yīng)時空數(shù)據(jù)的耦合性、關(guān)聯(lián)性、異質(zhì)性問題。因此，本文將從分析時空大數(shù)據(jù)的研究現(xiàn)狀出發(fā)，研究一種大數(shù)據(jù)環(huán)境下的時空數(shù)據(jù)聚類方法，從而更好地適應(yīng)時空大數(shù)據(jù)的復(fù)雜特點。

1 大數(shù)據(jù)環(huán)境下時空數(shù)據(jù)聚類分析研究現(xiàn)狀

1.1 時空數(shù)據(jù)聚類分析研究現(xiàn)狀

目前時空聚類分析是數(shù)據(jù)挖掘領(lǐng)域的前沿之一，方法主要包括以下幾種：①基于劃分的聚類方法。雷小鋒等[3]提出K-MeanSCAN的算法；Bagirov[4]提出的全局K-Means算法。②基于模型的聚類方法。Gaffney等人[5]對軌跡數(shù)據(jù)使用了回歸混合模型進行聚類；Chudova等人[6]研究了地理實體的時間和空間軌跡漂移參數(shù)的聚類方法；Alon等人[7]利用馬爾可夫模型表達地理實體簇在兩個相鄰位置的轉(zhuǎn)換關(guān)系。③基于密度的聚類方法。Birant等人[8]研究了ST-DBSCAN基于密度的時空聚類算法，Li等人[9]提出了交通網(wǎng)絡(luò)中熱點路線的聚類算法。④基于大數(shù)據(jù)的聚類方法。Bose等人[10]提出一種增量并行數(shù)據(jù)挖掘方法；Zhao等人[11]提出基于MapReduce和邊結(jié)構(gòu)相似度的聚類方法；Laptev等人[12]通過樣本抽樣和放回的方法，減少了進入MapReduce運算的數(shù)據(jù)量。

已有研究成果的主要特點是，在局域網(wǎng)中集中存儲數(shù)據(jù)，使用抽樣方法減少數(shù)據(jù)規(guī)模，利用降維方法降低數(shù)據(jù)復(fù)雜程度，然后再利用傳統(tǒng)方法實現(xiàn)聚類運算[13]，仍然無法解決大數(shù)據(jù)環(huán)境下時空數(shù)據(jù)聚類面臨的問題。

1.2 分布式時空大數(shù)據(jù)聚類方法研究策略

本文的研究策略是在已有研究成果的基礎(chǔ)上，分析已有算法和實現(xiàn)中存在的問題，顧及在處理大數(shù)據(jù)集時需要的可伸縮和高效率問題，提出一種大數(shù)據(jù)環(huán)境下基于MapReduce的分布式增量聚類流程DICP(Distributed Incremental Clustering Process)，該方法在廣域網(wǎng)環(huán)境下，顧及時空數(shù)據(jù)特征利用增量和分布機制實現(xiàn)聚類，將聚類計算任務(wù)分配到各個分布式節(jié)點，避免大量數(shù)據(jù)的傳輸拷貝，節(jié)約網(wǎng)絡(luò)資源，減小參與計算的數(shù)據(jù)規(guī)模和聚類運算的重復(fù)執(zhí)行次數(shù)，可大大縮短海量時空數(shù)據(jù)聚類運算時間，提升運算效率。

對于DICP流程中的時空數(shù)據(jù)聚類算法本身，本文研究了一種大數(shù)據(jù)環(huán)境下的IMSTDCA時空數(shù)據(jù)聚類算法(The Improved Method of Spatio-Temporal Data Cluster Analysis Based on STARIMA,IMSTDCA)。該方法通過時空數(shù)據(jù)的聚集趨勢預(yù)分析，聚類算法，以及聚類結(jié)果評價3個步驟，對時空自回歸移動平均模型[14](Space-time Autoregressive Integrated Moving Average,STARIMA) 進行擴展，構(gòu)建一體化時空鄰域，實現(xiàn)時空大數(shù)據(jù)的快速高效信息挖掘。

2 時空大數(shù)據(jù)聚類分析關(guān)鍵技術(shù)實現(xiàn)

2.1 分布式增量聚類分析流程DICP

本文提出了一種分布式增量聚類流程DICP(Distributed Incremental Clustering Process)。流程將網(wǎng)絡(luò)中的節(jié)點分為中心節(jié)點和分布節(jié)點，按照時間間隔分為多個周期階段持續(xù)執(zhí)行。第一階段，是初次聚類分析階段，稱作歷史全集數(shù)據(jù)聚類階段，基于網(wǎng)絡(luò)中所有節(jié)點的數(shù)據(jù)全集進行分布式聚類運算；后期階段，稱作周期增量數(shù)據(jù)聚類階段，利用后續(xù)階段產(chǎn)生的有限增量數(shù)據(jù)集合進行聚類運算，用于得到新的聚類結(jié)果并提高聚類準(zhǔn)確度。

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

歷史全集階段是對網(wǎng)絡(luò)中所有節(jié)點的已有數(shù)據(jù)全集進行聚類。該階段在每個分布節(jié)點上將已有數(shù)據(jù)全集切分為較小數(shù)據(jù)分塊，由Map運算完成各個數(shù)據(jù)分塊的聚類，形成中間聚類結(jié)果，由Combine運算將多個中間聚類結(jié)果合并，并傳輸?shù)街行墓?jié)點，利用Reduce運算合并中間結(jié)果，生成全局聚類結(jié)果，其基本思路如下：

1)將分布節(jié)點Ki(i=1,2,…,n)的已有數(shù)據(jù)切塊為M個數(shù)據(jù)分塊。

2)在分布節(jié)點的Map運算中使用IMSTDCA算法對每個數(shù)據(jù)分塊進行聚類運算，從而產(chǎn)生M個數(shù)據(jù)塊聚類結(jié)果。

3)在分布節(jié)點本地由Combine運算將M個數(shù)據(jù)塊聚類結(jié)果合并，從而生成中間聚類結(jié)果。

4)n個分布節(jié)點的中間結(jié)果傳輸?shù)街行墓?jié)點后，由中心節(jié)點的Reduce運算執(zhí)行所有中間結(jié)果的二次合并，生成全局聚類中心。

5)如果全局聚類結(jié)果收斂或達到最大迭代次數(shù)，則完成聚類；否則，由Reduce運算計算下一次迭代所使用的比較參數(shù)，分發(fā)給每個數(shù)據(jù)塊后，從步驟2)開始進行下一次迭代。

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

周期增量階段是對每個數(shù)據(jù)增長周期新產(chǎn)生的增量數(shù)據(jù)進行聚類，該階段將每個分布節(jié)點數(shù)據(jù)增量周期內(nèi)的新產(chǎn)生的增量數(shù)據(jù)切分為較小數(shù)據(jù)分塊并進行聚類運算，其基本思想如下：

1)將分布節(jié)點Ki(i=1,2,…,n)某一周期內(nèi)新增數(shù)據(jù)集合切塊為ΔM個增量數(shù)據(jù)分塊。

2)在分布節(jié)點的Map運算中，使用IMSTDCA算法中的時空距離計算方法，計算每一條增量數(shù)據(jù)記錄與已有聚類中心的時空距離，若距離小于規(guī)定閾值，則將該數(shù)據(jù)記錄歸并到距離最小的類中。

3)按照已有聚類中心對分布節(jié)點Ki的所有數(shù)據(jù)記錄進行劃分，然后由分布節(jié)點中的Combine運算執(zhí)行偏離誤差計算方法，從而得到每個聚類中心在分布節(jié)點Ki的局部偏離誤差。

4)將所有分布節(jié)點Combine運算計算得到的局部偏離誤差傳輸?shù)街行墓?jié)點后，由中心節(jié)點的Reduce運算進行合并，完成每個類的全局偏離誤差的計算。

5)所有聚類結(jié)果的全局偏離誤差若小于規(guī)定指標(biāo)，則完成了本周期增量聚類；若某個聚類結(jié)果的全局偏離誤差大于規(guī)定指標(biāo)，則將該類解體，將解體后的數(shù)據(jù)記錄和未被分類的數(shù)據(jù)記錄組合成為新的待聚類數(shù)據(jù)集，按照歷史全集階段方法重新進行聚類運算。

經(jīng)過中心節(jié)點和分布式節(jié)點多個周期的聚類運算，即可以較高的準(zhǔn)確度和分布式并行運算效率，完成針對某些應(yīng)用的時空大數(shù)據(jù)的聚類分析。

2.2 IMSTDCA時空數(shù)據(jù)聚類分析方法

在分布式增量聚類分析流程中，最為關(guān)鍵的就是時空數(shù)據(jù)的聚類分析方法，算法的優(yōu)劣直接影響到整個聚類分析過程的準(zhǔn)確性和高效性。本文提出了IMSTDCA時空數(shù)據(jù)聚類分析方法，包括時空數(shù)據(jù)聚集趨勢預(yù)分析，聚類算法，聚類結(jié)果評價3個步驟，其中時空數(shù)據(jù)聚類算法又包含構(gòu)建時空鄰域和聚類分析兩部分。圖1是IMSTDCA聚類分析方法流程圖。

圖1 IMSTDCA時空數(shù)據(jù)聚類分析方法流程圖

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

時空數(shù)據(jù)聚集趨勢預(yù)分析主要是為了在進行大量的聚類計算之前，先對數(shù)據(jù)的相關(guān)性和異質(zhì)性進行分析，判斷對地理實體進行聚類的可行性，如果地理實體之間不存在相關(guān)性，則無法通過聚類分析判斷實體之間的聚集現(xiàn)象。可以使用Geary’C指數(shù)、Moran’I指數(shù)、變差函數(shù)等方法[15]對空間相關(guān)性進行判斷，若數(shù)據(jù)呈現(xiàn)隨機分布，則計算出來的結(jié)果空間不相關(guān)，地理實體之間也就沒有聚集趨勢，無法執(zhí)行聚類分析運算。

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

2.2.2.1 構(gòu)建時空鄰域

在時空數(shù)據(jù)聚集趨勢預(yù)分析基礎(chǔ)上，已經(jīng)獲得了時空平穩(wěn)的數(shù)據(jù)集合，在此數(shù)據(jù)集中可以使用改進的STARIMA時間延遲算子進行時間鄰域的判斷。時空自回歸移動平均模型STARIMA公式如下：

(1)

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

在時空聚類分析中，某個時空實體不但會受到前一時間延遲內(nèi)的其他實體的影響，同樣該實體也會對后一時間延遲內(nèi)的其他時空實體產(chǎn)生影響，因此,可以將STARIMA模型中的時間延遲k擴展為以某一時刻為中心的時間半徑，以時間半徑作為時空聚類分析的時間維度。

另一個方面就是要確定時空實體之間的空間鄰近關(guān)系。在空間分析方法中，如果使用未經(jīng)任何處理的Delaunay三角網(wǎng)進行聚類分析的鄰近關(guān)系判斷，在網(wǎng)絡(luò)邊緣將產(chǎn)生較大誤差，從而對聚類分析產(chǎn)生不可忽略的影響，從圖2(a)中可以看出未經(jīng)處理的Delaunay三角網(wǎng)邊界誤差。

本文研究了一種基于整體和局部距離約束進行修正的Delaunay三角網(wǎng)構(gòu)建時空實體的空間鄰近關(guān)系。

針對Delaunay三角網(wǎng)中頂點Pi，其整體距離約束條件公式如下：

Entiretyconstraint(Pi)=EntiretyMean+

(2)

式中：EntiretyMean為所有邊長的均值；Mean(Pi)為頂點Pi的所有鄰接邊的邊長均值；Entirentyvariance為所有邊長的方差。

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

Localityconstraint(Pi)=LocalityMean(Pi)+

(3)

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

判斷空間鄰近關(guān)系時，按照順序刪除長度大于整體距離約束條件和局部距離約束條件的邊，可得到圖2(b)和圖2(c)中的結(jié)果，即為時空實體在空間維度鄰近關(guān)系的最終結(jié)果。

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

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

時空鄰域定義了時空實體在時間和空間維度的鄰近關(guān)系，時空聚類流程如下：

1)首先選取一個時空實體作為時空中心，若其時間鄰域與空間鄰域內(nèi)的所有時空實體都與其滿足時空鄰接條件，則認(rèn)為該時空實體為初始時空中心。

2)以該初始時空中心為核心，利用前文定義的時空鄰域判斷周圍時空實體與時空中心的遠近關(guān)系，按照順序加入距離最近的一個時空實體，開始生成第一個聚類集合。

3)按照步驟2)中原則擴展聚類集合，將已加入到聚類集合中的時空實體作為擴展中心，繼續(xù)利用時空鄰域?qū)χ車鷮嶓w進行判斷，依次將滿足時空鄰接條件的實體加入聚類集合，直到周圍沒有符合條件的實體為止，此時即完成了一個聚類集合的生成。

4)對剩余未被聚類的時空實體進行判斷，若某個沒有被標(biāo)記為孤立點，則可以將其作為另一個初始時空中心，重復(fù)進行步驟1)到3)的運算，若所有時空實體均屬于某個聚類集合，或被標(biāo)記為孤立點，則完成了整個聚類計算。

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

本文時空數(shù)據(jù)聚類方法有兩個影響其復(fù)雜度的因素：一是在時空鄰域中搜索鄰近目標(biāo)，二是生成聚類集合。設(shè)時空數(shù)據(jù)集中有n個實體，則基于本文方法構(gòu)建時空鄰域時，復(fù)雜度約為O(nlog2n)，比ST-DBSCAN[8]方法的復(fù)雜度O(n2)低；而在生成時空簇時，其復(fù)雜度近似于ST-DBSCAN方法，同時也近似線性，因此，本文提出的時空數(shù)據(jù)聚類分析方法IMSTDCA復(fù)雜度約為O(nlog2n)。

3 實驗結(jié)果分析

本文實驗基于智能交通綜合管理平臺搭建，該平臺提供了城市交通指揮系統(tǒng)、智能交通誘導(dǎo)系統(tǒng)、聯(lián)網(wǎng)視頻監(jiān)控系統(tǒng)、智能交通檢測系統(tǒng)等一整套綜合管理平臺。目前，已經(jīng)在鄭州、開封、洛陽等城市實現(xiàn)了部分應(yīng)用。

實驗選取鄭州為中心節(jié)點，開封和洛陽作為分布節(jié)點，基于真實廣域網(wǎng)環(huán)境搭建，利用系統(tǒng)采集車輛移動軌跡數(shù)據(jù)進行分析，驗證本文設(shè)計的分布式增量聚類分析流程DICP，以及IMSTDCA時空數(shù)據(jù)聚類分析方法。

本文進行了3種時空大數(shù)據(jù)聚類方法實驗，并對其結(jié)果進行了比較。

1)局域網(wǎng)集中存儲全集時空數(shù)據(jù)聚類方法(簡稱LGCP方法)。在分布節(jié)點中對軌跡數(shù)據(jù)進行抽樣，傳輸?shù)街行墓?jié)點集中存儲，然后由中心節(jié)點針對全集數(shù)據(jù)進行Map和Reduce運算，生成聚類結(jié)果。

2)廣域網(wǎng)分布存儲全集時空數(shù)據(jù)聚類方法(簡稱WGCP方法)。在分布節(jié)點的服務(wù)器上存儲時空數(shù)據(jù)，并行執(zhí)行Map和Combine運算，成中間聚類結(jié)果后，由分布節(jié)點將其推送到中心節(jié)點，由中心節(jié)點合并結(jié)果，生成全局聚類結(jié)果。

3)廣域網(wǎng)分布增量時空數(shù)據(jù)聚類方法(簡稱DICP方法)。該方法基于WGCP方法，在首次聚類分析完畢之后，之后每次數(shù)據(jù)增長周期僅僅針對增量數(shù)據(jù)進行聚類，從而保證每個周期的聚類計算數(shù)據(jù)量相對平穩(wěn)，最終通過不斷迭代優(yōu)化聚類結(jié)果。實驗結(jié)果如表1—表3所示。

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

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

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

對比3種方法可以看出：LGCP方法雖然不需要Combine運算，但是從分布節(jié)點抽取數(shù)據(jù)到中心節(jié)點仍然需要耗費大量時間，聚類效率較低。WGCP方法雖然利用了分布節(jié)點的計算能力，但是每次都基于數(shù)據(jù)全集進行運算，隨著數(shù)據(jù)量的增大，聚類時間會不斷增加。DICP方法在每個周期內(nèi)所參與計算的數(shù)據(jù)量遠遠小于WGCP方法中參與運算的數(shù)據(jù)全集，可以大大提高聚類運算效率。

再從聚類準(zhǔn)確率方面比較3種方法，表1～3中在數(shù)據(jù)量相同情況下，聚類準(zhǔn)確率基本相同，結(jié)果表明，數(shù)據(jù)規(guī)模大小是保證聚類準(zhǔn)確率的重要因素。同時也說明以往的抽樣降維方法，雖然可以在一定程度上提高聚類運算的效率，但是也會導(dǎo)致聚類準(zhǔn)確率的下降，而本文的DICP能夠有效保證聚類準(zhǔn)確程度。

進一步從每一增量周期聚類集合數(shù)量，以及被解體的集合數(shù)量分析聚類結(jié)果，具體如表4所示。

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

從表4可以看出，每一個增量周期都會對之前周期的聚類結(jié)果進行修正，即解體已有類并生成新類，聚類準(zhǔn)確率隨數(shù)據(jù)量增加而提高。由此可得，在數(shù)據(jù)不斷更新的大數(shù)據(jù)環(huán)境下，使用類解體方法對聚類結(jié)果進行不斷修正，是保證增量聚類質(zhì)量的一種有效方法。

4 結(jié)束語

本文提出了基于分布式增量聚類流程DICP和IMSTDCA時空數(shù)據(jù)聚類方法，并在廣域網(wǎng)分布式實驗環(huán)境中進行了驗證。

分布式增量聚類流程DICP通過增量聚類運算對之前完成的聚類結(jié)果進行持續(xù)修正，使得時空數(shù)據(jù)的重復(fù)聚類計算和遷移拷貝次數(shù)大大減少，在保持聚類結(jié)果準(zhǔn)確的條件下，運算效率明顯提升。本文實驗中的時空數(shù)據(jù)記錄已經(jīng)達到一定規(guī)模，但分布式節(jié)點仍然相對較少，在海量分布式節(jié)點條件下，中心節(jié)點的負載會大大增加，因此，可以設(shè)計多層次的分布式結(jié)構(gòu)，經(jīng)過多層次的聚類結(jié)果合并最終完成全局聚類，此種模式可以在海量分布式節(jié)點條件下緩解中心節(jié)點的壓力還有待在下一步的實驗中進行驗證。

IMSTDCA時空數(shù)據(jù)聚類方法包括時空數(shù)據(jù)的聚集趨勢預(yù)分析，時空數(shù)據(jù)聚類算法，以及時空數(shù)據(jù)聚類結(jié)果評價3個步驟，聚類方法在考慮時空數(shù)據(jù)相關(guān)性、耦合性與異質(zhì)性的同時，減少了人為主觀因素對聚類結(jié)果的影響，通過實驗證明了時空聚類結(jié)果可靠有效。本文研究的IMSTDCA聚類方法在實驗過程中僅僅針對車輛軌跡數(shù)據(jù)進行了驗證，時空尺度較為局限，并沒有對更大尺度的時空對象或現(xiàn)象進行研究，因此，在下一步的工作中，還需要對不同尺度下的時空對象聚類問題進行研究，探索更加全面反應(yīng)時空對象發(fā)展規(guī)律的數(shù)據(jù)挖掘方法，為預(yù)測和決策提供有效工具。

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

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

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

[4] BAGIROV A M. Modified global k-means algorithm for minimum sum-of-squares clustering problems[J]. Pattern Recognition, 2008, 41(10): 3192-3199.

[5] GRAFFNEY S, SMYTH P. Trajectory clustering with mixtures of regression models[C] //Proc of the 5th ACM SIGKDD Int Conf 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]//Proc of the 9th ACM SIGKDD Int Conf 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] //Proc of the 2003 IEEE Conf on Computer Vision and Pattern Recognition. Los Alamitos, CA:IEEE Computer Society,2003:375-381.

[8] BIRANT D, KUT A.ST-DBSCAN:An algorithm for clustering spatial-temporal data[J].Data&Knowledge Engineering,2007,60(1):208-221

[9] LI X,HAN J, LEE J G, et al. Traffic density-based discovery of hot routes in road networks[C] //Proc of the 10th Int Conf on Advances in Spatial and Temporal Databases. Berlin: Springer,2007:441-459.

[10] BOSE J H, ANDRZEJAK A, HOGQVIST M. Beyond online aggregation: Parallel and incremental data mining with online Map-Reduce[C]//Proc of Workshop on Massive Data Analytics on the Cloud. New York:ACM,2010.

[11] ZHAO W Z, MARTHA V S, XU X W. PSCAN: A parallel structural clustering algorithm for big networks in MapReduce[C]//Proc of AINA.Piscataway,NJ:IEEE,2013:862-869.

[12] LAPTEV N, ZENG K, ZANIOLO C. Very fast estimation for result and accuracy of big data analysis:The EARL system[C]//Proc of ICDE.Piscataway,NJ:IEEE,2013:1296-1299.

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

[14] MARTIN R L, OEPPEN J E. The identification of regional forecasting models using space-time correlation functions[M]. Trans Inst Brit Geogr, 1975, 66: 95-118.

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

[16] KAMARIANAKIS Y, PRASTACOS P. Space-time modeling of traffic flow. Comput Geosci-UK, 2005, 31: 119-133.

[17] BEZDEK J C, PAL N R. Some new indexes of cluster validity[C]. IEEE Trans Syst Man Cy, 1998, 28: 301-315.

[責(zé)任編輯：劉文霞]

Research on the distributed incremental IMSTDCA clustering method on spatio-temporal big data

LI Xin1,2,MENG Deyou1,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 means of using spatio-temporal big data. At present, the traditional clustering algorithm has some disadvantages, for which it’s difficult to deal with massive data, it takes much time to process massive data, it’s difficult to confirm the parameters, and the quality of clustering result is low. Therefore, a method, named distributed incremental clustering process(DICP) based on MapReduce is proposed in this paper, which can avoid the transferring and copying of large amounts of data, and greatly improve the efficiency of clustering operation. This paper studies IMSTDCA spatio-temporal data clustering algorithm on big data in DICP. This clustering algorithm makes clustering with the help of density clustering, including three steps: the analysis of gathered trend of spatio-temporal data, the spatio-temporal data clustering algorithm, and the evaluation of spatio-temporal data clustering result. This clustering algorithm can obtain valuable information from spatio-temporal big data in a fast and efficient way.

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

著錄：李欣,孟德友.時空大數(shù)據(jù)分布式增量IMSTDCA聚類方法研究[J].測繪工程，2017，26(11)：12-17.

10.19349/j.cnki.issn1006-7949.2017.11.003

2016-10-03

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

李 欣(1981-)，男，講師，博士.

K909

A

1006-7949(2017)11-0012-06