自適應(yīng)DBSCAN算法在快速落點預(yù)報中的應(yīng)用研究*

陶鶴丹 項樹林 吳詩帆

（91550部隊 大連 116000）

1 引言

在高空飛行器飛行任務(wù)中，落點預(yù)報結(jié)果是判斷實時飛行器飛行態(tài)勢，實施安控的重要依據(jù)，依靠有限的測量數(shù)據(jù)提高落點預(yù)報的精度與可靠性至關(guān)重要，這就需要使用高效聚類算法。落點預(yù)報往往基于不同設(shè)備測量的多組數(shù)據(jù)，這些數(shù)據(jù)一般呈散點狀態(tài)分布，若默認(rèn)測量設(shè)備誤差為單純的機器誤差，可以認(rèn)為任一設(shè)備的測量數(shù)據(jù)均為圍繞實際落點產(chǎn)生的隨機分布，服從概率統(tǒng)計規(guī)律。因此，利用可靠的聚類算法，獲取盡可能精確的落點統(tǒng)計信息是可行的。

在現(xiàn)今軍內(nèi)飛行任務(wù)中，多采用K-means聚類算法進(jìn)行落點統(tǒng)計，但K-means聚類算法具有只適用于凸數(shù)據(jù)集、受異常點影響較大、必須提前確定聚類簇數(shù)等局限性［1］，因此，本文提出了使用DBSCAN 算法應(yīng)用于快速落點預(yù)報。DBSCAN 密度聚類算法是經(jīng)典聚類算法之一，通過判斷樣本分布的疏密程度區(qū)分獲取類別簇。與K-means 聚類算法相比，DBSCAN算法有以下幾點主要優(yōu)點：

1）可以對任意形狀的稠密數(shù)據(jù)進(jìn)行聚類［2］。

2）對樣本集的噪聲點不敏感，可以主動發(fā)現(xiàn)并排除測量數(shù)據(jù)中的異常點［3］。

3）無需提前確定簇數(shù)，對于未知簇數(shù)樣本亦能聚類［4］。

這些特性都很好地適用于樣本集復(fù)雜、異常點較多、殘骸數(shù)目不定的快速落點預(yù)報。但是，工程實踐表明，DBSCAN算法在應(yīng)用中存在以下缺點：

1）通過設(shè)定的鄰域半徑（Eps）與鄰域內(nèi)最少樣本的數(shù)量（minPts）來區(qū)分高密度區(qū)域與低密度區(qū)域［5］，所以，DBSCAN 算法對于全局參數(shù)的選取十分敏感。常規(guī)DBSCAN 算法選取參數(shù)依靠人工干預(yù)，在密度分布不均或先驗信息少等情況下，很難選取較優(yōu)的參數(shù)組合，很可能出現(xiàn)聚類錯誤甚至聚類失敗的情況［6］，本文旨在解決該問題。

2）樣本集較大時，聚類收斂時間長。可以通過KD樹等限制樣本數(shù)量的方法進(jìn)行優(yōu)化［7］。

3）聚類間距相差較大、疏密特征不明顯時，聚類質(zhì)量較差。

鑒于此，本文依據(jù)實際任務(wù)中快速落點預(yù)報的算法需求，分別基于樣本集自身數(shù)據(jù)特征與核密度估計，在實測落點數(shù)據(jù)集中實現(xiàn)并分析了兩種自適應(yīng)合理設(shè)定DBSCAN算法全局參數(shù)的方法，有效解決了DBSCAN算法人工干預(yù)的問題。

2 常規(guī)DBSCAN算法原理

DBSCAN 算法的前提為假定樣本集的類別可以通過樣本分布疏密程度來區(qū)分［8］。該算法通過確定鄰域半徑Eps與最小閾值minPts大小來確定樣本集中的核心對象，通過遍歷找到所有核心對象的全部密度可達(dá)對象，從而得到每一核心對象最大密度相連的樣本集合，自動確定最終的類別簇［9］。

算法流程具體如下：

1）首先通過計算樣本集D中任意兩點的距離，通過距離度量在樣本集中找到全部滿足預(yù)設(shè)條件的核心對象xi，即滿足xi為圓心以Eps為半徑的鄰域內(nèi)包含的樣本數(shù)目滿足N(xi)≤minPts，將xi加入核心對象集合C，初始化聚類簇數(shù)k=0，未訪問樣本集T=D；

2）判斷當(dāng)前核心對象集合C是否為空，若核心對象集合為空則進(jìn)入步驟6），否則繼續(xù)步驟3）；

