基于改進粒子群聚類算法的出行熱點提取方法

摘 要：提出一種基于改進粒子群算法的聚類算法來實現城市出行熱點挖掘。首先對軌跡數據進行清洗、標準化、分割等預處理；其次采用改進粒子群的聚類算法分析熱點區域；最后以這些熱點作為網絡節點，以道路作為連接邊建立網絡模型，從節點和連接邊出發，實現出行熱點可視化。算法的全局尋優能力和分布式隨機搜索特性能夠解決傳統聚類算法易陷入局部最優的問題，算法引入了壓縮因子，能通過配置最優參數控制粒子群更新速度，從而有效改進粒子群算法準確率和全局收斂性。

關鍵詞：軌跡數據；壓縮因子；改進粒子群算法；聚類算法；熱點挖掘

中圖分類號：TP319 文獻標識碼：A 文章編號：2096-4706（2024）15-0047-04

Method of Extracting Travel Hotspots Based on Improved Particle Swarm Optimization Cluster Algorithm

CHEN Ying， WU Mingzhu

（Information Technology and Engineering Department of Guangzhou Institute of Technology， Guangzhou 510075， China）

Abstract： This paper proposes a clustering algorithm based on improved Particle Swarm Optimization to achieve urban travel hotspot mining. Firstly， it preprocesses the trajectory data through cleaning， standardization， and segmentation. Then， an improved Particle Swarm Optimization clustering algorithm is used to analyze the hotspot area. Finally， it takes the hotspots as network nodes and takes the roads as connecting edges to establish network model. Starting from the nodes and connecting edges， it achieves visualization of travel hotspots. The global optimization ability and distributed random search characteristics of the algorithm can solve the problem of traditional clustering algorithms easily falling into local optima. The algorithm introduces a compression factor and can control the update speed of the particle swarm by configuring the optimal parameters， so as to effectively improve the accuracy and global convergence of the Particle Swarm Optimization algorithm.

Keywords： trajectory data; compressibility factor; improved Particle Swarm Optimization algorithm; cluster algorithm; hotspot mining

0 引 言

移動定位技術和無線通信技術的快速發展，為城市交通領域積累了大量的移動軌跡數據，這些數據是智慧城市發展的重要研究對象之一，具有重要的社會和經濟價值。海量軌跡數據在實時記錄城市交通狀況的同時，不僅在交通預測、位置服務、推薦系統等各個應用領域有著重要作用，也反映了城市居民出行規律和城市空間結構等信息。出行熱點區域的時空分布及動態演化，直觀展示了居民在城市的流動性和城市區域的功能分布[1]。因此，基于城市軌跡數據挖掘熱點區域分析居民出行行為，一直受到眾多學者的關注，成為數據挖掘領域的重要研究方向，通過對移動對象軌跡數據及相關信息的研究，我們可以更好地分析移動對象運動的特點和規律，進而發現移動行為模式[2]。

1 研究現狀

隨著物聯網技術、大數據技術、通信技術、人工智能等為代表的新一代技術的發展和完善，利用地理時空大數據探測城市熱點并探討其應用已成為城市熱點研究的主流趨勢。

Mou等[3]從車輛軌跡數據中提取“起點—終點”數據進行聚類，提出一種基于網格密度混合的聚類方法，旨在挖掘出行行為與城市功能區的聯系。Qin等[4]基于時空數據場理論，將聚類分析方法引入到出租車軌跡數據中，以識別居民出行的持續熱點區和非持續熱點區。Yuan等[5]提出一種基于城市活動人群潛在移動軌跡的城市功能區識別方法。周勍等[6]基于出租車軌跡數據，提出利用數據場勢值域值方法探測城市熱點區域，并對比分析了節假日和非節假日的差異。胡慶武等[7]使用社交網絡位置簽到數據，提出一種城市商圈挖掘方法，但該方法缺乏對各商圈間聯系的深入分析。李文明等[8-9]通過對交通軌跡數據建立時空索引結構和反向索引結構，完成數據分析與挖掘，實現預測出行時間及路線推薦。陳凱等[10]提出一種基于城市交通監控數據的出行位置范圍推理方法，將城市交通監控數據與上下文興趣點數據相結合，來探索挖掘車輛的移動模式。

