基于改進(jìn)FCM聚類算法的高速公路交通狀態(tài)識(shí)別

余 慶，胡 堯,2

（1.貴州大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，貴州 貴陽(yáng) 550025；2.貴州省公共大數(shù)據(jù)重點(diǎn)實(shí)驗(yàn)室，貴州 貴陽(yáng) 550025）

0 引言

隨著經(jīng)濟(jì)的快速發(fā)展，我國(guó)汽車保有量不斷增加，交通擁堵問(wèn)題不斷加劇。交通狀態(tài)的分類識(shí)別能從整體上反映道路的交通狀況，有助于交通管理部門制定相應(yīng)的擁堵緩解措施或?yàn)槌鲂姓咄扑]合理的出行路線。同時(shí)，準(zhǔn)確的交通狀態(tài)識(shí)別和描述對(duì)于道路交通的智能化發(fā)展及解決道路交通擁堵、提高路網(wǎng)服務(wù)水平等至關(guān)重要，因此有必要對(duì)其進(jìn)行深入研究。

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

在用聚類分析法進(jìn)行交通狀態(tài)識(shí)別的過(guò)程中，不同分類指標(biāo)對(duì)聚類分析結(jié)果的影響程度不同，為提高交通狀態(tài)識(shí)別的有效性，研究人員探索對(duì)分類指標(biāo)進(jìn)行賦權(quán)[9-10]，如王宇俊等[11]對(duì)宏觀交通參數(shù)的權(quán)重分配進(jìn)行多次實(shí)驗(yàn)，并通過(guò)比較誤判率從中選取最優(yōu)的權(quán)重分配方案；于泉等[12]利用單一賦權(quán)法和組合賦權(quán)法確定交通狀態(tài)評(píng)價(jià)指標(biāo)的權(quán)重，并結(jié)合K-Means 算法與隸屬度函數(shù)，將城市交叉口的交通狀態(tài)劃分為暢通、輕微擁擠、擁擠、嚴(yán)重?fù)頂D4 種類別，結(jié)果表明組合賦權(quán)法的聚類結(jié)果比單一賦權(quán)法更精確、穩(wěn)定。

綜上，當(dāng)前交通狀態(tài)識(shí)別研究已取得一些比較有效的成果，但整體上存在以下不足：分類指標(biāo)偏于單一，對(duì)交通狀態(tài)的描述不夠全面、不夠準(zhǔn)確；缺乏關(guān)于不同樣本對(duì)交通狀態(tài)識(shí)別影響的分析。鑒于此，本文選用多個(gè)交通狀態(tài)分類指標(biāo)，利用熵權(quán)法確定分類指標(biāo)權(quán)重，同時(shí)結(jié)合樣本權(quán)重對(duì)FCM 算法進(jìn)行改進(jìn)，并以美國(guó)加州某高速公路交通數(shù)據(jù)為例對(duì)改進(jìn)FCM 算法的聚類效果和運(yùn)行效率進(jìn)行驗(yàn)證[13]。

1 交通狀態(tài)分類指標(biāo)

本文選取交通流量、空間占有率、平均速度和路網(wǎng)充裕度作為交通狀態(tài)分類指標(biāo)。交通流量、空間占有率、平均速度都是描述道路交通流的基本參數(shù)，是交通運(yùn)行效率評(píng)價(jià)、交通狀態(tài)判別、交通安全分析、交通事故鑒定等的重要指標(biāo)?？臻g占有率指所有車道在5min內(nèi)的平均占有率，取值區(qū)間為[0,1]。路網(wǎng)充裕度定義為路段i在t時(shí)刻的剩余交通流量與飽和交通流量的比值，描述路網(wǎng)資源在空間上的剩余程度，用來(lái)反映路網(wǎng)資源在空間上的可利用率，能為交通擁堵疏導(dǎo)提供依據(jù)[14]。路網(wǎng)充裕度可根據(jù)交通流實(shí)時(shí)數(shù)據(jù)計(jì)算得到[15]：

式（1）中：ρit為路段i在t時(shí)刻的路網(wǎng)充裕度；qimax為通過(guò)路段i的飽和交通流量；qit為路段i在t時(shí)刻的交通流量；qimax-qit為路段i在t時(shí)刻的剩余交通流量。

2 交通狀態(tài)識(shí)別算法

2.1 傳統(tǒng)FCM聚類算法

