基于信息熵加權(quán)的FCM交通狀態(tài)識別研究

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

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

0 引 言

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

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

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

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

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

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

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

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

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

交叉口的不同交通狀態(tài)會引起車輛的排隊長度不同[12]，具體表現(xiàn)為：當交叉口暢通時，車輛可能需要一個綠燈時間通過交叉口，此時排隊長度為該時間內(nèi)通過的車輛數(shù)；當交叉口嚴重擁堵時，車輛可能需要兩個或兩個以上的綠燈時間通過交叉口，此時排隊長度為多個綠燈時間通過的車輛數(shù)。因此，本文選取交叉口評價指標(飽和度、排隊長度)和其上游路段評價指標(平均行程速度、時間占有率)來進行交通狀態(tài)的準確識別。

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

表1 交通狀態(tài)識別指標閾值

1.2 FCM聚類算法

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

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

(1)

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

(2)

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

(3)

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

(4)

3) 更新模糊偽劃分。

(5)

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

2 改進方法

2.1 信息熵加權(quán)

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

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

1) 通過評價指標的閾值表，建立交通狀態(tài)識別系統(tǒng)的評價矩陣：

(6)

式中：需要識別的交通狀態(tài)有c(c=4)種類別，m(m=4)個交通評價指標，xij為第i類交通狀態(tài)的第j個交通評價指標的閾值。

2) 對評價矩陣X進行歸一化處理。為了解決交通指標量綱不同的問題，用以下公式對矩陣X進行歸一化處理：

(7)

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

(8)

4) 計算評價指標的偏差度。第dj=1-Ej,j=1,2,…,m個交通評價指標的偏差度為：

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

(9)

5) 計算每個交通評價指標的權(quán)重大小。用熵測度來表示第j個指標的權(quán)重系數(shù)為：

(10)

式中：第j個交通評價指標rij(j=1,2,…,m)值的分布情況可以衡量該指標對交通狀態(tài)的影響程度。其衡量準則為：rij值分布越分散，相應的dj值越大，該指標對交通狀態(tài)的影響程度越高；相反，rij值分布越集中，相應的dj值越小，該評價指標對交通狀態(tài)的影響程度越低。

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

(11)

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

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

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

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

(12)

(13)

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

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

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

3 實驗與分析

3.1 實驗數(shù)據(jù)采集

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

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

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

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

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

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

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

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

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

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

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

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

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

通過對路網(wǎng)采集的數(shù)據(jù)集進行實驗仿真，得到改進前后算法的目標函數(shù)如圖5所示。

圖5 改進前后算法的目標函數(shù)

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

3.3 改進前后識別率的比較

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

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

圖6 實際狀態(tài)與改進前后識別狀態(tài)

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

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

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

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

4 結(jié) 語

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