曹 潔 張麗君 侯 亮 陳作漢 張 紅

1(蘭州理工大學(xué)計(jì)算機(jī)與通信學(xué)院 甘肅 蘭州 730050)2(甘肅省制造業(yè)信息化工程研究中心 甘肅 蘭州 730050)

0 引 言

如何準(zhǔn)確地對(duì)城市路網(wǎng)的交通狀態(tài)進(jìn)行識(shí)別是智能交通(ITS)的重要研究?jī)?nèi)容之一[1]。該內(nèi)容在出行者信息系統(tǒng)(TIS)和交通管理系統(tǒng)(TMS)等ITS子系統(tǒng)中應(yīng)用較廣泛[2]。通過(guò)對(duì)路網(wǎng)交通狀態(tài)的識(shí)別，可以從全局角度實(shí)時(shí)反映交通流總體運(yùn)行狀態(tài)，對(duì)交通控制和交通誘導(dǎo)起著先導(dǎo)作用。

由于交通狀態(tài)的特性是具有模糊性和不確定性[3]，通?？墒褂靡恍┙煌〝?shù)據(jù)對(duì)其變化情況進(jìn)行定量的說(shuō)明及反饋。而聚類分析作為一種無(wú)監(jiān)督機(jī)器學(xué)習(xí)算法，能夠在沒(méi)有任何先驗(yàn)知識(shí)的情況下實(shí)現(xiàn)交通流數(shù)據(jù)的模式分類[4]。因此，該算法在交通狀態(tài)識(shí)別領(lǐng)域中受到廣泛應(yīng)用。文獻(xiàn)[5]在感應(yīng)線圈所采集到的交通數(shù)據(jù)基礎(chǔ)上，提出一種基于模糊聚類的交通狀態(tài)判別算法及評(píng)價(jià)方法；文獻(xiàn)[6]結(jié)合高速公路擁堵的特點(diǎn)，建立了基于FCM粗糙集的城市高速公路交通狀態(tài)識(shí)別模型。以上方法雖然能夠快速識(shí)別高速路段和城市路段的交通狀態(tài)，但對(duì)交通流在交叉口處的間斷性與復(fù)雜性考慮得不夠全面。文獻(xiàn)[7]通過(guò)分析交通流的特征并對(duì)交通狀態(tài)進(jìn)行劃分，提出一種基于FCM聚類算法實(shí)時(shí)識(shí)別交通狀態(tài)的方法；文獻(xiàn)[8]基于大數(shù)據(jù)驅(qū)動(dòng)技術(shù)并結(jié)合FCM聚類算法構(gòu)建了一種交通狀態(tài)聚類模型。以上方法雖然實(shí)現(xiàn)了交通狀態(tài)的快速識(shí)別，但對(duì)評(píng)價(jià)指標(biāo)在交通狀態(tài)識(shí)別結(jié)果中的權(quán)重影響問(wèn)題考慮得不夠全面。文獻(xiàn)[9]將交通流的3個(gè)參數(shù)(流量、速度、占有率)作為樣本數(shù)據(jù)的評(píng)價(jià)指標(biāo)，提出基于FCM聚類算法的交通狀態(tài)實(shí)時(shí)判別方法；文獻(xiàn)[10]在FCM聚類算法的基礎(chǔ)上，通過(guò)設(shè)定交通評(píng)價(jià)指標(biāo)的權(quán)重，提出基于不同參數(shù)權(quán)重的交通狀態(tài)識(shí)別方法。以上方法雖然根據(jù)評(píng)價(jià)指標(biāo)的權(quán)重對(duì)交通狀態(tài)進(jìn)行了識(shí)別，但對(duì)評(píng)價(jià)指標(biāo)權(quán)重的確定具有一定的主觀性，影響到最終的識(shí)別結(jié)果。

