楊迪 徐文瑜 王鵬

摘 要：城市路網(wǎng)的合理劃分對于優(yōu)化區(qū)域交通控制以及協(xié)調(diào)策略的實(shí)施具有重要意義。為提高道路通行效率，提出基于密度峰值聚類算法的城市路網(wǎng)劃分方法，首先，綜合考慮交叉口靜態(tài)和動態(tài)因素的影響，構(gòu)建相鄰交叉口的關(guān)聯(lián)度模型，為合理量化交叉口之間的關(guān)聯(lián)程度提供定量描述。其次，提出改進(jìn)的密度峰值聚類算法，結(jié)合相鄰交叉口之間的關(guān)聯(lián)度對路網(wǎng)區(qū)域進(jìn)行劃分。針對密度峰值聚類算法中局部密度在不同規(guī)模數(shù)據(jù)集上差異較大的問題，引入KNN的思想，重新對局部密度進(jìn)行描述，其次為避免算法聚類中心人工選取的主觀性導(dǎo)致的誤差問題，采用肘部法則實(shí)現(xiàn)聚類中心的自動選取。實(shí)驗(yàn)結(jié)果表明，與改進(jìn)的Newman算法及Ncut算法相比，提出的改進(jìn)算法在優(yōu)化子區(qū)平均勻質(zhì)度上可分別降低12.5%和22.8%，提高了控制子區(qū)的劃分效果，使區(qū)域劃分效果更合理。

關(guān)鍵詞：區(qū)域劃分；交叉口關(guān)聯(lián)度；密度峰值聚類算法；KNN；肘部法則

中圖分類號：TP391；U491?? 文獻(xiàn)標(biāo)志碼：A?? 文章編號：1001-3695（2023）12-009-3578-06

doi：10.19734/j.issn.10013695.2023.04.0149

Road network classification method based on improved density peak clustering

Abstract：The reasonable classification of urban road network is of great significance for the optimization of regional traffic control and the implementation of coordination strategies.In order to improve road traffic efficiency，this paper proposed an urban road network classification method based on density peak clustering algorithm.Firstly，it comprehensively considered the influence of static and dynamic factors at intersections to construct a correlation degree model for adjacent intersections，and provided a quantitative description for reasonably quantifying the correlation degree between intersections.Secondly，it proposed an improved density peak clustering algorithm that combined the correlation between adjacent intersections to partition the road network area.To address the problem that the local density in the density peak clustering algorithm varies greatly on different size data sets，it introduced the idea of KNN to redescribe the local density，and secondly，in order to avoid the subjectivity of the manual selection of the algorithm clustering center which could lead to error problem，using the elbow rule to realize the automatic selection of the clustering center.The experimental results show that compared with the improved Newman algorithm and Ncut algorithm，the improved proposed algorithm can reduce 12.5% and 22.8% respectively in optimizing the flat homogeneity of subregions，improve the effect of control subregion division and make the region division effect more reasonable.

Key words：regional division；intersection correlation；density peak clustering；KNN；elbow law

0 引言

隨著經(jīng)濟(jì)社會的不斷發(fā)展，我國汽車保有量在逐年攀升，隨之而來了交通擁堵和安全問題。作為城市路網(wǎng)協(xié)調(diào)控制的重要組成部分，合理地對交通路網(wǎng)進(jìn)行劃分，不僅可以提高交通控制系統(tǒng)的靈活性，降低路網(wǎng)管理的復(fù)雜性，而且為交通控制子區(qū)協(xié)調(diào)策略的實(shí)施奠定基礎(chǔ)，從而達(dá)到緩解交通擁堵的目的。