3）在核心對象集合C中，任意選取一核心對象i，初始化當(dāng)前簇核心對象隊列Ck={i}，初始化簇序號k=k+1，初始化當(dāng)前簇樣本集合Wk={i}，更新未訪問樣本集合T=T-{i}；

4）若當(dāng)前簇核心對象隊列Ck=φ，則認(rèn)定當(dāng)前聚類簇Wk生成完畢，更新核心對象集合C=C-Wk，轉(zhuǎn)入步驟2），否則更新核心對象集合后繼續(xù)步驟5）；

5）在當(dāng)前簇核心對象隊列Ck中取出任一核心對象i'，在鄰域半徑Eps范圍內(nèi)找出全部的子樣本集，將該子樣本集與未訪問數(shù)據(jù)求交集，將交集結(jié)果Δ 更新至當(dāng)前簇樣本集合，再將其從未訪問樣本中刪除，更新當(dāng)前簇核心對象隊列Ck=Ck∪(Δ ∩C)-i'，轉(zhuǎn)到步驟4）；

6）此時輸出的結(jié)果W={W1，W2，…，Wk}即為簇劃分結(jié)果，根據(jù)劃分的結(jié)果，使用K-means 算法得到每簇中心點，即落點預(yù)報中統(tǒng)計得到的落點位置。

3 兩種自適應(yīng)DBSCAN算法

3.1 基于樣本集數(shù)據(jù)特征確定全局參數(shù)

該種方法依據(jù)類中樣本的距離計算及統(tǒng)計確定，算法流程如下：

1）首先使用傳統(tǒng)DBSCAN 算法對數(shù)據(jù)集進(jìn)行簡單聚類，得到聚類簇數(shù)k與聚類結(jié)果{W1，W2，…，Wk}；

2）在類Wi中，計算任意兩點之間的距離，得到距離集合Di；

3）統(tǒng)計集合Di中的最大值與最小值，求其差值Δ，將Δ 劃分為t個區(qū)間；

4）求出每個區(qū)間中包含的樣本數(shù)目，確定包含最多樣本數(shù)目的區(qū)間，將該區(qū)間的距離中心值確定為該類的Epsi；

5）確定Epsi后，求出該類中全部樣本距離在Epsi范圍內(nèi)的樣本數(shù)量，對得到的數(shù)量矩陣使用K-means聚類，確定中心點設(shè)定為該類的minPtsi；

6）判斷是否遍歷過全部類簇，若否則轉(zhuǎn)至步驟2），若是繼續(xù)步驟7）；

7）選取各類的minPtsi的最大值作為最終的minPts，即各類對應(yīng)的參數(shù)值為（Epsi，max(minPtsi)），在聚類時首先判斷所屬一級類簇，自適應(yīng)調(diào)整參數(shù)后確定最終類簇。

3.2 基于核密度估計確定全局參數(shù)

該種方法依據(jù)核心平滑密度估計確定，核密度估計是刻畫數(shù)據(jù)分布特征，有效檢測出噪聲點的一種非參數(shù)方法，原理為假定待聚類樣本集中的樣本都是獨立隨機的，且屬于某一未知概率密度函數(shù)，其分布函數(shù)為f(x)，那么，該樣本集的核密度估計值為

核函數(shù)與光滑參數(shù)的選取均會影響核密度估計的精確性，根據(jù)大量研究表明，核函數(shù)對于精度的影響遠(yuǎn)沒光滑參數(shù)的影響大，可以根據(jù)實際需求選擇核函數(shù)，本文選用復(fù)雜度較低的高斯核函數(shù)。應(yīng)用于聚類時，樣本集即為所有樣本之間的距離矩陣，全局參數(shù)Eps即為光滑參數(shù)值，為使聚類結(jié)果最佳，需要將光滑參數(shù)值設(shè)置在一定范圍內(nèi)，根據(jù)文獻(xiàn)［10］，最佳的光滑系數(shù)如下式所示：

為降低計算復(fù)雜度，在樣本方差較低時，采用Silverman提出的拇指法則［11］，方差對應(yīng)的正態(tài)密度代替函數(shù)f''，使用樣本方差代替σ，得到Eps值為

將所有樣本半徑為Eps的空間內(nèi)存在的對象數(shù)Pi和的平均值定義為minPts，即為

3.3 仿真分析

