阿里工业级LBS DMP设计思路

先打个广告: 团队长期招p6~p9数据,工程,算法; 业务发展快。 感兴趣的同学可直接关注以下公众号获取岗位信息:

前言

通过阅读本文, 可以有两方面的收获:

  1. 我们针对LBS 场景的DMP建设, 定义了新的基于底层人地关系原子能力的范式,避免了传统DMP用户数据生产过程中, 标签建设代价过大,无法迅速扩展的缺陷
  2. 展示了分层DMP建设的框架

个人隐私相关的行业背景

最近国家密集出台史无前例的互联网个人隐私管控的法律,以及算法管控备案的条纹, 例如:《互联网个人信息保护法》中明确对互联网APP个人信息收集,利用做了非常严格的限制。

对于各种设备级ID的使用, 例如原来imei, idfa, androidid等都有较为严格的限定,对于类似于轨迹,定位数据也做了较为严格限定。

从系统分发的角度, 《互联网信息服务推荐算法管理规定》也对算法的分发提出了较多要求, 对于个性化, 大数据杀熟等国家也在加强备案和管控。

在这样的行业背景下, 互联网的大数据使用会逐渐趋于规范和精细化。 这里需要明确的是, 国家不是限定大数据的发展,而是限定原有不规范,粗放式的数据使用。

例如早些年我的确听说有些公司对外提供DMP服务,按照请求次数收费,各种个人隐私数据不管应用方的类似随便使用, 这样的确是很恐怖的情况。 因为现在每个人在手机上产生的数据太丰富: 包括家庭住址,信息获取偏好, 购物, 所在位置等。

挑战

在这样的大背景下, 在构建工业级的LBS DMP体系的时候, 就会面临两大类挑战:

  1. 传统的技术挑战, 更多是技术问题, 包括如何更高效,实时地处理海量数据; 如何从数据中,对业务的LBS 能力进行原子能力的抽象; 基于原子能力如何对数据资产沉淀, 以及如何更通用化, 更高效地对外提供数据能力的支持。 每一个点均能衍生出较多非常多的技术挑战点需要攻克。
  2. 新的隐私数据安全, 包括哪些隐私数据我们能够收集, 哪些能够使用, 应该如何使用, 提升个性化效果以及触及个人隐私的边界在什么地方,这些都需要在数据使用,系统设计实现的时候充分考虑。 毕竟我们在社会主义的红旗下,需要做遵纪守法的产品研发,打造合法的系统。

同时,在大数据时代,我们也不可能就因为个人隐私风险而放弃对数据的建设, 毕竟互联网快速发展了20多年,基于数据算法的个性化被证明是提升系统效果的利器, 过去工业界,学术界的算法得核心也是数据驱动的个性化精准分发, 同时以后随着数字化的发展, 更多IOT设备的加入导致更多的信息需要处理都需要我们有更加强大的数据处理能力。

所以各个公司, 特别是阿里,腾讯,字节等大厂, 更是会在这一块工作上持续投入。 都会构建自己工业级的LBS DMP,以便在各种搜广推的分发应用中,提升分发的效率。

下边就为大家介绍我们LBS DMP建设的思路。

设计


图:LBS DMP架构分层图

工程实现

