梅 朵 楊慶芳 鄂 旭

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

0 引 言

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

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

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

1 模糊C均值聚類算法

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

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

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

目標(biāo)函數(shù)為

(1)

約束條件為

(2)

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

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

(3)

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

(4)

(5)

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

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

(6)

式中：μ為樣本均值；σ為樣本標(biāo)準(zhǔn)差.

此外，為了提高整個(gè)算法的速度，引入MapReduce編程模型對(duì)FCM進(jìn)行并行化處理.

2 MapReduce并行編程模型

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

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

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

3 基于MR的FCM算法

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

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

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

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

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

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

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

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

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

4 實(shí)例驗(yàn)證

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

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

圖2 仿真路網(wǎng)

4.2 確定評(píng)價(jià)指標(biāo)及其閾值表

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

平均行程車速的表達(dá)式為

(7)

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

路段飽和度的表達(dá)式為

(8)

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

時(shí)間占有率的表達(dá)式為

(9)

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

排隊(duì)長度比的表達(dá)式為

(10)

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

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

表1 判別指標(biāo)閾值表

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

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

1) 聚類中心的確定 采用均值-標(biāo)準(zhǔn)差方法確定的初始聚類中心為

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

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

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

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

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

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

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

圖4 運(yùn)行時(shí)間對(duì)比圖 圖5 加速比曲線圖

5 結(jié) 束 語

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