針對(duì)以上問(wèn)題，本文將路網(wǎng)中關(guān)鍵交叉口和其上游路段作為一個(gè)交通狀態(tài)識(shí)別單元，引入概率論中的信息熵確定每個(gè)評(píng)價(jià)指標(biāo)的權(quán)重，提出基于信息熵加權(quán)的FCM聚類交通狀態(tài)識(shí)別方法。利用理論分析與實(shí)驗(yàn)仿真驗(yàn)證本文所提出方法的有效性。

1 交通狀態(tài)識(shí)別與FCM算法

交通狀態(tài)識(shí)別是解決交通擁堵問(wèn)題的首要任務(wù)。其步驟如下：首先，選取路網(wǎng)中關(guān)鍵交叉口和其上游路段作為交通狀態(tài)識(shí)別單元并采集該識(shí)別單元的交通數(shù)據(jù)；其次，根據(jù)不同交通狀態(tài)的交通評(píng)價(jià)指標(biāo)閾值不同，利用信息熵對(duì)選取的評(píng)價(jià)指標(biāo)進(jìn)行權(quán)重計(jì)算，以解決評(píng)價(jià)指標(biāo)對(duì)交通狀態(tài)影響程度不同的問(wèn)題；最后，利用改進(jìn)FCM算法對(duì)采集的交通數(shù)據(jù)進(jìn)行仿真，輸出交通狀態(tài)的聚類結(jié)果。整個(gè)流程如圖1所示。

圖1 交通狀態(tài)識(shí)別流程圖

1.1 識(shí)別單元的建立與狀態(tài)劃分

傳統(tǒng)交通狀態(tài)的識(shí)別單元是單一交叉口或單一路段，但在城市路網(wǎng)中由于交叉口的交通供給不足，會(huì)影響到上游路段的通行能力[11]。因此，為了有效地度量路網(wǎng)的交通狀態(tài)，本文將路網(wǎng)中關(guān)鍵交叉口和其上游路段作為交通狀態(tài)識(shí)別的單元，如圖2所示。

圖2 交通狀態(tài)判別的研究區(qū)域

交叉口的不同交通狀態(tài)會(huì)引起車輛的排隊(duì)長(zhǎng)度不同[12]，具體表現(xiàn)為：當(dāng)交叉口暢通時(shí)，車輛可能需要一個(gè)綠燈時(shí)間通過(guò)交叉口，此時(shí)排隊(duì)長(zhǎng)度為該時(shí)間內(nèi)通過(guò)的車輛數(shù)；當(dāng)交叉口嚴(yán)重?fù)矶聲r(shí)，車輛可能需要兩個(gè)或兩個(gè)以上的綠燈時(shí)間通過(guò)交叉口，此時(shí)排隊(duì)長(zhǎng)度為多個(gè)綠燈時(shí)間通過(guò)的車輛數(shù)。因此，本文選取交叉口評(píng)價(jià)指標(biāo)(飽和度、排隊(duì)長(zhǎng)度)和其上游路段評(píng)價(jià)指標(biāo)(平均行程速度、時(shí)間占有率)來(lái)進(jìn)行交通狀態(tài)的準(zhǔn)確識(shí)別。

為了確定以上4種交通狀態(tài)識(shí)別指標(biāo)的閾值，本文將《交通工程學(xué)》、《城市道路交通管理評(píng)價(jià)指標(biāo)體系》與國(guó)內(nèi)城市交通狀態(tài)的研究相結(jié)合，得出的結(jié)果如表1所示。

表1 交通狀態(tài)識(shí)別指標(biāo)閾值

1.2 FCM聚類算法

模糊C均值FCM(Fuzzy C-means)的原理是將聚類定義為一個(gè)約束的非線性規(guī)劃問(wèn)題，并通過(guò)不斷迭代優(yōu)化使其目標(biāo)函數(shù)取得最小值，實(shí)現(xiàn)樣本數(shù)據(jù)集的劃分和聚類[13]。

假定一個(gè)數(shù)據(jù)樣本集為X={x1,x2,…,xn}，每個(gè)樣本xi有m個(gè)評(píng)價(jià)指標(biāo)，即xi={xi1,xi2,…,xim}。其中，樣本集X的一個(gè)子集為模糊簇集V1,V2,…,Vc。FCM的目標(biāo)函數(shù)為：

