楊 迪，蔡怡然，王 鵬，李巖芳

(長(zhǎng)春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，吉林 長(zhǎng)春 130022)

0 引 言

交通擁堵是目前全世界共同面臨又亟待解決的問題，其態(tài)勢(shì)一般存在區(qū)域性和不確定性。合理高效的交通區(qū)域劃分能夠清晰地展現(xiàn)交通傳播規(guī)律以及區(qū)域道路擁堵情況，對(duì)于交通疏導(dǎo)具有實(shí)際的指導(dǎo)意義。目前學(xué)者們對(duì)于路網(wǎng)動(dòng)態(tài)劃分問題進(jìn)行了廣泛的研究。路網(wǎng)動(dòng)態(tài)劃分方法主要有傳統(tǒng)劃分方法，如基于多特征參數(shù)的劃分方法[1-5]、基于MFD屬性劃分方法[6]和智能劃分方法，如基于遺傳算法的劃分方法[7]、基于譜聚類算法的劃分方法[8-12]。由于譜聚類算法[13]操作簡(jiǎn)單，具有較強(qiáng)的普適性，被廣泛應(yīng)用于路網(wǎng)劃分中，但算法本身相似圖的計(jì)算會(huì)忽視路網(wǎng)節(jié)點(diǎn)之間復(fù)雜的關(guān)聯(lián)性，而且易產(chǎn)生局部最優(yōu)解等問題。針對(duì)這些問題有不少改進(jìn)方案被提出，如Yang等[8]提出了一種異構(gòu)時(shí)空交通三階段模式的路網(wǎng)劃分方法，將路網(wǎng)劃分為相似性較高的區(qū)域子網(wǎng)。趙菲等[11]提出了基于邊聚類系數(shù)的譜聚類子區(qū)劃分方法，改善圖譜劃分的局限性。Tarique等[12]提出了基于密度聚類和譜聚類的路網(wǎng)劃分方法，提高路網(wǎng)劃分聚類精度。

雖然上述改進(jìn)提升了譜聚類的部分性能，但是大部分方法所承載的路網(wǎng)結(jié)構(gòu)信息較少，并且沒有結(jié)合實(shí)際交通路網(wǎng)環(huán)境。本文結(jié)合實(shí)際路網(wǎng)交通環(huán)境提出了一種基于改進(jìn)譜聚類算法的交通區(qū)域劃分方法，其利用馬爾可夫鏈完善譜聚類算法的相似圖，通過轉(zhuǎn)移概率重新構(gòu)造路網(wǎng)節(jié)點(diǎn)之間的相似圖，確保能夠反映出完整的路網(wǎng)信息，同時(shí)針對(duì)聚類初始中心節(jié)點(diǎn)敏感的問題，通過遺傳算法，提高譜聚類的全局搜索能力，保證路網(wǎng)分區(qū)的準(zhǔn)確度。

1 基于譜聚類算法的區(qū)域劃分算法

譜聚類是基于圖論的聚類算法，其原理是將原本的聚類問題轉(zhuǎn)化為拓?fù)鋱D的劃分問題。利用節(jié)點(diǎn)之間相似度設(shè)計(jì)相似矩陣，計(jì)算出該矩陣的前k特征向量,從而將不同數(shù)據(jù)點(diǎn)進(jìn)行分類。

譜聚類算法應(yīng)用于交通路網(wǎng)步驟如下：

E={(vi,vj)|(vi,vj)∈V×V,vivj}

(1)

步驟2 構(gòu)造相似矩陣W。使用一個(gè)非負(fù)的相似矩陣W表示整個(gè)無向圖，其元素wij表示無向圖中的兩個(gè)節(jié)點(diǎn)vi和vj之間的權(quán)重，并且wij=wji。然后得出相似矩陣W，相似矩陣W的計(jì)算表達(dá)式為式(2)

(2)

步驟3 計(jì)算拉普拉斯矩陣L=D-W。D為度矩陣，其計(jì)算表達(dá)式為式(3)

(3)

式中：元素wij表示無向圖中的兩個(gè)節(jié)點(diǎn)vi和vj之間的權(quán)重。

