考慮道路形狀約束的車(chē)輛軌跡聚類(lèi)方法

馮心欣，柳澤烽，謝志鵬，鄭海峰

(福州大學(xué) 物理與信息工程學(xué)院，福州 350116)

0 引 言

近年來(lái)，隨著汽車(chē)數(shù)量的持續(xù)增長(zhǎng)，城市的道路承載容量已近飽和，道路擁堵問(wèn)題日益嚴(yán)重。車(chē)聯(lián)網(wǎng)的相應(yīng)技術(shù)對(duì)道路及車(chē)輛情況的分析提供了技術(shù)支持，運(yùn)用該技術(shù)可以得到車(chē)輛的行為狀態(tài)規(guī)律信息，并應(yīng)用這些分析結(jié)果達(dá)到合理分配交通資源的目的[1]。通過(guò)相應(yīng)互聯(lián)網(wǎng)技術(shù)降低交通擁堵的概率和時(shí)間，從而減輕道路負(fù)擔(dān)，并在一定程度上緩解了資源浪費(fèi)現(xiàn)象并改善環(huán)境污染的問(wèn)題[2]。

由于城市交通路網(wǎng)結(jié)構(gòu)的復(fù)雜性以及市民出行模式的多樣性和動(dòng)態(tài)性等因素，傳統(tǒng)的車(chē)聯(lián)網(wǎng)技術(shù)已無(wú)法有效地解決交通問(wèn)題[3]。近年來(lái)，隨著大數(shù)據(jù)挖掘和分析技術(shù)的發(fā)展，海量車(chē)聯(lián)網(wǎng)數(shù)據(jù)的獲取可以利用城市交通監(jiān)測(cè)、控制技術(shù)等方法實(shí)現(xiàn)。分析車(chē)輛數(shù)據(jù)可以挖掘出車(chē)輛行駛的潛在規(guī)律，該規(guī)律能夠指導(dǎo)車(chē)輛出行，也能夠?yàn)槌鞘新肪W(wǎng)規(guī)劃、城市交通設(shè)施建設(shè)及預(yù)測(cè)未來(lái)城市交通狀況提供參考基礎(chǔ)，從而避免或減輕車(chē)輛擁堵的狀況[4-5]。

為了找到不同移動(dòng)物體共享的代表性路徑或共同趨勢(shì)，通常需要將類(lèi)似的軌跡組合成簇類(lèi)。在城市交通里，類(lèi)似軌跡的聚類(lèi)結(jié)果代表了同一時(shí)段內(nèi)大量車(chē)輛具有共同的行駛路線，即道路擁堵。

根據(jù)軌跡分析中使用的軌跡信息，通?？梢詫⒒谝苿?dòng)物體軌跡的研究分為3類(lèi)。第1類(lèi)是以位置點(diǎn)數(shù)據(jù)分析并提供查詢和挖掘基于點(diǎn)的位置數(shù)據(jù)的算法[6]。例如，找到附近的興趣點(diǎn)或發(fā)現(xiàn)人們喜歡在周末和假期聚集的熱門(mén)地點(diǎn)。第2類(lèi)是對(duì)移動(dòng)物體的整個(gè)軌跡進(jìn)行軌跡聚類(lèi)分析和挖掘的算法。例如，Gaffney等提出通過(guò)使用回歸混合模型和EM(expectation maximization)算法將類(lèi)似的軌跡組合成簇[7-8]。該算法針對(duì)2條完整軌跡之間的總距離聚類(lèi)軌跡。然而，移動(dòng)的物體很少在現(xiàn)實(shí)世界中具有相同的行徑軌跡。第3類(lèi)是基于移動(dòng)物體軌跡的形狀將軌跡進(jìn)行分割，從整個(gè)軌跡的數(shù)據(jù)集中識(shí)別有用子軌跡的算法。以上聚類(lèi)算法均沒(méi)有考慮實(shí)際道路網(wǎng)絡(luò)的情況，僅針對(duì)自由空間上的軌跡進(jìn)行聚類(lèi)分析[9-11]。