出行熱點區域的提取通常是基于軌跡數據中的關鍵軌跡點進行聚類分析。聚類算法的工作原理是先對預處理過的原始數據集進行初始劃分，然后通過迭代的方法不斷更新類簇中心和類簇對象，直至滿足聚類條件時，停止迭代。盡管該算法原理簡潔且時間效率高，但其聚類結果受初始點選擇影響較大，合理選擇初始聚類數目及類中心較為困難，容易導致結果的不穩定性。此外，一般聚類算法難以有效識別噪聲點，不適合處理非凸形狀和密度差異較大的數據集。

2 基于改進粒子群聚類的出行熱點提取方法

2.1 算法主要思想

針對上述現有技術的缺點，本算法提出一種基于改進粒子群算法的聚類算法，以實現城市出行熱點的有效挖掘。首先，對交通軌跡數據進行清洗、標準化、分割等預處理。然后，采用改進粒子群的聚類算法分析熱點區域，并以這些熱點作為網絡節點，以道路作為連接邊建立網絡模型，實現出行熱點可視化。算法流程如圖1所示。

本算法提出的改進粒子群聚類算法，通過全局尋優能力和分布式隨機搜索特性，有效解決了傳統聚類算法易陷入局部最優問題。算法中引入了壓縮因子，能通過配置最優參數控制粒子群更新速度，有效改進粒子群算法準確率和全局收斂性。

2.2 算法具體步驟

2.2.1 交通軌跡數據預處理

1）數據清洗。本算法采用上海2020年7月3 000輛出租車的軌跡數據作為研究基礎。原始軌跡數據可能包含缺失值、異常值或錯誤數據。在對數據進行聚類分析之前，需要對數據進行清洗，包括去除缺失值、異常值、重復值，糾正可能存在的錯誤數據，確保數據的準確性和完整性，減少由錯誤數據引起的誤導和偏差，以提高聚類質量和可解釋性。

對采樣數據中的關鍵數據有缺失的情況下，應該將記錄刪KpZiynsgZ2l7WV/JOK6mfchOYoglnaT5AzIsMuzX7XM=除。GPS在采集出租車軌跡數據的過程中，可能因為信號不良、設備故障或數據傳輸丟失數據包等問題，導致數據沒有采集完整，故而在原始軌跡數據中記錄為空值。在數據分析前，需進行剔除。

對采樣數據中存在異常值的情況，應做相應處理。如經緯度缺失部分位置信息時，可認為是運動對象在移動過程中，儀器未檢測到位置數據的異常。可通過線性插值的方法，即根據前后兩個非缺失數據擬合一個線性函數對缺失數據進行預測，補充缺失數據。如軌跡記錄每個數據字段都有有效的值域范圍，不在值域范圍的數據應視為異常數據進行處理。如速度字段，速度的單位是千米每小時，值域為[0，160]，將采樣記錄中速度不在[0，160]范圍內的數據均作為異常數據加以剔除。

對于采樣數據中的大量重復數據，應該予以刪除。GPS設備每隔一段時間對出租車信息進行一次采樣，如果出租車當日處于停運靜止狀態，整個軌跡文件除了時間字段，其他的位置、速度、角度等數據完全相同，這種大量重復數據會對聚類、熱點提取等分析造成不良影響，所以在進行相應分析之前，應予刪除。同理，某個整個軌跡文件有行車軌跡變化，但其中有一大段時間內，位置信息無任何變化，此時出租車應該處于臨時停車、司機休息或者進餐狀態，這種重復數據也會對聚類、熱點等分析造成不良影響，所以在進行相應分析之前，應予去除。

2）數據標準化。標準化的目的是消除數據的度量單位的影響，使不同單位或量級的指標能夠進行比較和加權。對軌跡數據進行標準化處理，使得屬性的不同度量具有相同的尺度或分布，包括經度與緯度數據標準化、時間標準化。如速度通常以千米/小時、米/秒等表示，因此需要進行數據標準化，標準化后的速度數據具有統一的標準，才能作為模型輸入的訓練數據。

