1.导语

1.1.术语

 1)   POI：Point Of Interesting，兴趣点，地图上任何有意义的点，比如商店，酒吧，加油站，医院，车站，景区等；

 2)   驾车导航到达点：用数字地图进行驾车路线规划及导航时的终点位置坐标；

 3)   亲子关系：POI的从属关系，例如，商场是所有内部商铺的父点；

 4)   众包：数据采集方式的一类，依靠用户采集地图数据；

 5)   参考到达点：辅助进行挖掘到达点正确性判断的坐标点，策略中多使用POI抓最近路点作为参考点；

 6)   合作APP：使用了高德地图开放API的第三方APP。

1.2.背景

 驾车导航是数字地图的核心用户场景，也是主要功能之一。导航质量依赖道路数据、定位系统、导航路径规划算法、到达点坐标等因素。

 导航路径规划参见下图示例：

 在路径规划中，到达点坐标至关重要，它直接决定导航结果是否有效，因此，到达点挖掘是数字地图的重要研发工作之一。

 高德地图及其竞品的传统到达点挖掘策略是“显示坐标抓路”：基于POI显示坐标，抓取最近可通行合理道路的垂足作为到达点。

“显示坐标抓路”策略对于临街类独立POI基本可行，但对于稍复杂的场景，解题能力有限，参见如下两个BADCASE：

（1）POI坐标与背面路距离更近，抓最近路抓到背面路。如下图CASE，POI在A位置，是一个临街店铺，抓最近路到达点在B位置，是小区内部路，正确到达在箭头所指处：

 （2）POI在楼栋内部（如商场、办公楼等），正确到达应该是楼栋区域入口，直接用POI坐标抓最近路错误概率较大。参考如下CASE，POI在A处，是图中商场子点，抓最近路抓到B点，正确的商场入口在箭头所指处：

 为解决“显示坐标抓路”策略的缺陷，提升整体到达正确率，高德地图组建了到达点挖掘项目组。在过去的一年时间里，我们分析了大量CASE，总结规律，设计了大量基于固定规则的挖掘策略，例如（仅举例3个简单策略）：

 （1）基于POI名称、地址中提到的道路，与到达点所在道路做对比，纠正不一致数据；

 （2）基于亲子关系，所有子点POI统一使用父点POI的到达点；

 （3）结合POI朝向角辅助挖掘到达点。

  基于现有的大量规则型策略，已经能挖掘产出高质量到达点数据，但由于到达场景的多样性和复杂性，策略表现不稳定，不同批次间正确率和收益率都存在一定程度波动。

 分析发现，规则型策略效果不稳定大概率由以下几方面原因导致：

 （1）所有规则均基于有限CASE分析总结得出，难以确保规则的普适性 ；

 （2）所有数值关系类规则，均通过人为分析得出，规则识别难度较大，质量难以保障；

       （3）部分规则涉及多个相关因子，多因子关系总结难度更大，人为识别效果不好。

 为了解决纯规则型策略的短板，我们决定引入机器学习解题，通过机器学习模型实现到达点可信度预测，最终形成“规则+模型”的组合解题方案。

1.3.目标

       通过机器学习方法对挖掘产出到达点进行可信度预测。

2.机器学习解题

2.1.模型选择

 我们最初考虑的问题是模型选择，用常规的机器学习模型，还是神经网络类模型。

 最开始我们倾向于使用目前很火的神经网络类模型，但经分析发现，到达点挖掘场景可能的输入都是一些相对静态的特征，和时序有关的RNN/LSTM派不上用场，同时，也不具备通过卷积可提取有效子模式的特征。所以，即使使用神经网络类模型，也只能选择DNN。

 在最初的特征和训练集准备完成后，我们尝试了DNN，LR，DT，RF，SVM，GBDT+LR几种模型。

 其中，针对DNN尝试了多种网络结构及各种损失函数、优化器、激活函数的组合，训练效果都不理想，可能的原因是，人为提炼的特征丢失了部分原始有效信息，但大部分原始信息和到达点相关度都很小，直接输入模型意义不大，例如：针对一个POI的所有用户导航定位及时间信息。

 相对于DNN，常规模型的预测效果优势明显。在常规机器学习模型中，线性模型LR、SVM表现不佳，AUC只能到0.6+；决策树表现稍好；表现最好的是集成模型，包括RF，GBDT+LR。效果最好的GBDT+LR，基于最初的特征集合和训练集，测试集上的AUC能达到0.9+，KS能达到0.6+。

 经过初步评测后，最初版本的到达点可信度预测决定选用GBDT+LR模型。

2.2.特征&建模规划

 从业务领域中识别和提取有效特征，是机器学习类工作的核心环节，如果特征的质量足够高，建模工作也就成功了一半。

 到达点可信度预测模型的特征规划和建模设计经历了以下三个版本：

2.2.1.版本一：基于策略因子

 由于启动机器学习工作之前，已有了大量的规则类策略积累，已对业务背景认识较深，所以已经积累了一批候选特征，可总结为以下3大类：

 （1）POI基础特征，包括：类别，亲子，门，楼层，是否临街等等；

       （2）挖掘到达点（待预测点，下文用Miner表示）周边环境特征，包括：距POI距离，所在道路相关特征，真实用户到达热度等等；

       （3）参考到达点（下文用Ref表示）基础特征及对比特征，参考点基础特征与Miner特征类似；对比特征旨在通过数值表达POI/Miner/Ref三者之间的位置关系，具体包括以下各维度POI/Miner/Ref三者之间相互对比：相互之间距离对比，朝向角夹角对比，所在道路信息对比等等。

 以上便是最初规划的模型特征集合，但分析发现存在一个问题，第3类参考到达点特征，由于存在的参考点较多，例如：抓最近路位置、朝向角与最近路交点等等。如果所有参考点都上一套特征的话，模型特征将过度冗余。为了解决该问题，规划了版本二。

