基于密度的快速DBSCAN 算法在無線電自動定位中的應用

劉曦元

（國家無線電監(jiān)測中心云南監(jiān)測站，昆明 650031）

1 DBSCAN

DBSCAN （Density-Based Spatial Clustering of Applications with Noise）是一種著名的密度聚類算法。聚類分析起源于分類學，在古老的分類學中，人們主要依靠經(jīng)驗和專業(yè)知識來實現(xiàn)分類，很少利用數(shù)學工具進行定量的分類。隨著人類科學技術的發(fā)展，對分類的要求越來越高，以致有時僅憑經(jīng)驗和專業(yè)知識難以確切地進行分類，于是人們逐漸地把數(shù)學工具引用到了分類學中，形成了數(shù)值分類學，之后又將多元分析的技術引入到數(shù)值分類學形成了聚類分析。DBSCAN 算法使用一組關于“鄰域”的參數(shù)來描述樣本分布的緊密程度。DBSCAN 算法將簇定義為密度相連的點的最大集合，能夠把具有足夠高密度的區(qū)域劃分為簇，并可在噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類。

無線電定位是通過直接或間接測定無線電信號在已知位置的固定點（岸臺）與船之間傳播過程中的時間、相位差、振幅或頻率的變化，確定距離、距離差、方位等定位參數(shù)，進而用位置線確定待定點位置（如船位）的測量技術利方法。目前而言，大部分無線電定位使用人工進行判斷，效率較低，且沒有統(tǒng)一的判斷標準。

因此，本文結合DBSCAN 算法，拓展為快速DBSCAN 算法，設計應用，通過對一定時間內(nèi)累計的無線電自動定位數(shù)據(jù)進行二次計算，去除數(shù)據(jù)噪聲點，將數(shù)據(jù)歸為簇（集合），計算中心點等，獲取精度更高更可靠的無線電定位數(shù)據(jù)。

2 軟件的總體設計

2.1 軟件架構

本應用設計使用Java 語言，采用swing 框架（Java 桌面級應用框架）和poi 插件（提供office 操作的插件），并使用MVC 的設計模式，即模型-視圖-控制的設計模式，以桌面終端的形式，提供簡易的操作。系統(tǒng)的總體結構圖如圖1所示。

圖1 系統(tǒng)架構圖

本系統(tǒng)的設計目標如下：通過讀入外部數(shù)據(jù)（excel 表格數(shù)據(jù)）進行數(shù)據(jù)建模，輸入DBSCAN 的必要參數(shù)，計算出其噪聲點、核心點、非核心點及中心點。

2.2 軟件流程結構設計

圖2 軟件流程圖

軟件啟動后，提示人工選擇數(shù)據(jù)源，然后輸入DBSCAN 算法的參數(shù)，系統(tǒng)開始進行計算，計算完成后給出計算結果。

2.3 數(shù)據(jù)類型

本文所述研究針對定位數(shù)據(jù)進行研究，即研究數(shù)據(jù)為二維的定位點數(shù)據(jù)，定位點為使用經(jīng)緯度表述的點P（x，y）。經(jīng)緯度需轉換為雙精度浮點值。輸出則為源數(shù)據(jù)的聚類結果。

注：雙精度浮點數(shù)（double）是計算機使用的一種數(shù)據(jù)類型，使用64位（8字節(jié)）來存儲一個浮點數(shù)。它可以表示十進制的15或16位有效數(shù)字，其可以表示的數(shù)字的絕對值范圍大約是：-1.79E+308-+1.79E+308。

3 快速 DBSCAN 算法詳解

3.1 簡介及定義

DBSCAN 是一種著名的密度聚類算法，它使用一組關于“鄰域”的參數(shù)來描述樣本分布的緊密程度?？焖貲BSCAN 算法使用了DBSCAN 算法的基本概念，DBSCAN 算法在使用時，需要計算其核心點與非核心點的區(qū)別，快速DBSCAN 算法減去了核心點與非核心之間的區(qū)別使程序復雜度降為O（N?。?。

