田智慧，馬占宇，魏海濤

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

0 概述

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

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

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

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

1.1 車輛軌跡模型

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

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

1.2 軌跡清洗

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

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

1.3 軌跡特征點提取

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

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

圖3 軌跡特征點Fig.3 Trajectory feature points

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

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

軌跡采樣點的速度變化一定程度上反映了出租車軌跡的運動模式，軌跡采樣點pi的速度變化可用式（3）表示：

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

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

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

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

2.1 DSP距離

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

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

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

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

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

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

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

2.2 C-Tra聚類算法

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

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

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

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

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

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

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

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

該算法的具體步驟如下：

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

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

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

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

3 實驗與結(jié)果分析

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

3.1 特征點提取前后的存儲空間對比

依次選取不同數(shù)量的載客軌跡數(shù)據(jù)，如表2所示，將這些軌跡數(shù)據(jù)在提取特征點前后分別存儲于.txt文件中。選取參數(shù)ω1=25、ω2=60、ε=65提取軌跡特征點。特征點提取前后軌跡數(shù)據(jù)存儲空間對比如表2所示?？梢钥闯觯ㄟ^提取特征點能夠大幅降低軌跡存儲的數(shù)據(jù)量，減小內(nèi)存空間的消耗。

表2 特征點提取前后存儲空間對比Table 2 Comparison of storage space before and after feature point extraction

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

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

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

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

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

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

4 結(jié)束語

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