基于集成聚類的交叉口車輛行駛路徑提取方法

尹 卓 許 甜 陳陽舟 盧佳程

1(北京工業(yè)大學(xué)北京市交通工程重點(diǎn)實(shí)驗(yàn)室 北京 100124)2(中交第一公路勘察設(shè)計(jì)研究院有限公司 陜西 西安 710075)3(北京工業(yè)大學(xué)人工智能與自動(dòng)化學(xué)院 北京 100124)

0 引 言

軌跡數(shù)據(jù)的聚類是監(jiān)控場(chǎng)景中目標(biāo)行為分析的一項(xiàng)具有挑戰(zhàn)性的基礎(chǔ)工作。針對(duì)交叉口場(chǎng)景而言，車輛的行駛軌跡聚類對(duì)于交叉口的安全評(píng)估具有重要的意義。例如，基于車輛行駛軌跡聚類提出不同行駛路徑，可用于分析車輛事故的碰撞方式，評(píng)估事故發(fā)生的風(fēng)險(xiǎn)程度等。交叉口的車輛軌跡數(shù)據(jù)通常來自交通監(jiān)控視頻中車輛的識(shí)別與跟蹤。雖然交叉口車輛的運(yùn)動(dòng)行為受到交通規(guī)則的限制，具有很強(qiáng)的規(guī)律性，但是基于機(jī)器學(xué)習(xí)的車輛軌跡聚類卻面臨著很大的挑戰(zhàn)性。首先，交叉口場(chǎng)景非常容易發(fā)生遮擋，導(dǎo)致軌跡不連續(xù)的現(xiàn)象發(fā)生；其次，對(duì)于軌跡聚類而言，由于監(jiān)控場(chǎng)景視野的緣故，聚類與聚類之間的區(qū)別不明顯，使得在相似位置具有相似特性的軌跡可能對(duì)應(yīng)于不同的聚類[1]，甚至兩個(gè)聚類的軌跡數(shù)據(jù)會(huì)存在重疊的現(xiàn)象；最后，交叉口的車輛常常出現(xiàn)的停止行為使軌跡存在大量的停止點(diǎn)，從而導(dǎo)致軌跡的冗余現(xiàn)象。針對(duì)交叉口場(chǎng)景設(shè)計(jì)車輛軌跡聚類算法，并在此基礎(chǔ)上獲取穩(wěn)定的場(chǎng)景路徑信息已成為具有挑戰(zhàn)性的研究熱點(diǎn)。

各種監(jiān)控場(chǎng)景下路徑提取的基礎(chǔ)是運(yùn)動(dòng)目標(biāo)的軌跡聚類，軌跡聚類主要分為三種方式。第一種聚類方式為基于軌跡的空間相似性。早期的代表性工作由Morris等[2-3]和Zhang等[4]完成，他們將軌跡聚類問題轉(zhuǎn)化為時(shí)間序列聚類問題，并使用序列相似性距離度量(如LCSS距離等)計(jì)算軌跡之間的距離。基于軌跡相似度，采用各種聚類算法對(duì)軌跡進(jìn)行聚類。例如，Morris等[3]針對(duì)DTW和LCSS等距離度量應(yīng)用于模糊C-means聚類算法的效果進(jìn)行了實(shí)驗(yàn)對(duì)比，總結(jié)了相關(guān)算法的特點(diǎn)與優(yōu)勢(shì)。Kim等[5]針對(duì)城市級(jí)別的GPS軌跡數(shù)據(jù)進(jìn)行分析，使用DBSCAN聚類算法對(duì)軌跡進(jìn)行聚類。他們采用LCSS距離來評(píng)估軌跡的相似性，然后借助DBSCAN中的核心點(diǎn)的定義，提出了聚類代表(CRS)提取算法，并在聚類代表的基礎(chǔ)上合并相似的軌跡聚類。基于比較的聚類算法往往能夠取得較好的效果[3]，但是其缺點(diǎn)是時(shí)間與空間復(fù)雜度較高。Lee等[6]基于最小描述長(zhǎng)度原則(MDL)設(shè)計(jì)了軌跡分段算法。他們對(duì)軌跡先根據(jù)關(guān)鍵點(diǎn)進(jìn)行分段，再對(duì)分段軌跡進(jìn)行聚類。由于分段軌跡的距離度量采用了針對(duì)線段的朝向角度以及垂直距離與平行歐式距離度量，該算法本質(zhì)上也是基于距離的聚類方式。

