基于信息熵加權的FCM交通狀態識別研究

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

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

0 引 言

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

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

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

1 交通狀態識別與FCM算法

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

圖1 交通狀態識別流程圖

1.1 識別單元的建立與狀態劃分

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

圖2 交通狀態判別的研究區域

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

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

表1 交通狀態識別指標閾值

1.2 FCM聚類算法

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

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

(1)

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

(2)

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

(3)

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

(4)

3) 更新模糊偽劃分。

(5)

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

2 改進方法

2.1 信息熵加權

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

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

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

(6)

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

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

(7)

3) 計算熵值。交通狀態類別關于各個屬性指標j的熵值為：

(8)

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

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

(9)

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

(10)

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

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

(11)

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

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

2.2 加權的FCM聚類算法

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

(12)

(13)

本文通過信息熵理論對交通狀態指標進行權重的計算，并采用加權的歐氏距離來優化FCM聚類算法的目標函數，最后，通過改進算法對城市路網的交通數據進行聚類仿真。具體實現步驟如下：

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

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

3 實驗與分析

3.1 實驗數據采集

為了驗證改進后FCM算法的有效性，選擇城市局部路網的實測數據進行交通狀態識別仿真，路網如圖3所示。

圖3 路網結構圖

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

3.2 改進前后聚類結果的比較

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

1) 傳統FCM算法的聚類中心矩陣：

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

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

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

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

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

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

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

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

圖5 改進前后算法的目標函數

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

3.3 改進前后識別率的比較

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

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

圖6 實際狀態與改進前后識別狀態

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

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

表2 聚類結果分析

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

4 結 語

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