一種改進的道路行車密度峰值模糊聚類算法

張正文， 鄧 薇， 廖桂生， 鞏朋成， 王兆彬

(1．湖北工業(yè)大學電氣與電子工程學院， 湖北武漢 430068；2．西安電子科技大學雷達信號處理國家重點實驗室， 陜西西安 710071；3．武漢工程大學計算機科學與工程學院， 湖北武漢 430205)

0 引言

在智能交通系統(tǒng)(ITS)中，多目標交通雷達作為道路交通輔助工具，可以監(jiān)測雷達探測區(qū)域內(nèi)全部車輛的運動狀態(tài)信息，及時掌握道路車輛信息，有利于交管部門管控道路，減少交通事故的發(fā)生，提高道路的安全指數(shù)。基于毫米波雷達的交通流量計是典型的用來監(jiān)測道路狀況的裝置，可以安裝在路側(cè)、路口紅綠燈處、天橋等視野較好的高處。雷達通過接收發(fā)射出去電磁波的回波信號，獲取道路車輛的運動信息，主要包括探測車輛的位置和速度等信息，實現(xiàn)對道路車輛運動軌跡的監(jiān)測。多目標聚類是雷達回波數(shù)據(jù)處理中關(guān)鍵的一步，快速得到準確的聚類結(jié)果可以減小聚類誤差在后續(xù)處理中產(chǎn)生的影響，減少后續(xù)跟蹤等高級算法的計算量，提高相關(guān)算法的精度。近年來，多種經(jīng)典聚類算法被應(yīng)用在交通領(lǐng)域中，包括基于密度的DBSCAN聚類算法，基于分區(qū)的-means算法和模糊C均值(FCM)算法?；诿芏确逯档木垲愃惴āＮ墨I[4]中的DBSCAN是基于空間數(shù)據(jù)點分布密度的算法，但當不同類數(shù)據(jù)相距較近時聚類效果會略差；基于分區(qū)的-means算法通過確定分類數(shù)目后，將距離作為分類指標，按照簇內(nèi)的點分布緊密且簇間的距離相對大的規(guī)則進行聚類，直至聚類結(jié)果不再更新，此方法對值較敏感，以及隨機確定的初始中心，會影響算法的收斂速度和聚類結(jié)果；FCM算法是模糊聚類算法，用隸屬度表示每個數(shù)據(jù)點屬于某簇的程度，通過求解目標函數(shù)最優(yōu)值確定聚類中心和隸屬度值。該算法具有較高的精度，但需要設(shè)置初始參數(shù)，如果參數(shù)初始化不合適，可能會影響最終聚類結(jié)果的正確性。其次，當數(shù)據(jù)樣本集較大時，算法實時性不佳。結(jié)合城市道路場景，當?shù)缆飞宪嚵髁枯^大、車輛相距很近時，雷達采樣點分布會更加密集，此時運用傳統(tǒng)FCM算法不能準確地識別相鄰車輛。意大利Rodriguez等提出了一種基于密度峰值的快速聚類算法(DPC算法)，該算法主要思想是：1) 聚類中心的密度大于鄰域密度；2) 聚類中心與其他高密度點的距離相對較大。DPC算法利用局部密度和相對距離劃分樣本點，處理過程簡單又高效。但DPC算法根據(jù)決策圖選取初始簇中心，若選取不當，將導致后續(xù)樣本點聚類錯誤。

針對以上傳統(tǒng)算法中的問題，結(jié)合毫米波雷達交通流量計中數(shù)據(jù)的特點，本文提出一種改進的基于密度峰值的FCM聚類算法：1) 對文獻[10]中DPC算法的決策圖做出改進，用改進后的決策圖確定初始聚類中心。在決策圖中使用自適應(yīng)橢圓距離代替歐式距離，并在圖中加入一條自適應(yīng)函數(shù)曲線用以自動確定初始聚類中心；2) 根據(jù)步驟1)確定的初始聚類中心計算隸屬度矩陣，將聚類中心坐標和隸屬度矩陣作為FCM算法的初始條件，使用FCM算法更新聚類中心和隸屬度，完成一次模糊聚類；3) 根據(jù)一次聚類結(jié)果計算各簇樣本點的速度中位數(shù)，將速度中位數(shù)與一次模糊聚類更新的隸屬度作為FCM算法初始條件，進行二次模糊聚類，得到最終模糊聚類結(jié)果。實驗證明，提出的算法最終得到更為精確的聚類結(jié)果。