步驟4 構(gòu)建標(biāo)準(zhǔn)化后拉式矩陣D-1/2LD-1/2。

步驟5 求標(biāo)準(zhǔn)化后拉式矩陣的前k個(gè)最大特征值以及相應(yīng)的特征向量(ξ1ξ2…ξk)，得到特征向量矩陣X。

步驟6 計(jì)算矩陣X的行向量，得到矩陣Y，其計(jì)算表達(dá)式為式(4)

(4)

式中：Xij表示第i行第j列元素。

步驟7 將Y的每一行作為Rc空間的一個(gè)樣本，使用k-means聚類，得到k個(gè)聚類。

步驟8 如果Y的第i行在j類中，那么當(dāng)且僅當(dāng)Y的第i行被歸為聚類j中。

2 改進(jìn)譜聚類的區(qū)域劃分方法

2.1 基于加權(quán)相似圖的路網(wǎng)提取方法

路網(wǎng)中相鄰路段間具有更緊密更復(fù)雜的結(jié)構(gòu)關(guān)系，傳統(tǒng)譜聚類的相似圖是基于歐式距離得出，其計(jì)算簡(jiǎn)單，但是容易忽略隱性的路網(wǎng)結(jié)構(gòu)信息。路網(wǎng)中節(jié)點(diǎn)之間的關(guān)系會(huì)隨空間距離的增加而減弱，在交通流量的傳播作用下，路網(wǎng)間交通流量的關(guān)聯(lián)度也會(huì)隨路網(wǎng)空間距離的增加而不斷地減小。通過路網(wǎng)間的轉(zhuǎn)移概率反映出交通流量隨著距離變化的趨勢(shì)，從而進(jìn)一步模擬出完整的路網(wǎng)關(guān)系相似圖。而以往的譜聚類相似圖僅考慮了相鄰路段間的關(guān)系，忽略了在傳播作用下，路網(wǎng)間交通流量的轉(zhuǎn)移關(guān)系，應(yīng)用于路網(wǎng)中難以有效反映路網(wǎng)的關(guān)聯(lián)度，使得聚類效果不理想，本節(jié)通過馬爾可夫鏈的轉(zhuǎn)移概率構(gòu)建譜聚類的相似圖。

2.1.1 轉(zhuǎn)移概率和概率矩陣

馬爾科夫鏈?zhǔn)且粋€(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)的隨機(jī)轉(zhuǎn)換過程，空間狀態(tài)之間變換的概率叫作轉(zhuǎn)移概率，并且未來狀態(tài)只依賴于當(dāng)前狀態(tài)。交通路網(wǎng)隨時(shí)間空間變化存在復(fù)雜的狀態(tài)轉(zhuǎn)移關(guān)系，其中交通流量每一時(shí)刻所在路網(wǎng)節(jié)點(diǎn)為狀態(tài)空間，而下一時(shí)刻所在路網(wǎng)節(jié)點(diǎn)狀態(tài)僅與車流量此時(shí)所在節(jié)點(diǎn)狀態(tài)有關(guān)。通過節(jié)點(diǎn)之間馬爾可夫的轉(zhuǎn)移概率來模擬復(fù)雜的路網(wǎng)關(guān)系，計(jì)算譜聚類相似度，并且重新構(gòu)造相似圖。

給定路網(wǎng)G，令t時(shí)刻路網(wǎng)流量狀態(tài)為隨機(jī)變量，利用概率矩陣表達(dá)路網(wǎng)節(jié)點(diǎn)之間的狀態(tài)轉(zhuǎn)移概率，根據(jù)馬爾科夫鏈特征并且滿足以下性質(zhì)，其計(jì)算表達(dá)式為式(5)

P{X(t+1)=at+1|X(t)=at,…,X(1)=a1}=

P{X(t+1)=at+1|X(t)=at}

(5)

式中：X(t)為t時(shí)刻的馬爾科夫過程，A={a1,a2,…,at} 為路網(wǎng)狀態(tài)空間。

通過交通流量特征，計(jì)算t時(shí)刻節(jié)點(diǎn)狀態(tài)到下一時(shí)刻節(jié)點(diǎn)狀態(tài)的轉(zhuǎn)移概率Pij，其計(jì)算表達(dá)式為式(6)

