時(shí)空約束下的熱點(diǎn)路徑空間分布檢測(cè)算法

段 煉，李 峙，胡寶清

（1.武漢大學(xué) 測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢430079；2.廣西師范學(xué)院 北部灣環(huán)境演變與資源利用教育部重點(diǎn)實(shí)驗(yàn)室，廣西 南寧530001；3.廣西師范學(xué)院 資源環(huán)境科學(xué)學(xué)院，廣西南寧530001；4.廣西師范學(xué)院 廣西地表過(guò)程與智能模擬重點(diǎn)實(shí)驗(yàn)室，廣西 南寧530001；5.廣西紅樹林研究中心廣西紅樹林保護(hù)與利用重點(diǎn)實(shí)驗(yàn)室，廣西 北海536000）

0 引 言

時(shí)空軌跡是移動(dòng)對(duì)象隨時(shí)間推移的位置序列。隨著移動(dòng)互聯(lián)網(wǎng)、定位系統(tǒng)等技術(shù)的快速發(fā)展，在交通、物流等應(yīng)用領(lǐng)域，人們通過(guò)智能移動(dòng)終端采集了大量時(shí)空軌跡數(shù)據(jù)。熱點(diǎn)路徑通常是指多個(gè)移動(dòng)對(duì)象頻繁經(jīng)過(guò)的路徑，能反映出路徑上移動(dòng)對(duì)象的個(gè)體或群體運(yùn)動(dòng)模式［1］，可輔助城市規(guī)劃、交通管理、用戶調(diào)查等領(lǐng)域的決策分析［2］。從時(shí)空軌跡數(shù)據(jù)（Trajectory）中獲取熱點(diǎn)路徑的通用方法是以聚類方式，通過(guò)對(duì)軌跡內(nèi)部運(yùn)動(dòng)模式和特征信息的分析，確定軌跡間的相似量度，然后將相似程度較高的軌跡歸為一類［3］，每一類反映了移動(dòng)對(duì)象的某種運(yùn)動(dòng)和行為模式，從而發(fā)現(xiàn)時(shí)空軌跡數(shù)據(jù)中的語(yǔ)義相似性與異常特征，進(jìn)而探測(cè)到城市熱點(diǎn)道路的時(shí)空分布。

目前，許多著名的聚類算法如K－MEANS、BIRCH，DBSCAN、OPTICS、STING 等［4］被用于軌跡聚類。KREVELD 等［5］首次將時(shí)間依賴關(guān)系引入到軌跡分析中。HAN 等［6］對(duì)軌跡分段，并將速度等要素引入軌跡段間的相似度計(jì)算。LEE［4］等采用Hausdorff距離，將軌跡劃分成若干t－partition進(jìn)行聚類。Chen等［7］提出了路網(wǎng)空間下基于密度的軌跡聚類方法。Kim 等［8］基于重疊路段長(zhǎng)度的相似度進(jìn)行軌跡聚類。Xia等［9］提出了在路網(wǎng)約束下綜合考慮時(shí)間和空間約束的軌跡相似性度量的軌跡聚類方法。然而，這些方法大多是基于軌跡的全局空間信息進(jìn)行聚類，沒有考慮軌跡的局部時(shí)空特征。已有的軌跡聚類方法也考慮了軌跡的時(shí)間特征，但對(duì)軌跡運(yùn)動(dòng)語(yǔ)義特征利用不足，而軌跡運(yùn)動(dòng)語(yǔ)義特征如方向、轉(zhuǎn)角、速度等更能體現(xiàn)路徑內(nèi)在、外在的異同。此外，一些軌跡聚類方法盡管考慮是速度等運(yùn)動(dòng)語(yǔ)義特征和軌跡的局部特征，但卻忽略了時(shí)間要素。

據(jù)此，本文提出了基于時(shí)空軌跡聚類的熱點(diǎn)路徑分布檢測(cè)方法。將該模型計(jì)算軌跡斷點(diǎn)，依據(jù)斷點(diǎn)將軌跡劃分成若干軌跡段，基于軌跡段之間的位置、時(shí)間、速度和方向相似度對(duì)軌跡段聚類。對(duì)聚類結(jié)果中的非顯著簇進(jìn)行適當(dāng)處理，或者將其并入其它鄰接的顯著簇，或者作為噪音刪除。將各顯著簇內(nèi)鄰近的斷點(diǎn)融合成停留斑點(diǎn)，停留斑點(diǎn)所承載軌跡段數(shù)量得到斑點(diǎn)熱度，基于DENCLUE（DENsity－based CLUstEring）算法［10］獲取熱點(diǎn)路徑的空間分布。實(shí)驗(yàn)結(jié)果表明，本文的方法可對(duì)大規(guī)模軌跡進(jìn)行高效聚類，并有效發(fā)現(xiàn)城市熱點(diǎn)路徑分布。