本文在考慮道路網(wǎng)絡(luò)物理約束的基礎(chǔ)上提出車(chē)輛軌跡聚類(lèi)的道路網(wǎng)絡(luò)感知方法。具體步驟：首先將車(chē)輛軌跡數(shù)據(jù)進(jìn)行預(yù)處理，主要有基于線性插值和考慮道路形狀關(guān)鍵點(diǎn)選取的車(chē)輛軌跡重構(gòu)；然后對(duì)車(chē)輛軌跡進(jìn)行聚類(lèi)，分為子軌跡聚類(lèi)、基于密度的聚類(lèi)初始化和鄰居流聚類(lèi)的合并3個(gè)步驟；最后對(duì)聚類(lèi)結(jié)果進(jìn)行分析。根據(jù)真實(shí)車(chē)輛位置信息數(shù)據(jù)集進(jìn)行驗(yàn)證。結(jié)果表明，針對(duì)車(chē)輛軌跡聚類(lèi)并結(jié)合道路網(wǎng)絡(luò)的方法能夠更加真實(shí)地反映車(chē)輛的行為特征。

1 數(shù)據(jù)預(yù)處理

1.1 城市車(chē)輛分布熱力圖

城市中道路熱點(diǎn)區(qū)域的分布在一定程度上能夠說(shuō)明車(chē)輛在道路上行駛行為特征的分布特點(diǎn)。實(shí)際上，針對(duì)于車(chē)輛軌跡的聚類(lèi)，無(wú)需對(duì)整個(gè)城市中的所有道路上的車(chē)輛軌跡進(jìn)行聚類(lèi)分析。在較偏遠(yuǎn)的地區(qū)，其道路及車(chē)流量較少，由此，其車(chē)輛軌跡不具有代表性，也可能不存在聚類(lèi)現(xiàn)象。在分析中，應(yīng)排除代表性低的車(chē)輛軌跡，只需對(duì)具有較密集車(chē)輛軌跡的道路進(jìn)行聚類(lèi)分析即可。

本文首先利用ArcGIS軟件對(duì)預(yù)處理后的匹配車(chē)輛位置數(shù)據(jù)的地圖進(jìn)行密度分析，得到該地圖上反映車(chē)輛密度區(qū)域的熱力圖，如圖1；然后將IRCC(image recognition cluster center)算法[12]應(yīng)用到此車(chē)輛分布熱力圖中，以識(shí)別出城市中主要的熱點(diǎn)區(qū)域，如圖2；最后針對(duì)這些熱點(diǎn)區(qū)域道路上行駛的車(chē)輛軌跡進(jìn)行聚類(lèi)分析，并利用得到的熱點(diǎn)區(qū)域?qū)Τ鞘械缆飞系能?chē)輛軌跡進(jìn)行分割，以此形成城市道路中不同的軌跡聚類(lèi)結(jié)果。

圖1 城市車(chē)輛分布熱力圖Fig.1 Thermodynamic map of urban vehicle distribution

圖2 識(shí)別出的主要熱點(diǎn)區(qū)域Fig.2 Identification of main hot spots

1.2 車(chē)輛軌跡數(shù)據(jù)處理

車(chē)輛軌跡數(shù)據(jù)處理部分包括數(shù)據(jù)處理、軌跡數(shù)據(jù)的重構(gòu)和道路密度的統(tǒng)計(jì)。

1.2.1 數(shù)據(jù)處理

