歸一化分割算法在路網(wǎng)劃分中的敏感度分析

陶黎明， 盧守峰， 江勇東

(長(zhǎng)沙理工大學(xué) 交通運(yùn)輸工程學(xué)院, 湖南 長(zhǎng)沙 410114)

針對(duì)復(fù)雜的交通網(wǎng)絡(luò)拓?fù)潢P(guān)系和現(xiàn)實(shí)交通荷載分布，路網(wǎng)的子區(qū)劃分為交通管理與控制提供了思路。通過(guò)路網(wǎng)劃分來(lái)提取系統(tǒng)內(nèi)部具有強(qiáng)關(guān)聯(lián)性的子區(qū)，服務(wù)于交通狀態(tài)的把握和子區(qū)信號(hào)的控制，從而提高交通運(yùn)行效率。目前，基于各種理論路網(wǎng)劃分方法的研究取得了一些成果，但缺乏對(duì)于劃分方法本身特性的客觀認(rèn)識(shí)，導(dǎo)致對(duì)其特性了解不全面和應(yīng)用不充分。Walinchus[1]提出交通控制子區(qū)的概念以來(lái)，路網(wǎng)劃分的相關(guān)研究一直備受關(guān)注。其中，對(duì)于各種劃分方法的應(yīng)用研究集中在交通信號(hào)控制子區(qū)[2-3]。在區(qū)域交通狀態(tài)分析方面，Geroliminis[4-5]等人研究了路網(wǎng)平均密度與平均流量相關(guān)性，并提出了能反映區(qū)域交通網(wǎng)絡(luò)狀態(tài)特性的宏觀基本圖(macroscopic fundamental diagram，簡(jiǎn)稱MFD)概念。利用實(shí)測(cè)數(shù)據(jù)創(chuàng)建宏觀交通基本圖已成為研究的熱點(diǎn)。盧守峰[6]等人對(duì)利用線圈檢測(cè)器數(shù)據(jù)和出租車GPS數(shù)據(jù)創(chuàng)建的宏觀交通基本圖進(jìn)行了研究。Geroliminis[7-8]等人通過(guò)對(duì)實(shí)測(cè)數(shù)據(jù)和模擬數(shù)據(jù)創(chuàng)建宏觀交通基本圖進(jìn)行研究，發(fā)現(xiàn)：交通網(wǎng)絡(luò)中車輛密度的空間分布是影響MFD離散度和形狀的關(guān)鍵因素。為了得到更準(zhǔn)確的MFD， Ji[9]等人基于路網(wǎng)劃分的思路，提出利用歸一化分割(Normalized cut，簡(jiǎn)稱為Ncut)方法進(jìn)行路網(wǎng)劃分，將交通網(wǎng)絡(luò)劃分為車輛密度分布均質(zhì)性較高(即密度方差較小)的子區(qū)。

歸一化分割屬于譜聚類算法的一種，最早應(yīng)用于圖像的分割[10]。該方法通過(guò)相似度函數(shù)計(jì)算權(quán)重后建立Laplace矩陣，并通過(guò)求解系統(tǒng)特征函數(shù)進(jìn)行劃分對(duì)象的聚類[11]。在實(shí)際應(yīng)用中，由于不同的相似度函數(shù)具有其自身的特性，聚類結(jié)果往往會(huì)依賴于相似度函數(shù)[12]。歸一化分割算法應(yīng)用于路段密度屬性劃分路網(wǎng)時(shí)，其相似函數(shù)對(duì)路網(wǎng)密度分布的變化不敏感，導(dǎo)致路網(wǎng)在不同密度分布時(shí)的劃分結(jié)果都相同。為創(chuàng)建性能良好的MFD，作者擬對(duì)劃分路網(wǎng)的歸一化分割算法進(jìn)行研究，對(duì)其相似函數(shù)利用懲罰系數(shù)法進(jìn)行敏感度分析，為該算法的應(yīng)用提供參考。

1 歸一化分割算法簡(jiǎn)介

在歸一化分割中，先將交通網(wǎng)絡(luò)作為無(wú)向圖G，路段作為節(jié)點(diǎn)。其中，每個(gè)節(jié)點(diǎn)i具有對(duì)應(yīng)的密度di屬性[9]。建立的鄰接矩陣{a(i,j)} (只有0或1 2個(gè)值)代表的是每對(duì)路段之間的相鄰關(guān)系。當(dāng)a(i,j)=1時(shí)，表示路段i和j相連，反之亦然。為了保證路網(wǎng)的空間連接，將路段之間的有效值定為1，同時(shí)，定義路段i和j之間的權(quán)重相似度函數(shù)w(i,j)，其表達(dá)式為：

(1)

(2)

(3)

