用机器学习模型预测驾车导航到达点可信度

  1. 云栖社区>
  2. 博客列表>
  3. 正文

用机器学习模型预测驾车导航到达点可信度

甘道夫阳 2018-03-08 19:47:23 浏览8441 评论0

摘要: 一种通过机器学习方法进行驾车导航到达点坐标可信度预测的方案。 本文为脱敏删减版,阿里的同学可到内网ATA阅读原文:https://www.atatech.org/articles/101742

1.导语

1.1.术语

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

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

 3)   亲子关系:POI的从属关系,例如,商场是所有内部商铺的父点;

 4)   众包:数据采集方式的一类,依靠用户采集地图数据;

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

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


1.2.背景

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

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

9fa7347f32d6015899fe7e637b79df000d771e4e

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

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

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

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

586077ceac11f919480c584a72b066df8138120c

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

4192eca9b375916e64d5d5223d520a9dc364484d

 为解决“显示坐标抓路”策略的缺陷,提升整体到达正确率,高德地图组建了到达点挖掘项目组。在过去的一年时间里,我们分析了大量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.版本二:二阶段动态参考点

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

6e8b2a78f2c4d518fa20225b68751cf36cec2bf2

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

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

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

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

77ff19ad1bf2c27295003a7330d4d3f01e2c4fd4

 

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

6c13bd6c4ae010eda7168b757a3471dc20a42de1

 

dc7b633b86d94b265a39721b62ce4dcb1d8c9400

bea71c05d6fc52ad9b67cc48f216ab3e1704b5b1


3.2.实战效果

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

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

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

 

4.致谢

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

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

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


用云栖社区APP,舒服~

【云栖快讯】《阿里巴巴Java开发手册》(详尽版)已经上线!您的Java学好了吗?如果没有,那就赶紧加入学习吧!  详情请点击

网友评论

甘道夫阳
文章1篇 | 关注4
关注
阿里云机器学习是基于阿里云分布式计算引擎的一款机器学习算法平台。用户通过拖拉拽的方式可视化的... 查看详情
大数据开发套件(Data IDE),提供可视化开发界面、离线任务调度运维、快速数据集成、多人... 查看详情
用于实时预测用户对物品偏好,支持企业定制推荐算法,支持A/B Test效果对比 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
飞天发布会第8期:智能选址解决方案

飞天发布会第8期:智能选址解决方案