基于改進(jìn)FCM算法的城市交叉口交通狀態(tài)判別

劉宗鋒， 楊凱利， 吳魯香， 吳東平

(1.山東科技大學(xué)交通學(xué)院， 青島 266590； 2.沈陽(yáng)建筑大學(xué)交通工程學(xué)院， 沈陽(yáng) 110168；3.山東華凌電纜有限公司， 濟(jì)南 250220)

0 引言

目前，在智能交通系統(tǒng)研究領(lǐng)域中，交通運(yùn)行狀態(tài)的判別已經(jīng)成為一個(gè)研究熱點(diǎn). 準(zhǔn)確、實(shí)時(shí)的交通狀態(tài)判別有助于交通管理部門及時(shí)了解和掌握城市整體的交通運(yùn)行狀況，同時(shí)也便于交通管理部門提前預(yù)估并制定城市交通擁堵的疏導(dǎo)決策方案，對(duì)緩解交通擁堵具有重要意義. 因此，國(guó)內(nèi)外許多學(xué)者對(duì)交通狀態(tài)判別的研究給予了高度的關(guān)注.

He等[1]選取速度性能指標(biāo)作為路網(wǎng)狀態(tài)評(píng)價(jià)指標(biāo)，提出了1種用擁擠指數(shù)衡量擁堵程度的評(píng)價(jià)方法，并以北京市公路網(wǎng)為例進(jìn)行了路段和路網(wǎng)擁堵評(píng)價(jià). Bae等[2]選取密度數(shù)據(jù)，利用Gaussian 混合模型實(shí)現(xiàn)對(duì)高速公路交通狀態(tài)的判別. 任其亮等[3]利用Relief F算法得到特征向量的權(quán)值，建立了基于改進(jìn)的FCM算法(W-FCM)的綜合判別模型，用于對(duì)城市交叉口交通狀態(tài)的判別. Antoniou等[4]利用數(shù)據(jù)驅(qū)動(dòng)的概念提出基于位置的目標(biāo)路段狀態(tài)判別的方法. 陳兆盟等[5]提出了1種以車頭時(shí)距的方差和時(shí)間占有率為判別指標(biāo)并結(jié)合交通信號(hào)控制優(yōu)化的交通狀態(tài)判別方法，結(jié)果表明，該方法可有效地判別過(guò)飽和交通狀態(tài). 商強(qiáng)等[6]提出1種譜聚類與隨機(jī)子空間集成K最近鄰的模型(SC-RS-KNN)，用于快速路交通狀態(tài)的判別. 戴學(xué)臻等[7]利用集對(duì)分析與三角模糊數(shù)ɑ-截集耦合實(shí)現(xiàn)對(duì)城市道路交通狀態(tài)的判別. 莊勁松等[8]建立1種模糊綜合判別模型，實(shí)現(xiàn)對(duì)道路交通狀態(tài)的判別. 蔡曉禹等[9]利用FCM算法實(shí)現(xiàn)對(duì)山地城市快速路交通狀態(tài)的判別，并結(jié)合視頻圖像驗(yàn)證判別的準(zhǔn)確度. 常麗君等[10]在FCM算法基礎(chǔ)上進(jìn)行優(yōu)化，將概率神經(jīng)網(wǎng)絡(luò)(PNN)與基于遺傳(GA)模擬退火(SA)的改進(jìn)FCM算法相結(jié)合實(shí)現(xiàn)對(duì)交通狀態(tài)的判別. 黃艷國(guó)等[11]利用馬氏距離代替?zhèn)鹘y(tǒng)歐式距離實(shí)現(xiàn)對(duì)FCM算法的改進(jìn)，使城市道路交通狀態(tài)的判別結(jié)果更加準(zhǔn)確.

