基于DBSCAN的基站定位算法?

夏 天 彭艷兵 張若愚

（1.武漢郵電科學(xué)研究院 武漢 430070）（2.南京烽火天地通信科技有限公司 南京 210019）

1 引言

隨著移動(dòng)智能終端設(shè)備的加速普及，移動(dòng)電子商務(wù)、休閑娛樂(lè)、社交、手機(jī)游戲等領(lǐng)域的使用率都在快速增長(zhǎng)，移動(dòng)用戶對(duì)手機(jī)和互聯(lián)網(wǎng)的依賴性和使用率越來(lái)越高，互聯(lián)網(wǎng)服務(wù)商積累了大量的移動(dòng)用戶的實(shí)時(shí)位置數(shù)據(jù)。挖掘這些軌跡信息，可以發(fā)現(xiàn)人們活動(dòng)的時(shí)空規(guī)律，使人們能夠更深層地認(rèn)知智能化城市中社群的生活軌跡、社交行為、環(huán)境變動(dòng)等，不僅能夠滿足用戶越來(lái)越強(qiáng)烈的個(gè)性化、社會(huì)化需求，為社交網(wǎng)絡(luò)的發(fā)展提供支持，而且能夠?yàn)檩浨闄z測(cè)、商務(wù)智能提供支撐和保障。

對(duì)于互聯(lián)網(wǎng)服務(wù)商而言，位置信息的準(zhǔn)確性至關(guān)重要，其中基站位置信息在人員定位、軌跡分析等方面具有重要的作用。而在實(shí)際應(yīng)用過(guò)程中，往往會(huì)出現(xiàn)基站數(shù)據(jù)陳舊、基站信息缺失，經(jīng)緯度位置偏差極大等情況，給定位服務(wù)帶來(lái)了困難。

DBSCAN（Density-Based Spaital Clus-tering of Applications with Noise）算法是一種基于密度的聚類算法，它可以通過(guò)計(jì)算點(diǎn)的密度把集合中的點(diǎn)分為核心點(diǎn)、邊界點(diǎn)、噪聲點(diǎn)，在此基礎(chǔ)上對(duì)所有的點(diǎn)進(jìn)行空間聚類，從而有效地處理噪音點(diǎn)，過(guò)濾低密度區(qū)域。

目前國(guó)內(nèi)外關(guān)于DBSCAN的應(yīng)用研究已有很多。劉暢［1］等使用基于DBSCAN的密度聚類方法發(fā)現(xiàn)城市交通阻塞區(qū)域，郭保青［2］等使用基于快速DBSCAN的方法用于檢測(cè)鐵路異物侵限，楊帆［3］等基于DBSCAN空間聚類對(duì)廣州市區(qū)餐飲集群進(jìn)行了識(shí)別，丁兆穎［4］等提出了基于DBSCAN的碼頭挖掘算法。

本文針對(duì)基站位置數(shù)據(jù)分析的特點(diǎn)，提出了一種基于DBSCAN的基站定位算法?？紤]到DB?SCAN聚類算法在噪聲處理上的良好表現(xiàn)，嘗試使用DBSCAN對(duì)基站下用戶上報(bào)的經(jīng)緯度坐標(biāo)進(jìn)行密度聚類，去除噪音點(diǎn)后根據(jù)聚類情況選擇不同的策略計(jì)算基站位置。本文基于某App中用戶上報(bào)的經(jīng)緯度數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，驗(yàn)證了所提算法的有效性。

2 基站定位算法

2.1 基站定位算法思路