1 基于密度峰值的聚類算法

基于密度峰值的聚類算法核心是認定簇中心滿足以下特征：1)簇中心的密度比其周圍點的密度大，即簇中心為密度峰值點；2)簇中心之間的距離比簇中心到其他點的距離更大。根據(jù)這兩個條件即可確定簇中心和簇數(shù)目。

(1)

式中為預(yù)設(shè)的截斷距離，表示任意兩點間的距離，當滿足<0時，()=1，否則()=0。式(1)的物理意義為統(tǒng)計以點為中心，為半徑的圓內(nèi)樣本點的個數(shù)，個數(shù)即代表密度大小。除了利用公式(1)中截斷核計算局部密度外，還可以用高斯核計算局部點密度，其定義如下：

(2)

由公式(2)可知，高斯核表示的點密度為連續(xù)值，不會出現(xiàn)截斷核密度中不同數(shù)據(jù)點具有相同密度值的現(xiàn)象，更有利于后續(xù)的數(shù)據(jù)處理。DPC算法中，在得到任意點的局部密度后，求各點的最小距離。最小距離由任意點與其他高密度點間的最小距離確定：

(3)

計算得到任意樣本點的局部密度和最小距離后，以每個點的為橫坐標，為縱坐標畫如圖1(a)所示的二維決策圖，用戶在決策圖中，根據(jù)分布情況手動選擇聚類中心點，通常將同時具有較大和較大的點定義為聚類中心，其余點分配到比自身密度高且距離最近的聚類中心所屬的簇中。

圖1(a)中橫坐標為樣本點密度，縱坐標為最小距離，紅色標記點為選定的初始聚類中心，藍色點為其他樣本點。圖1(b)是所有樣本點分類后的二維坐標圖，不同顏色的點為不同簇，黑色圓點是由二維策略圖確定的聚類中心。

DPC算法需要在策略圖中手動確定聚類中心，導致算法的運行效率低，在確定聚類中心后，僅根據(jù)各樣本點到聚類中心的距離進行最終聚類，導致聚類結(jié)果準確率低。因此，本文提出的算法對DPC算法中的決策圖進行改造，使用自適應(yīng)橢圓距離代替歐式距離計算，進一步計算得到更可靠的和，并在決策圖中引入自適應(yīng)函數(shù)曲線自動判定聚類中心，提高聚類中心確定的效率。

圖1 密度峰值聚類算法過程圖

2 提出的算法

針對傳統(tǒng)DPC算法中聚類中心的確定需要人工操作、聚類僅靠距離這一判定條件，本文對DPC算法進行改造，并使用FCM算法進行模糊聚類。首先，改進DPC算法決策圖，使用自適應(yīng)橢圓距離代替歐氏距離，計算樣本點的局部密度和最小距離并將二者作為橫、縱坐標，畫決策圖，在決策圖中添加一條自適應(yīng)函數(shù)曲線，以自動確定初始聚類中心；接著，將初始聚類中心信息代入FCM算法，根據(jù)距離信息構(gòu)造目標函數(shù)，做一次模糊聚類；最后，在一次模糊聚類結(jié)果基礎(chǔ)上，根據(jù)每簇的速度信息構(gòu)造目標函數(shù)，做二次模糊聚類，以修正一次聚類結(jié)果。

2.1 初始聚類中心的確定

(4)

此計算方法設(shè)置，兩個變量參數(shù)來調(diào)整數(shù)據(jù)之間的距離相關(guān)性，用來作為自適應(yīng)橢圓距離的長軸、短軸參數(shù)，其分別為

(5)

(6)

其中，和分別由兩點的橫、縱坐標差決定：

(7)

