基于群組與密度的軌跡聚類算法

俞慶英，趙亞軍，葉梓彤，胡 凡，夏 蕓

（1.安徽師范大學計算機與信息學院，安徽蕪湖 241002；2.安徽師范大學網絡與信息安全安徽省重點實驗室，安徽蕪湖 241002）

0 概述

隨著定位、通信和存儲技術的快速發展，車輛行駛軌跡數據、用戶活動軌跡數據以及颶風軌跡數據等大量移動對象的軌跡數據可被搜集和存儲。軌跡數據中包含豐富的時空語義信息，從中可挖掘出眾多有價值的信息［1-2］。聚類分析是常用的數據挖掘方法，其被廣泛用于圖像分析［3］、模式識別［4］、知識發現［5］以及生物信息學［6］等領域。近年來，研究人員針對不同的應用領域提出多種聚類算法，主要包括以BIRCH 為代表的基于層次的聚類算法［7］、以STING為代表的基于網格的聚類算法［8］、以K-means 為代表的基于劃分的聚類算法［9-10］，以及以DBSCAN 為代表的基于密度的聚類算法［11-12］。然而上述算法主要用于點數據的聚類，不能直接用于軌跡數據的聚類。

對軌跡數據聚類可獲得移動對象的代表性路徑，從而掌握其周期性行為規律［13］。由于軌跡數據中包含大量時間、空間和形狀等固有特征信息，因此大部分軌跡聚類方法先進行基于軌跡數據對象的相似性度量，再通過改進傳統聚類算法來實現軌跡數據聚類。例如，目前使用最廣泛的TRACLUS［14］軌跡聚類算法先基于軌跡分段進行相似性度量，再利用傳統DBSCAN 算法實現軌跡聚類。DBSCAN 算法可形成任意形狀的簇并能有效處理噪聲點，但由于該算法在執行過程中會重復遍歷整個數據集來搜索某個樣本的鄰域集合，因此處理大數據集的耗時較長，時間復雜度為O（n2），并需要較大內存和I/O 開銷。針對該問題，研究人員采用R-樹［15］、KD-樹［16］等空間索引方法降低鄰域集合搜索所需計算次數來減少算法的時間開銷，但空間索引方法實現較困難，且不適用于高維數據集。

針對上述問題，本文提出一種基于改進鄰域搜索技術的聚類算法。對軌跡進行分段預處理找出具有較高相似度的子軌跡段，通過遍歷整個軌跡數據集將其分為不同的群組，采用群組搜索代替距離計算減少鄰域對象搜索的計算次數，以縮短算法在海量軌跡數據集上的運行時間。

1 相關工作

本文以TRACLUS 算法中相似性度量方法為基礎，通過改進DBSCAN 算法來實現軌跡聚類，以下對DBSCAN 算法的相關工作進行介紹。

DBSCAN 算法是一種基于密度的空間聚類算法，其本質是尋找密度相連點的最大集合，能有效濾除低密度點區域，將高密度區域劃分為簇，并在具有噪聲點的數據中發現任意形狀的簇。研究人員基于DBSCAN 算法的上述特性，對其不斷改進與創新，并將研究成果應用于多個領域。

DBSCAN 算法需要人為確定半徑參數ε和鄰域密度閾值MinPts，這兩個參數能否合理選取對聚類結果影響較大，然而目前DBSCAN 算法無法在多密度情況下設置參數。對此，文獻［17］提出一種初始點優化與參數自適應的改進DBSCAN 算法，其能為不同密度的簇自適應設置不同參數，并優先對高密度簇進行聚類，即實現對多密度數據集的聚類。文獻［18］通過改進DBSCAN 算法得到EXDBSCAN 聚類算法，可用于多密度數據集且只需輸入一個參數。文獻［19］結合DBSCAN 算法和粒子群算法提出改進算法，其可基于數據集自動生成參數并有效進行空間熱點識別。