2.2.2.版本二：二阶段动态参考点

 为了解决版本一中存在的参考点特征过度冗余的问题，设计了二阶段动态参考点方案：

 如上图所示，通过阶段一模型筛选出最具参考价值的1个参考点，用该参考点的对比特征、可信度，和POI基础特征、挖掘点周边环境特征，共同组成阶段二模型的特征集合，通过阶段二模型预测最终可信度。

 在该方案中，通过阶段一模型需要挑选出最具参考价值的1个参考点，即，在参考点集合中，该参考点作为到达点的可能性最大，或距正确到达点最近。为了实现这个目标，阶段一模型也需具备到达点可信度的基础预测能力。

2.2.3.版本三：第一版上线模型

 最终上线的1.0版本模型，是一个包含144个特征的阶段一模型，该模型特征的思维导图如下（脱敏，仅保留一级特征节点）：

2.3.训练集自动生产

       启动该工作之初考虑过人工生产训练集，但评估后发现，基于现有人力，生产周期太长，无法满足项目进度要求，所以决定通过策略自动生产训练集。

2.3.1.正样本

 训练集正样本是POI的最佳到达点。

 经组内讨论，决定使用最近半年内更新的、POI类型合理范围内的、人工制作的线上到达点。

2.3.2.负样本

 训练集负样本需满足两个条件：

 1》 在POI附近一定区域合理范围内。不能地图上随意找一个距POI很远的点就当做负样本，那没意义；

 2》 不满足所有判正确的条件。

 经过分析设计，最终确定了一套基于正样本生产负样本的策略，基本思路是：在POI附近合理距离范围内，召回多个不满足正确条件的错误到达点，然后随机选择一个作为当前POI的错误到达点。

2.4.模型效果优化

 模型调优过程中，对于模型参数的调整做得并不多，做过相关尝试，优化效果不明显。

 目前，调优过程主要集中在训练集优化和特征优化两方面，主要包括以下几点：

2.4.1.特征重要性评估 & 高重要性因子分析

 评估特征重要性的现成工具很多，常见工具包括LR，RF，GBDT等模型。

 评估特征重要性的目标包含两方面：

 （1）排除重要性极低的特征

 （2）识别基于当前训练集和建模方式，重要性极高的特征，并分析这些特征重要的合理性。

 第2个目标相比第1个目标更为重要，因为导致特征重要性高的因素包含以下几方面：

 （1）在真实场景中，某特征的重要性的确很高；

 （2）由于训练集是用策略自动化生成，所以某特征的重要性高，有可能是由于不合理的训练集生成策略导致；

 （3）某特征的重要性很高，有可能是由于不合理的特征预处理导致。

 从以上三方面对重要性最高的少量特征进行分析，有可能可以找到一些模型优化思路。本项目基于该思路成功发现了一些训练集生成策略的缺陷。

2.4.2.缺失值填充

 由于业务场景的特殊性，部分特征存在缺失值情况，分析对比了多种缺失值填充策略后，决定使用PAI平台的“缺失值填充”组件中的min值填充功能。

 Min填充的本质，是用价值最小的数值填充，但由于存在部分特征的业务背景并不是数值越小，价值越小，而是相反，例如：轨迹的平均速度（平均速度越小，附近是合理到达点的可能性越大），所以需要进行反向数值处理，目前采用的处理方式是 (1.0/X)*1000。

2.4.3.ONEHOT编码

 分类型特征需要进行ONEHOT编码，直接使用分类项的原值或序号都不合理。

2.4.4.分箱

 对于一些取值范围为浮点型的特征，例如“POI距挖掘点距离”，会由于全量训练集的取值范围过大而导致树类模型的分裂点增加，加大训练难度，可基于合理的业务背景进行数值分箱，例如，“POI距挖掘点距离”按5米进行分箱。

2.4.5.训练集分析

 如果全部或部分训练集通过策略自动生成，一定要确保生成的训练集具有随机性，能相对真实的模拟真实世界。

 例如，该模型负样本的自动生成策略，最初选取的是满足一系列条件的、距POI最近的候选点，但后来分析发现只选用最近候选点会导致负样本代表性不强，无法模拟更多的真实场景，所以我们做了优化，先针对每个POI构建一个合理的负样本候选集合，再从候选集中随机选取一个作为最终使用的负样本。

3.模型效果

3.1.基于PAI的“二分类评估”组件

       最终上线使用的GBDT+LR模型，测试集的评估效果为：

3.2.实战效果

 目前的应用方式是“策略+模型”，模型接在所有挖掘策略之后，先由策略挖掘产出到达点，再用模型从策略产出数据中识别并过滤命中“策略盲区”的高危数据，以实现整体正确率的进一步提升。

 在最新批次的真实数据生产中，基于该应用方式，在规则型策略产出高质量数据的基础上，通过应用机器学习模型，进一步提升正确率4%。

 基于传统的“显示坐标抓路”策略，及过去一年最新设计的规则型挖掘策略，到达点的整体正确率始终难以达到高质量上线标准（高于目前国内业界最高水平），通过上述机器学习方案则第一次实现了高质量上线标准的突破。

4.致谢

 工作开展过程及本文编写过程得到了以下同学的大力支持，特此感谢：

 感谢 @梅树起(澜生) @赵琦 同学在架构设计过程、模型优化过程、本文编写过程给予的大力帮助；

 感谢 @胡珂(汝风) @彭金艳(九嶷) 同学在方案构思、模型特征设计、特征优化、依赖数据生产、预测效果优化、模型应用、本文编写等过程给予的大力帮助。