基于密度核心的出租車載客軌跡聚類算法

田智慧，馬占宇，魏海濤

（1.鄭州大學(xué)信息工程學(xué)院，鄭州 450001；2.鄭州大學(xué)地球科學(xué)與技術(shù)學(xué)院，鄭州 450052）

0 概述

近年來，數(shù)據(jù)挖掘、無線通信、移動(dòng)定位等技術(shù)發(fā)展迅速，持有GPS定位信息的移動(dòng)設(shè)備以及基于位置信息服務(wù)（Location Information Service，LBS）的終端應(yīng)用產(chǎn)生了海量時(shí)空軌跡數(shù)據(jù)［1］。這些時(shí)空數(shù)據(jù)蘊(yùn)含著豐富的語義信息，可用于提取移動(dòng)對象的運(yùn)動(dòng)特征模式和預(yù)測移動(dòng)對象的運(yùn)動(dòng)行為［2-4］，已成為目前空間數(shù)據(jù)挖掘方面［5-7］的研究熱點(diǎn)。軌跡大數(shù)據(jù)可以分為兩大類：一類是由出租車以及其他攜帶GPS交通工具生成的坐標(biāo)序列；另一類是移動(dòng)物體利用特殊裝置（如信號基站、連接WiFi信號）而產(chǎn)生的帶有時(shí)間戳的地點(diǎn)坐標(biāo)序列［8］等。這些軌跡數(shù)據(jù)包含行人的出行規(guī)律［9］、交通擁堵規(guī)律［10］和社會(huì)活動(dòng)模式等信息。軌跡聚類的目的是挖掘軌跡大數(shù)據(jù)的移動(dòng)模式，通過分析聚類結(jié)果得到移動(dòng)對象的出行規(guī)律。其中，研究出租車軌跡聚類對城市規(guī)劃和管理、出租車調(diào)度以及城市發(fā)展具有積極意義。

文獻(xiàn)［11］提出了移動(dòng)微聚類（Moving Micro Clustering，MMC）的概念，通過應(yīng)用BIRCH算法中的微聚類思想來改進(jìn)移動(dòng)對象的聚類過程，并利用聚類特征描述MMC的特征信息。文獻(xiàn)［12］對OPTICS算法加以改進(jìn)，提出一種基于時(shí)間維度的T-OPTICS軌跡聚類算法。該算法增加了軌跡的時(shí)間語義信息，提高了聚類結(jié)果在時(shí)間維度的準(zhǔn)確性。文獻(xiàn)［13］構(gòu)建分段及歸組軌跡聚類框架TRACLUS，利用提取到的軌跡特征點(diǎn)將軌跡分為多段，使粒度更細(xì)致，在此基礎(chǔ)上利用DBSCAN聚類算法再進(jìn)行歸組，以避免丟失部分軌跡信息。但是DBSCAN聚類算法對參數(shù)敏感，需要利用專家先驗(yàn)知識(shí)獲得參數(shù)并反復(fù)調(diào)整得到最優(yōu)值。文獻(xiàn)［14］提出基于路網(wǎng)的聚類算法框架NETSCAN，將路段聚類為一組密集路徑簇后，再根據(jù)密集路徑之間的相似性度量對軌跡進(jìn)行聚類。文獻(xiàn)［15］提出一種基于MFTSM的軌跡聚類算法，利用基于區(qū)域計(jì)算的位置距離解決軌跡的連續(xù)性問題。文獻(xiàn)［16］提出一種T-CLUS軌跡聚類方法，在將原始軌跡劃分成粒度較小的子段后再進(jìn)行聚類，得到子軌跡對象的增廣聚類序列，根據(jù)可達(dá)距離圖分析不同參數(shù)的聚類效果。文獻(xiàn)［17］提出一種基于結(jié)構(gòu)相似度的軌跡聚類算法，通過提取軌跡方向、速度、轉(zhuǎn)角和位置等組成的結(jié)構(gòu)特征信息計(jì)算相似性度量，并基于結(jié)構(gòu)相似性度量進(jìn)行軌跡聚類。文獻(xiàn)［18］在聚類算法上采用外包矩形作為核心軌跡的搜索鄰域，同時(shí)重新定義軌跡核心距離與軌跡可達(dá)距離，通過鄰接表代替空間索引，從而降低算法的復(fù)雜度。

