基于Spark 并行化的改進K-means 軌跡聚類的方法

中國科學技術大學先進技術研究院 孫明悅 馬胤垚

本文設計了一種對K-means 初始化改進的Canopy+Kmeans++聚類方法，提高上軌跡聚類算法的效率，為進一步提升軌跡大數據聚類的迭代計算效率，本文利用Spark計算架構的可伸縮性和分布式等特，實現Canopy+Kmeans++軌跡聚類算法的并行化，并通過對比實驗來證明該并行化聚類方案的有效性。

1 模型與方法

1.1 LCSS 距離歸一化設計

LCSS(A,B)為兩條軌跡間的最長公共子序列長度，表示軌跡間匹配相似點的對數情況[1]。相似點對數占整條軌跡的比值越大，則兩條軌跡距離越近，相似度越高。為實現海量軌跡聚類時各軌跡間的距離判定能夠統一，對上述LCSS 距離做了改進，進行歸一化處理，設計了Jaccard\_L 軌跡相似性度量方法，定義計算如公式（1）所示：

Jaccard_L(A,B)相似度表示將A和B的LCSS距離轉化為相似性度量值，|N|和|M|表示兩條軌跡的長度。相似度J(A,B)取值范圍為[0,1]，是對相似距離的歸一化。其中0 表示兩條軌跡完全不具有相似性，1 表示兩條軌跡完全一致，經過計算，若兩條軌跡的J(A,B)值超過閾值T，認為兩條待測軌跡相似。

1.2 基于初始化改進的軌跡聚類

K-means 是一種經典的基于劃分的聚類算法，其優化目標函數如公式（2）所示：

其中，K是設定好的聚類數量，p表示樣本點，dist是樣本點與中心點的距離，本文用軌跡相似度Jaccard_L表示，C是聚類中心軌跡，用矩陣表示，J是最小目標函數，通過迭代找到最優解。

1.2.1 確定聚類數目K 值

本課題利用Canopy 算法解決K-means 的K 值無法確定問題。Canopy 算法不需要事先指定最終聚類數目，可以利用此算法對海量大數據進行聚類。

1.2.2 改進后的算法

改進后的Canopy+K-means++主要步驟如下：

（1）讀取歷史軌跡數據集，指定兩個軌跡相似度閾值T1、T2（T1>T2），T1、T2由測試結果調整。

（2）在軌跡數據集中隨機選取1 個樣本軌跡P，然后計算P 與所有其他Canopy 集合中心之間的軌跡相似度Jaccard_L（如果沒有集合就把P 點當作新的Canopy，為其創建Buffer），如果該相似度小于T1，則將軌跡P 加入到這個集合的Buffer。如果軌跡P 與集合中心距離小于T2，則將P 從這個集合的Buffer 中刪除，如果到所有集合中心的距離都大于T2，把P 點當作新的Canopy，為其創建新Buffer。

（3）迭代執行步驟（2），直到軌跡數據集內數目為空。匯總所有Canopy 集合個數,也就得到了K-means聚類K 值。

（4）計算待測軌跡集X 相對于聚類中心軌跡N 的軌跡相似度矩陣，采用上述提出的Jaccard_L 方法。

（5）計算待測軌跡被選為聚類中心點的概率，將概率最大的樣本軌跡作為聚類中心軌跡N+1，將N 替換為N+1，重復（4）直到聚類中心軌跡數目等于K。概率計算公式如公式（3）所示，D(x,N)表示待測軌跡x到聚類中心N的相似度。

（6）匯總聚類中心點，得到初始聚類中心軌跡。

（7）基于初始聚類中心軌跡和聚類K 值，以Jaccard_L 作為軌跡相似度，迭代執行K-means 聚類算法，直至聚類簇收斂。

1.3 Spark 分布式計算架構

為了能夠在集群上運行應用程序，首先創建Spark Context，然后連接到多種Cluster Manager，例如Standlone或YARN,用于應用程序資源調度。連接上Cluster Manager后，Cluster Manager 會在集群中為各個Slave 節點應用程序申請執行器，最后數據節分成多個Task 任務分發給各個執行器執行，多個Executor 按照DAG 任務圖獨立執行任務，開展任務具體的數據處理和計算工作，實現程序的分布式及并行化執行。

