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, 常规模型的预测效果优势明显在常规机器学习模型中, 线性模型 LRSVM 表现不佳, 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 模型, 测试集的评估效果为:
F1 score | 0.8558 |
AUC | 0.9276 |
KS | 0.6963 |
3.2. 实战效果
目前的应用方式是策略 + 模型, 模型接在所有挖掘策略之后, 先由策略挖掘产出到达点, 再用模型从策略产出数据中识别并过滤命中策略盲区的高危数据, 以实现整体正确率的进一步提升
在最新批次的真实数据生产中, 基于该应用方式, 在规则型策略产出高质量数据的基础上, 通过应用机器学习模型, 进一步提升正确率 4%
基于传统的显示坐标抓路策略, 及过去一年最新设计的规则型挖掘策略, 到达点的整体正确率始终难以达到高质量上线标准(高于目前国内业界最高水平), 通过上述机器学习方案则第一次实现了高质量上线标准的突破
4. 致谢
工作开展过程及本文编写过程得到了以下同学的大力支持, 特此感谢:
感谢 @梅树起(澜生) @赵琦 同学在架构设计过程模型优化过程本文编写过程给予的大力帮助;
感谢 @胡珂(汝风) @彭金艳(九嶷) 同学在方案构思模型特征设计特征优化依赖数据生产预测效果优化模型应用本文编写等过程给予的大力帮助
来源: https://yq.aliyun.com/articles/520806