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

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

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

0 引言

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

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

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

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

(1)

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

(2)

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

(3)

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

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

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

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

2 提出的算法

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

2.1 初始聚類中心的確定

(4)

此計算方法設置，兩個變量參數來調整數據之間的距離相關性，用來作為自適應橢圓距離的長軸、短軸參數，其分別為

(5)

(6)

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

(7)

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

(8)

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

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

(9)

(10)

(11)

圖2 加入冪函數曲線的決策圖

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

2.2 結合速度的FCM算法

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

(12)

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

(13)

(14)

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

(15)

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

(16)

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

(17)

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

=-<

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

(18)

式中，為設定的最小更新量，本文取0.000 1。最大迭代次數=1 000，此數值可根據實際情況調整，經實驗驗證，迭代次數一般在100以內，迭代結束便得到一次聚類結果。

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

(19)

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

(20)

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

|-|<, ?,且≠

(21)

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

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

輸出：更新的

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

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

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

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

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

g) 提取各簇樣本點的，確定簇內樣本點的速度中位數；

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

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

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

3 仿真實驗

3.1 整體流程

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

表1 雷達工作參數及理論性能

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

數據處理流程如下：

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

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

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

3.2 實驗結果對比

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

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

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

圖3 道路場景1

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

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

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

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

圖5 道路場景2

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

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

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

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

圖7 道路場景3

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

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

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

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

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

(21)

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

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

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

表2 算法運行時間比較

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

4 結束語

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