由于開(kāi)始時(shí)得到的車(chē)輛數(shù)據(jù)是某一些時(shí)刻不同車(chē)輛的位置數(shù)據(jù)，這些位置數(shù)據(jù)只能反映車(chē)輛某一時(shí)刻的靜態(tài)數(shù)據(jù)特征，無(wú)法說(shuō)明車(chē)輛在某一段連續(xù)時(shí)間內(nèi)位置移動(dòng)的行為特征。因此，需要在得到數(shù)據(jù)的基礎(chǔ)上對(duì)這些數(shù)據(jù)做進(jìn)一步的處理。具體處理步驟如下：①針對(duì)主要熱點(diǎn)區(qū)域，選擇出該區(qū)域某些車(chē)輛在一段時(shí)間內(nèi)的位置數(shù)據(jù)；②對(duì)該區(qū)域的所有道路進(jìn)行標(biāo)號(hào)，通過(guò)限制經(jīng)緯度范圍從MapInfo中獲取每條道路的標(biāo)號(hào)，與之前獲得的數(shù)據(jù)(車(chē)牌、時(shí)間以及每輛車(chē)對(duì)應(yīng)的經(jīng)度、緯度)整合形成完整的數(shù)據(jù)集；③以各車(chē)的車(chē)牌作為車(chē)輛ID標(biāo)識(shí)每輛車(chē)的數(shù)據(jù)，根據(jù)車(chē)輛ID將車(chē)輛位置數(shù)據(jù)進(jìn)行歸類(lèi)，并且將每輛車(chē)的數(shù)據(jù)以時(shí)間順序進(jìn)行排序?；谝陨喜襟E，就能夠得到每輛車(chē)在一段連續(xù)時(shí)間內(nèi)的軌跡數(shù)據(jù)。

1.2.2 車(chē)輛軌跡的重構(gòu)

車(chē)輛位置數(shù)據(jù)過(guò)多，極大的占用了內(nèi)存空間，同時(shí)也將影響到接下來(lái)的軌跡聚類(lèi)速度。實(shí)際上，繪制一輛車(chē)的軌跡，僅需部分位置數(shù)據(jù)即可得出該車(chē)輛的完整軌跡。而有些路段，由于各種原因使得車(chē)輛的位置數(shù)據(jù)較為稀疏或偏離正常位置，從而無(wú)法給出較為精確的車(chē)輛軌跡。因此，需要對(duì)這些位置數(shù)據(jù)進(jìn)重構(gòu)。

對(duì)于車(chē)輛軌跡的重構(gòu)，即車(chē)輛位置數(shù)據(jù)的再選取的過(guò)程。具體過(guò)程如下：①在車(chē)輛位置數(shù)據(jù)較為稀疏的部分，通過(guò)線性插值的方法將這些位置數(shù)據(jù)連接起來(lái)形成車(chē)輛軌跡；②在車(chē)輛位置數(shù)據(jù)較為密集的地方，從中選取出構(gòu)成車(chē)輛軌跡的關(guān)鍵點(diǎn)；③剔除對(duì)車(chē)輛軌跡重構(gòu)沒(méi)有影響或影響較小的數(shù)據(jù)。

以圖3為例說(shuō)明軌跡重構(gòu)關(guān)鍵點(diǎn)選取的步驟，圖3中的道路上3條虛線分別表示3輛車(chē)的軌跡。選取步驟如下：①根據(jù)道路的節(jié)點(diǎn)將道路劃分為Ⅰ，Ⅱ，Ⅲ；②選取由于道路分段而將車(chē)輛軌跡截?cái)嗟狞c(diǎn)作為軌跡重構(gòu)的關(guān)鍵點(diǎn)，如2，5，8位置點(diǎn)，并以此對(duì)車(chē)輛軌跡進(jìn)行分段；③剔除對(duì)車(chē)輛軌跡重構(gòu)沒(méi)有影響或影響較小的數(shù)據(jù)，以1→2，4→5，7→10→8這3條車(chē)輛軌跡為例，它們之間有許多位置數(shù)據(jù)，而這些位置數(shù)據(jù)對(duì)于構(gòu)成這些軌跡沒(méi)有任何影響。其他路段對(duì)于車(chē)輛軌跡關(guān)鍵點(diǎn)的選取也以上述的步驟進(jìn)行處理。

圖3 車(chē)輛軌跡重構(gòu)關(guān)鍵點(diǎn)選取示意圖Fig.3 Selection key points of vehicle trajectory reconstruction

1.2.3 道路密度統(tǒng)計(jì)