(6)

由此構(gòu)建構(gòu)成路網(wǎng)的轉(zhuǎn)移概率矩陣P，其計(jì)算表達(dá)式為式(7)

(7)

路網(wǎng)中狀態(tài)之間的狀態(tài)轉(zhuǎn)移過程如圖1所示。

圖1 路網(wǎng)狀態(tài)轉(zhuǎn)移過程

其中，節(jié)點(diǎn)表達(dá)路網(wǎng)狀態(tài)空間，pij為路網(wǎng)的轉(zhuǎn)移概率。例如p21為路網(wǎng)流量狀態(tài)2轉(zhuǎn)移到狀態(tài)1的概率。同時(shí)，在路網(wǎng)空間狀態(tài)中處于狀態(tài)2的路網(wǎng)流量下一刻選擇的空間狀態(tài)的概率都取決于路網(wǎng)流量當(dāng)前所處的狀態(tài)。

轉(zhuǎn)移概率矩陣P中的狀態(tài)轉(zhuǎn)移僅依賴于前一個(gè)狀態(tài)，其能夠直觀地描述節(jié)點(diǎn)與相鄰節(jié)點(diǎn)之間的路網(wǎng)關(guān)系，但是無法描述與多個(gè)非鄰近路網(wǎng)區(qū)域節(jié)點(diǎn)之間關(guān)系。通過多次狀態(tài)轉(zhuǎn)移得到高階轉(zhuǎn)移概率，可以拓展更多非鄰近節(jié)點(diǎn)，所以利用高階轉(zhuǎn)移概率來表征交通區(qū)域各個(gè)節(jié)點(diǎn)之間存在的復(fù)雜路網(wǎng)關(guān)系。

給定路網(wǎng)G，路網(wǎng)空間狀態(tài)個(gè)數(shù)為g，通過計(jì)算路網(wǎng)交通流量的轉(zhuǎn)移概率矩陣，其所得到的特征向量作為路網(wǎng)交通流量權(quán)重即馬爾科夫的狀態(tài)向量為R，R={r1,r2,…,rg}。路網(wǎng)節(jié)點(diǎn)i狀態(tài)到達(dá)節(jié)點(diǎn)j狀態(tài)期間經(jīng)過m次轉(zhuǎn)移，則狀態(tài)的轉(zhuǎn)變僅依賴于前m個(gè)狀態(tài)，得到m階轉(zhuǎn)移概率矩陣Pm，其計(jì)算表達(dá)式為式(8)

Pm=rmpm

(8)

式中：rm為m階轉(zhuǎn)移概率的權(quán)值,pm為m階矩陣。

進(jìn)而構(gòu)建馬爾可夫模型，其計(jì)算表達(dá)式為式(9)

X(t+m)=PmX(t)

(9)

式中：馬爾可夫鏈模型的初值為X(1)。

2.1.2 相似圖的計(jì)算

給定路網(wǎng)G，m階轉(zhuǎn)移概率矩陣為Pm，通過概率矩陣Pm構(gòu)建相似矩陣W，路網(wǎng)中節(jié)點(diǎn)i和j之間相似度wij，其計(jì)算表達(dá)式為式(10)

(10)

式中：pmij是節(jié)點(diǎn)i處狀態(tài)轉(zhuǎn)移到節(jié)點(diǎn)j的概率。

通過相似矩陣W所構(gòu)建的拉普拉斯矩陣滿足以下性質(zhì)：

(1)L=D-W，其中D為度矩陣，所有的特征值都是實(shí)數(shù)。

(2)對(duì)于任意向量f，都滿足計(jì)算表達(dá)式(11)

fTLf=fTDf-fTWf=

(11)

表明W能夠構(gòu)造Laplace矩陣，進(jìn)而得出譜聚類算法的相似圖。基于以上推導(dǎo)，基于轉(zhuǎn)移概率矩陣實(shí)現(xiàn)了譜聚類相似圖構(gòu)造。

2.2 基于遺傳算法的譜聚類優(yōu)化方法

