李 欣,孟德友

(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í)空大數(shù)據(jù)分布式增量IMSTDCA聚類方法研究

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在時(shí)空數(shù)據(jù)聚集趨勢(shì)預(yù)分析基礎(chǔ)上，已經(jīng)獲得了時(shí)空平穩(wěn)的數(shù)據(jù)集合，在此數(shù)據(jù)集中可以使用改進(jìn)的STARIMA時(shí)間延遲算子進(jìn)行時(shí)間鄰域的判斷。時(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ī)誤差。式中的時(shí)間延遲k可以代表實(shí)體在時(shí)間維度的距離，可以通過(guò)時(shí)空偏相關(guān)函數(shù)[16]以及時(shí)空自相關(guān)函數(shù)[17]計(jì)算獲得。

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

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

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

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

Entiretyconstraint(Pi)=EntiretyMean+

(2)

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

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

Localityconstraint(Pi)=LocalityMean(Pi)+

(3)

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

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

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

[3] 雷小鋒,謝昆青,林帆.一種基于K-Means局部最優(yōu)性的高效聚類算法[J].軟件學(xué)報(bào), 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í)空軌跡大數(shù)據(jù)的群體挖掘方法[J].計(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í)空大數(shù)據(jù)分布式增量IMSTDCA聚類方法研究[J].測(cè)繪工程，2017，26(11)：12-17.

10.19349/j.cnki.issn1006-7949.2017.11.003

2016-10-03

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

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

K909

A

1006-7949(2017)11-0012-06