由于交通狀態(tài)很難用具體的數(shù)字來(lái)表示，具有不確定性和模糊性，模糊聚類算法被廣泛應(yīng)用在交通狀態(tài)判別中，其中應(yīng)用FCM算法來(lái)判別交通狀態(tài)已經(jīng)取得了不少成就，但是大多數(shù)的研究都是針對(duì)城市道路或者高速公路的，對(duì)城市交叉口交通狀態(tài)判別的研究相對(duì)較少，其次，忽略了各特征參數(shù)之間的不均衡性，缺少對(duì)各判別指標(biāo)權(quán)重的研究. 基于此，本文開(kāi)展了對(duì)城市交叉口交通狀態(tài)判別的研究，引入熵權(quán)法計(jì)算各判別指標(biāo)的權(quán)重值，構(gòu)建1種基于K-means算法和熵權(quán)法加權(quán)的改進(jìn)FCM算法，實(shí)現(xiàn)對(duì)交叉口交通狀態(tài)的快速判別，為交通管理者制定交叉口信號(hào)控制策略提供依據(jù).

1 城市交叉口交通狀態(tài)劃分

1.1 判別指標(biāo)的選取

用于描述城市交叉口交通狀態(tài)的判別指標(biāo)有很多，如到達(dá)率、平均延誤時(shí)間、排隊(duì)長(zhǎng)度、平均運(yùn)行速度、飽和度、車頭時(shí)距等. 為了綜合判別交叉口交通狀態(tài)需要選取合理的判別指標(biāo)，然而并不意味著選取的判別指標(biāo)越多越好，而是要考慮選取的判別指標(biāo)能對(duì)交叉口狀態(tài)反應(yīng)敏感且獲取簡(jiǎn)單，因此，本文選取平均排隊(duì)長(zhǎng)度、平均延誤、飽和度3個(gè)交通參數(shù)為判別指標(biāo)，組成了交叉口交通狀態(tài)判別指標(biāo)體系.

1)飽和度

交叉口飽和度反映了整個(gè)交叉口交通負(fù)荷狀況，其為各進(jìn)口道飽和度的加權(quán)平均值[13]，并非各進(jìn)口道飽和度之和：

(1)

式中，n為進(jìn)口車道數(shù)；qi為進(jìn)口道i的飽和度；Qi為進(jìn)口道i的交通量(pcu/h).

2)平均延誤

延誤反映了交叉口交通狀態(tài)，利用數(shù)學(xué)模型計(jì)算難度大，可通過(guò)仿真的形式比較容易獲得.交叉口的平均延誤：

(2)

式中，di為進(jìn)口道i的平均延誤(pcu/s)；其他符號(hào)同前.

3)平均排隊(duì)長(zhǎng)度

排隊(duì)長(zhǎng)度反映了交叉口的擁擠程度[14]，是指從停止線開(kāi)始排隊(duì)到排隊(duì)末尾之間的距離.平均排隊(duì)長(zhǎng)度見(jiàn)式(3)：

(3)

式中，n為車道數(shù)；li為進(jìn)口道i的平均排隊(duì)長(zhǎng)度(m).

1.2 交叉口交通狀態(tài)劃分

本文依據(jù)交叉口的交通流特性及擁堵強(qiáng)度，將城市交叉口交通狀態(tài)分為暢通、緩行、擁堵3個(gè)狀態(tài)，其對(duì)應(yīng)的交通特征如下：

1)“暢通”狀態(tài)：車輛較少，車輛行駛速度很高，不超過(guò)限速的條件下，駕駛員能自由地選擇車速行駛，受到其他車輛的影響較小；

2)“緩行”狀態(tài)：車輛不斷增多，行駛速度降低，車輛行駛自由受限，延誤增大；

3)“擁堵”狀態(tài)：進(jìn)口道的排隊(duì)長(zhǎng)度不斷增加，導(dǎo)致車輛需要停車一次或者多次才能通過(guò)交叉口，行駛速度大幅降低.

2 交通狀態(tài)判別方法

2.1 FCM算法

模糊C均值聚類算法是基于模糊理論的1種軟分類算法，這種算法并不是把每個(gè)樣本嚴(yán)格劃為某1個(gè)類，而是通過(guò)迭代計(jì)算使非相似性指標(biāo)的目標(biāo)函數(shù)達(dá)到最小[15]，得到此時(shí)每個(gè)樣本對(duì)于每個(gè)類的隸屬度，用于確定每個(gè)樣本的類屬.

設(shè)特征空間中的數(shù)據(jù)樣本集為X={x1，x2，x3，…，xn}∈RS，n代表樣本的數(shù)量.FCM算法的目標(biāo)函數(shù)是各個(gè)樣本到各個(gè)類的歐式距離的和(誤差的平方根)，用JFCM表示.