1 軌跡時(shí)空聚類

1.1 基本概念

定義1 軌跡：三維空間中的有序點(diǎn)集稱為軌跡。軌跡TRi定義：TRi＝｛p1，p2，…，pk｝，其中pk＝｛xk，yk，tk｝，他們分別代表該點(diǎn)的二維空間坐標(biāo)和采用時(shí)間。不同軌跡長(zhǎng)度可能不一樣。

定義2 軌跡段：為TRi內(nèi)連續(xù)的部分三維點(diǎn)集，如：SubTrajectorys＝｛p1，…，pk｝（1≤s≤k），k 為該軌跡段所屬軌跡的采樣點(diǎn)總數(shù)。

定義3 Hausdorff距離：是描述兩組點(diǎn)集之間相似程度的一種度量，也是集合之間距離的一種定義形式。相關(guān)定義請(qǐng)參見文獻(xiàn)［11］。

定義4 軌跡段速度：軌跡段上移動(dòng)對(duì)象在每個(gè)采樣點(diǎn)位置瞬時(shí)速度的集合。對(duì)描述某段時(shí)間內(nèi)該軌跡所在路徑的通達(dá)程度具有十分重要的意義。由于實(shí)驗(yàn)數(shù)據(jù)集缺失采樣點(diǎn)的速度，因此，通過(guò)如下公式得到每個(gè)采樣點(diǎn)速度

式中：p－——p 點(diǎn)之前的相鄰采樣點(diǎn)，p＋——p點(diǎn)之后的相鄰采樣點(diǎn)，tp－、tp＋——p－、p＋的采樣時(shí)間，該計(jì)算公式利用移動(dòng)對(duì)象在3個(gè)連續(xù)采用點(diǎn)的平均速度作為當(dāng)前點(diǎn)的速度。軌跡段的速度通過(guò)該軌跡段中的最小速度、最大速度和平均速度來(lái)衡量

式中：ωm＋ωa≤1，vmin——軌跡段中速度最低值，vmax——軌跡段中速度最高值，i、j——該軌跡段采樣點(diǎn)的下標(biāo)。對(duì)于一條軌跡段多個(gè)采樣點(diǎn)，其速度都是不相同的，因此，這里要綜合考慮速度的各種因素，以將具有相似速度結(jié)構(gòu)的軌跡段聚集在一塊。

定義5 軌跡段方向：軌跡段始末采樣點(diǎn)之間形成的角度。盡管道路上兩條軌跡段在每個(gè)采樣位置的移動(dòng)方向差異可能較大，但在道路網(wǎng)的約束下往往這些采樣點(diǎn)的總體移動(dòng)方向是相同的，如果采用已有軌跡聚類方法比較每個(gè)采樣點(diǎn)之間的角度差異，在軌跡聚類算法執(zhí)行過(guò)程中，不僅會(huì)因?yàn)楸容^兩個(gè)軌跡段間每個(gè)采樣點(diǎn)在不同時(shí)刻、不同位置的角度變化而影響算法效率，還會(huì)有可能將總體上位移方向一致、行為目的一致的軌跡段劃分到不同聚類中。因此，軌跡段的總體移動(dòng)方向能表達(dá)他們之間主要方向差別。采用如下公式表達(dá)軌跡段的運(yùn)動(dòng)方向角

式中：（xs，ys）軌跡段起點(diǎn)，（xe，ye）為軌跡段終點(diǎn)。

定義6 ξ鄰域：設(shè)軌跡段為L(zhǎng)i的ξ鄰域?yàn)镹ξ（Li）：Nξ（Li）＝｛Lj∈D｜d（Li，Lj）≤ξ｝。其中，D 為所有軌跡段數(shù)據(jù)集合，d（Lj，Lj）為軌跡段，Lj和Lj在時(shí)間、位置、速度、方向上的相似度。鄰域用以在軌跡密度聚類中，判斷每個(gè)軌跡段的當(dāng)前空間密度，進(jìn)而將空間密度高于閾值的軌跡段聚為同一簇。