此式通過自然數(shù)e將橫、縱坐標差值轉(zhuǎn)化為值域為[0,1]的變量，當橫、縱坐標差變化時，和成反比例變化，接著公式(6)可自適應(yīng)地調(diào)整和大小，從而確定長軸、短軸參數(shù)。假設(shè)縱坐標差值大于橫坐標差值，由公式(6)可知此時為長軸參數(shù)，為短軸參數(shù)。當橫、縱坐標差較大時，由公式(7)可知自適應(yīng)橢圓距離在計算過程中發(fā)生數(shù)量級變化，從而增大距離差異性，進一步使得最小距離的差異顯著，有利于策略圖中聚類中心的準確判斷。

(8)

其中，表示式(4)所求的任意兩點間的橢圓距離，表示截斷距離。截斷距離需要通過設(shè)置一個百分比來確定，取值一般為1%～2%，本文中取2%。確定截斷距離前，需要先根據(jù)式(4)計算得到所有點的橢圓距離，做升序排列，過濾掉前2%的值，此時的最小值定義為截斷距離。

計算各點密度后，需要根據(jù)密度來確定任意樣本點的最小距離。這里的最小距離指的是，距離樣本點最近且密度大于的樣本點，此時兩點的橢圓距離為的最小距離；若不存在密度大于的點，則找出距離最遠的樣本點，將此時的標記為最小距離，其數(shù)學表示為

(9)

(10)

(11)

圖2 加入冪函數(shù)曲線的決策圖

由圖2可容易確定位于曲線()上方的點滿足密度大且最小距離大，即為所求的初始簇中心；位于曲線()下方的點為其他點，需要進一步做聚類處理。

2.2 結(jié)合速度的FCM算法

FCM算法是一種基于對目標函數(shù)優(yōu)化的數(shù)據(jù)聚類算法，其聚類結(jié)果是每個樣本點關(guān)于簇中心的隸屬度和更新的簇中心。其中隸屬度是一個模糊概念，表示的是某一樣本點屬于某簇的程度，取值范圍為[0,1]，任一樣本點關(guān)于所有簇中心的隸屬度之和為1。在計算過程中隸屬度和簇中心會不斷更新，直至簇內(nèi)加權(quán)誤差平方和最小，得到最終的聚類劃分。

(12)

由隸屬度定義可知，任意樣本點關(guān)于聚類中心的隸屬度之和為1，即

(13)

(14)

式中‖-‖表示樣本點集中第點到第個聚類中心的距離；表示模糊指數(shù)，其大小代表模糊程度，值越大表示分類的模糊性越大，反之越小，范圍為[15,25] ，通常取2，在本文中亦取2。將式(14)結(jié)合約束式(13)，構(gòu)造拉格朗日函數(shù)為

(15)

為求取目標函數(shù)的極值，需要將函數(shù)分別對和求偏導，并令偏導為0，即

(16)

求解式(16)得到式(17)，由式(17)關(guān)系式可知模糊隸屬度與聚類中心之間存在一定的相關(guān)性，因此FCM算法的和初始值是十分重要的。

(17)

在計算迭代過程中，算法的目標函數(shù)值會不斷變化，并最終趨于穩(wěn)定。當更新的目標函數(shù)值與上一次的迭代值滿足迭代停止條件時，結(jié)束計算，輸出此時的、。迭代停止條件：

=-<

一是開展新進公務(wù)員培訓。堅持每年對新錄用公務(wù)員、轉(zhuǎn)業(yè)干部等開展國土資源專業(yè)法律法規(guī)知識培訓。以學法用法為載體，夯實國土干部法治理念。據(jù)統(tǒng)計，省廳每年舉辦各類培訓班二十多期，這些師資主要來自各相關(guān)業(yè)務(wù)工作領(lǐng)域，由處室負責人或者業(yè)務(wù)骨干講解，通過這種“傳、幫、帶”的教育培訓，新進干部受益非淺，為他們及時轉(zhuǎn)換角色適應(yīng)工作打下了基礎(chǔ)，反響較好。

(18)

