移動(dòng)軌跡聚類方法研究綜述

牟乃夏，徐玉靜，張恒才，陳 潔，張靈先，劉希亮

(1. 山東科技大學(xué)測(cè)繪科學(xué)與工程學(xué)院，山東 青島 266590； 2. 中國(guó)科學(xué)院地理科學(xué)與資源研究所資源與環(huán)境信息系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京100101)

人類的出行活動(dòng)造就了城市的動(dòng)態(tài)性。城市中移動(dòng)對(duì)象(人或車輛)的位置變化感知了城市的韻律，是城市動(dòng)態(tài)性的直接體現(xiàn)[1-2]。隨著城市的急劇擴(kuò)張，以及人類活動(dòng)空間頻度和廣度的不斷拓展，人類的出行活動(dòng)引發(fā)了一系列的社會(huì)問題，如交通擁堵、能耗增加、空氣污染等，這些問題影響著人類的生活質(zhì)量，也一直是城市管理亟待解決的問題。出行活動(dòng)在帶來一系列問題的同時(shí)，出行所產(chǎn)生的軌跡數(shù)據(jù)也為解決這些問題提供了新的契機(jī)。出行軌跡的獲取隨著物聯(lián)網(wǎng)和智能移動(dòng)設(shè)備的普及而更加便捷[3-4]，由此從這些軌跡(出租車軌跡、公卡刷卡、手機(jī)定位、社交網(wǎng)站簽到等數(shù)據(jù))數(shù)據(jù)中挖掘人類活動(dòng)信息和活動(dòng)規(guī)律從而探求深層次的移動(dòng)模式的研究已經(jīng)廣泛開展[5-6]。基于相似性的空間聚類是挖掘軌跡隱含的語(yǔ)義信息的重要方法[7]，它通過分析軌跡數(shù)據(jù)的時(shí)間、空間和其他屬性信息，將相似的數(shù)據(jù)聚集在一個(gè)類簇中，從而發(fā)現(xiàn)一些有意義的信息。如發(fā)現(xiàn)人類的移動(dòng)模式[8]、城市的不同功能分區(qū)[9]、興趣點(diǎn)和興趣區(qū)域的分布[10-11]等，從而為解決城市問題提供直接的、實(shí)時(shí)的數(shù)據(jù)與方法支持。

1 移動(dòng)軌跡模型

軌跡數(shù)據(jù)是一組帶有時(shí)間戳并按時(shí)間排序的離散點(diǎn)序列。對(duì)移動(dòng)軌跡數(shù)據(jù)進(jìn)行挖掘之前，必須要對(duì)其模型進(jìn)行定義，根據(jù)軌跡模型的定義，來確定軌跡的相似性度量的衡量標(biāo)準(zhǔn)，從而基于軌跡的相似性對(duì)對(duì)象進(jìn)行聚類，進(jìn)一步挖掘數(shù)據(jù)的語(yǔ)義信息。本文將不同的移動(dòng)軌跡數(shù)據(jù)總結(jié)為兩種模型：軌跡點(diǎn)模型與軌跡段模型。

1.1 軌跡點(diǎn)模型

移動(dòng)對(duì)象經(jīng)過事件觸發(fā)記錄下來的軌跡，或只能反映出行流的軌跡可以用軌跡點(diǎn)模型來表達(dá)。軌跡點(diǎn)模型可以表示為

TRa={(ID1,X1,Y1,Ti,v1),(ID2,X2,Y2,T2,v2),…}

(1)

TRb={(ID1,O1,D1,Ti,v1),(ID2,O2,D2,T2,v2),…}

(2)

式(1)表示常規(guī)的軌跡點(diǎn)模型。其中，IDi是軌跡點(diǎn)的唯一標(biāo)識(shí)；(Xi,Yi)是軌跡點(diǎn)在二維平面上的坐標(biāo)；Ti是軌跡點(diǎn)記錄的時(shí)刻；vi是移動(dòng)對(duì)象的其他屬性。式(2)表示OD流模型，模型中的一些參數(shù)與式(1)中的相同，Oi和Di分別表示出行流的起始點(diǎn)與終點(diǎn)的坐標(biāo)。