在對城市路網(wǎng)進(jìn)行擁堵疏導(dǎo)時，應(yīng)當(dāng)根據(jù)其各自的交通流特性進(jìn)行分區(qū)協(xié)調(diào)控制，即以子區(qū)為單位，依據(jù)子區(qū)內(nèi)的交通流特性進(jìn)行協(xié)調(diào)控制。在路網(wǎng)區(qū)域的劃分過程中，主要的依據(jù)是交叉口之間的關(guān)聯(lián)度，關(guān)聯(lián)度是定量描述兩個交叉口在連接關(guān)系上關(guān)聯(lián)程度的指標(biāo)，也是評價交叉口是否應(yīng)該歸屬到同一個控制子區(qū)中進(jìn)行協(xié)調(diào)控制的重要依據(jù)。針對這一問題，國內(nèi)外學(xué)者開展了廣泛的研究。Whitson模型［1］作為經(jīng)典且目前仍在廣泛使用的關(guān)聯(lián)度計算方法，考慮到道路中交通流量、路段行程時間及交叉口間距等因素的影響，來構(gòu)建關(guān)聯(lián)度模型，但該模型并沒有充分考慮下游交叉口存在等待車輛時造成行程時間變化的問題，此外忽略了車輛從上游交叉口到達(dá)下游交叉口的離散問題。劉端陽等人［2］以子區(qū)總關(guān)聯(lián)度最大為目標(biāo)，計算交通流量和路段速度信息交通態(tài)勢并結(jié)合路段距離得到關(guān)聯(lián)度指標(biāo)。Lan等人［3］從車隊離散性對交通協(xié)調(diào)控制的影響出發(fā)，通過對交通控制劃分關(guān)鍵技術(shù)的研究，采用相關(guān)分析法和回歸分析法建立基于路段交通流量和路段長度相關(guān)聯(lián)的相鄰交叉口的關(guān)聯(lián)度模型。在此基礎(chǔ)上，Xing等人［4］將交叉口之間的關(guān)聯(lián)度與道路排隊長度、通行能力、交叉口之間的間距、交叉口流量以及交通流分散等影響因素結(jié)合起來，通過將車輛行駛速度和排隊長度等作為評估指標(biāo)選擇基準(zhǔn)交叉口，從而建立了基于邊界指標(biāo)的關(guān)聯(lián)度模型。針對交通區(qū)域的具體劃分方法，Dong等人［5］基于宏觀基本圖理論對問題區(qū)域劃分問題進(jìn)行求解，首先結(jié)合回歸分析方法及相關(guān)系數(shù)理論，提出基于聚類分析的交通關(guān)鍵控制區(qū)域識別方法，實(shí)現(xiàn)了與路網(wǎng)動態(tài)特征的緊密結(jié)合。李明東等人［6］通過交通路網(wǎng)相似度構(gòu)建帶權(quán)值的路網(wǎng)拓?fù)鋱D，并采用NCut算法對組件相似性為標(biāo)準(zhǔn)的路網(wǎng)進(jìn)行歸一劃分，針對NCut算法無法每次判斷子區(qū)數(shù)量的問題，引入各子區(qū)間的勻質(zhì)性均值進(jìn)行改進(jìn)。有部分學(xué)者采用社區(qū)發(fā)現(xiàn)算法對區(qū)域劃分問題進(jìn)行求解。鄭黎黎等人［7］將路網(wǎng)抽象為以路段行程時間為權(quán)值的網(wǎng)絡(luò)，并參照強(qiáng)社團(tuán)和弱社團(tuán)的思想，提出了強(qiáng)連接區(qū)域和弱連接區(qū)域作為評價指標(biāo)，并提出改進(jìn)的GN算法對路網(wǎng)進(jìn)行劃分。王磊等人［8］依據(jù)交叉口關(guān)聯(lián)度的計算，將實(shí)際路網(wǎng)抽象為網(wǎng)絡(luò)，并以交叉口之間的關(guān)聯(lián)度作為抽象路網(wǎng)的邊權(quán)，以模塊度Q作為劃分標(biāo)準(zhǔn)，重新對傳統(tǒng)的Newman算法有關(guān)概念公式進(jìn)行定義，最終實(shí)現(xiàn)交通路網(wǎng)的區(qū)域劃分。采用聚類分析方法對交通路網(wǎng)進(jìn)行劃分，也是近年來學(xué)者研究的熱點(diǎn)。韓利釗等人［9］利用網(wǎng)格密度差將數(shù)據(jù)空間劃分為密度不同的區(qū)域，并依據(jù)區(qū)域內(nèi)的密度自動獲取對應(yīng)的Eps，最終提出DBSCAN多密度聚類算法實(shí)現(xiàn)區(qū)域劃分。閆學(xué)東等人［10］采用網(wǎng)格模型對研究區(qū)域進(jìn)行處理，并將獲取的對應(yīng)實(shí)際數(shù)據(jù)匹配到對應(yīng)的網(wǎng)格中，最后結(jié)合手肘法與輪廓系數(shù)法，采用基于網(wǎng)格的Kmeans++算法獲取最佳聚類數(shù)量并完成區(qū)域劃分。Niu等人［11］考慮了時空軌跡信息的完整頻譜，將每個密集時間間隔處對應(yīng)的整個交通網(wǎng)絡(luò)劃分到同一個控制子區(qū)作為劃分思想，采用改進(jìn)的密度峰值聚類算法實(shí)現(xiàn)對交通路網(wǎng)的區(qū)域劃分。

綜上所述，目前對城市路網(wǎng)進(jìn)行控制子區(qū)劃分時，主要是依托交叉口的關(guān)聯(lián)特性來實(shí)現(xiàn)的，但存在子區(qū)劃分關(guān)聯(lián)指標(biāo)考慮不全面，最終導(dǎo)致區(qū)域劃分效果不理想甚至粗糙的問題。另外針對交通區(qū)域的劃分問題，Kmeans算法存在一定的局限性，其對高維的數(shù)據(jù)對象聚類效果不佳。DBSCAN算法則對聚類間距要求嚴(yán)格，且適用的樣本集合范圍較窄，因此對于求解城市路網(wǎng)大數(shù)量級的問題并不適合。因密度峰值聚類算法（density peaks clustering，DPC）具備能夠自動識別出任意形狀的簇，且思想簡單，在處理噪聲孤立點(diǎn)上具有良好表現(xiàn)等優(yōu)勢，被廣泛研究和應(yīng)用。

然而傳統(tǒng)的密度峰值聚類算法也存在著一些不足，其中截斷距離的選取依據(jù)是大部分樣本點(diǎn)具有的平均鄰居個數(shù)為數(shù)據(jù)集整體大小的1%～2%，這會使得參數(shù)在不同數(shù)據(jù)集上選取差異較大，且局部密度的計算在不同的數(shù)據(jù)集上計算方式也不統(tǒng)一。此外，聚類中心通常需要人工借助決策圖進(jìn)行選取，具有較強(qiáng)的主觀性，不同人可能選取的聚類中心不同，容易產(chǎn)生誤差問題。