式中，為設(shè)定的最小更新量，本文取0.000 1。最大迭代次數(shù)=1 000，此數(shù)值可根據(jù)實際情況調(diào)整，經(jīng)實驗驗證，迭代次數(shù)一般在100以內(nèi)，迭代結(jié)束便得到一次聚類結(jié)果。

在不斷的實驗中發(fā)現(xiàn)來自同一輛車的不同采樣點速度差值極小，而來自不同車的速度差異明顯。根據(jù)這一特性，結(jié)合一次聚類結(jié)果，使用模糊聚類的思想進行二次聚類以提高聚類精度。首先，提取每簇樣本點的速度信息，確定每簇的速度中位數(shù)(=1,2,…，)。這里采用每簇的速度中位數(shù)而不使用均值是因為，經(jīng)實驗發(fā)現(xiàn)一次聚類結(jié)果中存在誤判的點但數(shù)目不多，而同一輛車的采樣點速度差值極小，因此選用中位數(shù)更具有代表性、更合理。利用一次聚類結(jié)果更新的，構(gòu)造目標函數(shù)如下：

(19)

其中，模糊指標取2，將約束條件式(13)代入目標函數(shù)中，與一次聚類相同使用拉格朗日乘子法，解得最優(yōu)解為

(20)

根據(jù)采樣點的速度特征，設(shè)定此部分的迭代終止條件是，同一簇內(nèi)任意兩點間的速度差值小于，即

|-|<, ?,且≠

(21)

滿足式(21)終止迭代后，得到更新的，確定最終的聚類結(jié)果。本文實驗中取05 m/s。最終，由兩次模糊聚類得到的是在位置、速度上具有強相關(guān)的聚類結(jié)果。

綜上，本文提出的一種改進的道路行車密度峰值模糊聚類算法具體步驟如下：

輸出：更新的

a) 由公式(4)得到，并代入式(7)計算各點的密度，根據(jù)式(9)得最短距離；

c) 以為橫軸，為縱軸畫二維決策圖，確定曲線()上方的點為初始簇中心；

d) 計算和各樣本點到初始簇中心的距離，將二者作為初始值代入FCM算法進行迭代計算；

e) 迭代更新隸屬度和聚類中心；

f) 重復(fù)e)，直至滿足迭代終止條件式(18)，輸出一次聚類結(jié)果和；

g) 提取各簇樣本點的，確定簇內(nèi)樣本點的速度中位數(shù)；

h) 根據(jù)式(20)迭代更新和；

i) 重復(fù)h)，直至同簇內(nèi)任意兩點的速度滿足式(21)時，迭代終止；

j) 輸出更新的和，得到二次模糊聚類結(jié)果。

3 仿真實驗

3.1 整體流程

本文采用77 GHz毫米波雷達，工作波形為線性調(diào)頻連續(xù)波，其發(fā)射天線和接收天線都為4個，最大可同時探測128個移動車輛目標。采集過程中雷達工作參數(shù)如表1所示，每個場景采集10幀ADC原始數(shù)據(jù)，數(shù)據(jù)傳輸速率為20.1 Mbit/s。

表1 雷達工作參數(shù)及理論性能

由表1參數(shù)可計算出一幀的數(shù)據(jù)量大小為發(fā)射天線×接收天線×距離維FFT點數(shù)×速度維FFT點數(shù)×2=8 192 Kbit。采集的數(shù)據(jù)為二進制格式，保存在“.dat”文件中，數(shù)據(jù)文件大小可以檢驗采集過程是否存在數(shù)據(jù)丟失。采集數(shù)據(jù)過程中有錄像可以和算法處理結(jié)果進行對比。處理數(shù)據(jù)的環(huán)境為MATLAB R2018b，計算機運算條件為Windows 10， 64-bit，8G內(nèi)存。

數(shù)據(jù)處理流程如下：

1) 將數(shù)據(jù)文件讀入MATLAB經(jīng)過傅里葉變換得到樣本點的位置、速度信息；

2) 對得到的數(shù)據(jù)信息做濾波、恒虛警等處理濾除雜波；

3) 將去除雜波后的樣本點位置、速度信息代入第三部分提出的算法中，經(jīng)兩次模糊聚類，得到最終高精度的聚類結(jié)果。

