于福華，范永青

(西安郵電大學(xué) 自動(dòng)化學(xué)院, 陜西 西安 710121)

基于改進(jìn)FCM算法的交通流分析

于福華，范永青

(西安郵電大學(xué) 自動(dòng)化學(xué)院, 陜西 西安 710121)

摘要:針對交通流聚類問題，提出一種改進(jìn)的模糊C-均值算法。該算法根據(jù)交通流特點(diǎn)，對樣本數(shù)據(jù)集進(jìn)行處理得到模糊等價(jià)矩陣，通過改進(jìn)隸屬度函數(shù)和距離度量函數(shù)得到新的目標(biāo)函數(shù),利用拉格朗日算法優(yōu)化隸屬度和聚類中心，最后通過凝聚度和分離度實(shí)現(xiàn)自動(dòng)聚類。實(shí)驗(yàn)結(jié)果表明，改進(jìn)FCM算法削弱了突變點(diǎn)影響，提高了聚類效果。

關(guān)鍵詞:FCM算法；改進(jìn)FCM算法；隸屬度函數(shù)；聚類中心；交通流

模糊C-均值(FuzzyC-Means，F(xiàn)CM)聚類算法是由硬C-均值(HardC-Means，HCM)聚類算法發(fā)展而來[1]，已被廣泛應(yīng)用于模式識(shí)別[2-3]、數(shù)據(jù)挖掘[4-5]、圖像處理[6]及機(jī)器學(xué)習(xí)[7]等領(lǐng)域。

交通流數(shù)據(jù)尤其是小數(shù)據(jù)量交通流數(shù)據(jù)存在數(shù)據(jù)噪聲，并且實(shí)時(shí)交通流是動(dòng)態(tài)變化的，其聚類數(shù)及聚類中心未知，這對FCM聚類算法提出更高的要求?，F(xiàn)有的FCM聚類算法在交通流數(shù)據(jù)聚類中存在抗噪性不足的問題[8-10]。本文通過改進(jìn)隸屬度函數(shù)和距離度量函數(shù)，對FCM聚類算法進(jìn)行優(yōu)化，最后利用改進(jìn)的FCM自動(dòng)聚類算法對某高速公路交通流樣本數(shù)據(jù)進(jìn)行聚類分析。

1FCM聚類算法

FCM算法通過迭代優(yōu)化目標(biāo)函數(shù)而得到聚類結(jié)果，用隸屬度來反映樣本點(diǎn)隸屬于某一類的程度[11]。原始數(shù)據(jù)樣本集X={x1,x2,…,xn}，共n個(gè)樣本，每個(gè)樣本有m項(xiàng)指標(biāo)。建立優(yōu)化目標(biāo)函數(shù)

其中隸屬矩陣為U=(uij)c×n，uij表示數(shù)據(jù)集合中第j個(gè)元素對第i個(gè)聚類中心的隸屬度；聚類中心矩陣為V=(vi)c，c為分類樹，vi表示第i個(gè)聚類的聚類中心，vi=(vi1,vi2,…,vim)；dij為第i個(gè)聚類中心與第j個(gè)元素間的歐幾里德距離；α為模糊指數(shù)，反映模糊程度。值越大，分類的模糊度越高。對隸屬度和聚類中心按照拉格朗日乘子尋優(yōu)算法進(jìn)行迭代。第q步后的隸屬度和聚類中心迭代表達(dá)式為

‖v(q+1)-v(q)‖<ε1并且‖u(q+1)-u(q)‖<ε2，

則迭代停止，其中ε1和ε2為迭代停止閾值。

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

對經(jīng)過標(biāo)準(zhǔn)均一化處理后的標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行模糊運(yùn)算，得到模糊相似矩陣，對模糊相似矩陣進(jìn)行平方法運(yùn)算得到模糊等價(jià)矩陣。通過優(yōu)化隸屬度函數(shù)和距離度量函數(shù)從而改進(jìn)目標(biāo)函數(shù)。經(jīng)過對隸屬度和聚類中心進(jìn)行迭代優(yōu)化，并由凝聚度和分離度確定最優(yōu)分類數(shù)，從而實(shí)現(xiàn)改進(jìn)FCM聚類算法的自動(dòng)聚類。

2.1數(shù)據(jù)預(yù)處理

2.2模糊等價(jià)矩陣

模糊相似矩陣R=(rij)n×n，分別按照最大最小法和比例相似法建立模糊相似矩陣

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