鑒于此，本文綜合考慮道路交通流量、信號周期、車流離散性、車流排隊長度以及路段距離等因素的影響，構(gòu)建相鄰交叉口的關(guān)聯(lián)度模型。在此基礎(chǔ)上，采用改進(jìn)密度峰值聚類算法融合關(guān)聯(lián)度模型，實(shí)現(xiàn)對交通路網(wǎng)的區(qū)域劃分，針對密度峰值聚類算法中局部密度在不同規(guī)模數(shù)據(jù)集上差異較大的問題，引入KNN的思想對局部密度進(jìn)行重新描述。另外，由于在算法中聚類中心需要人工進(jìn)行選取，容易導(dǎo)致誤差問題，本文借用肘部法則實(shí)現(xiàn)聚類中心自動選取。最后通過實(shí)際道路運(yùn)行數(shù)據(jù)進(jìn)行實(shí)驗(yàn)分析，驗(yàn)證本文算法對于交通區(qū)域劃分的合理性和優(yōu)越性。

1 相鄰交叉口關(guān)聯(lián)度模型

相鄰交叉口之間的關(guān)聯(lián)性通常受到多種因素的影響，比如路段流量、信號周期、車流速度、車輛排隊長度、車流離散性和交叉口間距等，其中由于相鄰兩個交叉口之間的間距是固定的，所以通常把它作為靜態(tài)影響因素進(jìn)行考慮，而由于道路流量、信號周期、車流離散性、車輛排隊等因素會動態(tài)實(shí)時變化，也會實(shí)時影響交叉口之間的關(guān)聯(lián)程度，現(xiàn)有的相關(guān)模型中大多都沒有充分全面地考慮上述影響。因此，本文針對這一問題，通過分別建立交通流量關(guān)聯(lián)系數(shù)、道路交通狀態(tài)關(guān)聯(lián)系數(shù)和信號周期關(guān)聯(lián)系數(shù)，綜合考慮交通流量、離散性、排隊長度、路段距離、信號周期等方面對交叉口關(guān)聯(lián)度的影響，建立基于相鄰交叉口的總關(guān)聯(lián)度模型。

1.1 交通流量關(guān)聯(lián)系數(shù)

由于駕駛?cè)藛T的駕駛習(xí)慣、車速差異、路段長度以及其他因素的影響，會導(dǎo)致車輛從上游交叉口駛出后，在行駛到達(dá)下游交叉口的過程中車流發(fā)生離散現(xiàn)象，而經(jīng)典且廣泛應(yīng)用的Whitson模型［1］在考慮交通流量和行程時間之間的關(guān)系時，忽略了車流離散性對關(guān)聯(lián)度的影響。另外在Whitson模型中，車輛的行程時間為車輛從上游交叉口駛出后到達(dá)下游交叉口停車線位置所花費(fèi)的時間，并未充分考慮下游交叉口可能存在排隊車輛的情況。Whitson模型關(guān)聯(lián)流量流向如圖1所示。

因此本文基于Whitson模型，引入胡華排隊長度［12］對行程時間t進(jìn)行改進(jìn)，如式（1）所示。另外加入離散系數(shù)以實(shí)現(xiàn)對車流離散性的考慮，目前常用的離散模型有Robertson模型［13］和Pacey模型［14］。這兩個模型的區(qū)別主要體現(xiàn)在它們在行程時間上選用的數(shù)學(xué)模型分別是幾何分布和正態(tài)分布，但由于Robertson模型中需要的參數(shù)較少，且計算方便，所以本文選取Robertson提出的車流離散系數(shù)模型對Whitson模型進(jìn)行改進(jìn)，如式（2）所示。

其中：F為離散系數(shù)；T為相鄰兩個斷面間車輛平均行駛時間的0.8倍；a為常數(shù)，經(jīng)過我國學(xué)者的適用性研究，a取值0.1～0.15，較符合我國的實(shí)際交通流特性。

由于交通流是雙向的，所以交叉口總流量的關(guān)聯(lián)系數(shù)Sq（ij）選取Sq（i→j）和Sq（j→i）中的較大值，具體如式（3）所示。

Sq（ij）=max（Sq（i→j），Sq（j→i））（3）

其中：Sq（ij）表示交叉口i和交叉口j之間的流量關(guān)聯(lián)系數(shù)，Sq（i→j）表示交叉口i到交叉口j方向的流量關(guān)聯(lián)系數(shù)；Sq（j→i）表示交叉口j到交叉口i方向的流量關(guān)聯(lián)系數(shù)。

1.2 道路交通狀態(tài)關(guān)聯(lián)系數(shù)

同一個控制子區(qū)的交叉口應(yīng)該具有相同的道路交通狀態(tài)。道路交通狀態(tài)可以反映相鄰交叉口之間道路的擁擠程度，也是描述相鄰交叉口關(guān)聯(lián)性強(qiáng)弱的重要依據(jù)。因此在進(jìn)行子區(qū)劃分時，應(yīng)考慮道路交通狀態(tài)這一因素，而道路交通狀態(tài)關(guān)聯(lián)性可以由路段長度和路段交通流量來進(jìn)行量化反映。因此基于現(xiàn)有研究，建立道路交通狀態(tài)關(guān)聯(lián)系數(shù)的計算公式如下：