第二種聚類方式主要基于統(tǒng)計(jì)特征。早期的代表性工作中，Li等[7]提出采用軌跡距離直方圖(TDH)對(duì)軌跡進(jìn)行描述，其中軌跡點(diǎn)的轉(zhuǎn)向角被投射到了方向直方圖中，因此形成了對(duì)軌跡方向的統(tǒng)計(jì)特征表示；Anjum等[8]拓展了相關(guān)的特征，提出了軌跡數(shù)據(jù)的一系列統(tǒng)計(jì)特征，并使用Mean-shift算法對(duì)軌跡進(jìn)行了聚類。基于統(tǒng)計(jì)特征的軌跡數(shù)據(jù)聚類往往能夠以較低的時(shí)間復(fù)雜度獲得較為穩(wěn)定而優(yōu)良的聚類效果，但是軌跡的統(tǒng)計(jì)特征忽略了軌跡數(shù)據(jù)的時(shí)空相關(guān)性，因此聚類效果往往不如基于相似度的軌跡聚類效果。

第三種聚類方式是在軌跡建模之后再利用模型對(duì)軌跡進(jìn)行分析。文獻(xiàn)[9]使用高斯混合模型與隱馬爾可夫模型對(duì)軌跡進(jìn)行建模，然后對(duì)軌跡進(jìn)行聚類。文獻(xiàn)[10]則利用狄利克雷過程對(duì)軌跡進(jìn)行分類與聚類，算法可以被拓展到實(shí)時(shí)方式，但是這種聚類方式的缺點(diǎn)在于其效果通常受到模型參數(shù)初值的影響。

在上述針對(duì)監(jiān)控場(chǎng)景的車輛軌跡聚類方法中，缺乏對(duì)基于空間軌跡相似度比較的方法與基于統(tǒng)計(jì)特征的軌跡聚類方法進(jìn)行集成，以發(fā)揮各自的優(yōu)勢(shì)。因此，為了獲取更具魯棒性的聚類結(jié)果，獲取場(chǎng)景的路徑信息，本文提出基于集成聚類的交叉口路徑信息挖掘方法，通過融合不同聚類方式獲取交叉口場(chǎng)景的路徑信息。首先，對(duì)基于軌跡統(tǒng)計(jì)特征的聚類方法與基于距離度量的聚類方法進(jìn)行集成，獲得了更具魯棒性的軌跡聚類結(jié)果；其次，針對(duì)軌跡相似度矩陣引入拉普拉斯中心性[11]，并對(duì)每一個(gè)聚類的聚類原型進(jìn)行提取，消除了噪聲軌跡對(duì)聚類原型提取的影響；最后，引入深度優(yōu)先搜索算法對(duì)聚類原型相似度鄰接矩陣的連通子圖進(jìn)行搜索，合并冗余的聚類，生成場(chǎng)景的路徑信息。使用獲取的路徑信息，可以進(jìn)一步對(duì)軌跡進(jìn)行分類或者異常檢測(cè)等。

1 相關(guān)概念與數(shù)據(jù)預(yù)處理

圖1 軌跡數(shù)據(jù)網(wǎng)格化實(shí)例，深色區(qū)域被標(biāo)定為停止區(qū)域

(1)

2 軌跡特征提取與距離度量

2.1 軌跡數(shù)據(jù)的直方圖描述

如圖2所示，軌跡的方向角度被分為了8份，每一個(gè)網(wǎng)格上的角度被分配到了統(tǒng)計(jì)圖上。

圖2 軌跡數(shù)據(jù)角度直方圖

對(duì)于pij而言，若(m-1)Δα≤aij

(2)