將DBSCAN 算法及其改進算法應用于軌跡數據集的處理也是研究熱點之一。由于大部分軌跡數據集規模龐大且數據量豐富，因此提高DBSCAN 算法的計算效率非常重要。文獻［20］提出一種可用于多密度數據集的RNN-DBSCAN 聚類算法，利用逆鄰域計數和權值剪枝方法使算法的時間復雜度由O（n2）降為O（n）。文獻［21］開發出DBSCAN 算法的分布式應用，在不影響聚類效果的情況下，使該算法在大規模數據集上實用性更強。文獻［22］在提高DBSCAN 算法實時性的基礎上，使用KD-樹和Spark GraphX 分布式圖處理框架，能顯著減少數據集中樣本之間距離的計算量，在大規模數據集上耗時更短。文獻［23］結合MapReduce 分布式計算框架和Hadoop 平臺，有效提高DBSCAN 算法在大規模數據集上的運行效率。文獻［24］提出一種用于處理時空軌跡數據的HDBSCAN 算法，其考慮到傳統聚類算法未考慮的軌跡先后性和內在層次，所得聚類結果更合理。文獻［25］提出一種基于軌跡數據密度分區的分布式并行聚類算法，構建可分布式并行聚類的局部數據集，在不同服務器上執行DBSCAN 算法進行局部聚類，然后對聚類結果進行合并和整合，通過并行處理提高了聚類分析效率。

在上述基于DBSCAN 的改進算法中，分布式圖處理框架和KD-樹等空間索引方法均較難實現，且空間索引樹較難應用于高維軌跡數據集。為此，本文提出一種基于群組和密度的軌跡聚類算法TraG-DBSCAN，以DBSCAN 算法為基礎，使用群組劃分方法減少聚類算法中鄰域對象搜索所需時間，從而提高算法實時性，并利用鄰域相似性度量提升軌跡聚類準確性。

2 本文算法

2.1 相關定義與符號

定義1（軌跡距離）軌跡距離是評價軌跡樣本之間相似性的度量值，是軌跡聚類效果的重要指標之一。兩個軌跡樣本之間距離越大，其相似度越小，反之亦然。

本文采用文獻［14］中的距離計算方法實現軌跡段之間的相似性度量，如圖1 所示。

圖1 距離計算示意圖Fig.1 Schematic diagram of distance calculation

在圖1 中，兩個軌跡段trai和traj之間的距離dist(trai，traj)包含垂直距離d⊥、平行距離d∥和角度距離dθ3 個部分，相關計算公式如下：

其中，w⊥、w∥和wθ分別為d⊥、d∥和dθ的權重，在本文中均設置為1/3。

定義2（群組）群組是一條核心軌跡和若干條非核心軌跡組成的集合，核心軌跡與任意非核心軌跡之間距離不大于距離閾值ε。群組形狀與最大半徑為ε的圓類似。

定義3（邊界距離）邊界距離Ts和Tw分別為群組中s和w的核心軌跡到非核心軌跡的最大距離，其值不大于ε。

定義4（群組可達）設Cs和Cw分別為不同群組s和w的核心軌跡，當滿足‖Cs-Cw‖≤Ts+Tw+ε時，稱s和w為群組可達，群組si的可達群組集合記為R(si)。

2.2 算法框架

在對軌跡數據集中一條軌跡進行聚類時，通常會忽略部分具有較高相似度的子軌跡段。因此，本文在對軌跡數據集聚類前，根據信息學中最小描述長度（Minimum Description Length，MDL）［14］原則對軌跡進行分段預處理。假設一條軌跡TRi=p1p2…pleni，特征點集合points={p1，p2，…，pleni}，計算公式如下：

其中，len(pcj pcj+1)為兩點之間的歐幾里得距離，d⊥和dθ分別由式（1）和式（3）計算得到。

圖2 為TraG-DBSCAN 算法流程，該算法包括兩個階段：1）通過2 次遍歷軌跡數據集獲得基于子軌跡段的群組集合；2）對子軌跡段進行聚類，并利用群組集合減少聚類算法中搜索軌跡樣本鄰域集合所需時間。

圖2 TraG-DBSCAN 算法流程Fig.2 Procedure of TraG-DBSCAN algorithm

2.3 群組的建立

在群組建立階段，通過2 次遍歷整個軌跡數據集將其劃分為不同群組，符合相應條件的群組之間相互可達。

