解读:滴滴“猜你去哪儿”功能的算法实现

阅读数:997 2019 年 9 月 19 日 08:00

解读:滴滴“猜你去哪儿”功能的算法实现

产品

解读:滴滴“猜你去哪儿”功能的算法实现

图:滴滴“猜你去哪儿”产品形态

从产品的角度,滴滴“猜你去哪儿”是在用户打开滴滴,用户还未输入的情况下,猜测用户的想去的目的地(POI)并以 TIPS 的形式直接进行提示,该功能从产品上有两个好处:

① 能够减少用户的输入,如果猜测准确,用户直接点击目的地 POI 即可;

② 能够提升用户对滴滴的好感,提升用户体验和粘性,毕竟用户都是感性的,这样一个功能点如果足够准,就能让用户印象深刻。

技术

首先分析下该产品的业务场景:用户打开滴滴,绝大部分情况下,都是心中已经有要去的地点了,技术需要做的只是将该 POI 猜对并提示出来。所以该场景所使用的技术,就和传统的视频,音乐,甚至电商推荐有很大区别:该过程不需要协同,而在乎准确,用户不会因为你打开滴滴的时候推荐的 POI 和他的兴趣比较相关就会去,在打开滴滴前,用户就已经做了决定。

换句话说,用户要去的地方是极度个性化的,几乎没有泛化,所以在技术上有以下两点设计:

① 召回的目的地候选 POI 就是用户的常去地;

② 去什么地方仅取决于用户及他所处的上下文,此处上下文包括位置,时间等。而所有的上下文中,从滴滴的论文中可以看到,最重要的就是 3 个因素:出发时间,出发地点,是否为工作日。

解读:滴滴“猜你去哪儿”功能的算法实现

图:最有效的场景上下文

算法

滴滴使用了一个比较简单的算法来解决该问题:针对每个用户的数据,对每一个去过的候选目的地,使用高斯分布来构建基于上下文的条件概率分布。之所以使用,之所以使用高斯分布,是从数据上来看,出发上下文和去的目的地之间,分布的确是一个钟形。

解读:滴滴“猜你去哪儿”功能的算法实现

图:特定目的地出发时间分布

如上图,如仅考虑时间一个维度,用户出发去特定目的地的分布,符合高斯分布。

故使用的模型形式如下:

解读:滴滴“猜你去哪儿”功能的算法实现

图:贝叶斯模型

其中 X 为当前用户所处上下文, Y=yi 表示目的地为 yi。其模型形式为给定上下文后,计算用户去目的地 yi 的概率,转化为使用贝叶斯方式计算,此时只要计算用户去各个目的地的先验,以及用户去各目的地的上下文概率即可。

先验计算比较直接,直接统计用户去各目的地的频次即可。

解读:滴滴“猜你去哪儿”功能的算法实现

图:特定目的地概率统计

P(X|Y=yi)则将其表示为高斯分布。简单出发,此处 X 如果仅包含时间维度的话,作如下表示:

解读:滴滴“猜你去哪儿”功能的算法实现

图:建模为条件概率分布

高斯分布仅需要给出 μ 和 variance 即可。而两个值通过观测样本即可给出。但此处有个细节,就是时间是以 24 小时的周期函数,不能直接使用数值方式计算均值 μ,故文中提出了计算时间维度 μ 的方法。

解读:滴滴“猜你去哪儿”功能的算法实现

图:求解 μ

其思路比较直接,其中有两个关键点:

① 时间以 24 小时作为周期,那么两个时间的差,不能大于 12 小时;

② μ 和所有时间点的差值的平方和最小,求解 μ 即可。

解读:滴滴“猜你去哪儿”功能的算法实现

解读:滴滴“猜你去哪儿”功能的算法实现

图:求解 μ,时间距离定义

同理可求解 variance。

以上方法仅使用了时间一个上下文,在实际中较为重要的上下文为时间,出发位置,是否工作日,以相似的方式,将模型构建为多维高斯分布并使用贝叶斯方式即可计算。

结果透出

使用以上方法,即可计算用户在特定场景上下文情况下去特定 POI 的概率。当用户使用滴滴时,只需要使用该用户当前的场景上下文,使用以上方法均计算一遍概率,再根据阈值挑出 TOP N 即可作为“猜你去哪儿”的结果。

算法不足

该方法的优点是足够简单,结果容易解释。缺点也很明显,主要包含以下几点:

① 场景上下文使用较少,也不太方便引入更多上下文,例如天气等;

② 用户行为使用较少,仅使用上下文信息进行单点预测,没有用到用户的行为轨迹信息。

解决第一个问题的思路比较直接:更多的特征,描述能力更强的模型。

第二个问题会比较有挑战,受限于滴滴的产品使用场景,滴滴能拿到的数据仅为用户行前的位置信息,以及用户行中的轨迹订单信息,但对用户行前之前的数据一无所知,所以如果华为,或者小米这样从底层操作系统角度能够完整拿到用户轨迹的厂商,可以使用用户长期行为模式,短期轨迹和即时上下文,更加精准地预估用户行为。当然这样也会面临着更大的用户隐私风险,目前是无法做到的,毕竟用户的轨迹信息基本是用户最私密的数据了。

参考文献

Zhang L, Hu T, Min Y, et al. A Taxi Order Dispatch Model based On Combinatorial Optimization[C]// Acm Sigkdd International Conference on Knowledge Discovery & Data Mining. 2017.

作者介绍

Dustinsea,混迹于各大互联网公司及创业公司;和自己赛跑的人,专注于推荐系统和互联网流量变现 & 推广,目前就职于阿里巴巴。

本文来自 DataFun 社区

原文链接

https://mp.weixin.qq.com/s?__biz=MzU1NTMyOTI4Mw==&mid=2247493496&idx=1&sn=16a9495c9a0452ef60e38bb129105b02&chksm=fbd75514cca0dc020fa508aa34e01a3c17949e70cbccd5531122556f14c7351d15da93775f17&scene=27#wechat_redirect

评论

发布