為了提高FCM聚類算法的抗噪性，提出改進(jìn)FCM聚類算法。減少數(shù)據(jù)樣本中噪聲點(diǎn)或跳變點(diǎn)對聚類的影響，引入偏差系數(shù)對隸屬度函數(shù)進(jìn)行優(yōu)化；在距離度量函數(shù)的優(yōu)化中，引入距離調(diào)整系數(shù)對距離度量函數(shù)進(jìn)行修正，從而改進(jìn)目標(biāo)函數(shù)[13]。

2.4迭代優(yōu)化

2.5自動(dòng)聚類

分析不同分類數(shù)c所對應(yīng)的聚類結(jié)果，按照凝聚度和分離度自動(dòng)確定最優(yōu)分類數(shù)，實(shí)現(xiàn)改進(jìn)FCM聚類算法。聚類有效性評價(jià)指標(biāo)FXB用以評價(jià)聚類有效性，F(xiàn)XB越小對應(yīng)聚類有效性越好?；贔CM聚類算法的理論最優(yōu)分類數(shù)目標(biāo)函數(shù)表達(dá)式為

3實(shí)驗(yàn)結(jié)果與分析

3.1指標(biāo)聚類

取某高速公路一個(gè)月上行和下行的交通流數(shù)據(jù)Y和Z為樣本，其指標(biāo)包括交通流量、平均速度、時(shí)間占有率、時(shí)間間距、交通密度。對數(shù)據(jù)樣本進(jìn)行指標(biāo)聚類，設(shè)定初始參數(shù)

w(xc)=w(bl)=0.5，ε1=ε2=1E-5，α=2。采用改進(jìn)FCM聚類算法進(jìn)行指標(biāo)聚類，其結(jié)果相同。自動(dòng)聚類c*=3，指標(biāo)聚類為{交通流量q}、{平均速度v}和{時(shí)間占有率o，時(shí)間間距t，交通密度ρ}。

3.2數(shù)據(jù)聚類

根據(jù)交通流指標(biāo)聚類結(jié)果，在交通流數(shù)據(jù)聚類中對交通流量q、平均速度v和時(shí)間占有率o進(jìn)行分析。采用各日平均小時(shí)交通流數(shù)據(jù)用于FCM聚類分析和改進(jìn)FCM聚類分析，得到各聚類中心以及評價(jià)指標(biāo)如表1所示。

表1　智能交通系統(tǒng)隧道交通流數(shù)據(jù)聚類

聚類評價(jià)指標(biāo)分別表示對于c*分類時(shí)各聚類水平，并且相對于FXB和FIXB越小代表其聚類越合理。從表1可看出，采用改進(jìn)FCM比采用FCM的評價(jià)指標(biāo)值減小，反映出改進(jìn)FCM聚類算法優(yōu)于FCM聚類算法。改進(jìn)FCM聚類算法提高了FCM聚類算法的抗噪性，在交通流數(shù)據(jù)聚類中削弱了噪聲點(diǎn)和突變點(diǎn)對聚類的影響，聚類中心向各中心靠近，提高了原有聚類算法的聚類效果。對于節(jié)假日出現(xiàn)突變數(shù)據(jù)時(shí)，改進(jìn)FCM聚類優(yōu)化明顯優(yōu)于經(jīng)典FCM聚類結(jié)果。

4結(jié)束語

改進(jìn)的FCM聚類算法通過引入偏差系數(shù)和距離調(diào)整系數(shù)分別對隸屬度函數(shù)和距離度量函數(shù)進(jìn)行優(yōu)化。通過對某高速公路的交通流樣本進(jìn)行實(shí)驗(yàn)，分別對FCM聚類算法和改進(jìn)FCM聚類算法進(jìn)行聚類對比。實(shí)驗(yàn)結(jié)果表明，通過采用改進(jìn)FCM聚類算法后評價(jià)指標(biāo)均有所改善，即改進(jìn)FCM聚類算法優(yōu)于原FCM聚類算法。改進(jìn)FCM算法削弱了噪聲對算法的影響，并且減弱了突變點(diǎn)數(shù)據(jù)對聚類的影響。

參考文獻(xiàn)

[1]KUMARP,SirohiD.ComparativeAnalysisofHCMandFCMAlgorithmonirisDataSet[J].InternationalJournalofComputerApplications, 2010,5(2):33.

