A cost

一个针对出租车司机有效花费的推荐系统

摘要

    GPS技术和新形式的城市地理学改变了手机服务的形式。比如说，丰富的出租车GPS轨迹使得出做租车领域有新方法。事实上，最近很多工作是在使用出租车GPS轨迹数据来开发手机推荐系统。这些系统可以推荐一系列的载客点，为了使得在最短的驾驶距离里最大可能地找到一个乘客。然而，在现实世界中，出租车的收入和有效的驾驶时间息息相关。换句话说，对一个出租车司机来说，在找到一个乘客前知道一个确切地驾驶路径来缩短驾驶时间更加重要。最后，在本文中，我们提出了开发一个收益比高的推荐系统。开发的目的是使得按照推荐的路径寻找乘客获得最大化收益。特别地，我们首先定义了一个净利润目标函数来评价驾驶路径的潜在的收益。然后，通过挖掘出租车历史轨迹，我们开发了一个图来表示一个路网，并且提供了一个暴力的方法来生成推荐的最佳驾驶路径。然而，沿着这个方法，一个关键的挑战是图的计算的巨大开销。因此，我们开发了一个新的递归策略，基于净利润函数的特殊形式，有效地寻找最佳候选路径。特别地，不同于推荐一个连续的载客点并且让司机决定如何到达这些点这种方法，我们的推荐系统能够提供一整条驾驶路线，并且出租车司机通过推荐能够找到获得最大潜在在收益的乘客。这就使得我们的推荐系统相对其它已有的推荐系统更加实用并且收益更多。最终，我们在一个现实世界的数据集上开展了实验，数据集来自San Francisco Bay地区，并且实验结果清楚地验证了我们提出的推荐系统的有效性。

关键词：Cost-E ffective, Mobile Recommender Systems, Taxi Drivers

1. 简介

GPS技术和新形式的城市地理学改变了手机服务的形式。比如说，丰富的出租车GPS轨迹使得出做租车领域有新方法。事实上，最近很多工作是在使用出租车GPS轨迹数据来开发手机推荐系统。这些系统可以推荐一系列的载客点，为了使得在最短的驾驶距离里最大可能地找到一个乘客。然而，在现实世界中，出租车的收入和有效的驾驶时间息息相关。换句话说，对一个出租车司机来说，在找到一个乘客前知道一个确切地驾驶路径来缩短驾驶时间更加重要。最后，在本文中，我们提出了开发一个收益比高的推荐系统。开发的目的是使得按照推荐的路径寻找乘客获得最大化收益。特别地，我们首先定义了一个净利润目标函数来评价驾驶路径的潜在的收益。然后，通过挖掘出租车历史轨迹，我们开发了一个图来表示一个路网，并且提供了一个暴力的方法来生成推荐的最佳驾驶路径。然而，沿着这个方法，一个关键的挑战是图的计算的巨大开销。因此，我们开发了一个新的递归策略，基于净利润函数的特殊形式，有效地寻找最佳候选路径。特别地，不同于推荐一个连续的载客点并且让司机决定如何到达这些点这种方法，我们的推荐系统能够提供一整条驾驶路线，并且出租车司机通过推荐能够找到获得最大潜在在收益的乘客。这就使得我们的推荐系统相对其它已有的推荐系统更加实用并且收益更多。最终，我们在一个现实世界的数据集上开展了实验，数据集来自San Francisco Bay地区，并且实验结果清楚地验证了我们提出的推荐系统的有效性。（作者话太多，用摘要代替一下，这不是关键）

