基于改進譜聚類算法的交通區域劃分方法

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

(長春理工大學 計算機科學技術學院，吉林 長春 130022)

0 引 言

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

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

1 基于譜聚類算法的區域劃分算法

譜聚類是基于圖論的聚類算法，其原理是將原本的聚類問題轉化為拓撲圖的劃分問題。利用節點之間相似度設計相似矩陣，計算出該矩陣的前k特征向量,從而將不同數據點進行分類。

譜聚類算法應用于交通路網步驟如下：

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

(1)

步驟2 構造相似矩陣W。使用一個非負的相似矩陣W表示整個無向圖，其元素wij表示無向圖中的兩個節點vi和vj之間的權重，并且wij=wji。然后得出相似矩陣W，相似矩陣W的計算表達式為式(2)

(2)

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

(3)

式中：元素wij表示無向圖中的兩個節點vi和vj之間的權重。

步驟4 構建標準化后拉式矩陣D-1/2LD-1/2。

步驟5 求標準化后拉式矩陣的前k個最大特征值以及相應的特征向量(ξ1ξ2…ξk)，得到特征向量矩陣X。

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

(4)

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

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

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

2 改進譜聚類的區域劃分方法

2.1 基于加權相似圖的路網提取方法

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

2.1.1 轉移概率和概率矩陣

馬爾科夫鏈是一個狀態轉移到另一個狀態的隨機轉換過程，空間狀態之間變換的概率叫作轉移概率，并且未來狀態只依賴于當前狀態。交通路網隨時間空間變化存在復雜的狀態轉移關系，其中交通流量每一時刻所在路網節點為狀態空間，而下一時刻所在路網節點狀態僅與車流量此時所在節點狀態有關。通過節點之間馬爾可夫的轉移概率來模擬復雜的路網關系，計算譜聚類相似度，并且重新構造相似圖。