3）軌跡分割。根據特定的軌跡標識對軌跡進行分割，以降低數據處理的復雜性，提高分析精度和增強適應性。軌跡分割可以基于車輛編號、時間段、車輛狀態變化等進行。按車輛編號進行分割，形成車輛的軌跡數據集；按時間段進行分割，形成時間分布軌跡數據集；按車輛狀態變化進行分割，形成空車數據集與載人數據集。

2.2.2 基于改進粒子群聚類算法的出行熱點提取

經典粒子群聚類算法（Particle Swarm Optimiz-ation， PSO）通過模擬鳥群中的個體通過協作和信息共享來尋找食物的過程，將每個鳥類比為“粒子”，每個粒子都代表問題的一個潛在解。PSO算法通過搜索粒子跟蹤“個體最優解”和“全局最優解”來更新自己的位置和速度，通過不斷地更新粒子的速度和位置，在搜索空間中尋找最優的聚類中心點，從而實現數據的聚類。PSO算法原理簡單、易于實現，但容易陷入局部最優解，導致收斂精度低和不穩定性。因此，本算法基于經典粒子群聚類算法，在計算粒子速度時增加了壓縮因子進行算法改進。

本算法將軌跡數據隨機劃分成若干個互不相交的簇，分別隨機選擇1個數據點作為每個簇的初始聚類中心。通過計算每個軌跡數據點到各簇中心的距離，根據最近鄰原則重新分配到距離它最近的簇中心。然后對新簇中的數據點做均值優化，重新計算得到新生成簇的聚類中心。

比較新舊聚類中心的距離，若距離在閾值內，則認為算法收斂并輸出結果；否則，繼續根據新的聚類中心重新迭代，直至收斂。

聚類中心點移動的下一位置速度公式為：

（1）

聚類中心點移動的下一位置公式為：

=xid+vid （2）

在本算法中，聚類中心點的維度包括經度、緯度、時刻三個維度。其中，表示中心點i在第d個維度上的下一個速度，xid表示中心點i在第d個維度上當前的位置，w表示慣性權重，pid表示中心點i當前搜索到的最優解，pgd表示整個中心點群當前的最優解，c1和c2表示加速系數，調節pid與pgd的相對重要性，rand（）為值在[0，1]之間的隨機數，增加一定的隨機擾動，以避免算法陷入局部最優解。w慣性權重的取值較大時，有利于在更大的范圍內進行搜索，而較小的w能保證最終收斂到最優位置。所以本算法將w設置為由0.9向0.4線性減小的變化取值，從而能夠使算法一開始全局搜索而后精確收斂，達到較優的效果。對于加速系數c1和c2，c1影響本身歷史信息對于聚類中心點運動的軌跡，c2影響其他中心點的歷史信息對中心點運動的軌跡，都不宜過大，本算法選取c1、c2為2.05。

對比經典粒子群算法，本算法通過壓縮因子φ對慣性權重和加速系數的控制，使算法能夠很好地在整體搜索和局部收斂之間達到均衡，防止加速系數c1或c2一方增長過大，同時也保證速度增長不致過大，從而在不增加時間成本的基礎上，使聚類算法在搜索全局性和收斂性上得到提高。為了算法順利求解，ρ必須大于4。

算法流程圖如圖2所示。

2.2.3 聚類中心個數K的確定

聚類算法聚類中心的個數直接影響聚類結果的質量和可解釋性。在確定聚類中心個數時，預設聚類中心個數為5至30，從中選擇最佳的K值。每次聚類后，通過計算誤差平方和（Sum of Squared Errors， SSE）來評估聚類效果，SSE值越小，表示聚類效果越好，即聚類內部的樣本點更加緊密，聚類間的差異較小。通過觀察每次聚類的K值和SSE值的關系圖，我們確定了最佳的K值為20時，SSE值達到最佳。

3 可視化模塊