聚類分析是一種無(wú)監(jiān)督的分類方法[16]，能將沒(méi)有分類標(biāo)簽的數(shù)據(jù)集分為若干個(gè)簇。FCM 聚類算法是一種常用的聚類分析方法，主要用于將多維空間數(shù)據(jù)分為一定的類別，其基本思路是將聚類問(wèn)題轉(zhuǎn)化為數(shù)學(xué)問(wèn)題，然后利用樣本分類的相關(guān)方法求解。通常，樣本集X={x1,x2,…,xn}可按一定的準(zhǔn)則劃分為c個(gè)模糊集（其中c為預(yù)先給定的類別數(shù)），然后確定各類別的聚類中心，使目標(biāo)函數(shù)最小化。

交通狀態(tài)識(shí)別的FCM 聚類算法目標(biāo)函數(shù)計(jì)算公式[15]為：

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

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

式（4）中：vhm為第m個(gè)分類指標(biāo)在第h個(gè)交通狀態(tài)類別下的聚類中心。

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

聚類過(guò)程中，聚類中心周圍的樣本數(shù)據(jù)往往分布不均勻，各數(shù)據(jù)對(duì)聚類結(jié)果的貢獻(xiàn)可能存在較大差異，同時(shí)每個(gè)分類指標(biāo)對(duì)聚類的影響也有所不同。傳統(tǒng)的FCM 聚類方法將所有指標(biāo)和樣本對(duì)聚類結(jié)果的影響都視為同等重要，可能會(huì)導(dǎo)致算法無(wú)法取得較好的聚類效果。本文采用信息熵[17-18]對(duì)每個(gè)分類指標(biāo)賦予不同的權(quán)重，同時(shí)采用樣本加權(quán)的方法克服樣本分布不均勻?qū)垲惖挠绊?，從而加快聚類的收斂速度?/p>

2.2.1 熵權(quán)法

熵權(quán)法可以對(duì)樣本數(shù)據(jù)攜帶的信息進(jìn)行量化，通過(guò)引入權(quán)重使聚類結(jié)果更加客觀真實(shí)。應(yīng)用熵權(quán)法對(duì)分類指標(biāo)賦權(quán)時(shí)，指標(biāo)的熵權(quán)越大，說(shuō)明其對(duì)聚類結(jié)果的影響越大，反之對(duì)聚類結(jié)果的影響越小。熵權(quán)法的計(jì)算步驟如下。

（1）歸一化處理。為避免不同指標(biāo)之間的量綱不同，首先采用極差法對(duì)數(shù)據(jù)進(jìn)行歸一化處理[12]：

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

（2）計(jì)算熵值。利用歸一化處理所得數(shù)據(jù)，計(jì)算第m個(gè)分類指標(biāo)的熵值Em[12]：

（3）計(jì)算每個(gè)交通狀態(tài)分類指標(biāo)的權(quán)重大小。利用熵值確定第m個(gè)分類指標(biāo)的權(quán)重wm[12]：

2.2.2 樣本加權(quán)

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

式（9）中：ti為第i個(gè)樣本的權(quán)重；為改 進(jìn)FCM 算法中第i個(gè)樣本對(duì)第j個(gè)交通狀態(tài)類別的隸屬度；為第i個(gè)樣本與第j個(gè)類別中心的加權(quán)距離。

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

2.2.3 改進(jìn)FCM聚類算法的迭代解

將通過(guò)信息熵和樣本權(quán)重改進(jìn)后的FCM 算法的目標(biāo)函數(shù)定義為：

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

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

可見，改進(jìn)后的FCM 聚類算法綜合考慮了聚類過(guò)程中每個(gè)樣本點(diǎn)的不同貢獻(xiàn)和每個(gè)特征的不同重要性。

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

將改進(jìn)后的FCM 算法應(yīng)用于高速公路交通狀態(tài)識(shí)別，具體流程如圖1所示。

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

3 高速公路交通狀態(tài)識(shí)別

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

圖2 交通流量時(shí)序圖

圖3 空間占有率時(shí)序圖

圖4 平均速度時(shí)序圖

圖5 路網(wǎng)充裕度時(shí)序圖

根據(jù)文獻(xiàn)[8]中的分類級(jí)別，將高速公路道路交通狀態(tài)分為7個(gè)等級(jí)，即暢通、較暢通、平穩(wěn)、較平穩(wěn)、較擁擠、擁擠及阻塞。表1 列出了采集點(diǎn)VDS 311974 的聚類中心及各類交通狀態(tài)的樣本數(shù)?？梢钥闯?，就樣本數(shù)而言，屬于暢通的最多，其次是較擁擠和較平穩(wěn)，屬于阻塞的最少。

表1 FCM聚類中心（VDS 311974）