對于DBSCAN 算法，給出以下的定義：

（1）Eps 鄰域：給定對象半徑Eps 內(nèi)的鄰域稱為該對象的Eps 鄰域。

（2）核心點（core point）：如果對象的Eps 鄰域至少包含最小數(shù)目MinPts 的對象，則稱該對象為核心對象。

（3）邊界點（edge point）：邊界點不是核心點，但落在某個核心點的鄰域內(nèi)。

（4）噪音點（outlier point）：既不是核心點，也不是邊界點的任何點。

（5）直接密度可達（directly density-reachable）：給定一個對象集合D，如果p 在q 的Eps 鄰域內(nèi)，而q 是一個核心對象，則稱對象p 從對象q 出發(fā)時是直接密度可達的。

（6）密度可達（density- reachable）：如果存在一個對象鏈p1， …，pi，..，pn， 滿 足 p1=p 和 pn=q，pi 是 從 pi+1 關 于 Eps和MinPts 直接密度可達的，則對象p 是從對象q 關于Eps 和MinPts 密度可達的。

（7）密度相連（density-connected）：如果存在對象O ∈D，使對象p 和q 都是從O 關于Eps 和MinPts 密度可達的，那么對象p 到q 是關于Eps 和MinPts 密度相連的。

對于快速DBSCAN 算法，給出以下定義：

圖3 定義示意圖

（1）掃描半徑（eps）：定義兩個點之間的歐幾里得距離的最大值，即Eps 鄰域的半徑，如圖3所示，如點A，B，C 的掃描半徑均為L，即最大距離，點A 與點B 的距離L1小于L，點A與點C 的距離L2大于L，則表示點B 在點A 的鄰域中，點C 不在點A 的鄰域中。

（2）集合最少點數(shù)量（minPts）：定義樣本集合中最少點的數(shù)量，少于該數(shù)目將不被認為是一個集合。

（3）噪聲點：若樣本i 所屬的集合中樣本數(shù)量少于集合最少點數(shù)量，則該樣本為一個噪聲點。

（4）中心點：在一個樣本集合中，所有樣本的橫坐標平均值和縱坐標平均值組成的點，稱其為該集合的中心點；

注：在數(shù)學中，歐幾里得距離或歐幾里得度量是歐幾里得空間中兩點間“普通”（即直線）距離。計算公式為：

3.2 計算方式

（1）獲取用于計算的外部參數(shù)（掃描半徑maxLen、最少點數(shù) minPts）。

（2）獲取所有點數(shù)據(jù)并將其封裝成（double x，double y，int type）的類型（double 為雙精度浮點型數(shù)據(jù)，int 為整形數(shù)據(jù)），type 位置置為0，并將所有數(shù)據(jù)存放于一個集合中。

（3）通過兩個循環(huán)遍歷該集合，循環(huán)1用于獲取當前的樣本點，循環(huán)2遍歷剩下的所有點的數(shù)據(jù)，例如，有數(shù)據(jù)總鏈L，包含數(shù)據(jù)A，B，C，D。當循環(huán)1遍歷到A 點時，循環(huán)2遍歷B，C，D數(shù)據(jù)；當循環(huán)1遍歷到B 點時，循環(huán)2遍歷C，D。通過該循環(huán)，可遍歷所有數(shù)據(jù)，并將其兩兩進行計算。

（4）通過計算兩個點之間的歐幾里得距離，并將其與掃描半徑maxLen 進行對比，小于掃描半徑maxLen 的值時，認為兩個點處于同一個集合簇。并識別循環(huán)2中的點的type 位置是否為0，如果為0，則表示該點未被標記，將其type 值設為為循環(huán)1的點的type 值將其標記；如果循環(huán)2中點的type 值不為0，且與循環(huán)1中的type 相同，則不作處理；如果循環(huán)2中點的type 值與循環(huán)1中點的type 值不同，則將該點及所有點中type 值與該點相同的點的type 值設為循環(huán)1中點的type 值。在循環(huán)1執(zhí)行完之后，可獲取生成的集合。具體例子如下所示：