(1)

式中：各個(gè)數(shù)據(jù)樣本與相應(yīng)聚類中心隸屬度構(gòu)成的隸屬度矩陣為U；聚類中心矩陣為V；樣本數(shù)據(jù)矩陣為X；第j個(gè)數(shù)據(jù)樣本的第i個(gè)聚類中心隸屬度為uij；q是一個(gè)隸屬度的因子，表示屬于樣本的輕緩程度；第i個(gè)聚類中心到第j個(gè)數(shù)據(jù)樣本的歐式距離為dij，定義如下：

(2)

1) 隨機(jī)初始化uij。隨機(jī)地選取q值，同時(shí)對(duì)于每個(gè)點(diǎn)xi和每個(gè)簇Vj，隸屬度uij取0和1之間的值。為了形成合理的模糊偽劃分，uij滿足約束條件：

(3)

2) 計(jì)算質(zhì)心。對(duì)于簇Vj，對(duì)應(yīng)的質(zhì)心vj由下式定義：

(4)

3) 更新模糊偽劃分。

(5)

FCM算法不斷重復(fù)地計(jì)算每個(gè)簇的質(zhì)心和模糊偽劃分，直到劃分達(dá)到穩(wěn)定狀態(tài)(迭代終止條件為“所有uij變化的絕對(duì)值低于指定的閾值”)。

2 改進(jìn)方法

2.1 信息熵加權(quán)

在傳統(tǒng)交通狀態(tài)的識(shí)別方法中，將不同評(píng)價(jià)指標(biāo)的權(quán)重視為相等或主觀確定其大小，從而影響到識(shí)別的準(zhǔn)確性。為了解決該問(wèn)題，本文引入概率論中的信息熵來(lái)確定不同交通評(píng)價(jià)指標(biāo)的權(quán)重。

信息熵的實(shí)質(zhì)是對(duì)系統(tǒng)無(wú)序程度的一種度量方式[14]，其度量準(zhǔn)則為：信息熵越大，系統(tǒng)的無(wú)序程度越高，提供的信息就越少[15]。從信息論與交通狀態(tài)相結(jié)合的角度來(lái)看，各個(gè)評(píng)價(jià)指標(biāo)權(quán)重的熵值并不是為了評(píng)價(jià)該指標(biāo)的實(shí)際熵值(信息量)大小，而是體現(xiàn)其在交通狀態(tài)識(shí)別中提供有用信息的多少，反映每個(gè)評(píng)價(jià)指標(biāo)的相對(duì)重要性?；诖?本文計(jì)算交通評(píng)價(jià)指標(biāo)權(quán)重的過(guò)程如下：

1) 通過(guò)評(píng)價(jià)指標(biāo)的閾值表，建立交通狀態(tài)識(shí)別系統(tǒng)的評(píng)價(jià)矩陣：

(6)

式中：需要識(shí)別的交通狀態(tài)有c(c=4)種類別，m(m=4)個(gè)交通評(píng)價(jià)指標(biāo)，xij為第i類交通狀態(tài)的第j個(gè)交通評(píng)價(jià)指標(biāo)的閾值。

2) 對(duì)評(píng)價(jià)矩陣X進(jìn)行歸一化處理。為了解決交通指標(biāo)量綱不同的問(wèn)題，用以下公式對(duì)矩陣X進(jìn)行歸一化處理：

(7)

3) 計(jì)算熵值。交通狀態(tài)類別關(guān)于各個(gè)屬性指標(biāo)j的熵值為：

(8)

4) 計(jì)算評(píng)價(jià)指標(biāo)的偏差度。第dj=1-Ej,j=1,2,…,m個(gè)交通評(píng)價(jià)指標(biāo)的偏差度為：

dj=1-Ejj=1,2,…,m

(9)