(4)

約束條件如下：

(5)

式中，m為模糊指數(shù)，當(dāng)m∈[1.5,2.5]時(shí)，聚類效果最好[16]，故本文取m=2；uij為樣本xj屬于第i類的隸屬度；c為聚類數(shù)目；dij為樣本xj到聚類中心ci的歐氏距離.

2.2 熵權(quán)法

考慮到各判別指標(biāo)在交叉口交通狀態(tài)判別體系中所占的比例不同，通過(guò)對(duì)各指標(biāo)設(shè)定不同權(quán)值來(lái)衡量對(duì)聚類結(jié)果的貢獻(xiàn)大小，因此，引入熵權(quán)法對(duì)各指標(biāo)的權(quán)重進(jìn)行計(jì)算.熵權(quán)法是通過(guò)指標(biāo)差異性大小確定權(quán)重，具有克服主觀賦權(quán)方法主觀性的優(yōu)勢(shì)，故計(jì)算各判別指標(biāo)權(quán)重的步驟如下：

1)數(shù)據(jù)標(biāo)準(zhǔn)化處理.若有n組數(shù)據(jù)，m個(gè)判別指標(biāo)，則構(gòu)建數(shù)據(jù)矩陣X=[xij]n×m(i=1,2,…,n;j=1,2,…,m)并利用公式(6)標(biāo)準(zhǔn)化處理.

(6)

式中min (xj)、max (xj)分別為第j項(xiàng)判別指標(biāo)的最小值、最大值.

2)計(jì)算第j項(xiàng)判別指標(biāo)的熵值ej：

(7)

3)計(jì)算第j項(xiàng)判別指標(biāo)的權(quán)重系數(shù)wj：

(8)

2.3 改進(jìn)的FCM聚類算法

改進(jìn)的FCM算法是將K-means算法、熵權(quán)法、FCM算法三者進(jìn)行結(jié)合來(lái)實(shí)現(xiàn)對(duì)傳統(tǒng)FCM算法的改進(jìn). 由于K-means算法具有收斂速度快的優(yōu)勢(shì)且得到的聚類中心與FCM算法得到的聚類中心較為相似，因此，利用K-means算法得到初始聚類中心，再利用熵權(quán)法計(jì)算各個(gè)指標(biāo)的權(quán)重，得到基于判別指標(biāo)加權(quán)的歐式距離度量方式，則加權(quán)的歐式距離表達(dá)式為

(9)

式中，ω=(ω1,ω2,…,ωt)，t為判別指標(biāo)的個(gè)數(shù)，本文t=3，ωk∈[0,1]為判別指標(biāo)的權(quán)值.

改進(jìn)的FCM算法中的目標(biāo)函數(shù)是利用上述的加權(quán)歐式距離來(lái)代替?zhèn)鹘y(tǒng)的歐式距離，用JEWFCM表示.

(10)

得到新的迭代解為：

(11)

(12)

改進(jìn)的FCM算法進(jìn)行交通狀態(tài)判別的流程圖見(jiàn)圖1.

圖1 改進(jìn)FCM算法的交通判別流程圖

2.4 算法評(píng)價(jià)指標(biāo)

為了驗(yàn)證聚類算法的有效性，本文采用劃分系數(shù)(PC)和劃分熵系數(shù)(PE)2個(gè)指標(biāo)對(duì)改進(jìn)前后的FCM算法的聚類效果進(jìn)行評(píng)價(jià).

1)劃分系數(shù)(PC)的值越大，說(shuō)明算法的判別效果越好，PC可按下式計(jì)算：

(13)

2)劃分熵系數(shù)(PE)的值越小，說(shuō)明算法的判別效果越好，PE可按下式計(jì)算：

(14)

3 案例分析

3.1 交通數(shù)據(jù)采集

選取濟(jì)南市某交叉口為研究對(duì)象，對(duì)該交叉口的交通狀態(tài)進(jìn)行判別應(yīng)用. 據(jù)調(diào)查可知，該交叉口是信號(hào)控制交叉口，其配時(shí)方案見(jiàn)表1.

表1 信號(hào)配時(shí)方案

