基于AP算法的路網同質區域劃分方法研究

郭紅莉，劉曉雯，種瀟敏，曲衛東

(長安大學 信息工程學院，陜西 西安 710064)

0 引 言

交通作為城市的重要組成部分，為城市經濟的快速發展做出了巨大貢獻，也在很大程度上促進了社會的進步。但是隨著城市規模的不斷擴大和城市化進程的加快，同時也導致了汽車的保有量急劇增長，城市的交通擁堵問題日益嚴峻。機動車保有量的快速增長給城市交通運行帶來了很大的壓力，嚴重影響了城市交通系統的正常運轉，并在一定程度上限制了社會經濟的穩定發展。同時交通擁堵所引發的經濟損失、交通事故等后果對城市居民和社會造成了很多負面影響，因此如何緩解交通擁堵問題成為當今的熱點研究方向之一。對城市路網進行合理的分區，有助于提高道路交通的運行效率。挖掘城市路網交通信息并對路網進行分區，降低路網復雜性成為智能交通領域中的一個重要研究方向。這些研究可以更好地發現城市交通內部的運行規律，從而為交通管理者制定交通擁堵緩解措施提供有力的理論依據。

目前，許多國內外研究者都認識到區域劃分在智能交通領域研究中的重要意義，并對路網區域劃分方面進行了大量的探索和研究。例如Geroliminis等人利用指數族函數對仿真數據進行回歸分析，并基于3D-vMFD、3D-pMFD提出了一種新的交通區域劃分方法[1]。Wang等人首先使用改進的C均值算法評價交叉口在交通路網中的重要性，然后選擇幾個關鍵路口將路網劃分成幾個不同的子區域，并最終達到了對路網的合理分區和控制[2]。尹洪英等人基于路網交叉口的拓撲特性和實時交通流數據構建了相似性矩陣，并采用譜聚類算法結合譜圖理論對路網進行動態劃分[3]。呂玉強等人以聚類算法為基礎，通過對比和交通區域劃分的相似性，利用K-means空間聚類法對交通區域進行劃分[4]。Saeedmanesh等人通過在路網中迭代計算，獲得局部性質相似的路段，然后采用對稱正定矩陣因式分解獲得較高相似性的集群，從而獲得路網的同質區域并實現區域的劃分[5]。馮樹民等人考慮路網區域之間的相似性和位置關系，使用兩維圖論聚類方法對交通區域進行劃分，能夠有效克服現有方法無法識別交通區域位置關系的缺點，并在此基礎上對區域進行合并[6]。

從國內外研究可以看出，交通區域劃分多基于聚類方法對路網宏觀交通狀態進行劃分，大多數劃分算法存在著初始值敏感性及聚類個數的設定問題。同時，如今國內外基于路網同質區域劃分的研究比較少，因此文中采用AP算法對路網進行同質區域劃分，該方法與現有的方法相比優勢在于它可以很好地挖掘出城市路網中的瓶頸路段和敏感節點，并且具有很好的穩定性、可靠性和高效性，從而有助于交通部門針對道路改造、交通誘導和交通規劃方面做一些措施以進一步改善交通擁堵問題。

1 AP算法原理

AP算法[7]是Frey等人于2007年在Science雜志中的“Clustering by Passing Messages Between Data Points”一文中提出的一種基于數據點間“信息傳遞”的新聚類算法，因其具有高效、穩定等特點，被廣泛應用于各大領域。并且AP算法不需要事先確定聚類中心和聚類個數，而是將所有樣本點都看作潛在的聚類中心，通過循環迭代，在迭代過程中不斷搜索合適的聚類中心，自動從數據點間識別聚類中心的位置及個數[8]。

AP算法的基本思想是基于網絡中數據點與數據點之間進行的消息傳遞[9]，將整個數據集合看作網絡，其中將各個數據點看作網絡中的節點，然后通過網絡中各條邊的消息傳遞進而尋找數據點與聚類中心之間的隸屬關系，從而實現數據間的自適應聚類。AP算法首先計算數據點間的相似度矩陣s，將任意兩個數據點i與j之間的相似度值定義為s(i,j)，一般將其設置為一個負的平方差值(歐氏距離的負數)，其計算公式為：