在聚類(lèi)前，需要先得到每條道路上的車(chē)輛密度。同一車(chē)輛可在同一條道路上的數(shù)據(jù)在統(tǒng)計(jì)車(chē)輛密度時(shí)，僅需對(duì)該車(chē)輛在這段時(shí)間內(nèi)計(jì)數(shù)一次即可，因此，將車(chē)輛ID和道路標(biāo)號(hào)同時(shí)相同的數(shù)據(jù)字段合并，僅留下一條數(shù)據(jù)字段。表1是某個(gè)區(qū)域中部分道路上的車(chē)輛密度統(tǒng)計(jì)表。

根據(jù)得到統(tǒng)計(jì)結(jié)果，以道路車(chē)輛密度降序列，在同一個(gè)道路標(biāo)號(hào)內(nèi)以時(shí)間升序，同時(shí)將車(chē)輛ID歸類(lèi)，最后得到根據(jù)道路密度降序排列并進(jìn)行相應(yīng)處理后的數(shù)據(jù)表，如表2。

表1 道路密度統(tǒng)計(jì)表

2 車(chē)輛軌跡聚類(lèi)

通過(guò)數(shù)據(jù)預(yù)處理的準(zhǔn)備工作，得到了所需分析的道路區(qū)域及相應(yīng)的車(chē)輛軌跡數(shù)據(jù)。根據(jù)處理后的車(chē)輛軌跡數(shù)據(jù)，本文將同一路段上的車(chē)輛軌跡看成是同一組軌跡并利用路網(wǎng)的各個(gè)路口交叉點(diǎn)對(duì)路網(wǎng)和車(chē)輛軌跡進(jìn)行分段。在本部分中將介紹對(duì)這些車(chē)輛軌跡數(shù)據(jù)進(jìn)行聚類(lèi)分析的方法和流程。

2.1 路網(wǎng)模型

道路網(wǎng)絡(luò)是由一個(gè)有向圖G=(V,E)表示，由連接節(jié)點(diǎn)V={n0,n1,…,nN}和有向邊E={(rid,ninj)|ninj∈V}。一條邊e=(rid,ninj)∈E在真實(shí)的道路網(wǎng)絡(luò)代表路段連接2路口ni和nj。本文用相應(yīng)的路段標(biāo)識(shí)符rid標(biāo)記每條邊。對(duì)于一輛車(chē)，它行駛的開(kāi)始位置和目標(biāo)位置形成一個(gè)軌跡。值得注意的是，在本文模型中，軌跡中的時(shí)間信息(即記錄的時(shí)間戳)確定了軌跡中位置的順序。

定義1定義一個(gè)軌跡集合TJ={tjid,r0r1…rn}，其中，r0r1…rn表示組成車(chē)輛軌跡的n+1坐標(biāo)點(diǎn)，tjid為該軌跡的標(biāo)識(shí)符；TJF為T(mén)J的子集，TJF={tjid,rid,rkrk+1…rk+m}，其中，rkrk+1…rk+m是由m+1坐標(biāo)點(diǎn)組成，為r0r1…rn的一部分。

定義2定義子軌跡聚類(lèi)簇的密度為在該聚類(lèi)簇中子軌跡的數(shù)量。定義子軌跡聚類(lèi)簇經(jīng)過(guò)聚類(lèi)操作得到的聚類(lèi)為流聚類(lèi)簇。

定義3流聚類(lèi)簇中的關(guān)鍵路徑由每一個(gè)基本子軌跡聚類(lèi)簇的末位置點(diǎn)連接而成。

同時(shí)，做以下假設(shè)：TJ1和TJ2在同一條道路上，TJ3在另一條道路上。根據(jù)歐氏距離得到TJ3與TJ2的距離小于TJ1與TJ2的距離，但仍將TJ1和TJ2歸為一類(lèi)，而不是將TJ3和TJ2歸為一類(lèi)。

2.2 軌跡聚類(lèi)算法

本文提出基于車(chē)輛軌跡聚類(lèi)的方法用于預(yù)測(cè)車(chē)輛的行為特征，從子軌跡聚類(lèi)、基于密度的聚類(lèi)初始化和鄰居流聚類(lèi)的合并這3個(gè)步驟進(jìn)行軌跡聚類(lèi)。