其中：SC（i，j）為道路交通狀態(tài)關(guān)聯(lián)系數(shù)，SC（i，j）∈［0，1］；Cij為交叉口i到交叉口j方向的交通狀態(tài)；CSij為飽和狀態(tài)下交叉口i到交叉口j方向的交通狀態(tài)；qi表示車道i上的車輛數(shù)，Nij為交叉口i和交叉口j方向的進(jìn)口車道數(shù)；Lij為交叉口i和j之間的路段長度。

1.3 信號周期關(guān)聯(lián)系數(shù)

對于具有相同或者成倍數(shù)關(guān)系的信號周期和穩(wěn)定相位差的交叉口，其相鄰之間表現(xiàn)出較強(qiáng)的關(guān)聯(lián)性，相反，若相鄰交叉口之間的信號周期或交通參數(shù)差異較大，則會導(dǎo)致車輛的平均延誤增加，從而不利于信號協(xié)調(diào)控制策略的實(shí)施。因此在計算交叉口之間的關(guān)聯(lián)度時，應(yīng)考慮信號周期對交叉口關(guān)聯(lián)度的影響。相鄰交叉口之間信號周期關(guān)聯(lián)系數(shù)的表達(dá)式如式（6）所示。

其中：ST（i，j）表示交叉口i和交叉口j的信號周期關(guān)聯(lián)系數(shù)；TA表示交叉口A的信號周期；TB表示交叉口B的信號周期；θ為相鄰交叉口信號周期比值的最大值，一般取值為2，ST（i，j）∈［0，1］。

因此本文綜合考慮上述關(guān)聯(lián)系數(shù)對關(guān)聯(lián)度的影響，結(jié)合式（3）（4）（6）建立相鄰交叉口總關(guān)聯(lián)度模型，具體如式（7）所示。

Sij=Sq（ij）SC（i，j）ST（i，j）（7）

其中：Sij表示交叉口i和交叉口j之間的關(guān)聯(lián)度；Sq（ij）表示交叉口i和交叉口j之間的流量關(guān)聯(lián)系數(shù)；SC（i，j）為交叉口i和j之間的道路交通狀態(tài)關(guān)聯(lián)系數(shù)；ST（i，j）表示交叉口i和交叉口j的信號周期關(guān)聯(lián)系數(shù)。

通過式（7），可得到相鄰交叉口總關(guān)聯(lián)度的矩陣，如式（8）所示。

2 密度峰值聚類算法

密度峰值聚類算法是Rodriguez等人［15］提出的，由于該算法能夠自動識別聚類中心，且能夠?qū)θ我庑螤畹臄?shù)據(jù)進(jìn)行高效聚類，自提出起就受到學(xué)者的廣泛關(guān)注。該方法的聚類實(shí)現(xiàn)基于兩個核心假設(shè)：a）聚類中心的密度比周圍鄰居點(diǎn)的密度更大；b）聚類中心與比它們更高密度的數(shù)據(jù)點(diǎn)之間的距離要相對較遠(yuǎn)。即兩個聚類中心中間有一定的距離。

對于數(shù)據(jù)集中的任意一個數(shù)據(jù)點(diǎn)xi，都需要計算其局部密度ρi和最近鄰距離δi。數(shù)據(jù)點(diǎn)xi截斷核的局部密度定義如式（9）所示，密度估計核函數(shù)如式（10）所示，其表示以數(shù)據(jù)點(diǎn)xi為搜索中心，在截斷距離dc范圍內(nèi)的樣本點(diǎn)數(shù)量。

其中：X（x）表示密度估計核函數(shù)；ρi表示局部密度；dij表示樣本點(diǎn)xi與樣本點(diǎn)xj之間的歐氏距離；dc表示截斷距離。

當(dāng)數(shù)據(jù)集的規(guī)模較小時，可通過高斯核函數(shù)定義的局部密度公式進(jìn)行求解，如式（11）所示，其表示數(shù)據(jù)點(diǎn)i到數(shù)據(jù)集中其他樣本點(diǎn)的高斯距離之和。

樣本點(diǎn)i到比其密度更高點(diǎn)的最近鄰距離δi定義如式（12）所示。

利用每個樣本點(diǎn)獲得的局部密度ρi和最近鄰距離δi繪制決策圖，如圖2所示。然后選取ρ和δ，同時，大的樣本點(diǎn)作為聚類中心，具體來說，選擇坐標(biāo)圖中靠右上角位置的樣本點(diǎn)，最后將非聚類中心的點(diǎn)分配到距離其最近的聚類中心所在的簇中完成聚類過程。

3 基于改進(jìn)密度峰值聚類的交通區(qū)域劃分

3.1 融合關(guān)聯(lián)度模型的自適應(yīng)截斷距離選取

傳統(tǒng)的密度峰值聚類算法截斷距離依靠數(shù)據(jù)集規(guī)模進(jìn)行選取，針對不同規(guī)模的數(shù)據(jù)集，選取差異較大，且這種選取方法會導(dǎo)致局部密度的計算考慮的是數(shù)據(jù)集中所有節(jié)點(diǎn)對該節(jié)點(diǎn)的密度貢獻(xiàn)值，忽略了該節(jié)點(diǎn)核心局部的獨(dú)特性和重要性。針對城市交通區(qū)域，路網(wǎng)關(guān)聯(lián)度主要是受與其有關(guān)聯(lián)關(guān)系的交叉口的影響，因此本文綜合路網(wǎng)的拓?fù)浣Y(jié)構(gòu)，將相鄰交叉口的關(guān)聯(lián)度與密度峰值聚類算法進(jìn)行融合，著重考慮節(jié)點(diǎn)附近距離其最近的k個鄰居節(jié)點(diǎn)對該節(jié)點(diǎn)的貢獻(xiàn)值，對截斷距離的計算進(jìn)行重新描述，如式（13）所示，最近鄰距離與其平均值的定義如式（14）（15）所示。