1.2 軌跡分割

城市中，浮動(dòng)車輛的行動(dòng)受道路網(wǎng)約束，其軌跡空間結(jié)構(gòu)不會(huì)類似動(dòng)物路徑或風(fēng)暴路徑那樣在角度和速度上經(jīng)常出現(xiàn)劇烈變化。因此已有依據(jù)每個(gè)采樣點(diǎn)的角度變化進(jìn)行軌跡分割的方法不適合城市空間中的軌跡段劃分。而受到交叉路口紅燈、交通擁塞、工作、休閑和生活場(chǎng)所的影響，城市中的移動(dòng)對(duì)象常常在這些位置停留，這些停留位置更全面地表達(dá)移動(dòng)對(duì)象的運(yùn)動(dòng)和行為語(yǔ)義狀態(tài)，具有相同停留位置而不是相同較大拐角的軌跡段，能反映移動(dòng)對(duì)象在目的和行為上的相似性。因此，通過(guò)采樣點(diǎn)在某個(gè)時(shí)間段內(nèi)的速度變化來(lái)分割軌跡，而往往這些位置有較明顯的速度差異。

定義7 斷點(diǎn)：假設(shè)存在一軌跡段，位于該軌跡段上的任何兩點(diǎn)之間的距離不超過(guò)閾值ε，并且這段子軌跡的采樣點(diǎn)數(shù)s大于閾值Ε，則我們將這段子軌跡中的第［s／2］個(gè)點(diǎn)設(shè)置為斷點(diǎn)。本文的軌跡是每5s記錄一次采樣點(diǎn)，因此ε設(shè)置為10，Ε設(shè)置為3，即只要車輛在超過(guò)15s的時(shí)間內(nèi)行駛不超過(guò)10m，我們就認(rèn)為存在斷點(diǎn)。

為保證軌跡的完整性，將位于該段子軌跡上其余的點(diǎn)刪除，這時(shí)，如果一條軌跡上有t個(gè)斷點(diǎn)，則該軌跡被分割為t＋1個(gè)軌跡段。

1.3 軌跡段相似性比較

軌跡段之間的相似性通過(guò)軌跡段之間的差異度獲取，該計(jì)算包括4方面：空間差異度、時(shí)間差異度、方向差異度和速度差異度。其中，空間差異度與時(shí)間差異度采用Hausdorff距離計(jì)算得到，方向差異度和速度差異度直接采用屬性差值絕對(duì)值表示即可。將他們結(jié)合得到一個(gè)統(tǒng)一的表達(dá)軌跡段相似性公式

式中：spatialDis、tempoDis、OrientDis和velocityDis——軌跡段之間的空間差異度、時(shí)間差異度、方向差異度和速度差異度。軌跡段相似性公式為

式中：tanh（subDis）——三角函數(shù)歸一化公式。

1.4 基于DBSCAN 的軌跡聚類算法

對(duì)軌跡進(jìn)行分割后，再利用DBSCAN 密度算法，采用式 （5），進(jìn)行軌跡段聚類。與DBSCAN 不同，這里還需考慮軌跡段與原始軌跡的關(guān)系。設(shè)聚類簇C 中包含的軌跡數(shù)目為簇基數(shù)ncb，簇基數(shù)ncb與該聚類中軌跡段數(shù)目nc之比為簇顯著度ncs，給定閾值τ和γ，我們進(jìn)行如下定義：

定義8 顯著簇：Csig＝｛C｜C∈O ∩ncb＞τ ∩ncs＞γ｝，其中，O 為第一次聚類的結(jié)果集。即簇基數(shù)nb高于τ且簇顯著度ns高于γ聚類稱為顯著簇。

定義9 非顯著簇：Cunsig＝｛C｜C∈O ∩COsig｝，其中，Osig為顯著簇集合。即顯著簇之外的聚類都為非顯著簇。

一旦某聚類中簇基數(shù)少于τ，則說(shuō)明該聚類中抑或包含了較多屬于同一條軌跡的軌跡段，抑或僅僅包含了較少的移動(dòng)對(duì)象，同樣，如果某聚類中的顯著度小于γ，則說(shuō)明該聚類中的軌跡數(shù)量相對(duì)于軌跡段來(lái)說(shuō)過(guò)少，這兩者均無(wú)法反映全局上的該聚類所覆蓋路徑的重要性。因此，將第一次聚類中非顯著簇刪除，同時(shí)將其包含的軌跡段歸并到離其最近距離小于閾值μ且包含同一條軌跡的聚類中。