在飛行測控過程中，為了實時測量信息準(zhǔn)確、有效，通常會在航區(qū)范圍內(nèi)布設(shè)大量的測量設(shè)備對飛行目標(biāo)進(jìn)行測量，主要包括連續(xù)波雷達(dá)、脈沖雷達(dá)以及GPS 等，根據(jù)設(shè)備測量體制不同，使用單臺設(shè)備或幾臺設(shè)備組合形成多種類型的測量方案，可以獲得多組落點預(yù)報數(shù)據(jù)。依據(jù)裝備組合形成的測量方案，可以劃分為高精度的交匯測量方案和精度稍差的單站定位測量方案。前者以連續(xù)波雷達(dá)交匯測量、GPS 為主，后者以脈沖雷達(dá)單站定位為主［12］。各種精度類型的測量數(shù)據(jù)，可以計算形成多組落點預(yù)測值，因此，最后參與統(tǒng)計分析的落點預(yù)測值是不同組合、不同精度值的混合樣本值。

為了驗證本文算法，進(jìn)行仿真試驗與對比分析，本文涉及算法均采用Matlab 進(jìn)行實現(xiàn)，采用數(shù)據(jù)集均使用某次任務(wù)實測單一落點數(shù)據(jù)，數(shù)據(jù)均經(jīng)過脫密清洗處理，該次任務(wù)的實際落點坐標(biāo)為（98.2940，35.3766）。在下文中，基于樣本集數(shù)據(jù)特征確定全局參數(shù)的方法簡稱為方法1，基于核密度估計確定全局參數(shù)的方法簡稱為方法2。

3.3.1 高精度數(shù)據(jù)集仿真分析

首先針對某高精度跟蹤設(shè)備的落點測量結(jié)果進(jìn)行仿真聚類，該種數(shù)據(jù)集特點為數(shù)據(jù)精度較高，聚集性較強，聚類結(jié)果的準(zhǔn)確度主要受設(shè)備誤差及個別異常點影響，仿真得到聚類結(jié)果如表1 與圖1。

圖1 高精度設(shè)備測量數(shù)據(jù)聚類結(jié)果

表1 高精度設(shè)備測量數(shù)據(jù)聚類結(jié)果

通過表1 可知，由于該數(shù)據(jù)集聚集程度較高，疏密特征明顯，三種方法的聚類計算結(jié)果精度均較高，但通過圖1（a）～（c）三張圖對比可以看出，常規(guī)DBSCAN 算法受噪聲點影響較大，而兩種自適應(yīng)DBSCAN 算法在仿真中雖采用了不同的參數(shù)組合，但是所得聚類結(jié)果相近，能夠主動發(fā)現(xiàn)并排除噪聲點，抗干擾能力強，統(tǒng)計落點與實際落點十分接近，精度均較常規(guī)DBSCAN算法有所提高。

3.3.2 低精度數(shù)據(jù)集仿真分析

下面針對某型單站低精度跟蹤設(shè)備的測量數(shù)據(jù)進(jìn)行聚類，該型數(shù)據(jù)集的特點是數(shù)據(jù)質(zhì)量較低，隨機誤差較大，落點散布分散，聚集性較差，對聚類算法考驗較大，但可以盡可能多地保留數(shù)據(jù)特征。仿真得到聚類結(jié)果如表2與圖2。

圖2 低精度設(shè)備測量數(shù)據(jù)聚類結(jié)果

表2 低精度設(shè)備測量數(shù)據(jù)聚類結(jié)果

根據(jù)表2 可知，低精度數(shù)據(jù)集對全局參數(shù)選擇的要求更為苛刻，常規(guī)DBSCAN算法依靠人工干預(yù)極易導(dǎo)致聚類失敗、無法聚類，必須使用算法進(jìn)行優(yōu)化。通過圖2（a）可以看出，對于數(shù)據(jù)聚集程度較弱的數(shù)據(jù)集，使用方法1 確定全局參數(shù)進(jìn)行聚類依舊可以得到較高精度的聚類結(jié)果，縮小了由于測量誤差導(dǎo)致的對落點計算的影響。而通過圖2（b）可以看出，方法2 確定全局參數(shù)受數(shù)據(jù)聚集程度影響較大，會將一些可用數(shù)據(jù)錯誤的聚類成了其他類別，導(dǎo)致可用數(shù)據(jù)缺失，破壞分布的平衡性，導(dǎo)致聚類結(jié)果偏差較大。

可以得到結(jié)論：

1）數(shù)據(jù)聚集程度對DBSCAN算法影響較大，數(shù)據(jù)聚類間距較大會大幅降低DBSCAN算法的準(zhǔn)確性。

2）對于該類疏密特征不鮮明的數(shù)據(jù)集，使用常規(guī)DBSCAN 算法極易失敗，無法保證工程應(yīng)用，而兩種自適應(yīng)改進(jìn)算法均能得到聚類結(jié)果。兩種方法中，方法2 受數(shù)據(jù)聚集程度影響更大，容易導(dǎo)致個別樣本錯誤聚類。在工程實踐中，對于該類數(shù)據(jù)集的聚類，建議使用方法1，能得到相對準(zhǔn)確的結(jié)果。