給定路網G，令t時刻路網流量狀態為隨機變量，利用概率矩陣表達路網節點之間的狀態轉移概率，根據馬爾科夫鏈特征并且滿足以下性質，其計算表達式為式(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時刻的馬爾科夫過程，A={a1,a2,…,at} 為路網狀態空間。

通過交通流量特征，計算t時刻節點狀態到下一時刻節點狀態的轉移概率Pij，其計算表達式為式(6)

(6)

由此構建構成路網的轉移概率矩陣P，其計算表達式為式(7)

(7)

路網中狀態之間的狀態轉移過程如圖1所示。

圖1 路網狀態轉移過程

其中，節點表達路網狀態空間，pij為路網的轉移概率。例如p21為路網流量狀態2轉移到狀態1的概率。同時，在路網空間狀態中處于狀態2的路網流量下一刻選擇的空間狀態的概率都取決于路網流量當前所處的狀態。

轉移概率矩陣P中的狀態轉移僅依賴于前一個狀態，其能夠直觀地描述節點與相鄰節點之間的路網關系，但是無法描述與多個非鄰近路網區域節點之間關系。通過多次狀態轉移得到高階轉移概率，可以拓展更多非鄰近節點，所以利用高階轉移概率來表征交通區域各個節點之間存在的復雜路網關系。

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

Pm=rmpm

(8)

式中：rm為m階轉移概率的權值,pm為m階矩陣。

進而構建馬爾可夫模型，其計算表達式為式(9)

X(t+m)=PmX(t)

(9)

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

2.1.2 相似圖的計算

給定路網G，m階轉移概率矩陣為Pm，通過概率矩陣Pm構建相似矩陣W，路網中節點i和j之間相似度wij，其計算表達式為式(10)

(10)

式中：pmij是節點i處狀態轉移到節點j的概率。

通過相似矩陣W所構建的拉普拉斯矩陣滿足以下性質：

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

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

fTLf=fTDf-fTWf=

(11)

表明W能夠構造Laplace矩陣，進而得出譜聚類算法的相似圖。基于以上推導，基于轉移概率矩陣實現了譜聚類相似圖構造。

2.2 基于遺傳算法的譜聚類優化方法

傳統譜聚類中k-means算法對初始中心十分敏感，聚類中心的選擇直接影響聚類結果的準確性，而不恰當的聚類中心往往會造成路網劃分區域間差異大，相鄰子區間的劃分作用不明顯，導致路網劃分效果不理想。本節為了提高路網的全局尋優能力，利用GA聚類算法對特征向量進行優化，其應用于譜聚類最后一步聚。

2.2.1 個體編碼與種群初始化

本文采用浮點數編碼的方式生成交通路網的初始種群，給定的路網聚類數量k，將通過拉普拉斯矩陣計算得出的特征向量設為初始樣本集Q，路網兩個節點之間的流量相似度設為基因，將路網隨機劃分成各個子區域。

2.2.2 適應度函數

遺傳算法的收斂速度以及能否找到最優解與遺傳算法適應函數的選取有關。本文構造適應度函數f通過路網中每個節點的特征來判斷路網各個節點的適應度，其計算表達式為式(12)

(12)

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

2.2.3 遺傳聚類操作

本文選取輪盤賭選擇方法，路網中每個節點能否進入下一代由其相對適應度所決定。然后進行交叉，路網中兩個節點隨機地交換基因，交叉后若發現子代具有相同點則歸并相同點，若沒有，則確定父輩是否在路網中有對應基因的權值不為零，即有直接的路網關系。若有，則選取子代中最優的基因對進行交叉操作。交叉操作可以完善算法在路網中的全局搜索能力，變異操作則保障了其局部搜索能力，防止過早收斂。

經過以上操作后，路網每次都需要重新計算各特征向量與各路網節點之間復雜的權重的關系，重新劃分種群，經過迭代后適應度最大的路網節點為最終結果。最后，按照與最終結果空間關系最近原則重新聚類劃分樣本集，得到路網聚類劃分結果。

2.3 算法總體框架

針對譜聚類中基于歐式距離計算的相似圖無法表征路網隱含信息的問題以及聚類初始化中心敏感的問題，本文提出的改進譜聚類的區域劃分方法(ISC)。首先，根據實際路網構建路網拓撲圖G=(V,E)。其次，通過構建馬爾可夫鏈轉移概率矩陣方法，利用路網節點之間的關聯權重來表征出完整的路網信息，重新構造相似矩陣W。然后，計算拉普拉斯矩陣，得出拉普拉斯矩陣L前k個最大特征值以及相應的特征向量。最后構造空間特征樣本集，通過遺傳優化選取全局最優的聚類中心進行聚類，得出聚類結果進行路網劃分。算法步驟如圖2所示。

圖2 算法總體步驟

算法流程：

輸入：網絡G=(V,E)

輸出：路網劃分結果

(1)計算轉移概率矩陣Pm。

(2)構建相似矩陣W。

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

(4)將L特征分解，計算最小的特征值以及對應特征向量。

(5)將對應節點映射至k維空間，作為特征樣本集。

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

(7)計算初始種群的適應度函數并設置迭代次數。

(8)結合傳統遺傳算法對第i代的種群進行遺傳操作得到新一代的種群。

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

(10)根據最后結果進行劃分路網。

3 實驗分析

以四川省成都市市中心作為研究對象，研究區域從西城大街東到東城根大街，北起人民中路至人民東路，共計23個路段交叉點，32條路段，根據實際道路路網和道路GPS數據可以得到路網的拓撲結構圖G=(V,E)，拓撲圖如圖3所示。

圖3 研究區域范圍拓撲

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

圖4 早上8:00-8:15時段出租車GPS數據分布

圖5 中午12:00-12:15時段出租車GPS數據分布

圖6 晚上18:00-18:15時段出租車GPS數據分布

3.1 分區評價指標

路網子區域劃分結果應該滿足區域內部的同質性和相鄰子區間的差異性，因此利用歸一化總體方差方法(TVn)來評估本文算法的區域內部的同質性，NCut Silhouette(NSk)來表征本文算法的相鄰子區間的差異性，從而判斷其路網劃分結果的合理性和科學性。

歸一化總體方差(TVn)為各子區域內部速度方差的和與整個路網速度方差的比值。對于k個子區域的分區結果，歸一化總體方差計算表達式為式(13)

(13)

式中：R為路網的道路集合，NRi為子區Ri內的道路數目，N為路網道路總數。Vart(Ri)為Ri在t時速度的方差，t為時間序列長度。TVn主要評判路網劃分后各個子區內部路段的相似性。當劃分子區越多，子區內部路段越少，路段相似度越高，則該評價指標越小。

NCut Silhouette(NSk)[14]評估不同子區的路段間在各個時刻t的速度差平方的平均值。對于整體路網劃分結果的總體評價計算表達式為式(14)

(14)

3.2 路網子區劃分

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

表1 實驗所需相關參數設定

將本文算法(ISC)與傳統譜聚類算法(SC)、基于馬爾可夫的譜聚類算法(MKSC)、基于遺傳算法的譜聚類算法(GASC)的劃分結果在相同的實驗環境下進行有效性對比，實驗參數設置見表2，子區劃分評價結果如表2、圖7所示。

表2 路網劃分評價結果

圖7 路網劃分評價指標

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

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

圖8 路網劃分結果

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

4 結束語

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