便可以得到軌跡方向落在第Im區(qū)間內(nèi)的頻率，并且得到一個(gè)長(zhǎng)度為α的一個(gè)軌跡方向向量。

2.2 軌跡形狀特征

(3)

而軌跡的復(fù)雜度定義為：

(4)

式中：ci取值在0到1的范圍內(nèi)。不同于文獻(xiàn)[3]，這里軌跡的復(fù)雜度計(jì)算使用了壓縮后的軌跡的復(fù)雜度計(jì)算。文獻(xiàn)[3]采用原始軌跡對(duì)軌跡復(fù)雜度進(jìn)行計(jì)算，但是在存在大量停止點(diǎn)的情況下，利用原始軌跡計(jì)算移動(dòng)總距離會(huì)受到冗余的停止點(diǎn)的影響，因此此處采用網(wǎng)格軌跡計(jì)算車輛行駛的距離，可以防止停止點(diǎn)對(duì)于計(jì)算的干擾。

前面從軌跡的朝向和形狀兩個(gè)角度給出了軌跡的特征提取方法，還提取了軌跡的以下特征：軌跡的起點(diǎn)與終點(diǎn)坐標(biāo)[xi1,yi1]與[xiTi,yiTi]，軌跡x與y坐標(biāo)的分布特征[μix,σix]與[μiy,σiy]等。由于這里使用的都是完整的軌跡，自然軌跡的起點(diǎn)與終點(diǎn)對(duì)于軌跡聚類的判別有一定的幫助，不同起點(diǎn)與終點(diǎn)的軌跡對(duì)應(yīng)于不同的運(yùn)動(dòng)模式。

2.3 軌跡相似度

(1) 邊界條件：路徑的起點(diǎn)位于(pi1,pj1)，終點(diǎn)位于(piTi,pjTj)。

(2) 漸進(jìn)性條件：路徑上的每一個(gè)軌跡點(diǎn)滿足條件：pi1≤…≤pik≤…≤piTi，pj1≤…≤pjl≤…≤pjTj。

(3) 步長(zhǎng)條件：當(dāng)位于(pik,pjl)點(diǎn)時(shí)，路徑的下一步坐標(biāo)在{(pi(k+1),pjl),(pik,pj(l+1)),(pi(k+1),pj(l+1))}集合內(nèi)。這意味著每次路徑只能沿著時(shí)間順序移動(dòng)一步。

條件(3)可以被放松為移動(dòng)多步[14]，這通常意味著DTW對(duì)于噪聲的軌跡點(diǎn)具有更強(qiáng)的魯棒性。假設(shè)這里存在一條累積損失值最小的路徑f*，而DTW距離被定義為：

DTW(Traji,Trajj)=sum(f*)

(5)

即DTW距離的值為滿足三個(gè)條件的累積損失值最小的一條路徑的累積損失值。

圖3為數(shù)據(jù)集中兩條軌跡的損失矩陣的熱力圖。顏色越深，則兩個(gè)坐標(biāo)點(diǎn)之間的歐式距離越近。而最優(yōu)的DTW距離的值為滿足前面條件的累積損失最小的一條路徑對(duì)應(yīng)的累積損失值，也就是白色的路徑。類似于DTW距離的度量方式還有LCSS距離、Frechet距離、編輯距離等。

圖3 DTW距離在損失矩陣中的最優(yōu)路徑

3 路徑提取算法

3.1 軌跡的集成聚類策略

現(xiàn)有的一系列研究中，對(duì)于交叉口場(chǎng)景的軌跡聚類可以粗略地分為基于統(tǒng)計(jì)特征聚類[7-8，14]的軌跡聚類方法與基于比較的軌跡聚類方法[5-6，9]，這些方法有各自的優(yōu)缺點(diǎn)。為了提升聚類的魯棒性，獲取更高質(zhì)量的聚類，本節(jié)采用兩類方法融合的集成聚類策略，即對(duì)基于特征的聚類與基于軌跡相似度的聚類進(jìn)行了集成。