[2]張超,趙向陽. 基于加權(quán)模糊核聚類的局部放電模式識(shí)別[J].電力電子,2012(1):32-35.

[3]侯雪梅. 基于全監(jiān)督算法RBF神經(jīng)網(wǎng)絡(luò)的語音識(shí)別[J]. 西安郵電學(xué)院學(xué)報(bào), 2011,16(1): 88-90.

[4]劉靜,趙宇馳. 數(shù)據(jù)挖掘領(lǐng)域中的聚類分析[J]. 東北林業(yè)大學(xué)學(xué)報(bào),2012(8): 163-166.

[5]支曉斌, 田溪. 判別模糊c-均值聚類算法[J]. 西安郵電大學(xué)學(xué)報(bào), 2013,18(5): 26-30.DOI:10.13682/j.issn.2095-6533.2013.05.025.

[6]李琳,范九倫,趙鳳. 模糊C-均值聚類圖像分割算法的一種改進(jìn)[J]. 西安郵電大學(xué)學(xué)報(bào), 2014,19(05):56-70.DOI:10.13682/j.issn.2095-6533.2014.05.011.

[7]高琰,古士文,唐琎. 機(jī)器學(xué)習(xí)中譜聚類方法的研究[J].計(jì)算機(jī)科學(xué),2007(2):201-203.

[8]王旭琴,諶業(yè)文,胡堯. 基于FCM聚類的多路段城市道路車流數(shù)據(jù)分析及其應(yīng)用[C]//貴州省系統(tǒng)工程學(xué)會(huì)第五屆學(xué)術(shù)年會(huì)論文集,貴陽：貴州省科學(xué)技術(shù)協(xié)會(huì)2014:10-20.

[9]黃艷國,許倫輝,鄺先驗(yàn).基于模糊C均值聚類的城市道路交通狀態(tài)判別[J].重慶交通大學(xué)學(xué)報(bào):自然科學(xué)版,2015,2:106-111.DOI:10.3969/j.issn.1674-0696.2015.02.22.

[10]夏美娟, 梁雪春, 韓峰濤. 基于改進(jìn)FCM聚類算法的T-S模糊神經(jīng)網(wǎng)絡(luò)水質(zhì)評價(jià)方法[J]. 計(jì)算機(jī)與應(yīng)用化學(xué), 2013,30(10):1197-1202.DOI:10.3969/j.issn.1001-4160.2013.10.024.

[11]高新波.模糊聚類分析及其應(yīng)用[M].西安：西安電子科技大學(xué)出版社,2004：1-212.

[12]張媛,沈慶偉,張鈴. 基于上空間的模糊等價(jià)關(guān)系在聚類分析中的應(yīng)用[J].安徽建筑工業(yè)學(xué)院學(xué)報(bào):自然科學(xué)版,2013,21(2):83-86.

[13]于福華.特長高速公路隧道交通流研究[D].西安:長安大學(xué),2010：1-66.

[責(zé)任編輯：祝劍]

AnalysisoftrafficflowbasedontheimprovedFCMalgorithm

YUFuhua，F(xiàn)ANYongqing

(SchoolofAutomation,Xi’anUniversityofPostsandTelecommunications,Xi’an710121,China)

Abstract:An improved Fuzzy C-Means (FCM) algorithm is put forward to resolve the traffic flow clustering. According to the characteristics of traffic flow, a fuzzy equivalent matrix is achieved by dealing with the sample data sets, a new objective function is optimized by improving the membership function and distance measurement function，and the Lagrange multiplier optimization algorithm is used to optimize the membership degree and clustering center. Then the automatic clustering is obtained by the degree of cohesion and separation. Experimental results show that, the improved FCM algorithm can weaken the mutation point effect and improve the clustering effect.

Keywords:FCM algorithm, improved FCM algorithm, membership function, clustering center, traffic flow

doi:10.13682/j.issn.2095-6533.2016.02.023

收稿日期：2014-5-16

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61305098)；陜西省教育廳科學(xué)研究計(jì)劃資助項(xiàng)目(12JK0791,14JK1671)

作者簡介：于福華(1976-)，女，博士，講師，從事智能交通系統(tǒng)仿真研究。E-mail:yufuhua@xupt.edu.cn 范永青(1978-)，女，博士，講師，從事非線性系統(tǒng)控制研究。E-mail:fanyongqing@xupt.edu.cn

中圖分類號(hào)：TP274

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：2095-6533(2016)02-0115-04