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

产品

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

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

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

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

技术

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

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

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

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

图：最有效的场景上下文

算法

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

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

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

故使用的模型形式如下：

图：贝叶斯模型

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

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

图：特定目的地概率统计

P（X|Y=y_i）则将其表示为高斯分布。简单出发，此处 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