基于DBSCAN的基站定位算法?

夏 天 彭艷兵 張若愚

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

1 引言

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

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

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

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

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

2 基站定位算法

2.1 基站定位算法思路

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

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

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

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

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

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

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

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

2.4 基站位置計(jì)算

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

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

2）如聚類個數(shù)小于1則定位失敗；如聚類個數(shù)等于1則將聚類重心作為基站的位置。

3）如聚類個數(shù)大于1，則計(jì)算每個區(qū)域的區(qū)域權(quán)重，按照權(quán)重從大到下對區(qū)域進(jìn)行排序，順序比較每一個區(qū)域之間的距離，如區(qū)域距離小于100m則算為1類，大于100m則跳過，直至遍歷所有基站。最后按照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ù)來自于烽火App中2017-06-01至2018-06-01的位置上報數(shù)據(jù)。該數(shù)據(jù)包含用戶的唯一ID、上報經(jīng)緯度、上報時間、上報基站號等信息。通過第三方接口獲得這些基站的相對精確位置構(gòu)成本次實(shí)驗(yàn)的數(shù)據(jù)集。本文算法采用的語言是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)過程

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

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

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

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

本文將基站下坐標(biāo)點(diǎn)的數(shù)量劃分為四個等級：[0，100)、(100，200]、(200，400]、(400，∞) 以上。針對這4個數(shù)量級的數(shù)據(jù)，使用訓(xùn)練集中的基站位置數(shù)據(jù)，對于DBSCAN的參數(shù)組合［?，MinPts］，建立了從［0.001，3］到［0.1，20］共1800種參數(shù)組合，采用遍歷的方式對1800種參數(shù)組合下的定位精度進(jìn)行計(jì)算，根據(jù)2.2中的方法得到每個參數(shù)組合的綜合評價值z，最后選出每個數(shù)量等級的最優(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ì)算時出現(xiàn)了極端值，影響了平均偏差。

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

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

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

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

4 結(jié)語

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