1.4 軌跡聚類的并行化實現

Step1：創建Spark 對象SparkContext，各分區Exctuor節點完成初始化并通過SparkContext 向資源管理器(Cluster Manager)申請分配資源。

Step2：使SparkSQL 算子對跡數倉數據dwd\_track\_summary\_db 表格先后按照Geohash 編碼對軌跡起點進行粗聚類得到地理位置分塊索引表格，以一個位置分區數據為例，通過軌跡索引表格從數倉文件中讀取軌跡原始數據至緩存中，對原始軌跡數據做解壓縮、ETL 等一系列預處理。并利用TransFormation 轉換成為RDD[Vector]格式，后對每個分區做Canopy+Kmeans++并行聚類操作。

Step3：采用Canopy-kmeans++改進算法，獲得類簇個數K 值和首次參與計算的聚類中心軌跡。并將聚類中心軌跡廣播到各個分區，用mapPartitions 算子將軌跡分發至不同的Executor 節點，以下一個分區代碼對所有分區適用。

Step4：計算軌跡間的Jaccard_L 相似度矩陣，遍歷分區軌跡，計算軌跡與哪個聚類簇中心軌跡相似度最高，并加入該聚類簇的case 類CenterInfo 中，CenterInfo 數據格式為（聚類簇編號id,單個軌跡向量）。

Step5：以CenterInfo 的聚類簇編號id 作為Key,單個軌跡向量作為Value,對各個Executor 節點軌跡數據用ReduceByKey 進行聚合計算。

Step6：計算新的聚類簇中心軌跡。找到每個聚類簇中到其他簇內成員Jaccard_L 相似度距離平均值最小的軌跡，得到最新的聚類中心軌跡，并拉回至Driver 中。

Step7：判斷各個簇的聚類中心軌跡是否已經收斂不變或者與原來的中心軌跡距離小于閾值，如果不滿足則去除已經收斂的聚類簇，剩下的繼續返回Step2 進行迭代，如果滿足則得到最終聚類結果。

Step8：迭代結束后返回Canopy+K-means++模型生成的簇，完成軌跡聚類，并從每個簇中選取與簇中其他軌跡Jaccard 相似度最高的一條軌跡作為特征模型軌跡。

2 實驗結果與分析

2.1 實驗環境和實驗數據

實驗環境:首先在本地自建Spark 集群，包括3臺服務器。其中1 臺服務器作為驅動器（Master）節點，2 臺服務器作為執行器(Worker)節點。操作系統是Centos7，Spark 版本為Spark-2.2.0-bin-hadoop3.1，Scala 版本為scala-2.11.8。

實驗數據:本文通過智能可穿戴設備采集數據，并通過采集和同步，將數據存入Hive 數據庫系統，從Hive數據庫利用SQL 引擎查詢某城市的一個區數據集H_Data共4043 條軌跡，每條軌跡由100-1000 個個數不等的軌跡點構成，每個軌跡點P=(lat,lng,t)，分別表示經緯度和時間戳；提取軌跡數據的環形軌跡至實驗集群中，首先按照Geohash 編碼前綴對軌跡進行粗聚類，然后以Jaccard_L為相似性度量再對粗聚類簇根據本文所提出算法進行詳細聚類。

2.2 Canopy+K-means++聚類性能測試。

在軌跡聚類算法中，簇內的軌跡到中心軌跡的相似距離越小，到其他簇的距離越大，聚類的質量越高[2]。本文利用軌跡間Jaccard_L 的輪廓系數來表示軌跡的聚類質量，定義計算公式如式（4）所示：

其中a表示某一軌跡到簇內中心軌跡的Jaccard_L相似度，b表示該軌跡到其他軌跡簇中心軌跡的相似度，Si表示第i個軌跡的輪廓系數，S表示所有軌跡輪廓系數，代表聚類質量，取值范圍為（-1，1），當輪廓系數接近1時，說明軌跡聚類相似度較高，且不同聚類簇之間相似度較低，軌跡質量越好。