其中：Ncut(A,B)的最小化和Nassoc(A,B)的最大化2個(gè)目標(biāo)可以被同時(shí)實(shí)現(xiàn)。兩者遵循的約束為：

Nassoc(A,B)=2-Ncut(A,B)。

(4)

準(zhǔn)確求解Ncut是一個(gè)多項(xiàng)式非確定性的問(wèn)題，但可通過(guò)求解實(shí)值域上的特征值系統(tǒng)，有效逼近離散解。歸一化分割的計(jì)算思想來(lái)自譜方法，其在劃分城市交通信號(hào)控制網(wǎng)絡(luò)小區(qū)中也得到應(yīng)用[3]。歸一化分割的步驟為：

1) 給定一個(gè)從運(yùn)輸網(wǎng)絡(luò)中建立的無(wú)向圖，并對(duì)連接路段的鄰接矩陣設(shè)置權(quán)重w(i,j)，得到矩陣C，作為2個(gè)路段之間相似性的度量。

2) 建立節(jié)點(diǎn)權(quán)重的Laplace矩陣F(設(shè)對(duì)角矩陣D，對(duì)角線權(quán)重為行或列權(quán)重的和F=D-C)。

3) 對(duì)矩陣系統(tǒng)D-0.5FD-0.5求解特征值，選取第二小特征值，并求取對(duì)應(yīng)特征向量。

4) 從小到大對(duì)特征向量進(jìn)行排序，根據(jù)向量是否大于0將路網(wǎng)劃分為2部分。

在歸一化分割過(guò)程中，為了評(píng)估和比較不同劃分后的聚類情況，引入評(píng)價(jià)指標(biāo)[8]：

(5)

式中：K為區(qū)域全部子區(qū)的數(shù)目；NA和NB均為子區(qū)內(nèi)路段的數(shù)量。

此外，評(píng)估簇A內(nèi)的路段聚類情況的計(jì)算公式為：

(6)

NSNK(A,B)=min{NSK(A,M)|M∈

Neighbor(A)}。

(7)

其中：Neighbor(A)為空間上與集群A相鄰的子區(qū)。在該指標(biāo)中，NSK(A,A)表示的是集群內(nèi)的相似度，NSK(A,B)表示的是不同集群之間的相似度。如果2個(gè)集群在空間上不相鄰，即使它們的路段車道密度很接近，也會(huì)被成功分區(qū)，因此，只要測(cè)量該子區(qū)與其相鄰子區(qū)之間的相似度。又由于A可能有多個(gè)相鄰子區(qū)，因此選擇與A最相似的一個(gè)進(jìn)行對(duì)比計(jì)算。整體分區(qū)的評(píng)價(jià)利用全部子區(qū)NSK(A)的平均值A(chǔ)NSK來(lái)評(píng)估。

(8)

式中：C為劃分的子區(qū)集合；K為子區(qū)的數(shù)量。

ANSK越小，表明劃分越理想。NSK評(píng)估度量可以等價(jià)地用集群中的路段車道密度方差和平均密度來(lái)表示，其計(jì)算式為：

NSK(A,B) =var(A)+var(B)+

(uA-uB)2。

(9)

式中：uA為子區(qū)A的路段平均密度；uB為子區(qū)B的路段平均密度。

同時(shí)，可以得到：

(10)

在式(10)中，相鄰不同子區(qū)的平均密度差越大，評(píng)價(jià)的子區(qū)內(nèi)部方差越小，則NSK越小，表明該子區(qū)劃分效果越好。由于一個(gè)具有較小方差和NSK的集群可能伴隨著一個(gè)具有較大方差和NSK的相鄰子區(qū)，因此，整區(qū)劃分的評(píng)價(jià)用NSK的平均值來(lái)評(píng)估。也可以使用集群的總方差來(lái)評(píng)估整區(qū)劃分的質(zhì)量，其計(jì)算式為：

(11)

歸一化分割算法的優(yōu)勢(shì)有：①歸一化分割是基于圖論的分割算法，圖像的線條和色彩與路網(wǎng)的路段荷載具有相同的關(guān)系特征；②該分割方法可以避免劃分出大小迥異的路段集群，同時(shí)，可以產(chǎn)生節(jié)點(diǎn)規(guī)格相近的子區(qū)；③它可以實(shí)現(xiàn)感知性的編組，即利用圖形最主要、最明顯的成分對(duì)全局進(jìn)行分割提?。虎芸杀ＷC劃分的路段集群在空間上緊湊連續(xù)；⑤該分割算法在路網(wǎng)劃分中可以有效實(shí)現(xiàn)。

2 敏感度分析

2.1 懲罰系數(shù)量級(jí)對(duì)劃分結(jié)果的影響