1）在第1 次遍歷軌跡數據集時，對于每個軌跡樣本，若群組數為0 或不存在任意一個群組的核心軌跡與該軌跡樣本之間距離不大于2ε，則以該軌跡樣本為核心軌跡建立新群組；若存在一個群組的核心軌跡與該軌跡樣本之間距離不大于ε，則將該軌跡樣本劃分到此群組中；若上述兩種情況均不符合，則將該軌跡樣本標記為未處理軌跡，等待進行第2 次遍歷過程。

2）在第2次遍歷軌跡數據集時，對于每個在第1次遍歷中被標記為未處理的軌跡樣本，計算其與所產生群組中核心軌跡之間的距離。若存在一條核心軌跡與該軌跡樣本的距離不大于ε，則將該軌跡樣本劃分到相應群組；否則以該軌跡樣本為核心軌跡建立新群組。

值得注意的是，以不同順序處理軌跡樣本會產生不同群組，但并不影響最終聚類結果。當一個新軌跡樣本加入群組時，群組的邊界距離需進行更新。通過計算兩個群組中核心軌跡之間的距離可判斷群組之間是否可相互抵達，當兩者之間距離不大于兩個群組的邊界距離與ε之和時，這兩個群組為可相互抵達。由于群組的邊界距離在算法結束前才可確定，邊界距離取最大值ε作為替代值，因此當兩條核心軌跡之間距離不大于3ε時，這兩個群組可相互抵達。以下分別為建立群組算法Group和CreateGroups（S，tra）函數算法的偽代碼。

算法1建立群組算法Group

算法2CreateGroups（S，tra）函數算法

2.4 軌跡聚類

TraG-DBSCAN 算法中的軌跡聚類算法以傳統DBSCAN 算法為基礎，采用群組搜索方法代替距離計算方法，以減少搜索鄰域集合所需計算次數和算法在規模較大的軌跡數據集上的時間開銷。

2.4.1 改進的鄰域搜索算法

在傳統DBSCAN 算法中，搜索鄰域集合主要通過計算該樣本與數據集中其他樣本之間的距離來實現，其在大規模軌跡數據集上時間開銷較大，建立群組可減少搜索鄰域集合所需計算次數。在搜索軌跡樣本時，首先判斷該樣本所在群組的邊界距離，若邊界距離不大于ε2，則該群組中所有樣本都處于該樣本的鄰域內，否則再分別計算；若邊界距離在（ε2，ε）范圍內，則將樣本添加至鄰域內。然后選取該群組的可抵達群組中的樣本。鄰域搜索算法FindNeighbours 的偽代碼見算法3。

算法3鄰域搜索算法FindNeighbours

2.4.2 軌跡聚類算法

基于上述鄰域搜索算法進行軌跡聚類，以下分別為軌跡聚類算法ClusterTra 和ExpandCluster（Q，C，ε，MinPts，S）函數算法的偽代碼。

算法4軌跡聚類算法ClusterTra

算法5ExpandCluster（Q，C，ε，MinPts，S）函數算法

2.5 時間復雜度

TraG-DBSCAN算法的時間復雜度包含以下3個部分：

1）軌跡分段處理的時間復雜度。遍歷整個數據集，處理每條軌跡并獲得待處理的子軌跡段，此部分時間復雜度為O（n）。

2）基于子軌跡段建立群組的時間復雜度。遍歷整個子軌跡段集合進行群組初步劃分，未被劃分到任何群組的子軌跡段在第2 次遍歷中進行處理。假設p為最初群組劃分后剩余的子軌跡段數目，則基于子軌跡段建立群組的時間復雜度為O（n+p），由于p?n，因此該部分時間復雜度也為O（n）。

3）基于劃分的群組對子軌跡段進行聚類的時間復雜度。該部分耗時主要集中在對每個子軌跡段的鄰域搜索上。在對子軌跡段樣本進行鄰域集合搜索時，需計算該樣本與所有可達群組中全部軌跡段樣本之間的距離，以及該樣本與數據集中所有其他軌跡樣本的距離。如果未做任何改進，則該部分的時間復雜度為O（n2）。實際上，TraG-DBSCAN 算法在該部分做了相應改進，需計算子軌跡段樣本與可達群組中軌跡樣本之間距離。此外，對于待處理的子軌跡段樣本，算法會對該樣本的可達群組進行相應的剪枝處理，從而減少時間開銷。假設d為數據集中鄰域集合搜索所需最大計算次數，則聚類階段的時間復雜度為O（nd）。

