超级巴士智能商圈123

曾子剑

2015年7月加入去哪儿，之前就职于腾讯天美工作室，目前负责超级巴士交易流程业务，对算法，机器学习和统计分析有浓厚兴趣。

背景

首先向大家介绍下我们的超级巴士业务，这是国内车在交通运输上的一次创新，根据用户的需求设定路线，包括接机，送机，接站送站等服务，服务类似于大巴，但是相比大巴，我们能提供解决用户最后一公里，车型升级和快速准时等优点，用户只需提供等于或者略高于大巴的价格就能享受到近似于专车的服务，为用户出行提供了一种更经济实惠的方式 , 符合公司战略下沉宗旨。 根据用户的需求设定路线 , 这句话说起来很简单，但是在我们实现中可并不容易。我们将线路定义为商圈的组合，商圈定义了服务的范围。怎么规划商圈，使之能尽可能满足用户的用车需求，而又不至于过大，导致成本增加，服务质量下降，是超级巴士能否做好做大的重中之重。

智能商圈的演进

我们对外宣传都是以按照用户的询价数据动态规划商圈，但是实现起来也不是一步到位的。超巴刚上线的时候由于时间，人力等资源相对紧张，并且也缺乏相应的参考数据做支撑，所以商圈的制定我们采用人为的方式，将商圈规划下发给供应商，供应商根据主观印象进行规划。缺点是主观，漏掉了很多有需求的地方；不规范，有的地方画了很多本可以合并的商圈；效率低下，影响开城进度。

针对以上痛点：

首先我们建立了超级巴士的数据中心，搜集用户用车相关的历史行为。

目前智能商圈规划会使用到 3000w 超巴历史询价数据点，600w 酒店下单数据 (最近一周)和 35w 专车订单数据 (最近一周)。

算法介绍商圈点聚类

DBSCAN，相较于其他算法，具有：

聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类

与 K-MEANS 比较起来，不需要输入要划分的聚类个数

聚类簇的形状没有偏倚

可以在需要时输入过滤噪声的参数

评价商圈是否合规

我们定义：商圈覆盖率 =∑聚类数据点 / 数据点总数

【注：为保证聚类符合要求，我们只会选取聚类数据点至少大于总数据点十分之一的聚类】

我们需要计算出覆盖率 =50% 的 A 类商圈，=70% 的 B 类商圈，=80% 的 C 类商圈。

目前我们采用的是增加 DBSCAN 算法中 eps 的值，初始值设定为 0.1 公里，梯度上升，求解一个近视解。

流程如图：

绘制商圈

凸包算法 (Graham 扫描)

流程大致如下：

把所有点放在二维坐标系中，则纵坐标最小的点一定是凸包上的点，如图中的 P0。

把所有点的坐标平移一下，使 P0 作为原点，如上图。

计算各个点相对于 P0 的幅角 α ，按从小到大的顺序对各个点排序。当 α 相同时，距离 P0 比较近的排在前面。例如上图得到的结果为 P1，P2，P3，P4，P5，P6，P7，P8。我们由几何知识可以知道，结果中第一个点 P1 和最后一个点 P8 一定是凸包上的点。

以上是准备步骤，以下开始求凸包。

以上，我们已经知道了凸包上的第一个点 P0 和第二个点 P1，我们把它们放在栈里面。现在从步骤 3 求得的那个结果里，把 P1 后面的那个点拿出来做当前点，即 P2 。

接下来开始找第三个点：连接 P0 和栈顶的那个点，得到直线 L 。看当前点是在直线 L 的右边还是左边。如果在直线的右边就执行步骤5；如果在直线上，或者在直线的左边就执行步骤6。

如果在右边，则栈顶的那个元素不是凸包上的点，把栈顶元素出栈。执行步骤4。

当前点是凸包上的点，把它压入栈，执行步骤7。

检查当前的点 P2 是不是步骤 3 那个结果的最后一个元素。是最后一个元素的话就结束。如果不是的话就把 P2 后面那个点做当前点，返回步骤4。

最后，栈中的元素就是凸包上的点了。

框架设计

利用城市 + 服务类型 (接机，送机，接站，送站等)对数据进行分片，减小数据规模，形成计算任务。

利用 QSchedule 平台调度计算任务，负载均衡，并设定计算周期。

Redis 缓存商圈边缘点集合，提高查询速度。

网页工具可视化展示商圈和询价点效果。

计算完成后 qmq 通知订阅方来拉取结果。

效果展示

为超巴已开 34 个城市 近 200 种业务场景绘制 abc 类商圈。

所有商圈保证 100% 合规 杜绝人为主观不合理。

机器绘制 效率大大提升并且可以按照用户的行为动态调整。

总结

通过无监督性学习 DBSCAN 聚类和凸包算法规划商圈边缘点，我们已经能根据用户的行为数据比较理想的规划出商圈。我们还在逐步摸索求解更加准确的聚类，更快的提高运算效率，如果同事有好的解决方案，非常欢迎一起进行讨论。