翁旭艷 鄭淑妮

摘要：針對軌跡聚類方法難以準(zhǔn)確識別高相似熱點路徑的問題，提出能區(qū)分起訖點或局部路段的熱點路徑識別方法，將出行軌跡映射并壓縮為移動網(wǎng)格序列，分別從邊界與內(nèi)部區(qū)分序列間的空間相似性度量，整合轉(zhuǎn)化為距離并進行基于方格序列密度的空間聚類（grid sequencedensity-based spatial clustering of applications with noise，GS-DBSCAN）。以青島市市南區(qū)部分出租車的軌跡數(shù)據(jù)為例，與只考慮內(nèi)部相似性且分別以對比序列中較短序列和較長序列為基準(zhǔn)的聚類方法進行對比驗證。結(jié)果表明：同時考慮邊界與內(nèi)部相似性且以較長序列為基準(zhǔn)的GS-DBSCAN算法能正確區(qū)分多出行起訖點分布下長度差異較大的分離、匯合與交叉耦合熱點路徑，受路徑長度、網(wǎng)格尺寸等變量差異的影響小于2%，且聚類運算效率較高。

關(guān)鍵詞：熱點路徑；邊界；內(nèi)部；軌跡聚類

中圖分類號：U491文獻標(biāo)志碼：A文章編號：1672-0032（2024）02-0089-08

引用格式：翁旭艷，鄭淑妮.基于網(wǎng)格聚類優(yōu)化的區(qū)域熱點路徑識別［J］.山東交通學(xué)院學(xué)報，2024，32（2）：89-96.

WENG Xuyan， ZHENG Shuni. Regional hotspot path identification based on grid clustering optimization［J］.Journal of Shandong Jiaotong University，2024，32（2）：89-96.

0?引言

在交通領(lǐng)域廣泛應(yīng)用全球定位系統(tǒng)（global positioning system，GPS），可得到大量車輛軌跡數(shù)據(jù)，為車輛路徑規(guī)劃、交通運行等研究提供數(shù)據(jù)支持。Wang等[1]、Zhang等[2]通過出租車軌跡GPS數(shù)據(jù)檢測車輛異常軌跡；Liu等[3]、陳振華[4]通過出租車GPS軌跡數(shù)據(jù)分析城市交通擁堵模式；Lin等[5]通過GPS軌跡數(shù)據(jù)預(yù)測城市交通路網(wǎng)流量。通過GPS軌跡數(shù)據(jù)分析熱點路徑的研究較多，熱點路徑指在一段時間內(nèi)車輛頻繁經(jīng)過的路段，通過識別熱點路徑，可為綠波帶設(shè)置、主路優(yōu)先等交通運行管理提供決策依據(jù)。采用聚類方法識別熱點路徑的關(guān)鍵是相似性度量[6]。李穎等[7]分別采用離散弗雷歇算法、動態(tài)時間規(guī)整算法、最長公共序列（longest common subsequence，LCS）算法和實序列編輯距離算法對貨車軌跡數(shù)據(jù)進行聚類，認(rèn)為LCS算法的有效性最優(yōu)。Kim等[8]以LCS算法下車輛行駛距離與較短軌跡距離之比作為軌跡空間相似度進行基于密度的聚類（density-based spatial clustering of application with noise，DBSCAN）算法，分析交通網(wǎng)絡(luò)中空間和時間出行模式。馮琦森[9]、趙欣[10]改進DBSCAN算法，前者結(jié)合重慶地形特點考慮海拔高度因素，認(rèn)為比對軌跡中的最大海拔高度差不應(yīng)超過一定范圍，否則相似度為0；后者在軌跡點空間相似度度量上增加車輛轉(zhuǎn)角差異性，定義時間維度上的軌跡相似度。Kang等[11]通過直接度量軌跡網(wǎng)格序列間重疊區(qū)域表征軌跡相似性。吳俊偉等[12]將網(wǎng)格抽象為圖模型并通過圖搜索進行網(wǎng)格聚類。王超[13]考慮時空事件的密度和類型對出租車軌跡點進行聚類。Lee等[14]提出基于軌跡分段的相似性度量，對速度或方向上快速變化的軌跡點分段。在軌跡映射至網(wǎng)格空間的聚類研究中，可通過直接度量軌跡網(wǎng)格序列間重疊區(qū)域表征軌跡相似性[15]，也可將網(wǎng)格抽象為圖，以鄰接網(wǎng)格的共有軌跡定義網(wǎng)格間可達性，通過圖搜索進行網(wǎng)格聚類及熱點路徑識別[16]。通過優(yōu)化相似度算法、增加相關(guān)因素變量等全面、準(zhǔn)確地分析軌跡數(shù)據(jù)，但以較短軌跡為基準(zhǔn)的LCS相似度可能造成過于重視不同熱點路徑的重疊部分，導(dǎo)致將重疊度較高的不同路徑歸為同一類熱點路徑。起訖點（origin-destination，OD）矩陣和路徑流量的研究較多，但考慮軌跡數(shù)據(jù)的邊界起訖點和內(nèi)部中間點屬性的研究較少。雙層規(guī)劃模型[17]在OD矩陣估計中應(yīng)用較多，Ou等[18]基于機器學(xué)習(xí)算法，提出估計動態(tài)OD流量的雙層框架；Tang等[19]將改進的三維卷積神經(jīng)網(wǎng)絡(luò)模型用于動態(tài)OD矩陣估計；Cao等[20-21]提出的OD矩陣，采用極大似然法擬合各路段的速度-密度函數(shù)，建立基于動態(tài)交通分配的雙層廣義最小二乘法估計器，分析浮動車采樣頻率較低時的OD矩陣估計方法，保證正常估計路段流量；Huang等[22]采用長短期記憶（long short-term memory，LSTM）模型估計OD矩陣。以較短軌跡為基準(zhǔn)的LCS相似度識別熱點路徑軌跡，易將不同起訖點的路徑歸為同一類熱點路徑。