3.3.3 混合精度數(shù)據(jù)集仿真分析

在實際的飛行任務(wù)中，高精度測量設(shè)備測量方式往往以應(yīng)答為主，測量的準(zhǔn)確性與快速性依賴于彈上設(shè)備，而低精度測量設(shè)備以反射為主，排除了這類依賴造成的風(fēng)險。為減少風(fēng)險、提高精度、盡可能獲取更加全面的數(shù)據(jù)特征，往往會使用低精度測量數(shù)據(jù)作為高精度測量設(shè)備數(shù)據(jù)的補充，得到不同組合、不同精度值的混合樣本，不同的測量設(shè)備誤差混雜會導(dǎo)致數(shù)據(jù)集復(fù)雜度變高，對聚類方法的要求也更高。為檢驗本文方法在混合數(shù)據(jù)集中的聚類效果，將兩種測量精度差異較大的測量設(shè)備對同一飛行目標(biāo)的測量數(shù)據(jù)混合，進(jìn)行極端情況下的檢驗，仿真結(jié)果如表3與圖3。

圖3 混合精度設(shè)備測量數(shù)據(jù)聚類結(jié)果

表3 混合精度設(shè)備測量數(shù)據(jù)聚類結(jié)果

根據(jù)表3可知，在混合數(shù)據(jù)集環(huán)境下，常規(guī)DBSCAN 算法受低精度樣本集影響較大，聚類精度較低，而兩種自適應(yīng)確定全局參數(shù)的DBSCAN算法仍能取得相對較高的落點計算精度。通過圖2（b）與圖2（c）可以看出，兩種方法的聚類結(jié)果均受低精度樣本集影響較小，方法1 聚類更為嚴(yán)格，僅選取數(shù)據(jù)集中最密集部分進(jìn)行聚類，拋棄的噪聲點更多，雖說在本次仿真中取得的聚類結(jié)果更為精確，但易產(chǎn)生遺漏數(shù)據(jù)特征的情形，方法2 聚類相對寬松，雖說在本次試驗中聚類精度低于方法1，但是可以盡可能地保留樣本集的多種數(shù)據(jù)特征，在應(yīng)用環(huán)境中，要根據(jù)實際情況進(jìn)行選擇。

可以得到結(jié)論：

1）在高低精度混合數(shù)據(jù)集的情況下，兩種自適應(yīng)改進(jìn)算法均能較大幅度提高常規(guī)DBSCAN 算法的聚類精度。

2）在快速落點預(yù)報的工程實踐中，對于此類高低精度差異較大的混合數(shù)據(jù)集，為了盡可能地保留低精度測量設(shè)備的數(shù)據(jù)樣本特征，降低設(shè)備故障等意外因素可能造成的風(fēng)險，建議使用方法2。

通過多次仿真，可以得到三種方法針對快速落點預(yù)報中不同精度類型的數(shù)據(jù)集中的聚類精度效果對比如表4，在工程應(yīng)用中，要依據(jù)上文的分析結(jié)論，根據(jù)參試設(shè)備的實際精度情況進(jìn)行選擇。

表4 聚類精度效果對比

4 結(jié)語

本文針對在快速落點預(yù)報應(yīng)用中K-means 聚類算法局限性較大且常規(guī)DBSCAN 算法人工選取參數(shù)困難的問題，對提出的兩種自適應(yīng)DBSCAN聚類算法進(jìn)行了研究分析，并利用實測落點測量數(shù)據(jù)進(jìn)行了仿真測試。結(jié)果證明，根據(jù)測量設(shè)備實際精度情況區(qū)分高精度、低精度、混合精度選擇自適應(yīng)DBSCAN 算法，可以得到較優(yōu)的參數(shù)組合，在復(fù)雜條件下亦能取得較好的聚類效果，統(tǒng)計落點結(jié)果較常規(guī)DBSCAN 算法精度提升較高，效率較優(yōu)，有效解決了常規(guī)DBSCAN 算法人工干預(yù)參數(shù)導(dǎo)致聚類質(zhì)量惡化的問題，且保留了常規(guī)DBSCAN算法的特性與優(yōu)點，適用于快速落點預(yù)報。但也存在不足之處，對于疏密程度不明顯的數(shù)據(jù)集的聚類準(zhǔn)確率較低，如何解決該問題仍是下一步的研究方向。