顯著簇判斷和軌跡段歸并算法偽代碼如下：

（1）從聚類集合O 中獲取下一個(gè)簇C；

（2）設(shè)簇C 的簇基數(shù)ncb，簇顯著度ncs，如果nc＞τ，并且ncs＞γ，則將C 放入顯著簇集合Osig，直至遍歷完O，將所有沒有放入Osig的簇放入Ounsig；

（3）從Ounsig取出下一個(gè)非顯著簇C’，從C’依次取出各軌跡段，判斷各軌跡段距離其最近且包含有相同軌跡標(biāo)示的顯著簇，如果軌跡段距離其最近顯著簇的距離大于μ，則將其作為噪音拋棄，否則將其加入該最近顯著簇；

（4）重復(fù)（3）直至遍歷完所有的非顯著簇。

該方法能較好地在全局空間上體現(xiàn)重要聚類的影響范圍，而傳統(tǒng)軌跡密度聚類方法無(wú)法做到這一點(diǎn)。

2 熱點(diǎn)路徑分布探測(cè)

熱點(diǎn)路徑分布探測(cè)的目的是發(fā)現(xiàn)那些承載大量浮動(dòng)車輛運(yùn)行的城市道路分布區(qū)域。常規(guī)熱點(diǎn)道路檢測(cè)往往是直接依據(jù)道路上軌跡數(shù)量或斷點(diǎn)的數(shù)量判斷路徑上的車流集中程度。然而，一些道路上盡管車流量大，但造成車輛停留的位置少，表明該道路上的商業(yè)網(wǎng)點(diǎn)或提供社會(huì)服務(wù)的區(qū)域少，如城市外環(huán)道路；一些道路上的軌跡斷點(diǎn)數(shù)量較多，但其主要分散在道路兩端，如通往旅游景區(qū)的道路，因此，常規(guī)方法無(wú)法準(zhǔn)確反映城市熱點(diǎn)路徑的分布。本文基本思路是在顯著簇中將鄰近斷點(diǎn)融合成停留斑點(diǎn)，基于停留斑點(diǎn)所承載軌跡段數(shù)量得到斑點(diǎn)熱度，最后利用點(diǎn)值密度聚類獲取熱點(diǎn)路徑的空間分布。

定義10 停留斑點(diǎn)：顯著簇中各軌跡段始末點(diǎn)（也就是斷點(diǎn)）構(gòu)成的、最小外接圓半徑小于閾值α區(qū)域。

停留斑點(diǎn)反映了道路中某種社會(huì)功能集聚或某種交通路況發(fā)生的區(qū)域，從而也反映了這一區(qū)域附近道路的重要程度。而車流量的大小往往與道路斷點(diǎn)集中處的車流集中程度緊密相關(guān)，如道路上的擁塞往往是道路始末點(diǎn)的十字路口或某個(gè)商業(yè)區(qū)的車流停滯造成的。因此，這些熱點(diǎn)停留斑的發(fā)現(xiàn)能集中體現(xiàn)移動(dòng)對(duì)象運(yùn)動(dòng)模式發(fā)生根源，其與相應(yīng)的軌跡聚類結(jié)果相結(jié)合既能發(fā)現(xiàn)熱點(diǎn)路徑，又能有助于發(fā)現(xiàn)熱點(diǎn)路徑的產(chǎn)生原因。

停留斑點(diǎn)的獲取也就是斷點(diǎn)的融合過(guò)程。計(jì)算要求停留斑點(diǎn)盡可能覆蓋更多的斷點(diǎn)，不允許存在單個(gè)斷點(diǎn)作為停留斑點(diǎn)。其獲取算法如下：

（1）從聚類集合中獲取下一個(gè)顯著簇C，將C 中所有軌跡段的始末點(diǎn)抽取為斷點(diǎn)集D；

（2）隨機(jī)從D 中取出一個(gè)斷點(diǎn)p，將其它斷點(diǎn)依次與p 合并，構(gòu)成一個(gè)不斷擴(kuò)大的點(diǎn)集A，如果新加入的點(diǎn)p｀造成A 的最小外接圓半徑大于閾值α，則從A 中刪除該點(diǎn)p｀；