其中：dc表示截斷距離；N為節(jié)點(diǎn)的總規(guī)模；μK為所有節(jié)點(diǎn)中最近鄰距離δKi的平均值，表示所有節(jié)點(diǎn)的分散程度；δKi表示樣本點(diǎn)i到其第K個鄰居節(jié)點(diǎn)的距離；dij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j之間的距離。

在計算截斷距離之后，本文使用高斯核函數(shù)對不同規(guī)模的數(shù)據(jù)集局部密度的計算進(jìn)行統(tǒng)一，利用節(jié)點(diǎn)局部核心區(qū)域?qū)υ摴?jié)點(diǎn)的密度貢獻(xiàn)值大的特點(diǎn)，通過使用K近鄰的思想，將局部密度的計算公式定義如式（16）所示。其中，dij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j之間的距離，本文選用相鄰交叉口的關(guān)聯(lián)度參見式（8）對節(jié)點(diǎn)間的距離dij重新描述。

其中：ρi表示局部密度；dij表示樣本點(diǎn)xi與樣本點(diǎn)xj之間的關(guān)聯(lián)度；N為節(jié)點(diǎn)的總規(guī)模；μK為所有節(jié)點(diǎn)中最近鄰距離δKi的平均值；δKi表示樣本點(diǎn)i到其第K個鄰居節(jié)點(diǎn)的距離。

3.2 聚類中心的選取以及分配策略

傳統(tǒng)密度峰值聚類算法選取聚類中心需要依靠人工在決策圖中選取局部密度ρi和最近鄰距離δi同時大的點(diǎn)，這種選取方法不僅具有主觀性和隨機(jī)性，而且對于某些復(fù)雜的數(shù)據(jù)集，通過人工在決策圖中選取聚類中心會非常困難。另外，聚類中心的不合理選取也會對非聚類中心的分配結(jié)果產(chǎn)生影響，容易導(dǎo)致誤差問題，最終使得聚類準(zhǔn)確率降低。因此本文對選取聚類中心的決策函數(shù)進(jìn)行定義，如式（17）所示，同時為了避免決策函數(shù)因局部密度或者距離分布不均而受到單一變量影響的情況發(fā)生，對γ 進(jìn)行歸一化處理，如式（18）所示。

其中：ρi表示樣本點(diǎn)i的局部密度；δi表示最近鄰距離。

由上述公式可知，節(jié)點(diǎn)的γ值越大，則成為聚類中心的可能性就越大。將所有節(jié)點(diǎn)的γi在決策圖中進(jìn)行降序處理，可得到γ的降序決策圖，如圖3所示。

由于γ決策圖中聚類中心和非聚類中心之間具有明顯跳躍的特點(diǎn)，所以定義具有明顯差異的點(diǎn)為該決策圖的拐點(diǎn)P，利用肘方法中基于搜索的起點(diǎn)和終點(diǎn)連線的概念，判斷樣本點(diǎn)的γ值到連線的距離。由于聚類中心到非聚類中心明顯跳躍，這會導(dǎo)致拐點(diǎn)P后的點(diǎn)M到直線AB的距離相對較遠(yuǎn)，所以本文求解樣本點(diǎn)γ值到直線AB最大距離值所屬的最大k值，并將其前一個樣本點(diǎn)k-1作為最終的類簇劃分?jǐn)?shù)量。連接決策圖中搜索γ起始點(diǎn)之間的連線，定義所求拐點(diǎn)為P，則拐點(diǎn)的后一個點(diǎn)為M，直線AB的表達(dá)式為y=kx+b。聚類數(shù)量的確定方法如圖4所示。

此外，出于對現(xiàn)實(shí)路網(wǎng)的實(shí)際情況以及算法求解復(fù)雜度的考慮，一般情況下，路網(wǎng)中很少出現(xiàn)半數(shù)以上孤立點(diǎn)交叉口，因此算法的遍歷次數(shù)及聚類中心拐點(diǎn)的確定方法如式（19）（20）所示。

因此聚類中心的集合可以表示為

{i|i

其中：N表示路網(wǎng)節(jié)點(diǎn)的總規(guī)模；k表示直線AB對應(yīng)的斜率；b表示直線AB對應(yīng)的截距；x0表示樣本點(diǎn)i對應(yīng)的橫坐標(biāo)；y0表示樣本點(diǎn)對應(yīng)的縱坐標(biāo)。

在得到聚類中心后，還需要對非聚類中心的節(jié)點(diǎn)進(jìn)行進(jìn)一步分配以完成聚類過程。本文考慮現(xiàn)有路網(wǎng)的拓?fù)浣Y(jié)構(gòu)以及算法的特性，提出非聚類中心的分配策略。