本文優(yōu)化基于軌跡數(shù)據(jù)的路徑識別方法，以區(qū)域網(wǎng)格化為基礎(chǔ)，將車輛軌跡壓縮為僅關(guān)注移動特征的網(wǎng)格序列，序列間的相似性度量包含邊界與內(nèi)部2部分，考慮GPS定位漂移及出行產(chǎn)生與吸引的集聚性，邊界網(wǎng)格的相似性通過基于熱點網(wǎng)格密度的空間聚類（hot grid density based spatial clustering of application with noise， HG-DBSCAN）得到熱點小區(qū)度量，內(nèi)部網(wǎng)格以基于網(wǎng)格的改進LCS相似度表征，二者融合后轉(zhuǎn)化為距離度量，最后進行基于方格序列密度的空間聚類（grid sequence density-based spatial clustering of applications with noise，GS-DBSCAN），優(yōu)化識別熱點路徑。

1?熱點路徑識別優(yōu)化

1.1?區(qū)域網(wǎng)格化

假設(shè)研究區(qū)域的經(jīng)度范圍為[ψmin，ψmax]，緯度范圍為[γmin，γmax]，正方形網(wǎng)格邊長為k，將研究區(qū)域劃分為若干正方形網(wǎng)格。綜合考慮路網(wǎng)密度、車輛GPS軌跡點密度及運算效率等因素確定網(wǎng)格尺寸，網(wǎng)格過大，易覆蓋同方向相互平行的若干道路；網(wǎng)格過小，會導(dǎo)致大部分網(wǎng)格沒有GPS軌跡點落入且運算效率低。

用Gx，y表示網(wǎng)格，x、y分別為Gx，y在網(wǎng)格坐標(biāo)系下的橫、縱坐標(biāo)。網(wǎng)約車訂單i的軌跡點列表為Oi=Pi1，Pi2，…，Pin，…，PiN，其中，N為軌跡點數(shù)；Pin（n∈［1，N］）為第n個軌跡點，是包含3項基本信息的一維向量，Pin=（tinψinγin），ψin、γin分別為tin時刻車輛的經(jīng)、緯度坐標(biāo)。以Pin為例說明車輛GPS軌跡點與網(wǎng)格的映射關(guān)系，公式為：

x=ψin－ψmin/k」y=γin－γmin/k」，（1）

式中?」為取整符號。

1.2?序列邊界

GPS定位有隨機漂移特征，挖掘熱點出行區(qū)域時不直接基于軌跡點進行聚類，而是先將軌跡抽象為熱點網(wǎng)格，再通過HG-DBSCAN算法聚類，提升搜索效率，且可處理任意形狀和大小的簇。采用HG-DBSCAN對熱點網(wǎng)格進行空間聚類時，作以下3個基本定義。

