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

田智慧，馬占宇，魏海濤

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

0 概述

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

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

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

1 軌跡數據處理

1.1 車輛軌跡模型

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

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

1.2 軌跡清洗

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

圖1 噪聲數據示意圖Fig.1 Schematic diagram of noise data

1.3 軌跡特征點提取

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

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

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

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

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

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

2.1 DSP距離

SP（Sum-of-Pairs）距離［20］表示兩條軌跡匹配點之間距離的總和，其要求兩條軌跡具有相同數量的點，并且按照兩條軌跡上點的順序一一對應，將匹配點的距離求和作為軌跡相似性度量。由于該度量方法要求兩條具有相同點數量的軌跡，因此不適用于軌跡長度不同的出租車載客軌跡。本文對SP距離進行改進，提出DSP（Double Sum-of-Pairs）距離，在計算兩條軌跡的相似度時，根據每條軌跡自身的軌跡點去匹配另一條軌跡的點，每個軌跡點匹配到的是另一條軌跡上距離自己最小的軌跡點。因此，兩條軌跡相互之間匹配到的軌跡點并不相同。由于雙向計算軌跡相似度，避免了偶然性，因此可使匹配軌跡的相似度更精確。以軌跡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聚類算法

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

聚類節點包含類簇的細節信息，由軌跡列表CTrList、致密核心軌跡h、軌跡數量n構成，如式（10）所示：

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

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

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

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

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

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

該算法的具體步驟如下：

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

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

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

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

3 實驗與結果分析

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

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

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

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

3.2 聚類結果與效率評價

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

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

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

3種算法在出租車載客數據實驗時的相關參數和運行時間如表4所示。可以看出，相對于TRACLUS和OPTICS算法，C-Tra算法具有更高的執行效率。

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

4 結束語

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