手機(jī)通話數(shù)據(jù)、WiFi熱點(diǎn)數(shù)據(jù)、社交網(wǎng)絡(luò)簽到數(shù)據(jù)和公共交通數(shù)據(jù)(公交卡刷卡、地鐵和公共自行車)等都可以看作是軌跡點(diǎn)模型。該類數(shù)據(jù)粒度較粗，不能直接反映人類活動(dòng)的真實(shí)軌跡，但能反映人類頻繁活動(dòng)或到訪的區(qū)域。其中，手機(jī)通話數(shù)據(jù)是基于基站產(chǎn)生的軌跡數(shù)據(jù)，該類數(shù)據(jù)的位置點(diǎn)是手機(jī)所在的基站位置，數(shù)據(jù)的精度取決于基站的密度；社交網(wǎng)絡(luò)簽到數(shù)據(jù)為簽到點(diǎn)的位置數(shù)據(jù)，往往包含著很強(qiáng)的語(yǔ)義信息；公交交通數(shù)據(jù)是上下車的位置數(shù)據(jù)，能很好地反映OD流。該類軌跡數(shù)據(jù)主要應(yīng)用于城市職住地分析[12-13]、個(gè)體活動(dòng)規(guī)律[14]、城市空間結(jié)構(gòu)發(fā)現(xiàn)[15]等方面的研究。

1.2 軌跡段模型

軌跡段是指通過兩個(gè)軌跡點(diǎn)之間的線性插值得到的軌跡段，軌跡段模型可以表示為

TR={SubTr1,SubTr2,…,SubTrn}

(3)

SubTr=(IDsub,trP1,trP2)

(4)

式(3)表示移動(dòng)對(duì)象的一條整軌跡，其由許多子軌跡SubTr組成。式(4)中trP1和trP2表示兩個(gè)相鄰的軌跡點(diǎn)。子軌跡段就是由兩個(gè)相鄰軌跡點(diǎn)之間進(jìn)行線性插值得到的。

由GPS終端采集的頻率較高的定位數(shù)據(jù)得到的軌跡數(shù)據(jù)可以用軌跡段模型來表達(dá)。該類數(shù)據(jù)具有固定的時(shí)間間隔，定位精度較高，如出租車軌跡數(shù)據(jù)，該類軌跡數(shù)據(jù)通常受限于道路交通路網(wǎng)[16]。通過對(duì)該類數(shù)據(jù)的挖掘可以實(shí)時(shí)獲取城市交通狀況，如車速、車流量等反映交通擁堵狀態(tài)的信息[17]；還可以發(fā)現(xiàn)城市熱點(diǎn)與預(yù)測(cè)未來的活動(dòng)熱點(diǎn)等[18]。

2 時(shí)空相似性度量

相似性度量標(biāo)準(zhǔn)是對(duì)數(shù)據(jù)進(jìn)行聚類的基礎(chǔ)，通過相似性度量來確定軌跡點(diǎn)或軌跡段之間的關(guān)系，再對(duì)軌跡進(jìn)行聚類分析。最終得到的結(jié)果，是簇內(nèi)相似度盡可能大，簇間相似度盡可能小。因此，需要定義一個(gè)軌跡間的相似度衡量標(biāo)準(zhǔn)。對(duì)于軌跡點(diǎn)模型，可以根據(jù)數(shù)據(jù)特點(diǎn)和具體分析的需求定義一種距離函數(shù)，然后再根據(jù)傳統(tǒng)的聚類方法進(jìn)行聚類。對(duì)于軌跡段模型，相似度衡量標(biāo)準(zhǔn)較為復(fù)雜，需要判斷各軌跡段在時(shí)空上的相似性。下面從空間相似性、時(shí)間相似性和時(shí)空相似性來說明軌跡點(diǎn)模型和軌跡段模型的相似性衡量標(biāo)準(zhǔn)。

2.1 空間相似性度量

對(duì)于軌跡點(diǎn)模型而言，空間相似性就是指空間距離函數(shù)(歐氏距離和路網(wǎng)距離)?？臻g距離函數(shù)如下

(5)

式中，(1)表示軌跡點(diǎn)A、B之間的歐氏距離；(2)表示路網(wǎng)距離。

兩條軌跡的空間相似性，是由相同子軌跡段所占比例來確定的兩條軌跡TR1和TR2(如圖1所示)，分別表示為[19]

TR1={SubTr1,SubTr2,SubTr3,SubTr4,SubTr5}

(6)

TR2={SubTr1,SubTr6,SubTr7,SubTr8,SubTr9,SubTr4}

(7)

圖1 軌跡段模型

兩條軌跡的空間相似性，可以用重疊部分的軌跡段的累加長(zhǎng)度與整條軌跡長(zhǎng)度的比值來表示

