基于区域划分的出租车统一推荐算法(2)

　　算法在前期会对历史GPS数据进行处理，获取旅程路线信息和区域时间信息。针对用户的特定请求，算法主要进行了三步处理：获取实时出租车信息；针对各个实时出租车，判定可能目的地，计算出租车对应的绕远时间比例；最后推荐绕远时间比例最小的出租车为用户提供拼车服务。
　　2.2前期准备
　　2.2.1旅程信息
　　推荐算法根据海量的GPS数据，持续跟踪每辆出租车可以得到所有每次旅程的起点、终点以及中间地点。通过这样的方式，推荐算法首先从海量的GPS数据中取得了出租车所有的旅程信息，之后根据已经得知的出租车起点（作为旅程的起点）、用户起点（作为中间经过地点）可以推测出可能的目的地。如图3所示，可能目的地D1有多种可能，使用虚线描述。
　　因此推荐算法需要先对原始GPS数据集进行处理，获得旅程信息，旅程信息的获得是这整个推荐算法的关键。
　　2.2.2区域与区域时间
　　如果采用GPS经纬度点对作为匹配旅程的标志，那么会造成几乎无法匹配到具有相同起点和中间地点的旅程，因为在同一个GPS经纬度点进行搭车的情况几乎没有。
　　为了将不可能化为可能，本文采用区域划分的方法，将区域作为旅程的标识，即将多个相近GPS经纬度点对转换为同一区域。在持续跟踪同一出租车GPS数据时，同一个区域内会包含此出租车多个GPS记录，最晚时间与最早时间的差可以作为此出租车通过这个区域的时间消耗[14]。
　　通过区域划分，推荐算法以多个区域编号标记一次搭载旅程，在旅程匹配方面化不可能为可能。划分区域后，整个旅程只在起点和终点区域存在很小的时间误差，更加接近现实情况。
　　2.3计算绕远时间比例
　　对于普通拼车服务，绕远时间比例为0。对于拼车服务，当接收到用户的拼车请求之后，推荐算法为了推荐一辆出租车给此特定乘客，会进行以下四步运算：
　　1）根据用户起点和时间，获取实时已有乘客出租车车牌号，根据时间反跟踪其GPS数据，获取其出发区域。
　　2）已知出租车起点区域，将新用户起点作为旅程中间区域，与旅程信息相比较，获得可能的出租车目的地。
　　3）对目的地进行筛选。平均分配每个目的地概率，计算该出租车对应的绕远时间比例。
　　4）比较所有实时出租车，推荐绕远时间比例最小的一辆出租车给乘客，完成一次请求任务。
　　对于用户来说，最好的推荐选项即为最有可能去往其目的地方向的出租车。假设对于某特定用户请求而言，可能目的地Db相比可能目的地Da拥有更小的绕远时间比例，此时有实时两辆出租车：出租车T1可能目的地有10个，8个为Da，2个为Db；出租车T2可能目的地也有10个，6个为Da，4个为Db。虽然两辆出租车均更有可能去往Da，但站在用户角度，只关心具有更小绕远时间比例的Db，所以相比T1，算法会推荐T2给乘客。
　　所以，本文对出租车可能目的地集合进行筛选的三种模式均站在用户角度，只关心相比其他实时出租车，推荐车辆是否具有最小的绕远时间比例，以具有更小的绕远时间比例作为筛选的依据。
　　图4是整个算法的操作流程；图5则针对“计算绕远时间比例”的三种不同模式，使用示意图展示其不同。下面对这三种模式进行详细的描述：
　　3数据处理
　　大数据处理工具有许多，例如Hadoop（主要包括MapReduce和Hadoop分布式文件系统（Hadoop Distributed File System， HDFS））、Spark和Storm。Storm适用于实时计算，而本文算法主要时间消耗为历史GPS数据的批量处理，Hadoop更加适合。Hadoop在外存处理数据，Spark在内存处理数据，Hadoop适合迭代处理，擅长批量处理；相对而言Spark更适合流处理，不擅长迭代处理。Spark处理速度确实比Hadoop快，但是对于服务器的内存有着较大需求，算法为了保证能够实时地推荐出租车给用户提供拼车服务，最终选择Hadoop，这样既可以减少历史GPS数据批量处理的时间消耗，也可以保证充分的内存空间应对实时用户请求的处理。
　　3.1前期准备
　　原始数据集合由成千上万条GPS数据集合获得。原始数据不能够直接被推荐算法使用，需要进行处理，以获取旅程信息和区域时间。在进行以下工作时，已经对原始数据进行数据清洗操作，并按照时间增序对数据进行排列，方便接下来的数据处理。
　　3.1.1旅程信息
　　从原始GPS数据中获取旅程信息，需要对单个出租车进行持续跟踪，并且需要对其状态进行监测，提取出连续状态值为1（即有乘客）的连续区域集合。
　　如图6、表1及表2所示，根据原始GPS数据集合，本文算法可获取到以区域标记的旅程信息，使用区域编号代替一个个GPS经纬度点对描述整个旅程，如图6所示，经过区域划分后，一次旅程变为：
　　通过这种持续跟踪与区域划分的思想，将原始GPS数据集合转化为用区域标记的旅程信息。
　　3.1.2区域与区域时间
　　由表3、表4可以看出某辆出租车进入区域Jd52Wd11的时间为0：01：36，驶出区域Jd52Wd11的时间为0：03：39，所以可以得知，这辆出租车经过区域Jd52Wd11所耗费时间为123s，依据同样的方法可以获得各个区域的时间。
　　需要格外注意的是，求区域时间时，无需考虑出租车状态，因为搭载乘客与否对于通过区域的时间不会产生影响；并且计算区域时间时，同一区域不同时间段的时间消耗是不一样的，所以本文采用时间段、区域两个变量来确定某区域在某个时间段的时间消耗，更加贴近现实情况。
　　3.2数据处理流程
　　3.2.1旅程信息
　　通过Map阶段获得起点区域为某特定区域（出租车起点）的旅程信息，Reduce阶段在Map的基础上获取中间区域包含某特定区域（用户起点）的旅程，并最终输出满足两个条件的旅程终点区域，这个终点区域即为出租车可能的目的地。