基于改進FCM聚類算法的高速公路交通狀態識別

余 慶，胡 堯,2

（1.貴州大學數學與統計學院，貴州 貴陽 550025；2.貴州省公共大數據重點實驗室，貴州 貴陽 550025）

0 引言

隨著經濟的快速發展，我國汽車保有量不斷增加，交通擁堵問題不斷加劇。交通狀態的分類識別能從整體上反映道路的交通狀況，有助于交通管理部門制定相應的擁堵緩解措施或為出行者推薦合理的出行路線。同時，準確的交通狀態識別和描述對于道路交通的智能化發展及解決道路交通擁堵、提高路網服務水平等至關重要，因此有必要對其進行深入研究。

國內外學者主要基于交通參數[1-2]、圖像特征[3]、高空視頻[4]等對道路交通狀態進行識別。如Ricardo 等[5]結合道路間的空間相關性，基于K-均值（K-Means）聚類算法實現日常交通模式的識別；Bae 等[6]基于交通密度數據，采用Gaussian 混合模型識別高速公路交通狀態，并檢測交通相位的變化；郭海濤[3]基于交通區域特定的圖像特征來識別交通擁堵狀態；彭博等[4]基于三維卷積神經網絡——深度神經網絡方法，采用高空視頻數據對道路交通狀態進行識別和預測。由于交通狀態具有模糊性和不確定性，近年來模糊理論方法在交通狀態識別領域得到廣泛應用，如陳忠輝等[7]應用模糊C 均值（Fuzzy C-Means,FCM）聚類算法分析歷史交通流，并結合隨機森林算法預測短時交通狀態；陳釗正等[8]基于K-Means 算法和FCM 算法，給出適合高速公路特點的交通狀態劃分方法和關鍵參數。

在用聚類分析法進行交通狀態識別的過程中，不同分類指標對聚類分析結果的影響程度不同，為提高交通狀態識別的有效性，研究人員探索對分類指標進行賦權[9-10]，如王宇俊等[11]對宏觀交通參數的權重分配進行多次實驗，并通過比較誤判率從中選取最優的權重分配方案；于泉等[12]利用單一賦權法和組合賦權法確定交通狀態評價指標的權重，并結合K-Means 算法與隸屬度函數，將城市交叉口的交通狀態劃分為暢通、輕微擁擠、擁擠、嚴重擁擠4 種類別，結果表明組合賦權法的聚類結果比單一賦權法更精確、穩定。

綜上，當前交通狀態識別研究已取得一些比較有效的成果，但整體上存在以下不足：分類指標偏于單一，對交通狀態的描述不夠全面、不夠準確；缺乏關于不同樣本對交通狀態識別影響的分析。鑒于此，本文選用多個交通狀態分類指標，利用熵權法確定分類指標權重，同時結合樣本權重對FCM 算法進行改進，并以美國加州某高速公路交通數據為例對改進FCM 算法的聚類效果和運行效率進行驗證[13]。

1 交通狀態分類指標

本文選取交通流量、空間占有率、平均速度和路網充裕度作為交通狀態分類指標。交通流量、空間占有率、平均速度都是描述道路交通流的基本參數，是交通運行效率評價、交通狀態判別、交通安全分析、交通事故鑒定等的重要指標。空間占有率指所有車道在5min內的平均占有率，取值區間為[0,1]。路網充裕度定義為路段i在t時刻的剩余交通流量與飽和交通流量的比值，描述路網資源在空間上的剩余程度，用來反映路網資源在空間上的可利用率，能為交通擁堵疏導提供依據[14]。路網充裕度可根據交通流實時數據計算得到[15]：

式（1）中：ρit為路段i在t時刻的路網充裕度；qimax為通過路段i的飽和交通流量；qit為路段i在t時刻的交通流量；qimax-qit為路段i在t時刻的剩余交通流量。

2 交通狀態識別算法

2.1 傳統FCM聚類算法

聚類分析是一種無監督的分類方法[16]，能將沒有分類標簽的數據集分為若干個簇。FCM 聚類算法是一種常用的聚類分析方法，主要用于將多維空間數據分為一定的類別，其基本思路是將聚類問題轉化為數學問題，然后利用樣本分類的相關方法求解。通常，樣本集X={x1,x2,…,xn}可按一定的準則劃分為c個模糊集（其中c為預先給定的類別數），然后確定各類別的聚類中心，使目標函數最小化。

交通狀態識別的FCM 聚類算法目標函數計算公式[15]為：