用戶通過(guò)基站傳輸數(shù)據(jù)時(shí)一般處于基站的覆蓋范圍內(nèi)，因此對(duì)于基站而言，用戶位置坐標(biāo)點(diǎn)會(huì)密集的環(huán)繞在基站坐標(biāo)周圍，使得基站所處位置密度較大，可以通過(guò)密度聚類的方式得到基站的位置。本文將基站數(shù)據(jù)分為訓(xùn)練集和測(cè)試集兩部分，使用訓(xùn)練集數(shù)據(jù)計(jì)算DBSCAN算法的關(guān)鍵參數(shù)組合［?，MinPts］，使用測(cè)試集數(shù)據(jù)評(píng)估算法準(zhǔn)確性。本算法主要分為四步。第一步對(duì)數(shù)據(jù)進(jìn)行預(yù)處理后構(gòu)成算法的數(shù)據(jù)集。預(yù)處理主要是篩除出數(shù)據(jù)量滿足聚類條件的基站。第二步對(duì)于訓(xùn)練集數(shù)據(jù)，遍歷若干種密度聚類的參數(shù)組合，找到合適的聚類參數(shù)。在運(yùn)用DBSCAN算法對(duì)基站位置定位的過(guò)程中，需要確定其鄰域參數(shù)?和最小點(diǎn)數(shù) MinPts［5～8］，對(duì)于不同的規(guī)模的數(shù)據(jù)集需要采用不同的聚類參數(shù)以獲得良好的聚類效果。第三步使用最優(yōu)參數(shù)組合對(duì)測(cè)試集數(shù)據(jù)進(jìn)行密度聚類。第四步根據(jù)聚類結(jié)果得到基站位置。DBSCAN按照密度將數(shù)據(jù)集劃分為任意個(gè)高密度區(qū)域，而我們期望得到一個(gè)坐標(biāo)點(diǎn)來(lái)表示基站的位置，因此當(dāng)聚類個(gè)數(shù)為1時(shí)，即高密度區(qū)域個(gè)數(shù)為1時(shí)，計(jì)算該高密度區(qū)域的重心點(diǎn)即可得到基站可能位置。而當(dāng)存在多個(gè)聚類結(jié)果，即多個(gè)高密度區(qū)域時(shí)，不能簡(jiǎn)單地通過(guò)計(jì)算多個(gè)區(qū)域的重心來(lái)得到基站的位置，而是需要根據(jù)具體的聚類結(jié)果來(lái)判別基站所在位置。

2.2 聚類參數(shù)的選擇

DBSCAN算法有兩個(gè)重要參數(shù)，即鄰域半徑?和鄰域最小點(diǎn)數(shù)MintPts，對(duì)于不同數(shù)據(jù)量，應(yīng)該設(shè)置不同的參數(shù)組合以適應(yīng)數(shù)據(jù)情況［9～14］。

本文將數(shù)據(jù)按照基站下坐標(biāo)點(diǎn)的數(shù)量劃分為N 個(gè)數(shù)據(jù)集：(0，x1]，(x1，x2]，…，(xN-1，∞)。針對(duì)這 N個(gè)數(shù)量級(jí)的數(shù)據(jù)，從系統(tǒng)中抽取部分有完整位置信息的基站，通過(guò)第三方接口獲取了其相對(duì)精確的經(jīng)緯度信息。以這些基站的經(jīng)緯度數(shù)作為訓(xùn)練集，計(jì)算各種參數(shù)組合下算法定位的精度，根據(jù)精度選取最優(yōu)參數(shù)組合。使用本文定位算法對(duì)N個(gè)測(cè)試集數(shù)據(jù)遍歷多種［?，MinPts］的參數(shù)組合，與第三方接口的數(shù)據(jù)相比計(jì)算定位精度，得出每種參數(shù)組合下的平均定位偏差（m）、定位偏差的四分位數(shù)(q1，q2）、定位成功的基站比例（s）。其中定位成功指的是誤差在200m以內(nèi)。

對(duì)于每種參數(shù)組合定位的結(jié)果按照式（1）計(jì)算綜合評(píng)價(jià)指標(biāo)：

2.3 區(qū)域權(quán)重算法

對(duì)于DBSCAN聚類結(jié)果，如果基站下上報(bào)經(jīng)緯度數(shù)據(jù)聚集性較高，則算法只會(huì)確定一個(gè)高密度區(qū)域，則此區(qū)域極可能為基站所在區(qū)域，只需計(jì)算該高密度區(qū)域的重心點(diǎn)即為基站可能位置。實(shí)際有部分基站因?yàn)楦浇匦蔚仍虻南拗?，造成算法劃分出多個(gè)高密度區(qū)域，因此不能直接對(duì)多個(gè)高密度區(qū)域計(jì)算重心來(lái)確定基站位置，需要對(duì)多個(gè)高密度區(qū)域進(jìn)行分析。若幾個(gè)高密度區(qū)域相隔較近，只是因?yàn)榈匦味环指畛啥鄩K，那么可以直接將幾個(gè)高密度區(qū)域合并為同一個(gè)區(qū)域進(jìn)行計(jì)算。若幾個(gè)高密度區(qū)域相隔較遠(yuǎn)，則可能存在數(shù)據(jù)上報(bào)有誤的情況，此時(shí)需要對(duì)幾個(gè)高密度區(qū)域內(nèi)數(shù)據(jù)情況進(jìn)行統(tǒng)計(jì)分析。

