基于MR-FCM的區(qū)域交通狀態(tài)識別方法*

梅 朵 楊慶芳 鄂 旭

(渤海大學(xué)信息科學(xué)與技術(shù)學(xué)院1) 錦州 121013) (遼寧省農(nóng)產(chǎn)品質(zhì)量安全追溯工程技術(shù)研究中心2) 錦州 121013) (吉林大學(xué)交通學(xué)院3) 長春 130012)

0 引 言

交通狀態(tài)識別一直是智能交通領(lǐng)域的研究熱點，如何準確地識別當(dāng)前的交通狀態(tài)，并可以預(yù)測未來時段的交通狀態(tài)，是實現(xiàn)交通控制與管理的前提[1].隨著城市路網(wǎng)規(guī)模的不斷擴大，傳統(tǒng)的針對路段或者交叉口的交通狀態(tài)識別方法，由于運行效率非常低，面對路網(wǎng)數(shù)據(jù)量的增大，顯然力不從心，已經(jīng)無法滿足當(dāng)前交通控制與管理的需求.

針對路網(wǎng)規(guī)模的擴大，一些專家學(xué)者已經(jīng)研究出了一些解決區(qū)域路網(wǎng)交通狀態(tài)識別的方法，大致可以分為三類：①統(tǒng)計學(xué)方法，即通過設(shè)計路網(wǎng)交通狀態(tài)評價體系，宏觀地實現(xiàn)路網(wǎng)交通狀態(tài)識別；②基于聚類、模式識別的方法[2-3]，即通過交通流參數(shù)分析得到交通狀態(tài)；③基于路網(wǎng)拓撲特征的方法[4-5]，即通過分析路網(wǎng)連通性，并設(shè)計交通狀態(tài)判別系數(shù)，從而得到區(qū)域交通狀態(tài).

這些方法在一定程度上實現(xiàn)了區(qū)域路網(wǎng)的交通狀態(tài)識別，但是仍然有一些不足，如對路網(wǎng)交通信息考慮不全面、算法運行效率低等問題，導(dǎo)致無法滿足智能交通控制與管理的實時性需求.云計算，自誕生之日起，就是為了解決數(shù)據(jù)量大、處理困難的問題而生，其MapReduce并行編程模型可以很好地實現(xiàn)大數(shù)據(jù)集的并行化處理，有效地避免通信瓶頸，為進一步解決區(qū)域路網(wǎng)交通狀態(tài)識別中的數(shù)據(jù)量大、求解難的問題提供了契機[6].因此，本文針對模糊C-均值(fuzzy C-means，F(xiàn)CM)聚類算法存在的不足之處，結(jié)合云計算的MapReduce并行編程模型，對該算法進行改進，提出基于MR-FCM的區(qū)域交通狀態(tài)識別方法，在保證區(qū)域路網(wǎng)交通狀態(tài)識別的準確性前提下，進一步提高區(qū)域路網(wǎng)交通狀態(tài)識別的效率，從而更好地滿足智能交通控制與管理的需求.

1 模糊C均值聚類算法

模糊聚類分析源于多元統(tǒng)計分析，由于模糊聚類分析可以獲得對象隸屬于不同類的不確定程度，更客觀地反映對象的實際屬性，被廣泛應(yīng)用于處理具有模糊關(guān)系的對象數(shù)據(jù)集[7-8].針對分類數(shù)可以確定的對象集合，基于目標函數(shù)聚類的模糊C均值聚類(FCM)是分析事物的最佳算法.

Balafar等[9]提出FCM算法，該算法可以把聚類問題轉(zhuǎn)化為非線性規(guī)劃問題，通過迭代優(yōu)化，糊劃分和聚類結(jié)果.FCM算法的基本思想是：分類數(shù)確定的情況下，通過算法的不斷迭代，將數(shù)據(jù)集進行分類，使同類中的數(shù)據(jù)相似度最大，非同類中的數(shù)據(jù)相似度最小[10].