算法的總體流程圖如圖4所示。算法的具體步驟如下。

圖4 車(chē)輛軌跡聚類(lèi)算法流程圖Fig.4 Flow chart of vehicle trajectory clustering algorithm

步驟1子軌跡聚類(lèi)。

以路網(wǎng)的交叉點(diǎn)為分割點(diǎn)對(duì)路網(wǎng)上的車(chē)輛軌跡進(jìn)行劃分以得到一系列的車(chē)輛子軌跡。對(duì)于每一個(gè)車(chē)輛軌跡TJk={tjidk,r0r1…rn}，從第1個(gè)位置點(diǎn)r0開(kāi)始提取每一輛車(chē)的子軌跡TJFk，直到最后一個(gè)位置rn。以其中一輛車(chē)的車(chē)輛軌跡為例進(jìn)行說(shuō)明。每次從車(chē)輛軌跡數(shù)據(jù)集中取出2個(gè)連續(xù)的位置點(diǎn)，如ri和ri+1，然后比較它們的路段標(biāo)識(shí)rid(ri)和rid(ri+1)，如果rid(ri)≠rid(ri+1)，這2個(gè)位置點(diǎn)在不同的路段上；如果這2個(gè)點(diǎn)是表示的路段是相鄰的，則可以得到這2個(gè)路段的交叉點(diǎn)；2個(gè)路段不連續(xù)，通過(guò)地圖匹配的方法能夠得到連接這2段路的一系列的道路交叉點(diǎn)；將這些得到的道路交叉點(diǎn)插入到這2段道路之間。通過(guò)上述方法，能夠得到車(chē)輛軌跡的一系列子軌跡。

步驟2基于密度的聚類(lèi)初始化流程。

通過(guò)路段標(biāo)識(shí)將得到的子軌跡進(jìn)行分組，即以路段為單位組成各基本的子軌跡段聚類(lèi)簇。根據(jù)定義2計(jì)算每個(gè)基本子軌跡聚類(lèi)簇的密度，并按密度大小降序排列。設(shè)置一個(gè)密度閾值δ，若是基本子軌跡聚類(lèi)簇的密度值小于閾值δ，則將該聚類(lèi)簇剔除后將剩下的基本子軌跡聚類(lèi)簇放入集合B中。

在得到上述的基本子軌跡聚類(lèi)簇后，選取密度最大的聚類(lèi)簇為初始聚類(lèi)簇M，并將該聚類(lèi)簇從集合B中刪除并放入集合C1中。聚類(lèi)的頭路口點(diǎn)為ns，尾路口點(diǎn)為ne。從集合B中查找子軌跡聚類(lèi)簇的尾路口點(diǎn)與M頭位置點(diǎn)相同的聚類(lèi)簇，并將其插入到M的前面，查找子軌跡聚類(lèi)簇的頭路口點(diǎn)與M的尾路口點(diǎn)相同的聚類(lèi)簇，將其插入到M的后面，若存在超過(guò)2個(gè)的基本子軌跡聚類(lèi)簇滿足條件，則選擇軌跡密度數(shù)大的那個(gè)插入到M的前面或后面；若這些滿足條件的基本子軌跡聚類(lèi)簇的軌跡密度數(shù)仍相同，則比較這些滿足條件的基本子軌跡聚類(lèi)簇的前面或后面的子軌跡聚類(lèi)簇的軌跡密度，選擇密度數(shù)大的那個(gè)插入到M的前面或后面；以此類(lèi)推，直到?jīng)]有滿足的聚類(lèi)簇為止[13]。

同時(shí)，插入到M前后的基本聚類(lèi)簇從集合B中刪除并加入到集合C1中。接下來(lái)，則從集合B中剩余的所有子軌跡聚類(lèi)簇中，選擇密度值最大的作為新的初始聚類(lèi)簇，放入集合C2中，然后重復(fù)上述操作，直到集合B中的所有子軌跡聚類(lèi)簇為空為止。最終，將得到的各聚類(lèi)簇集合添加到集合W中，從而得到一個(gè)對(duì)基本子軌跡聚類(lèi)簇進(jìn)行聚類(lèi)操作后的集合W。