定義1?熱點網(wǎng)格。Gx，y包含的GPS軌跡起訖點數(shù)w應(yīng)大于預(yù)先設(shè)定的判斷閾值λ。

定義2?網(wǎng)格經(jīng)、緯度坐標(biāo)?？紤]到Gx，y中GPS軌跡點分布不均勻，采用網(wǎng)格內(nèi)軌跡點的平均經(jīng)、緯度表示網(wǎng)格經(jīng)、緯度坐標(biāo)，公式為：

ψ—x，y=∑wq=1ψq/wγ—x，y=∑wq=1γq/w。

定義3?網(wǎng)格球面距離。任意2個網(wǎng)格Gx，y、Gx′，y′在經(jīng)、緯度坐標(biāo)下的球面距離[23]

d（Gx，y，Gx′，y′）=ΔηR，

式中：Δη為Gx，y的平均經(jīng)、緯度坐標(biāo)（ψ—x，y，γ—x，y）、Gx′，y′的平均經(jīng)、緯度坐標(biāo)（ψ—′x′，y′，γ—′x′，y′）連線與地球中心線的夾角，Δη=2arcsin（sin2（Δψ/2）+cos ψ—cos ψ—′sin2（Δγ/2）），其中Δψ為2個網(wǎng)格經(jīng)度之差，Δγ為2個網(wǎng)格緯度之差；R為地球半徑。

HG-DBSCAN的網(wǎng)格密度是以熱點網(wǎng)格的經(jīng)緯度坐標(biāo)為圓心，在指定半徑Eps內(nèi)的熱點網(wǎng)格數(shù)。若網(wǎng)格密度大于給定的最小核心網(wǎng)格判別數(shù)Num，則該網(wǎng)格為核心網(wǎng)格。邊界網(wǎng)格指落在某核心網(wǎng)格的鄰域內(nèi)，但本身不是核心網(wǎng)格；噪聲網(wǎng)格是既非核心也非邊界的網(wǎng)格。HG-DBSCAN算法流程包括輸入、初始化、運行、輸出。

1）輸入。輸入λ、Eps、Num。

2）初始化。將分析時間內(nèi)所有訂單軌跡的起訖點映射至對應(yīng)網(wǎng)格；依據(jù)定義1確定熱點網(wǎng)格集合H={Gh1，Gh2，…，Ghb，…，GhB}，其中，B為熱點網(wǎng)格數(shù)，Ghb為第b個熱點網(wǎng)格，Ghb=（xyψ—γ—l）hb，其中l(wèi)為網(wǎng)格的類標(biāo)簽，l=－2，簇編號C=－1。

3）運行。（1）隨機選取1個類標(biāo)簽l=－2的熱點網(wǎng)格Ghb，若Ghb的Eps鄰域內(nèi)至少有Num個熱點網(wǎng)格Gh，則C+1，并將第b個熱點網(wǎng)格的類標(biāo)簽lhb賦值為C，令H′為Ghb鄰域中的熱點網(wǎng)格集合，循環(huán)遍歷H′中的每個熱點網(wǎng)格直至結(jié)束，若類標(biāo)簽lhb′＝－2，則將lhb′賦值為C，同時若Ghb′鄰域內(nèi)至少有Num個Gh，則將Ghb′鄰域中的熱點網(wǎng)格追加至H′；（2）若Ghb的Eps鄰域內(nèi)沒有大于或等于Num個熱點網(wǎng)格Gh，lhb＝－1；（3）重復(fù)步驟（1）（2），直到?jīng)]有l(wèi)=－2的Ghb。

4）輸出。依據(jù)簇內(nèi)軌跡點數(shù)確定熱點小區(qū)集合Z={Zh1，Zh2，…，Zha，…，ZhA}，其中，A為熱點小區(qū)數(shù)，Zha為第a個熱點小區(qū)，含若干類標(biāo)簽相同且大于－1的Ghb。

1.3?序列內(nèi)部