為驗(yàn)證改進(jìn)后FCM 算法的聚類效果，現(xiàn)用其進(jìn)行高速公路交通狀態(tài)識(shí)別。首先采用熵權(quán)法計(jì)算交通狀態(tài)分類指標(biāo)的權(quán)重。各分類指標(biāo)在不同數(shù)據(jù)集下的信息熵權(quán)重如表2 所示?？梢钥闯?，在不同數(shù)據(jù)集中，同一指標(biāo)對(duì)應(yīng)的熵權(quán)不同；3個(gè)數(shù)據(jù)集中，空間占有率的熵權(quán)最大，平均速度的熵權(quán)最小，這表明在本文所選數(shù)據(jù)中，空間占有率對(duì)聚類結(jié)果的影響最大，而平均速度對(duì)聚類結(jié)果的影響最小。

表2 分類指標(biāo)熵權(quán)值

接著，計(jì)算不同數(shù)據(jù)集的交通狀態(tài)分類樣本數(shù)及占比，如表3所示?？梢钥闯觯?個(gè)數(shù)據(jù)集中屬于暢通狀態(tài)的樣本數(shù)最多，占比分別為21.15%,21.25%和24.93%；其次是較擁擠狀態(tài)。此外，前兩個(gè)數(shù)據(jù)集中屬于阻塞狀態(tài)的樣本數(shù)最少，占比分別為5.94%和9.26%，而第3個(gè)數(shù)據(jù)集中屬于擁擠狀態(tài)的樣本數(shù)最少，占比為4.03%。這進(jìn)一步表明不同道路的劃分情況有所不同，應(yīng)根據(jù)道路的實(shí)際情況來(lái)劃分交通狀態(tài)等級(jí)。

表3 交通狀態(tài)分類樣本數(shù)及占比

最后，比較傳統(tǒng)FCM 算法與改進(jìn)后FCM 算法的目標(biāo)函數(shù)值、迭代次數(shù)及運(yùn)行時(shí)間，所得結(jié)果如表4 所示?？梢钥闯?，所有數(shù)據(jù)集中改進(jìn)FCM 算法的目標(biāo)函數(shù)值都明顯小于傳統(tǒng)FCM 算法的目標(biāo)函數(shù)值，3 個(gè)數(shù)據(jù)集的目標(biāo)函數(shù)值分別減小了75%,74.95%和75.38%，符合目標(biāo)函數(shù)值越小，聚類效果越好的思想。此外，所有數(shù)據(jù)集中改進(jìn)后的FCM 算法迭代次數(shù)更少，運(yùn)行時(shí)間更短?？梢?，改進(jìn)后的FCM 算法在聚類效果和運(yùn)行效率方面均優(yōu)于傳統(tǒng)FCM聚類算法。

表4 傳統(tǒng)FCM算法與改進(jìn)FCM算法結(jié)果比較

應(yīng)用改進(jìn)FCM 算法計(jì)算數(shù)據(jù)集在不同交通狀態(tài)下各分類指標(biāo)具體的取值范圍。數(shù)據(jù)采集點(diǎn)VDS 311974 的數(shù)據(jù)分布情況如表5 所示?？梢钥闯觯舨捎脝蝹€(gè)分類指標(biāo)來(lái)識(shí)別高速公路交通狀態(tài)，則不能為交通狀態(tài)的識(shí)別提供有效信息（如同樣的平均速度可能處于不同的交通狀態(tài)）；當(dāng)采用多個(gè)指標(biāo)劃分交通狀態(tài)時(shí)，同一指標(biāo)對(duì)應(yīng)不同交通狀態(tài)的取值范圍具有明顯差異。比較各交通狀態(tài)對(duì)應(yīng)的指標(biāo)取值范圍可以看出，暢通狀態(tài)和較暢通狀態(tài)對(duì)應(yīng)的交通流量和空間占有率較低，平均速度和路網(wǎng)充裕度較高；平穩(wěn)狀態(tài)和較平穩(wěn)狀態(tài)對(duì)應(yīng)的4 個(gè)指標(biāo)均處于中值；較擁擠狀態(tài)、擁擠狀態(tài)和阻塞狀態(tài)對(duì)應(yīng)的交通流量和空間占有率較高，平均速度和路網(wǎng)充裕度較低。此外，分析得出數(shù)據(jù)采集點(diǎn)VDS 319129的交通流量明顯低于另外兩個(gè)采集點(diǎn)，但改進(jìn)后的FCM 聚類法仍能清楚地劃分該數(shù)據(jù)集所對(duì)應(yīng)的交通狀態(tài)?？梢?，該算法在識(shí)別交通狀態(tài)時(shí)，能根據(jù)道路的實(shí)際情況調(diào)整聚類結(jié)果，從而更加準(zhǔn)確、全面地識(shí)別交通狀態(tài)。

表5 不同交通狀態(tài)下分類指標(biāo)的取值范圍（數(shù)據(jù)采集點(diǎn)VDS 311974）

4 結(jié)語(yǔ)

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