步驟3鄰居流聚類(lèi)的合并。

在得到經(jīng)過(guò)聚類(lèi)操作的集合W后，測(cè)量W集合中聚類(lèi)簇之間的Hausdorff距離。若2個(gè)流聚類(lèi)簇之間的距離小于預(yù)設(shè)的閾值Θ，將認(rèn)為這2個(gè)流聚類(lèi)簇具有較大的相關(guān)性從而將這2個(gè)流聚類(lèi)簇合并。

在合并過(guò)程中，選擇流聚類(lèi)密度最大的流聚類(lèi)簇開(kāi)始，將其從W集合中刪除并加入到集合F中，然后計(jì)算其關(guān)鍵路徑在小于Θ范圍內(nèi)是否有其他的流聚類(lèi)，若有，則將它們合并為一個(gè)聚類(lèi)，并將該流聚類(lèi)也從W集合中刪除加入到F集合中，直到?jīng)]有滿足條件的流聚類(lèi)為止。接下來(lái)從W集合中剩余的具有最大密度值的流聚類(lèi)開(kāi)始，重復(fù)上述步驟，直到W集合為空。

2.3 算法時(shí)間復(fù)雜度分析

設(shè)論域U中的數(shù)據(jù)總條目為N，車(chē)輛軌跡數(shù)目為M，流聚類(lèi)數(shù)目為l，近鄰數(shù)目為q?？梢灾乐炼嘤?N-M)個(gè)子軌跡段。

設(shè)有車(chē)輛軌跡TJi中2個(gè)連續(xù)的位置點(diǎn)ri和ri+1。首先判定它們的路段標(biāo)識(shí)rid(ri)和rid(ri+1)的情況，共1次。然后，每一軌跡上的2個(gè)連續(xù)的位置點(diǎn)都要進(jìn)行判定，共(N-M)次。故子聚類(lèi)方法算法的時(shí)間復(fù)雜度為O(N-M)。

設(shè)有2個(gè)子軌跡TJFi和TJFk首先判斷2子軌跡是否有相同的路口點(diǎn)，共4次。然后，每個(gè)子軌跡都要與其余的(N-M-1)個(gè)子軌跡進(jìn)行判斷，共需2(N-M-1)2次。可得基于密度的聚類(lèi)初始化算法的時(shí)間復(fù)雜度為O(2(N-M-1)2)。

設(shè)有2個(gè)流聚類(lèi)Ci和Ck，類(lèi)中對(duì)象分別為ni和nk。首先計(jì)算類(lèi)Ci中的對(duì)象ni與類(lèi)Ck中每一個(gè)對(duì)象的距離，共ni·q次；計(jì)算類(lèi)Ck中的對(duì)象nk與類(lèi)Ci中每一個(gè)對(duì)象的距離，共nk·q次。每個(gè)流聚類(lèi)都要與其余的(l-1)流聚類(lèi)進(jìn)行計(jì)算，共需計(jì)算(q2l(l-1)/2)次。流聚類(lèi)的合并的時(shí)間復(fù)雜度為O(q2l(l-1)/2)。

3 實(shí)驗(yàn)

3.1 仿真車(chē)輛數(shù)據(jù)驗(yàn)證

將本文的算法應(yīng)用到仿真車(chē)輛數(shù)據(jù)以驗(yàn)證上述車(chē)輛軌跡聚類(lèi)算法的有效性。

首先模擬了6個(gè)路口及周?chē)慕煌ㄇ闆r，仿真出車(chē)輛數(shù)據(jù)，讓車(chē)輛位置數(shù)據(jù)在道路交叉口及其2邊呈正態(tài)分布，即在道路交叉口處車(chē)輛位置數(shù)據(jù)較為密集，距離道路交叉口越遠(yuǎn)，車(chē)輛位置數(shù)據(jù)則越稀疏，如圖5。