將軌跡點的LCS擴展至網(wǎng)格序列可提升搜索效率，且LCS允許序列部分形變（車輛運動的隨機性）。訂單軌跡Oi通過式（1）映射為網(wǎng)格序列Si，刪除Si中的重復(fù)網(wǎng)格，得到壓縮后的Si′。考慮網(wǎng)格化下，同一路徑的不同軌跡-網(wǎng)格序列受駕駛行為、GPS定位漂移及網(wǎng)格大小等因素影響，網(wǎng)格的重疊率可能較低，建立基于網(wǎng)格的LCS，需定義網(wǎng)格間的空間相似度。

給定2個網(wǎng)格序列Si′={Gi′1，Gi′2，…，Gi′N′}與Sj′={Gj′1，Gj′2，…，Gj′M′}，計算Si′中的第n個網(wǎng)格Gi′n=（t x y）i′n和Sj′中的第m個網(wǎng)格Gj′m=（t x y）j′m間的歐式距離

dG（Gi′n，Gj′m）=（xi′n－xj′m）2+（yi′n－yj′m）2，

式中：xi′n、yi′n分別為Gi′n的橫、縱坐標(biāo)，xj′m、yj′n分別為Gj′m的橫、縱坐標(biāo)。

對網(wǎng)格相似度sG（Gi′n，Gj′m）進行歸一化處理，公式為：

sG（Gi′n，Gj′m）=0，dG（Gi′n，Gj′m）>δ1－dG（Gi′n，Gj′m）/δ，dG（Gi′n，Gj′m）≤δ，

式中δ為網(wǎng)格間允許的最大臨近距離。

基于網(wǎng)格相似度，通過動態(tài)規(guī)劃方法確定Si′與Sj′間的最長公共序列，需將待求解的問題劃分為若干階段，定義各階段的狀態(tài)及變量，確定階段間的狀態(tài)轉(zhuǎn)移方程。Si（n）′為Si′前n個網(wǎng)格，Sj（m）′為Sj′前m個網(wǎng)格，將sLCS（Si（n）′，Sj（m）′）狀態(tài)定義為Si（n）′與Sj（m）′間匹配網(wǎng)格相似度總和的最大值。當(dāng)n=0或m=0時，sLCS（Si（n）′，Sj（m）′）=0；若n、m均不為0，滿足無后效性前提下，sLCS（Si（n）′，Sj（m）′）與Si′前n-1個網(wǎng)格與Sj′前m-1個網(wǎng)格的相似度sLCS（Si（n-1）′，Sj（m-1）′）、Si′前n-1個網(wǎng)格與Sj′前m個網(wǎng)格的相似度sLCS（Si（n-1）′，Sj（m）′）、Si′前n個網(wǎng)格與Sj′前m-1個網(wǎng)格的相似度sLCS（Si（n）′，Sj（m-1）′）有關(guān)，分別對應(yīng)M1、M2及M3 3種匹配模式，M1=sLCS（Si（n－1）′，Sj（m－1）′）+sG（Gi′n，Gj′m），M2=sLCS（Si（n－1）′，Sj（m）′），M3=sLCS（Si（n）′，Sj（m－1）′），即：

sLCS（Si（n）′，Sj（m）′）=0，m=0或n=0

maxM1，M2，M3，m、n≠0。

對長度分別為N′與M′的序列Si′與Sj′，建立行列數(shù)分別為N′+1與M′+1的矩陣D（N′+1，M′+1），通過D（N′+1，M′+1）說明動態(tài)規(guī)劃求解最長公共序列長度及內(nèi)容的過程，如圖1所示。矩陣D（n，m）保存當(dāng)前sLCS（Si（n）′，Sj（m）′）及匹配的網(wǎng)格序列長度lLCS（Si（n）′，Sj（m）′），M1、M2及M3對應(yīng)D（n，m）由D（n-1，m-1）、D（n-1，m）及D（n，m-1）分別沿對角線、向下及向右方向傳遞得到。以Si（3）′（長度為3的網(wǎng)格序列Si′）與Sj（3）′（長度為3的網(wǎng)格序列Sj′）為例，設(shè)置δ=2，分析Si（3）′與Sj（2）′匹配至Si（3）′與Sj（3）′匹配的轉(zhuǎn)移過程。對Si（3）′與Sj（2）′，只有在M1下Gi′3與Gj′2相匹配，sLCS（Si（2）′，Sj（1）′）+SG′（Gi′3，Gj′2）取得最大值，并沿對角線由D（2，1）傳遞至D（3，2）。對Si（3）′與Sj（3）′，sLCS（Si（3）′，Sj（2）′）并未繼續(xù)傳遞，D（3，3）中的sLCS（Si（3）′，Sj（3）′）由D（2，2）傳遞得到，說明該方法從全局確定網(wǎng)格間的最佳匹配。D（m，n）中的lLCS（Si（n）′，Sj（m）′）遵循sLCS（Si（n）′，Sj（m）′）確定的傳遞方向，但當(dāng)D（n-1，m-1）沿對角線向D（m，n）傳遞時，lLCS（Si（n-1）′，Sj（m-1）′）是否加1還需檢驗sG（Gi′n，Gj′m）是否大于0，若大于0，說明Gi′n與Gj′m真正匹配且最長公共序列長度加1。當(dāng)n或m從0變化至N′或M′時，D（M′，N′）的sLCS（Si（N′）′，Sj（M′）′）及l(fā)LCS（Si（N′）′，Sj（M′）′）分別表示序列間網(wǎng)格相似度總和最長公共序列長度的最大值。若獲取最長公共序列中的匹配網(wǎng)格對，需借助矩陣D（M′+1，N′+1）反向搜索，但耗時長。