記聯(lián)合相關(guān)矩陣為S，矩陣的元素為：

(6)

式中：

(7)

可以看出，聯(lián)合相關(guān)矩陣元素的取值范圍在0到1之間，其生成過程如圖5所示。

圖5 聯(lián)合相關(guān)矩陣生成

(8)

式中：

(9)

(10)

(11)

(12)

權(quán)重wn的定義為：

wn=ECI(clsn(Traji))

(13)

基于軌跡相似性的聚類采用譜聚類方法進(jìn)行。譜聚類[15]是一種基于圖的聚類算法，其思想是基于結(jié)點(diǎn)的相似度構(gòu)建鄰接矩陣與拉普拉斯矩陣，然后優(yōu)化基于拉普拉斯矩陣的損失函數(shù)[15]。以DTW距離為例，首先構(gòu)建軌跡數(shù)據(jù)的鄰接矩陣A：

Aij=e-DTW(Traji,Trajj)/2ζ2

(14)

針對(duì)軌跡特征的聚類，本文采用層次聚類算法。其優(yōu)點(diǎn)在于對(duì)于非凸聚類也能取得優(yōu)異的結(jié)果，缺點(diǎn)是時(shí)間復(fù)雜度較高。當(dāng)進(jìn)行特征聚類時(shí)，軌跡形狀特征與軌跡方向直方圖(TDH)描述的特征被組合以后進(jìn)行聚類。其中，軌跡的形狀特征需要進(jìn)行Min-Max歸一化后，才能送入到聚類算法中進(jìn)行聚類。例如，對(duì)于第i條軌跡的復(fù)雜度di表示為：

(15)

在進(jìn)行歸一化以后，就可以對(duì)歸一化以后的特征進(jìn)行聚類，從而獲取特征聚類的結(jié)果。

獲取了加權(quán)聯(lián)合相關(guān)矩陣之后，任意一種聚類算法都可以被用來對(duì)集成以后的結(jié)果進(jìn)行聚類。本文仍然采用譜聚類對(duì)軌跡集成結(jié)果進(jìn)行聚類，其中加權(quán)聯(lián)合相關(guān)矩陣作為譜聚類的鄰接矩陣。最后一步采用譜聚類，一方面是因?yàn)樽V聚類能夠應(yīng)對(duì)非凸聚類問題，另一方面，Liu等[20]提出的針對(duì)聯(lián)合相關(guān)矩陣的譜聚類通過特征編碼的方式將問題轉(zhuǎn)換為加權(quán)K-means聚類問題，從而在保證同等質(zhì)量的前提下降低了時(shí)間復(fù)雜度。在完成最后一步的譜聚類后，可以獲得Nc個(gè)軌跡聚類。

3.2 獲取聚類原型

在集成聚類之后，訓(xùn)練數(shù)據(jù)中的每一條軌跡都將擁有聚類標(biāo)簽，但是這些軌跡聚類的數(shù)目與實(shí)際路徑的數(shù)目不一致。主要原因在于在不同場(chǎng)景中，并不知道真實(shí)的路徑個(gè)數(shù)Nr，只能保證指定的聚類數(shù)目Nc>>Nr，即聚類可能存在冗余。為此，需要對(duì)聚類后的軌跡進(jìn)行進(jìn)一步處理，以獲得場(chǎng)景中實(shí)際的路徑數(shù)目Nr。

軌跡聚類的合并分為兩步:(1) 針對(duì)每一個(gè)聚類的軌跡，提取該軌跡的聚類原型，聚類原型為該聚類中最具有代表性的軌跡。(2) 利用聚類原型將相似的聚類合并，從而得到場(chǎng)景的路徑信息。