圖5 仿真的車(chē)輛位置數(shù)據(jù)Fig.5 Location data of simulation vehicle

接下來(lái)對(duì)該仿真的車(chē)輛位置數(shù)據(jù)行密度分析及圖像識(shí)別，得到的熱力圖如圖6，識(shí)別出的熱點(diǎn)區(qū)域如圖7。

圖6 仿真車(chē)輛位置數(shù)據(jù)熱力圖Fig.6 Thermodynamic diagramof simulation vehicle’s location data

圖7 識(shí)別出的熱點(diǎn)區(qū)域Fig.7 Identified hot spots

實(shí)驗(yàn)步驟如下：①將車(chē)輛的位置數(shù)據(jù)根據(jù)時(shí)間信息連接生成車(chē)輛軌跡，得到如圖8所示的車(chē)輛軌跡圖；②將車(chē)輛軌跡算法及熱力圖識(shí)別結(jié)果等應(yīng)用到其中，可以得到如圖9所示的最終仿真數(shù)據(jù)軌跡聚類(lèi)結(jié)果圖。

圖8 仿真數(shù)據(jù)車(chē)輛軌跡Fig.8 Vehicle trajectory of simulation data

圖9 仿真數(shù)據(jù)車(chē)輛軌跡聚類(lèi)結(jié)果(不同序號(hào)代表不同的聚類(lèi)簇)Fig.9 Results simulation data vehicle trajectory clustering (Different designation represent different cluster)

圖9表明，通過(guò)本文軌跡聚類(lèi)算法，各個(gè)車(chē)輛軌跡密集的區(qū)域有效地聚集一起，形成各自的聚類(lèi)簇。同時(shí)，避免了僅因?yàn)樯倭寇?chē)輛軌跡將2個(gè)本不相關(guān)或相關(guān)性較低的車(chē)輛軌跡聚類(lèi)簇合并成同一個(gè)聚類(lèi)簇，這也與真實(shí)車(chē)輛數(shù)據(jù)下進(jìn)行驗(yàn)證的結(jié)果相符合。

3.2 真實(shí)車(chē)輛數(shù)據(jù)驗(yàn)證

本文選取福州市車(chē)聯(lián)網(wǎng)的真實(shí)車(chē)輛位置數(shù)據(jù)進(jìn)行驗(yàn)證。該數(shù)據(jù)集包括整個(gè)福州城區(qū)，經(jīng)緯度范圍為119.13～119.78°E，25.52～26.48°N。本文選取的是2015-12-01～2015-12-07之間的數(shù)據(jù)，總數(shù)據(jù)條目為10 628 352條。為了體現(xiàn)本文算法的運(yùn)行時(shí)間優(yōu)勢(shì)，根據(jù)地理位置隨機(jī)均勻抽取出2個(gè)數(shù)據(jù)集，分別包含759 168個(gè)條目和5 314 176個(gè)條目，并通過(guò)比較k-means代表的傳統(tǒng)聚類(lèi)方法來(lái)評(píng)估算法的效率和有效性。基于車(chē)輛軌跡數(shù)據(jù)聚類(lèi)方法通過(guò)利用道路網(wǎng)絡(luò)信息產(chǎn)生有意義的軌跡群，并且運(yùn)行速度比較快。圖10顯示了車(chē)輛軌跡的數(shù)量點(diǎn)與2種聚類(lèi)方法的對(duì)應(yīng)關(guān)系，其中第1種為本文提出的基于車(chē)輛軌跡數(shù)據(jù)聚類(lèi)方法，第2種為k-means聚類(lèi)方法。結(jié)果表明，當(dāng)數(shù)據(jù)量越大，算法節(jié)約的運(yùn)算時(shí)間越明顯。

圖10 運(yùn)行時(shí)間對(duì)比Fig.10 Running time

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