為了更全面地獲取交叉口各個(gè)交通狀態(tài)下的指標(biāo)數(shù)據(jù)，本文利用實(shí)際獲得交叉口的信號(hào)配時(shí)方案以及渠化信息，借助 VISSIM軟件進(jìn)行仿真模擬. VISSIM仿真軟件獲取指標(biāo)數(shù)據(jù)簡(jiǎn)單，并且該軟件能很好地表征交叉口的實(shí)際運(yùn)行情況，因此，利用VISSIM仿真軟件獲取指標(biāo)數(shù)據(jù)是可靠的，可將仿真數(shù)據(jù)用于對(duì)聚類算法的驗(yàn)證分析.

在仿真的過(guò)程中，通過(guò)對(duì)各進(jìn)口道輸入不同的流量數(shù)據(jù)來(lái)采集不同交通狀態(tài)下各判別指標(biāo)的數(shù)據(jù)，以5 min為時(shí)間間隔輸出1組數(shù)據(jù)，共150組，通過(guò)對(duì)仿真數(shù)據(jù)整理計(jì)算得到每組數(shù)據(jù)包括交叉口交通狀態(tài)劃分的3個(gè)指標(biāo)參數(shù)，依次為飽和度、平均延誤、平均排隊(duì)長(zhǎng)度.

在仿真數(shù)據(jù)預(yù)處理的過(guò)程中需要依據(jù)熵權(quán)法計(jì)算交叉口各判別指標(biāo)的權(quán)重，再利用改進(jìn)前后的FCM算法得到交叉口交通狀態(tài)的劃分結(jié)果. 而數(shù)據(jù)的標(biāo)準(zhǔn)化處理是熵權(quán)法中的必要的步驟，其可提高FCM算法的準(zhǔn)確性. 因此，在數(shù)據(jù)預(yù)處理時(shí)，首先將150組數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理，再利用熵權(quán)法計(jì)算出各判別指標(biāo)的權(quán)重向量集，計(jì)算結(jié)果見(jiàn)表2.

表2 基于熵權(quán)法的各判別指標(biāo)權(quán)重值

由表2可知，交叉口交通狀態(tài)的判別指標(biāo)的權(quán)重向量集為ω=[ω1,ω2,ω3]=[0.265 7,0.340 4,0.393 9].

3.2 改進(jìn)的FCM算法與FCM算法的聚類結(jié)果

改進(jìn)前后的FCM算法進(jìn)行聚類時(shí)，需要確定算法的參數(shù)：c=3，ε=1×10-3，m=2，Tmax=100.使用Python編程軟件將交叉口150組的仿真數(shù)據(jù)分別通過(guò)2種聚類算法進(jìn)行迭代計(jì)算，得到以下聚類結(jié)果：

1)FCM聚類算法聚類中心：

2)利用K-means算法得到初始聚類中心：

然后將權(quán)重向量集ω=[0.265 7,0.340 4，0.393 9]和初始聚類中心帶入改進(jìn)的FCM算法進(jìn)行循環(huán)迭代計(jì)算，得到最終的聚類中心：

聚類中心矩陣的列表示各個(gè)判別指標(biāo)在3種交通狀態(tài)下的值，從左到右依次是飽和度、平均延誤、平均排隊(duì)長(zhǎng)度；行表示每種交通狀態(tài)下的3個(gè)指標(biāo)值，從上到下依次是暢通、緩行、擁堵. 改進(jìn)后的FCM算法采用是隸屬度最大原則對(duì)交通狀態(tài)進(jìn)行劃分，即每組數(shù)據(jù)對(duì)于每一類都會(huì)產(chǎn)生所對(duì)應(yīng)的隸屬度，其中哪一類的隸屬度最大，則這組數(shù)據(jù)就屬于哪一類，將樣本的類別用不同顏色表示，紅色、藍(lán)色、綠色分別代表順暢、緩行、擁堵3種狀態(tài)，得到聚類結(jié)果空間分布見(jiàn)圖2.

圖2 改進(jìn)的FCM算法聚類結(jié)果空間分布圖

3.3 結(jié)果對(duì)比與分析

3.3.1 排隊(duì)長(zhǎng)度與迭代次數(shù)