a）對于所有樣本節(jié)點(diǎn)，分別計算其與各聚類中心的距離，并將其分配到在其dc范圍內(nèi)距離該節(jié)點(diǎn)最近的類簇中。

b）對于a）中未分配的節(jié)點(diǎn)，借用KNN的思想，判斷其dc范圍內(nèi)密度比該節(jié)點(diǎn)高的所有節(jié)點(diǎn)，并將其分配到密度值比其大且歸屬同一類簇數(shù)量最多的節(jié)點(diǎn)所在的類簇中。

c）若還存在未分配的節(jié)點(diǎn)，則選擇距離未分配節(jié)點(diǎn)最近且局部密度比未分配節(jié)點(diǎn)大的樣本點(diǎn)，確認(rèn)其所屬類簇，并將未分配節(jié)點(diǎn)歸并到該類別中。

基于以上描述，采用改進(jìn)的密度峰值聚類算法對交通區(qū)域進(jìn)行劃分流程如圖5所示。

a）確定需要區(qū)域劃分的路網(wǎng)，分別計算路網(wǎng)中相鄰交叉口的交通流量關(guān)聯(lián)系數(shù)、道路交通狀態(tài)關(guān)聯(lián)系數(shù)以及信號周期關(guān)聯(lián)系數(shù)，最終獲得基于相鄰交叉口的總關(guān)聯(lián)度Sij。

b）依據(jù)式（13）計算截斷距離dc。

c）將截斷距離dc和相鄰交叉口的關(guān)聯(lián)度Sij代入式（16）得到樣本點(diǎn)的局部密度ρ；并且計算當(dāng)前樣本點(diǎn)的最近鄰距離。

d）根據(jù)式（17）計算每個交叉口的γ，并分別依據(jù)式（18）對每個交叉口的γ進(jìn)行歸一化處理。

e）繪制決策圖并將歸一化處理后的γ降序。

f）利用聚類中心到非聚類中心在決策圖中明顯變化的特點(diǎn)，參考手肘法的思想，求解樣本點(diǎn)到直線AB距離最大的樣本點(diǎn)所在的k值，即為所求拐點(diǎn)的后一個點(diǎn)。

g）確定拐點(diǎn)后，也即確定了聚類中心的個數(shù)，將剩余的非聚類中心按照分配原則來進(jìn)行分配，以此完成聚類過程。

4 實(shí)驗(yàn)與結(jié)果分析

本文參照實(shí)際路網(wǎng)，采用VISSIM對交通路網(wǎng)進(jìn)行仿真實(shí)驗(yàn)，然后計算相鄰交叉口的總關(guān)聯(lián)度。在此基礎(chǔ)上，使用改進(jìn)的密度峰值聚類算法對路網(wǎng)進(jìn)行區(qū)域劃分，并通過對比多種算法以驗(yàn)證改進(jìn)密度峰值聚類算法的合理性和優(yōu)越性。

本文選擇安徽省宣城區(qū)部分區(qū)域路網(wǎng)作為路網(wǎng)研究對象，道路數(shù)據(jù)來源于OpenITS網(wǎng)絡(luò)開放數(shù)據(jù)，選擇雙塔路、昭亭路、梅溪路、狀元路、鰲峰路、疊嶂路等組成的區(qū)域路網(wǎng)，其中包括16個信號交叉口，21條路段。本文通過對開放數(shù)據(jù)進(jìn)行統(tǒng)計整理，結(jié)合百度地圖獲取研究路網(wǎng)的交叉口距離，以及道路的車道數(shù)，選擇17：00～18：00高峰時期的交通檢測數(shù)據(jù)進(jìn)行實(shí)驗(yàn)驗(yàn)證，在此基礎(chǔ)上，利用VISSIM進(jìn)行路網(wǎng)建模。具體研究路網(wǎng)的抽象圖如圖6所示。

為了方便后續(xù)對相鄰交叉口關(guān)聯(lián)度的計算，以及路網(wǎng)區(qū)域劃分，將區(qū)域研究路網(wǎng)抽象成以交叉口為點(diǎn)、連接路網(wǎng)為邊的無向網(wǎng)絡(luò)拓?fù)鋱D，并對交叉口進(jìn)行編號，如圖7所示。

通過百度地圖對各交叉口之間的間距進(jìn)行測量，其平均間距約為483 m，各相鄰交叉口之間的間距具體如表1所示。

根據(jù)前文提出的關(guān)聯(lián)度計算模型，結(jié)合實(shí)際路網(wǎng)數(shù)據(jù)，分別計算相鄰交叉口的交通流量關(guān)聯(lián)系數(shù)、道路交通狀態(tài)關(guān)聯(lián)系數(shù)以及信號周期關(guān)聯(lián)系數(shù)，從而得到相鄰交叉口的總關(guān)聯(lián)度，如表2所示。

本文使用MATLAB對改進(jìn)的密度峰值聚類算法進(jìn)行實(shí)現(xiàn)，通過對各交叉口局部密度和最近鄰距離的計算，可以得到γ值，然后利用決策降序圖，從而確定聚類中心，如圖8所示。

由圖8可知，拐點(diǎn)為樣本點(diǎn)P，因此聚類中心的數(shù)量為5。結(jié)合上文的剩余樣本點(diǎn)聚類分配原則，得到基于改進(jìn)密度峰值聚類的交通區(qū)域劃分結(jié)果，如圖9所示。