傳統(tǒng)譜聚類中k-means算法對(duì)初始中心十分敏感，聚類中心的選擇直接影響聚類結(jié)果的準(zhǔn)確性，而不恰當(dāng)?shù)木垲愔行耐鶗?huì)造成路網(wǎng)劃分區(qū)域間差異大，相鄰子區(qū)間的劃分作用不明顯，導(dǎo)致路網(wǎng)劃分效果不理想。本節(jié)為了提高路網(wǎng)的全局尋優(yōu)能力，利用GA聚類算法對(duì)特征向量進(jìn)行優(yōu)化，其應(yīng)用于譜聚類最后一步聚。

2.2.1 個(gè)體編碼與種群初始化

本文采用浮點(diǎn)數(shù)編碼的方式生成交通路網(wǎng)的初始種群，給定的路網(wǎng)聚類數(shù)量k，將通過拉普拉斯矩陣計(jì)算得出的特征向量設(shè)為初始樣本集Q，路網(wǎng)兩個(gè)節(jié)點(diǎn)之間的流量相似度設(shè)為基因，將路網(wǎng)隨機(jī)劃分成各個(gè)子區(qū)域。

2.2.2 適應(yīng)度函數(shù)

遺傳算法的收斂速度以及能否找到最優(yōu)解與遺傳算法適應(yīng)函數(shù)的選取有關(guān)。本文構(gòu)造適應(yīng)度函數(shù)f通過路網(wǎng)中每個(gè)節(jié)點(diǎn)的特征來判斷路網(wǎng)各個(gè)節(jié)點(diǎn)的適應(yīng)度，其計(jì)算表達(dá)式為式(12)

(12)

式中：b為常數(shù)，E為樣本集的誤差平方和。

2.2.3 遺傳聚類操作

本文選取輪盤賭選擇方法，路網(wǎng)中每個(gè)節(jié)點(diǎn)能否進(jìn)入下一代由其相對(duì)適應(yīng)度所決定。然后進(jìn)行交叉，路網(wǎng)中兩個(gè)節(jié)點(diǎn)隨機(jī)地交換基因，交叉后若發(fā)現(xiàn)子代具有相同點(diǎn)則歸并相同點(diǎn)，若沒有，則確定父輩是否在路網(wǎng)中有對(duì)應(yīng)基因的權(quán)值不為零，即有直接的路網(wǎng)關(guān)系。若有，則選取子代中最優(yōu)的基因?qū)M(jìn)行交叉操作。交叉操作可以完善算法在路網(wǎng)中的全局搜索能力，變異操作則保障了其局部搜索能力，防止過早收斂。

經(jīng)過以上操作后，路網(wǎng)每次都需要重新計(jì)算各特征向量與各路網(wǎng)節(jié)點(diǎn)之間復(fù)雜的權(quán)重的關(guān)系，重新劃分種群，經(jīng)過迭代后適應(yīng)度最大的路網(wǎng)節(jié)點(diǎn)為最終結(jié)果。最后，按照與最終結(jié)果空間關(guān)系最近原則重新聚類劃分樣本集，得到路網(wǎng)聚類劃分結(jié)果。

2.3 算法總體框架

針對(duì)譜聚類中基于歐式距離計(jì)算的相似圖無法表征路網(wǎng)隱含信息的問題以及聚類初始化中心敏感的問題，本文提出的改進(jìn)譜聚類的區(qū)域劃分方法(ISC)。首先，根據(jù)實(shí)際路網(wǎng)構(gòu)建路網(wǎng)拓?fù)鋱DG=(V,E)。其次，通過構(gòu)建馬爾可夫鏈轉(zhuǎn)移概率矩陣方法，利用路網(wǎng)節(jié)點(diǎn)之間的關(guān)聯(lián)權(quán)重來表征出完整的路網(wǎng)信息，重新構(gòu)造相似矩陣W。然后，計(jì)算拉普拉斯矩陣，得出拉普拉斯矩陣L前k個(gè)最大特征值以及相應(yīng)的特征向量。最后構(gòu)造空間特征樣本集，通過遺傳優(yōu)化選取全局最優(yōu)的聚類中心進(jìn)行聚類，得出聚類結(jié)果進(jìn)行路網(wǎng)劃分。算法步驟如圖2所示。