現(xiàn)有的軌跡聚類大多基于DBSCAN、OPTICS和K-means等算法，聚類時(shí)需要計(jì)算所有軌跡或者軌跡段相互間的相似性距離，在面向海量出租車載客軌跡數(shù)據(jù)時(shí)會(huì)消耗大量的計(jì)算資源，降低算法效率。本文通過引入密度核心［19］的概念，提出一種新的載客軌跡聚類算法。計(jì)算軌跡點(diǎn)的變向角和速度，根據(jù)變向角閾值、累積變向角閾值和速度閾值提取軌跡特征點(diǎn)，以減少軌跡的數(shù)據(jù)量，加快計(jì)算速度。同時(shí)，根據(jù)聚類節(jié)點(diǎn)中致密核心軌跡與參與聚類軌跡的相似度距離判斷軌跡的匹配程度，從而聚合相似軌跡，提高聚類的執(zhí)行效率。

1 軌跡數(shù)據(jù)處理

1.1 車輛軌跡模型

出租車軌跡數(shù)據(jù)一般包含出租車營運(yùn)設(shè)備編號（ID）、經(jīng)緯度信息、出租車營運(yùn)狀態(tài)、衛(wèi)星定位時(shí)間和車輛速度等屬性，表1給出了出租車軌跡數(shù)據(jù)的部分屬性信息。根據(jù)營運(yùn)狀態(tài)可將出租車軌跡分為載客軌跡和空載軌跡。載客時(shí)出租車營運(yùn)狀態(tài)記為1，空載時(shí)出租車營運(yùn)狀態(tài)記為0。為研究出租車在不同營運(yùn)狀態(tài)下的移動(dòng)模式，本文以載客軌跡為研究對象。同時(shí)為更好地描述軌跡，對軌跡及其相關(guān)屬性進(jìn)行形式化描述。以TD表示載客軌跡集合，TD=｛T1，T2，…，TN｝。載客軌跡T是由出租車在連續(xù)的時(shí)間段內(nèi)行駛生成的載客軌跡點(diǎn)組成的集合，表示為T=｛pi|1≤i≤n｝，其中，n為出租車載客軌跡點(diǎn)的個(gè)數(shù)，pi為載客軌跡點(diǎn)。軌跡點(diǎn)pi是由經(jīng)度、維度和時(shí)間戳組成的三元組，表示為pi=（latitude，longitude，timestamp）。

表1 出租車軌跡屬性信息Table 1 Attribute information of taxi trajectory

1.2 軌跡清洗

出租車在行駛過程中，所獲取GPS信息的準(zhǔn)確度會(huì)受到各種地理環(huán)境或者天氣因素的影響，生成的軌跡數(shù)據(jù)可能會(huì)包含一些噪聲數(shù)據(jù)（如偏移點(diǎn)、回溯點(diǎn)和丟失點(diǎn)）。如圖1所示，出租車在軌跡點(diǎn)p7偏離正確軌跡方向。由于噪聲數(shù)據(jù)會(huì)影響軌跡聚類的精度，因此需要對軌跡數(shù)據(jù)進(jìn)行降噪處理。軌跡降噪的目的就是尋找到軌跡原始數(shù)據(jù)中的噪聲數(shù)據(jù)并對其進(jìn)行平滑處理，以此消除噪聲值。本文采用卡爾曼濾波法對出租車軌跡數(shù)據(jù)進(jìn)行降噪處理?？柭鼮V波模型是一種線性最優(yōu)濾波器，本文利用該模型構(gòu)建一個(gè)預(yù)測模型，以準(zhǔn)確反映出租車軌跡前一個(gè)狀態(tài)和當(dāng)前狀態(tài)的關(guān)系。在此基礎(chǔ)上，根據(jù)噪聲點(diǎn)的誤差值對出租車軌跡進(jìn)行清洗，最終消除噪聲點(diǎn)。