設(shè)聚類樣本X={x1,x2,…,xn}.其中n為樣本中數(shù)據(jù)的個數(shù)，將樣本分為C(1

目標函數(shù)為

(1)

約束條件為

(2)

式中：V=[V1,V2,…,VC]為每一類的聚類中心；dij2=‖xj-υi‖=(xj-υi)TA(xj-υi)為第j個數(shù)據(jù)到第i個聚類中心的歐式距離；m為模糊加權(quán)指數(shù)，m越大，U的模糊程度越高[12].

用拉格朗日乘法求解(1)，可得

(3)

對式(3)所有變量求導(dǎo)可得

(4)

(5)

由FCM算法的基本思想可以看出，F(xiàn)CM算法的聚類效果和初始聚類中心、聚類個數(shù)C，以及加權(quán)指數(shù)m三個參數(shù)有關(guān)；FCM算法的運行時間主要消耗在求解式(4)～(5)上.其中，聚類個數(shù)C根據(jù)實際需求而定，對于區(qū)域交通狀態(tài)判別問題來說，C=3；關(guān)于m的取值，Pal等[13]通過實驗發(fā)現(xiàn)，m的最佳取值范圍為[1.5,2.5]，本文取中間值2.為避免初始聚類中心的噪聲影響，導(dǎo)致算法陷入局部最優(yōu)，基于均值-標準差確定初始聚類中心.

均值-標準差的思想來自于隨機函數(shù)的分布知識，聚類樣本是均勻分布在樣本均值附近的.假設(shè)分類數(shù)為C，則第i類的初始聚類中心mi為

(6)

式中：μ為樣本均值；σ為樣本標準差.

此外，為了提高整個算法的速度，引入MapReduce編程模型對FCM進行并行化處理.

2 MapReduce并行編程模型

MapReduce并行編程模型是一種開源的、精簡的計算模型，其實現(xiàn)過程需要兩個函數(shù)：映射(Map)和歸約(Reduce)[14].映射函數(shù)負責(zé)將大數(shù)據(jù)集劃分成多個小數(shù)據(jù)集來處理，歸約函數(shù)負責(zé)對中間結(jié)果進行匯總.具體實現(xiàn)過程見圖1 .

圖1 MapReduce的實現(xiàn)過程

MapReduce的實現(xiàn)過程分為數(shù)據(jù)分割、任務(wù)指派、Map執(zhí)行、保存中間結(jié)果、Reduce執(zhí)行、輸出最終結(jié)果等階段[15].主控程序負責(zé)數(shù)據(jù)分割和任務(wù)分配；工作機負責(zé)接收數(shù)據(jù)片段和任務(wù)，并完成Map函數(shù)和Reduce函數(shù)的調(diào)用，對數(shù)據(jù)進行處理，并輸出中間結(jié)果和最終結(jié)果.MapReduce的實現(xiàn)過程中，數(shù)據(jù)都是以鍵值對格式保存和傳輸?shù)?

3 基于MR的FCM算法

MR-FCM算法的基本流程如下.

1) 數(shù)據(jù)準備 獲取交通狀態(tài)參數(shù)的數(shù)據(jù)樣本，定義數(shù)據(jù)樣本的初始鍵值對格式為<路段編號，記錄屬性向量>，并將數(shù)據(jù)集保存到本地磁盤上.

2) 數(shù)據(jù)樣本分割 將M+1臺機器中的一臺既作為主機器又作為從機器，其余M臺均為從機器.主機器將數(shù)據(jù)集分割為M個小數(shù)據(jù)塊，并發(fā)送到M臺從機器上.

3) 初始聚類中心的確定 主機器基于均值-標準差確定的初始聚類中心，并將初始聚類中心、聚類個數(shù)、迭代次數(shù)、算法終止閾值、加權(quán)指數(shù)等參數(shù)發(fā)送到M個從機器上.

4) Map階段，計算隸屬度 從機器調(diào)用Map()函數(shù)，按照式(5)計算每一個樣本點對初始聚類中心的歐氏距離和隸屬度，并以鍵值對(key,value)的形式輸出中間結(jié)果.

