基于聚類算法的城市快速路交通狀態(tài)模式分類

周余軍 劉智勇 阮太元

摘要：交通狀態(tài)模式分類在城市交通控制系統(tǒng)中具有重要的應(yīng)用價值，本文以車流量、平均速度、時間占有率為特征參數(shù)，利用CFSFDP（快速搜索查找密度峰值聚類）算法與FCM（模糊C均值聚類）算法進行組合，給出一種新的交通狀態(tài)模式分類算法。針對廣州市某快速路交通流實測數(shù)據(jù)進行了仿真，結(jié)果表明：組合算法是可行的，且分別比CFSFDP和FCM算法有更高的分類準確率。

關(guān)鍵詞：決策圖 模糊聚類 交通狀態(tài)模式 截斷距離 密度峰值 快速路

中圖分類號：TP391 文獻標識碼：A 文章編號：1007-9416（2016）07-0117-03

Abstract：The classification of traffic patterns has a great value in urban traffic control system， this essay used the vehicle flow，vehicle speed and time occupy as feature vector， combined CFSFDP（Clustering by Fast Search and Find of Density Peaks） and FCM（Fuzzy C-Means），used the combined algorithm to classify the traffic patterns of a certain freeway in GuangZhou. The result turned out that the combined algorithm is applicable in classifying traffic patterns and it is more accurate than CFSFDP and FCM alternatively.

Key Words：decision graph，F(xiàn)CM，traffic pattern classification，cut-off distance，density peaks，Urban freeway

引言

交通信號控制是解決城市交通擁堵的有效方法之一。隨著信息技術(shù)和人工智能技術(shù)的發(fā)展，智能交通信號控制系統(tǒng)的效果已經(jīng)得到明顯改善。然而，現(xiàn)有的智能交通信號控制系統(tǒng)都需要根據(jù)交通流狀態(tài)在線優(yōu)化配時方案，當路口數(shù)規(guī)模比較大時，在線優(yōu)化將會遇到“維數(shù)災(zāi)”問題，此時系統(tǒng)將無法實時響應(yīng)交通流的變化，因此會大大影響信號控制效果。

統(tǒng)計表明，從某一個時刻來看：交通流的變化是隨機的，但從某一個時間段來看，交通流的變化呈現(xiàn)出明顯的規(guī)律性，如：上下班高峰期、節(jié)假日出行高峰期，其交通量比非高峰時段明顯增加。把這些規(guī)律性出現(xiàn)的交通現(xiàn)象稱之為交通狀態(tài)模式。如果能夠準確分辨出各種交通狀態(tài)模式，則可離線計算對應(yīng)的最優(yōu)配時方案，并存貯在交通信號控制系統(tǒng)中；在實施交通信號控制時，通過檢測器所獲得的交通狀態(tài)信息能夠匹配已知模式，則可用相應(yīng)的最優(yōu)配時方案進行信號控制。這就解決了交通信號控制系統(tǒng)在線優(yōu)化所遇到的問題。

目前，國內(nèi)外學者已經(jīng)提出了一些交通狀態(tài)模式分類的方法，其中具有代表性的有加州算法標準偏差算法[1]、雙指數(shù)平滑算法等[2]、相對流量增量相對占有率增量比較檢測算法[3]、模糊支持向量機分類方法[4]等等。上述交通狀態(tài)模式分類算法主要依據(jù)路段上交通流基本參數(shù)的變化（占有率、流量、速度、飽和度等），并設(shè)定相應(yīng)閾值來判斷交通處于何種狀態(tài)，但是交通流狀態(tài)的定義具有主觀上的模糊性，與每條道路的實際運行環(huán)境密切相關(guān)，因此相關(guān)參數(shù)閾值的確定對交通狀態(tài)模式的分類結(jié)果將會產(chǎn)生很大影響。基于此，本文采用FCM進行交通狀態(tài)模式分類?？紤]到模糊聚類算法對初始點的敏感性，引入能確定聚類中心的CFSFDP，將CFSFDP與FCM的進行組合，分別采用這3類算法進行交通狀態(tài)模式分類。

1 基于聚類算法的交通狀態(tài)模式分類

1.1 基于CFSFDP的交通狀態(tài)模式分類

CFSFDP能全局遍歷數(shù)據(jù)點確定聚類中心，CFSFDP確定的聚類中心同時具有以下兩個特點[5]：

聚類中心點本身的密度大，且密度大于周圍鄰居點密度；

聚類中心點與其他密度比它大的數(shù)據(jù)點之間的距離大。

對于待聚類的交通數(shù)據(jù)集，其中，代表第個交通數(shù)據(jù)點的平均車速、時間占有率與流量，定義表示數(shù)據(jù)點和之間的距離。對于中的任何數(shù)據(jù)點，為其定義和兩個量，分別對應(yīng)上述特點中的密度與距離。

（1）局部密度：

（1）

其中函數(shù)，參數(shù)為截斷距離，需要事先指定。

（2）距離

設(shè)表示為的降序排列下標序：

（2）

定義距離為：

（3）