式（2）～式（3）中：F(U,V)為目標函數；U為隸屬度矩陣；V為聚類中心矩陣；c為聚類數；n為樣本數；d為分類指標數；uij∈U為第i個樣本對第j個交通狀態類別的隸屬度；?為加權指數，表示模糊度；xim為第i個樣本在第m個分類指標下的取值；vjm∈V為第m個分類指標在第j個交通狀態類別下的聚類中心。

在目標函數中引入拉格朗日乘子，并求偏導，令其等于0，從而得到參數的迭代解[15]：

式（4）中：vhm為第m個分類指標在第h個交通狀態類別下的聚類中心。

2.2 改進的FCM聚類算法

聚類過程中，聚類中心周圍的樣本數據往往分布不均勻，各數據對聚類結果的貢獻可能存在較大差異，同時每個分類指標對聚類的影響也有所不同。傳統的FCM 聚類方法將所有指標和樣本對聚類結果的影響都視為同等重要，可能會導致算法無法取得較好的聚類效果。本文采用信息熵[17-18]對每個分類指標賦予不同的權重，同時采用樣本加權的方法克服樣本分布不均勻對聚類的影響，從而加快聚類的收斂速度。

2.2.1 熵權法

熵權法可以對樣本數據攜帶的信息進行量化，通過引入權重使聚類結果更加客觀真實。應用熵權法對分類指標賦權時，指標的熵權越大，說明其對聚類結果的影響越大，反之對聚類結果的影響越小。熵權法的計算步驟如下。

（1）歸一化處理。為避免不同指標之間的量綱不同，首先采用極差法對數據進行歸一化處理[12]：

式（6）中：yim為第i個樣本在第m個分類指標下的歸一化值；xi為第i個樣本。

（2）計算熵值。利用歸一化處理所得數據，計算第m個分類指標的熵值Em[12]：

（3）計算每個交通狀態分類指標的權重大小。利用熵值確定第m個分類指標的權重wm[12]：

2.2.2 樣本加權

為減小甚至消除噪聲和離群數據對聚類結果的影響，通常對這兩種數據賦予較小的權重。對于給出的數據樣本，其權重計算公式[18]為：

式（9）中：ti為第i個樣本的權重；為改 進FCM 算法中第i個樣本對第j個交通狀態類別的隸屬度；為第i個樣本與第j個類別中心的加權距離。

顯然，樣本權重的大小與樣本到各聚類中心的距離有關，故將樣本權重計算也納入算法迭代過程。不過其缺點是權重對聚類中心較敏感，聚類中心越精確，權重計算就越合理，如果聚類中心偏離真實中心，得到的樣本權重則會存在偏差。K-Means 聚類算法是一種經典的聚類算法，能簡單、快速地對數據進行類別劃分，故本文首先應用K-Means 聚類算法選取初始聚類中心，以避免樣本權重偏差。

2.2.3 改進FCM聚類算法的迭代解

將通過信息熵和樣本權重改進后的FCM 算法的目標函數定義為：

同樣可以得到隸屬度和聚類中心的迭代解，分別為：

式（10）～式（12）中：F′(U′,V′)為改進FCM 算法的目標函數；U′為改進FCM 算法的隸屬度矩陣；V′為改進FCM 算法的聚類中心矩陣；表示第i個樣本與第h個類別中心的加權距離；∈V′為改進FCM 算法中第m個分類指標在第j個交通狀態類別下的聚類中心；其他變量意義同前。

可見，改進后的FCM 聚類算法綜合考慮了聚類過程中每個樣本點的不同貢獻和每個特征的不同重要性。

2.3 交通狀態識別流程

將改進后的FCM 算法應用于高速公路交通狀態識別，具體流程如圖1所示。

圖1 交通狀態識別流程圖

3 高速公路交通狀態識別

為驗證改進FCM 算法的聚類效果，本文選取美國加州高速公路交通數據集[13]實現交通狀態識別。該數據為每30s 實時采集一次，由加州運輸局性能測量系統（Performance Measurement Sys?tem,PeMS）聚合成間隔為5min 的連續數據，包含交通流量、空間占有率、平均速度等監測數據，適用于交通數據分析與狀態識別及不同方法的比較。本文選取數據采集點VDS 311974,VDS 312139 及VDS 319129 的10 個工作日（2020年7月6日0:00—2020年7月10日23:55和2020年7月13日0:00—2020年7月17日23:55）的高速公路數據。對交通參數（包括每5min交通流量、空間占有率、平均速度和路網充裕度）進行可視化，如圖2～圖5所示，其中路網充裕度由式（1）計算得到。由圖可知，同一采集點的交通數據在一天內會發生多次變化且每日變化規律大致相同，其中交通流量和空間占有率曲線走勢相同，平均速度和路網充裕度曲線則朝相反方向變化。此外，VDS 311974 和VDS 312139 數據集在各分類指標下的變化范圍相差不大，而VDS 319129數據集的交通流量指標變化幅度較小，其最大流量僅為前兩個數據集的1/3。可見，不同采集點的交通數據可能表現出不同的變化規律，該數據適用于交通狀態分類識別。