从具体设计实现的角度,高德的LBS DMP从工程的角度和业界是比较类似的,从底层数据到上层应用,主要分成以下四层:

  1. 底层原始数据数仓,该层主要包括原始的数据收集,数仓ETL建设,以及对应的实时计算。具体的数据包括超级APP端内的搜点规划导航等LBS数据和用户行为数据的处理,以及高德开放平台数据。这两类数据一个最大的区别就是APP端内数据可以对应到具体的用户,但开放平台的一部分数据,我们是对应不到具体的用户的,拿不到体用户ID的数据,这些数据可以用来做热力相关的应用。具体实现层面,该层我们会基于ODPS和Blink来进行数据处理。
  2. 第二层是我们的人地关系算法层,该层更多的是基于我们的原始数据做进一步的深加工,包括对应的数据挖掘以及实时的算法处理。该层的算法挖掘质量会决定最终DMP效果。在实现层面,我们会用到非常多的深度学习,以及推荐类似的算法,所以也需要算法架构的支持,这次我们就基于AI OS去打造我们的数据挖掘和匹配逻辑算法。但是我们会给我们的应用场景去抽象,我们极少的原子能力,不求多,但求精。
  3. 第三层是我们的数据资产沉淀层,我们需要基于第二层打造出来的核心原子能力,进行灵活的拼装,组成上层应用,包括实时或离线的特征和标签,这些特征和标签既有表征用户长期兴趣特点的类型,又有实时用户的状态,行为的类型,例如,用户长期的类别偏好,兴趣偏好,这些都是用户长期的数据积累下来的,并且是在一定时间之内,不太会改变的用户的固有属性,这种就是长期的兴趣标签数据,另外,类型是跟永辉相关的事实,实的会很快改变的,需要快速补充的类型,例如,当前用户的需求是不是在饭店需要吃饭?是不是在外地需要订酒店?甚至细化到最近30分钟是不是有酒店需求这样的动态标签,这些都是实时类型。 从我的角度,我们对标签的定义进行了扩展:这些都是标签,只是长期兴趣标签总体来说没有时效性,相对稳定而短期实时标签具有动态性和时效性。
  4. 第四层就是服务层,例如,以什么样的方式对外提供数据服务,构建什么样的中台,什么样的通用的数据方式去提供通用的数据解决方案。这层我们会基于阿里的 AIOS,并且配合我们的数据管理平台,对外提供通用化的数据伏。

算法

从算法的角度,最重要的就是我们如何去抽象我们的LBS场景问题,将众多的数据以及对应的应用抽象为可数的几个核心原子能力

原子能力
这里先解释一下什么是原子能力:原子能力就是基于最底层的抽象,不能再分割的能力,而上层的更复杂的业务能力,都是由底层的可数的原子能力拼装组合并演绎而出。

之前在听美团的干嘉伟的一个分享的时,他提到所有的问题都可以进行拆解,再打碎为原子能力后重构,而对LBS场景所有的问题都可以根据时间,空间去进行拆解,所以我们在这样的拆解框架之下,只要我们的原子能力从时间和空间的角度分成点线面(空间)*过去现在未来(时间)的模式:


图:LBS 时空原子能力拆解

我们在建设上层特征及标签的时候,不再遵循传统的方式对标签进行一对一的深加工定制,因为这样是有一个扩展性的限制的,扩展性标签的代价是线性的,当标签非常多的时候,代价是不可承受的。不可能无限的扩展。

例如,在之前的系统中,我们建设了400多个标签,但之后就无法再高效准确的维护对应标签的数据质量,所以后来我们转变思路:所有标签都是基于我们的原则能力,在上层,进行组合加工得到最终的标签,底层的原则能力会持续地不断深化,

对于原子能力,我们在单点上进行深化建设,底层的原子能力,我们使用了非常多的深度学习及图关系的算法,讲原子能力做的足够准确,相反上层的组合做的足够简单,并且可解释,当然,底层的原则能力都需要配合debug分析平台来提升数据质量。

这一部分其实是这个算法的核心,因为算法会涉及到比较多和业务相关的数据能力,数据算法能力,所以此处主要就说一下思路更多的时间此处就不展开了。

这里也有一个比较有意思的现象,就是无论线上的搜广推还是离线的LBS标签建设,在实现的时候都是使用相同的思路。

例如,我们在线上搜光腿检索轮实现的时候,经常会进行召回排序机制将各个环节分开进行;比较有意思的是,在离线进行数据处理标签建设的时候,也会使用类似的思路,都是先招呼一个大集合,然后再去做排序,最后再进行挑选。像我们在识别一个用户,他的家庭住址的时候,也会先挑出来这个用户候选的家庭住址,然后再去做打分排序,最后再选TOP N。