圖2 算法總體步驟

算法流程：

輸入：網(wǎng)絡(luò)G=(V,E)

輸出：路網(wǎng)劃分結(jié)果

(1)計(jì)算轉(zhuǎn)移概率矩陣Pm。

(2)構(gòu)建相似矩陣W。

(3)構(gòu)造拉普拉斯矩陣L，L=D-W。

(4)將L特征分解，計(jì)算最小的特征值以及對(duì)應(yīng)特征向量。

(5)將對(duì)應(yīng)節(jié)點(diǎn)映射至k維空間，作為特征樣本集。

(6)將樣本集進(jìn)行編碼并生成初始種群。

(7)計(jì)算初始種群的適應(yīng)度函數(shù)并設(shè)置迭代次數(shù)。

(8)結(jié)合傳統(tǒng)遺傳算法對(duì)第i代的種群進(jìn)行遺傳操作得到新一代的種群。

(9)判定迭代次數(shù)是否為迭代次數(shù)最大值，如果是，則i=i+1，回到(8)，否則結(jié)束迭代過程，將種群中適應(yīng)度函數(shù)最大的個(gè)體作為算法的最后結(jié)果。

(10)根據(jù)最后結(jié)果進(jìn)行劃分路網(wǎng)。

3 實(shí)驗(yàn)分析

以四川省成都市市中心作為研究對(duì)象，研究區(qū)域從西城大街東到東城根大街，北起人民中路至人民東路，共計(jì)23個(gè)路段交叉點(diǎn)，32條路段，根據(jù)實(shí)際道路路網(wǎng)和道路GPS數(shù)據(jù)可以得到路網(wǎng)的拓?fù)浣Y(jié)構(gòu)圖G=(V,E)，拓?fù)鋱D如圖3所示。

圖3 研究區(qū)域范圍拓?fù)?/p>

選取2014年8月3日成都1.4萬輛出租車GPS軌跡數(shù)據(jù)，利用ArcGIS通過地理坐標(biāo)將GPS軌跡數(shù)據(jù)與實(shí)際道路路網(wǎng)匹配。不同時(shí)段交通流量密度變化如圖4～圖6所示：早上8:00至8:15和晚上18:00至18:15處于早高峰時(shí)段和晚高峰時(shí)段，各路段車流量較大，交通流量比較密集，中午12:00至12:15處于平峰時(shí)期流量較高峰時(shí)相對(duì)減少。

圖4 早上8:00-8:15時(shí)段出租車GPS數(shù)據(jù)分布

圖5 中午12:00-12:15時(shí)段出租車GPS數(shù)據(jù)分布

圖6 晚上18:00-18:15時(shí)段出租車GPS數(shù)據(jù)分布

3.1 分區(qū)評(píng)價(jià)指標(biāo)

路網(wǎng)子區(qū)域劃分結(jié)果應(yīng)該滿足區(qū)域內(nèi)部的同質(zhì)性和相鄰子區(qū)間的差異性，因此利用歸一化總體方差方法(TVn)來評(píng)估本文算法的區(qū)域內(nèi)部的同質(zhì)性，NCut Silhouette(NSk)來表征本文算法的相鄰子區(qū)間的差異性，從而判斷其路網(wǎng)劃分結(jié)果的合理性和科學(xué)性。

歸一化總體方差(TVn)為各子區(qū)域內(nèi)部速度方差的和與整個(gè)路網(wǎng)速度方差的比值。對(duì)于k個(gè)子區(qū)域的分區(qū)結(jié)果，歸一化總體方差計(jì)算表達(dá)式為式(13)

(13)

式中：R為路網(wǎng)的道路集合，NRi為子區(qū)Ri內(nèi)的道路數(shù)目，N為路網(wǎng)道路總數(shù)。Vart(Ri)為Ri在t時(shí)速度的方差，t為時(shí)間序列長(zhǎng)度。TVn主要評(píng)判路網(wǎng)劃分后各個(gè)子區(qū)內(nèi)部路段的相似性。當(dāng)劃分子區(qū)越多，子區(qū)內(nèi)部路段越少，路段相似度越高，則該評(píng)價(jià)指標(biāo)越小。

