LBS猜你去哪儿功能实现

最近看了一篇比较有意思的文章,关于滴滴’猜你去哪儿’功能的算法实现,在这里记录下。

产品

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

从产品的角度,滴滴’猜你去哪儿’是在用户打开滴滴,用户还未输入的情况下,猜测用户的想去的目的地(POI)并以TIPS的形式直接进行提示,该功能从产品上有两个好处:1是能够减少用户的输入,如果猜测准确,用户直接点击目的地POI即可;2是能够提升用户对滴滴的好感,提升用户体验和粘性,毕竟用户都是感性的,这样一个功能点如果足够准,就能让用户印象深刻

技术

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

换句话说,用户要去的地方是极度个性化的,几乎没有泛化,所以在技术上有以下两点设计:1,召回的目的地候选POI就是用户的常去地;2,去什么地方仅取决于用户及他所处的上下文,此处上下文包括位置,时间等。而所有的上下文中,从滴滴的论文中可以看到,最重要的就是3个因素:出发时间,出发地点,是否为工作日

图:最有效的场景上下文

算法

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

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

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

故使用的模型形式如下:

图:贝叶斯模型

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

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

图:特定目的地概率统计

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

图:建模为条件概率分布

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

图:求解u

其思路比较直接,其中有两个关键点:1,时间以24小时作为周期,那么两个时间的差,不能大于12小时;2,u和所有时间点的差值的平方和最小,求解u即可。

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

同理可求解variance。

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

结果透出

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

算法不足

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

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

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

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

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

参考文献

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.