圖4 案例示意

例如：有以下點A，B，C，D，E，F(xiàn)，G，H，I，共9個點。

將這9個點根據(jù)橫縱坐標建模為以下形式并存入集合：

A（x1，y1，0） B（x2，y2，0） C（x3，y3，0）

D（x4，y4，0） E（x5，y5，0） F（x6，y6，0）

G（x7，y7，0） H（x8，y8，0） I（x9，y9，0）

按照上述的方式，開始分析所有點：

A～A.type=0， #A～ 表示循環(huán)1走到 A 點

A.type=1， # 將 A 的 type 值設為1

A：B（T）， #對A 與B 的距離進行計算，小于掃描半徑時記為（T）

B.type=0 #識別到B 的type 為0

B.type=A.type=1 # 將 B 的 type 置為 A 的 type 的值，為1。

A：C（T）

C.type=0

C.type=A.type=1

A：D（F） #對A 與D 的距離進行計算，小于掃描半徑時記為（F）

A：E（F）

A ：F（F）

A：G（F）

A：H（F）

A ：I（F）

表1 此時集合中的數(shù)據(jù)和其type值

B～B.type=1 #識別到B 的type 不為0，不做操作

B：C（T）

B：D（F）

B：E（F）

B ：F（F）

B：G（T）

G.type=0

G.type=B.type=1

B：H（F）

B ：I（F）

表2 此時集合中的數(shù)據(jù)和其type值

C～C.type=1

C：D（T）

D.type=0

D.type=C.type=1

C：E（F）

C ：F（F）

C：G（F）

C：H（F）

C ：I（F）

表3 此時集合中的數(shù)據(jù)和其type值

D～D.type=1

D：E（F）

D ：F（F）

D：G（F）

D：H（F）

D ：I（F）

表4 此時集合中的數(shù)據(jù)和其type值

E～E.type=0

E.type=2 #識別到E 的type 為0，將其置為2

E：F（F）

E：G（F）

E：H（T）

H.type=2

H.type=E.type=2

E ：I（F）

表5 此時集合中的數(shù)據(jù)和其type值

F～F.type=0

F.type=3

F：G（F）

F：H（F）

F：I（T）

I.type=0

I.type=F.type=3

表6 此時集合中的數(shù)據(jù)和其type值

G～G.type=1

G：H（T）

H.type=2 #識別到點H 在2集合中

E、H.type=G.type=1 #將2集合并入1集合

G ：I（F）

表7 此時集合中的數(shù)據(jù)和其type值

H～H.type=1

H ：I（F）

表8 此時集合中的數(shù)據(jù)和其type值

此時循環(huán)識別玩所有的點，共發(fā)現(xiàn)集合1和集合3兩個集合。

如果此時集合最少點數(shù)目設為3，則集合1的數(shù)目為7；集合3的數(shù)目為2，少于最少點數(shù)目，因此，集合3中的點F 與I 為噪聲點。

4 結束語

針對無線電自動定位系統(tǒng)，在短時間內(nèi)多次定位所產(chǎn)生的多條數(shù)據(jù)，通過上述的軟件算法應用，進行無線電自動定位數(shù)據(jù)的二次計算，可將雜散的定位數(shù)據(jù)去除噪聲，并找出中心點。在設置好適合的掃描半徑之后，計算結果的中心點可認為是更準確的定位結果。

本文從軟件開發(fā)的角度，結合DBSCAN 算法進行應用程序設計，并拓展及簡述了DBSCAN 聚合算法在無線電監(jiān)測中的作用，為無線電自動化監(jiān)測定位提供支持。