(8)

式中，lm(TRi,TRj)表示相似軌跡段的長(zhǎng)度；ls(TRi)和ls(TRj)分別表示軌跡i和j的總長(zhǎng)度。由式(8)可以看出D(TRi,TRj)的取值在[0,1]，0表示兩條軌跡完全不相似，1表示兩條軌跡完全相似。

2.2 時(shí)空相似性度量

僅僅考慮空間距離對(duì)對(duì)象進(jìn)行聚類劃分是不夠的，時(shí)間是影響聚類結(jié)果的另一個(gè)因素。如一個(gè)區(qū)域的聚集程度在上午和晚上肯定是不同的，其反映的真實(shí)語(yǔ)義也是不同的。因此，需要利用時(shí)間屬性來對(duì)聚類結(jié)果進(jìn)行過濾。

對(duì)于軌跡段模型，時(shí)間相似性度量計(jì)算公式與式(8)一致，差別在于識(shí)別兩個(gè)軌跡段的重合依據(jù)是時(shí)間段。

兩條軌跡的時(shí)空相似性度量可以表示為

ST(TRi,TRj)=D(TRi,TRj)×T(TRi,TRj)

(9)

式中，ST(TRi,TRj)的取值在[0,1]，0表示完全不相似，1表示完全相似。

3 移動(dòng)軌跡聚類算法

聚類是一種非監(jiān)督式學(xué)習(xí)方法，基于相似性將對(duì)象聚集成不同的類簇或子集，使同一個(gè)類簇中的對(duì)象都具有相似的屬性[20]?？梢酝ㄟ^聚類算法來識(shí)別用戶感興趣的地點(diǎn)和區(qū)域、發(fā)現(xiàn)異常事件、挖掘軌跡中的序列特征等[21]。

根據(jù)軌跡數(shù)據(jù)模型的不同，選擇相應(yīng)相似度衡量標(biāo)準(zhǔn)，進(jìn)而選用合適的聚類方法。對(duì)于軌跡點(diǎn)模型，以距離函數(shù)作為相似度衡量標(biāo)準(zhǔn)，聚類思想與傳統(tǒng)的聚類方法相同。軌跡段模型要以整條軌跡的時(shí)空相似性度量標(biāo)準(zhǔn)來進(jìn)行聚類分析，具體的聚類方法要與傳統(tǒng)的方法有所不同。

3.1 傳統(tǒng)的聚類方法

常見的有4種方法：劃分方法、層次方法、基于密度的方法和基于網(wǎng)絡(luò)的方法[22]。

3.1.1 劃分方法

劃分方法是將對(duì)象集合劃分成k份，每一個(gè)劃分表示一個(gè)聚類[23]。一般的，以所得到的聚類使得客觀劃分標(biāo)準(zhǔn)(即相似函數(shù)，如幾何距離等)最優(yōu)化來達(dá)到較好的劃分效果，使結(jié)果滿足：①每個(gè)聚類簇至少包含一個(gè)數(shù)據(jù)對(duì)象(不能有空的簇)；②每個(gè)數(shù)據(jù)對(duì)象只能屬于一個(gè)聚類簇(任意兩個(gè)聚類簇交集為空)；③使準(zhǔn)則函數(shù)(方差之和)達(dá)到最小值(式(5))。衡量劃分結(jié)果的準(zhǔn)則為：盡可能地使同一類簇(劃分)之間的數(shù)據(jù)差異最小，不同類簇(劃分)之間的數(shù)據(jù)差異最大。

(10)

式中，k表示聚類簇的個(gè)數(shù)；q表示聚類簇Ci中的所包含的數(shù)據(jù)對(duì)象；mi表示聚類簇Ci的中心點(diǎn)(均值)。

常用的算法包括K-Means[24]、K-Medoids[25]和EM算法[26]等，這些啟發(fā)式算法適合于發(fā)現(xiàn)中小規(guī)模數(shù)據(jù)集中的球狀簇。Mohamed等提出了一種適用于移動(dòng)對(duì)象軌跡數(shù)據(jù)聚類的新的K-Means算法，該算法根據(jù)移動(dòng)對(duì)象的移動(dòng)方向、加速度和時(shí)間間隔，來確定算法中的聚類數(shù)k值，克服了K-Means算法對(duì)初始值依賴的缺點(diǎn)[27]。Park等在K-Means基礎(chǔ)上進(jìn)行了改進(jìn)，提出了K-Medoids算法，該算法用各聚類的中心點(diǎn)作為參考點(diǎn)，克服了K-Means算法對(duì)異常值敏感的缺陷[28]。何彬彬等考慮空間聚類的隨機(jī)性和不確定性，基于EM算法和空間對(duì)象的Delaunay三角網(wǎng)的鄰近關(guān)系，提出了不確定性的空間聚類算法[29]。