由圖9可知，路網(wǎng)總共被劃分為5個子區(qū)域，其中，子區(qū)1包括交叉口1、2、3、5，子區(qū)2包括交叉口4和6，子區(qū)3包括交叉口7、10、13、14，子區(qū)4包括交叉口11、15、16，子區(qū)5包括交叉口8、9、12。

為驗(yàn)證改進(jìn)密度峰值聚類算法的劃分效果，本文選擇改進(jìn)的Newman算法［8］以及Ncut算法［16］對同一個研究路網(wǎng)進(jìn)行區(qū)域劃分，最后通過劃分子區(qū)數(shù)、歸一化總方差以及平均勻質(zhì)度三個方面對區(qū)域劃分效果進(jìn)行對比分析。通過采用改進(jìn)的Newman算法對路網(wǎng)進(jìn)行區(qū)域劃分，可得到聚類劃分結(jié)果，如圖10所示?；贜cut算法對交通路網(wǎng)進(jìn)行劃分，可得到聚類劃分結(jié)果，如圖11所示。

對比圖9～11可知，改進(jìn)密度峰值聚類算法能夠更為細(xì)致地考慮到道路的交通流特性，以對路網(wǎng)進(jìn)行區(qū)域劃分。具體而言，比如交叉口6和7，由于兩個交叉口之間的距離相對較遠(yuǎn)，導(dǎo)致交叉口之間的關(guān)聯(lián)性也相對較弱，所以不適合將交叉口6和7劃分到同一個控制子區(qū)中進(jìn)行信號控制，而改進(jìn)的Newman算法和Ncut算法都將其劃分到同一個控制子區(qū)中進(jìn)行研究。另外，交叉口10和14相對于交叉口14和15，交通流量更大，這也意味著交叉口10和14相互影響的程度要比交叉口14和15大，關(guān)聯(lián)性也會相對更大，因此應(yīng)該將交叉口10和14劃分為同一個控制子區(qū)，而改進(jìn)Newman算法和Ncut算法中，都將交叉口10和14劃分到不同的控制子區(qū)內(nèi)。

由于改進(jìn)密度峰值聚類算法交通區(qū)域劃分模型考慮了車輛在行駛過程中路段間距對車流離散性的影響，以及道路車流量過大時存在車輛排隊的問題，分別引入了離散系數(shù)以及胡華排隊長度對道路交通流量模型進(jìn)行修正，所以在路網(wǎng)劃分中，與其他兩個算法相比，更能夠根據(jù)道路交通流特性進(jìn)行劃分，且劃分效果更好。

為了更加直觀地了解這三個算法對交通子區(qū)的劃分效果，下文將從劃分子區(qū)數(shù)、歸一化總方差以及平均勻質(zhì)度三個方面對本文改進(jìn)算法與其他算法進(jìn)行比較，具體如表3所示。

從評價指標(biāo)的對比結(jié)果圖中可知，三個劃分算法在子區(qū)劃分?jǐn)?shù)量上基本相同，但改進(jìn)密度峰值聚類算法在歸一化總方差TVn及平均勻質(zhì)度AHk方面均低于其他兩個算法，也即表明改進(jìn)密度峰值聚類算法劃分的子區(qū)勻質(zhì)性優(yōu)于其他算法。其中，對比改進(jìn)的Newman算法，本文算法在TVn和AHk分別降低了17.3%和12.5%；而相比于Ncut算法，本文算法在TVn和AHk方面分別降低了21.5%和22.8%，表明了結(jié)合交叉口關(guān)聯(lián)度以及路網(wǎng)拓?fù)浣Y(jié)構(gòu)進(jìn)行算法改進(jìn)和區(qū)域劃分，能夠有效降低控制子區(qū)內(nèi)部的異質(zhì)性，提高控制子區(qū)的劃分效果，同時也驗(yàn)證了算法子區(qū)劃分的合理性與有效性。

由于本文的改進(jìn)算法需要計算節(jié)點(diǎn)之間的歐氏距離，也即節(jié)點(diǎn)之間的關(guān)聯(lián)度，另外由于借助KNN的思想統(tǒng)一描述局部密度，進(jìn)而實(shí)現(xiàn)聚類中心自動選取等目的，所以本文的改進(jìn)算法相較于改進(jìn)的Newman算法時間復(fù)雜度會高一點(diǎn)，但對比Ncut算法，其時間復(fù)雜度低于Ncut算法。

5 結(jié)束語

本文提出了考慮路網(wǎng)拓?fù)浣Y(jié)構(gòu)以及融合交叉口關(guān)聯(lián)度的密度峰值聚類路網(wǎng)劃分方法。實(shí)驗(yàn)結(jié)果表明，針對同一劃分區(qū)域，改進(jìn)密度峰值聚類算法能夠更為細(xì)致地考慮到道路的交通流特性，以對路網(wǎng)進(jìn)行區(qū)域劃分，充分考慮了車輛在行駛過程中路段間距對車流離散性以及道路車流量過大時存在車輛排隊等因素的影響，且能夠更好地優(yōu)化子區(qū)劃分后子區(qū)內(nèi)部的勻質(zhì)度，使得子區(qū)劃分結(jié)果更加合理，同時也為子區(qū)內(nèi)部協(xié)調(diào)控制策略的實(shí)施奠定了基礎(chǔ)。