5) 合并操作 為了降低網(wǎng)絡(luò)的通信成本，執(zhí)行Combine操作.此時，具有相同key值的參數(shù)合并起來，使具有具有相同交通狀態(tài)的路段聚成一類，共形成C類.

6) Reduce階段 計算新的聚類中心.從機器調(diào)用Reduce函數(shù)，按照式(4)計算C個類的新聚類中心.

7) 判斷算法是否收斂 比較新聚類中心和初始聚類中心，如果變化小于給定閾值，則輸出聚類中心；否則用新聚類中心替代初始聚類中心，重復(fù)執(zhí)行4)～6)，直到滿足條件或達到最大迭代次數(shù)，輸出聚類中心.

8) 主機器將聚類中心分配到M臺從機器上，從機器調(diào)用Map()函數(shù)，按照式(5)計算每一個樣本點對初始聚類中心的歐氏距離和隸屬度，經(jīng)主機器匯總，輸出最終交通狀態(tài)判別的結(jié)果.

4 實例驗證

4.1 數(shù)據(jù)來源

區(qū)域路網(wǎng)交通狀態(tài)判別方法的驗證數(shù)據(jù)來自于VISSIM仿真軟件，仿真路網(wǎng)見圖2，該路網(wǎng)共12個交叉口，其中交叉口6，8為兩相位，其余均為三相位.該路網(wǎng)共17條雙向路段，1-2-3-4,1-5-9，3-7-11和9-10-11-12均為雙向6車道，其余為雙向4車道.通過VISSIM仿真采集平均路段行程速度、飽和度、時間占有率、排隊長度等交通狀態(tài)參數(shù).仿真時長27 000 s，采集數(shù)據(jù)間隔300 s，共采集到3 060條交通狀態(tài)參數(shù)數(shù)據(jù).

圖2 仿真路網(wǎng)

4.2 確定評價指標及其閾值表

選取對交通狀態(tài)影響比較顯著的四個交通參數(shù)：平均路段行程速度、路段飽和度、時間占有率和排隊長度比為區(qū)域路網(wǎng)交通狀態(tài)的指標.

平均行程車速的表達式為

(7)

式中：Li為路段長度；Ti(t)為路段形成時間.

路段飽和度的表達式為

(8)

式中：V為路段實際流量；C為路段通行能力.

時間占有率的表達式為

(9)

式中：Δti為第i輛車通過檢測器需要的時間，s；Ti(t)為檢測器檢測總時間，s.

排隊長度比的表達式為

(10)

式中：Q為檢測時間內(nèi)的平均排隊長度，m；L為路段長度，m.

由VISSIM仿真確定閾值表，分別改變路段的流量輸入以模擬出暢通、擁擠、嚴重擁擠的交通狀況，同時記錄車輛的運行數(shù)據(jù)包，按照式(7)～(10)計算單個探測車擁堵表征量.標定后的道路交通擁堵狀態(tài)特征量閾值見表1.

表1 判別指標閾值表

4.3 基于MR-FCM的路網(wǎng)交通狀態(tài)判別

定義區(qū)域路網(wǎng)的交通狀態(tài)有三種，即C=3.為了驗證所提出的基于MR-FCM算法的有效性和高效性，與串行FCM算法進行對比.采用8臺計算機搭建Hadoop實驗平臺，其中一臺計算機既為主機器也為從機器，其余均為從機器.取并行節(jié)點數(shù)為1，2，4，6，8，當(dāng)并行節(jié)點數(shù)為1時是串行算法.

1) 聚類中心的確定 采用均值-標準差方法確定的初始聚類中心為

分別采用并行算法和串行算法對采集到的3 060組評價指標數(shù)據(jù)進行聚類分析.并行算法得到的三種交通狀態(tài)的聚類中心用矩陣表示為

串行算法得到的三種交通狀態(tài)的聚類中心用矩陣表示為

