1.導讀
GPS定位精度高，且早已成為移動裝置标配，但GPS也具有一些難以克服的缺陷，包括：
- 冷啟動時間長。GPS啟動時，需要進行搜星，鎖定衛星信号，然後再進行位置技術，這個過程可能會達到幾十秒，即使采用諸如AGPS等技術，仍然有秒級的時間無法定位。
- 室内或有遮擋的場景。GPS信号弱，無法有效定位。
使用者需要持續的有效定位，是以需要另一個技術對GPS進行補充，這就是網絡定位技術。
網絡定位是将手機裝置收到的信号（主要是基站、Wifi、藍牙）發送到網絡伺服器，獲得位置。之是以要将信号資料發送到網絡上，是因為網絡定位是利用信号指紋進行定位，需要一個龐大的且持續更新的指紋資料庫，這個資料庫難以同步到移動裝置上。為了進行定位，需要事先建立每個位置的指紋特征，然後在定位時用實時指紋比對每個位置的曆史指紋，确定位置。
高德網絡定位不僅承擔着高德地圖使用者的定位請求，還面向國内所有主流手機廠商，以及國内30萬以上App提供服務，日均處理請求千億次，峰值QPS百萬級。
在過去的幾年中，高德網絡定位算法經曆了從無監督算法向有監督算法的演進，從定位精度、定位能力透出等方面都有了顯著的提升。
注：高德網絡定位隻存在于安卓平台上，在iOS上由于蘋果公司未開放任何定位相關的指紋資料（Wifi、基站清單等），定位結果全部來自于iOS自身。
2.基于聚類的無監督算法
經典的指紋定位算法是無監督算法，其核心是計算指紋的相似性，用指紋确定位置。下圖是一個例子，AP代表手機掃描到的基站和Wifi裝置編号，縱軸代表不同的位置，二者交點的數值代表該位置掃描到該AP的信号強度，為空代表該位置沒有掃描到該AP。
要對一個新定期請求進行定位（比如AP1:-30,AP2:-50,AP3:-90），一個最簡單的方法，是用KNN逐一計算該指紋與曆史指紋的相似度（比如用L2距離或者餘弦相似度），取相似度最大的曆史位置作為使用者位置。
這有兩個問題，第一是計算量太大（AP是10億量級，loc是千億量級），無法滿足實時定位的要求，第二是曆史指紋在局部可能比較稀疏，對于使用者指紋無法精确比對。
于是需要對曆史資料進行預處理，提取出AP和網格的通用指紋，這樣在定位時隻需要比對一次即可。下圖是利用一個AP的曆史采集位置進行聚類，獲得AP實際位置和覆寫半徑的過程，有了每個AP的位置，在定位時将多個AP的位置進行權重平均即可獲得最終位置。
這種方法需要解決的一個挑戰是當有多個候選位置時如何選擇，如下圖所示，有兩個候選位置。
此時需要設計一個政策進行簇選擇，基于每個簇的特征進行打分，找出最有可能的一個簇作為使用者位置。
基于權重平均的定位，速度很快，但精度比較差，原因是指紋在空間上的分布并不是連續的，而可能受到建築、地形、道路的影響，呈現一種不規則的分布，于是在上面定位方式的基礎上，發展出一種基于格子排序的算法，可以更精準的定位。
首先将地球劃分為25*25的網格，然後統計每個網格内的指紋特征，最後進行格子排序。設候選網格為l，信号向量是S，則定位過程就是計算
根據貝葉斯公式，有
根據1-1，由于所有候選網格的分母相同，隻需要計算分子，即：
其中P(l)是某個位置在全量使用者位置中出現的機率，可以用定位PV表示，而P(S=S0|l)則需要計算在每個網格内出現某種信号向量的機率，由于向量維數高，機率難以計算，是以對不同維進行獨立假設，認為每個信号出現的機率是獨立的。有：
這樣，可以基于曆史指紋對每個網格内的每個AP的信号強度進行直方圖統計，即可計算出機率，最後對所有格子的機率進行排序，獲得機率最高的那一個，如下圖：
3.基于分層排序的有監督算法
無監督算法的一個問題，是難以疊代，對于badcase無法進行有效優化，一旦調整政策就會影響到其他case，無法獲得全局最優。
是以，有監督學習就變得很有必要，高德定位從近兩年開始全面轉向有監督學習，持續進行特征和模型設計，提升效果，取得了不錯的收益，解決了50%以上的大誤差問題（5公裡以上），在移動Wifi識别上獲得了99%以上的識别準确率。
有監督學習需要使用大量的特征，特征的計算需要消耗較多資源，考慮到定位服務要承受10萬以上的QPS，模型的複雜性與效果同等重要，是以我們首先将定位服務進行了分層，上面的層級針對大網格，計算粗略的位置，下面的層級針對小網格，逐漸細化位置。這樣可以極大減少不必要的計算，在性能和效果間取得平衡。
對于每一個單獨的算法子產品，都采用類似下面的神經網絡模型對每個候選網格進行打分，再使用LTR損失函數作為目标進行訓練，進而獲得神經網絡的參數。在特征方面，同時考慮以下三類：
- AP的動态特征，比如信号強度
- 網格特征，比如PV、UV、AP數、周邊候選網格數等
- AP在網格上的特征，比如信号強度分布、PV、UV等
采用這種方法可以解決絕大部分格子選擇不準确的問題，遺留的一個問題是當定位依據特别少的時候，比如隻有一個基站和一個Wifi，二者分别位于距離較遠的兩個網格，此時無論選擇哪個都有50%的錯誤機率。為了解決這個問題，我們引入了使用者曆史定位點輔助進行各自選擇。
在特征部分加入曆史定位點序列，輸出一個曆史位置特征（可以看成是一個預測的新位置），讓這個預測位置參與網格打分。當有兩個距離較遠但打分接近的網格進行對比時，通過預測位置進行權重。這樣模型應該可以學出這樣的規律：如果網格距離預測位置比較遠，打分就降低，如果比較近，分就高。通過這個方法，大誤差case的比例可以降低20%。
4.場景化定位
使用者在不同場景下對定位的要求是不同的，比如使用者在旅途中可能隻需要知道大緻的位置，不需要很精确，但是在導航時就需要精确的知道自己在哪條道路上，距離出口多遠。
是以，除了在整體算法架構上進行優化，高德還在不同特定場景上進行針對性的優化，滿足使用者不同場景下的定位需求。
室内場景
指紋定位的一個局限，是需要采集帶GPS的樣本作為真值進行訓練，由于GPS隻能在室外被采集到，即使使用者在室内，其定位結果有很大機率在室外，這會對使用者造成不少困擾，特别是在使用者準備出行的時候，其定位點的漂移會導緻起點偏離真實位置較大。
為了解決這個問題，有兩個解決辦法，一是采集室内真值，但這種方法需要大量人工采集工作，工作量巨大，目前高德在一些熱門商場和交通樞紐進行人工指紋采集（除了基站Wifi還支援藍牙、傳感器定位）。第二個辦法是借助大資料，無需人工幹預，對Wifi進行建築/POI關聯，用建築/POI位置去修正定位結果。
Wifi-POI關聯有多種方法，一個簡單的方法是用POI名字與Wifi名字的相似度判斷是否有關聯，比如麥當勞的Wifi名字就是McDonald，關聯的時候需要考慮中英文、大小寫、中英文縮寫等。從名稱能分析出關聯關系的Wifi畢竟是少數。另外一種覆寫能力更強的方法是利用Wifi信号分布規律去挖掘Wifi的真實位置，畢竟絕大部分Wifi都是部署在室内的。
這裡我們采用的是CNN的方法，将樓塊資料、POI資料、采集真值資料繪制為二維圖像，然後進行多層卷積計算，label為Wifi所在的真實樓塊區域。下圖中藍色塊為樓塊，綠色為采集點，顔色越亮代表信号強度越高，紅色點代表Wifi真實位置。
目前算法能挖掘出30%Wifi對應的真實位置，在最終定位效果上，使用者在室内時，能正确定位到室内的樣本比例提升了15%
高鐵場景
從使用者報錯情況看，有大量報錯是使用者乘坐高鐵時定位異常。高鐵在近兩年開通了車載Wifi，這些Wifi都是移動Wifi，是以這些AP是沒有一個固定位置的，如果不進行任何處理，算法訓練獲得的Wifi位置一定是錯誤的，很大機率會在沿途的某個車站（使用者集中，采集量高）。
針對這種場景，需要将移動Wifi全部去除再進行定位。我們開發了針對高鐵和普通場景的移動Wifi挖掘算法，利用采集點時空分布等特征判斷某個Wifi是否移動，挖掘準确率和召回率均超過99%，可以解決絕大部分高鐵定位錯誤的問題。
地鐵場景
地鐵場景有點類似高鐵，使用者掃到的Wifi基本都是移動Wifi（少量車站有固定Wifi），是以隻能借助基站進行定位。但基站深埋地下，缺乏采集資料，如何獲得基站的真實位置呢？我們采用了兩種政策，第一個政策是利用相鄰基站資訊，當使用者在一個請求裡或者在短暫時間段内同時掃描到地鐵基站（無GPS采集）和非地鐵基站（有GPS采集）時，我們可以用後者的位置去推算前者位置，當然這種方式得到的基站位置不太準确。于是我們進行了進一步優化，利用使用者軌迹去精準挖掘出每個請求對應的地鐵站，進而建構出指紋對應的真值。
基于以上方法，地鐵内的定位精度可達到90%以上，實作地鐵報站和換乘提醒。
5.未來演進
在未來，定位技術特别是移動裝置的定位技術還将快速發展，主要突破可能來自以下方面：
圖像定位：谷歌已經釋出了基于街景的AR定位，可以解決在城市峽谷區域内的精準定位。這種定位利用了更豐富的資料源，對使用者體驗的提升也會非常顯著。
5G定位：5G相比4G，頻率更高，頻帶更寬，用于測距時精度更高（比如利用相位差進行傳輸時間計算），行業協會也在孵化5G定位相關的标準，營運商在未來可能會支援基于5G網絡的定位，屆時在5G覆寫區将會有類似GPS精度的定位效果。
IOT定位：随着物聯網的普及，基于NB-IOT的定位技術也會應運而生，它可以使用類似基站定位的方法，或者使用P2P定位的方法為物聯網裝置進行定位。