或者在进行路线规划的时候,也是先选择一部分的候选路线,再进行排序。整个过程从框架思路上没有本质区别。所以这应该也是搞互联网技术的人比较倾向于招搜广推经验丰富的候选人,因为搜广推比较有经验的话,这些技术迁移到其他的领域也会比较方便。

从本质上来说,这些操作都是信息处理过程,都是user和item的匹配,这可能是这些技术比较相近最本质的原因。

成果

和公司相关的业务此处就不再展开。此处人地关系的通用原子能力,我们也发表了对应的论文,会在后续的文章中介绍。具体参见《learning the continuous context-aware temporal knowledge graph representation for user and poi understanding》

Reference

  • Learning the Continuous Context-aware Temporal Knowledge Graph Representation for User and POI Understanding
  • 阿里巴巴 AIOS

[LBS]工业界ETA应用及滴滴WDR技术

介绍

最近几年共享经济比较火,也出现了很多成功的共享经济企业,而共享经济中比较成功的模式大部分都围绕着共享出行展开业务,例如Uber,Lyft, 中国的滴滴,以及近两年遍地开花的共享单车公司(虽然现在部分共享单车的业务已经在停滞或萎缩)

与此同时,很多关键技术也随着共享经济的发展而被重视起来。像MM(Map Matching)[10],RP(Route Plan),Navi(Navigation)以及ETA(Estimation Time of Arrival),这些都是LBS中比较基础同时比较重要的关键技术,无论是共享单车,出租,快车,顺风车等在进行调度,收费定价的时候,都会涉及这些关键技术。

本文就向大家专门介绍其中的一个关键技术:ETA,内容包括: ETA是什么? 为什么重要? 常用ETA技术有哪些,有哪些优缺点,以及现在up-to-date的ETA技术实现细节及效果。特别会重点介绍目前滴滴已经公开发表的WDR模型在ETA上取得的成果

P.S. 本文不会透露滴滴出行内部仍在进行的项目及对应数据,涉及到的技术细节及数据均已通过论文,或者PR文对外公开发表

图:滴滴ETA(接驾ETA以及送驾ETA)

ETA是什么

从业务的角度讲,ETA就是预估一个行程中,从出发时间到到达时间的时间差,例如滴滴快车中预估到达时间,或者高德导航中规划路线行驶所花的时间

图:高德ETA(2:整体路径规划时间预估)

从技术上,我们可以将ETA的一次调用,看成是一次query,每个query的内容为:<o_i,d_i,s_i>,表示第i个请求o,d,s分别表示起点位置(original),终点位置(destination),起点时刻,ETA需要给出的就是t_i  = e_i - s_i,其中e_i为行驶到终点的时刻

ETA问题看似很直接,但现实中需要准确预估ETA却非常有挑战。挑战主要来自于以下几方面:

  1. 时空维度上数据较为稀疏:因为需要预估的物理世界的数据,在时空维度上非常稀疏,虽然滴滴对外宣称每天有近3KW单的订单,但这些订单所产生的轨迹,也不足于充分覆盖时间+空间的路网数据。例如光北京的路网link数就有超过1Million,而从时间的维度,每2分钟发布一次路网交通状况,全天时间维度上有720的时间切片,故时空维度仅北京市共需发布约2亿个发布值,轨迹数据覆盖会非常稀疏。
  2. 存在较多突发局部事件:且很多时候还存在较多不确定性,例如突发性的车祸,或者交通灯损坏,修路,交通管制,等都会导致路网历史信息失效。

数量较少但影响全局的事件:而碰到节假日或者恶劣天气,整个物理世界的交通也会从系统层面恶化导致预测算法整体失效

为什么重要