1.4?序列整體相似度及GS-DBSCAN

車輛的出行不僅受路網(wǎng)約束，還與起訖點的用地相關(guān)，故軌跡-網(wǎng)格序列的相似性度量應(yīng)充分考慮邊界與內(nèi)部的特征。對熱點小區(qū)間的任意2個網(wǎng)格序列Si′與Sj′，首先結(jié)合Gx，y與熱點小區(qū)zha的隸屬關(guān)系，將邊界網(wǎng)格分別替換成對應(yīng)的熱點小區(qū)Si′（od）={zh（i）a，Gi′2，…，Gi′N′－1，zh（i）a′}、Sj′（od）={zh（j）a，Gj′2，…，Gj′M′－1，zh（j）a′}，根據(jù)移動序列Si″={Gi′2，…，Gi′N′－1}與Sj″={Gj′2，…，Gj′M′－1}計算序列相似度sSeq（S′（od）i，

S′（od）j），其包含2部分：1）起訖熱點小區(qū)間的比較，若存在不同，則懲罰因子pf=－1，保證相似序列小于等于0；2）Si″與Sj″比較，以序列中較長的1個為基準(zhǔn)，計算最大公共子序列與其長度之比，計算公式為：

sSeq（S′（od）i，S′（od）j）=lLCS（Si″，Sj″）max（lSeq（Si″），lSeq（Sj″））+pf，

pf=0，zh（i）a=zh（j）a且zh（i）a′=zh（j）a′－1，zh（i）a≠zh（i）a或zh（i）a′≠zh（i）a′，

式中：lLCS（Si″，Sj″）為Si″與Sj″間匹配的最長網(wǎng)格序列長度，lSeq（Si″）、lSeq（Sj″）分別為Si″與Sj″的網(wǎng)格序列長度。

耦合路徑軌跡因起訖點或局部路段不同分為分離、匯入及交叉3種情況，如圖2所示。對同時與S3相耦合且長度差異較大的S4及S5，以較長序列為基準(zhǔn)的度量可正確表征S4與S5分別對S3的相似性，即受長度差異影響較小。對長度相近的路徑，如處于同一對小區(qū)的S1與S2，以較短或較長序列為基準(zhǔn)均可，前者比后者更接近1；但對不同小區(qū)的S3與S6，2種度量方法均存在局限性，此時需增加起訖邊界小區(qū)不同的限制條件進行區(qū)分。

計算Si′（od）與Sj′（od）間的相似度后，需轉(zhuǎn)化為距離度量才可進行GS-DBSCAN聚類，公式為：

dSeq（Si′（od），Sj′（od））=1－sSeq（Si′（od），Sj′（od））。

GS-DBSCAN的偽代碼與HG-DBSCAN類似，研究對象變成網(wǎng)格序列，不再贅述，得到熱點路徑集合R={rh1，rh2，…，rhU}，其中U為熱點路徑數(shù)。

2?案例分析