圖1 噪聲數(shù)據(jù)示意圖Fig.1 Schematic diagram of noise data

1.3 軌跡特征點(diǎn)提取

出租車在行駛過程中，GPS采樣的頻率較高，導(dǎo)致軌跡中存在大量的冗余數(shù)據(jù)點(diǎn)，這些重復(fù)的軌跡點(diǎn)在進(jìn)行存儲(chǔ)和計(jì)算時(shí)會(huì)消耗大量的資源。提取軌跡特征點(diǎn)的目的是在保證軌跡形狀基本不變的情況下盡可能減少重復(fù)軌跡點(diǎn)的個(gè)數(shù)。目前的軌跡特征點(diǎn)提取方法主要是選取道路交匯口軌跡采樣點(diǎn)和方向變化較大的軌跡采樣點(diǎn)，如文獻(xiàn)［16-18］方法，其選擇軌跡點(diǎn)方向變化超過預(yù)先設(shè)置的角度閾值的采樣點(diǎn)作為特征點(diǎn)。這種方法雖然可以選取到有價(jià)值的關(guān)鍵點(diǎn)，但忽略了軌跡方向的累積變化對特征點(diǎn)選取的影響。當(dāng)角度閾值設(shè)置過大時(shí)，在選取軌跡特征點(diǎn)的過程中會(huì)丟失部分有價(jià)值的軌跡采樣點(diǎn)。如圖2所示，由于載客軌跡的所有變向角{θ1，θ2，θ3，θ4，θ5，θ6}都小于角度閾值，因此這些采樣點(diǎn)不能被選取為軌跡特征點(diǎn)，顯然軌跡丟失了部分特征點(diǎn)。為解決這一問題，本文在角度閾值的基礎(chǔ)上增加了累積角度閾值和速度閾值，以更精準(zhǔn)地選取軌跡的特征點(diǎn)，如圖3所示。

圖2 累積變向角Fig.2 Cumulative turning angles

圖3 軌跡特征點(diǎn)Fig.3 Trajectory feature points

相鄰軌跡采樣點(diǎn)p1～p3的速度分別表示為軌跡點(diǎn)p2的夾角表示為α，軌跡段長度a、b、c表示軌跡點(diǎn)p2鄰邊和對邊的長度，夾角α的計(jì)算公式如下：

軌跡點(diǎn)的變向角反映了軌跡運(yùn)動(dòng)的變化趨勢。軌跡采樣點(diǎn)p2、p3的變向角分別表示為θ1和θ2。為便于軌跡運(yùn)動(dòng)趨勢的相似度計(jì)算，指定外向角θ1為正值，內(nèi)向角θ2為負(fù)值。由式（1）可以得到變向角θ的計(jì)算式如下：

軌跡采樣點(diǎn)的速度變化一定程度上反映了出租車軌跡的運(yùn)動(dòng)模式，軌跡采樣點(diǎn)pi的速度變化可用式（3）表示：

軌跡特征點(diǎn)提取是軌跡聚類的基礎(chǔ)，影響到軌跡聚類的準(zhǔn)確率和執(zhí)行效率。本文借鑒文獻(xiàn)［17］中的角度閾值算法并加以改進(jìn)，在角度閾值的基礎(chǔ)上增加累積角度閾值和速度閾值，以更精準(zhǔn)地保留軌跡的細(xì)節(jié)信息。本文設(shè)計(jì)的特征點(diǎn)提取算法步驟如下：