5) 計(jì)算每個(gè)交通評(píng)價(jià)指標(biāo)的權(quán)重大小。用熵測(cè)度來(lái)表示第j個(gè)指標(biāo)的權(quán)重系數(shù)為：

(10)

式中：第j個(gè)交通評(píng)價(jià)指標(biāo)rij(j=1,2,…,m)值的分布情況可以衡量該指標(biāo)對(duì)交通狀態(tài)的影響程度。其衡量準(zhǔn)則為：rij值分布越分散，相應(yīng)的dj值越大，該指標(biāo)對(duì)交通狀態(tài)的影響程度越高；相反，rij值分布越集中，相應(yīng)的dj值越小，該評(píng)價(jià)指標(biāo)對(duì)交通狀態(tài)的影響程度越低。

6) 確定分類樣本的特性指標(biāo)矩陣。設(shè)有n個(gè)交通狀態(tài)識(shí)別單元，樣本集為X={x1,x2,…,xn}，每個(gè)xi有m個(gè)評(píng)價(jià)指標(biāo)，利用信息熵確定每個(gè)特性指標(biāo)的權(quán)重大小，即n個(gè)待分類樣本的特性指標(biāo)矩陣為：

(11)

當(dāng)交通特性指標(biāo)選取m(m=4)時(shí)，上述矩陣的列分別是飽和度、平均排隊(duì)長(zhǎng)度，平均行程速度和時(shí)間占有率；矩陣的行代表識(shí)別單元樣本。

通過(guò)信息熵理論對(duì)表1中交通狀態(tài)評(píng)價(jià)指標(biāo)的權(quán)重進(jìn)行計(jì)算，得出以上4個(gè)評(píng)價(jià)指標(biāo)的權(quán)重向量為W={w1,w2,w3,w4}={0.128 4,0.301 8,0.188 4,0.381 4}。

2.2 加權(quán)的FCM聚類算法

引入信息熵確定出各個(gè)指標(biāo)的權(quán)重后，通過(guò)計(jì)算誤差的平方和來(lái)確定每個(gè)樣本數(shù)據(jù)和類中心間距最小的隸屬度矩陣以及c個(gè)聚類中心，改進(jìn)的FCM算法的目標(biāo)函數(shù)定義如下：

(12)

(13)

本文通過(guò)信息熵理論對(duì)交通狀態(tài)指標(biāo)進(jìn)行權(quán)重的計(jì)算，并采用加權(quán)的歐氏距離來(lái)優(yōu)化FCM聚類算法的目標(biāo)函數(shù)，最后，通過(guò)改進(jìn)算法對(duì)城市路網(wǎng)的交通數(shù)據(jù)進(jìn)行聚類仿真。具體實(shí)現(xiàn)步驟如下：

Step2根據(jù)交通數(shù)據(jù)的性質(zhì)，對(duì)模糊參數(shù)q和迭代停止閾值ε進(jìn)行設(shè)置；

Step5當(dāng)‖V(l+1)-V(l)‖≤ε時(shí)，則算法終止。此時(shí)，V*=V(l+1)為最終所求聚類中心；否則，令l=l+1，返回Step3繼續(xù)迭代。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)采集

為了驗(yàn)證改進(jìn)后FCM算法的有效性，選擇城市局部路網(wǎng)的實(shí)測(cè)數(shù)據(jù)進(jìn)行交通狀態(tài)識(shí)別仿真，路網(wǎng)如圖3所示。

圖3 路網(wǎng)結(jié)構(gòu)圖

將路網(wǎng)中關(guān)鍵交叉口A3和其上游路段作為交通狀態(tài)的識(shí)別單元，對(duì)其進(jìn)行數(shù)據(jù)采集。數(shù)據(jù)采集時(shí)間為工作日上午6:00-11:45(70組/天，共350組)，時(shí)間間隔為5 min，每組數(shù)據(jù)樣本包括狀態(tài)識(shí)別單元的4個(gè)評(píng)價(jià)指標(biāo)(飽和度、平均排隊(duì)長(zhǎng)度、平均行程速度和時(shí)間占有率)。通過(guò)MATLAB平臺(tái)對(duì)采集的交通樣本數(shù)據(jù)進(jìn)行暢通、穩(wěn)定、一般擁堵和嚴(yán)重?fù)矶滤姆N狀態(tài)的聚類仿真。根據(jù)樣本數(shù)據(jù)的性質(zhì)，本文選取模糊指數(shù)q=2.25[16]，迭代終止閾值ε為0.01。