NCut Silhouette(NSk)[14]評(píng)估不同子區(qū)的路段間在各個(gè)時(shí)刻t的速度差平方的平均值。對(duì)于整體路網(wǎng)劃分結(jié)果的總體評(píng)價(jià)計(jì)算表達(dá)式為式(14)

(14)

3.2 路網(wǎng)子區(qū)劃分

本文從實(shí)際應(yīng)用方面考慮，路網(wǎng)子區(qū)的劃分?jǐn)?shù)量過多不利于交通管控，使得管理計(jì)算成本過高，結(jié)合所研究的路網(wǎng)分布，為獲取較好的分區(qū)效果，將所研究的路網(wǎng)劃分為6個(gè)子區(qū)。實(shí)際交通路網(wǎng)中早高峰時(shí)期交通流量變化大，流量密度較集中，能夠顯現(xiàn)出更多交通流量特征，故選取2014年8月3日早上8:00-8:15時(shí)早高峰的實(shí)際路網(wǎng)交通流數(shù)據(jù)作為研究對(duì)象，通過將具有相似特征的流量進(jìn)行聚類實(shí)現(xiàn)路網(wǎng)劃分。根據(jù)參考文獻(xiàn)[15]的參數(shù)設(shè)置并結(jié)合多次實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)所需相關(guān)參數(shù)設(shè)定見表1。

表1 實(shí)驗(yàn)所需相關(guān)參數(shù)設(shè)定

將本文算法(ISC)與傳統(tǒng)譜聚類算法(SC)、基于馬爾可夫的譜聚類算法(MKSC)、基于遺傳算法的譜聚類算法(GASC)的劃分結(jié)果在相同的實(shí)驗(yàn)環(huán)境下進(jìn)行有效性對(duì)比，實(shí)驗(yàn)參數(shù)設(shè)置見表2，子區(qū)劃分評(píng)價(jià)結(jié)果如表2、圖7所示。

表2 路網(wǎng)劃分評(píng)價(jià)結(jié)果

圖7 路網(wǎng)劃分評(píng)價(jià)指標(biāo)

從表2可以看出MKSC算法與傳統(tǒng)SC算法相比TVn評(píng)價(jià)指標(biāo)降低了9.16%，NSk指標(biāo)降低了2.8%，表明了MKSC算法相比于歐氏距離構(gòu)造相似矩陣的SC算法容易忽視路網(wǎng)之間復(fù)雜的關(guān)聯(lián)關(guān)系，考慮了交通路網(wǎng)之間的流量傳播規(guī)律，通過轉(zhuǎn)移概率模擬路網(wǎng)節(jié)點(diǎn)間流量變化以構(gòu)造反映交通區(qū)域結(jié)構(gòu)的譜聚類相似圖，從而減少了由于空間距離的增加對(duì)路網(wǎng)節(jié)點(diǎn)之間交通關(guān)系的影響，增強(qiáng)了相似圖的健壯性，提高了聚類效果。GASC算法與傳統(tǒng)SC算法相比TVn評(píng)價(jià)指標(biāo)降低了8.42%，NSk指標(biāo)降低了11.58%，表明了GASC算法通過對(duì)特征向量選取過程進(jìn)行優(yōu)化，結(jié)合遺傳進(jìn)化思想對(duì)全局聚類中心尋優(yōu)完成聚類，能夠克服傳統(tǒng)譜聚類對(duì)初始值選取較敏感的問題，提高了路網(wǎng)全局搜索能力，提升了聚類精度。本文所提出的ISC算法在兩個(gè)指標(biāo)上取得了最小值，其子區(qū)劃分效果優(yōu)于SC、MKSC、GASC這3個(gè)算法，在TVn指標(biāo)上分別降低了10.27%、1.23%、2.03%，在NSk指標(biāo)上分別降低了13.23%、10.73%、1.87%，表明了本文所提出的ISC算法具備高內(nèi)聚低耦合的特性。基準(zhǔn)算法SC、GASC算法忽略了在傳播作用下路網(wǎng)間交通流量的轉(zhuǎn)移關(guān)系，通過歐式距離得出的相似矩陣難以有效表征路網(wǎng)信息。SC、MKSC算法對(duì)于聚類初始中心選擇的較為敏感，容易產(chǎn)生局部最優(yōu)解，不利于算法運(yùn)行。ISC算法相較于其它算法，同時(shí)考慮了歐氏距離的不合理性和聚類中心的敏感性，采用馬爾科夫的轉(zhuǎn)移概率重構(gòu)相似圖，同時(shí)通過遺傳算法優(yōu)化聚類中心，使交通子區(qū)更符合實(shí)際路網(wǎng)情況，提高模型整體聚類效果。由圖7可以看出本文算法與其它算法相比TVn評(píng)價(jià)指標(biāo)和NSk評(píng)價(jià)指標(biāo)相對(duì)較低，表明了本文算法既使得各個(gè)子區(qū)內(nèi)部具有較高的相似性同時(shí)又能保證路網(wǎng)子區(qū)之間的差異性，在路網(wǎng)劃分中比較有優(yōu)勢(shì)，更加符合實(shí)際交通特性，驗(yàn)證了本文算法的有效性。

