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

周余軍 劉智勇 阮太元

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

關(guān)鍵詞：決策圖 模糊聚類(lèi) 交通狀態(tài)模式 截?cái)嗑嚯x 密度峰值 快速路

中圖分類(lèi)號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

引言

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

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

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

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

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

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

聚類(lèi)中心點(diǎn)本身的密度大，且密度大于周?chē)従狱c(diǎn)密度；

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

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

（1）局部密度：

（1）

其中函數(shù)，參數(shù)為截?cái)嗑嚯x，需要事先指定。

（2）距離

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

（2）

定義距離為：

（3）

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

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

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

第一步：設(shè)定的取值范圍為（為交通數(shù)據(jù)點(diǎn)中每?jī)牲c(diǎn)間最大的距離），采用啟發(fā)式的學(xué)習(xí)方法，以指定的步長(zhǎng)在中對(duì)進(jìn)行取值。經(jīng)過(guò)反復(fù)實(shí)驗(yàn)，將步長(zhǎng)取為0.1。

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

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

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

（4）

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

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

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

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

（5）

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

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

（6）

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

（7）

（8）

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

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

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

第二步：計(jì)算模糊隸屬度矩陣。

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

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

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

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

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

第一步：設(shè)定的取值范圍為，采用啟發(fā)式的學(xué)習(xí)方法，以0.1為步長(zhǎng)在中對(duì)進(jìn)行取值。

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

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

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

第五步：計(jì)算模糊隸屬度矩陣。

第六步：更新模糊聚類(lèi)中心。

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

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

2 仿真結(jié)果分析

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

（9）

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

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

3 結(jié)語(yǔ)

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

參考文獻(xiàn)

[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]莊斌，楊曉光，李克平.道路交通擁擠事件判別準(zhǔn)則與檢測(cè)算法[J].中國(guó)公路學(xué)報(bào)，2006，19（3）：82-86.

[4]李清泉，高德荃，楊必勝. 基于模糊支持向量機(jī)的城市道路交通狀態(tài)分類(lèi)[J].吉林大學(xué)學(xué)報(bào)：工學(xué)版，2009，吉林大學(xué)學(xué)報(bào)（工學(xué)版），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.