（3）當(dāng)D 中所有的點(diǎn)都已遍歷完，如果A 包含的斷點(diǎn)數(shù)量高于閾值ρ，則A 為停留斑點(diǎn)；

（4）重復(fù)（2）直至生成完C 中所有的候選停留斑點(diǎn)；

（5）重復(fù)（1）直至遍歷完所有的顯著簇。

以上停留斑點(diǎn)的計(jì)算結(jié)果會(huì)因?yàn)閿帱c(diǎn)的計(jì)算順序而不同，即某個(gè)斷點(diǎn)會(huì)因?yàn)楸蝗〕鲰樞虻牟煌粍澐值讲煌Ａ舭唿c(diǎn)中。實(shí)驗(yàn)表明，從總體上看，無(wú)論斷點(diǎn)的計(jì)算順序如何變化，最終得到的停留斑點(diǎn)變化極為細(xì)微，不會(huì)造成所探測(cè)到的熱點(diǎn)路徑有明顯變化。停留斑點(diǎn)中，當(dāng)較多斷點(diǎn)屬于同一軌跡時(shí)，則說(shuō)明該區(qū)域上所經(jīng)過(guò)的移動(dòng)對(duì)象較少，因此，如果該停留斑點(diǎn)包含的斷點(diǎn)很大，但實(shí)際上熱點(diǎn)較低。為了體現(xiàn)這種現(xiàn)象，設(shè)hspot為停留斑點(diǎn)熱度，nsubtraj為停留斑點(diǎn)包含的軌跡段數(shù)量，ntra為停留斑點(diǎn)包含軌跡數(shù)量，β為系數(shù)，實(shí)驗(yàn)中β＝ntra／2，采用如下公式表達(dá)停留斑熱度

由此，我們獲取到了各顯著簇中所有停留斑點(diǎn)的熱點(diǎn)。依據(jù)停留斑點(diǎn)熱點(diǎn)的空間分布利用DENCLUE 算法獲得停留斑點(diǎn)的熱點(diǎn)分布。熱點(diǎn)路徑分布檢測(cè)算法見表1。

軌跡聚類算法的ExpandCluster（）方法中涉及的概念如核心軌跡段、直接密度可達(dá)、密度可達(dá)、密度相連、密度相連集合的定義與DBSCAN 中定義相同。我們采用空間四叉樹存儲(chǔ)軌跡段，以提高鄰接軌跡段、最近鄰接顯著簇和停留斑點(diǎn)融合的計(jì)算。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)與運(yùn)行環(huán)境

為了驗(yàn)證本文提出的聚類算法，開發(fā)了軌跡聚類分析系統(tǒng)。軌跡數(shù)據(jù)存儲(chǔ)在MySQL 數(shù)據(jù)庫(kù)中。實(shí)驗(yàn)的軟硬件環(huán)境包括：64 位的Windows 7，Visual Studio 2010，CPU（CORE 2DUO 2.8GH），內(nèi)存8GB。采用武漢市武昌區(qū)2010年2 月至4 月的出租車數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)，共10835條軌跡，每條軌跡的采樣點(diǎn)包括了經(jīng)緯度坐標(biāo)、采樣時(shí)間。通過(guò)計(jì)算斷點(diǎn)，最終得到52934個(gè)軌跡段。

3.2 實(shí)驗(yàn)分析

3.2.1 不同聚類算法效果對(duì)比

本文提出的軌跡時(shí)空聚類算法TTC（trajectory temporal－spaito clustering）與DBSCAN進(jìn)行比較。TTC 和DBSCA 的參數(shù)調(diào)優(yōu)以最大程度體現(xiàn)城市主干要道、最低程度減少非主干道的出現(xiàn)為準(zhǔn)，其中，DBSCAN 方法基于速度和方向進(jìn)行軌跡分割，依據(jù)軌跡段的空間位置計(jì)算軌跡段相似性。