以2017-01-13青島市市南區(qū)的網(wǎng)約車訂單數(shù)據(jù)為案例驗證方法的有效性。區(qū)域覆蓋的經(jīng)度區(qū)間為（120.375 6°，120.400 0°），緯度區(qū)間為（36.063 1°，36.075 9°），面積約為4.79 km2。案例共采集33 538條訂單軌跡數(shù)據(jù)，每條訂單數(shù)據(jù)包含脫敏處理后的訂單編號及軌跡點列表2個字段，如訂單編號3e7a3f2d231的軌跡點列表為{（1 484 236 791 s?120.398 56°?36.007 014°），（1 484 236 794 s?120.398 57°?36.070 17°），（1 484 236 977 s?120.398 55°?36.070 18°）}，軌跡點列表中包含Unix時間戳及WGS84坐標(biāo)系下的經(jīng)、緯度。

2.1?熱點路徑識別結(jié)果

先聚類識別熱點小區(qū)，再將熱點小區(qū)作為網(wǎng)格邊界，增加約束條件，聚類識別熱點路徑。取網(wǎng)格尺寸為30 m×30 m，小于次干路及以上等級道路間的最小平行距離。假設(shè)車輛

在網(wǎng)格內(nèi)的位置均勻分布且速度為36～55 km/h，軌跡點平均采樣時間為3 s，則車輛每次移動的網(wǎng)格數(shù)為1.0～1.5。

首先建立參數(shù)不同間隔取值下的交叉組合，通過試算，設(shè)置λ=30，Eps=30 m，Num=2。根據(jù)所選組合進行HG-DBSCAN聚類，聚類后的簇總數(shù)為82，根據(jù)簇中包含的出行起訖點數(shù)降序排列選取前13個簇作為熱點小區(qū)，如圖3所示。

由圖3可知：該區(qū)域內(nèi)的熱點小區(qū)多分布在研究范圍內(nèi)道路的端點處，表示聯(lián)系研究范圍外熱點區(qū)域的主要途經(jīng)點。zh12和zh13位于研究范圍內(nèi)道路中間，結(jié)合該點的用地可知，周邊商業(yè)綜合體華潤萬象城成為農(nóng)歷新年前最后1個工作日的出行熱點。從熱點小區(qū)間出行期望線可知zh12與zh1間的聯(lián)系最強，說明華潤萬象城是研究范圍內(nèi)有強吸引力的出行熱點，同時對研究范圍外從zh1方向的居民有較強吸引力。

選取早、晚高峰時段（07：00—10：00，18：00—21：00）數(shù)據(jù)識別熱點路徑。通過試算，設(shè)置δ=2，Eps=0.2 m，Num=3。對13個熱點小區(qū)間的軌跡-網(wǎng)格序列進行GS-DBSCAN聚類，選取其中序列數(shù)較多的前20個簇作為熱點路徑集合，如圖4所示。由圖4結(jié)合熱點小區(qū)分布可知：熱點路徑主要分布在主干道，受相交道路或道路一側(cè)鄰近熱點小區(qū)的吸引，又存在若干條轉(zhuǎn)入、轉(zhuǎn)出的高相似路徑。

2.2?基于LCS的序列相似性度量算法對比與網(wǎng)格敏感性分析

保持δ=2，Eps=0.2 m，Num=3不變，對比分析不同計算方法下的聚類效果。方法1：只考慮內(nèi)部相似性且以對比序列中較短序列為基準(zhǔn)。方法2：只考慮內(nèi)部相似性且以對比序列中較長序列為基準(zhǔn)。方法3：本文建立同時考慮邊界與內(nèi)部相似性的GS-DBSCAN聚類且以對比序列中較長序列為基準(zhǔn)。

以zh1至zh5、zh7、zh9的網(wǎng)格序列集為例分別進行3種方法下的軌跡聚類，得到的簇如圖5所示。由圖5可知：方法3中的5個軌跡簇C0、C1、C2、C3、C4對應(yīng)區(qū)域中的路徑rh2、rh7、rh14、rh21、rh22；方法1中以較短序列為基準(zhǔn)，C1與其他簇軌跡的相似度均較高，在密度可達的傳遞作用下將其歸于1類；方法2中雖以較長序列為基準(zhǔn)，但C0與C2序列長度相近且重疊度較高，導(dǎo)致rh2與rh14無法區(qū)分；方法3中C0、C1、C2、C3、C4可較好地區(qū)分rh2、rh7、rh14、rh21與rh22的軌跡，說明本文考慮邊界與內(nèi)部相似性，且以對比序列中較長序列為基準(zhǔn)的方法合理。