針對(duì)上述問(wèn)題，對(duì)于聚類類個(gè)數(shù)大于一的情況，本文選用數(shù)據(jù)量、總天數(shù)、時(shí)間跨度三個(gè)維度，對(duì)每個(gè)區(qū)域計(jì)算權(quán)重，權(quán)重越高說(shuō)明該區(qū)域內(nèi)上報(bào)的數(shù)據(jù)越接近真實(shí)基站區(qū)域。

2.4 基站位置計(jì)算

將待定位數(shù)據(jù)按照訓(xùn)練集的劃分方式進(jìn)行劃分，得到N個(gè)數(shù)據(jù)集，對(duì)每個(gè)數(shù)據(jù)集選用2.2中確定的最優(yōu)參數(shù)組合進(jìn)行DBSCAN聚類。根據(jù)聚類個(gè)數(shù)、各類的區(qū)域權(quán)重計(jì)算基站位置。具體步驟如下：

1）對(duì)基站下的坐標(biāo)點(diǎn)進(jìn)行聚類。

2）如聚類個(gè)數(shù)小于1則定位失?。蝗缇垲悅€(gè)數(shù)等于1則將聚類重心作為基站的位置。

3）如聚類個(gè)數(shù)大于1，則計(jì)算每個(gè)區(qū)域的區(qū)域權(quán)重，按照權(quán)重從大到下對(duì)區(qū)域進(jìn)行排序，順序比較每一個(gè)區(qū)域之間的距離，如區(qū)域距離小于100m則算為1類，大于100m則跳過(guò)，直至遍歷所有基站。最后按照K-Means計(jì)所有區(qū)域聚為一類并計(jì)算中心點(diǎn)，以此作為基站位置。

3 實(shí)驗(yàn)驗(yàn)證

3.1 數(shù)據(jù)集和實(shí)驗(yàn)環(huán)境

本文實(shí)驗(yàn)數(shù)據(jù)來(lái)自于烽火App中2017-06-01至2018-06-01的位置上報(bào)數(shù)據(jù)。該數(shù)據(jù)包含用戶的唯一ID、上報(bào)經(jīng)緯度、上報(bào)時(shí)間、上報(bào)基站號(hào)等信息。通過(guò)第三方接口獲得這些基站的相對(duì)精確位置構(gòu)成本次實(shí)驗(yàn)的數(shù)據(jù)集。本文算法采用的語(yǔ)言是Python 3.6，在Windows系統(tǒng)下運(yùn)行，計(jì)算機(jī)CPU為Intel Core i5-7500@3.40GHz，內(nèi)存大小為8G。

3.2 實(shí)驗(yàn)過(guò)程

3.2.1 數(shù)據(jù)預(yù)處理

由于每個(gè)基站下應(yīng)用上報(bào)經(jīng)緯度數(shù)據(jù)質(zhì)量存在較大差別，并不是所有基站都適合使用算法進(jìn)行定位，有部分基站下數(shù)據(jù)質(zhì)量較差，需要再積累數(shù)據(jù)，達(dá)到算法要求標(biāo)準(zhǔn)后再進(jìn)行定位。首先，為了避免某用戶短時(shí)間內(nèi)重復(fù)上報(bào)錯(cuò)誤經(jīng)緯度坐標(biāo)點(diǎn)數(shù)據(jù)，需要對(duì)每個(gè)基站下應(yīng)用上報(bào)經(jīng)緯度數(shù)據(jù)按照用戶賬號(hào)、時(shí)間（精確到小時(shí)忽略分秒）、經(jīng)緯度進(jìn)行去重，去重后剔除數(shù)據(jù)量小于3條的基站。然后統(tǒng)計(jì)每個(gè)基站下上報(bào)經(jīng)緯度數(shù)據(jù)的認(rèn)證賬號(hào)及不同日期的數(shù)量，剔除用戶數(shù)量小于2或不同日期數(shù)小于2的基站，避免極端情況對(duì)聚類造成影響。