3.1.2 層次方法

層次方法是將數(shù)據(jù)以樹的形式分成若干組，表現(xiàn)形式有兩種：一種是自下而上凝聚層次的聚類方法(AGNES)，另一種是自頂而下分解層次的聚類方法(DIANA)[30]，如圖2所示。層次聚類算法能產(chǎn)生高質(zhì)量的聚類，但存在計(jì)算和存儲(chǔ)需求大，且缺乏全局目標(biāo)函數(shù)等缺點(diǎn)。層次聚類方法的主要代表算法有BIRCH[31]、CURE[32]和ROCK[33]等。Tu等提出了一種基于BIRCH算法的在線分隔時(shí)間序列數(shù)據(jù)的方法，該方法很容易發(fā)現(xiàn)時(shí)間序列模式的變化，時(shí)間復(fù)雜度也較低，能夠取得更好的分割效果[34]。Shao等提出了一種基于改進(jìn)的CURE算法的大規(guī)模網(wǎng)絡(luò)文本數(shù)據(jù)聚類算法，CURE算法在大數(shù)據(jù)集中有較好的伸縮性，因此在大型數(shù)據(jù)挖掘中應(yīng)用廣泛[35]。

圖2 凝聚和分解層次聚類方法示意圖

3.1.3 基于密度的方法

基于密度聚類的思想主要是：對(duì)于樣本中的每個(gè)數(shù)據(jù)點(diǎn)，在一個(gè)給定范圍的區(qū)域(ε)中至少包含某個(gè)數(shù)量(MinPs)的點(diǎn)[36]。與基于層次聚類和劃分聚類的凸形聚類簇不同，該算法可以發(fā)現(xiàn)任意形狀的聚類簇，而且還可以過濾“噪聲”孤立點(diǎn)?；诿芏染垲惖姆椒ㄖ饕蠨BSCAN算法[37]和OPTICS算法[38]。DBSCAN算法在進(jìn)行聚類時(shí)需要設(shè)置初始參數(shù)ε和MinPs，為了解決這一問題，Ankerst等提出了OPTICS算法，它是一個(gè)自動(dòng)和交互式的聚類方法，該算法不產(chǎn)生明確的數(shù)據(jù)聚類，而是創(chuàng)建一個(gè)基于密度的聚類結(jié)構(gòu)的數(shù)據(jù)庫(kù)，其中包含了很多滿足需求的簇序列[40]。Schoier等提出了一種改進(jìn)的DBSCAN算法，該算法以Lagrange-Chebychev度量作為相似度指標(biāo)，來發(fā)現(xiàn)較大空間數(shù)據(jù)集的單元簇，對(duì)于高維較大空間數(shù)據(jù)集的執(zhí)行效率也較高[39]。Huang等提出了一種基于網(wǎng)格和基于密度的混合聚類算法GRPDBSCAN，該算法可以有效處理噪聲點(diǎn)，運(yùn)行效率比傳統(tǒng)基于密度的聚類算法要高，并且可以自動(dòng)地生成ε和MinPs兩個(gè)參數(shù)[40]。

3.1.4 基于網(wǎng)格的方法

基于網(wǎng)格的方法把對(duì)象空間劃分為有限數(shù)量的單元，從而形成一個(gè)網(wǎng)絡(luò)布局，所有的聚類操作都在量化的空間結(jié)構(gòu)上進(jìn)行[41-42]。該方法的優(yōu)點(diǎn)在于處理速度比較快，而且它的處理時(shí)間獨(dú)立于數(shù)據(jù)對(duì)象的數(shù)量，只和量化空間中每一維的單元數(shù)量有關(guān)?；诰W(wǎng)格的聚類方法的一個(gè)難點(diǎn)在于網(wǎng)格大小的選取，Edla等通過使用類簇的邊界來尋找最佳網(wǎng)格粒度的大小[40]?；诰W(wǎng)格聚類的算法有STING和CLIQUE等。STING算法是一種基于網(wǎng)格的多分辨率聚類技術(shù)，該算法有利于并行化處理，處理效率很高[43]。CLIQUE算法是基于網(wǎng)絡(luò)和基于密度聚類方法的結(jié)合，適用于高維數(shù)據(jù)的聚類[44]。