分析GS-DBSCAND方法對網(wǎng)格尺寸的敏感性，在k=30 m的基礎(chǔ)上分別縮小、擴大1倍，相應(yīng)地調(diào)整δ進行聚類，得到不同路徑下的正確軌跡數(shù)，如表1所示。

由表1可知：聚類時間隨k的減小而增大，當(dāng)δ=4，k=15 m時，聚類時間約為440 s，僅比δ=2，k=30 m時的聚類時間增大43.32%，GS-DBSCAN方法的軌跡聚類運算效率較高；不同k和δ下，rh2、rh7、rh14、rh21及rh22的聚類結(jié)果整體偏差小于2%，受k和δ的影響較小。

3?結(jié)束語

為準(zhǔn)確識別熱點路徑，本文提出細(xì)分邊界與內(nèi)部兩部分度量序列間相似性的軌跡數(shù)據(jù)熱點路徑識別優(yōu)化方法，以區(qū)域網(wǎng)格化為基礎(chǔ)，將車輛軌跡映射為移動網(wǎng)格序列，通過HG-DBSCAN算法識別熱點區(qū)域，再將熱點區(qū)域作為網(wǎng)格邊界，增加約束條件，通過GS-DBSCAN算法識別熱點路徑。以青島市市南區(qū)的網(wǎng)約車訂單數(shù)據(jù)為案例進行熱點路徑識別，驗證方法的有效性。結(jié)果表明：本文提出的移動網(wǎng)格序列研究方法能準(zhǔn)確識別熱點小區(qū)，正確區(qū)分多出行起訖點分布下長度差異較大的分離、匯合與交叉耦合熱點路徑，且聚類運算效率較高，可為城市范圍內(nèi)交通組織設(shè)計、交通擁堵治理、智慧交通出行路徑規(guī)劃等城市交通規(guī)劃設(shè)計與管理提供參考依據(jù)。后續(xù)將結(jié)合實際工作，采集私家車、共享單車等更豐富的軌跡數(shù)據(jù)，擴大案例范圍，開展更全面的研究。

參考文獻：

[1]?WANG Y L， QIN K， CHEN Y X， et al. Detecting anomalous trajectories and behavior patterns using hierarchical clustering from taxi GPS data[J].ISPRS International Journal of Geo-Information， 2018，7（1）：25-45.

[2]?ZHANG D Q， LI N， ZHOU Z H， et al. Ibat： detectiong anomalous taxi trajectories from GPS traces[C]//Proceedings of 13th International Conference on Ubiquitous Computing. Beijing， China： Ubicomp，2011：17-21.

[3]?LIU C K， QIN K， KANG C G. Exploring time-dependent traffic congestion patterns from taxi trajectory data[C]//2015 2nd IEEE International Conference on Spatial Data Mining and Geographical Knowledge Services （ICSDM）. Fuzhou， China：IEEE，2015：39-45.

[4]?陳振華.基于軌跡數(shù)據(jù)的城市交通擁塞傳播模式挖掘[D].吉林：吉林大學(xué)，2019.

[5]?LIN S， SCHUTTER B D， XI Y G， et al. Efficient network-wide model-based predictive contral for urban traffic networks[J].Transportation Research Part C： Emerging Technologies， 2012，24：122-140.

[6]?MAZIMPAKA J D， TIMPF S. Trajectory data mining： a review of methods and applications[J].Journal of Spatial Information Science，2016，13：61-99.

[7]?李穎，趙莉，趙祥模，等.基于大貨車GPS數(shù)據(jù)的軌跡相似性度量有效性研究[J].中國公路學(xué)報，2020，33（2）：146-157.

[8]?KIM J， MAHMASSANI H S. Spatial and temporal characterization of travel patterns in a traffic network using vehicle trajectories[J].Transportation Research Part C： Emerging Technologies， 2015，7（10）：164-184.

[9]?馮琦森.基于出租車軌跡的居民出行熱點路徑和區(qū)域挖掘[D].重慶：重慶大學(xué)，2016.

[10]?趙欣.基于時空約束的城市熱點區(qū)域與熱點路徑挖掘[D].重慶：重慶大學(xué)，2017.

[11]?KANG H Y， KIM J S， LI K J. Similarity measures for trajectory of moving objects in cellular space[C]//Proceedings of the 2009 ACM Symposium on Applied Computing. Honolulu， Hawaii， USA： Spatial Information Society，2009：9-12.