步驟1遍歷軌跡中的點(diǎn)序列，提取道路交匯點(diǎn)作為軌跡的特征點(diǎn)，利用式（1）、式（2）計(jì)算軌跡點(diǎn)的變向角，選取變向角大于ω1的軌跡點(diǎn)確定為軌跡特征點(diǎn)。

步驟2如果軌跡點(diǎn)累積的變向角大于累積變向角閾值ω2，那么該點(diǎn)也會(huì)被保留為特征點(diǎn)。在此基礎(chǔ)上，利用式（3）計(jì)算軌跡點(diǎn)的變速大小選取大于速度閾值ε的采樣點(diǎn)作為軌跡特征點(diǎn)，并將這些特征點(diǎn)組成的軌跡作為軌跡聚類的基礎(chǔ)單位。

2 基于密度核心的軌跡聚類算法

2.1 DSP距離

SP（Sum-of-Pairs）距離［20］表示兩條軌跡匹配點(diǎn)之間距離的總和，其要求兩條軌跡具有相同數(shù)量的點(diǎn)，并且按照兩條軌跡上點(diǎn)的順序一一對應(yīng)，將匹配點(diǎn)的距離求和作為軌跡相似性度量。由于該度量方法要求兩條具有相同點(diǎn)數(shù)量的軌跡，因此不適用于軌跡長度不同的出租車載客軌跡。本文對SP距離進(jìn)行改進(jìn)，提出DSP（Double Sum-of-Pairs）距離，在計(jì)算兩條軌跡的相似度時(shí)，根據(jù)每條軌跡自身的軌跡點(diǎn)去匹配另一條軌跡的點(diǎn)，每個(gè)軌跡點(diǎn)匹配到的是另一條軌跡上距離自己最小的軌跡點(diǎn)。因此，兩條軌跡相互之間匹配到的軌跡點(diǎn)并不相同。由于雙向計(jì)算軌跡相似度，避免了偶然性，因此可使匹配軌跡的相似度更精確。以軌跡TA和TB為例：軌跡TA到軌跡TB的距離如圖4（a）所示，以軌跡TA的每個(gè)點(diǎn)到軌跡TB中點(diǎn)的最短距離和的均值表示；軌跡TB到軌跡TA的距離如圖4（b）表示，以軌跡TB的每個(gè)點(diǎn)到軌跡TA中點(diǎn)的最短距離和的均值表示。

圖4 軌跡對之間的相互距離Fig.4 Mutual distance between trajectory pairs

DSP距離的形式化描述如下：給定兩條軌跡TA和TB，TA=｛p1，p2，…，pn｝，TB=｛q1，q2，…，qm｝。軌跡TA中任意一點(diǎn)pi到軌跡TB的距離定義為pi軌跡點(diǎn)與TB=｛q1，q2，…，qm｝中任意軌跡點(diǎn)的最小距離，如式（4）所示：

其中，q（j1≤j≤m）表示軌跡TB中的一個(gè)軌跡點(diǎn)。由于出租車軌跡的長度不同且受軌跡方向的影響，因此軌跡TB中的點(diǎn)qj到軌跡TA的距離不同于上述情況。軌跡TB中任意一點(diǎn)qj與軌跡TA的最小距離如式（5）所示：

定義軌跡TA到軌跡TB的距離dAB為TA中所有點(diǎn)到TB的距離和的均值，如式（6）所示：

同理可得軌跡TB到軌跡TA的距離dAB，如式（7）所示：

對dAB和dBA求和并取平均值可以得到DSP相似性度量，如式（8）所示：

2.2 C-Tra聚類算法