2. 相关工作

    现在很多人在个性化推荐系统上做了大量工作，但是这些系统都是围绕一些传统的算法，基于内容的推荐，基于协同过滤的推荐，混合推荐等。都是一些根据网上的信息，给用户推荐电影、文章、书籍、或者网页之类的。大多数数据都是来自用户的评分，来自手机系统的很少。

    在手机上的个性化推荐系统比其它传统领域更加具有挑战，主要因为：空间数据的复杂性、时空数据内在的关系、不明确的情景感知角色、增长的环境感知能力的可用性。确实，手机环境下的推荐系统以前已经做过研究[1, 3, 5, 6, 12, 19, 20]。比如说，[1,5]手机路线导航。对手机用户提出了个性化情景推荐框架。[30]提出了一些技术机遇，与手机推荐系统[20]相关。Aver-janova等人开发了一个基于地图的手机推荐系统，可以提供一些个性化推荐给用户。然而，以上工作大多数都是根据用户的评分和互动，相应的推荐系统也是为智能设备比如说智能手机开发。确实，为出租车行业构建手机推荐系统的问题仍然是大有空间的。

    近来，丰富的出租车GPS轨迹使得出做租车领域有新方法。大量精力投入到了使用出租车轨迹数据做手机推荐系统。这些系统能够从历史的轨迹数据中提取出energy-ecient的交通模式，并且为出租车司机推荐潜在的载客点。这类系统能个提供一系列最佳的载客点。Powell等人[16]提出了一个基于网格的方法来为出租车司机建议盈利的地点，通过建立一个时空的盈利地图。此外，Yuan等人[24,25,26]对移动智慧展开了一系列的研究，通过夸大公交轨迹，比如说基于概率模型来进行载客点侦测，并且为出租车司机和乘客两者都提供位置推荐。本文不同于以上的研究，我们提议开发一种新奇的推荐系统，能够提供一整条驾驶路线，而不是离散的载客点，司机通过这种推荐就能够发现最大的潜在利润。

3. 问题陈述

    这章，我们首先介绍一下定义一些预备知识，然后为出租车司机正式定义最大净利润Maximum Net Pro t(MNP)的问题。

3.1 预备知识

3.1.1  路网的定义（Road Network Formulation）

定义1（路段）。一个长的街道通过交叉口可以被划分成若干个路段r，特别地，每一个路段r都是有一个起点r.s和一个重点r.e组成。此外，每一个路段r有很多的相邻的线段组成了一个集合r.next[]，表示的含义是如果 ri.s=r.e ，ri就属于r.next[]。

    定义2（路径）。一个路径R是一系列的连接的路段组成，例如，同时，R的起点和终点可以表示成 R.s=r1.s 以及 R.e=rn.e。

    定义3（路网）。一个路网G可以表示成一个图G=<V,E>，V={ri}表示节点的集合（包含了所有的路段），E表示边的集合，满足

    图1展示了一个路网。从图中看出，每一个节点表示一个路段。注意，每一条边只有一个方向。这是因为我们不允许出租车掉头再在同一个路段往回走，这在显示生活中不推荐，因为有很大的可能性会造成交通事故。然而，司机可以可以通过3个路段绕一圈，比如说r1，r2，r7。

    3.1.2 净利润的计算 （Calculation of Net Profit）

    对于每个路段r，净利润g(r)由两个部分组成，也就是可能的利润（potential earning） 以及可能的花费（potential cost）。特别地，我们定义了路段r可能的利润为e(r)，通过以下方式来计算：

    （我对这个公式的理解就是这个路段的平均一个客人的花费*概率，也就是说利润的数学期望）

    在这里，Nr表示的是在路段r特定的时间段里的载客量，Fee(i; r)是是指在路段r从第i个乘客身上的利润，P(r)指的是在路段r载到客的可能性（这个会在第四节介绍）。另一方面，在路段r可能的花费可以通过以下方式来计算：

    在这里，L(r)指的是路段r的长度，Gas指的是单位距离里面（比如说每英里）耗油的价格，T(r)指的是通过路段r所需要的时间，公司的花费（CompanyFee）指的是单位时间（比如说1分钟）工作花费。事实上，T(r)是和实时的交通状况息息相关的。比如说，交通阻塞会导致较高的T(r)，因此会带来较高的花费（T(r)*CompanyFee）。在这样的情况下，这个路段不会被我们的模型所推荐。因此，路段r的净利润，比如说叫做g(r)，可以表示为：

    通过以上的定义，我们可以进一步定义每一个路径R的净利润。特别地，当给定一个路径从r1出发，它的总的净利润可以通过以下方式来计算：

    凭直觉，路径R的净利润是R所包含的的路段{ri}的净利润之和，这是在之前的路段（比如说r1到ri-1）没有载到任何乘客的前提下衡量的。

    实际上，在净利润的的概率上，司机不会考虑到远离他当前所在位置的路段，因为利润的期望是十分低的。更具体的说来，当增加一个路段到路径中时，我们可以定义净利润的平均增长率来表示净利润的增长。图2展现了对于增加不同数量的路段以及不同载客概率时，净利润的增长率的趋势。我们可以观察出在增加5条线段以后，增长率就低于了10%。

    事实上，在我们的实验中，每个路段平均载客的概率通常是低于0.1的，因此，可能要设置一个上界对于公式4中的路径长度M。通过以上的定义，我们可以正式地给MNP推荐问题做出如下定义。

