基于網(wǎng)格聚類優(yōu)化的區(qū)域熱點(diǎn)路徑識(shí)別

翁旭艷 鄭淑妮

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

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

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

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

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

1?熱點(diǎn)路徑識(shí)別優(yōu)化

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

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

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

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

式中?」為取整符號(hào)。

1.2?序列邊界

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

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

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

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

定義3?網(wǎng)格球面距離。任意2個(gè)網(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個(gè)網(wǎng)格經(jīng)度之差，Δγ為2個(gè)網(wǎng)格緯度之差；R為地球半徑。

HG-DBSCAN的網(wǎng)格密度是以熱點(diǎn)網(wǎng)格的經(jīng)緯度坐標(biāo)為圓心，在指定半徑Eps內(nèi)的熱點(diǎn)網(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算法流程包括輸入、初始化、運(yùn)行、輸出。

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

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

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

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

1.3?序列內(nèi)部

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

給定2個(gè)網(wǎng)格序列Si′={Gi′1，Gi′2，…，Gi′N′}與Sj′={Gj′1，Gj′2，…，Gj′M′}，計(jì)算Si′中的第n個(gè)網(wǎng)格Gi′n=（t x y）i′n和Sj′中的第m個(gè)網(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)。

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

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)格相似度，通過(guò)動(dòng)態(tài)規(guī)劃方法確定Si′與Sj′間的最長(zhǎng)公共序列，需將待求解的問(wèn)題劃分為若干階段，定義各階段的狀態(tài)及變量，確定階段間的狀態(tài)轉(zhuǎn)移方程。Si（n）′為Si′前n個(gè)網(wǎng)格，Sj（m）′為Sj′前m個(gè)網(wǎng)格，將sLCS（Si（n）′，Sj（m）′）狀態(tài)定義為Si（n）′與Sj（m）′間匹配網(wǎng)格相似度總和的最大值。當(dāng)n=0或m=0時(shí)，sLCS（Si（n）′，Sj（m）′）=0；若n、m均不為0，滿足無(wú)后效性前提下，sLCS（Si（n）′，Sj（m）′）與Si′前n-1個(gè)網(wǎng)格與Sj′前m-1個(gè)網(wǎng)格的相似度sLCS（Si（n-1）′，Sj（m-1）′）、Si′前n-1個(gè)網(wǎng)格與Sj′前m個(gè)網(wǎng)格的相似度sLCS（Si（n-1）′，Sj（m）′）、Si′前n個(gè)網(wǎng)格與Sj′前m-1個(gè)網(wǎng)格的相似度sLCS（Si（n）′，Sj（m-1）′）有關(guān)，分別對(duì)應(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。

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

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

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

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

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″間匹配的最長(zhǎng)網(wǎng)格序列長(zhǎng)度，lSeq（Si″）、lSeq（Sj″）分別為Si″與Sj″的網(wǎng)格序列長(zhǎng)度。

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

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

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

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

2?案例分析

以2017-01-13青島市市南區(qū)的網(wǎng)約車訂單數(shù)據(jù)為案例驗(yàn)證方法的有效性。區(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ù)包含脫敏處理后的訂單編號(hào)及軌跡點(diǎn)列表2個(gè)字段，如訂單編號(hào)3e7a3f2d231的軌跡點(diǎn)列表為{（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°）}，軌跡點(diǎn)列表中包含Unix時(shí)間戳及WGS84坐標(biāo)系下的經(jīng)、緯度。

2.1?熱點(diǎn)路徑識(shí)別結(jié)果

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

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

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

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

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

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

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

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

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

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

3?結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[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].中國(guó)公路學(xué)報(bào)，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]?馮琦森.基于出租車軌跡的居民出行熱點(diǎn)路徑和區(qū)域挖掘[D].重慶：重慶大學(xué)，2016.

[10]?趙欣.基于時(shí)空約束的城市熱點(diǎn)區(qū)域與熱點(diǎn)路徑挖掘[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]?吳俊偉，朱云龍，庫(kù)濤，等.基于網(wǎng)格聚類的熱點(diǎn)路徑探測(cè)[J].吉林大學(xué)學(xué)報(bào)（工學(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

基金項(xiàng)目：浙江省交通運(yùn)輸科技計(jì)劃項(xiàng)目（2023001）

第一作者簡(jiǎn)介：翁旭艷（1993—），女，上海人，工程師，工學(xué)碩士，主要研究方向?yàn)槌鞘薪煌?，E-mail：2445951226@qq.com。

DOI：10.3969/j.issn.1672-0032.2024.02.013