綜上所述，TraG-DBSCAN 算法的時間復雜度為上述各部分時間復雜度之和O（n）+O（n）+O（nd），其總體時間復雜度為O（nd）。對于可行的鄰域參數ε，d通常很小且受到樣本對象處理順序的影響。

3 實驗與結果分析

本文在不同軌跡數據集上驗證TraG-DBSCAN 算法（以下稱為本文算法）的有效性和準確性，將本文算法與TRACLUS 算法的運行時間和聚類結果準確性進行對比分析。本文算法和TRACLUS 算法均由Matlab語言實現，實驗環境為AMD FX-7600P Radeon R7 4 核處理器，8 GB 內存，Windows 7 操作系統以及Matlab 2016b 運行平臺。

3.1 實驗數據集

本文實驗采用Best Track大西洋颶風軌跡數據集，其記錄了大西洋颶風發生的時間、經緯度、最大持續風速和每6小時的中心氣壓。本文從該軌跡集中選取颶風發生的時間和經緯度軌跡數據進行實驗。每條軌跡數據的存儲格式T={Tid，loc1，loc2，…，locn}，其中Tid為軌跡標識符，loci=＜ti，lati，longi＞(i=1，2，…，n)為每個時刻的位置點，其中包含時間、緯度和經度信息。將1990 年至2013 年的大西洋颶風軌跡數據作為數據集DS1，該數據集包含152 條颶風軌跡，共6 557 個軌跡點。將1851 年至2013 年的大西洋颶風軌跡數據作為數據集DS2，該數據集包含855 條颶風軌跡，共30 146個軌跡點。

3.2 評價指標

3.2.1 輪廓系數

本文采用以下輪廓系數評價算法的聚類效果：

1）計算樣本i到同簇中其他樣本的平均距離a（i），該值越小說明樣本i更應被聚類到該簇。將a（i）稱為樣本i的簇內不相似度。

2）計算樣本i到其他某簇Cj中所有樣本的平均距離bij，將min{bi1，bi2，…，bik}（k為其他簇的個數）定義為樣本i的簇間不相似度，記為b（i）。

3）樣本i的輪廓系數值記為s（i）并定義如下：

其中，若s（i）接近1 則說明樣本i聚類更合理，若s（i）接近?1則說明樣本i更應分類到另外的簇，若s（i）近似為0則說明樣本i在兩個簇的邊界上。

3.2.2 總平方誤差和

為進一步驗證本文算法的可行性，采用總平方誤差和（Total Sum of Squared Error，TSSE）作為算法聚類效果的評價指標，其計算公式如下：

其中，numc表示簇的個數，|Ci|表示第i個簇中軌跡樣本的個數，dist（Tx，Ty）表示軌跡樣本Tx和Ty之間的距離。TSSE值越小，算法聚類效果越好。

3.3 參數設置

人為選取的半徑參數和鄰域密度閾值通常不準確，需耗費較多時間確定合適的參數值。本文在參數設置上避免人為干預，采用啟發式搜索方法［14］確定ε，再通過最佳的ε確定MinPts，相關計算公式如下：

其中,Nε(trai)為軌跡樣本trai的鄰域集合,|Nε(trai)|為trai鄰域集合中的軌跡樣本個數。

