基于MR-FCM的區域交通狀態識別方法*

梅 朵 楊慶芳 鄂 旭

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

0 引 言

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

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

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

1 模糊C均值聚類算法

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

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

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

目標函數為

(1)

約束條件為

(2)

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

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

(3)

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

(4)

(5)

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

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

(6)

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

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

2 MapReduce并行編程模型

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

圖1 MapReduce的實現過程

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

3 基于MR的FCM算法

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

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

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

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

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

5) 合并操作 為了降低網絡的通信成本，執行Combine操作.此時，具有相同key值的參數合并起來，使具有具有相同交通狀態的路段聚成一類，共形成C類.

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

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

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

4 實例驗證

4.1 數據來源

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

圖2 仿真路網

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

選取對交通狀態影響比較顯著的四個交通參數：平均路段行程速度、路段飽和度、時間占有率和排隊長度比為區域路網交通狀態的指標.

平均行程車速的表達式為

(7)

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

路段飽和度的表達式為

(8)

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

時間占有率的表達式為

(9)

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

排隊長度比的表達式為

(10)

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

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

表1 判別指標閾值表

4.3 基于MR-FCM的路網交通狀態判別

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

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

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

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

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

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

圖3 路網交通狀態判別結果

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

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

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

5 結 束 語

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