對于中的每一個數(shù)據(jù)點，可以計算其對應(yīng)的，作出對應(yīng)決策圖[5]（為橫軸，為縱軸的二維圖）選擇、都大的數(shù)據(jù)點作為聚類中心點。

CFSFDP對于參數(shù)的取值設(shè)定了大致范圍，但具體的取值對于本文研究的交通狀態(tài)模式分類沒有定論；式（1）中也看出參數(shù)的取值很大程度上影響著決策圖中聚類中心點的分布，進而影響最終的分類效果，為確保CFSFDP能較好地運用到交通狀態(tài)模式分類，本文對參數(shù)的選取進行改進。

參數(shù)選取的改進：CFSFDP對于的取值會使得每個數(shù)據(jù)點的平均鄰居個數(shù)約為數(shù)據(jù)點總數(shù)的1%～2%，但這只是針對一般分類情況；對于交通狀態(tài)模式分類，如何找到較好的進而有效地找到各交通狀態(tài)模式中心點尚未明確，所以本文提出一種尋找較優(yōu)的改進，使得CFSFDP能夠獲得較準確的聚類中心。改進具體步驟為：

第一步：設(shè)定的取值范圍為（為交通數(shù)據(jù)點中每兩點間最大的距離），采用啟發(fā)式的學習方法，以指定的步長在中對進行取值。經(jīng)過反復(fù)實驗，將步長取為0.1。

第二步：在當前取值下，使用式（1）、（3）計算每個交通數(shù)據(jù)點的和，作出決策圖找出當前的聚類中心點，并構(gòu)造聚類中心點矩陣。

第三步：判斷前后兩次迭代獲得的聚類中心點個數(shù)是否相同，如果不同，則回到第一步繼續(xù)迭代。

第四步：由式（4）計算前后兩次迭代獲得的聚類中心點矩陣的距離。設(shè)當次迭代所構(gòu)造的聚類中心點矩陣為。如果前后中心點矩陣間距離小于某個閾值，則表明當前為較優(yōu)截斷距離，停止迭代。否則回到第一步繼續(xù)迭代。

（4）

式（4）中，為最終聚類個數(shù)，為特征參數(shù)個數(shù)，本文中取。

本文通過改進找到4個聚類中心，分別對應(yīng)自由流、穩(wěn)定流、擁擠流、堵塞流四種交通狀態(tài)模式。找到4類交通狀態(tài)模式聚類中心點后，根據(jù)歐式距離最短原則，對交通數(shù)據(jù)樣本點逐一遍歷，判斷樣本點離哪個中心點的歐式距離最短，則歸為相應(yīng)的交通狀態(tài)模式類。

1.2 基于FCM的交通狀態(tài)模式分類

FCM是一種基于目標函數(shù)的分類算法，通過求解帶約束條件的目標函數(shù)將聚類問題轉(zhuǎn)換成非線性規(guī)劃問題，之后通過迭代優(yōu)化得到滿意的聚類結(jié)果[6]。待求解的FCM目標函數(shù)為：

（5）

式（5）中，，為待分類的交通數(shù)據(jù)集，其中，代表第個交通數(shù)據(jù)點的平均車速、時間占有率與流量；表示聚類中心矩陣；為最終輸出的隸屬度矩陣，為隸屬度矩陣中第行第列的隸屬度；為第個聚類中心與第個樣本間的歐式距離；為加權(quán)指數(shù)，令；設(shè)定聚類中心數(shù)為4，即。

求解帶約束條件的目標函數(shù)，通常是引入拉格朗日系數(shù)構(gòu)造新函數(shù)進行求解：

（6）

對式（6）求偏導(dǎo)，進一步求得：

（7）

（8）

式（7）、（8）即為目標函數(shù)式（5）取得極小值的必要條件。通過反復(fù)迭代式（7）、（8）就可以得到最終的和。

采用FCM進行交通狀態(tài)模式分類步驟為：

第一步：設(shè)定聚類中心點個數(shù)、迭代次數(shù)閾值、初始化聚類中心，設(shè)置計數(shù)器。

第二步：計算模糊隸屬度矩陣。

第三步：更新模糊聚類中心。第四步：判斷如果，則算法迭代停止，最終輸出聚類中心和隸屬度矩陣；否則，，重新回到第二步求隸屬度矩陣，繼續(xù)迭代。

迭代完成，得到隸屬度矩陣與四個交通狀態(tài)模式中心，通過隸屬度矩陣完成未分類交通數(shù)據(jù)點的分類得到四類交通狀態(tài)模式數(shù)據(jù)集。

1.3 基于組合算法的交通狀態(tài)模式分類

FCM的初始聚類中心點是隨機選擇的，在算法迭代過程中有可能使目標函數(shù)陷入局部最優(yōu)，導(dǎo)致FCM過早迭代完成使得分類效果不佳；CFSFDP能較準確的找到聚類中心點，但分類過程是遵循歐式距離最短原則，如果要分類的交通數(shù)據(jù)點離幾個交通狀態(tài)模式中心點的距離都一致時，則容易發(fā)生錯分從而影響分類總體結(jié)果?；诖?，本文采用CFSFDP與FCM組合的算法。組合算法在分類過程中能找到較準確的聚類中心，將找到的聚類中心代入FCM作為其初始聚類中心點，然后迭代找到最優(yōu)聚類中心，從而輸出最優(yōu)聚類結(jié)果。