出行熱點提取算法可設置聚類中心集合元素個數，本算法將數據劃分成20個簇，并獲取每個聚類中心點的經緯度坐標。采用Python第三方庫Folium提供的接口，通過多圖層繪制路線段和聚類中心，配合地圖實現可視化。

首先創建一個地圖對象并設置中心位置的經緯度。然后創建一個點圖層和一個線路圖層，將所有聚類點添加到點圖層，將相關路線段添加到線路圖層。最后，將點圖層和線路圖層通過add_to方法添加到地圖對象中，并顯示地圖。例如將車輛的軌跡數據映射到地圖上，可以繪制出一輛車一天的行車路線，如圖3所示。

提取數據的時間屬性，按不同的時間粒度（一小時或半小時），基于改進的粒子群聚類算法對居民出行熱點挖掘，分析早高峰和晚高峰的時間區間，以及不同時間區間車輛行駛的熱點變化。圖4為上午8：00軌跡數據聚類結果，圖5為凌晨3：00軌跡數據聚類結果。

提取全天車輛軌跡的起點終點數據，基于改進的粒子群聚類算法對居民出行進行熱點挖掘，結果如圖6所示。

4 結 論

本算法首先對交通軌跡數據進行清洗處理，隨后深入研究基于清洗后軌跡數據的城市出行熱點提取算法，通過壓縮因子φ對聚類算法慣性權重和加速系數進行控制。在保證時間開銷不提高的基礎上，使得算法在搜索全局性和收斂性上得到提高。此外，算法還實現了多圖層繪制功能，能夠直觀地展示路線段和聚類中心，實現對不同時間區間的出行熱點提取結果的可視化呈現。

隨著大數據和人工智能技術的不斷發展，城市出行熱點提取將變得更加智能和精準，如利用深度學習算法對出行數據進行挖掘和分析。在出行熱點的應用上，可以預測出行趨勢、實施對城市交通的實時監控和調度等。這表明，城市出行熱點的提取具有廣闊的應用前景和重要的社會價值。

參考文獻：

[1] 顏亮.基于出租車載客數據的紐約市交通熱點分析與挖掘 [D].青島：山東科技大學，2020.

[2] 彭定永.基于軌跡數據的城市居民出行熱點與出行模式研究 [D].贛州：江西理工大學，2021.

[3] MOU N，LI J，ZHANG L，et al. Spatio-Temporal Characteristics of Resident Trip Based on Poi and OD Data of Float Car in Beijing [C]//ISPRS Geospatial Week.Wuhan：ISPRS，2017，XLII-2/W7：99-105.

[4] QIN K，ZHOU Q，WU T，et al. Hotspots Detection from Trajectory Data Based on Spatiotemporal Data Field Clustering [C]//ISPRS Geospatial Week.Wuhan：ISPRS，XLII-2/W7：1319-1325.

[5] YUAN N J，ZHENG Y，XIE X，et al. Discovering Urban Functional Zones Using Latent Activity Trajectories [J].IEEE Transactions on Knowledge and Data Engineering，2015，27（3）：712-725.

[6] 周勍，秦昆，陳一祥，等.基于數據場的出租車軌跡熱點區域探測方法 [J].地理與地理信息科學，2016，32（6）：51-56+127.

[7] 胡慶武，王明，李清泉.利用位置簽到數據探索城市熱點與商圈 [J].測繪學報，2014，43（3）：314-321.

[8] 李文明.基于交通監控大數據的路線推薦與行程時間評估 [D].煙臺：煙臺大學，2021.

[9] 李文明，劉芳，呂鵬，等.基于城市交通監控大數據的行程時間估計 [J].大數據，2021，7（1）：107-123.

[10] 陳凱，于彥偉，趙金東，等.基于城市交通監控大數據的工作位置推理方法 [J].計算機應用，2021，41（1）：177-184.

作者簡介：陳瑛（1979—），女，漢族，廣東揭陽人，副教授，本科，主要研究方向：信息化技術、新型數據管理技術及其在學情數據、交通數據中的理論與應用。