基于聚類算法的城市快速路交通狀態模式分類

周余軍 劉智勇 阮太元

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

關鍵詞：決策圖 模糊聚類 交通狀態模式 截斷距離 密度峰值 快速路

中圖分類號：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，FCM，traffic pattern classification，cut-off distance，density peaks，Urban freeway

引言

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

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

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

1 基于聚類算法的交通狀態模式分類

1.1 基于CFSFDP的交通狀態模式分類

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

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

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

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

（1）局部密度：

（1）

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

（2）距離

設表示為的降序排列下標序：

（2）

定義距離為：

（3）

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

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

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

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

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

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

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

（4）

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

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

1.2 基于FCM的交通狀態模式分類

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

（5）

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

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

（6）

對式（6）求偏導，進一步求得：

（7）

（8）

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

采用FCM進行交通狀態模式分類步驟為：

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

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

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

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

1.3 基于組合算法的交通狀態模式分類

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

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

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

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

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

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

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

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

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

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

2 仿真結果分析

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

（9）

式中，為分類準確率，為分類正確的交通樣本數，為某類交通狀態模式樣本總數。

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

3 結語

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

參考文獻

[1]姜桂艷.道路交通狀態判別技術與應用[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]李清泉，高德荃，楊必勝. 基于模糊支持向量機的城市道路交通狀態分類[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.