基于ＦＦＣＭ聚類的城市交通擁堵判別研究

摘 要：對(duì)城市道路交通擁堵?tīng)顟B(tài)判別的問(wèn)題，提出了一種硬C均值(HCM)聚類與模糊C均值(FCM)聚類相結(jié)合的快速模糊C均值聚類(FFCM)算法。用硬聚類的結(jié)果對(duì)模糊聚類初始值的選取進(jìn)行指導(dǎo)，以加速算法的收斂過(guò)程。將該算法用于城市交通流數(shù)據(jù)的聚類分析結(jié)果表明，該算法能夠快速而有效地對(duì)城市交通流狀況進(jìn)行判別，為動(dòng)態(tài)交通擁堵預(yù)警和交通疏導(dǎo)策略的制定提供依據(jù)。

關(guān)鍵詞：城市交通； 快速模糊聚類； 擁堵判別

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：10013695(2008)09276803

Study of urban traffic congestion judgment based on FFCM clustering

YANG Zuyuan， HUANG Xiyue， DU Changhai， TANG Mingxia

(College of Automation， Chongqing University， Chongqing 400044， China)

Abstract:In order to solve the problem of urban traffic congestion judgment， a fast fuzzy Cmeans (FFCM) clustering method integrating hard Cmeans clustering method and fuzzy Cmeans clustering method was put forward. In this algorithm， the result of HCM clustering is the basis of the initial value of FFCM， which can speedup its convergence. Then it’s applied to a set of real traffic flow data. The clustering result shows that this method enjoy good performance in fast and effective distinguishing urban traffic congestion and will contribute to dynamic traffic congestion warning and traffic guidance.

Key words：urban traffic; fast fuzzy clustering; traffic congestion judgment

0 引言

交通擁堵已成為現(xiàn)代城市交通的嚴(yán)重問(wèn)題。旅行時(shí)間、旅行安全、環(huán)境質(zhì)量和生活質(zhì)量均受到了交通狀況的制約，各級(jí)交通管理部門都在積極尋求解決辦法。

智能交通系統(tǒng)被認(rèn)為是解決交通擁堵難題的有效途徑。在智能交通管理系統(tǒng)中，通常應(yīng)用各種交通狀態(tài)判別算法進(jìn)行道路環(huán)境中實(shí)時(shí)交通擁堵?tīng)顟B(tài)的判別。這個(gè)判別的結(jié)果將提供給交通系統(tǒng)的管理者和決策者，他們針對(duì)不同的情況作出相應(yīng)的交通控制、管理和誘導(dǎo)措施。因此，及時(shí)而正確地判別道路的交通擁堵?tīng)顟B(tài)，是采取合理交通擁堵預(yù)警措施、主動(dòng)避免交通擁堵的前提^[1]。

在交通流理論中， 用于描述交通狀態(tài)的參數(shù)主要有三個(gè)，即交通量、車速和密度。單獨(dú)根據(jù)某個(gè)交通流變量來(lái)判斷交通流狀況是不夠全面的：當(dāng)速度為0時(shí)，可能是車輛堵死的情況， 也可能是道路上沒(méi)有車輛的暢通情況；交通流量很低可以對(duì)應(yīng)擁堵和暢通兩種交通流狀況；密度小可能是道路暢通的表現(xiàn)，也可能是大車居多的情況。所以，應(yīng)該對(duì)交通流的三個(gè)變量進(jìn)行綜合分析來(lái)確定交通流狀況，才能較全面反映交通流的真實(shí)情況。

交通擁堵的判別也就是對(duì)交通流數(shù)據(jù)的分類，對(duì)數(shù)據(jù)進(jìn)行分類的方法稱為聚類分析。聚類的目的在于將大量的數(shù)據(jù)辨識(shí)為幾個(gè)較少的數(shù)據(jù)組從而能對(duì)系統(tǒng)行為進(jìn)行簡(jiǎn)潔描述。傳統(tǒng)的聚類分析是一種硬分類，將每個(gè)待識(shí)別的對(duì)象嚴(yán)格地劃分到某個(gè)類中，非此即彼，界限分明。然而，客觀事物之間并沒(méi)有一個(gè)截然區(qū)別的界限，分類時(shí)所依據(jù)的數(shù)據(jù)指標(biāo)的變化也大多是一個(gè)連續(xù)的過(guò)程^[2，3]。因此，用模糊聚類方法對(duì)交通流狀態(tài)進(jìn)行判別更符合實(shí)際。模糊聚類方法得到的結(jié)果指明事物在多大程度上屬于哪一類。同理，交通流狀態(tài)的變化也具有連續(xù)性，人們對(duì)交通狀況的判斷往往擁堵、暢通等模糊概念。所以利用模糊聚類的方法進(jìn)行研究比較合理。