3.1.5 其他聚類方法

鄧敏等為了改善傳統(tǒng)聚類算法對(duì)輸入?yún)?shù)的依賴，提出了一種基于場(chǎng)論的空間聚類方法(FTSC)，該算法通過使用Delaunay三角網(wǎng)來表示實(shí)體間的鄰近程度，因此算法不涉及輸入?yún)?shù)的設(shè)置，并且可以發(fā)現(xiàn)任意形狀的簇，具有較強(qiáng)的魯棒性[45]。Izakian等提出了一種自動(dòng)化模糊聚類粒子群優(yōu)化技術(shù)來發(fā)現(xiàn)移動(dòng)軌跡數(shù)據(jù)的結(jié)構(gòu)特征，粒子群優(yōu)化方法主要用來找到最優(yōu)聚類簇?cái)?shù)量及最佳聚類中心，從而提高算法的性能[46]。Li等基于層次聚類的思想提出了一種移動(dòng)微聚類算法(moving micro-clustering，MMC)，并應(yīng)用在移動(dòng)軌跡數(shù)據(jù)的聚類中[47]。

表1給出了基于幾何聚類的幾種傳統(tǒng)算法各自的優(yōu)缺點(diǎn)。

表1 幾何聚類算法及其優(yōu)缺點(diǎn)

3.2 軌跡段模型的聚類方法

基于道路網(wǎng)絡(luò)空間的聚類，即道路約束下的聚類，屬于障礙空間下的聚類[49]。該類聚類方法適用于受限于道路網(wǎng)絡(luò)的連續(xù)型軌跡數(shù)據(jù)，如車輛軌跡數(shù)據(jù)等。Liu等提出了一種在道路網(wǎng)絡(luò)約束條件下的聚類對(duì)象模型，給出了約束聚類算法，并驗(yàn)證了算法的效率[50]。廖律超等結(jié)合移動(dòng)對(duì)象的方向信息提出了一種有向密度的快速聚類方法，來提取城市復(fù)雜路網(wǎng)的結(jié)構(gòu)信息[51]。實(shí)際上，該類聚類方法是基于幾何空間聚類思想的擴(kuò)展和細(xì)化，它更側(cè)重于通過交通流及流密度來反映移動(dòng)對(duì)象的特性?；诘缆肪W(wǎng)絡(luò)空間聚類，主要在于動(dòng)態(tài)微觀現(xiàn)象的發(fā)現(xiàn)，以及城市細(xì)粒度現(xiàn)象的發(fā)現(xiàn)。

為了得到移動(dòng)對(duì)象在某一聚集的時(shí)間段內(nèi)高流量、強(qiáng)連續(xù)的運(yùn)動(dòng)軌跡，通常采用軌跡段模型。軌跡段模型聚類以時(shí)空相似性來衡量?jī)蓷l軌跡段是否相似，需要考慮移動(dòng)對(duì)象的速度、方向和位置[52]。軌跡段的聚類可以分為兩類：移動(dòng)對(duì)象的軌跡段聚類和道路路段劃分聚類。

3.2.1 移動(dòng)對(duì)象的軌跡段聚類

馬林兵等將時(shí)空軌跡數(shù)據(jù)進(jìn)行離散化處理，利用CLIQUE算法對(duì)離散化后的軌跡段進(jìn)行聚類分析[53]。Lee等提出了一種新的軌跡聚類的劃分-組合(partition-and-group)框架，通過把軌跡劃分成軌跡片段的集合，再把軌跡片段聚集到簇中，基于這種劃分組合框架提出了一個(gè)軌跡聚類的算法TRACLUS[54]，如圖3所示。

圖3 軌跡段聚類劃分-組合框架

3.2.2 道路路段劃分聚類

道路路段劃分聚類的主要思想：①道路交叉口被看作初始劃分點(diǎn)，將道路劃分成道路片段；②對(duì)應(yīng)于每個(gè)道路段的軌跡段可以看作是一個(gè)局部聚類簇；③軌跡段需要在道路交通流連續(xù)的基礎(chǔ)上聚類。Han等提出了一種道路網(wǎng)絡(luò)感知的方法(NEAT)進(jìn)行軌跡數(shù)據(jù)聚類，來發(fā)現(xiàn)一組高密集、高度連續(xù)的移動(dòng)對(duì)象的交通流子軌跡[55]，如圖4所示。