本文所提出的算法(ISC)與傳統(tǒng)譜聚類算法(SC)、基于馬爾可夫的譜聚類算法(MKSC)、基于遺傳算法的譜聚類算法(GASC)對(duì)應(yīng)路網(wǎng)劃分結(jié)果如圖8(a)～圖8(d)所示。

圖8 路網(wǎng)劃分結(jié)果

從路網(wǎng)劃分結(jié)果可以看出，如圖8(a)所示，傳統(tǒng)譜聚類算法在路網(wǎng)劃分時(shí)在空間上雖然各個(gè)子區(qū)域相連但聚類精度較低，粗略地將路網(wǎng)劃分成多個(gè)獨(dú)立子區(qū)。如圖8(b)所示，MKSC算法考慮了復(fù)雜的路網(wǎng)結(jié)構(gòu)特征，在傳統(tǒng)的譜聚類路劃分方法的基礎(chǔ)上利用路網(wǎng)子區(qū)之間復(fù)雜的關(guān)聯(lián)關(guān)系進(jìn)行路網(wǎng)子區(qū)域之間的劃分，形成了多個(gè)空間分布上更加緊密的路網(wǎng)子區(qū)。如圖8(c)所示，GASC算法在傳統(tǒng)譜聚類算法基礎(chǔ)上結(jié)合遺傳算法，以一個(gè)較大概率尋找全局最優(yōu)解進(jìn)行路網(wǎng)劃分，生成了子區(qū)域之間具有較大差異性的路網(wǎng)。如圖8(d)所示，本文所提出的算法既考慮了路網(wǎng)復(fù)雜的關(guān)聯(lián)特性又兼顧了聚類中心的優(yōu)化，將路網(wǎng)劃分成多個(gè)內(nèi)部緊密而子區(qū)間相似性較低的路網(wǎng)子區(qū)域，表明本文所提出的算法能夠有效地對(duì)城市路網(wǎng)進(jìn)行劃分。

4 結(jié)束語(yǔ)

本文提出基于改進(jìn)譜聚類算法的交通區(qū)域劃分方法，從路網(wǎng)結(jié)構(gòu)信息與聚類中心兩個(gè)角度對(duì)傳統(tǒng)譜聚類算法進(jìn)行改進(jìn)。通過馬爾可夫鏈對(duì)相似圖重構(gòu)，考慮了復(fù)雜的路網(wǎng)隱含信息，然后結(jié)合遺傳算法，提高全局的尋優(yōu)能力，并用實(shí)際交通數(shù)據(jù)進(jìn)行聚類分析。實(shí)驗(yàn)結(jié)果表明，ISC算法考慮了復(fù)雜的路網(wǎng)結(jié)構(gòu)信息，既有效保證了路網(wǎng)子區(qū)內(nèi)部的同質(zhì)性又滿足了子區(qū)之間的差異性要求，聚類效果好于對(duì)比算法。文中在特征研究時(shí)只考慮了交通流量特征，未來將進(jìn)一步增加特征因素，例如城市路網(wǎng)興趣點(diǎn)、人群流量分布等。