在眾多的模糊聚類方法中，應(yīng)用最廣泛的是模糊C均值(fuzzy Cmeans，F(xiàn)CM)算法。與硬C均值(HCM)相比，F(xiàn)CM能夠獲得更豐富的聚類信息，能更準(zhǔn)確地反映樣本的實(shí)際分布，其收斂性也已得到了證明。因此，F(xiàn)CM算法得到了廣泛應(yīng)用。FCM算法的主要問(wèn)題是計(jì)算復(fù)雜度遠(yuǎn)遠(yuǎn)高于HCM算法，聚類時(shí)間冗長(zhǎng)。特別是在數(shù)據(jù)量很大的情況下，F(xiàn)CM算法要消耗大量的運(yùn)算時(shí)間^[3，4]。針對(duì)交通流數(shù)據(jù)量大的特點(diǎn)，本文考慮使用硬聚類的結(jié)果對(duì)模糊聚類初始值的選取進(jìn)行指導(dǎo)，以加速算法的收斂過(guò)程，使之滿足交通管理和控制的實(shí)際需要。

1 快速模糊C均值聚類算法

1.1 標(biāo)準(zhǔn)FCM算法

模糊聚類的概念最早是由Ruspini提出來(lái)的。FCM聚類是一種比較典型的模糊聚類算法，由Bezdek在1981年提出，用于將多維數(shù)據(jù)空間分布的數(shù)據(jù)點(diǎn)分成特定數(shù)目的類第i個(gè)聚類中心間的歐氏距離；m為模糊指數(shù)，控制分類矩陣U 的模糊程度，m越大，分類的模糊程度越高。當(dāng)m取值為1時(shí)，F(xiàn)CM便退化為HCM^[5]。目標(biāo)函數(shù)Jm(U，V)為每個(gè)數(shù)據(jù)點(diǎn)到各聚類中心的加權(quán)距離平方和。FCM 算法就是一個(gè)使目標(biāo)函數(shù)Jm(U，V)最小化的迭代求解過(guò)程。

應(yīng)用Lagrange乘數(shù)法求解式(2)在式(1)約束下的優(yōu)化問(wèn)題，可得到U、V的取值公式為

FCM算法中，隨機(jī)給定一初始聚類中心，每次迭代都依據(jù)式(3)(4)對(duì)分類和聚類中心同時(shí)進(jìn)行調(diào)整，直到相鄰兩次迭代所得的聚類中心變化小于預(yù)先設(shè)定的ε，則認(rèn)為算法已收斂。1.2 快速FCM算法

研究表明，標(biāo)準(zhǔn)FCM算法中，當(dāng)m取值范圍為m=1~5時(shí)，模糊聚類中心與硬聚類中心非常接近，兩者的偏差隨m值的增加略有增大，在最大偏差時(shí)兩者的接近度為0.98。而在典型的m值(m=2)附近，兩者非常接近于1^[6]。Pal和Bezdek認(rèn)為m的合理取值范圍為1.5~2.5^[7]，本文中取2，故硬聚類中心和模糊聚類中心是非常接近的。因此，可以將硬聚類中心作為模糊聚類中心的迭代初值，以獲得加快算法收斂速度的效果。據(jù)此，本文提出一種改進(jìn)的FCM聚類算法。首先用快速的HCM聚類算法確定輸入數(shù)據(jù)的硬聚類中心，然后將所得的硬聚類中心作為FCM算法的初始聚類中心，加快了算法的收斂速度。算法的迭代步驟如下：

第一階段算法

