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

關(guān)鍵詞：軌跡數(shù)據(jù)；壓縮因子；改進(jìn)粒子群算法；聚類算法；熱點(diǎn)挖掘

中圖分類號(hào)：TP319 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引 言

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

1 研究現(xiàn)狀

隨著物聯(lián)網(wǎng)技術(shù)、大數(shù)據(jù)技術(shù)、通信技術(shù)、人工智能等為代表的新一代技術(shù)的發(fā)展和完善，利用地理時(shí)空大數(shù)據(jù)探測城市熱點(diǎn)并探討其應(yīng)用已成為城市熱點(diǎn)研究的主流趨勢。

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

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

2 基于改進(jìn)粒子群聚類的出行熱點(diǎn)提取方法

2.1 算法主要思想

針對上述現(xiàn)有技術(shù)的缺點(diǎn)，本算法提出一種基于改進(jìn)粒子群算法的聚類算法，以實(shí)現(xiàn)城市出行熱點(diǎn)的有效挖掘。首先，對交通軌跡數(shù)據(jù)進(jìn)行清洗、標(biāo)準(zhǔn)化、分割等預(yù)處理。然后，采用改進(jìn)粒子群的聚類算法分析熱點(diǎn)區(qū)域，并以這些熱點(diǎn)作為網(wǎng)絡(luò)節(jié)點(diǎn)，以道路作為連接邊建立網(wǎng)絡(luò)模型，實(shí)現(xiàn)出行熱點(diǎn)可視化。算法流程如圖1所示。

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

2.2 算法具體步驟

2.2.1 交通軌跡數(shù)據(jù)預(yù)處理

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

對采樣數(shù)據(jù)中的關(guān)鍵數(shù)據(jù)有缺失的情況下，應(yīng)該將記錄刪KpZiynsgZ2l7WV/JOK6mfchOYoglnaT5AzIsMuzX7XM=除。GPS在采集出租車軌跡數(shù)據(jù)的過程中，可能因?yàn)樾盘?hào)不良、設(shè)備故障或數(shù)據(jù)傳輸丟失數(shù)據(jù)包等問題，導(dǎo)致數(shù)據(jù)沒有采集完整，故而在原始軌跡數(shù)據(jù)中記錄為空值。在數(shù)據(jù)分析前，需進(jìn)行剔除。

對采樣數(shù)據(jù)中存在異常值的情況，應(yīng)做相應(yīng)處理。如經(jīng)緯度缺失部分位置信息時(shí)，可認(rèn)為是運(yùn)動(dòng)對象在移動(dòng)過程中，儀器未檢測到位置數(shù)據(jù)的異常?？赏ㄟ^線性插值的方法，即根據(jù)前后兩個(gè)非缺失數(shù)據(jù)擬合一個(gè)線性函數(shù)對缺失數(shù)據(jù)進(jìn)行預(yù)測，補(bǔ)充缺失數(shù)據(jù)。如軌跡記錄每個(gè)數(shù)據(jù)字段都有有效的值域范圍，不在值域范圍的數(shù)據(jù)應(yīng)視為異常數(shù)據(jù)進(jìn)行處理。如速度字段，速度的單位是千米每小時(shí)，值域?yàn)閇0，160]，將采樣記錄中速度不在[0，160]范圍內(nèi)的數(shù)據(jù)均作為異常數(shù)據(jù)加以剔除。

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

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

3）軌跡分割。根據(jù)特定的軌跡標(biāo)識(shí)對軌跡進(jìn)行分割，以降低數(shù)據(jù)處理的復(fù)雜性，提高分析精度和增強(qiáng)適應(yīng)性。軌跡分割可以基于車輛編號(hào)、時(shí)間段、車輛狀態(tài)變化等進(jìn)行。按車輛編號(hào)進(jìn)行分割，形成車輛的軌跡數(shù)據(jù)集；按時(shí)間段進(jìn)行分割，形成時(shí)間分布軌跡數(shù)據(jù)集；按車輛狀態(tài)變化進(jìn)行分割，形成空車數(shù)據(jù)集與載人數(shù)據(jù)集。

2.2.2 基于改進(jìn)粒子群聚類算法的出行熱點(diǎn)提取

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

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

比較新舊聚類中心的距離，若距離在閾值內(nèi)，則認(rèn)為算法收斂并輸出結(jié)果；否則，繼續(xù)根據(jù)新的聚類中心重新迭代，直至收斂。

聚類中心點(diǎn)移動(dòng)的下一位置速度公式為：

（1）

聚類中心點(diǎn)移動(dòng)的下一位置公式為：

=xid+vid （2）

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

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

算法流程圖如圖2所示。

2.2.3 聚類中心個(gè)數(shù)K的確定

聚類算法聚類中心的個(gè)數(shù)直接影響聚類結(jié)果的質(zhì)量和可解釋性。在確定聚類中心個(gè)數(shù)時(shí)，預(yù)設(shè)聚類中心個(gè)數(shù)為5至30，從中選擇最佳的K值。每次聚類后，通過計(jì)算誤差平方和（Sum of Squared Errors， SSE）來評(píng)估聚類效果，SSE值越小，表示聚類效果越好，即聚類內(nèi)部的樣本點(diǎn)更加緊密，聚類間的差異較小。通過觀察每次聚類的K值和SSE值的關(guān)系圖，我們確定了最佳的K值為20時(shí)，SSE值達(dá)到最佳。

3 可視化模塊

出行熱點(diǎn)提取算法可設(shè)置聚類中心集合元素個(gè)數(shù)，本算法將數(shù)據(jù)劃分成20個(gè)簇，并獲取每個(gè)聚類中心點(diǎn)的經(jīng)緯度坐標(biāo)。采用Python第三方庫Folium提供的接口，通過多圖層繪制路線段和聚類中心，配合地圖實(shí)現(xiàn)可視化。

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

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

提取全天車輛軌跡的起點(diǎn)終點(diǎn)數(shù)據(jù)，基于改進(jìn)的粒子群聚類算法對居民出行進(jìn)行熱點(diǎn)挖掘，結(jié)果如圖6所示。

4 結(jié) 論

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

隨著大數(shù)據(jù)和人工智能技術(shù)的不斷發(fā)展，城市出行熱點(diǎn)提取將變得更加智能和精準(zhǔn)，如利用深度學(xué)習(xí)算法對出行數(shù)據(jù)進(jìn)行挖掘和分析。在出行熱點(diǎn)的應(yīng)用上，可以預(yù)測出行趨勢、實(shí)施對城市交通的實(shí)時(shí)監(jiān)控和調(diào)度等。這表明，城市出行熱點(diǎn)的提取具有廣闊的應(yīng)用前景和重要的社會(huì)價(jià)值。

參考文獻(xiàn)：

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

[2] 彭定永.基于軌跡數(shù)據(jù)的城市居民出行熱點(diǎn)與出行模式研究 [D].贛州：江西理工大學(xué)，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] 周勍，秦昆，陳一祥，等.基于數(shù)據(jù)場的出租車軌跡熱點(diǎn)區(qū)域探測方法 [J].地理與地理信息科學(xué)，2016，32（6）：51-56+127.

[7] 胡慶武，王明，李清泉.利用位置簽到數(shù)據(jù)探索城市熱點(diǎn)與商圈 [J].測繪學(xué)報(bào)，2014，43（3）：314-321.

[8] 李文明.基于交通監(jiān)控大數(shù)據(jù)的路線推薦與行程時(shí)間評(píng)估 [D].煙臺(tái)：煙臺(tái)大學(xué)，2021.

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

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

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