為了研究歸一化分割對(duì)于路網(wǎng)密度變化的敏感性，本研究基于浙江紹興柯橋城區(qū)道路的車牌照數(shù)據(jù)進(jìn)行了路網(wǎng)劃分試驗(yàn)。由CUPRITE模型[13]計(jì)算得到路段密度，其單位為輛/m。該模型在道路上、下游車輛數(shù)據(jù)統(tǒng)計(jì)上已得到深入驗(yàn)證，并被廣泛應(yīng)用。初始路網(wǎng)和一次初始劃分的結(jié)果如圖1所示。

圖1 初始路網(wǎng)和一次劃分結(jié)果Fig. 1 Initial road network and first division result

初始路網(wǎng)由39個(gè)交叉口和62條路段構(gòu)成，區(qū)域面積約7.36 km2。將1 d中6∶10-21∶50的時(shí)段取10 min為間隔，提取了94個(gè)時(shí)間間隔，并基于密度方差最大的第70個(gè)時(shí)段(17∶40-17∶50)路網(wǎng)密度進(jìn)行了一次分割。對(duì)所有時(shí)間段進(jìn)行劃分后，發(fā)現(xiàn)94次劃分結(jié)果完全相同。但1 d中的不同時(shí)段，路網(wǎng)的道路密度方差是有明顯變化的，如圖2所示。

圖2 路網(wǎng)密度方差與時(shí)間的變化Fig. 2 The change of network density with time

對(duì)歸一化分割中的相似度函數(shù)添加了懲罰系數(shù)α，將相鄰路段相似度權(quán)重w(i,j)設(shè)計(jì)為 exp(-α(di-dj)2),并通過(guò)調(diào)整其數(shù)量級(jí)，對(duì)劃分結(jié)果進(jìn)行了研究。最初劃分中的密度單位取輛/m，(di-dj)2的數(shù)量級(jí)為10-4。通過(guò)依次調(diào)整α，將α設(shè)為100～104，當(dāng)α=103，即α(di-dj)2的數(shù)量級(jí)為10-1時(shí)，劃分結(jié)果出現(xiàn)了變化,如圖3所示。

圖3中，橫坐標(biāo)代表94個(gè)時(shí)間段，縱坐標(biāo)為路段編號(hào)，白色和黑色表示對(duì)應(yīng)編號(hào)隸屬于的不同子區(qū)。比較不同α數(shù)量級(jí)下的劃分效果，可以發(fā)現(xiàn)：當(dāng)相似度函數(shù)的量級(jí)過(guò)小時(shí)，其對(duì)路網(wǎng)密度的分布不敏感，劃分結(jié)果固定。同時(shí)，當(dāng)路網(wǎng)劃分結(jié)果出現(xiàn)變化時(shí)，密度方差較大的早、晚高峰時(shí)段子區(qū)的臨界路段波動(dòng)很大，劃分效果對(duì)密度分布變化的敏感度加強(qiáng)。表明：歸一化分割的劃分效果對(duì)權(quán)重指數(shù)的數(shù)量級(jí)存在依賴。為了進(jìn)一步對(duì)比不同α量級(jí)下相似函數(shù)對(duì)密度分布的敏感性，驗(yàn)證其指數(shù)對(duì)數(shù)量級(jí)的依賴，同樣，基于第70個(gè)時(shí)段下的路網(wǎng)密度，進(jìn)行了具體劃分并計(jì)算了相應(yīng)評(píng)價(jià)指標(biāo)。不同α數(shù)量級(jí)下的路網(wǎng)具體劃分如圖4所示。

圖3 不同α數(shù)量級(jí)下的路段子區(qū)分布Fig. 3 The distribution maps of the road section under different orders of magnitude alpha

從圖4中可以看出，不同α數(shù)量級(jí)下的劃分結(jié)果均不同。同時(shí)，計(jì)算得到劃分子區(qū)的評(píng)價(jià)指標(biāo)見表1。

圖4 不同α數(shù)量級(jí)下的路網(wǎng)具體劃分Fig. 4 Specific division diagrams of road network with different orders of magnitude alpha

懲罰系數(shù)車輛密度平均值/(輛·m-1)方差/(輛2·m-2)子區(qū)相似度路段數(shù)/條總方差/(輛2·m-2)相似度平均值100,101,102 (子區(qū)1)0.039 1 3.25×10-40.928 9 330.020 320.936 5 100,101,102 (子區(qū)2)0.032 4 3.31×10-40.944 0 29--103 (子區(qū)1)0.039 2 3.35×10-40.958 2 320.020 290.935 6 103 (子區(qū)2)0.032 5 3.19×10-40.913 0 30--104 (子區(qū)1)0.038 9 3.02×10-40.754 2 480.019 160.793 0 104 (子區(qū)2)0.026 0 3.33×10-40.831 7 14--

