[LBS] 网络定位算法

1. 导语

目前定位技术主要包括：GPS定位、网络定位、惯性导航定位、MM（地图匹配）、视觉定位等。 GPS是最为人熟知的定位技术，是依靠设备与卫星交互来获取经纬度的方式。

惯性导航定位：

惯性定位: 依靠惯性传感器（IMU）获得加速度和角速度信息，通过推算获得当前的位置和方位的定位技术。

地图匹配：

地图匹配(map matching)指将行车轨迹的经纬度采样序列与数字地图路网匹配的过程, 其本质是平面线段序列的模式匹配问题

1.1 GPS定位缺点

1）冷启动时间长。GPS启动时，需要进行搜星，锁定卫星信号，然后进行定位。这个过程可能达到几十秒；
2）室内或有遮挡的场景。GPS信号弱，无法进行有效定位；

比如在滴滴打车场景，当乘客和司机在有遮挡的场景下，例如室内、高架下等，GPS通常处于不可用状态。这时就需要有其他定位技术作为GPS的补充，是的乘客发单、司机导航等服务依然可用。其中最主要的补充便是网络定位。

1.2 网络定位定义

室内类场景虽然有遮挡，但设备通常可以扫描到Cell（基站）和Wifi列表，而且Cell和Wifi设备相对稳定，连接其上的设备可以借其定位，这就产生了网络定位。Wifi的接入设备通常称为AP（Acess Point），方便起见，下文将AP和基站统称为AP。
网络定位包含wifi定位和基站定位，是指基于终端扫描到的wifi或基站列表进行的定位技术。

网络定位通常采用的是指纹定位技术，是一个根据Query匹配指纹库信息，并计算得到坐标位置的过程。网络定位系统主要包括离线建库和在线定位两个阶段。

query匹配指纹库.png

1.3 网络定位离线建库

离线建库主要是基于有GPS时的采集数据，建立指纹库的过程。指纹库中记录AP的各类信息在不同地理网格内的采集数据分布。
指纹信息：记录每个AP在每个网格出现的信号强度、采集次数等信息；

AP指纹库建立.png

2. 网络定位算法演进

在线网络定位算法经历了无监督概率模型、有监督回归模型、端到端CNN模型三次大的迭代。前两个阶段的网络定位主要包括：网格召回、网格排序、网格平滑三步。
端到端CNN模型去除了网格排序和网格平滑，基于一个召回中心点，直接回归位置坐标。

无监督模型、有监督回归模型.png

端到端CNN模型.png

2.1 无监督概率模型

以AP指纹库的信号强度为例，看下网格概率计算过程；下图中纵轴为采集数据中的AP编号，横轴为网格编码。相交点表示每个AP在对应网格中的采集信号强度分布。空值表示AP在对应的位置无采集数据。

AP指纹库.png

假设一个实时定位query信息为：(AP1: rssi=1, AP3: rssi = 0)为例子，介绍网格召回、排序、平滑的过程。
（1）召回阶段，基于扫描到的AP1和AP3，可以召回Grid1/Grid2/Grid4三个网格；
（2）排序阶段，结合离线AP库，基于独立性假设和贝叶斯公式； 下式中 $ap_j$ 表示观测到的APj的信息。
$w_{Grid_i} = p(Grid_i|query) = \prod_j p(Grid_i | ap_j) = \prod_j \frac{p(Grid_i, ap_j)}{p(ap_j)}$
以信号强度这一单一特征为例，
$w_{Grid_1} = p(Grid_1|rssi_{AP1}=1) * p(Grid_1| rssi_{AP3}=0) = 3/5 * 2/3 = 0.4$
$w_{Grid_2} = p(Grid_2|rssi_{AP1}=1) * p(Grid_2| rssi_{AP3}=0) = 1/5 * 0/3 = 0$
$w_{Grid_4} = p(Grid_4|rssi_{AP1}=1) * p(Grid_4| rssi_{AP3}=0) = 1/5 * 1/3 = 0.067$
（3）平滑阶段，基于上述的统计概率，排序获取Topk个网格，采用爬山法求解最优坐标； $d_i$ 表示预测位置到 $Grid_i$ 的距离。
$x,y = argmin \sum_i w_{Grid_i} * d_i$