從系統(tǒng)中提取數(shù)據(jù)，經(jīng)過(guò)預(yù)處理后共190萬(wàn)條上報(bào)經(jīng)緯度數(shù)據(jù)，共計(jì)4.8萬(wàn)個(gè)基站構(gòu)成算法的數(shù)據(jù)集。選用其中2萬(wàn)個(gè)基站作為算法的訓(xùn)練集，剩余數(shù)據(jù)作為測(cè)試集。采用基于DBSCAN的基站定位算法對(duì)測(cè)試集中的基站位置數(shù)據(jù)進(jìn)行定位，對(duì)比判斷算法的可靠性。

3.2.2 確定最優(yōu)參數(shù)

本文將基站下坐標(biāo)點(diǎn)的數(shù)量劃分為四個(gè)等級(jí)：[0，100)、(100，200]、(200，400]、(400，∞) 以上。針對(duì)這4個(gè)數(shù)量級(jí)的數(shù)據(jù)，使用訓(xùn)練集中的基站位置數(shù)據(jù)，對(duì)于DBSCAN的參數(shù)組合［?，MinPts］，建立了從［0.001，3］到［0.1，20］共1800種參數(shù)組合，采用遍歷的方式對(duì)1800種參數(shù)組合下的定位精度進(jìn)行計(jì)算，根據(jù)2.2中的方法得到每個(gè)參數(shù)組合的綜合評(píng)價(jià)值z(mì)，最后選出每個(gè)數(shù)量等級(jí)的最優(yōu)參數(shù)組合，如表1所示。

表1 最優(yōu)參數(shù)組合

表2 組合數(shù)據(jù)統(tǒng)計(jì)

由表2可以看出在數(shù)據(jù)量小于100的最優(yōu)組合里，平均偏差0.383公里大于上四分位數(shù)0.358公里，即至少75%的基站偏差都是小于均值的，這種情況的出現(xiàn)的原因就是在定位偏差計(jì)算時(shí)出現(xiàn)了極端值，影響了平均偏差。

3.3 實(shí)驗(yàn)結(jié)果分析

將測(cè)試集數(shù)據(jù)，按照同樣的數(shù)量等級(jí)劃分為四個(gè)數(shù)據(jù)子集，并所確定的參數(shù)組合對(duì)每個(gè)數(shù)據(jù)子集進(jìn)行聚類。結(jié)果如表3所示。

表3 最優(yōu)參數(shù)組合定位偏差

表3中偏差距離指的是算法定位點(diǎn)與已知坐標(biāo)點(diǎn)的距離，從表3可以看出，定位偏差在200m以內(nèi)的基站有16135個(gè)，占基站總數(shù)的57.62%，定位偏差在200m～500m之內(nèi)的基站共有7254個(gè)，占基站總數(shù)的25.90%。成功定位率為83.52%。

4 結(jié)語(yǔ)

本文提出了一種基于DBSCAN的基站定位算法。以基站下應(yīng)用上報(bào)經(jīng)緯度為數(shù)據(jù)來(lái)源，運(yùn)用DBSCAN算法對(duì)基站位置進(jìn)行定位。本文根據(jù)數(shù)據(jù)規(guī)模選擇合適的聚類參數(shù)，并對(duì)聚類結(jié)果從數(shù)據(jù)量、總天數(shù)、時(shí)間跨度三個(gè)維度計(jì)算區(qū)域權(quán)重，最后得到定位結(jié)果。對(duì)比第三方接口提供的基站位置數(shù)據(jù)，本文算法成功率達(dá)到83.52%。實(shí)際上，在手機(jī)進(jìn)行通話的過(guò)程中，由于信號(hào)、基站容量等客觀問(wèn)題，并不能總是選擇距離最近的基站［15］，且在信號(hào)不佳的情況下，還會(huì)出現(xiàn)上報(bào)應(yīng)用中記憶經(jīng)緯度（上一次定位經(jīng)緯度）的情況，給本文算法的定位帶來(lái)了困難。