在聚類原型提取中，一般選取同一聚類的平均軌跡作為聚類的代表，即聚類原型。軌跡的平均需要將聚類內(nèi)的軌跡進(jìn)行插值得到等長(zhǎng)軌跡才能進(jìn)行。Morris等[9]借助插值的策略提取了平均軌跡，并基于平均軌跡間的DTW距離對(duì)聚類進(jìn)行了合并。以平均軌跡作為聚類原型會(huì)帶來兩個(gè)問題：(1) 聚類不可避免地會(huì)包含少量的噪聲軌跡或是分類錯(cuò)誤的軌跡，若是該聚類樣本數(shù)目比較小，則會(huì)對(duì)平均軌跡的質(zhì)量產(chǎn)生較大的影響；(2) 平均法對(duì)軌跡的平移，伸縮變換不具有魯棒性。Paparrizos等[16]討論了針對(duì)時(shí)間序列聚類中的聚類中心提取問題，提出若是對(duì)時(shí)間序列進(jìn)行時(shí)間方向的平移或是伸縮變換，則平均的時(shí)間序列將不具有穩(wěn)定性，這里針對(duì)軌跡也是一樣的效果。針對(duì)這些問題，本文引入圖的拉普拉斯能量的思想[11]，對(duì)聚類原型進(jìn)行提取。

圖G的拉普拉斯能量：給定圖G的鄰接矩陣A和度矩陣D，計(jì)算拉普拉斯矩陣L=D-A，則圖G的拉普拉斯能量定義為：

(16)

式中：λ1,λ2,…,λM是拉普拉斯矩陣的特征值。

圖G的節(jié)點(diǎn)vi的拉普拉斯中心性：給定圖G，刪除連接節(jié)點(diǎn)vi的所有邊之后的圖記為Gi，則給定節(jié)點(diǎn)vi∈G的拉普拉斯中心性hi定義為：

(17)

3.3 路徑生成

Kij=I(Edit(Pi,Pj)≥ηe)

(18)

式中：I(·)代表指示函數(shù)；Edit(Pi,Pj)代表編輯距離[22]。采用編輯距離是因?yàn)榫庉嬀嚯x能夠被很好地歸一化到0到1的區(qū)間，方便ηe的取值。在獲取矩陣K之后，使用深度優(yōu)先搜索對(duì)連通子圖進(jìn)行搜索，屬于同一子圖的聚類將被合并在一起，并重新根據(jù)軌跡屬于路徑的情況提取聚類原型。本文ηe的取值為0.9，代表聚類原型之間至少有90%的點(diǎn)匹配時(shí)，才將二者進(jìn)行合并，這也意味著給定嚴(yán)格的合并條件能取得魯棒的效果。

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

4.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

針對(duì)所提出的方法，采用西安市2個(gè)交叉口的軌跡數(shù)據(jù)進(jìn)行實(shí)驗(yàn)分析。實(shí)驗(yàn)環(huán)境為Ubuntu 18.04 LTS系統(tǒng)，處理器為Intel Xeon(R) E3-1230v3，內(nèi)存20 GB，軟件平臺(tái)使用到了基于Python的Anaconda集成環(huán)境。數(shù)據(jù)集的相關(guān)特性如表1所示。

表1 兩個(gè)軌跡數(shù)據(jù)集基本信息

圖6與圖7顯示了兩個(gè)場(chǎng)景中提取的路徑，可以看出場(chǎng)景具有非常復(fù)雜的運(yùn)動(dòng)模式。其中數(shù)據(jù)集JYGY采集于早高峰8點(diǎn)到9點(diǎn)左右，場(chǎng)景擁有24條路徑；HJDS數(shù)據(jù)集包含28條路徑。實(shí)驗(yàn)的評(píng)估標(biāo)準(zhǔn)采用的是V-measure[17]。V-measure是一種基于熵的聚類質(zhì)量度量，取值范圍在0到1之間。并且使用V-measure需要預(yù)先知道樣本的聚類標(biāo)簽與真實(shí)類標(biāo)簽，V-measure值越高越好。

圖6 JYGY數(shù)據(jù)集路徑(24條路徑)

圖7 HJDS數(shù)據(jù)集路徑(28條路徑)

4.2 軌跡集成聚類效果