2.2 有监督回归模型

无监督概率模型方法，实现简单是早期网络定位的主要方式。但有以下问题：（1）联合概率的方式对采集信息不充分的位置不友好，例如 $w_{Grid_2} = 0$ ；（2）难以拟合多维特征，尾部badcase较严重；（3）技术目标无法得到直接优化，天花板较低；
出于以上问题的思考，整体流程仍然保持网格召回、排序、平滑三个阶段。将网格排序升级为有监督回归模型，引入多元特征和显示的优化目标，实现对网格的更精准打分。

有监督回归模型：

label：预测网格与真实位置的位置偏差，回归任务；
特征工程：构建近百维特征，主要包含AP特征、网格特征、前文特征等；
模型选择：一期上线GBDT模型；二期对比了GBDT/FM/DeepFM/FM+GBDT，最终话线上最优融合模型结构如下。原始特征中的稠密特征和低维稀疏特征经过GBDT进行特征组合、交叉；GBDT输出的叶子节点编号与高维稀疏特征经过DeepFM网络，最终输出网格与真值的位置偏差。
TopK网络平滑：预测偏差距离从小到大排序，取Topk网格；爬上法，梯度下降求解最优坐标；

有监督回归模型.png

2.3 端到端CNN模型

有监督模型在特征利用、模型结构、优化目标等方面提供了更大的操作空间，可以极大打开天花板。上线后定位精度等指标取得了显著的收益。但是存在以下问题：
（1）每个网格孤立刻画，信息采集时的不均衡、有偏的问题无法有效解决；
（2）TopK平滑层与排序层割裂，无法联合优化，且引入部分人工超参；
对于以上问题，考虑以下解决方案：
（1）CNN网络：充分利用空间信息的局部相关性，增强特征的提取能力；
（2）端到端网络：合并排序与平滑层，改为直接回归位置坐标，目标更统一，减少人工超参；

端到端CNN模型.png

特征图如下：每个通道对应某个维度的特征； $C$ 表示特征图通道数量，特征图大小为 $M * M$

特征图.png

label与loss：label为真实位置与召回中心位置的偏移dx和dy，召回中心+预测位置偏移即可得到预测位置。loss最终选择的是球面距离偏差的L2 loss；

CNN损失.png

参考资料

网络定位：

高德网络定位算法的演进
https://mp.weixin.qq.com/s?__biz=Mzg4MzIwMDM5Ng==&mid=2247484570&idx=1&sn=fb869bba6f5cc60dbd77ee85676bb45c&chksm=cf4a5c79f83dd56f014ecd85c5e76a9e5f6a893a0ae71402d14a3fad92f54c6b03231052e83d&scene=21#wechat_redirect
高德在提升定位精度方面的探索和实践
https://mp.weixin.qq.com/s?__biz=Mzg4MzIwMDM5Ng==&mid=2247484274&idx=1&sn=5f2d316cae6d4df75eeb3cc8076e4d90&chksm=cf4a5b91f83dd28716c3a9a299342f03fafc935a4ba38fd451dc87d500786ed0ea81cb72959c&scene=21#wechat_redirect
高德网络定位之“移动WiFi识别”
https://mp.weixin.qq.com/s?__biz=Mzg4MzIwMDM5Ng==&mid=2247483875&idx=1&sn=3b1087bb6df4748fcd54d339f3c3e2e6&chksm=cf4a5900f83dd0162f318e7a18ca42676fd5d4ceeccc7dba57d4d8702aaf536af21e38b5d848&scene=21#wechat_redirect
机器学习在滴滴网络定位中的探索和实践
https://mp.weixin.qq.com/s?__biz=MzU1ODEzNjI2NA==&mid=2247507048&idx=1&sn=7e4d8721e819d7aa61f43922650b09c6&chksm=fc29b2cfcb5e3bd9e1f4de8316f2c5437c770e04921def858e7b4da6a9215cb0508d6219ad82&scene=27#wechat_redirect