本文在其他條件不變的情況下，將Canopy+Kmeans++算法改成其他聚類算法，QuickBundles 設置為與Canopy+K-means++相同K 值，OPTICS 參數ε=0.85，MinPts=8 時，與本文K 值最為接近。將多個實驗進行準確率比較，定義運行時間比表示為FT=Ti/TL，TL表示應用Canopy+Kmeans++算法聚類運行時間[3]，當FT＞1時，該算法運行時間復雜度比Canopy+Kmeans++算法高,結果可知，OPTICS 和Canopy+Kmeans++方法準確率較高，且聚類質量高，OPTICS 是對DBSCAN 的一種改進，但是OPTICS 的時間復雜度最高，且需要調節ε、MinPts 兩個參數；QuickBundles 是一種快速聚類，時間復雜度低，但是一旦劃分到某個簇就不會改變，精確度較低；而層次聚類雖然不用提前設定K 值，但聚類終止條件不好設定，且只適合小型數據聚類迭代，在海量軌跡聚類中，算法時間復雜度快速增長，聚類質量差進而影響后續軌跡挖掘效果。Canopy+K-means++算法可以提前確定聚類數目，且對初始化聚類中心軌跡做了優化，聚類質量也相對較高，相比較DBSCAN 和OPTICS，K-means 本身是一種比較快速的聚類方式。

2.3 Spark 并行化計算性能實驗

為測試Spark 并行化后性能是否提高，提取了某城市地區的軌跡數據分別導入單機（串行計算）和Spark 集群服務器，然后編寫Canopy+K-means++聚類代碼并運行，進行A/Btest 測試，設置num-excutors 參數為1，executor-cores 參數為4，測試軌跡數量與計算性能的關系。比較了單機情況下運行結果和并行計算結果運行速度，發現Spark 并行化后的Canopy+K-means++模型計算速度明顯優于串行模型計算（單機環境）速度，說明Spark 引擎提高了計算效率，并行化處理后該聚類方法適用于海量數據處理情況。

2.4 并行計算加速比實驗

并行計算方式下，定義加速比計算如公式（5）所示：

其中Ts表示單機運行時間，n表示并行計算時numexcutors 取值，分別取約5k 和3k 條軌跡，測試算法在Spark 并行計算情況下，設置num-excutors 為1。隨著executor-cores 數目的增加，Canopy+K-means++算法并行計算加速比越來越大。但隨著Cores 數目超過6 時，加速比隨Cores 節點增加變化不大，這也與節點數目無節制增多反而會影響計算性能經驗一致。另外，隨著數據量增加，Cores 數目也增加，其加速效果也就更為明顯，說明Spark 并行化后的算法計算性能更適合于海量數據。

3 結語

本文主要研究了軌跡大數據聚類的實現方案，以Jaccard_L 為軌跡相似性度，利用Canopy+K-means++算法進行軌跡聚類，然后利用Spark 計算將數據集分區后分發給多個子節點，實現軌跡聚類算法的并行化設計，并給出Canopy+K-means++的并行化步驟。通過在可穿戴設備上采集的軌跡數據集分別在單機和Spark 集群運行，并進行A/B Test 實驗，驗證了改進的Canopy+Kmeans++算法相較于其他聚類方法，聚類質量高且時間復雜度較好。另外，基于Spark 并行化的算法模型計算速度明顯優于單機環境模型，且隨著數據量的增加，該并行化算法具有更好的時效性，綜上所述，基于Spark并行化的改進的Canopy+K-means++算法更適用于軌跡大數據聚類場景。

引用

[1] 江紅.一種新的時空軌跡聚類算法KST-DBSCAN的研究[D].武漢:華中師范大學,2022.

[2] 俞慶英,趙亞軍,葉梓彤,等.基于群組與密度的軌跡聚類算法[J].計算機工程,2021,47(4):100-107.

[3] 嚴斯柔.基于GPS數據的軌跡聚類算法研究[D].杭州:杭州電子科技大學,2021.