高德网络定位之“移动 WiFi 识别”

阅读数:1 2020 年 3 月 4 日 14:48

高德网络定位之“移动WiFi识别”

1. 导读

随着时代的发展,近 10 年来位置产业蓬勃发展,定位能力逐渐从低精度走向高精度,从部分场景走向泛在定位。设备和场景的丰富,使得定位技术和能力也不断的优化更新。定位能力包括 GNSS、DR(航迹推算)、MM(地图匹配)、视觉定位和网络定位等。

其中网络定位是通过客户端扫描到的 WiFi 和基站信息来进行定位的一种定位方式。网络定位能力是 GNSS 定位的有力补充,在 GNSS 无法定位或者定位较慢的时候,网络定位都可以快速给出位置。网络定位能力也是高德能够深植于各类手机厂商(提供系统级网络定位能力)和 APP(出行、社交、O2O、P2P、旅游、新闻、天气等诸多领域)的原因之一。

要做到通过 WiFi 和基站来定位,我们需要通过亿级数据来挖掘出 WiFi 和基站的类型、位置、指纹等各种信息。这些信息的挖掘,历史上是通过一系列的人工经验策略来进行的,人工规则的历史局限带来了所挖掘信息较低的准召率,为了进一步提升高德网络定位能力,我们需要卸下以往的包袱,从方法上进行改变。

2. 如何定义“网络定位”

网络定位分为离线训练和在线定位两个过程:

  • 离线训练:是在用户有 GPS 位置时采集周边的 WiFi 和基站(以下统称为 AP)信息,通过对采集数据进行聚类和关联,得到两类数据产品:AP 库和指纹库 ;
  • 在线定位:与离线训练的过程正好相反,当用户没有 GPS 定位时,可以通过扫描到的周边 WiFi 和基站信号,结合离线训练出的 AP 库和指纹库来进行实时定位。

AP 库和指纹库这两类数据产品中:

  • 指纹库:以物理坐标位置对应的特征指纹信息为内容,这些特征指纹信息可以包括扫描到的 WiFi 或者基站的信号强度分布,采集点频次等统计信息,也可以是通过神经网络提取出的特征信息。
  • AP 库:以 WiFi 的 mac 地址或者基站的 ID(gsm 基站为 mcc_mnc_lac_cid,cdma 基站为 mcc_sid _bsid_nid )为主键,以 WiFi 或者基站的物理坐标信息(经纬度或者地理栅格坐标信息)为内容。

典型的 AP 库数据只包含挖掘出的物理坐标信息和覆盖半径,这种“点圆模型”是对 AP 发射信号的一种理想化,没有考虑任何实际场景中的信号遮挡、反射等情况,所以 AP 库大多用来进行粗略定位。而指纹库直接与位置相关,可以刻画比“点圆模型”更细致的分布信息,所以指纹库可以用来进行精细定位。

高德网络定位之“移动WiFi识别”

高德的指纹库主要包括特有的室内指纹和全场景指纹信息两种。

3. “网络定位”的问题

网络定位的基本思路类似聚类,假设用户手机扫描到的 AP 列表中的 AP 的位置均比较固定,则我们可以以这些 AP 位置为锚点,来确定用户位置。现实世界中,锚点(即 AP 库中的 AP)的位置通过大数据来进行挖掘,并不一定完全准确,甚至出现严重错误。

针对 WiFi 而言,移动 WiFi、克隆 WiFi、搬家 WiFi 等都可能造成 AP 位置的错误。移动 WiFi 包含手机热点,4g 移动路由器,公交车 / 地铁 / 高铁上的 WiFi 热点等,这些 WiFi 的移动属性较强,位置频繁变化,如下图所示。

高德网络定位之“移动WiFi识别”

如果以移动 WiFi 作为锚点,因为这些锚点的位置不固定,极可能会导致用户的定位出现极大误差。克隆 WiFi 指不同的 WiFi 设备使用了同一个 mac 地址,国内的腾达和斐讯等路由器厂商制造了大量这样的 WiFi 设备(例如大部分 mac 前缀为“c8:3a:35”的即为腾达的克隆 WiFi),克隆 WiFi 导致 AP 库中同一个 mac 地址对应的锚点位置有多个。搬家 WiFi 指某些因为搬家而发生位置变化的 WiFi,数据挖掘存在一定的滞后性,搬家后 AP 库中的位置未及时更新,也会造成定位错误。

因为大误差的 badcase 严重损害用户体验,我们必须要将这些非固定 WiFi 的属性在 AP 库中标记出来。

历史上,高德是通过一系列简单的人工规则对这些 WiFi 的属性进行分类的。例如,通过采集点覆盖范围较大来判定移动 WiFi,通过 mac 前缀来判定克隆 WiFi 等。人工规则的缺点是准召率不高,训练分类模型就成了一个自然的选择。

鉴于 badcase 中最严重的问题是移动 WiFi 的准召率不高,下面我们就尝试使用监督学习的方法来进行“移动 WiFi 识别”。

4. 如何实现“移动 Wifi 识别”

4.1 样本提取