3.2 改進(jìn)前后聚類結(jié)果的比較

實(shí)驗(yàn)選取其中一個(gè)工作日的70組交通數(shù)據(jù)，分別輸入到改進(jìn)前后的FCM聚類算法中，得出4種交通狀態(tài)的聚類中心矩陣。

1) 傳統(tǒng)FCM算法的聚類中心矩陣：

2) 加權(quán)后FCM算法的聚類中心矩陣：

上述聚類中心矩陣中，列表示一類交通狀態(tài)的4個(gè)評(píng)價(jià)指標(biāo)，行表示一個(gè)評(píng)價(jià)指標(biāo)在4種交通狀態(tài)下的值，且矩陣元素與交通狀態(tài)參數(shù)的閾值相符合。

通過(guò)對(duì)路網(wǎng)采集的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)仿真，得到改進(jìn)前后算法的隸屬度函數(shù)如圖4所示。

(a) 改進(jìn)前算法的隸屬度函數(shù)

(b) 改進(jìn)后算法的隸屬度函數(shù)圖4 改進(jìn)前后算法的隸屬度函數(shù)

由圖4可知：(1) 改進(jìn)后算法的隸屬度函數(shù)在四類交通狀態(tài)的曲線較改進(jìn)前更加平滑；(2) 改進(jìn)后算法的隸屬度函數(shù)在四類交通狀態(tài)的值較改進(jìn)前接近于1的樣本數(shù)有所增多。實(shí)驗(yàn)結(jié)果表明：基于信息熵加權(quán)改進(jìn)的FCM算法聚類效果更佳，分類性能提高。

FCM算法的目標(biāo)函數(shù)由相應(yīng)樣本的隸屬度值與該樣本到各個(gè)交通狀態(tài)聚類中心的距離相乘組成的。衡量算法聚類中心能否準(zhǔn)確表示各個(gè)交通狀態(tài)中心的指標(biāo)是算法產(chǎn)生的目標(biāo)函數(shù)。其衡量準(zhǔn)則為：聚類產(chǎn)生的目標(biāo)函數(shù)值越小，聚類中心越能更好地代表各個(gè)交通狀態(tài)的中心。

通過(guò)對(duì)路網(wǎng)采集的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)仿真，得到改進(jìn)前后算法的目標(biāo)函數(shù)如圖5所示。

圖5 改進(jìn)前后算法的目標(biāo)函數(shù)

由圖5可知，在第一次迭代時(shí)，改進(jìn)后算法的目標(biāo)函數(shù)值(約630)遠(yuǎn)遠(yuǎn)小于改進(jìn)前算法的目標(biāo)函數(shù)值(1 000)。在迭代過(guò)程中，兩種算法的目標(biāo)函數(shù)都在持續(xù)減小，但改進(jìn)后算法達(dá)到目標(biāo)函數(shù)最小值的迭代次數(shù)(10次)小于改進(jìn)前算法達(dá)到目標(biāo)函數(shù)最小值的迭代次數(shù)(15次)。迭代完成時(shí)，改進(jìn)后算法目標(biāo)函數(shù)的最小值(約100)小于改進(jìn)前算法目標(biāo)函數(shù)的最小值(約160)，降低了約37.5%。實(shí)驗(yàn)結(jié)果表明：基于信息熵加權(quán)改進(jìn)的算法以更少的迭代次數(shù)達(dá)到更小的目標(biāo)函數(shù)值，改進(jìn)算法的效率和性能有所提高。

3.3 改進(jìn)前后識(shí)別率的比較