2 數(shù)據(jù)準(zhǔn)備

要正確對(duì)主干道交通狀態(tài)進(jìn)行分類，所采集的數(shù)據(jù)應(yīng)該覆蓋交通流數(shù)據(jù)變化的整個(gè)范圍，不僅包括暢通狀態(tài)，也包括擁堵?tīng)顟B(tài)，還有兩者之間的過(guò)渡狀態(tài)^[8]。

本文所用的數(shù)據(jù)來(lái)源于重慶市交通控制管理中心的交通信息數(shù)據(jù)庫(kù)，采集自重慶市渝中區(qū)菜園壩至上清寺的CC斷面。本文處理的數(shù)據(jù)對(duì)象為單車道內(nèi)流量、速度和密度。由于時(shí)間間隔太短無(wú)法準(zhǔn)確地把握交通狀態(tài)的特征，而且狀態(tài)特征還易于走向極端現(xiàn)象。這里所處理數(shù)據(jù)時(shí)間間隔為5 min。連續(xù)統(tǒng)計(jì)一周，以保證數(shù)據(jù)的完整性。

最終得到的數(shù)據(jù)樣本為：每個(gè)車道共2 016組數(shù)據(jù)，每組數(shù)據(jù)包含流量、速度和交通流密度三個(gè)特征參數(shù)。其中流量按照標(biāo)準(zhǔn)車輛進(jìn)行轉(zhuǎn)換，單位為pcu/5min。速度為單車道5 min內(nèi)車流的平均速度，密度為單車道5 min內(nèi)車流的平均密度。獲得的交通流數(shù)據(jù)如圖1所示。其中流量數(shù)據(jù)是5 min內(nèi)通過(guò)檢測(cè)點(diǎn)的車輛數(shù)，沒(méi)有轉(zhuǎn)換為小時(shí)流量，是為了使交通流三個(gè)參數(shù)在數(shù)值上相差不大，以利于聚類分析。

3 交通擁堵?tīng)顟B(tài)的模糊判別及分析

依據(jù)我國(guó)公安部2002年公布的《城市交通管理評(píng)價(jià)指標(biāo)體系》，本文將道路交通狀態(tài)劃分為四個(gè)等級(jí)，即通暢、輕度擁堵、擁堵和嚴(yán)重?fù)矶隆Ｆ渲型〞潮硎咀罴训牡缆愤\(yùn)行狀態(tài)，而嚴(yán)重?fù)矶聞t表示最差的運(yùn)行狀態(tài)。

利用前述FFCM算法進(jìn)行模糊聚類，ε值取0.001，聚類結(jié)果如圖2所示。目標(biāo)函數(shù)迭代過(guò)程如圖3所示。

表示通暢、輕度擁堵、擁堵和嚴(yán)重?fù)矶滤膫€(gè)分類的聚類中心分別為[65.5 13.2 60.5]、[96.0 25.7 50.9]、[48.8 54.7 28.5]和[18.0 70.3 16.4]。聚類中心的三個(gè)參數(shù)分別表示流量(pcu/5 min)、速度(km/h ) 和密度(pcu/km)。從圖2可以看出基于模糊聚類的算法綜合考慮到交通流三個(gè)變量的綜合作用。為了檢驗(yàn)算法的效果，隨機(jī)抽取幾個(gè)樣本點(diǎn)進(jìn)行分析，如表1所示。

表1 隨機(jī)選取的樣本

樣本流量速度密度μcμqμyμyz結(jié)果

4828.661.223.20.590.350.030.02CT

7483.047.533.80.080.320.420.18YD

34030.957.624.60.390.550.030.03QD

77074.514.658.70.020.040.060.88YZ

1 27889.221.057.30.010.020.820.14YD

1 78634.454.928.20.220.700.030.04QD