圖4 道路路段劃分聚類框架

4 結(jié) 語(yǔ)

移動(dòng)軌跡數(shù)據(jù)作為社會(huì)感知位置大數(shù)據(jù)的重要表現(xiàn)形式，蘊(yùn)含了人類活動(dòng)的時(shí)空規(guī)律，表征著城市的脈搏和動(dòng)態(tài)。通過對(duì)這些數(shù)據(jù)的挖掘和分析，能及時(shí)有效地發(fā)現(xiàn)人群移動(dòng)規(guī)律、探測(cè)城市熱點(diǎn)區(qū)域、感知實(shí)時(shí)交通狀態(tài)、挖掘城市功能分區(qū)等，能真實(shí)反映城市的韻律，是城市計(jì)算的主要數(shù)據(jù)源，為解決城市問題提供了科學(xué)的數(shù)據(jù)支撐。聚類是對(duì)這些數(shù)據(jù)進(jìn)行挖掘和分析的重要方法，也是為進(jìn)一步研究進(jìn)行數(shù)據(jù)處理的基礎(chǔ)環(huán)節(jié)。本文根據(jù)不同的軌跡模型定義不同的相似度衡量標(biāo)準(zhǔn)，進(jìn)一步對(duì)兩類軌跡模型的聚類方法進(jìn)行了詳細(xì)的描述，得出聚類方法的關(guān)鍵在于相似度衡量標(biāo)準(zhǔn)的確定。

移動(dòng)軌跡數(shù)據(jù)聚類方法盡管已經(jīng)有廣泛的研究，但仍然存在一些挑戰(zhàn)，具體體現(xiàn)在以下幾個(gè)方面：①對(duì)于不同結(jié)構(gòu)的數(shù)據(jù)，如何準(zhǔn)確判斷數(shù)據(jù)之間的相似性衡量指標(biāo)，以使聚類方法適合于廣泛存在的異構(gòu)數(shù)據(jù)；②對(duì)于需要設(shè)置初始參數(shù)的聚類算法，怎樣才能更準(zhǔn)確地設(shè)置參數(shù)，或?qū)崿F(xiàn)自適應(yīng)的聚類方法；③聚類結(jié)果的有效性評(píng)價(jià)一直是時(shí)空聚類分析中的難點(diǎn)問題，移動(dòng)軌跡數(shù)據(jù)聚類的有效性評(píng)價(jià)需要更加深入，如何使現(xiàn)有的聚類方法適應(yīng)動(dòng)態(tài)軌跡數(shù)據(jù)也需要進(jìn)一步研究。

[1] 牟乃夏，張恒才，陳潔，等.軌跡數(shù)據(jù)挖掘城市應(yīng)用研究綜述[J].地球信息科學(xué)學(xué)報(bào)，2015,17(10):1136-1142.

[2] 李石堅(jiān)，齊觀德，張王晟.移動(dòng)軌跡數(shù)據(jù)分析與智慧城市[J].中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊，2012,8(5):31-37.