對(duì)于聚類算法而言，目標(biāo)函數(shù)值是用來(lái)衡量聚類中心能否準(zhǔn)確的表示各分類中心，即目標(biāo)函數(shù)越小，越能說(shuō)明聚類中心能代表各分類中心，將改進(jìn)前后的FCM算法進(jìn)行多次運(yùn)行，得到2種算法的樣本目標(biāo)函數(shù)值和迭代次數(shù)的結(jié)果見(jiàn)圖3.

圖3 改進(jìn)前后FCM算法目標(biāo)函數(shù)的對(duì)比

由圖3可知，首次迭代時(shí)，改進(jìn)的FCM算法的目標(biāo)函數(shù)值約為10 076，F(xiàn)CM算法的目標(biāo)函數(shù)值約為170 771，可得出改進(jìn)的FCM算法的目標(biāo)函數(shù)值遠(yuǎn)小于FCM算法的目標(biāo)函數(shù)值，說(shuō)明改進(jìn)的FCM算法的初始搜尋目標(biāo)優(yōu)于FCM算法. 在迭代過(guò)程中，隨著迭代次數(shù)的增加，2種聚類算法的目標(biāo)函數(shù)值都呈現(xiàn)出逐漸下降的趨勢(shì). 當(dāng)?shù)Y(jié)束時(shí)， FCM算法迭代了21次，目標(biāo)函數(shù)值為41 849，而改進(jìn)的FCM算法迭代了15次，目標(biāo)函數(shù)值為10 049. 由上述可知，迭代次數(shù)由傳統(tǒng)的FCM算法的21次降為15次，減少了28.6%，說(shuō)明改進(jìn)的FCM算法收斂速度更快；目標(biāo)函數(shù)值由41 849降為10 049，降低了76.0%，且多次運(yùn)行時(shí)改進(jìn)的FCM的目標(biāo)函數(shù)值趨于穩(wěn)定，說(shuō)明改進(jìn)的FCM算法的穩(wěn)定性更好. 綜上所述，改進(jìn)的FCM算法更適用于交叉口交通狀態(tài)的判別.

3.3.2 算法有效性指標(biāo)對(duì)比

利用PC和PE 2種有效性指標(biāo)對(duì)改進(jìn)前后的FCM算法進(jìn)行評(píng)價(jià)，得到的計(jì)算結(jié)果見(jiàn)表3.

表3 改進(jìn)前后FCM算法的有效性指標(biāo)

從表3可知，對(duì)于PC和PE 2個(gè)評(píng)價(jià)指標(biāo)，改進(jìn)的FCM算法都比傳統(tǒng)的FCM算法更優(yōu)，說(shuō)明改進(jìn)的FCM算法聚類效果更好，更適用于處理大量的交通數(shù)據(jù).

4 結(jié)束語(yǔ)

針對(duì)傳統(tǒng)FCM算法判別交通狀態(tài)時(shí)所存在的問(wèn)題，本文提出將K-means算法、熵權(quán)法、FCM算法進(jìn)行結(jié)合實(shí)現(xiàn)對(duì)傳統(tǒng)的FCM算法的改進(jìn). 以獲取簡(jiǎn)單且反應(yīng)敏感的原則選取飽和度、平均延誤、平均排隊(duì)長(zhǎng)度為判別指標(biāo)，再利用改進(jìn)前后的FCM算法對(duì)仿真數(shù)據(jù)進(jìn)行聚類分析，以隸屬度的大小作為交通狀態(tài)判別的依據(jù). 實(shí)例分析表明：本文所提的改進(jìn)FCM算法相較傳統(tǒng)的FCM算法，目標(biāo)函數(shù)值降低了76.0%，迭代次數(shù)減少了28.6%，PC和PE 2個(gè)指標(biāo)的評(píng)價(jià)結(jié)果更優(yōu)，驗(yàn)證了改進(jìn)的FCM算法的收斂速度更快、聚類性能更好，并且對(duì)城市道路交叉口交通狀態(tài)劃分的準(zhǔn)確性更高. 此外，未來(lái)可在本研究的基礎(chǔ)上開(kāi)展對(duì)交叉口控制策略及信號(hào)配時(shí)優(yōu)化的研究.