圖2 交通流量時序圖

圖3 空間占有率時序圖

圖4 平均速度時序圖

圖5 路網充裕度時序圖

根據文獻[8]中的分類級別，將高速公路道路交通狀態分為7個等級，即暢通、較暢通、平穩、較平穩、較擁擠、擁擠及阻塞。表1 列出了采集點VDS 311974 的聚類中心及各類交通狀態的樣本數。可以看出，就樣本數而言，屬于暢通的最多，其次是較擁擠和較平穩，屬于阻塞的最少。

表1 FCM聚類中心（VDS 311974）

為驗證改進后FCM 算法的聚類效果，現用其進行高速公路交通狀態識別。首先采用熵權法計算交通狀態分類指標的權重。各分類指標在不同數據集下的信息熵權重如表2 所示。可以看出，在不同數據集中，同一指標對應的熵權不同；3個數據集中，空間占有率的熵權最大，平均速度的熵權最小，這表明在本文所選數據中，空間占有率對聚類結果的影響最大，而平均速度對聚類結果的影響最小。

表2 分類指標熵權值

接著，計算不同數據集的交通狀態分類樣本數及占比，如表3所示。可以看出，3個數據集中屬于暢通狀態的樣本數最多，占比分別為21.15%,21.25%和24.93%；其次是較擁擠狀態。此外，前兩個數據集中屬于阻塞狀態的樣本數最少，占比分別為5.94%和9.26%，而第3個數據集中屬于擁擠狀態的樣本數最少，占比為4.03%。這進一步表明不同道路的劃分情況有所不同，應根據道路的實際情況來劃分交通狀態等級。

表3 交通狀態分類樣本數及占比

最后，比較傳統FCM 算法與改進后FCM 算法的目標函數值、迭代次數及運行時間，所得結果如表4 所示。可以看出，所有數據集中改進FCM 算法的目標函數值都明顯小于傳統FCM 算法的目標函數值，3 個數據集的目標函數值分別減小了75%,74.95%和75.38%，符合目標函數值越小，聚類效果越好的思想。此外，所有數據集中改進后的FCM 算法迭代次數更少，運行時間更短。可見，改進后的FCM 算法在聚類效果和運行效率方面均優于傳統FCM聚類算法。

表4 傳統FCM算法與改進FCM算法結果比較

應用改進FCM 算法計算數據集在不同交通狀態下各分類指標具體的取值范圍。數據采集點VDS 311974 的數據分布情況如表5 所示。可以看出，若采用單個分類指標來識別高速公路交通狀態，則不能為交通狀態的識別提供有效信息（如同樣的平均速度可能處于不同的交通狀態）；當采用多個指標劃分交通狀態時，同一指標對應不同交通狀態的取值范圍具有明顯差異。比較各交通狀態對應的指標取值范圍可以看出，暢通狀態和較暢通狀態對應的交通流量和空間占有率較低，平均速度和路網充裕度較高；平穩狀態和較平穩狀態對應的4 個指標均處于中值；較擁擠狀態、擁擠狀態和阻塞狀態對應的交通流量和空間占有率較高，平均速度和路網充裕度較低。此外，分析得出數據采集點VDS 319129的交通流量明顯低于另外兩個采集點，但改進后的FCM 聚類法仍能清楚地劃分該數據集所對應的交通狀態。可見，該算法在識別交通狀態時，能根據道路的實際情況調整聚類結果，從而更加準確、全面地識別交通狀態。

表5 不同交通狀態下分類指標的取值范圍（數據采集點VDS 311974）

4 結語

本文針對傳統FCM 算法未考慮各指標重要性和各樣本貢獻度不同的缺陷，采用信息熵確定分類指標權重，同時對每個樣本賦予不同的加權系數，然后選用交通流量、空間占有率、平均速度和路網充裕度4 個分類指標來識別高速公路的交通狀態，并比較了傳統FCM 算法和改進FCM 算法的目標函數值、迭代次數及運行時間。結果表明：改進后的FCM 算法因綜合考慮了不同指標和樣本對聚類結果的影響，其聚類效果優于傳統FCM 算法，且迭代次數較少，運行時間更短。值得注意的是，本文僅針對高速公路交通數據進行狀態劃分，而城市道路情況更加復雜，因此未來還需考慮道路的實際情況來實現對城市道路交通狀態的高效識別。