（此处应该有3.2，3.2 问题陈述 )

  定义4（问题陈述）。给定一个司机当前的位置LCab属于r，一个具体的驾驶距离M，并且有一系列的候选路径，对于任意R属于，满足R从r开始。MNP推荐问题就是推荐一个路径R*属于，这个路径拥有最大的净利率，例如：

    不同于已有的其它出租车司机推荐系统，它们主要关注于提取出耗时和收益比高（energy-efficient）的交通模式——基于时间/距离，并且为出租车司机推荐一系列的可能的载客点[25, 26, 8]，MNP推荐问题集中于为出租车司机提供一整条驾驶路径。按照这个路线（思路），解决MNP推荐问题有两个主要的挑战。第一点，如何从历史载客数据中计算线段r的参数g(r)，P(r) 。第二点，如何从复杂的有向环路的路网中有效的搜索出一个最佳路径。在接下来的一节，我们将介绍我们的解决方案对应这两个挑战。

    （我认为这篇论文的作者标号也太差了吧，3，3.1，3.1.1，3.1.2，否则直接3.1，3.2不就完事了？）

4. 最大净利润（MAXIMUM.NET PROFIT (MNP)）推荐

在这一小节，我们将介绍MNP推荐问题解决方法的技术细节。

4.1 估计参数，通过road buff er

为了精确的获得出租车司机当前的位置和估计净利润的参数，比如说P(r)和g(r)，我们为每个路段开发了road buff er 评估。特别地，在地理信息系统中，一个buffer是指在空间对象附近有特定距离一个区域。buffer的边界是离这个对象等距离的实线solid line（此处应该是论文的作者有点笔误，应该是虚线dashed line）。图3(a)解释了不同的buffer操作，比如说一个点，三线段以及一个三角形的buffers[21]。从直观来看，人们愿意等待在路边的出租车，而不是路中央的，并且出租车的载客点通常在路边。因此，当计算历史载客事件的数目时，我们需要在每个路段周围构建一个buffer，通常就像一个矩形包围了这条道路。特别地，buffer的大小取决于现实世界中不同问题额需求。

    为了建立road buff er ，首先，我们需要定义垂直的道路和水平的道路。更具体的来说，通过使用每个路段的起点和终点的经度(longitude)和纬度(latitude)，我们可以计算出这个路段正切（tangent）值。如果这个正切值比1大，我们认为这个对应的道路是一个垂直的道路，否则，它就是一个水平的道路。对于每一个垂直的道路，我们保持它的起点的经度和终点的经度不便，并且向西和向东拓展对应的纬度。对于一个水平的道路，我们保持它起点和终点的纬度不变，并且将它的经度向北和南拓展。例如，图3(b)展示了对垂直的道路和水平的道路的buffer操作。

    给定历史载客数据以及road buff ers ，我们就能够计算在每一个路段r载客事件的数目，这解释了当出租车经过每个路段时，发生一个载客事件有多么频繁。让 表示在路段r的buffer区出租车空闲的次数，让表示在路段r的buffer区出租车有载客事件的次数。因此，对于每个路段r，载客时间的概率P(r)可以估算如下：

    在路段r中的第i次历史载客事件，我们也能够得到公式1中的收益Fee(i; r)。此外，路径的距离L(r)和实时的驾驶时间T(r)可以从历史数据中估算得出或者借助一些额外资源，比如说谷歌地图。因此，净利润g(r)可以通过公式3得出。特别地，每个路段T(r),g(r)和P(r)的值可以预先存储在对应的路网（例如，图1）的节点上。