s(i,j)=-d2(xi,xj)=-|xi-xj|2,i≠j

(1)

在相似度矩陣中，對角線上的數值s(i,i)作為某點能否成為聚類中心的評判標準，這個值稱為參考度p，調節p值可以改變某點成為聚類中心的概率，p值越大則證明該數據點成為聚類中心的概率越大。在消息傳遞之前，通常認為所有的數據點都同等地適合作為聚類中心，因此p值的選取一般為相似度矩陣的中心值(結果產生聚類中心的數量較合適)或相似度矩陣的最小值(結果產生聚類中心的數量較少)，但也可以根據實際情況來設定。p值通過以下公式計算：

(2)

為了找到合適的聚類中心，AP算法通過迭代不斷地更新相似度矩陣中每個數據點的吸引度值和歸屬度值，直到找到最合適的聚類中心，然后將網絡中其余的數據點分配到相應的簇中。算法通過r(i,k)+a(i,k)的值來確定聚類中心點，r(i,k)+a(i,k)的值越大，則k最終作為聚類中心的可能性越大。算法迭代之前，將吸引度矩陣R和歸屬度矩陣A都初始化為0矩陣，并使用以下公式迭代計算：

(3)

at+1(i,k)=min(0,rt(k,k)+

(4)

(5)

其中，r(i,k)為吸引度信息，表示點i選擇點k的過程；a(i,k)為歸屬度信息，表示點k選擇點i的過程。

算法在傳遞消息的過程中，可能會由于數據震蕩影響最終聚類結果，因此在更新信息的過程中引入阻尼系數λ，其值在0和1之間。迭代公式為：

rt+1(i,k)=(1-λ)rt+1(i,k)+λrt(i,k)

(6)

at+1(i,k)=(1-λ)at+1(i,k)+λat(i,k)

(7)

迭代完成后，根據吸引度值和歸屬度值來得到最終的聚類中心點，不論是否k=i，對于點i來說，使得r(i,k)+a(i,k)取最大值的那個k即為點i的聚類中心。當算法的迭代次數達到設定閾值或經過若干次迭代后其聚類中心保持不變時，則消息傳遞過程終止，算法結束。

2 路網同質區域劃分

道路交通網絡不僅要考慮路網的拓撲結構，還要考慮路網本身的交通特性[10]。城市路網的拓撲特性與交通流的周期相似特性揭示著路網中存在同質的區域。路網的同質區域是指路網中交通流在一段時間內具有規律變化的相似性的區域。首先對交通時間序列數據進行聚類分析，然后得到交通狀態變化的同質區域并挖掘出路網中的瓶頸路段和敏感節點。發現和挖掘出這些同質區域對于局部區域實施靈活的協調控制方案、保證交通控制系統的可靠性等方面有很大作用，不同同質區域間的交通狀態變化情況還可以很好地幫助我們分析出路網結構的脆弱性，挖掘出路網的敏感交叉點。文中主要關注路網宏觀同質區域的劃分。

2.1 數據預處理

文中實驗數據來自于陜西省西安市二環區域內的13 000輛出租車運行的GPS數據，每日采集數據條目數約為2 700萬條，浮動車系統每隔30秒更新一次數據。由于出租車采集到的GPS數據均為沒有經過處理的原始數據，這些數據可能受到定位設備或外部因素的影響，導致其內容和準確性存在部分的偏差和錯誤[11]。數據篩選和處理的目的是為了去除錯誤數據和研究范圍之外的數據。對出租車GPS數據做了如下分類和相應處理：

(1)數據冗余。若數據表中有多條相同記錄則只保留其中一條，其余記錄全部刪除。

(2)數據錯誤。若數據表中某個字段的屬性值超出合理范圍，如經緯度、速度等字段，則刪除此類數據。

(3)數據失效。文中是對15分鐘內的交通狀態分析，所以篩選出速度字段連續15分鐘取值為0的數據條目并將其刪除。

(4)坐標糾偏。在將出租車GPS坐標匹配城市路網之前，針對出租車GPS數據的偏移情況，將出租車GPS數據坐標系與路網坐標系統一轉換為WGS-84坐標系。

GPS數據做以上處理之后，文中選擇西安市內交通狀態變化較復雜的二環區域作為研究對象。由于城市路網是一個具有離散性、強耦合性和非線性的復雜網絡，所以首先要將真實的城市路網抽象成拓撲結構圖[12]。通過標記西安市二環區域內的交叉點經緯度坐標來構建城市路網的拓撲結構圖，然后通過計算西安市13 000輛浮動車在工作日各區域路段不同時間段內的平均速度，對城市路網的各個區域擁堵情況進行劃分。采用國內最常用的B類城市的標準，即公安部新修訂的《城市道路交通管理評價指標體系》中的規定來判別交通狀態。該指標根據城市主干道路車輛的平均速度定義道路的擁堵程度，并將交通狀態劃分為五個等級，分別是暢通、基本暢通、輕度擁堵、中度擁堵和嚴重擁堵，同時規定了各自的速度閾值[13-14]。當平均速度大于等于28 km/h時為暢通狀態，當平均速度位于25 km/h和28 km/h之間時為基本暢通狀態，當平均速度位于22 km/h和25 km/h之間時為輕度擁堵狀態，當平均速度位于19 km/h和22 km/h之間時為中度擁堵狀態，平均速度小于19 km/h時為嚴重擁堵狀態。

2.2 時間序列數據的相似性度量

時間序列數據是按照時間順序排列的數據序列，可以潛在地表達數據內部狀態隨時間變化的規律，交通流是典型的時間序列數據。對時間序列數據進行分析，挖掘其內部規律在各個領域應用廣泛。文中以西安市二環區域內某工作日6:00到22:00這一時間段內的189條路段的出租車為研究對象，每隔15分鐘計算一次各路段出租車的平均速度作為時間序列數據。

時間序列數據在進行聚類分析之前，通常需要計算樣本之間的相似度。對于很多的機器學習算法來說，選擇一種合適的相似性度量方法評價數據之間的相似性對這些算法的性能有非常重要的影響。相似性度量[15]指的是樣本之間相似性程度的一種度量，然后根據數據點間的相似度，將時間序列數據集劃分為多個類別。時間序列的相似性度量通常采用衡量兩個不同時間序列之間距離遠近程度的方式來驗證兩個序列是否相似[16]。聚類算法在數據挖掘領域應用廣泛，在應用于時間序列數據挖掘領域時，一般會與相似性度量相結合[17]。相似性度量的目的在于計算、衡量空間中樣本點間的相似性。文中采用的時間序列數據是等長的，而動態時間規整距離(DTW)主要用于解決兩個不等長的時間序列進行相似性對比的問題，并且DTW距離需要計算累加矩陣及最優規整路徑，所以復雜度較高且對數據點變化敏感，因此選用歐氏距離作為相似性度量的方法。

2.3 算法設計及流程

文中研究的數據為在工作日內預處理后的(6:00至22:00)189條路段的時間序列數據，然后采用歐氏距離計算每兩條路段之間的相似度值并構建相似度矩陣。

基于AP算法的路網同質區域劃分步驟如下：

步驟1：首先使用歐氏距離作為相似性度量方法計算189條路段時間序列數據的相似性；

步驟2：將建立的時間序列相似度矩陣作為本次聚類的輸入數據集；

步驟3：選擇相似度矩陣的均值作為參考度p的值，來得到合適的聚類個數；

步驟4：算法初始化，迭代更新吸引度矩陣R(189*189)和歸屬度矩陣A(189*189)；

步驟5：當聚類中心穩定或迭代次數達到設定閾值時，會生成最終聚類中心點，并根據聚類中心與其他點的相似程度將數據集劃分為不同的類別。

算法實現流程如圖1所示。

3 實驗結果分析

3.1 路網同質區域劃分

路網全天交通狀態變化同質區域劃分的可視化結果如圖2所示。同質區域的道路采用同一種灰度表示，不同灰度代表了路網各個區域一天內的交通擁堵程度，其中，灰度由深到淺依次表示為嚴重擁堵區域、暢通區域、基本暢通區域、中度擁堵區域和輕度擁堵區域。

從圖2中可以看出，通過對相似性路段進行聚類可以很好地發現路網中交通狀態變化的同質區域，并且可以看出路網中全天處于嚴重擁堵或者高峰時段嚴重擁堵的道路大多集中在西安市的核心區域附近。

圖1 路網區域劃分流程

圖2 路網同質區域劃分

道路時間序列變化的譜圖如圖3所示，其不同灰度表示道路的擁堵程度。從以下譜圖可以看出，從早6:00到晚10:00這一時間段內，第一、二類道路處于基本暢通狀態，第三、四、五類路網子區域的周期變化和潮汐交通現象逐漸明顯，第六類則全天多處于嚴重擁堵狀態。從譜圖中還可看出全天路網中道路狀態的變化情況，路網中同質區域內路段的交通狀態變化規律基本一致，交通部門可以根據這些變化規律做出一些交通誘導。這種同質的變化規律能很好地對該區域進行交通信號控制、道路改造及交通誘導指揮，同時也減少了一些不必要的交通疏導，從而能夠更加有效地對擁堵區域進行交通疏導工作，提高城市交通運行的效率和可靠性，進一步緩解交通擁堵問題。同時也為城市的智能交通控制和交通信息誘導提供理論支撐。

3.2 路網脆弱性的識別

通過對路網中同質區域的劃分和其全天的交通狀態情況還可以很好地幫我們挖掘出路網結構的特性。當交叉點鄰接多個不同的同質區域時，由于受到多個不同交通狀態的影響，交叉點的控制就顯得格外重要。圖4中分別標記出了部分瓶頸路段和敏感節點。

圖3 道路時間序列數據變化譜圖

分析圖4可以看到，路網中的交叉點(例如交叉點ID為25、54等)連接的路段處于不同交通狀態的區域，由于各區域的交通流變化情況并不一致，車輛從某一區域經交叉點進入另一區域時不能很好地同步，使得該交叉點的交通狀態不穩定且比較敏感；此外，當某些路段處在相同的同質區域間時(例如路段ID為11、18等)，其全天交通狀態的變化情況與周圍區域的交通狀態并不一致，因此這些路段屬于瓶頸路段，產生路段交通流瓶頸的原因可能是由于其附近存在人流量較大的公共場所，如學校、商場及醫院等。

圖4 路網同質區域劃分

3.3 針對路網同質區域的交通控制策略及誘導

交通網絡具有獨特的動態特性，應根據聚類結果設計緩解交通擁堵的潛在控制策略[18]。通過對路網時間序列數據的聚類分析，可以識別出路網中的交通狀態變化的同質區域，并且還可以挖掘出路網中的瓶頸路段和敏感節點。這里基于同質區域的劃分和結論，提出適合的交通擁堵緩解策略：

(1)針對路網中交通狀態變化的同質區域，城市交通管理者可以對其進行統一管理，大力發展公共交通，根據路段的擁堵情況，調整人們的出行方式，鼓勵人們使用公共交通方式出行，減少私家車的出行，提高公共交通換乘的便捷性[19]，進一步緩解交通擁堵的問題；

(2)針對路網中的瓶頸路段，可以在這些路段設置交通誘導板，并在高峰時段之間完成分流，同時把轉移外圍剩余車流量作為輔助措施，減少高峰時段車輛臨時變道帶來的交通擁堵[19]；

(3)針對路網中的敏感節點，可以在這些交叉口設置信號控制對其進行合理的交通流引導，以提高交叉口的通行能力。

4 結束語

依照城市交通路網不同區域內浮動車在不同時段的平均速度來判斷某路段的擁堵程度，并對城市路網進行劃分，文中提出基于AP算法的城市交通路網劃分方法，并將該方法用于路網同質區域劃分這一任務中。經過多次實驗，證明基于AP算法的交通路網區域劃分方法具有很好的穩定性、可靠性和高效性，能夠得到有效的交通擁堵區域，同時AP算法可以有效地識別路網中交通狀態變化的同質區域，并且能夠挖掘出路網中的瓶頸路段和敏感節點，從而可以更好地發現城市交通內部的運行規律，并且為交通管理者制定交通擁堵緩解措施提供有力的理論依據。