抖音技术能力大揭密!钜惠大礼、深度体验,尽在火山引擎增长沙龙,就等你来! 立即报名>> 了解详情
写点什么

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

2019 年 9 月 19 日

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

产品


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


从产品的角度,滴滴“猜你去哪儿”是在用户打开滴滴,用户还未输入的情况下,猜测用户的想去的目的地(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


2019 年 9 月 19 日 08:001445

评论

发布
暂无评论
发现更多内容

超越竞争文化:致善式创新能否打造手机产业的“海法城”

脑极体

直播卖货已成趋势

anyRTC开发者

音视频 WebRTC RTC

支撑2715​亿元海量订单 揭秘京东大促背后的数据库基石

京东科技开发者

数据库 数据仓库 云服务 云数据库

揭秘双11:前端技术体系

阿里云情报局

前端 前端进阶

程序员双十一剁手指南

数据君

腾讯云 程序员

6个JDK自带JVM调优工具,一次性打包给你说清楚

田维常

jvm调优

程序员如何判断跳槽岗位是否有坑!

Java架构师迁哥

甲方日常 52

句子

工作 随笔杂谈 日常

读完某C++神作,我只记住了100句话

MySQL从删库到跑路

c++

SQL数据库集合运算

正向成长

SQL表联结 SQL集合运算

Java中NullPointerException的完美解决方案

Silently9527

java8 Optional

花四个月和阿里面试官“大战”7回合,成功将其“斩于马下”!复盘面试题及答案!

Java架构追梦

Java 阿里巴巴 面试题 面试经历 java架构

有点意思的gif动图生成平台开发实战(二)

徐小夕

Java Vue 前端 GIF React

Java中的线程与C++中的区别

jiangling500

Java c++ 线程

这份算法攻略,我拿到了5个大厂的offer

yes

面试 算法 笔试

架构师第一期作业(第 9 周)

Cheer

作业

代码写的烂才是原罪?字节三面+微信四面+PayPal四面,大厂面经分享

Crud的程序员

架构 面试 数据 字节

Vokenization:一种比GPT-3更有常识的视觉语言模型

脑极体

厉害了!阿里内部都用的Spring+MyBatis源码手册,实战理论两不误

小Q

Java spring 学习 面试 mybatis

断供,危机or契机?开源商业化or社区化?后疫情下的开源路这样走 | 大咖对话

易观大数据

即将写入MySQL源码的官方bug解决之路

数据君

MySQL

响应式关系数据库处理R2DBC

程序那些事

MySQL R2DBC 程序那些事 响应式系统 响应式数据库

区块链数字货币商城系统开发模式

薇電13242772558

区块链 数字货币

.net core增强工作流组件,基于稳定平台,多项目整合开发

雯雯写代码

什么是服务器租用?

德胜网络-阳

容器和虚拟机到底有啥区别?

网管

容器 虚拟机 容器化

程序员求助:腾讯面试题,64匹马8个跑道,多少轮选出最快的四匹

Java架构师迁哥

【JVM】肝了一周,吐血整理出这份超硬核的JVM笔记(升级版)!!

冰河

性能优化 内存模型 JVM 堆栈 JVM笔记

2020双十一,阿里云GRTN拉开直播和RTC技术下半场的序幕

阿里云视频云

架构 云直播 直播 流媒体 直播架构

两句话给面试官讲清楚IOC

执墨

spring ioc 依赖倒置原则 springioc 控制反转

adb的常用操作命令

Yolanda_trying

Study Go: From Zero to Hero

Study Go: From Zero to Hero

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