表中：μc表示暢通隸屬度；μq表示輕度擁堵隸屬度；μy表示擁堵隸屬度；μyz表示嚴(yán)重?fù)矶码`屬度；CT表示暢通；QD表示輕度擁堵；YD表示擁堵；YZ表示嚴(yán)重?fù)矶隆＊?/p>

從表1和圖2可以看出：

a)交通流的分類與速度的關(guān)系最為緊密，單憑速度幾乎可以將交通流分為四類：速度大于61 km/h，可以認(rèn)為是暢通，速度在[45，61]可認(rèn)為是輕度擁堵，速度在[20，45]可以認(rèn)為是擁堵，而速度在20 km/h以下則認(rèn)為是嚴(yán)重?fù)矶隆＿@與大多數(shù)只根據(jù)速度經(jīng)驗(yàn)性地對(duì)交通流的分類方法基本一致。

b)交通流密度超過(guò)55 pcu/km，可以判斷交通狀態(tài)為嚴(yán)重?fù)矶拢渌闆r需要根據(jù)三個(gè)變量來(lái)綜合判斷。

c)單獨(dú)用流量很難對(duì)交通流進(jìn)行劃分，因?yàn)橛泻芏喔黝惤煌鳡顩r相互重合的區(qū)域，即同一個(gè)流量對(duì)應(yīng)多種交通流狀況。

d)僅僅依靠速度也很難精確劃分交通流狀態(tài)，因速度在[40，50]，需要根據(jù)流量和密度進(jìn)一步判斷交通流狀態(tài)。

4 結(jié)束語(yǔ)

及時(shí)而有效的交通擁堵?tīng)顟B(tài)判別是進(jìn)行動(dòng)態(tài)交通擁堵預(yù)警和交通疏導(dǎo)、主動(dòng)避免交通擁堵、保持道路暢通的前提和依據(jù)。通常情況下，人們對(duì)交通流狀態(tài)的判別是憑經(jīng)驗(yàn)進(jìn)行的。本文給出一種較科學(xué)的判斷方法，根據(jù)實(shí)測(cè)的道路交通流數(shù)據(jù)，采用FFCM聚類分析方法對(duì)交通擁堵?tīng)顟B(tài)分類進(jìn)行了研究。在得出交通流狀態(tài)各聚類中心之后， 根據(jù)算法很容易判斷新測(cè)的交通流數(shù)據(jù)屬于何種交通流狀態(tài)。

聚類結(jié)果表明：a)用模糊聚類的方法進(jìn)行交通流狀態(tài)聚類分析是一種行之有效的方法；b)速度對(duì)交通流分類的影響最大， 其次是交通流密度， 流量的作用最低；c)交通流狀態(tài)是各個(gè)交通流變量綜合作用的結(jié)果，單獨(dú)根據(jù)某一個(gè)交通流變量進(jìn)行經(jīng)驗(yàn)性的交通擁堵判別是不夠全面的。

參考文獻(xiàn)：

［1］SHANGA P， LUB Y， KAMA S. The application of Hlder exponent to traffic congestion warning［J］.Physica，2006，370:769776.

［2］姜桂艷， 江龍暉， 王江鋒. 城市快速路交通擁擠識(shí)別方法［J］.交通運(yùn)輸工程學(xué)報(bào)， 2006，6(3):8791.

［3］成衛(wèi)， 李江. 模糊聚類法在基于交通沖突技術(shù)的交叉口安全評(píng)價(jià)中的應(yīng)用［J］.交通運(yùn)輸系統(tǒng)工程與信息， 2004，4(2):4855.

［4］普運(yùn)偉， 金煒東， 朱明，等. 核模糊C均值算法的聚類有效性研究［J］.計(jì)算機(jī)科學(xué)， 2007，34(2):207210.

［5］HATHAWAY R J，BEZDEK J C. Extending fuzzy and probabilistic clustering to very large data sets［J］.Computational Statistics Data Analysis， 2006，51:215234.

［6］GAO Xinbo， XIE Weixin. Advances in theory and applications of fuzzy clustering［J］.Chinese Science Bulletin，2000，45(11):961970.

［7］錢同惠，沈其聰，葛曉濱，等. 模糊邏輯及其工程應(yīng)用［M］.北京：電子工業(yè)出版社，2001:165210.

［8］皮曉亮， 王正， 韓皓，等. 基于環(huán)形線圈檢測(cè)器采集信息的交通狀態(tài)分類方法應(yīng)用研究［J］. 公路交通科技， 2006，23(4):115119.