雖然本文在晚高峰時期的交通區(qū)域劃分效果上表現(xiàn)良好，但尚未對其他時段的道路運(yùn)行數(shù)據(jù)進(jìn)行驗(yàn)證，因此在未來的研究中，會對各個時段道路數(shù)據(jù)的區(qū)域劃分效果進(jìn)行分析驗(yàn)證。

參考文獻(xiàn)：

［1］美國運(yùn)輸部聯(lián)邦公路局.交通控制系統(tǒng)手冊［M］.北京：人民交通出版社，1987.（The Federal Highway Administration of the United States Department of Transportation.Traffic control system manual［M］.Beijing：Peoples Communications Publishing House，1987.）

［2］劉端陽，潘策.基于Ncut的城市路網(wǎng)交通子區(qū)劃分方法［J］.浙江工業(yè)大學(xué)學(xué)報，2019，47（4）：436-441.（Liu Duanyang，Pan Ce.Ncutbased traffic subdivision method for urban road networks［J］.Journal of Zhejiang University of Technology，2019，47（4）：436-441.）

［3］Lan Huihui，Wu Xianyu.Research on key technology of signal control subarea partition based on correlation degree analysis［J］.Mathematical Problems in Engineering，2020，2020：article ID 1879503.

［4］Xing Yan，Li Wenqing，Liu Weidong，et al.A dynamic regional partitioning method for active traffic control［J］.Sustainability，2022，14（16）：9802.

［5］Dong Wanli，Wang Yunpeng，Yu Haiyang.An identification model of critical control subregions based on macroscopic fundamental diagram theory［J］.Journal of Intelligent Transportation Systems，2019，23（5）：441-451.

［6］李明東，秦子雁.基于Ncut算法的道路網(wǎng)子區(qū)劃分研究［J］.交通節(jié)能與環(huán)保，2020，16（6）：46-48.（Li Mingdong，Qin Ziyan.Research on road network subzone classification based on Ncut algorithm［J］.Transportation Energy Conservation and Environmental Protection，2020，16（6）：46-48.）

［7］鄭黎黎，楊帆，孫寶鳳，等.基于GN算法的城市路網(wǎng)區(qū)域劃分方法研究［J］.重慶交通大學(xué)學(xué)報：自然科學(xué)版，2020，39（4）：610，22.（Zheng Lili，Yang Fan，Sun Baofeng，et al.Research on urban road network area classification method based on GN algorithm［J］.Journal of Chongqing Jiaotong University：Natural Science Edition，2020，39（4）：610，22.）

［8］王磊，羅杰.融合改進(jìn)關(guān)聯(lián)度與Newman算法的區(qū)域交通劃分研究［J］.計算機(jī)工程與應(yīng)用，2022，58（20）：270-276.（Wang Lei，Luo Jie.A study on regional traffic classification by fusing improved correlation with Newman algorithm［J］.Computer Engineering and Applications，2022，58（20）：270-276.）

［9］韓利釗，錢雪忠，羅靖，等.基于區(qū)域劃分的DBSCAN多密度聚類算法［J］.計算機(jī)應(yīng)用研究，2018，35（6）：16681671，1685.（Han Lizhao，Qian Xuezhong，Luo Jing，et al.Multidensity clustering algorithm DBSCAN based on region division［J］.Application Research of Computers，2018，35（6）：16681671，1685.）

［10］閆學(xué)東，郭浩楠，李永昌，等.基于順風(fēng)車數(shù)據(jù)和聚類方法的都市圈區(qū)域劃分與層級結(jié)構(gòu)研究［J］.交通運(yùn)輸系統(tǒng)工程與信息，2021，21（4）：30-39.（Yan Xuedong，Guo Haonan，Li Yongchang，et al.Research on regional division and hierarchical structure of metropolitan area based on hitchhiking data and clustering method［J］.Transportation System Engineering and Information，2021，21（4）：3039.）

［11］Niu X Z，Zhu J H，Wu C Q，et al.On a clusteringbased mining approach for spatially and temporally integrated traffic subarea division［J］.Engineering Applications of Artificial Intelligence，2020，96：103932.

［12］胡華，高云峰，楊曉光.考慮路網(wǎng)OD路徑的交叉口群動態(tài)劃分方法［J］.計算機(jī)工程與應(yīng)用，2010，46（31）：14，18.（Hu Hua，Gao Yunfeng，Yang Xiaoguang.A dynamic partitioning method for intersection groups considering OD paths in road networks［J］.Computer Engineering and Applications，2010，46（31）：14，18.）

［13］Robertson D I.“TRANSYT” method for area traffic control［J］.Traffic Engineering and Control，1969，11（6）：276-281.

［14］Grace M J，Potts R B.A theory of the diffusion of traffic platoons［J］.Operations Research Society of America，1964，12（2）：255-275.

［15］Rodriguez A，Laio A.Clustering by fast search and find of density peaks［J］.Science，2014，344（6191）：14921496.

［16］殷辰堃，方茹，李拓.基于交通流時間序列相似性的NCut城市路網(wǎng)分區(qū)算法［J］.交通運(yùn)輸工程學(xué)報，2021，21（5）：238-250.（Yin Chenkun，F(xiàn)ang Ru，Li Tuo.NCut urban road network zoning algorithm based on traffic flow time series similarity［J］.Journal of Transportation Engineering，2021，21（5）：238-250.）