周余軍 劉智勇 阮太元

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

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

中圖分類號(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)在線優(yōu)化配時(shí)方案，當(dāng)路口數(shù)規(guī)模比較大時(shí)，在線優(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)象稱之為交通狀態(tài)模式。如果能夠準(zhǔn)確分辨出各種交通狀態(tài)模式，則可離線計(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)在線優(yōu)化所遇到的問(wèn)題。

目前，國(guó)內(nèi)外學(xué)者已經(jīng)提出了一些交通狀態(tài)模式分類的方法，其中具有代表性的有加州算法標(biāo)準(zhǔn)偏差算法[1]、雙指數(shù)平滑算法等[2]、相對(duì)流量增量相對(duì)占有率增量比較檢測(cè)算法[3]、模糊支持向量機(jī)分類方法[4]等等。上述交通狀態(tà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)模式的分類結(jié)果將會(huì)產(chǎn)生很大影響?；诖耍疚牟捎肍CM進(jìn)行交通狀態(tài)模式分類?？紤]到模糊聚類算法對(duì)初始點(diǎn)的敏感性，引入能確定聚類中心的CFSFDP，將CFSFDP與FCM的進(jìn)行組合，分別采用這3類算法進(jìn)行交通狀態(tài)模式分類。

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

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

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

聚類中心點(diǎn)本身的密度大，且密度大于周圍鄰居點(diǎn)密度；

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

對(duì)于待聚類的交通數(shù)據(jù)集，其中，代表第個(gè)交通數(shù)據(jù)點(diǎn)的平均車速、時(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)作為聚類中心點(diǎn)。

CFSFDP對(duì)于參數(shù)的取值設(shè)定了大致范圍，但具體的取值對(duì)于本文研究的交通狀態(tài)模式分類沒(méi)有定論；式（1）中也看出參數(shù)的取值很大程度上影響著決策圖中聚類中心點(diǎn)的分布，進(jìn)而影響最終的分類效果，為確保CFSFDP能較好地運(yùn)用到交通狀態(tà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ì)一般分類情況；對(duì)于交通狀態(tài)模式分類，如何找到較好的進(jìn)而有效地找到各交通狀態(tài)模式中心點(diǎn)尚未明確，所以本文提出一種尋找較優(yōu)的改進(jìn)，使得CFSFDP能夠獲得較準(zhǔn)確的聚類中心。改進(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)前的聚類中心點(diǎn)，并構(gòu)造聚類中心點(diǎn)矩陣。

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

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

（4）

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

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

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

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

（5）

式（5）中，，為待分類的交通數(shù)據(jù)集，其中，代表第個(gè)交通數(shù)據(jù)點(diǎn)的平均車速、時(shí)間占有率與流量；表示聚類中心矩陣；為最終輸出的隸屬度矩陣，為隸屬度矩陣中第行第列的隸屬度；為第個(gè)聚類中心與第個(gè)樣本間的歐式距離；為加權(quán)指數(shù)，令；設(shè)定聚類中心數(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)模式分類步驟為：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 仿真結(jié)果分析

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

（9）

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

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

3 結(jié)語(yǔ)

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