在傳統(tǒng)的DBSCAN、OPTICS等聚類算法中，查詢鄰域內(nèi)的軌跡對象數(shù)目需要掃描一次全部軌跡數(shù)據(jù)，軌跡聚合時(shí)需要再掃描一次全部數(shù)據(jù)，當(dāng)數(shù)據(jù)量增大時(shí)，聚類的時(shí)間效率就會(huì)大幅下降。為降低聚類算法的復(fù)雜度，本文提出一種新的聚類算法C-Tra。該算法定義聚類節(jié)點(diǎn)作為一種數(shù)據(jù)結(jié)構(gòu)來儲(chǔ)存聚類過程中生成的聚類簇，每一個(gè)節(jié)點(diǎn)儲(chǔ)存一個(gè)類簇。所有的聚類節(jié)點(diǎn)構(gòu)成軌跡聚類集合，如式（9）所示：

聚類節(jié)點(diǎn)包含類簇的細(xì)節(jié)信息，由軌跡列表CTrList、致密核心軌跡h、軌跡數(shù)量n構(gòu)成，如式（10）所示：

其中，軌跡列表CTrList為聚類簇中所有軌跡組成的集合，如式（11）所示，列表中的軌跡隨著聚類過程滿足聚類條件而動(dòng)態(tài)增加，直到聚類完成，軌跡列表停止更新。

聚類節(jié)點(diǎn)中的致密核心軌跡h是軌跡密度最高的軌跡，軌跡Ti的軌跡密度如式（12）所示：

其中：Tj表示聚類簇中的其他軌跡；當(dāng)x＜0時(shí)，χ(x)=1，而在其他情況下，χ(x)=0；dc為截至距離。

在本文設(shè)計(jì)的C-Tra算法中，參與聚類的軌跡T與每一個(gè)聚類節(jié)點(diǎn)的致密核心軌跡的相似度距離集合如式（13）所示：

在simlist集合中，最小的相似度距離si如果小于聚類閾值，則軌跡T可分配到此距離對應(yīng)的聚類節(jié)點(diǎn)中。當(dāng)所有參與聚類的軌跡聚合到對應(yīng)的聚類節(jié)點(diǎn)，即完成軌跡聚類。在C-Tra聚類算法中，聚類節(jié)點(diǎn)的致密核心軌跡需要?jiǎng)討B(tài)確定，每當(dāng)有新的軌跡添加到聚類節(jié)點(diǎn)中，節(jié)點(diǎn)就會(huì)根據(jù)軌跡列表中全部軌跡的密度重新確定致密核心軌跡，以保證聚類結(jié)果的準(zhǔn)確性。

C-Tra聚類算法的偽代碼如下：

該算法的具體步驟如下：

步驟1選擇參與聚類的第一個(gè)軌跡T1并將其放入第一個(gè)聚類節(jié)點(diǎn)c1中（［T1］，T1，1），此時(shí)聚類節(jié)點(diǎn)的數(shù)量M=1（見算法第1行～第3行）。

步驟2選擇軌跡列表中的軌跡線T（ii=1，2，…，N），分別計(jì)算軌跡Ti和所有聚類節(jié)點(diǎn)c（kk=1，2，…，M）的致密核心軌跡hk的相似度軌跡距離，選擇相似度d=最小的聚類節(jié)點(diǎn)cF。（見算法第4行～第10行）

步驟3如果d小于聚類閾值θ，則將Ti添加到聚類節(jié)點(diǎn)c（F見算法第11行～第18行）。

步驟4如果d不小于聚類閾值θ，則創(chuàng)建一個(gè)新的聚類簇cM（［T］i，Ti，1），M=M+1（見算法第19行～第23行）。

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

為驗(yàn)證C-Tra聚類算法的性能，在河南省超算中心的CPU節(jié)點(diǎn)上進(jìn)行實(shí)驗(yàn)。該節(jié)點(diǎn)擁有2顆CPU處理器，內(nèi)存為128 GB。實(shí)驗(yàn)數(shù)據(jù)為鄭州市出租車GPS軌跡數(shù)據(jù)，時(shí)間為2017年2月26日，這些數(shù)據(jù)是1.2萬余輛出租車的GPS記錄，每條記錄包含約30個(gè)字段信息，包括經(jīng)緯度、狀態(tài)、速度、方向、溫度、濕度等。經(jīng)過對軌跡數(shù)據(jù)的預(yù)處理，選取設(shè)備編號、運(yùn)營狀態(tài)、緯度、經(jīng)度、時(shí)間戳這五個(gè)屬性存儲(chǔ)在ORACLE 11g中進(jìn)行實(shí)驗(yàn)。