由式（9）和式（10）可確定使H（x）最小的半徑參數，即最佳半徑參數ε。在此基礎上，計算數據集的鄰域軌跡樣本數的平均值avg|Nε(trai)|，MinPts 的取值范圍為[。

3.4 結果分析

3.4.1 運行時間的對比

表1 和表2 分別為不同半徑參數和鄰域密度閾值下本文算法和TRACLUS 算法在DS1 數據集上的運行時間。可以看出，2 種算法的運行時間均隨著參數值變化而改變，本文算法在數據集DS1 上的運行時間遠短于TRACLUS 算法。

表1 不同ε 值下2 種算法在DS1 數據集上的運行時間Table 1 Running time of two algorithms on DS1 dataset with different ε valuess

表2 不同MinPts值下2種算法在DS1數據集上的運行時間Table 2 Running time of two algorithms on DS1 dataset with different MinPts valuess

表3 和表4 分別為在不同半徑參數和鄰域密度閾值下本文算法和TRACLUS 算法在DS2 數據集上的運行時間。可以看出，在規模較大的軌跡數據集上進行聚類時2 種算法的運行時間均較長，本文算法在數據集DS2 上的運行時間遠短于TRACLUS 算法，其在不同參數下時間開銷更少。

表3 不同ε 值下2 種算法在DS2 數據集上的運行時間Table 3 Running time of two algorithms on DS2 dataset with different ε valuesh

表4 不同MinPts值下2種算法在DS2數據集上的運行時間Table 4 Running time of two algorithms on DS2 dataset with different MinPts valuesh

由上述分析結果可知，本文算法在DS2數據集上運行時間較TRACLUS算法的減幅比DS1數據集更顯著。由此可知，本文算法可有效地應用于海量的軌跡數據集。

3.4.2 聚類結果準確性的對比

圖3 為不同半徑參數和不同鄰域密度閾值下本文算法和TRACLUS 算法在DS1 數據集上聚類結果的TSSE 值對比情況。可以看出，本文算法的TSSE 值較TRACLUS算法更小，其在DS1數據集上聚類效果更好。

圖3 2 種算法在DS1 數據集上聚類結果的TSSE 值對比Fig.3 Comparison of TSSE values of clustering results of two algorithms on DS1 dataset

圖4 為不同半徑參數和不同鄰域密度閾值下本文算法和TRACLUS 算法在DS1 數據集上聚類結果的輪廓系數值對比情況。可以看出，本文算法的輪廓系數值較TRACLUS 算法更接近1，表明其在DS1數據集上聚類結果更準確。

圖4 2 種算法在DS1 數據集上聚類結果的輪廓系數值對比Fig.4 Comparison of silhouette coefficient values of clustering results of two algorithms on DS1 dataset

圖5 和圖6 分別為不同半徑參數和不同鄰域密度閾值下本文算法和TRACLUS 算法在DS2 數據集上聚類結果的TSSE 值和輪廓系數值對比情況。可以看出，2 種算法的TSSE 值和輪廓系數值隨著半徑參數和不同鄰域密度閾值的變化相應改變，本文算法的聚類評價結果較TRACLUS 算法更優。

圖5 2 種算法在DS2 數據集上聚類結果的TSSE 值對比Fig.5 Comparison of TSSE values of clustering results of two algorithms on DS2 dataset

圖6 2 種算法在DS2 數據集上聚類結果的輪廓系數值對比Fig.6 Comparison of silhouette coefficient values of clustering results of two algorithms on DS2 dataset

3.4.3 聚類結果的可視化

由上述對聚類結果準確性分析可知，在DS1 數據集上，當ε=281 且MinPts=10 時，本文算法聚類效果最好，選擇該條件下的聚類結果進行可視化顯示。類似地，在DS2 數據集上，當ε=190 且MinPts=17 時，本文算法聚類效果也最好，選擇該條件下的聚類結果進行可視化顯示。圖7 和圖8 分別為本文算法在DS1 數據集和DS2 數據集上的可視化聚類結果（彩色效果參見《計算機工程》官網HTML 版）。

圖7 本文算法在DS1 數據集上的可視化聚類結果Fig.7 Visual clustering results of the proposed algorithm on DS1 dataset

圖8 本文算法在DS2 數據集上的可視化聚類結果Fig.8 Visual clustering results of the proposed algorithm on DS2 dataset

4 結束語

本文提出一種結合群組和密度的聚類算法。根據MDL 原則將一整條軌跡劃分為若干條軌跡段，通過遍歷軌跡數據集將所有軌跡段劃分到相應的群組中，以減少聚類時鄰域集合搜索過程中冗余的計算次數，最終利用群組和密度對軌跡數據集進行聚類。實驗結果表明，與基于密度的TRACLUS 算法相比，該算法運行時間更短且聚類準確性更高，運行時間的減幅隨軌跡數據集規模的擴大而增加。后續將結合并行和分布式計算框架，進一步縮短該算法在海量軌跡數據集上的運行時間并提升聚類準確性。