但ETA又是一个很基础的关键技术,其应用场景非常广泛, 例如路径规划中用来寻找时间最短的行驶路径,分单,定价,拼单等场景都依赖于ETA。其准确性会直接影响到整个共享出行平台的效率,举几个例子:

  1. 体验:选定一条路线后,起终点的预估时间不准确,会直接影响用户对平台的信任,特别是很多时间敏感场景,例如赶飞机
  2. 计价:很多共享出行平台都会在计费的时候引入行驶时间,ETA不准会导致计价预估不准,如果是事前一口价等策略,则可能导致平台亏钱
  3. 调度:例如拼车场景,ETA不准则会导致拼成率大打折扣,影响用户体验,口碑及平台,司机收益

因为上述ETA的基础性&重要性,目前滴滴每天的ETA调用次数超过40 billions次(数据出处:https://outreach.didichuxing.com/tutorial/kdd2018/)

WDR模型

传统方法主要分为两类:

  1. route-based method: 该类方法将route 的ETA问题分解为 subroute+crossing的子eta问题。其中subroute为待预估的<o, d> route的子route, 一般地图行业叫link,为表征地图路网的最小单位,长度为数米到数百米不等,crossing为交叉路口,交叉路口因受到交通灯等的影响,故单独抽离出来。该类方法一般可以作为ETA的baseline,来评估复杂ETA算法的效果。该方法的优点就是计算比较直观,简单,而且具有很强的可解释性,出了问题后容易分析定位。缺点也很明显:时间空间上数据覆盖较低,误差容易积累,因为没有用上道路,时序,个性化等特征,故效果有提升空间。具体参见图:route-base method方法示意
  2. 另一类算法我们称为data-driven method,例如在预估<o, d>的ETA时,可以使使用neighborhood-based的方法找到相似的轨迹时间进行加权来计算ETA[5],类似于推荐问题(具体参见图:neighborhood-based方法),该类问题的缺点仍然是时空上的覆盖较为稀疏,比较适合车流量较大,速度相对均衡的高速或者快速路。例如,在公开的‘Shanghai Taxi Data’上, 虽然后超过3亿个点的记录,但仍然有50%的道路没有被任何轨迹覆盖,且该数据还没考虑时间维度,并且在时间维度上,高峰期和平峰期的数据分布也不一样

图:route-base method方法示意图

图:neighborhood-based方法

在解决ETA问题的同时,也会衍生出来不同分支的子问题,例如比较重要的一类问题是:我们不仅需要预估具体route的eta,同时需要预估对应eta的概率。应为有些场景我们并不需要最短的eta,但需要时间预估最准确的eta,例如赶飞机火车的场景, 一条预估50分钟的路线并不比另一条1小时的route好, 如果后者的预估置信度比前者高很多的话。该类问题可以参考[7]

而比较up-to-date的方法是使用模型来解ETA问题

问题定义

使用传统机器学习的概念, 可以将ETA问题定义为regression问题,即每条sample为给定<o,d,s>以及该sample对应的特征, 将问题建模成回归问题,使用模型来回归具体的ETA值

特征

传统的route-based方法及data-driven方法仅使用计算的路网的traffic特征来计算ETA,该处的traffic仅指具体子route(或称为link)的通行速度(或者对应的通行时间,因确定route后,route长度固定,故通行速度和时间可以相互转换)。

Traffic特征是计算ETA极其重要的特征,但在计算ETA的过程中,我们能够获取到更多更丰富的特征来提升ETA预估的准确性。route-based方法和data-driven方法的问题是很难直接使用这些特征,但复杂模型却能够使用这些特征提升模型的效果。这些特征包括:

  1. 空间特征spatial information:包括<o, d>路线之间经过的link序列,交叉路口序列(intersections),经过的红绿灯信息,走过的(拥堵)POI等
  2. 时间信息(temporal information):例如当前时间的月份,是一年中的第几天,周,小时等;以及根据历史信息计算出来是否为早晚高峰or非早晚高峰,是否节假日等;这些特征可能需要经过预处理才能得到, 甚至需要将时间信息映射到频域,找出频域特征后引入模型(参见后续博文:《LBS时空特征的提取技术》)
  3. 路况信息(traffic information):每两分钟发布一次全网(路网中所有link)的通行速度,该通行速度作为该2分钟时间片内全路网通行能力的重要描述。该路况信息在ETA的计算过程中比较基础也至关重要,发布路况的准确性会直接影响最终ETA的预估准确性,而且根据该路况信息,即可使用route-based方法计算出baseline的ETA。
    另外路况信息发布是否准确也是一大挑战,因为在时空维度下,经过每个 link的轨迹数也比较少
  4. 个性化信息(personalized information) 包括driverid, 乘客id以及汽车相关的属性
  5. 其他特征:例如天气特征等,该类特征对大盘的影响相对较少, 但对用户体验影响非常大,例如下雨天,整体路网的拥堵程度会大幅上升,但下雨天的占比相对较少, 导致模型不一定能学出该规律,但异常天气下如果ETA不准,又会极度影响用户体验,故最后可能需要使用一些特殊逻辑进行定制处理

优化目标

模型候选的优化目标可以是MAPE,MAE,MSE等,考虑到预估偏差的大小对用户感知体验的影响,与行程本身的时长有关, 故前期在提升模型总体效果的时候,离线模型使用MAPE作为优化目标。在模型基础能力提升到一定程度后, 主要考虑用户体验影响较大的极端CASE时,会同时兼顾异常CASE率,对模型效果进行评估。

其中MAPE定义为:

模型

如,‘问题定义’部分所述,问题一旦定义成regression后, 即可使用传统回归模型进行解决。

近些年深度学习比较火,所以在有足够数据,足够计算资源,对效果又有较高要求的场景, 一般都会使用的深度学习来解决。相较之下,传统的浅模型就没有那么高端了, 但这些模型在特定的场景, 仍然会是比较好的选择。 例如我们在使用模型预估当前的路况状态(行驶道路的状态:畅通,缓行,拥堵)的情况下,使用GBDT仍然会是比较好的选择, 一则我们的Ground Truth较少,目前主要还是通过人工标注获取, 另外则是我们的应用场景需要有较强的可解释性,否则收到用户或者业务方的投诉case时,很难进行分析解释。

在ETA场景中, 浅模型和深度模型的特点如下:

浅模型

传统效果较好浅的模型有gbdt, fm, 这两个模型各有优缺点, gbdt上手比较方便,且能够直接处理连续值,能够自己进行特征选择与组合,但gbdt很难处理特征量较大的场景;fm的效果依赖于特征的表达, 表达能力有限, 对于滴滴的ETA,我们能够获取海量的训练数据,且从加强表达能力的角度考
虑, 深度学习会更胜一筹

图:Wide&Deep模型示意

深度模型

常用的深度模型很多,而且各自有适合自己的优缺点和应用场景,而现在的趋势是构建复杂网络,在复杂网络模型中, 结合浅模型和深度模型的优点,最大化提升预估效果,比较经典且在工业界落地的方法是GooglePlay App推荐场景使用的方法,参见《Wide&Deep Learning for Recommender System》,该方法使用线性模型作为Wide部分进行exploitation,而使用Deep部分进行exploration

Wide&Deep两部分的作用如下:

  1. Wide部分为线性模型,将特征映射到较高维度空间;一般具体的特征会先进行交叉(也相当于在线性模型中引入部分非线性特征);Wide部分主要作用是做memorization,可以充分exploit历史信息,具有较强的可解释性,并且效率较高
  2. Deep部分:将高维特征映射到低维的dense特征(进行embedding),之后进行concate。 Deep部分主要是进行exploration;embedding相当于从已经出现过的数据中学习feature的co-corelation,deep部分更倾向于多样性进行explore

但在滴滴ETA场景,我们引入了世界序列模型LSTM,因为传统W&D方案存在缺点:每个sample的feature必须要对齐,但对于给定<o,d>pair对应的route中,组成route的link数量不一样,一般起终点间距小则link数量会少,反之则link数量会比较多,这些link自身的属性可以作为强特征,对最终ETA的效果影响较大,但传统W&D模型在使用的时候,因为不能处理变长的link序列,故模型很难用到link的local,而只能用到这些link的统计信息,故需要引入额外的网络结构来学习这些local信息;此时时间序列模型能够处理变长输入,故是较好的选择。

所以很自然地在W&D模型基础上增加LSTM结构来adopt local的link序列信息,最终形成滴滴ETA使用的WDR模型

图:WDR模型,其中Wide部分既有dense特征也有sparse特征;而Deep部分的Sparse特征需要首先使用embedding方式转为Dense特征,之后进行Concatenation

 

说到这里简单岔开一下,我们在进行特征设计,或者模型网络结构设计的时候,背后都是有容易理解&解释的Philosopy的:W&D的思路是使用Wide部分进行Memorization,以便对历史信息进行exploitation,使用Deep部分寻找特征之前潜在的Co-Correlation,对特征进行exporation,而R(LSTM)部分则是为了处理W&D处理不好的link边长序列

在具体实现过程中,线性部分一般会先做特征交叉;Deep部分会先将稀疏特征使用embedding方式转成dense特征,lstm部分则在输入link序列后,使用最终的hidden status输入值最后一层,作为最上层regression

评测方法

在评测模型的时候,我们首先对数据进行了预处理,移除了异常的trajectories, 例如travel time < 60s 或者speed>120km/h的trajectories;之后我们使用3个月的数据,并分接驾数据(pick-up)和送驾(trip)数据分别进行模型训练,并将接下来两周的数据按时间维度分为两份,分别作为验证集合(validation)和测试集(test)评估模型效果

指标

离线使用MAPE(之前提总体乘坐时间越长,偏差的容忍就越长)在线则同时使用MAPE, APE20, bad case率对模型效果进行评估,其中: APE20表示absolute error 小于 20%的case的占比,而相反地,bad case 率定位为预估偏差大于50%,或者大于180秒的case,该指标用于衡量bad case出现的概率,控制极端误差case对用户体验的影响

效果

此处仅给出送驾段MAPE衡量的模型效果,现实中送驾段MAPE能从baseline的15.01%降低到WDR的11.66%,而WDR效果可以比GBDT好2.5%.

其中WDR的R部分, 在送驾段能带来1.77%的MAPE收益,可见将local的link信息使用时间序列方法引入模型,能够带来较大的效果提升。

当然,在算法需要上线时,还需要考虑线上服务的性能,故我们还尝试了另外一种更高效的基于Attention机制的深度网络,以后再向大家介绍。

参考文献

  1. 《2017年滴滴出行平台就业研究报告》
  2. Gers, Felix A., Jürgen Schmidhuber, and Fred Cummins. "Learning to forget: Continual prediction with LSTM." (1999): 850-855.
  3. Cheng, Heng-Tze, et al. "Wide & deep learning for recommender systems." Proceedings of the 1st Workshop on Deep Learning for Recommender Systems. ACM, 2016.
  4. Wang, Zheng, Kun Fu, and Jieping Ye. "Learning to Estimate the Travel Time." Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM, 2018.
  5. Wang, Hongjian, et al. "A simple baseline for travel time estimation using large-scale trip data." Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2016.
  6. Wang, Yilun, Yu Zheng, and Yexiang Xue. "Travel time estimation of a path using sparse trajectories." Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014.
  7. Asghari, Mohammad, et al. "Probabilistic estimation of link travel times in dynamic road networks." Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2015.
  8. https://outreach.didichuxing.com/tutorial/kdd2018/
  9. google官方wide&deep实现:https://github.com/tensorflow/models/tree/master/official/wide_deep
  10. map-matching:http://www.semocean.com/lbs%E5%9C%B0%E5%9B%BEmap-matching%E6%B5%81%E8%A1%8C%E7%AE%97%E6%B3%95%E5%8F%8A%E5%BA%94%E7%94%A8/

更多内容也可参见: http://www.semocean.com