本文首發(fā)于公眾號【調(diào)皮連續(xù)波】，其他平臺為自動同步，同步內(nèi)容若有不全或亂碼，請前往公眾號閱讀。保持關(guān)注調(diào)皮哥，獲得更多雷達干貨學(xué)習(xí)資料和建議，助力大家輕松、快樂、有方向地學(xué)習(xí)雷達技術(shù)。
本文參考TI的一種適用于汽車?yán)走_的聚類算法研究和實現(xiàn).pdf文檔，原文鏈接如下：https://www.ti.com.cn/cn/lit/an/zhca739/zhca739.pdfts=1672973254109&ref_url=https%253A%252F%252Fwww.google.com.hk%252F。
由于不涉及硬件，因此本文僅對算法部分進行分析，需要用到硬件分析部分的讀者，可以直接參考原文。
1.概述
雷達接收處理包括射頻前端，基帶信號處理和后處理算法三部分：
（1）射頻前端完成高頻雷達接收信號的模擬域信號處理和數(shù)模轉(zhuǎn)換(ADC)；
（2）基帶信號處理在零中頻上完成雷達接收信號的數(shù)字信號處理(DSP)和目標(biāo)檢測；
（3）在目標(biāo)檢測之后的高層算法被統(tǒng)稱為后處理算法，如聚類(Clustering)、 關(guān)聯(lián)(Association)、跟蹤(Tracking)、分類(Classification)等。
這三部分是雷達工程師需要重視的，建議進行系統(tǒng)性地學(xué)習(xí)，多看、多思考、多動手實踐。本文主要是針對后處理算法中的一種聚類算法做分析，解決汽車?yán)走_目標(biāo)由于目標(biāo)尺寸、雷達發(fā)射系數(shù)(RCS)和檢測算法的不同所帶來的一系列問題。
聚類算法的本質(zhì)是“物以類聚，人以群分”思想，只有“志同道合”的點云才會被歸為一類。本文選取了 DBSCAN(Density-Based Spatial Clustering of
Application with Noise)作為適合汽車?yán)走_的聚類算法，重點研究了這種算法的性能和參數(shù)敏感性，并提出了一種簡單可行的參數(shù)調(diào)整(有點類似于自適應(yīng))方法。
2.算法背景
線性快速頻率調(diào)制連續(xù)波(Linear Fast FMCW) 是一種頻率隨時間快速線性變化(斜率在幾十 MHz/us)的雷達波形，由于它可以提供較高的分辨率，同時有效地解決距離-速度模糊性的問題，當(dāng)前已經(jīng)成為主流的汽車?yán)走_波形。
常用的信號處理鏈流程如下圖所示：
圖1：雷達信號處理鏈
首先，通過第一維和第二維 FFT 計算獲得目標(biāo)距離和速度，然后采用特定的角度估計算法(例如 FFT，MUSIC 等)來獲得目標(biāo)的角度，最后再通過特定的目標(biāo)檢測算法(例如 CFAR-CA、CFAR-OS 等)從噪聲中檢測獲得反射點。隨著目標(biāo)的尺寸、雷達發(fā)射系數(shù)(RCS)和檢測算法的不同，一個物體在目標(biāo)檢測后可能產(chǎn)生從幾個到幾百個不同的反射點。
如果通過聚類算法分析這些反射點的內(nèi)部結(jié)構(gòu)，將屬于同一 個物體的反射點歸為一個簇，這樣每一個檢測到的物體都形成一個簇，最后再通過對聚類以后的簇進行目標(biāo)跟蹤和分類， 可以獲得可靠的物體的距離和移動速度。
3.汽車?yán)走_聚類算法
聚類在無監(jiān)督機器學(xué)習(xí)領(lǐng)域是一個非常熱門的研究課題，近年來出現(xiàn)了許多的算法。現(xiàn)有的聚類算法可以大致分為：原型聚類(Prototype-based clustering)、密度聚類 (Density-based clustering) 和層次聚類 (Hierarchical clustering)三個類別。
（1）原型聚類
通常，假設(shè)聚類結(jié)構(gòu)能通過一組原型刻畫，在現(xiàn)實聚類算法中比較常用。通常情況下，算法先對原型進行初始化，然后對原型進行迭代更新求解。采用不同的原型表示，不同的求解方式，將產(chǎn)生不同的算法。常見的原型聚類算法有 k 均值方法 (k-means)、高斯混合聚類方法 (Mixture-of-Gaussian) ，在數(shù)據(jù)挖掘領(lǐng)域被廣泛應(yīng)用，但是這些算法都要求在聚類之前就確定輸出的簇的數(shù)量。對于汽車?yán)走_來說，也就是要求在聚類之前就確定目標(biāo)的數(shù)量，這顯然是無法做到的，因為汽車?yán)走_無法確定當(dāng)前的目標(biāo)數(shù)量是多少。
（2）層次聚類
層次聚類嘗試在不同層次對數(shù)據(jù)集進行劃分，從而形成樹形的聚類結(jié)構(gòu)。層次聚類可以采用“自下而上”的聚類策略，也可以采用“自上而下”的聚類策略。AGNES 方 法 (AGglomerative NESting)是一種常用的“自下而上”的層次聚類算法。然而這種算法面臨和原型聚類相同的問 題，也需要在聚類之前確定輸出的簇的數(shù)量，因此也無法直接應(yīng)用到汽車?yán)走_上，因此就只剩下了密度聚類。
（3）密度聚類
密度聚類(Density-based clustering)沒有其它兩種聚類的限制，不需要事先確定簇的數(shù)量。密度聚類假設(shè)簇的 結(jié)構(gòu)能通過目標(biāo)點分布的緊密程度來確定。在密度聚類中，簇被認(rèn)為是數(shù)據(jù)空間中目標(biāo)點密集的區(qū)域，在簇之間出 現(xiàn)的低密度的目標(biāo)點被認(rèn)為是噪聲. 這些簇可以有任意的形狀，并且簇內(nèi)的目標(biāo)點也可以任意分布，這一點和汽車 雷達上的檢測目標(biāo)特性十分接近。汽車?yán)走_對應(yīng)同一個目標(biāo)的檢測點之間距離接近，并且這些點的密度分布是一定 的（這個密度分布和物體的反射特性相關(guān)）。因為具備以上這些特性，密度聚類更加適合于汽車?yán)走_的應(yīng)用，DBSCAN 算法是一種常用的密度聚類算法(可以清晰地知道，DBSCAN能夠用于汽車?yán)走_的本質(zhì)原因)。
4.聚類算法指標(biāo)
一個好的聚類結(jié)果的目標(biāo)點應(yīng)該具有高的簇內(nèi)相似性和低的簇間相似性，在低維度數(shù)據(jù)集上， 聚類性能的好壞通過可視化的數(shù)據(jù)分布圖就可以直觀的看出來，但是通過度量指標(biāo)來定量地衡量聚類性能的好壞更加準(zhǔn)確。
參考文獻[2] 給出了常用的聚類性能度量 DI (Dunn Index), DBI (Davies-Bouldin Index) ，這兩種度量在原理上類似，本文選擇 DI 作為分析聚類性能的度量指標(biāo)。假設(shè)數(shù)據(jù)集???? = {??1, ??2, … , ????}被劃分成了??個簇 ?? = {??1, ??2,… , ????}, DI 的定義如下：
上式中的分母對應(yīng)的是所有簇內(nèi)目標(biāo)點之間的最大距離，分子對應(yīng)的是所有簇間目標(biāo)點之間的最小距離。顯然同于同一個數(shù)據(jù)集，一個聚類結(jié)果對應(yīng)的 DI 越大，聚類的性能越好。即：最大距離越小，說明點云越集中，則點云越相似。
5.DBSCAN算法分析
5.1 算法定義
DBSCAN算法比較容易理解，它基于一組“鄰域” (neighborhood) 參數(shù)(??, ??inPts)來刻畫樣本分布的緊密程度。給定數(shù)據(jù)集?? = {??1, ??2, … , ????}， 定義下面幾個概念：
DBSCAN 算法先任選數(shù)據(jù)集中的一個核心對象為種子 (seed), 將它的 ε-鄰域中的所有樣本加入一個簇，新加入的樣本如果是核心對象，再將這個核心對象的 ε-鄰域中的所有樣本加入本簇。通過這種遞歸搜索，將所有密度相連的樣本歸入一個簇。如果此時數(shù)據(jù)集中還有未處理的核心對象，再重復(fù)上述的過程開始一個新簇的搜索。DBSCAN
算法的偽代碼描述如下圖所示：
圖2：DBSCAN算法描述
5.2 算法代碼
讀者根據(jù)上述算法流程編寫仿真代碼應(yīng)該是不難的，這也是一名工程師必備的職業(yè)素養(yǎng)。如果實在有困難，那可以參照下面的代碼(https://blog.csdn.net/yuanshixin_/article/details/117409961)，這也是網(wǎng)友編寫的，調(diào)皮哥驗證過，好使。
clc;clear all;close all;%% 數(shù)據(jù)X1 =[5.1,3.5,1.4,0.2;%,Iris-setosa4.9,3.0,1.4,0.2;4.7,3.2,1.3,0.2;4.6,3.1,1.5,0.2;5.1,3.7,1.5,0.4;4.6,3.6,1.0,0.2;5.1,3.3,1.7,0.5;5.0,3.6,1.4,0.2;5.4,3.9,1.7,0.4;4.6,3.4,1.4,0.3;5.0,3.4,1.5,0.2;4.4,2.9,1.4,0.2;4.9,3.1,1.5,0.1;5.4,3.7,1.5,0.2;4.8,3.4,1.6,0.2;4.8,3.0,1.4,0.1;4.3,3.0,1.1,0.1;5.8,4.0,1.2,0.2;5.7,4.4,1.5,0.4;5.4,3.9,1.3,0.4;5.1,3.5,1.4,0.3;5.7,3.8,1.7,0.3;5.1,3.8,1.5,0.3;5.4,3.4,1.7,0.2;6.4,3.2,4.5,1.5;%Iris-versicolor6.9,3.1,4.9,1.5;5.5,2.3,4.0,1.3;6.5,2.8,4.6,1.5;5.7,2.8,4.5,1.3;6.3,3.3,4.7,1.6;4.9,2.4,3.3,1.0;4.9,2.4,3.3,1.0;6.6,2.9,4.6,1.3;5.2,2.7,3.9,1.4;5.0,2.0,3.5,1.0;5.9,3.0,4.2,1.5;6.0,2.2,4.0,1.0];X=X1(:,3:4);A = X;%% 觀察數(shù)據(jù)距離，估計epsilon[index,Dist] = knnsearch(A(2:end,:),A(1,:));Kdist(1) = Dist;for i = 1:size(A,1)[index,Dist] = knnsearch(A([1:i-1,i+1:end],:),A(i,:));Kdist(i) = Dist;endsortKdist = sort(Kdist,'descend');distX = 1:size(A);plot(distX,sortKdist,'r+-');grid on;%% 運行DBSCAN% parament1epsilon = 0.15;minPts = 3;[IDC,isnoise] = DBSCAN(epsilon,minPts,A);PlotClusterinResult(A,IDC,epsilon,minPts);% parament2epsilon= 0.25 ;minPts= 3 ;[IDC2,isnoise2] = DBSCAN(epsilon,minPts,A);PlotClusterinResult(A,IDC2,epsilon,minPts);function [IDC,isnoise] = DBSCAN(epsilon,minPts,X)% DBSCANC = 0;D = pdist2(X,X); % 各元素之間距離IDC = zeros(size(X,1),1);visited = false(size(X,1),1); % 訪問標(biāo)志isnoise = false(size(X,1),1); % 噪聲for i = 1:size(X,1)if ~visited(i)visited(i) = true;Neighbors = find(D(i,:)<=epsilon); % 找領(lǐng)域樣本if numel(Neighbors)<minPtsisnoise(i) = true;elseC = C + 1;[IDC,isnoise] = expandCluster(i,Neighbors,C,IDC,isnoise); % 以核心對象X(j)擴展簇endendendfunction [IDC,isnoise] = expandCluster(i,Neighbors,C,IDC,isnoise)% 針對核心對象X(i)進行擴展IDC(i) = C; % 將X(j)的領(lǐng)域元素規(guī)定為族Ck = 1;while truej = Neighbors(k);if ~visited(j)% 針對未訪問元素繼續(xù)尋找領(lǐng)域樣本visited(j) = true;Neighbors2 = find(D(j,:)<=epsilon);if numel(Neighbors2) >= minPtsNeighbors = [Neighbors,Neighbors2]; % X(j)也是核心對象endendIDC(j) = C; %k = k +1;if k > numel(Neighbors)break;endendendendfunction PlotClusterinResult(X, IDC,epsilon,minPts)figure;k=max(IDC);Colors=hsv(k);Legends = {};for i=0:kXi=X(IDC==i,:);if i~=0Style = 'x';MarkerSize = 8;Color = Colors(i,:);Legends{end+1} = ['Cluster #' num2str(i)];elseStyle = 'o';MarkerSize = 6;Color = [0 0 0];if ~isempty(Xi)Legends{end+1} = 'Noise';endendif ~isempty(Xi)plot(Xi(:,1),Xi(:,2),Style,'MarkerSize',MarkerSize,'Color',Color);endhold on;endhold off;axis equal;grid on;legend(Legends);legend('Location', 'NorthEastOutside');title(['DBSCAN Clustering (\epsilon = ' num2str(epsilon) ', MinPts = ' num2str(minPts) ')']);end
執(zhí)行效果：
圖3：DBSCAN聚類結(jié)果
5.3 參數(shù)敏感性分析
通過上述的代碼，相信讀者也能夠看出DBSCAN算法的性能對這兩個參數(shù)非常敏感，因此如何設(shè)置算法的入?yún)垲惖男Ч浅Ｖ匾斎?span style="text-align: left;">不合適的參數(shù)將會產(chǎn)生錯誤的聚類結(jié)果。
圖 4 也給出了一個在不同入?yún)⑾?DBSCAN 聚類結(jié)果的例子。在子圖(1)的原始的數(shù)據(jù)集中我們很容
易發(fā)現(xiàn)存在 5 個簇，子圖(2)的聚類結(jié)果輸出了 5 個簇，比較接近真實的場景。子圖(3)因為選取了過大的??inPts 將原本比較稀疏的原始數(shù)據(jù)集中右上角的簇錯誤地分成了 2 個簇，而子圖(4)因為選取了過小的?導(dǎo)致聚類結(jié)果中出
現(xiàn)了過多的簇劃分，并且錯誤地將原始數(shù)據(jù)集中右上角的簇當(dāng)成了噪聲。同樣通過對子圖(2),(3),(4)的聚類結(jié)果
計算的 DI 分別為 0.8323, 0.1234 和 0.1145，同樣說明子圖(2)的聚類效果比較好，而子圖(3) 和(4)的聚類效
果不太令人滿意。
圖4：DBSCAN 參數(shù)敏感性 (1)原始數(shù)據(jù)(左上角), (2)MinPts=5, ??=0.2 下聚類結(jié)果(右上角)， (3)MinPts=10, ??=0.2 下聚類結(jié)果(左下角)，(4)MinPts=5, ??=0.1 下聚類結(jié)果(右下角)
5.4 參數(shù)調(diào)整策略
大部分關(guān)于 DBSCAN 的文獻都討論的是算法本身，而很少涉及如何為算法選擇合適的參數(shù)，而從上一節(jié)的介紹中
可以看到參數(shù)的選取對聚類結(jié)果非常重要。
汽車?yán)走_使用 DBSCAN 時需要根據(jù)探測場景和目標(biāo)檢測算法的性能對 參數(shù)有針對性地進行一些調(diào)整。實踐中，通常選取一些典型的測試場景，對 DBSCAN 的入?yún)⑦M行調(diào)教以獲得期望的聚類效果，最后對不同測試場景下的理想?yún)?shù)進行綜合來確定車上實際使用的參數(shù)，比如：道路上的兩個靠近的行人不被聚類為一個簇，以及一輛汽車因為點云太稀疏不被聚類為多個簇，主要是想解決掉這個問題。
本文將提出一種創(chuàng)新的方法針對一個特定測試場景，確定最優(yōu)的??inPts和?。??inPts是區(qū)別于噪聲的一個簇內(nèi)的最少點數(shù)，在理論上噪聲和它的鄰點之間的距離要大于目標(biāo)點和它的鄰點之間的距離。
如果定義點p和它的第k個最近的鄰點之間的k近鄰距離為k_neighbor_dis(p)，理論上噪聲點的k近鄰距離要大于目標(biāo)點的k近鄰距離。如果對一個數(shù)據(jù)集中的所有點分別計算k近鄰距離并進行從大到小排序，k近鄰距離較大的一些點對應(yīng)的是噪聲，而k近鄰距離較小的一些點對應(yīng)的是簇中的目標(biāo)點。
另外，如果分別計算一個數(shù)據(jù)集中所有 點的 1 近鄰，2 近鄰，…k近鄰距離，并對近鄰距離最大的n 個點的近鄰距離分別進行平均，會發(fā)現(xiàn)這個平均值隨 著k的增加而增加，但是平均值的增量隨著k的增加而降低，會發(fā)現(xiàn)一個特定的k，超過這個k后，k + 1近鄰距離， k + 2近鄰距離…會越來越接近。
從理論上講，這個k值接近于合理的??inPts值，因為對于近鄰距離最大的 n 個點 (主要是噪聲點)，其k近鄰，k + 1近鄰， k + 2近鄰距離趨向接近，也就是對應(yīng)的k近鄰，k + 1近鄰，k + 2近鄰更 加接近于簇中的目標(biāo)點。
基于這種思想，設(shè)計了下面的??inPts搜索算法：
1) 計算數(shù)據(jù)集??中所有樣點的 1 近鄰，2 近鄰，…n 近鄰距離，并對所有的近鄰距離從大到小進行排序 ；
2) 選定一個 n 值，從 1)中得到的 1 近鄰，2 近鄰，…n 近鄰距離選擇出最大的 n 個值，并求平均值 ；
3) 計算 2)中得到的相鄰兩個平均值之間的差值，找到一個??值使得????近鄰的平均值大于?? + 1近鄰的平均值，并 且??近鄰的平均值減去?? + 1近鄰的平均值最小
4) 定義??inPts= ?? ? 1。
上述過程本質(zhì)上講就是一個用統(tǒng)計的思路，來區(qū)分噪聲和目標(biāo)點，得到二者之間的大概界限，然后把這個界限作為??inPts。
圖 5 中畫出了對于圖 4 數(shù)據(jù)集中最大的 3 個?? + 1近鄰和????近鄰的平均值之間的差值(例如圖中第一個柱狀圖對應(yīng)的是 3 個最大的 2 近鄰距離平均值減去 3 個最大的 1 近鄰距離平均值的差值)。從這張圖中我們可以發(fā)現(xiàn)?? = 6下有最小的近鄰距離增量，因此建議的??inPts設(shè)置為 5。
圖 5. 圖 4 數(shù)據(jù)集的 k+1 近鄰和 k 近鄰距離中最大 n 個數(shù)值的平均值之差(n=3)
5.5 Optics算法
??inPts談完了，我們繼續(xù)來搞?。
?決定了聚類時鄰域搜索的半徑，DBSCAN 算法中一個點的?-鄰域中的鄰點的數(shù)目大于??inPts的時候被定義為核心 節(jié)點，并且這個點和所有它的?-鄰域中的點都被歸入同一個簇。通常一個數(shù)據(jù)集越密集，聚類時選取的?應(yīng)該越小， 因此在調(diào)整?參數(shù)的時候，需要分析數(shù)據(jù)集的密度結(jié)構(gòu)。怎么分析？是一個問題。
參考文獻[3]介紹了一種 OPTICS (Ordering Points To Identify the Clustering Structure) 算法可以獲得一個數(shù)據(jù)集的密度信息。作者基于 OPTICS 算法進行了一些 改進，提出了一種更有效的?搜索的算法。作者設(shè)計的?搜索算法分為兩步：
第一步通過改進的 OPTICS 算法對數(shù)據(jù)集的密度信息進行分析，得到一個大致的?搜索區(qū)間；
第二步在第一步獲得的?搜索區(qū)中，按照一定的步長嘗試進行DBSCAN 聚類，對聚類的結(jié)果分別計算DI 進行評估，從而選擇出最優(yōu)的?。
作者給出的改進的 OPTICS 算法的偽代碼描述如圖 6 所示：
圖6：改進的 OPTICS 算法描述
對于圖 4 中的數(shù)據(jù)集，采用改進的 OPTICS 算法對樣本重新排序后輸出的包含可達距離的曲線如圖 7 所示。
圖7：圖 4 數(shù)據(jù)集采用改進的 OPTICS 算法排序輸出的可達距離
圖中的峰值突起對應(yīng)的是一個簇中樣本和其前序樣本(通常是另一個簇中的樣本) 之間的可達距離。從圖中可以直觀地發(fā)現(xiàn)，簇中樣本之間的可達距離（對應(yīng)曲線的底部）要遠遠小于簇間樣本之間的可達距離（對應(yīng)曲線的峰值突起），同時也能直觀的發(fā)現(xiàn)數(shù)據(jù)集中簇中樣本之間和簇間樣本之間的可達距離的大致范圍?？梢栽O(shè)置?搜索的大致范圍在曲線的最低峰值和底部平均值之間，比如在圖 7 中可以設(shè)置?的搜索范圍為 0.1 到 0.6 之間。
在 0.1 到 0.6 之間選擇搜索步長為 0.1，對數(shù)據(jù)集進行 DBSCAN 聚類， 并計算聚類結(jié)果的 DI，可以得到表 1 中對應(yīng)的 DI 數(shù)值。從表 1 中可以發(fā)現(xiàn)，? = 0.1時，DI 最小，而對于其他的 ?值，DI 較大且取值相同，也就是說采用這些?值的聚類效果都比較理想。
綜合本節(jié)前面的內(nèi)容，對于圖 4 數(shù)據(jù)集， 采用MinPts = 5，ε = 0.2 ? 0.6是一個比較合理的 DBSCAN 算法入?yún)?，這與圖 4 本身顯示的聚類效果一致。
其實，這里讀者可以采用MATLAB自帶的OPTICS算法模塊（具體見幫助文檔）來對上述DBSCAN代碼中自帶的數(shù)據(jù)參數(shù)進行驗證，就能夠繪制出與圖5類似的圖，用于確定DBSCAN的參數(shù)。
6.總結(jié)
DBSCAN的主要優(yōu)點有：
（1）可以對任意形狀的稠密數(shù)據(jù)集進行聚類，而K-Means之類的聚類算法一般只適用于凸數(shù)據(jù)集。
（2）可以在聚類的同時發(fā)現(xiàn)異常點，對數(shù)據(jù)集中的異常點不敏感。
（3）聚類結(jié)果沒有偏倚，而K-Means之類的聚類算法初始值對聚類結(jié)果有很大影響。
（4）DBSCAN不需要輸入類別數(shù)，而K-Means之的聚類算法需要輸入類別數(shù)。
DBSCAN的主要缺點有：
（1）如果樣本集的密度不均勻、聚類間距差相差很大時，聚類質(zhì)量較差，這時用DBSCAN聚類一般不適合。
（2） 如果樣本集較大時，聚類收斂時間較長，此時可以對搜索最近鄰時建立的KD樹或者球樹進行規(guī)模限制來改進。
（3）調(diào)參相對于傳統(tǒng)的K-Means之類的聚類算法稍復(fù)雜，主要需要對距離閾值?，鄰域樣本數(shù)閾值MinPts聯(lián)合調(diào)參，不同的參數(shù)組合對最后的聚類效果有較大影響。
參考文獻：