本文所選取路網(wǎng)的關(guān)鍵交叉口靠近公交車站且車流量較大，根據(jù)視頻檢測(cè)器中對(duì)交通狀態(tài)的判斷，得出該工作日在采集時(shí)間段內(nèi)的實(shí)際路網(wǎng)交通狀態(tài)為：暢通(6:00-7:05)，穩(wěn)定狀態(tài)(7:05-7:25)，一般擁堵?tīng)顟B(tài)(7:25-8:00)，嚴(yán)重?fù)矶聽(tīng)顟B(tài)(8:00-9:40)，一般擁堵?tīng)顟B(tài)(9:40-10:05)，穩(wěn)定狀態(tài)(10:05-11:00)，一般擁堵?tīng)顟B(tài)(11:00-11:30)，嚴(yán)重?fù)矶聽(tīng)顟B(tài)(11:30-11:45)。

在交通狀態(tài)的隸屬度波形圖(圖4)中，將樣本隸屬度值最大所對(duì)應(yīng)的交通狀態(tài)定義為該樣本的交通狀態(tài)。通過(guò)對(duì)采集時(shí)間段內(nèi)路網(wǎng)的實(shí)際交通狀態(tài)與算法改進(jìn)前后識(shí)別的交通狀態(tài)進(jìn)行對(duì)比，得出如圖6所示的結(jié)果。其中，交通狀態(tài)的等級(jí)分別為1-暢通、2-穩(wěn)定、3-一般擁堵及4-嚴(yán)重?fù)矶隆?/p>

圖6 實(shí)際狀態(tài)與改進(jìn)前后識(shí)別狀態(tài)

由圖6可知，改進(jìn)前FCM聚類算法對(duì)交通狀態(tài)識(shí)別不準(zhǔn)確的時(shí)間段分別是8:25-9:45和9:50-10:05。改進(jìn)后FCM聚類算法對(duì)交通狀態(tài)識(shí)別不準(zhǔn)確的時(shí)間段是9:55-10:05。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后算法識(shí)別不準(zhǔn)確的時(shí)間段較少，更接近于實(shí)際的交通狀態(tài)。

為了進(jìn)一步明確改進(jìn)算法的識(shí)別率大小，將隸屬度值在0.5～1之間且符合實(shí)際交通狀態(tài)的數(shù)據(jù)樣本視為正確識(shí)別的樣本。表2是改進(jìn)前后算法對(duì)5個(gè)工作日采集的所有數(shù)據(jù)(350組)的聚類結(jié)果。

表2 聚類結(jié)果分析

由表2可知：文中采用信息熵理論對(duì)識(shí)別指標(biāo)進(jìn)行權(quán)重計(jì)算，相比于傳統(tǒng)FCM聚類算法，改進(jìn)后算法識(shí)別錯(cuò)誤的樣本總組數(shù)少于改進(jìn)前識(shí)別錯(cuò)誤的樣本組數(shù)，誤判率降低了7.14%。實(shí)驗(yàn)結(jié)果表明，文中改進(jìn)的聚類算法是有效的，避免了因主觀確定權(quán)重而造成識(shí)別不準(zhǔn)確的后果。

4 結(jié) 語(yǔ)

本文在傳統(tǒng)FCM聚類算法的基礎(chǔ)上，考慮到評(píng)價(jià)指標(biāo)對(duì)交通狀態(tài)的影響程度不同，采用信息熵理論計(jì)算交通狀態(tài)評(píng)判指標(biāo)的權(quán)重，提出了一種基于加權(quán)的FCM聚類算法的交通狀態(tài)識(shí)別方法。通過(guò)采集城市局部路網(wǎng)的交通數(shù)據(jù)，并用改進(jìn)前后的算法進(jìn)行仿真，實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的聚類算法能有效識(shí)別路網(wǎng)的交通狀態(tài)。但聚類中心個(gè)數(shù)的選取會(huì)影響到算法的性能，因此，下一步將致力于其個(gè)數(shù)的優(yōu)選研究。