聚類中心矩陣的三行分別表示暢通、擁擠、嚴重擁擠三種交通狀態(tài)的聚類中心，聚類中心由平均路段行程速度、路段飽和度、時間占有率和排隊長度比組成.對比并行算法和串行算法得到的聚類中心矩陣可以看出，兩種算法得到的聚類中心比較接近，說明并行算法的并行環(huán)境，以及中間結(jié)果合并、傳遞和最終結(jié)果匯總等過程并沒有影響聚類質(zhì)量.

2) 判別結(jié)果分析 以采集的指標數(shù)據(jù)為基礎(chǔ)，實現(xiàn)34條路段在90個時段的交通狀態(tài)判別，并對比串行算法和并行算法的判別結(jié)果.通過實驗發(fā)現(xiàn)，并行算法和串行算法的判別結(jié)果基本相同，說明并行算法的中間結(jié)果傳遞和最終結(jié)果匯總等過程并沒有影響判別效果，驗證了所提出的并行FCM算法的正確性.通過計算統(tǒng)計，發(fā)現(xiàn)并行算法的路網(wǎng)交通狀態(tài)判別準確率大于90%，驗證了所提出的并行FCM算法的有效性.圖3為隨機選取的四條路段在90個時段內(nèi)的判別結(jié)果，并與仿真運行的實際交通狀態(tài)進行相應(yīng)的對比圖，其中縱坐標1，2，3分別表示暢通狀態(tài)，擁擠狀態(tài)和嚴重擁擠狀態(tài).

圖3 路網(wǎng)交通狀態(tài)判別結(jié)果

3) 運行時間分析 以運行時間(聚類時間和區(qū)域交通狀態(tài)判別時間的總和)和加速比(Sn)為指標對所提出算法進行評價.圖4～5為運行時間對比圖和加速比曲線圖.由圖4可知，當(dāng)并行節(jié)點數(shù)為2時，所提出的并行FCM算法的運行時間小于串行FCM算法，但是運行時間減小的幅度較小，運行效率提高得不明顯，原因是并行節(jié)點數(shù)太少，增加了Map階段耗時.當(dāng)并行節(jié)點數(shù)繼續(xù)增加以后，運行時間減少的幅度增大，但是當(dāng)并行節(jié)點數(shù)增加到8時，運行時間減少的幅度又變小，原因是并行節(jié)點數(shù)增加的過程，也增加了并行節(jié)點之間的通信負荷，并不是并行節(jié)點數(shù)越多越好，該實例中并行節(jié)點數(shù)取6時可以得到最佳性能比.可見，在交通狀態(tài)判別過程中，根據(jù)區(qū)域路網(wǎng)的規(guī)模，合理地選擇并行節(jié)點數(shù)，才能達到提高判別效率、節(jié)省資源的目的.

由圖5可知，所提出并行算法的加速比逐漸增加，說明其具有良好的擴展性.當(dāng)并行節(jié)點數(shù)為8時，算法獲得最大的加速比，S8=Ts/Tp=378.24 s/50.46 s=7.49，即并行算法是串行算法的運行效率的7.49倍，最小運行時間50.46 s，滿足區(qū)域路網(wǎng)交通狀態(tài)判別的需求.

圖4 運行時間對比圖 圖5 加速比曲線圖

5 結(jié) 束 語

本文通過分析FCM算法的初始聚類中心、聚類個數(shù)、加權(quán)指數(shù)等參數(shù)以及算法的并行性，對FCM算法進行了改進，提出了一種基于MapReduce的FCM并行算法，彌補了FCM算法在解決區(qū)域路網(wǎng)交通狀態(tài)判別時存在的困難.通過實驗發(fā)現(xiàn)，與串行FCM算法相比，本文所提出的基于MapReduce和FCM的區(qū)域交通狀態(tài)判別方法具有高效性、可行性和可擴展性，更好地滿足了城市路網(wǎng)區(qū)域交通狀態(tài)判別的需求.