[3] 李清泉，李德仁.大數(shù)據(jù)GIS[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2014,39(6):641-644.

[4] 鄭宇.城市計(jì)算概述[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2015,40(1):1-13.

[5] YE Y，ZHENG Y，CHEN Y，et al.Mining Individual Life Pattern Based on Location History[C]∥Tenth International Conference on Mobile Data Management：Systems.Taipei：[s.n.]，2009.

[6] 劉瑜，康朝貴，王法輝.大數(shù)據(jù)驅(qū)動(dòng)的人類移動(dòng)模式和模型研究[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2014,39(6):660-666.

[7] 龔璽，裴韜，孫嘉，等.時(shí)空軌跡聚類方法研究進(jìn)展[J].地理科學(xué)進(jìn)展，2011,30(5):522-534.

[8] 劉瑜，肖昱，高松，等.基于位置感知設(shè)備的人類移動(dòng)研究綜述[J].地理與地理信息科學(xué)，2011,27(4):8-13.

[9] YUAN J，ZHENG Y，XIE X.Discovering Regions of Different Functions in a City Using Human Mobility and POIs[C]∥ACM Sigkdd International Conference on Knowledge Discovery and Data Mining.[S.l.]：ACM,2012.

[10] MOUSAVI S M，HARWOOD A，KARUNASEKERA S，et al.Geometry of Interest (GOI)：Spatio-temporal Destination Extraction and Partitioning in GPS Trajectory Data[J].Journal of Ambient Intelligence and Humanized Computing，2016：1-16.

[11] PANG L X，CHAWLA S，LIU W，et al.On Detection of Emerging Anomalous Traffic Patterns Using GPS Data[J].Data & Knowledge Engineering，2013,87(9):357-373.

[12] 龍瀛，張宇，崔承印.利用公交刷卡數(shù)據(jù)分析北京職住關(guān)系和通勤出行[J].地理學(xué)報(bào)，2012,67(10):1339-1352.

[13] 徐金壘，方志祥，蕭世倫，等.城市海量手機(jī)用戶停留時(shí)空分異分析——以深圳市為例[J].地球信息科學(xué)學(xué)報(bào)，2015,17(2):197-205.

[14] 陳佳，胡波，左小清，等.利用手機(jī)定位數(shù)據(jù)的用戶特征挖掘[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2014,39(6):734-738.

[15] 常曉猛，樂陽(yáng)，李清泉，等.利用位置的虛擬社交網(wǎng)絡(luò)地理骨干網(wǎng)提取[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2014,39(6):706-710.

[16] 李婷，裴韜，袁燁城，等.人類活動(dòng)軌跡的分類、模式和應(yīng)用研究綜述[J].地理科學(xué)進(jìn)展，2014,33(7):938-948.

[17] KOBAYASHI T，SHINAGAWA N，WATANABE Y.Vehicle Mobility Characterization Based on Measurements and Its Application to Cellular Communication Systems (Special Issue on Multimedia Mobile Communication Systems)[J].Ieice Transactions on Communications，1999,82(12):2055-2060.

[18] 許寧，尹凌，胡金星.從大規(guī)模短期規(guī)則采樣的手機(jī)定位數(shù)據(jù)中識(shí)別居民職住地[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2014,39(6):750-756.

[19] WON J I，KIM S W，BAEK J H，et al.Trajectory Clustering in Road Network Environment[J].IEEE Symposium on Computational Intelligence and Data Mining，2009(3)：299-305.

[20] 吳笛，杜云艷，易嘉偉，等.基于密度的軌跡時(shí)空聚類分析[J].地球信息科學(xué)學(xué)報(bào)，2015,17(10):1162-1171.

[21] 宋樂怡.海量出租車軌跡數(shù)據(jù)分析與位置推薦服務(wù)[D].上海：華東師范大學(xué)，2015.

[22] HAN J，KAMBER M.Data Mining：Concepts and Technique[M].[S.l.]：Morgan Kaufmann Publishers Inc.，2006.

[23] 孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學(xué)報(bào)，2008,19(1):48-61.

[24] MACQUEEN J.Some Methods for Classification and Analysis of Multivariate Observations[C]∥Proceedings of Berkeley Symposium on Mathematical Statistics and Probability.[S.l.]：University of California Press，1967.

[25] KAUFMAN L，ROUSSEEUW P J.Finding Groups in Data:An Introduction to Cluster Analysis[M].[S.l.]：John Wiley & Sons,Inc.,2008.

[26] DEMPSTER A，LAIRD N，RUBIN D. Maximum Likelihood Eitimation from Imcomplete Data via EM Algorithm [J].Journal of the Royal Statistical Society：Series B，1977,39:1-38.

[27] MOHAMED O O K，EL-SHARKAWI M E，MOKHTAR H，et al.Mining Moving Objects Trajectories[J].2012.

[28] PARK H S，JUN C H.A Simple and Fast Algorithm for K-medoids Clustering[J].Expert Systems with Applications，2009,36(2):3336-3341.

[29] 何彬彬，方濤，郭達(dá)志.基于不確定性的空間聚類[J].計(jì)算機(jī)科學(xué)，2004,31(11):196-198.

[30] ZHONG C，MIAO D，F(xiàn)RNTI P.Minimum Spanning Tree Based Split-and-merge：A Hierarchical Clustering Method[J].Information Sciences，2011,181(16):3397-3410.

[31] ZHANG T，RAMAKRISHNAN R，LINVY M.BIRCH：An Efficient Data Clustering Method for Very Large Databases[J].ACM Sigmod International Conference on Management of Data，1996，25(2)：103-114.

[32] ROUSSEEUW P J，KAUFMAN L.Finding Groups in Data[J].Series in Probability & Mathematical Statistics，1990,34(1):111-112.

[33] GUHA S，RASTOGI R，SHIM K.ROCK：A Robust Clustering Algorithm for Categorical Attributes[J].Information Systems，1999,25(5):345-366.

[34] TU Y，LIU Y，LI Z.Online Segmentation Algorithm for Time Series Based on BIRCH Clustering Features[C]∥International Conference on Computational Intelligence and Security.Nanning：SCIS，2010.

[35] SHAO X，CHENG W.Improved CURE Algorithm and Application of Clustering for Large-scale Data[C]∥International Symposium on IT in Medicine and Education (ITME).Guangzhou：IEEE,2011.

[36] HINNEBURG A，KEIM D A.An Efficient Approach to Clustering in Large Multimedia Databases with Noise[C]∥Proceedings of the Fourth Data Mining.New York：AAAI Press，1998.

[37] ESTER M，KRIEGEL H P，SANDER J，et al.A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[C]∥Proceeding of the Second International Conference on Knowledge Discovery and Data Mining. Portland：AAAI Press,1996.

[38] ANKERST M,BREUNIG M M,KRIEGEL H,et al.OPTICS：Ordering Points to Identify the Clustering Structure[J].ACM SIGMOD Record,1999,28(2)：49-60.

[39] SCHOIER G.On the MDBSCAN Algorithm in a Spatial Data Mining Context[J].Data Mining Concepts Methodologies Tools & Applications，2013,7974:375-388.

[40] EDLA D R，JANA P K.A Grid Clustering Algorithm Using Cluster Boundaries[J].Information and Communication Technologies，2013，15(3)：254-259.

[41] 周濤，陸惠玲.數(shù)據(jù)挖掘中聚類算法研究進(jìn)展[J].計(jì)算機(jī)工程與應(yīng)用，2012,48(12):100-111.

[42] 趙慧，劉希玉，崔海青.網(wǎng)格聚類算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2010,20(9):83-85.

[43] WANG W，YANG J，MUNTZ R R.STING：A Statistical Information Grid Approach to Spatial Data Mining[C]∥Proceedings of International Conference on Very Large Data Bases.Athens，Greece：Morgan Kaufmann Publishers Inc.,1997.

[44] AGRAWAL R，GEHRKE J，GUNOPULOS D，et al.Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications[J].ACM，1998,27(2):94-105.

[45] 鄧敏，劉啟亮，李光強(qiáng)，等.基于場(chǎng)論的空間聚類算法[J].遙感學(xué)報(bào)，2010,14(4):694-709.

[46] IZAKIAN Z，MESGARI M S，ABRAHAM A.Automated Clustering of Trajectory Data Using a Particle Swarm Optimization[J].Computers，Environment and Urban Systems，2016,55:55-65.

[47] LI Y，HAN J，YANG J.Clustering Moving Objects[C]∥Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Seattle：ACM,2004.

[48] 賀玲，吳玲達(dá)，蔡益朝.數(shù)據(jù)挖掘中的聚類算法綜述[J].計(jì)算機(jī)應(yīng)用研究，2007,24(1):10-13.

[49] TUNG A K H，HOU J，HAN J，et al.Spatial Clustering in the Presence of Obstacles[C]∥2013 IEEE 29th International Conference on Data Engineering.Herdelberg：ICDE，2001:359-367.

[50] LIU W，F(xiàn)ENG J，WANG Z.Constrained Clustering Objects on a Spatial Network[C]∥2009 WRI World Congress on Computer Science and Information Engineering.Los Angeles:IEEE，2009.

[51] 廖律超，蔣新華，鄒復(fù)民，等.浮動(dòng)車軌跡數(shù)據(jù)聚類的有向密度方法[J].地球信息科學(xué)學(xué)報(bào)，2015,17(10):1152-1161.

[52] 王金鳳，邢長(zhǎng)征.基于道路網(wǎng)絡(luò)的移動(dòng)對(duì)象聚類[J].計(jì)算機(jī)工程與應(yīng)用，2016,52(7):74-78.

[53] 馬林兵，李鵬.基于子空間聚類算法的時(shí)空軌跡聚類[J].地理與地理信息科學(xué)，2014,30(4):7-11.

[54] LEE J G，HAN J，WHANG K Y.Trajectory Clustering：A Partition-and-group Framework[C]∥ACM SIGMOD International Conference on Management of Data.Beijing：ACM,2007.

[55] HAN B，LIU L，OMIECINSKI E.NEAT：Road Network Aware Trajectory Clustering[C]∥IEEE International Conference on Distributed Computing Systems.[S.l.]: IEEE,2012.