針對(duì)軌跡數(shù)據(jù)集成聚類的效果進(jìn)行實(shí)驗(yàn)。首先對(duì)數(shù)據(jù)集分別進(jìn)行基于特征的聚類與基于距離度量的聚類，從而生成一系列的基聚類。每個(gè)方法聚類的數(shù)目從30個(gè)一直到50個(gè)，所以生成的基聚類的組數(shù)N=40。這樣保證了各個(gè)聚類的數(shù)目Nc大于場(chǎng)景潛在的路徑數(shù)目Nr。在獲得基聚類之后，利用所有獲得的基聚類，參照式(12)構(gòu)建了加權(quán)聯(lián)合相關(guān)矩陣，并運(yùn)用譜聚類對(duì)其進(jìn)行聚類，獲取了集成聚類的類標(biāo)簽。對(duì)于集成聚類而言，其聚類的數(shù)目從30個(gè)變化到50個(gè)，方便與之前的結(jié)果進(jìn)行對(duì)比。并且針對(duì)基于距離度量的聚類算法與基于特征的聚類算法也進(jìn)行了集成，用以驗(yàn)證集成聚類的效果并非只受到單一聚類方式集成的影響。

圖8是聚類數(shù)目從30變化到50的時(shí)候，各組方法的V-measure分?jǐn)?shù)的變化情況。可以看出，單獨(dú)使用結(jié)合DTW距離的譜聚類時(shí)，其聚類效果并不穩(wěn)定，隨著聚類個(gè)數(shù)的變化聚類分?jǐn)?shù)發(fā)生波動(dòng)，這主要是由于對(duì)于鄰接矩陣的高斯核參數(shù)調(diào)整不當(dāng)造成的。但是對(duì)其進(jìn)行集成聚類之后，其聚類效果與穩(wěn)定性都有大幅的提升，這也說明聚類集成能夠提升聚類質(zhì)量。就聚類分?jǐn)?shù)而言，軌跡的特征工程配合層次聚類的方法取得的結(jié)果最為穩(wěn)定，隨著聚類數(shù)目的變化，其V-measure分?jǐn)?shù)沒有發(fā)生太大的波動(dòng)。但是事實(shí)上該方法在設(shè)計(jì)損失函數(shù)時(shí)，沒有對(duì)聚類包含的樣本數(shù)目進(jìn)行約束，因此容易受到噪聲的影響從而切分出單條軌跡作為聚類，并且由于前者的原因，基聚類之間的差異性也較低，導(dǎo)致集成結(jié)果不明顯。對(duì)于兩種方法結(jié)合的集成聚類算法，在聚類效果上與基于特征的集成結(jié)果類似，但是其集成后分?jǐn)?shù)的穩(wěn)定性高，并在部分指定聚類數(shù)目下超越了之前的所有方法。

(a) JYGY數(shù)據(jù)集聚類結(jié)果

(b) HJDS數(shù)據(jù)集聚類結(jié)果圖8 兩個(gè)數(shù)據(jù)集的聚類結(jié)果

集成聚類對(duì)低質(zhì)量聚類的加入也具有較高的魯棒性。圖9是通過調(diào)整超參數(shù)，降低譜聚類分?jǐn)?shù)之后得到的集成的結(jié)果。可以看到在譜聚類結(jié)果的質(zhì)量較低的情況下，集成的結(jié)果仍然保持了非常高的準(zhǔn)確性，表明二者結(jié)合的集成策略具有較高的精度與魯棒性。

圖9 HJDS數(shù)據(jù)集聚類融合低質(zhì)聚類的結(jié)果

4.3 路徑生成實(shí)驗(yàn)

在獲取了軌跡的各個(gè)聚類之后，對(duì)各個(gè)聚類的聚類原型進(jìn)行了提取。這里已經(jīng)獲取了聚類的標(biāo)簽，因此可以依據(jù)聚類標(biāo)簽對(duì)實(shí)現(xiàn)進(jìn)行譜聚類的鄰接矩陣A進(jìn)行分解為子圖的鄰接矩陣，并按照式(17)，計(jì)算子圖每一結(jié)點(diǎn)的拉普拉斯中心性，選取中心性最高的軌跡作為聚類的聚類原型。