[12]?吳俊偉，朱云龍，庫濤，等.基于網(wǎng)格聚類的熱點路徑探測[J].吉林大學(xué)學(xué)報（工學(xué)版），2015，45（1）：274-282.

[13]?王超.基于軌跡聚類的頻繁模式挖掘方法[D].杭州：浙江大學(xué)，2021.

[14]?LEE J G， HAN J W， WHANG K Y. Trajectory clustering： a partition-and-group framework[C]//Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. Beijing， China： SIGMOD，2007：593-604.

[15]?KANG H Y， KIM J S， LI K J. Similarity measures for trajectory of moving objects in cellular space[C]//Proceedings of the 2009 ACM Symposium on Applied Computing. Honolulu， Hawaii， USA：ACM Symposium on Applied Computing， 2009：1325-1330.

[16]?YANG H， SASAKI T， IIDA Y， et al. Estimation of origin-destination matrices from link traffic counts on congested networks[J].Transportation Research Part B： Methodological， 1992，26（6）：417-434.

[17]?ZHOU X S ， MAHMASSANI H S. Dynamic origin-destination demand estimation using automatic vehicle identification data[J].IEEE Transactions on Intelligent Transportation Systems， 2006，7（1）：105-114.

[18]?OU J S， LU J W， XIA J X， et al. Learn， assign， and search： real-time estimation of dynamic origin-destination flows using machine learning algorithms[J].IEEE Access， 2019， 7：26967-26983.

[19]?TANG K S， CAO Y M， CHEN C， et al. Dynamic origin-destination flow estimation using automatic vehicle identification data： a 3D convolutional neural network approach[J].Computer-Aided Civil and Infrastructure Engineering， 2021，36（1）：30-46.

[20]?CAO P， MIWA T， YAMAMOTO T， et al. Bilevel generalized least squares estimation of dynamic origin-destination matrix for urban network with probe vehicle data[J].Transportation Research Record： Journal of the Transportation Research Board， 2013， 2333：66-73.

[21]?CAO P， MIWA T， YAMAMOTO T， et al. Estimation of dynamic link flows and origin-destination matrices from lower polling frequency probe vehicle data[J].Journal of the Eastern Asia Society for Transportation Studies， 2013，10：762-775.

[22]?HUANG T， MA Y T， QIN Z T， et al. Origin-destination flow prediction with vehicle trajectory data and semi-supervised recurrent neural network[C]//2019 IEEE International Conference on Big Data. Los Angeles， CA， USA：IEEE， 2019：1450-1459.

[23]?GODAU M， ALT H. Computing the Fréchet distance between two polygonal curves[J].International Journal of Computational Geometry & Applications， 1995，5（1）：75-91.

Regional hotspot path identification based on grid clustering optimization

WENG Xuyan， ZHENG Shuni

Zhejiang Scientific Research Institute of Transport， Hangzhou 310023，China

Abstract：To solve the problem that the trajectory clustering method is difficult to accurately identify high-similarity hotspot paths， a hotspot path identification method that can distinguish between start and end points or local sections is proposed. The travel trajectory is mapped and compressed into a moving mesh sequence， and the spatial similarity measurement between sequences is distinguished from the boundary and the interior， integrated and transformed into distance， and spatial clustering based on grid sequencedensity-based spatial clustering of applications with noise （GS-DBSCAN） is performed. Taking the trajectory data of some taxis in Shinan District， Qingdao as an example， the clustering method that only considers internal similarity and is based on the shorter and longer sequences in the comparison sequence is verified. The results show that the GS-DBSCAN algorithm， which considers both boundary and internal similarity and is based on longer sequences， can correctly distinguish the separation， convergence， and cross-coupling hotspot paths with large length differences under the distribution of multiple travel start and end points. The influence of variable differences such as path length and grid size is less than 2%， and the clustering operation efficiency is high.

Keywords：hotspot path; boundary; interior; trajectory clustering

（責(zé)任編輯：趙玉真）

收稿日期：2023-02-02

基金項目：浙江省交通運輸科技計劃項目（2023001）

第一作者簡介：翁旭艷（1993—），女，上海人，工程師，工學(xué)碩士，主要研究方向為城市交通，E-mail：2445951226@qq.com。

DOI：10.3969/j.issn.1672-0032.2024.02.013