選取福州市某一車(chē)輛較為密集的區(qū)域進(jìn)行分析。該區(qū)域的具體經(jīng)緯度范圍為119.315 3～119.359 4°E，26.078 9～26.061 8°N。該區(qū)域包含福州市臺(tái)江區(qū)、晉安區(qū)、鼓樓區(qū)等主要鬧市區(qū)域，在這些區(qū)域中包含了福州市西湖公園、左海公園和三坊七巷等著名景區(qū)，東街口、王府井百貨等商業(yè)中心以及一些中小學(xué)和醫(yī)院等具有大量人流出入的地點(diǎn)，對(duì)這些區(qū)域進(jìn)行分析能夠更好地反映車(chē)輛軌跡聚類(lèi)算法對(duì)于福州市真實(shí)車(chē)輛軌跡數(shù)據(jù)聚類(lèi)結(jié)果的情況。選取2015-12-04 17:30～17:40這段連續(xù)時(shí)間內(nèi)的若干車(chē)輛軌跡數(shù)據(jù)進(jìn)行聚類(lèi)，在經(jīng)過(guò)基本聚類(lèi)后，能得到最終在該區(qū)域的車(chē)輛軌跡流聚類(lèi)結(jié)果如圖11，每個(gè)序號(hào)所表示的線段代表著各自的流聚類(lèi)，即各個(gè)車(chē)輛密集的地方。在此圖的基礎(chǔ)上，進(jìn)一步對(duì)流聚類(lèi)結(jié)果進(jìn)行一次聚類(lèi)。最終得到該區(qū)域的整體車(chē)輛軌跡聚類(lèi)結(jié)果如圖12，每個(gè)序號(hào)所表示的線段代表著各自的軌跡流聚類(lèi)合并結(jié)果。

圖11 車(chē)輛軌跡流聚類(lèi)結(jié)果Fig.11 Results of vehicle trajectory flow clustering

圖12 車(chē)輛軌跡聚類(lèi)結(jié)果Fig.12 Results of vehicle trajectory clustering

從圖11中對(duì)于車(chē)輛軌跡流聚類(lèi)的結(jié)果中可以看出，得到了8條以不同序號(hào)表示的主要的軌跡流聚類(lèi)結(jié)果，即表示8個(gè)車(chē)輛密集的道路聚類(lèi)簇。以圖12中序號(hào)②標(biāo)識(shí)的路段為例進(jìn)行分析，這條路段主要是經(jīng)過(guò)福州市的連江北路并且連同到福新中路。這條道路上有較多車(chē)輛的原因有以下3點(diǎn)：①途徑五里亭的高架橋，會(huì)有大量的車(chē)輛在此交匯；②路線上存在大醫(yī)院、診所和購(gòu)物中心等人群密集的地點(diǎn)，如福建省腫瘤醫(yī)院、晉安區(qū)第四中心小學(xué)和天虹商場(chǎng)；③該道路是通往福州市火車(chē)站和汽車(chē)站其中一條線路。這條道路的交通情況也與最后車(chē)輛軌跡聚類(lèi)的結(jié)果情況相符。

4 結(jié) 論

本文提出了針對(duì)車(chē)輛軌跡聚類(lèi)并結(jié)合道路網(wǎng)絡(luò)的車(chē)輛軌跡聚類(lèi)算法，包括得到城市的熱力圖及識(shí)別交通密集區(qū)域和對(duì)車(chē)輛軌跡數(shù)據(jù)的處理工作；詳細(xì)地闡述了車(chē)輛軌跡聚類(lèi)的方法原理，并對(duì)詳細(xì)的操作進(jìn)行了說(shuō)明；最后，使用福州市車(chē)輛數(shù)據(jù)以及本文仿真的車(chē)輛位置數(shù)據(jù)對(duì)提出的車(chē)輛軌跡聚類(lèi)算法進(jìn)行驗(yàn)證，并對(duì)最后的聚類(lèi)結(jié)果進(jìn)行詳細(xì)分析。實(shí)驗(yàn)結(jié)果表明，研究結(jié)果能夠反映福州市真實(shí)的車(chē)輛行為與道路網(wǎng)絡(luò)情況，與實(shí)際相符。