圖1中，TTC能表現(xiàn)出較明顯的主干路徑分布，發(fā)現(xiàn)的聚類更能體現(xiàn)城市交通特征。而圖2中的DBSCAN 聚類空間形態(tài)表現(xiàn)出了大量旁支路徑，不能明顯表現(xiàn)出主干要道的分布。從表2 中可以看出，TTC 算法具有較高的聚類速度，聚類數(shù)量適中（共58個(gè)聚類），而DBSCAN 的聚類效率較低，聚類個(gè)數(shù)過(guò)多（208個(gè)聚類）。以上結(jié)果主要有以下原因：①TTC以方向和速度特征為依據(jù)，容易區(qū)分開那些路徑相同但移動(dòng)屬性不同隱蔽軌跡群；②TTC 通過(guò)過(guò)濾掉大量非顯著簇，表現(xiàn)了總體上軌跡運(yùn)動(dòng)模式和趨勢(shì)；③TTC采用了空間四叉樹存儲(chǔ)軌跡段，提高了鄰接軌跡段的搜索效率。

表2 聚類效果比較

圖1 TTC聚類效果 （58個(gè)聚類）

圖2 DBSCAN 聚類效果 （204個(gè)聚類）

3.2.2 熱點(diǎn)路徑空間分布

圖3顯示了停留斑點(diǎn)在不同城市要道上的分布密度，其中，每個(gè)點(diǎn)代表一個(gè)停留斑點(diǎn)。圖中可發(fā)現(xiàn)，盡管顯著簇所覆蓋道路的軌跡密度高，但在不同顯著簇上的停留斑點(diǎn)密度有較大不同，長(zhǎng)江附近顯著簇的停留斑點(diǎn)密度明顯高于其它顯著簇。

圖4 帶有熱度信息的停留斑點(diǎn)分布

圖4顯示了帶有熱度信息的停留斑點(diǎn)空間分布，表現(xiàn)了對(duì)停留斑點(diǎn)進(jìn)行熱點(diǎn)聚類后的效果，其中，顏色越黑，代表該位置的熱度越大，反之，熱度小。圖中可發(fā)現(xiàn)高熱度的停留斑點(diǎn)具有集聚效應(yīng)，在較靠近長(zhǎng)江一橋的區(qū)域中形成了較為明顯的高熱度聚類，即隨著與長(zhǎng)江距離的接近，區(qū)域的路徑熱點(diǎn)逐漸增大，在沿江區(qū)域的熱點(diǎn)達(dá)到頂峰；而越趨向城市外圍，區(qū)域的路徑熱度越低。圖中清晰表達(dá)了城市熱點(diǎn)路徑主要集中在武昌沿江地區(qū)，這與實(shí)際中該區(qū)域分布著眾多商業(yè)網(wǎng)點(diǎn)，同時(shí)也是武昌和漢口、漢陽(yáng)交匯處相吻合。在一些主干道上聚集著大量停留斑點(diǎn)的分布，這是因?yàn)橛捎诩t綠燈造成車輛停留較久，從而形成了大量斷點(diǎn)。

圖5通過(guò)熱點(diǎn)密度聚類，得到了熱點(diǎn)路徑的空間分布，其中，黑色表示該熱度聚集區(qū)，淺色表示地?zé)岫染奂瘏^(qū)。圖5中可清晰表現(xiàn)車流在城市中的最為主要的停留區(qū)域分布在靠近長(zhǎng)江的區(qū)域，不僅說(shuō)明這些道路上車流集聚，也說(shuō)明了這些道路兩旁覆蓋了大量社會(huì)服務(wù)設(shè)施。此外，路徑熱度沿著城市主干道隨著遠(yuǎn)離長(zhǎng)江而衰減，從側(cè)面體現(xiàn)了城市主要功能區(qū)靠近長(zhǎng)江。圖5中顏色較淺區(qū)域同樣也是車流集中的區(qū)域，然而這些區(qū)域的城市功能相對(duì)于長(zhǎng)江沿岸區(qū)域來(lái)說(shuō)較弱，因此停留斑點(diǎn)較少?？梢姡疚奶岢龅臒狳c(diǎn)路徑分布方法能較為準(zhǔn)確的反映路徑熱點(diǎn)的分布和城市功能集聚分異。

圖5 停留斑點(diǎn)熱點(diǎn)密度聚類

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

