基于密度的快速DBSCAN 算法在無(wú)線電自動(dòng)定位中的應(yīng)用

劉曦元

（國(guó)家無(wú)線電監(jiān)測(cè)中心云南監(jiān)測(cè)站，昆明 650031）

1 DBSCAN

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

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

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

2 軟件的總體設(shè)計(jì)

2.1 軟件架構(gòu)

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

圖1 系統(tǒng)架構(gòu)圖

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

2.2 軟件流程結(jié)構(gòu)設(shè)計(jì)

圖2 軟件流程圖

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

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

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

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

3 快速 DBSCAN 算法詳解

3.1 簡(jiǎn)介及定義

DBSCAN 是一種著名的密度聚類算法，它使用一組關(guān)于“鄰域”的參數(shù)來(lái)描述樣本分布的緊密程度。快速DBSCAN 算法使用了DBSCAN 算法的基本概念，DBSCAN 算法在使用時(shí)，需要計(jì)算其核心點(diǎn)與非核心點(diǎn)的區(qū)別，快速DBSCAN 算法減去了核心點(diǎn)與非核心之間的區(qū)別使程序復(fù)雜度降為O（N！）。

對(duì)于DBSCAN 算法，給出以下的定義：

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

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

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

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

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

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

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

對(duì)于快速DBSCAN 算法，給出以下定義：

圖3 定義示意圖

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

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

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

（4）中心點(diǎn)：在一個(gè)樣本集合中，所有樣本的橫坐標(biāo)平均值和縱坐標(biāo)平均值組成的點(diǎn)，稱其為該集合的中心點(diǎn)；

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

3.2 計(jì)算方式

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

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

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

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

圖4 案例示意

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

將這9個(gè)點(diǎn)根據(jù)橫縱坐標(biāo)建模為以下形式并存入集合：

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）

按照上述的方式，開始分析所有點(diǎn)：

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

A.type=1， # 將 A 的 type 值設(shè)為1

A：B（T）， #對(duì)A 與B 的距離進(jìn)行計(jì)算，小于掃描半徑時(shí)記為（T）

B.type=0 #識(shí)別到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） #對(duì)A 與D 的距離進(jìn)行計(jì)算，小于掃描半徑時(shí)記為（F）

A：E（F）

A ：F（F）

A：G（F）

A：H（F）

A ：I（F）

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

B～B.type=1 #識(shí)別到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í)集合中的數(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í)集合中的數(shù)據(jù)和其type值

D～D.type=1

D：E（F）

D ：F（F）

D：G（F）

D：H（F）

D ：I（F）

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

E～E.type=0

E.type=2 #識(shí)別到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í)集合中的數(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í)集合中的數(shù)據(jù)和其type值

G～G.type=1

G：H（T）

H.type=2 #識(shí)別到點(diǎn)H 在2集合中

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

G ：I（F）

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

H～H.type=1

H ：I（F）

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

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

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

4 結(jié)束語(yǔ)

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

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