3.1 特征點(diǎn)提取前后的存儲(chǔ)空間對比

依次選取不同數(shù)量的載客軌跡數(shù)據(jù)，如表2所示，將這些軌跡數(shù)據(jù)在提取特征點(diǎn)前后分別存儲(chǔ)于.txt文件中。選取參數(shù)ω1=25、ω2=60、ε=65提取軌跡特征點(diǎn)。特征點(diǎn)提取前后軌跡數(shù)據(jù)存儲(chǔ)空間對比如表2所示。可以看出，通過提取特征點(diǎn)能夠大幅降低軌跡存儲(chǔ)的數(shù)據(jù)量，減小內(nèi)存空間的消耗。

表2 特征點(diǎn)提取前后存儲(chǔ)空間對比Table 2 Comparison of storage space before and after feature point extraction

3.2 聚類結(jié)果與效率評價(jià)

C-Tra聚類算法的特性是快速高效，適用于大數(shù)據(jù)量的載客軌跡。本文選擇鄭州市2017年2月26日午高峰（11：00—14：00）的出租車軌跡數(shù)據(jù)，選取其中10 000條軌跡作為實(shí)驗(yàn)數(shù)據(jù)集進(jìn)行驗(yàn)證。對本文C-Tra算法與TRACLUS、OPTICS算法的實(shí)驗(yàn)結(jié)果進(jìn)行對比。表3列出了3種算法的時(shí)間復(fù)雜度，其中，M表示聚類簇的數(shù)目。圖5給出了3種算法的聚類效果，可以看出，本文算法可以實(shí)現(xiàn)對載客軌跡的聚類，且聚類的軌跡更加集中，聚類效果更為明顯。由于本文算法使用整體軌跡進(jìn)行聚類，因此聚類后軌跡的長度較長，保留了軌跡的整體信息，能夠準(zhǔn)確反映載客軌跡的熱點(diǎn)路徑。

表3 3種算法的時(shí)間復(fù)雜度對比Table 3 Comparison of time complexity of three algorithms

圖5 3種算法的聚類效果對比Fig.5 Comparison of clustering effect of three algorithms

3種算法在出租車載客數(shù)據(jù)實(shí)驗(yàn)時(shí)的相關(guān)參數(shù)和運(yùn)行時(shí)間如表4所示?？梢钥闯觯鄬τ赥RACLUS和OPTICS算法，C-Tra算法具有更高的執(zhí)行效率。

表4 3種算法的參數(shù)設(shè)置和運(yùn)行時(shí)間對比Table 4 Comparison of parameter setting and running time of three algorithms

4 結(jié)束語

本文研究出租車載客軌跡聚類問題，考慮載客軌跡特性并從提高算法執(zhí)行效率角度出發(fā)，提出具有線性復(fù)雜度的聚類算法C-Tra。根據(jù)軌跡的方向和速度提取特征點(diǎn)以精簡軌跡，通過改進(jìn)SP距離使算法適用于長度不同的出租車載客軌跡，同時(shí)利用致密核心軌跡計(jì)算動(dòng)態(tài)聚類節(jié)點(diǎn)的核心軌跡，完成軌跡聚類。實(shí)驗(yàn)結(jié)果表明，與TRACLUS和OPTICS算法相比，本文算法對于出租車軌跡聚類具有較高的執(zhí)行效率，可為城市規(guī)劃管理和交通擁堵治理提供借鑒。