4.2 MNP 路径推荐

    在这一小部分中，我们介绍如何通过不同策略解决MNP推荐的问题。

4.2.1 暴力推荐策略

在获得路网之后，我们可以利用它来生成候选路径用于MNP推荐。在最后，我们首先提出一个暴力策略来完成了这个任务，基于广度优先搜索的算法。特别地，推荐的算法如算法1所示。在这个算法中，我们保持一个路径队列Q，为了生成一个候选路径集合C，然后第五步函数MNP(C)被用来在候选集合C寻找最佳路径，也就是最大利润的。然而，这个搜索MNP路径的暴力方法并没有什么软用，因为它检查了所有在G中长度为M的所有可能的路径。

    引理 1. 给定一个固定的驾驶长度M以及路网G={V,E}，满足|V|=N，通过暴力算法需找一个最佳的MNP路径的计算复杂度是

    证明：显然，总共候选路径在路网中的数目是的，并且计算每个路径净利润需要M次操作。因此，搜索最佳MNP路径的复杂度是。

    直观感受到，这个暴力算法的计算复杂度太高了以至于不能满足现实世界应用的需求。有一些算法可以节省到达时间——现实世界中的高速公路。在最后，我们会进一步提出另一个推荐策略，基于净利润函数的递归特性。

4.2.2 递归推荐策略

通过观察路径的净利润的表达形式，我们可以把公式4重写为如下形式：

    同时。实际上，总的净利润这种特殊的形式可以通过递归算法来实现。在最后，对于每个路段r1，我们可以把所有候选路径从r1开始的作为一个递归树结构。特别地，每个路段的递归树被定义成了以下形式。

    定义5 （递归树）。路段r1的递归树是一棵树，它的每一个节点表示的是路段同时树根是r1。此外，对于在递归树中的每一个节点ri，它的孩子的节点集合等于ri.next[]。

    例如，图4展示了路段A的递归树的一个样例。在这篇文章中，我们提出了一个方法RTree(r,M)位的是为r构建一个深度为M的递归树，这在算法2中有所体现。特别地，通过我们的算法获得的这颗树将保留M个节点的 ，这代表了在树中第i层的的节点。通过这个结构，从r1开始的MNP推荐可以递归地被划分成若干个更简单的MNP推荐任务。拿图4作为一个样例，我们可以开发一个由底向上的方法来计算长度为3的MNP路径，它的净利润可以表示成G(A,3)。特别地，根据净利润的定义，我们可以获得G(A,3)=g(A)+(1-P(A))*max{G(B; 2);G(C; 2);G(F; 2);G(E; 2)}，在这里长度为2的MNP路径的净利润同样可以通过它们的子路径计算净利润。例如，我们图中有G(B; 2) = g(B)+(1-P(B))*{maxfG(D; 1);G(I; 1)}，并且每一个个体的路段（例如叶子节点）的利润可以直接计算，例如g(D)。因此，给定一个递归树r，我们可以获得一个路径长度为M的MNP路径通过递归M-1次。

    特别地，在这篇文章中，我们为MNP推荐开发了一个递归算法rNMP(r;K)，如算法3所示。通过我们的算法，令参数r = r1同时K = M，那么长度为M的MNP路径从路段r1开始的相应的MNP值就可以得到。

    引理 2. 假定一个深度为M的递归树，对于任意r属于，|r.next[]|<=N，通过递归方法寻找一个最佳的MNP路径的复杂度是。

    证明：假设寻找G(R,r1,M)的计算花费是T(M)，很显然我们会得到。此外，对于任意的r满足|r.next[]|=N，计算可以被划分成N个子问题。特别地，对于路径只有一个路段的，我们得到T(1)=1。同时，在递归M-1次后，我们得到。因此，通过递归树寻找最佳MNP路径的计算复杂度是。

    尽管递归树比暴力算法可以取得更有效的推荐，但是计算花费会随着M的增大而急剧上升。根据第3节的讨论，我们可以设置一个M的上界，因为在M>5之后平均利润增长力会变得十分低。因此，我们在我们的实验中设置=5。