圖10與圖11分別為兩個(gè)場(chǎng)景下的任意5個(gè)軌跡聚類與其聚類原型。聚類原型通常為聚類最具代表性的軌跡，例如聚類的平均軌跡。若將每一條聚類中的軌跡視為圖中的一個(gè)節(jié)點(diǎn)，則聚類原型理應(yīng)與聚類中其他節(jié)點(diǎn)之間的連接的權(quán)值之和低，一般來說，這樣的節(jié)點(diǎn)應(yīng)當(dāng)位于聚類的中心。由圖10與圖11可以看出，算法很好地找到了每一個(gè)聚類的中心，并抵御了噪聲軌跡的干擾。

圖10 JYGY數(shù)據(jù)集中的5個(gè)聚類與其聚類原型

圖11 HJDS數(shù)據(jù)集中的5個(gè)聚類原型

在獲取了各個(gè)軌跡聚類的聚類原型之后，便可以進(jìn)行聚類原型的合并以獲得場(chǎng)景的路徑信息。為了對(duì)比集成方法對(duì)于場(chǎng)景路徑獲取的有效性，我們通過實(shí)驗(yàn)對(duì)比了各個(gè)方法聚類合并的效果。具體而言，定義命中率(HR)與冗余率(RR)：

(19)

(20)

式(19)中:Nr代表場(chǎng)景實(shí)際路徑的數(shù)目，Nc代表聚類原型的數(shù)目，Nh代表Nc中能夠與場(chǎng)景實(shí)際路徑匹配的聚類原型的個(gè)數(shù)。判斷是否匹配的方式為對(duì)比合并以后的路徑與真實(shí)路徑的編輯距離是否小于預(yù)設(shè)閾值，這里閾值被設(shè)定為0.9以確保試驗(yàn)結(jié)果的可靠性。HR∈[0,1]越高越好，RR代表合并以后剩余的或是缺失路徑的比率，越接近0越好。

表2是設(shè)定不同數(shù)據(jù)集、聚類方法與聚類數(shù)目的條件下，路徑合并后的命中率與冗余率情況。其中集成聚類字樣代表路徑的提取方式為先進(jìn)行集成聚類，從集成聚類的結(jié)果中提取聚類原型，然后進(jìn)行聚類合并的操作，以下簡(jiǎn)稱為集成方式；帶有特征聚類或是距離字樣的聚類方式和前述相似，只是獲取聚類的手段是之前提到的基于特征的聚類和基于距離度量的聚類方式，以下分別簡(jiǎn)稱為距離方式與特征方式。

表2 不同聚類數(shù)目，不同數(shù)據(jù)集下的路徑提取命中率(HR)/冗余率(RR)

從結(jié)果上來看，就路徑提取的命中率而言，集成方式與距離方式具有相似的命中率；而特征方式V-measure的分?jǐn)?shù)較高，但是由于忽略了軌跡的時(shí)序特性，導(dǎo)致對(duì)于路徑的提取效果不論是命中率還是冗余率都不如前兩種方式。而在JYGY數(shù)據(jù)集上，經(jīng)典方式提取的命中率高于集成方式，但是冗余率遠(yuǎn)高于集成方式，若是考慮低冗余和高命中的話，本文的集成聚類具有較強(qiáng)的優(yōu)勢(shì)。

5 結(jié) 語

本文提出了一種基于集成聚類的交叉口路徑信息挖掘方法。利用基于距離度量的譜聚類算法與基于特征的層次聚類算法的集成，對(duì)軌跡進(jìn)行聚類；針對(duì)軌跡的相似性鄰接矩陣，引入了拉普拉斯中心性的思想提取了聚類的中心結(jié)點(diǎn)。在多個(gè)數(shù)據(jù)集實(shí)驗(yàn)中，本文提出的聚類方法具有較強(qiáng)的魯棒性與較高的精度。在提取路徑的實(shí)驗(yàn)中，在不降低命中率前提下本文方法具有較低的冗余率。但是，其在時(shí)間復(fù)雜度方面有待進(jìn)一步改進(jìn)。