采用組合算法進行交通狀態(tài)模式分類步驟為：

第一步：設(shè)定的取值范圍為，采用啟發(fā)式的學習方法，以0.1為步長在中對進行取值。

第二步：在當前取值下，計算每個交通數(shù)據(jù)點的和，作出決策圖找出當前聚類中心點，并構(gòu)造聚類中心點矩陣；并判斷前后兩次迭代獲得的聚類中心點個數(shù)是否相同，如果不同，則回到第一步繼續(xù)迭代。

第三步：計算前后兩次迭代獲得的聚類中心點矩陣的距離，如果前后中心點矩陣間距離小于某個閾值，停止迭代，輸出聚類中心數(shù)c及聚類中心點矩陣。否則回到第一步繼續(xù)迭代。

第四步：設(shè)定FCM聚類中心點個數(shù)為c、初始化聚類中心點矩陣為、迭代次數(shù)閾值，設(shè)置計數(shù)器。

第五步：計算模糊隸屬度矩陣。

第六步：更新模糊聚類中心。

第七步：判斷如果，則算法迭代停止，最終輸出聚類中心和隸屬度矩陣；否則，，重新回到第五步求隸屬度矩陣，繼續(xù)迭代。

迭代完成，得到隸屬度矩陣與四個交通狀態(tài)模式中心，通過隸屬度矩陣完成未分類交通數(shù)據(jù)點的分類得到四類交通狀態(tài)模式數(shù)據(jù)集。

2 仿真結(jié)果分析

本文采用的數(shù)據(jù)為廣州市某快速路完整一周的交通流數(shù)據(jù)，車輛檢測器類型為地感線圈，車輛類型都相應(yīng)的折算成標準小客車類型，采集參數(shù)為流量、時間占有率、平均速度，每5分鐘作為一個樣本數(shù)據(jù)，總共樣本數(shù)據(jù)2017個。表1為三種算法分別對交通狀態(tài)模式分類后的各類交通狀態(tài)模式的分類準確率，準確率定義是，對于某一類交通狀態(tài)模式，分類正確的交通樣本數(shù)與某一類交通狀態(tài)模式樣本總數(shù)比值，計算公式為：

（9）

式中，為分類準確率，為分類正確的交通樣本數(shù)，為某類交通狀態(tài)模式樣本總數(shù)。

由表1得知組合算法比CFSFDP有更高的準確率，CFSFDP的分類過程是遵循歐式距離最短原則，待分類的交通數(shù)據(jù)點離幾個交通狀態(tài)模式中心點的距離都一致時，容易發(fā)生錯分，而組合算法采用隸屬度最大原則進行分類，會考慮整體交通樣本點計算隸屬度矩陣，從而得到各交通樣本點較理想的分類；同時從表1中可得知組合算法比FCM準確率高，這兩種算法雖然都采用隸屬度最大原則進行分類，但由推導(dǎo)公式（7）、公式（8）得知隸屬度矩陣的計算與聚類中心點的選擇有很大關(guān)系，更合理的聚類中心點會計算出更合理的隸屬度矩陣，因此組合算法的分類效果優(yōu)于FCM。

3 結(jié)語

本文在FCM和CFSFDP的基礎(chǔ)上，通過準確選取聚類中心點，用模糊均值聚類算法將歷史交通流數(shù)據(jù)進行分類，并利用Matlab軟件進行仿真，結(jié)果表明：所采用的組合算法在交通狀態(tài)模式分類上是可行的，且分別比FCM和CFSFDP具有更高的準確率。需要指出的是，本文所給出的算法對該快速路是有效的，對其他快速路或交通路段進行交通狀態(tài)模式分類是否有效則需進一步研究。

參考文獻

[1]姜桂艷.道路交通狀態(tài)判別技術(shù)與應(yīng)用[M].北京：人民交通出版社，2004.

[2] Huang Y， Kang Y， Zhao S. Urban Regional Road Network Traffic State Identifying Method[C]// Intelligent Computation Technology and Automation （ICICTA）， 2012 Fifth International Conference on. IEEE， 2012：530-533.

[3]莊斌，楊曉光，李克平.道路交通擁擠事件判別準則與檢測算法[J].中國公路學報，2006，19（3）：82-86.

[4]李清泉，高德荃，楊必勝. 基于模糊支持向量機的城市道路交通狀態(tài)分類[J].吉林大學學報：工學版，2009，吉林大學學報（工學版），2009，39（增刊2）：131-0134（S2）：131-134.

[5]Alex Rodriguez and Alessandro Laio. Clustering by fast search and find of density peaks.Science 344，1492（2014）；DOI：10.1126/science.1242072.

[6]Bezdek J C. Pattern Recognition with Fuzzy Objective Function Algorithms[M]. New York Plenum Press，1981.