4.3 Top-K 路径推荐

    通过以上算法，我们的推荐系统可以为单个司机推荐了一条MNP路径。但是，在实际生活中，一个理想的推荐系统必须能够同时地为同一个区域里面的多个出租车司机提供推荐。在这节，我们着重于这个问题并且为这种现实世界里的推荐处理介绍一种最小冗余策略。

    从直觉感受到，一个直接的推荐策略是为所有的司机推荐最佳的驾驶路径。然而，如果我们同时为太多的司机推荐同一条路径，这会导致一个过载问题并且会降低推荐系统的表现。过载问题是一个经典的问题，已经被广泛的研究。例如，负载平衡机制在多个web服务器之间分发请求，为的是减少执行时间[22,10]。在我们的问题中，我们可以把多个空的出租车看成是任务，多个最佳的驾驶路径看作是计算机。不是通过探索已有的负载均衡的算法来解决过载问题，而是我们想要集中于手机推荐系统的偏转特性并且开发了一个基于方向的聚类方法(DEN)[29]来分配空车，遵循top-K最佳驾驶路径[9,23]。

    在推荐驾驶路线给出租车司机之前，我们首先标记所有的候选路径根据它们的净利润并且获得top-K驾驶路线。在推荐给第一个司机排名靠前的路径后，我们需要计算这条路径和剩下的K-1条候选路径之间的相关性，并且随后把相关性最低的路径推荐给第二个司机。

    为了计算这些候选路径之间的相关性，我们首先把空间划分成格子并且把每个格子的移动数据转变成一个向量，它代表了在这个格子移动方向的概率。然后，我们把出租车移动的方向信息转变成同样的数据格式，并且进一步把每个小格子划分成8个方向的bin。例如，在图5(a)中，每个bin的角度拥有的范围。下一步，我们把每个格子划分成一个方向的向量g=(p1,p2,p3,......,p8)，在这里pi指的是这个格子往i方向移动的概率，并且，在这里fi是指穿过这个格子并且方向是沿着方向i的移动物体的频率。

    举个例子，如图5(b)所示，我们首先把路径A推荐给第一个司机，路径B,C和D是其它的候选路径在相同的时间和相同的地点。然后我们把空间划分成了小格子并且获得了每个格子的向量。一条与之前推荐的路径相关性最低的候选路径通常是一开始的驾驶方向就不同的。因此，我们只需要分析前n个格子来决定驾驶方向。我们把n个格子的向量结合起来并且对于每条候选路径得到了一个8*n个元素的向量。例如，路径A的向量g(A) = (p11,p12,......pn7,pn8)。然后，我们为每对候选路径的向量计算相关性。因此，A和B的相似度可以被计算成。如果路径B和路径A之间的相关性最低，我们将把B推荐给下一个空车。

5. 实验结果

去验证提出的系统的效率和有效性，在现实世界旧金山区域收集了30天的数据集，并在上面做到了广泛的试验。

5.1 实验数据

原标题：A cost