AP 库中的 WiFi 数量十分庞大,如果我们在 AP 库中随机抽取样本进行人工标注,那大部分标注的结果可能是人工规则判定正确的样本,为了尽可能低成本获取有效的标注样本,我们借鉴主动学习的思路,不断抽取模糊样本进行标注,快速迭代使得模型稳定。

我们根据人工规则的判定结果提取了一批确定性较高的样本,使用人工强特征训练第一版模型,之后将第一版模型的预测结果与线上人工规则的结果进行全量比较,提取出模糊样本进行人工标注。在标注样本的过程中发现问题,持续特征工程,不断迭代模型。

这里模糊样本的定义包含三种:预测结果与上一版模型的结果不同,预测概率值在 0.5 附近,预测结果在不同训练周期内存在波动(例如昨天识别是移动 WiFi,今天识别是非移动)。

4.2 特征提取

4.2.1 移动 WiFi vs 克隆 / 搬家 WiFi

第一版模型中,我们使用了一些采集聚集程度相关的特征。

名称 描述
ratioX 聚簇寻找中心点,中心点向外 X 米圆形范围内的定位点占总定位数的比例
areaSqare 定位点覆盖的矩形围栏范围的面积

模型迭代过程中,我们遇到的第一个问题是移动 WiFi 与克隆 WiFi 或搬家 WiFi 比较容易混淆。下面几幅图分别画出了固定 WiFi、移动 WiFi、克隆 WiFi、搬家 WiFi 的定位点散布的实例。

高德网络定位之“移动WiFi识别”

高德网络定位之“移动WiFi识别”

可以看到,如果仅仅使用定位点的聚集程度来分类,那克隆 WiFi 和搬家 WiFi 的定位点也比较分散,极易与移动 WiFi 混淆。所以我们先使用聚簇算法,将采集点局部聚集的点集合成不同的簇,在每个簇中计算定位点的散布程度,再将所有簇的散布程度求平均值等,获取平均意义上的聚集程度。

4.2.2 多维度提取特征

为了进一步提升分类的准召率,我们不仅从定位点的聚集维度来提取特征,还增加了信号强度、关联特征、IP 特征、时间特征等,以下进行简要介绍:

  • 信号强度信息:(和上节中的聚集特征一起,统称为采集特征)移动设备与非移动设备采集点的信号强度在去除设备差异性之后,分布存在差异性。
  • 关联特征:关联信息是指当设备扫描到的一次 WiFi 列表中,列表中所有 WiFi 两两之间就算产生了一次关联(或称邻居)关系,统计 WiFi 周边关联的 WiFi 和基站信息,可以描述出 WiFi 的移动属性。
  • IP 特征:固网 IP 和移动网的 IP 存在一定隔离,移动 WiFi 设备的上游一般是通过基站连接的移动网,固定 WiFi 设备的上游一般是通过 ADSL 等连接的固网。
  • 时间特征:固定 WiFi 一般是长时间连接电源的,而移动 WiFi 一般是临时在某些地方和时间短暂出现的。

4.2.3 聚合特征

在 AP 库中,存在一部分 WiFi 定位信息不够充分,即使是人工标注也存在着非常大的不确定性,这些定位信息不够充分的 WiFi,我们称之为“弱信息 WiFi”。

对于这类 WiFi,我们只有通过 ssid 和 mac 前缀来进行辅助判断。因为 ssid 中包含了一些诸如“iPhone”、“个人热点”、“oppo”、“shouqiyueche”(首汽约车)、“往返免费”、“tp-link”等能够表明设备属性的信息。另一方面,mac 前缀(mac 信息的前半部分)代表了厂商信息。基于这些辅助信息,我们可以在其他信息不够充分的情况下辅助推测 WiFi 的类别属性。

我们将基础特征(采集特征、关联特征、IP 特征、时间特征)中较为重要的 TOP_N 维特征按照 ssid 和 mac 前缀进行聚合,聚合函数为中位数(median)和总体标准差(stddev)。这样,聚合特征体现了一类 WiFi 共有的特征,针对弱信息 WiFi,我们就可以通过集体的特征来推测出个体的属性。

高德网络定位之“移动WiFi识别”

5. 应用场景

除了提升网络定位能力,移动 WiFi 的识别还有更多用武之地,例如手机热点的识别,室内外的判断,建筑物和 POI 级别的定位等等。其中一个例子就是判断当前设备所连接的 WiFi 是否为移动热点(如 4g 路由器,手机热点等),在视频类的 APP 中,可以通过判别当前用户连接的 WiFi 是否为移动热点,从而控制是否进行视频的自动播放或缓存,给予用户提示性信息。

6. 小结

最终我们使用随机森林来训练分类模型,经过特征选择和模型参数调整之后,最终得到的模型,移动 WiFi 的准召率均优于 99.8%。高德网络定位的精度也因此得到了较大提升,尾部大误差 badcase 降低了 18% 左右。

网络定位作为一种低功耗的定位手段,不仅在 GNSS 无法触达的地区(例如地铁、室内等场景)为普通用户带来辅助的定位信息,而且在某些急救和寻人的场景中发挥了重要的作用。未来,随着 5G 通信技术的开展,将迎来更加精准的网络定位能力。

评论

发布