3.2 實驗結(jié)果對比

為驗證本文提出的算法，用雷達板在城市天橋上采集道路上行駛車輛的數(shù)據(jù)，對采集的原始數(shù)據(jù)經(jīng)預(yù)處理后做聚類處理。本部分驗證FCM算法、DBSCAN聚類算法和本文提出的聚類算法在3個不同場景下的聚類處理結(jié)果。

場景1： 多個小轎車相距較近。

以圖3所示的道路場景1為對照，處理相應(yīng)的雷達數(shù)據(jù)，圖4給出了不同聚類算法對場景1的處理結(jié)果。其中，圖4(a)給出了經(jīng)濾波處理后的采樣點，共53個。圖4(b)為DBSCAN聚類算法處理結(jié)果，其中最小半徑設(shè)定為2.2，簇內(nèi)最小數(shù)目為3，共識別出6簇數(shù)據(jù)。圖4(c)為FCM算法處理結(jié)果，最終得到7簇數(shù)據(jù)和各簇中心。圖4(d)為DPC算法處理結(jié)果，由策略圖確定初始聚類中心后，根據(jù)各點到聚類中心的距離進行分類，共得到3簇結(jié)果。圖4(e)為本文提出的算法處理結(jié)果，得到7簇數(shù)據(jù)和各簇中心。

圖3 道路場景1

圖4 不同聚類算法對場景1的處理結(jié)果

對比圖4(b)和圖4(c)可知，DBSCAN算法和FCM算法能區(qū)分大部分車輛目標，但均不能區(qū)分位于道路前方相距很近的兩輛車。圖4(d)由于聚類中心數(shù)目誤差較大，不能正確聚類道路車輛。由圖4(e)可知，本文提出的算法能很好地區(qū)分車輛目標，聚類正確。

場景2： 公交車與小轎車相距較近。

以圖5所示的道路場景2為對照，處理相應(yīng)的雷達數(shù)據(jù)。圖6給出不同聚類算法對場景2的處理結(jié)果。其中，圖6(a)是經(jīng)濾波處理后的采樣點，共39個。圖6(b)為DBSCAN聚類算法處理結(jié)果，最小半徑設(shè)定為2.5，簇內(nèi)最小數(shù)目為3，共識別出5簇數(shù)據(jù)。圖6(c)為FCM算法處理結(jié)果，最終得到6簇數(shù)據(jù)和各簇中心。圖6(d)為DPC算法處理結(jié)果，共識別出3簇數(shù)據(jù)。圖6(e)為本文提出的算法處理結(jié)果，得到5簇數(shù)據(jù)和各簇中心。

圖5 道路場景2

圖6 不同聚類算法對場景2的處理結(jié)果

圖6(b)中DBSCAN聚類算法的參數(shù)比場景1中參數(shù)大，是為了兼顧大目標，但從聚類結(jié)果可知，由于公交車目標過大，分布稍遠的點會被歸為噪聲點，影響聚類正確率。圖6(c)中FCM算法將公交車大目標分為了兩個小目標，圖6(d)為DPC算法不能正確聚類道路車輛，簇數(shù)目相比其他算法誤差最大，而本文提出的算法如圖6(d)所示，可以做到正確聚類。

場景3： 多個小轎車相距較近，公交車與小轎車相距較近。

以圖7所示的道路場景3為對照，處理相應(yīng)的雷達數(shù)據(jù)。圖8給出了不同聚類算法對場景3的處理結(jié)果。其中，圖8(a)給出了經(jīng)濾波處理后的采樣點，共58個。圖8(b)為DBSCAN聚類算法處理結(jié)果，其中最小半徑設(shè)定為2.5，簇內(nèi)最小數(shù)目為3，共識別出6簇數(shù)據(jù)。圖8(d)為DPC算法聚類結(jié)果，共識別出4簇數(shù)據(jù)。圖8(c)和圖8(e)分別為FCM算法、本文提出的算法處理結(jié)果，均得到8簇數(shù)據(jù)和各簇中心。

圖7 道路場景3

圖8 不同聚類算法對場景3的處理結(jié)果