從表1中可以看出，當(dāng)劃分結(jié)果出現(xiàn)變化后，隨著α數(shù)量級(jí)的增加，子區(qū)內(nèi)路段的密度、方差、總方差及相似度平均值均降低了。劃分效果的優(yōu)化表明：歸一化分割的相似函數(shù)對(duì)路網(wǎng)中路段密度的分布敏感度提高了，驗(yàn)證了其劃分結(jié)果對(duì)相似度函數(shù)的指數(shù)量級(jí)存在依賴。這對(duì)于歸一化分割算法在不同應(yīng)用中具有實(shí)際參考價(jià)值。

2.2 相似函數(shù)圖像分析

為了分析權(quán)重對(duì)相似函數(shù)圖形的影響，α取100,103,105和107, 分別繪制了函數(shù)exp(-αx2)的圖像，如圖5所示。

從圖5中可以看出，歸一化分割算法的相似度函數(shù)在初始α=100時(shí)，其函數(shù)在變量較小時(shí)斜率絕對(duì)值過(guò)小，對(duì)于變量的變化不敏感，導(dǎo)致其在劃分應(yīng)用中對(duì)于不同密度分布情況結(jié)果相同。但隨著懲罰系數(shù)量級(jí)的增加，函數(shù)圖像逐漸變窄變陡，變量對(duì)應(yīng)的斜率絕對(duì)值變大，對(duì)不同變量的感知力增強(qiáng)，使得不同密度方差下的子區(qū)劃分產(chǎn)生了差異。當(dāng)α=107時(shí)，函數(shù)圖像僅在0附近很小的區(qū)間有值，其他均趨于0。這與實(shí)際試驗(yàn)中利用Matlab求解矩陣系統(tǒng)特征向量時(shí)出現(xiàn)無(wú)效值錯(cuò)誤相吻合。因此，在應(yīng)用歸一化分割算法時(shí)，其劃分結(jié)果對(duì)相似函數(shù)的指數(shù)量級(jí)存在著依賴。量級(jí)過(guò)小，會(huì)導(dǎo)致其對(duì)劃分對(duì)象屬性變化不敏感；量級(jí)過(guò)大，會(huì)帶來(lái)求解困難。經(jīng)試驗(yàn)驗(yàn)證，在MFD創(chuàng)建的路網(wǎng)劃分應(yīng)用中，其相似度函數(shù)的指數(shù)-α(di-dj)2的整體量級(jí)控制在100到101比較合適，即懲罰系數(shù)α取104～105。

圖5 exp(-αx2)函數(shù)圖像Fig. 5 The image of exp(-αx2)function

2.3 宏觀交通基本圖分析

考慮到歸一化分割算法在MFD創(chuàng)建中應(yīng)用的有效性[9]，對(duì)其劃分的第70個(gè)時(shí)段的路網(wǎng)子區(qū)進(jìn)行了宏觀基本圖的分析。路網(wǎng)劃分前、后MFD的對(duì)比如圖6所示。

圖6 α取104時(shí)，劃分前、后MFD的對(duì)比Fig. 6 The MFD contrast of the network before and after the partition

從圖6中可以看出，歸一化分割后各子區(qū)的最大流量是不同的。該結(jié)論為精細(xì)化分析交通路網(wǎng)運(yùn)行狀況和交通管控措施提供了依據(jù)。

3 結(jié)論

由于歸一化分割算法可以將路網(wǎng)劃分為密度分布均質(zhì)性更高的子區(qū)，提高宏觀基本圖的準(zhǔn)確性，但劃分敏感度在相似度函數(shù)的指數(shù)量級(jí)上存在依賴。因此，本研究通過(guò)懲罰系數(shù)法，對(duì)歸一化分割算法進(jìn)行了不同指數(shù)量級(jí)下的敏感度分析，通過(guò)比較劃分后子區(qū)路網(wǎng)的評(píng)價(jià)指標(biāo)，驗(yàn)證了數(shù)量級(jí)會(huì)對(duì)劃分結(jié)果產(chǎn)生重要影響。同時(shí)，對(duì)不同指數(shù)量級(jí)產(chǎn)生敏感度變化影響的原因進(jìn)行了函數(shù)曲線分析，表明了其產(chǎn)生影響的原因。基于歸一化分割算法在實(shí)際路網(wǎng)劃分應(yīng)用中的有效性，以及其相似函數(shù)的敏感度特點(diǎn)，提出：在實(shí)際應(yīng)用中，應(yīng)根據(jù)劃分目標(biāo)和劃分對(duì)象的屬性，合理控制其相似函數(shù)的指數(shù)量級(jí)。