熱點(diǎn)路徑探測(cè)在交通、物流等領(lǐng)域有重要應(yīng)用價(jià)值。本文提出了基于軌跡時(shí)空聚類的熱點(diǎn)路徑分布探測(cè)方法。通過(guò)斷點(diǎn)對(duì)軌跡分割，引入速度和方向作為軌跡段相似性計(jì)算的特征，通過(guò)Hausdorff距離度量軌跡段之間在時(shí)空上的差異，提取出具有全局顯著意義的軌跡簇。之后依據(jù)顯著簇中停留斑點(diǎn)的熱點(diǎn)進(jìn)行空間密度聚類，獲得城市熱點(diǎn)路徑的空間分布。通過(guò)實(shí)驗(yàn)驗(yàn)證了該方法能準(zhǔn)確發(fā)現(xiàn)城市熱點(diǎn)路徑的集中區(qū)域和城市功能集聚區(qū)域。下一步工作將研究致力于語(yǔ)義時(shí)間信息的引入，探討不同時(shí)段的城市熱點(diǎn)路徑分布的演變。

［1］XIA Ying，WEN Haiping，ZHANG Xu.Hot route analysis method based on trajectory clustering ［J］.Journal of Chongqing of Posts and Telecommunications（Natural Science Edition），2011，23 （5）：602－606 （in Chinese）. ［夏英，溫海平，張旭.基于軌跡聚類的熱點(diǎn)路徑分析方法 ［J］.重慶郵電大學(xué)學(xué)報(bào) （自然科學(xué)版），2011，23 （5）：602－606.］

［2］LI Xiaolei，HAN Jiawei，LEE Jae Gil，et al.Traffic densitybased discovery of hot routes in road networks ［C］／／Proceedings of the 10th International Symposium on Spatial and Temporal Databases.Boston，MA，USA：Springer，2007：441－ 459.

［3］YUAN Guan，XIA Shixiong，ZHANG Lei，et al.Trajectory clustering algorithmbased on structural similarity ［J］.Journal on Communications，2011，32 （9）：103－110 （in Chinese）.［袁冠，夏士雄，張磊，等.基于結(jié)構(gòu)相似度的軌跡聚類算法［J］.通信學(xué)報(bào)，2011，32 （9）：103－110.］

［4］Lee J G，Han J W，Whang K Y.Trajectory clustering：A partition－and－group framework ［C］／／Beijing，China：Proceedings of the ACM SIGMOD International Conference on Management of Data，2007：593－604.

［5］Kreveld M V，Luo J.The definition and computation of trajectory and sub－trajectory similarity ［C］／／Seattle，Washington，USA：Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems，2007：324－327.

［6］HAN Chenshou，XIA Shixiong，ZHANG Lei，et al.Subtrajectory clustering algorithm based on speed restriction ［J］.Computer Engineering，2011，37 （7）：219－221 （in Chinese）.［韓陳壽，夏士雄，張磊，等.基于速度約束的分段軌跡聚類算法 ［J］.計(jì)算機(jī)工程，2011，37 （7）：219－221.］

［7］Chen Ping，Huo Qiuyan，Xu Xuezhou.Clustering networkconstrained uncertain trajectories ［C］／／Eighth International Conference on Fuzzy Systems and Knowledge Discovery，2011：1657－1662.

［8］Kim Sang Wook，Baek Ji Haeng，Lee Junghoon.Trajectory clustering in road network environment ［C］／／Computational Intelligence and Data Mining，2009：299－305.

［9］XIA Ying，WANG Guoyin，ZHANG Xu，et al.Research of Spatio－temporal similarity measure on network constrained trajectory data［G］.LNCS 6401：Proceedings of the 5th International Conference on Rough Set and Knowledge Technology，2010：491－498.

［10］YAN Jun，YUAN Hongyong，SHU Xueming，et al.Optimal clustering algorithm for crime spatial aggregation states analysis［J］.Journal Tsinghua Univ（Sci ＆Tech），2009，49（2）：176－178 （in Chinese）. ［顏峻，袁宏永，疏學(xué)明，等.用于犯罪空間聚集態(tài)研究的優(yōu)化聚類算法 ［J］.清華大學(xué)學(xué)報(bào) （自然科學(xué)版），2009，49 （2）：176－178.］

［11］QU Lin，ZHOU Fan，CHEN Yaowu.Trajectory Classification based on Hausdorff distance for visual surveillance system［J］.Journal of Jilin University（Engineering and Technology Edition），2009，39 （6）：1618－1624 （in Chinese）. ［曲琳，周凡，陳耀武.基于Hausdorff距離的視覺監(jiān)控軌跡分類算法 ［J］.吉林大學(xué)學(xué)報(bào)（工學(xué)版），2009，39 （6）：1618－1624.］