對比圖8(b)和圖8(c)可知，DBSCAN算法和FCM算法能區(qū)分大部分車輛目標，但均不能區(qū)分位于道路前方相距很近的兩輛車。圖8(d)的DPC算法由于聚類中心的判斷錯誤，導致最終聚類結(jié)果效果差。由圖8(e)可知，本文提出的算法能很好地區(qū)分車輛目標，聚類正確。

圖8(b)中DBSCAN聚類算法對于相距較近的小轎車容易聚類成一個目標，并且由于半徑的限制，不能完整識別出場景中的公交車大目標。由圖8(c)可知，F(xiàn)CM算法能夠識別出各個車輛，但仍存在個別誤判的樣本點，精確度不夠。DPC算法對于相距較近的車輛樣本點聚類效果差。本文提出的算法在FCM算法的效果上做出優(yōu)化，能夠識別公交車的全部樣本點，減少了誤判的樣本點。

根據(jù)以上3個特殊場景的聚類結(jié)果對比可知，DBSCAN聚類算法根據(jù)密度分類時，對相距較近和目標較大的車輛聚類效果較差。同時，受半徑參數(shù)的約束，不能在兼顧小目標的前提下完整識別大目標。傳統(tǒng)FCM算法聚類精度較高，能基本識別出道路上的大小車輛目標，但會有個別樣本點的誤判。DPC算法的初始聚類中心的確定存在誤差，導致最終結(jié)果誤差較大。本文提出的算法在FCM算法的基礎(chǔ)上使用速度對數(shù)據(jù)點再次聚類，明顯聚類效果更好。

最后，用指標來衡量各個算法的聚類準確度，定義為

(21)

式中，表示第簇中正確聚類的采樣點個數(shù)，表示簇的總個數(shù)，表示處理的原始采樣點個數(shù)。取值越高說明聚類準確度高，值為1時說明聚類結(jié)果完全準確。圖9給出了選取的100幀采集數(shù)據(jù)，使用5種聚類算法的聚類精度比較，其中改進的FCM算法指本文提出的一次模糊聚類算法，即不作二次模糊聚類處理。由圖9可以看出，改進的FCM算法比FCM算法聚類精度高，但存在不穩(wěn)定的問題，本文提出的算法在真實公路場景中聚類精度更高且效果最穩(wěn)定。

圖9 各聚類算法的聚類精度比較

同時對上述實驗的3個場景的算法運行時間進行比較，每個場景分別用DBSCAN算法、FCM算法、DPC算法、改進的FCM算法和本文所提算法運行100次，求取運行時間平均值，時間比較如表2所示。

表2 算法運行時間比較

由表2可知，本文提出的算法使用DPC算法初始化后再做模糊聚類使得時間復(fù)雜度增加，耗時相對較長，但在場景3數(shù)據(jù)較大的情況下，本文所提算法與各算法處理時間接近。同時，本文采用結(jié)合速度信息的二次模糊聚類處理，用較小的時間消耗獲取更高、更穩(wěn)定的聚類正確率。因此本文所提算法可以解決相鄰車輛聚類結(jié)果不準確的問題，具有更高的準確度，在之后的工作中需要優(yōu)化算法減少運行時間，使其在時間上具有明顯優(yōu)勢。

4 結(jié)束語

本文提出的算法根據(jù)道路場景的車輛毫米波雷達數(shù)據(jù)特征，首先，使用改進的DPC算法，采用自適應(yīng)橢圓距離繪制決策圖，找出密度峰值點確定為初始聚類中心。接著，根據(jù)初始聚類中心計算初始隸屬度矩陣，將二者代入FCM算法中，迭代計算得到一次聚類結(jié)果。最后，根據(jù)道路中每輛車的速度信息特點，構(gòu)造關(guān)于速度的模糊目標函數(shù)，對一次聚類結(jié)果進行修正，迭代計算得到最終的聚類結(jié)果。實驗結(jié)果表明，本文算法能有效解決城市道路車輛相距很近導致的目標聚類存在較大誤差的問題，具有精度高、魯棒性強的優(yōu)點。