一种基于路径轨迹的目的地预测方法、系统及存储介质

摘要

本发明公开了一种基于路径轨迹的目的地预测方法、系统及存储介质，所述方法包括：根据预设转换规则对待预测订单中的路径数据进行数值转换处理，得到对应的路径轨迹表示数据；将所述对应的路径轨迹表示数据输入至局部敏感哈希模型，根据LSH算法计算得到对应的匹配结果；采用K‑Means算法对所述对应的匹配结果按照目的地个数进行聚类，根据相似度衡量公式计算每个聚类中的匹配结果的路径相似度，选取各个聚类中的最高相似度的路径作为多目的地预测结果。本发明能够通过哈希模型匹配近似路径集合，针对预测唯一目的地与筛选多目的地等不同问题采取不同的方法，提高基于路径轨迹的目的地预测能力，为用户或司机个人信息不可用的应用提供参考。

权利要求

1.一种基于路径轨迹的目的地预测方法，其特征在于，至少包括如下步骤：

根据预设转换规则对待预测订单中的路径数据进行数值转换处理，得到对应的路径轨迹表示数据；

将所述对应的路径轨迹表示数据输入至局部敏感哈希模型，根据LSH算法计算得到对应的匹配结果；

采用K-Means算法对所述对应的匹配结果按照目的地个数进行聚类，根据相似度衡量公式计算每个聚类中的匹配结果的路径相似度，选取各个聚类中的最高相似度的路径作为多目的地预测结果；

筛选在待预测订单的出发时间前后预设的时间范围内的样本订单；

对所述样本订单按照起点位置采用K-Means算法进行聚类，并记录对应的聚类中心；

根据待预测订单的起点位置找到最近的聚类中心，确定所属聚类；

对所述对应的匹配结果进行筛选，保留与所述待预测订单在同个聚类的样本订单；

根据相似度衡量公式计算匹配结果的路径相似度，选取同个聚类中的最高相似度的路径作为单个目的地预测结果。

2.根据权利要求1所述的基于路径轨迹的目的地预测方法，其特征在于，所述数值转换处理，具体为：根据经纬线将地图分为若干个网格，并按照经纬度的顺序对若干个网格进行标号；

将路径轨迹数据中的二维点序列进行数值转换，通过行扫面的方式，逐行读取后拼接转化成一维数组。

3.根据权利要求1所述的基于路径轨迹的目的地预测方法，其特征在于，所述预设转换规则，具体为：保留路径轨迹数据中的原始序列中的各坐标点出现的顺序；利用网格标号代替原始序列中的各坐标点；若网格中出现连续的坐标点，则只保留一个坐标点。

4.根据权利要求1所述的基于路径轨迹的目的地预测方法，其特征在于，所述局部敏感哈希模型，包括Offline阶段和Online阶段，其中，所述Offline阶段，具体为：通过设计的h个哈希函数对任意长度的样本轨迹进行MinHash转换，得到h维的向量；通过LSH算法将h维的数据平均划分为b个Band，其中每个Band中含有r个哈希函数的结果；对于每一个Band，将r个哈希值都相同的订单存入同一个Bucket，且该Bucket的索引值为对应的r个哈希值；存储LSH阶段的计算结果作为后续OffLine阶段待预测订单的匹配；

所述Online阶段，具体为：对于一个待预测订单，在Query过程中，遍历各个Band，按照订单轨迹在该Band中的哈希值找到对应的Bucket，将所有的Buckets存储的样本订单作为待预测订单在哈希模型中的匹配结果。

5.根据权利要求1所述的基于路径轨迹的目的地预测方法，其特征在于，所述相似度衡量公式，具体为SIM(S1,S2)＝COMm(S1,S2)/len(S1)

其中，S1为待预测订单的路径，S2为预测路径，COMm(S1,S2)为路径S2相对于路径S1的最大不连续公共长度，len(S1)为路径S1的长度。

6.一种基于路径轨迹的目的地预测系统，其特征在于，包括：

路径预处理模块，用于根据预设转换规则对待预测订单中的路径数据进行数值转换处理，得到对应的路径轨迹表示数据；

局部敏感哈希模型模块，用于将所述对应的路径轨迹表示数据输入至局部敏感哈希模型，根据LSH算法计算得到对应的匹配结果；

多目的地预测模块，用于采用K-Means算法对所述对应的匹配结果按照目的地个数进行聚类，根据相似度衡量公式计算每个聚类中的匹配结果的路径相似度，选取各个聚类中的最高相似度的路径作为多目的地预测结果；

样本筛选模块，用于在OffLine阶段和OnLine阶段，筛选在待预测订单的出发时间前后预设的时间范围内的样本订单；对所述对应的匹配结果进行筛选，保留与所述待预测订单在同个聚类的样本订单；

单目的地预测模块，用于对所述样本订单按照起点位置采用K-Means算法进行聚类，并记录对应的聚类中心；根据待预测订单的起点位置找到最近的聚类中心，确定所属聚类；根据相似度衡量公式计算匹配结果的路径相似度，选取同个聚类中的最高相似度的路径作为单个目的地预测结果。

7.根据权利要求6所述的基于路径轨迹的目的地预测系统，其特征在于，所述局部敏感哈希模型模块，包括Offline单元和Online单元，其中，所述Offline单元，用于通过设计的h个哈希函数对任意长度的样本轨迹进行MinHash转换，得到h维的向量；通过LSH算法将h维的数据平均划分为b个Band，其中每个Band中含有r个哈希函数的结果；对于每一个Band，将r个哈希值都相同的订单存入同一个Bucket，且该Bucket的索引值为对应的r个哈希值；存储LSH阶段的计算结果作为后续OffLine阶段待预测订单的匹配；

所述Online单元，用于对于待预测订单在Query过程中，遍历各个Band，按照订单轨迹在该Band中的哈希值找到对应的Bucket，将所有的Buckets存储的样本订单作为待预测订单在哈希模型中的匹配结果。

8.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质包括存储的计算机程序，其中，在所述计算机程序运行时控制所述计算机可读存储介质所在设备执行如权利要求1至5任一项所述的基于路径轨迹的目的地预测方法。

说明书

一种基于路径轨迹的目的地预测方法、系统及存储介质

技术领域

[0001] 本发明涉及智能交通信息处理技术领域，具体涉及一种基于路径轨迹的目的地预测方法、系统及存储介质。

背景技术

[0002] 随着GPS和4G网络的发展，现代移动设备，如智能手机，基本内置GPS接收器及导航系统，可以高精度地定位用户。这些设备产生了大量的位置数据，可用于各种各样基于位置的服务(Location-Based Services，简称“LBS”)，包括路线规划，路况实时反馈，饮食、购物或旅游胜地的推荐，基于位置的社交网络分析等。LBS的应用极大地方便了人们的日常生活，其中最受欢迎的应用之一便是各种打车软件。这些软件平台每天采集大量的订单及轨迹信息，收集到的数据为我们提供了前所未有的挖掘司机及用户行为特征的机会，可在不同应用中构建实时智能决策系统，如订单调度、出租车需求预测和路线规划等。

[0003] 在日常生活中，随着基于位置信息的应用需求日益增加，也展开了越来越多关于通过司机行程轨迹预测当前路径目的地的研究。用户目的地预测在广告投放的用途显而易见。当用户乘坐出租车时，LBS提供商可以从他们的手机或出租车的GPS设备收集位置信息，预测最可能的目的地并向用户推荐目的地附近的餐馆或商场的广告，若用户被判断为旅客则可以尝试推荐观光地点。目的地预测还可以用于辅助路线判断、人群异常检测等。另外，在导航系统中，对人的目的地的预测可以帮助确定该人是否偏离预期的路线。作为潜在的应用，通过预测某个时间段多数人去的地方，管理员可以判断这些地点的人群规模，并采取相应的预防措施；甚至一些极端情况下，当获取到某一段路径时，某些政府机关的侦查人员可对嫌疑人的目的地进行预判并提前安排好应对措施。

[0004] 由于目的地预测问题在上述应用中的重要性，已经对其进行了广泛的研究，其中一个方向便是基于轨迹数据的目的地预测。大多数现有方法基于各种(隐式)马尔可夫链模型。一种典型的方法是将区域均匀地划分为网格单元或将道路划分为段，并使用单元或分段作为马尔可夫过程的状态，历史轨迹用于训练马尔可夫链的状态转移概率矩阵。然而，采用(一阶)马尔可夫链模型，隐含着车辆以无记忆随机驾驶方式行驶的假设，这显然与我们的实际经验相矛盾，即真实的轨迹不是完全随机的。

[0005] 并且，在对现有技术的研究与实践过程中，本发明的发明人发现，在目的地预测问题中，很多时候我们需要的并不只有一个值，在诸如广告投放的应用中，我们可能需要得到多个不同的目的地。现有的方法大多使用概率推理来计算各目的地的概率并返回概率最高的前k个值。当预测正在进行的行程的目的地时，依次计算到达某些地方的条件概率，并且返回最高的前k个值对应的位置(即前k个最可能的地方)作为预测结果。显然，这种方法没有对概率计算结果采取进一步的处理。各个目的地的预测概率可能很小，并且彼此接近，此时返回的前k个概率最高的结果可能在地理位置上彼此非常接近。这种情况下，由于忽略了其他一些在地理上与这k个位置不太接近但具有相似概率的地点，得到的这k个结果不利于我们实际生活中的应用。

发明内容

[0006] 本发明实施例所要解决的技术问题在于，提供一种基于路径轨迹的目的地预测方法、系统及存储介质，能够针对预测唯一目的地和筛选多目的地采取不同预测方式，提高预测的精准性。

[0007] 为解决上述问题，本发明的一个实施例提供一种基于路径轨迹的目的地预测方法，至少包括如下步骤：

[0008] 根据预设转换规则对待预测订单中的路径数据进行数值转换处理，得到对应的路径轨迹表示数据；

[0009] 将所述对应的路径轨迹表示数据输入至局部敏感哈希模型，根据LSH算法计算得到对应的匹配结果；

[0010] 采用K-Means算法对所述对应的匹配结果按照目的地个数进行聚类，根据相似度衡量公式计算每个聚类中的匹配结果的路径相似度，选取各个聚类中的最高相似度的路径作为多目的地预测结果。

[0011] 进一步地，所述基于路径轨迹的目的地预测方法，还包括：

[0012] 筛选在待预测订单的出发时间前后预设的时间范围内的样本订单；

[0013] 对所述样本订单按照起点位置采用K-Means算法进行聚类，并记录对应的聚类中心；

[0014] 根据待预测订单的起点位置找到最近的聚类中心，确定所属聚类；

[0015] 对所述对应的匹配结果进行筛选，保留与所述待预测订单在同个聚类的样本订单；

[0016] 根据相似度衡量公式计算匹配结果的路径相似度，选取同个聚类中的最高相似度的路径作为单个目的地预测结果。

[0017] 进一步地，所述数值转换处理，具体为：

[0018] 根据经纬线将地图分为若干个网格，并按照经纬度的顺序对若干个网格进行标号；

[0019] 将路径轨迹数据中的二维点序列进行数值转换，通过行扫面的方式，逐行读取后拼接转化成一维数组。

[0020] 进一步地，所述预设转换规则，具体为：保留路径轨迹数据中的原始序列中的各坐标点出现的顺序；利用网格标号代替原始序列中的各坐标点；若网格中出现连续的坐标点，则只保留一个坐标点。

[0021] 进一步地，所述局部敏感哈希模型，包括Offline阶段和Online阶段，其中，所述Offline阶段，具体为：通过设计的h个哈希函数对任意长度的样本轨迹进行MinHash转换，得到h维的向量；通过LSH算法将h维的数据平均划分为b个Band，其中每个Band中含有r个哈希函数的结果；对于每一个Band，将r个哈希值都相同的订单存入同一个Bucket，且该Bucket的索引值为对应的r个哈希值；存储LSH阶段的计算结果作为后续OffLine阶段待预测订单的匹配；

[0022] 所述Online阶段，具体为：对于一个待预测订单，在Query过程中，遍历各个Band，按照订单轨迹在该Band中的哈希值找到对应的Bucket，将所有的Buckets存储的样本订单作为为待预测订单在哈希模型中的匹配结果。

[0023] 进一步地，所述相似度衡量公式，具体为SIM(S1,S2)＝COMm(S1,S2)/len(S1)[0024] 其中，S1为待预测订单的路径，S2为预测路径，COMm(S1,S2)为路径S2相对于路径S1的最大不连续公共长度，len(S1)为路径S1的长度。

[0025] 本发明的一个实施例提供了一种基于路径轨迹的目的地预测系统，包括：

[0026] 路径预处理模块，用于根据预设转换规则对待预测订单中的路径数据进行数值转换处理，得到对应的路径轨迹表示数据；

[0027] 局部敏感哈希模型模块，用于将所述对应的路径轨迹表示数据输入至局部敏感哈希模型，根据LSH算法计算得到对应的匹配结果；

[0028] 多目的地预测模块，用于采用K-Means算法对所述对应的匹配结果按照目的地个数进行聚类，根据相似度衡量公式计算每个聚类中的匹配结果的路径相似度，选取各个聚类中的最高相似度的路径作为多目的地预测结果。

[0029] 进一步地，所述基于路径轨迹的目的地预测系统，还包括：

[0030] 样本筛选模块，用于在OffLine阶段和OnLine阶段，筛选在待预测订单的出发时间前后预设的时间范围内的样本订单；对所述对应的匹配结果进行筛选，保留与所述待预测订单在同个聚类的样本订单；

[0031] 单目的地预测模块，用于对所述样本订单按照起点位置采用K-Means算法进行聚类，并记录对应的聚类中心；根据待预测订单的起点位置找到最近的聚类中心，确定所属聚类；根据相似度衡量公式计算匹配结果的路径相似度，选取同个聚类中的最高相似度的路径作为单个目的地预测结果。

[0032] 进一步地，所述局部敏感哈希模型模块，包括Offline单元和Online单元，其中，[0033] 所述Offline单元，用于通过设计的h个哈希函数对任意长度的样本轨迹进行MinHash转换，得到h维的向量；通过LSH算法将h维的数据平均划分为b个Band，其中每个Band中含有r个哈希函数的结果；对于每一个Band，将r个哈希值都相同的订单存入同一个Bucket，且该Bucket的索引值为对应的r个哈希值；存储LSH阶段的计算结果作为后续OffLine阶段待预测订单的匹配；

[0034] 所述Online单元，用于对于待预测订单在Query过程中，遍历各个Band，按照订单轨迹在该Band中的哈希值找到对应的Bucket，将所有的Buckets存储的样本订单作为为待预测订单在哈希模型中的匹配结果。

[0035] 本发明的一个实施例还提供了一种计算机可读存储介质，所述计算机可读存储介质包括存储的计算机程序，其中，在所述计算机程序运行时控制所述计算机可读存储介质所在设备执行如上述的基于路径轨迹的目的地预测方法。

[0036] 实施本发明实施例，具有如下有益效果：

[0037] 本发明实施例提供的一种基于路径轨迹的目的地预测方法、系统及存储介质，所述方法包括：根据预设转换规则对待预测订单中的路径数据进行数值转换处理，得到对应的路径轨迹表示数据；将所述对应的路径轨迹表示数据输入至局部敏感哈希模型，根据LSH算法计算得到对应的匹配结果；采用K-Means算法对所述对应的匹配结果按照目的地个数进行聚类，根据相似度衡量公式计算每个聚类中的匹配结果的路径相似度，选取各个聚类中的最高相似度的路径作为多目的地预测结果。本发明能够通过基于最小哈希的局部敏感哈希算法对轨迹进行降维处理和匹配近似路径集合，针对预测唯一目的地与筛选多目的地等不同问题采取不同的方法，设计多参数评价不同方法的效果验证，提高基于路径轨迹的目的地预测能力，而不含有任何的个人属性特征信息，为用户或司机个人信息不可用的应用提供参考。

附图说明

[0038] 图1为本发明实施例提供的一种基于路径轨迹的目的地预测方法的流程示意图；

[0039] 图2为本发明实施例提供的一种基于路径轨迹的目的地预测系统的结构示意图。

具体实施方式

[0040] 下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

[0041] 首先介绍本发明可以提供的应用场景，如基于路径轨迹数据的进行目的地预测。

[0042] 本发明第一实施例：

[0043] 请参阅图1。

[0044] 如图1所示，本实施例提供的一种基于路径轨迹的目的地预测方法，至少包括如下步骤：

[0045] S101、根据预设转换规则对待预测订单中的路径数据进行数值转换处理，得到对应的路径轨迹表示数据；

[0046] 具体的，对于步骤S101，对于一条采用WGS-84坐标表示的路径轨迹，所有轨迹点都是二维的。为了将路径轨迹输入至哈希模型，要将二维的点序列转化为一维的数组，即通过行扫面的方式，一行一行读取拼接转化成一维数组。规定了路径表示方式后，也就确定了模型的输入格式，即一维数组。

[0047] S102、将所述对应的路径轨迹表示数据输入至局部敏感哈希模型，根据LSH算法计算得到对应的匹配结果；

[0048] 具体的，对于步骤S102，整个模型可以分为提前训练数据的OffLine阶段以及对于待预测订单的OnLine阶段。哈希模型的流程在OffLine阶段及OnLine阶段均起作用。在OffLine阶段，所有的样本订单在哈希模型被划分到桶中，这一过程称为“LSH过程”；在OnLine阶段，对于一个待预测订单，根据其经过哈希模型落在的桶得到路径高概率相似的样本订单，这一过程称为“Query过程”。这些订单往往有多个，但相比于所有的样本订单而言只是极小的一部分。

[0049] S103、采用K-Means算法对所述对应的匹配结果按照目的地个数进行聚类，根据相似度衡量公式计算每个聚类中的匹配结果的路径相似度，选取各个聚类中的最高相似度的路径作为多目的地预测结果。

[0050] 具体的，对于步骤S103，针对多个目的地预测问题，在挑选出高相似度的路径同时希望这些订单的终点相距较远，因此设计了新的衡量方式，采用K-Means对哈希子模型的匹配结果(样本订单集)按照目的地的个数进行聚类，并取各聚类中相似度最高的路径作为结果。

[0051] 在优选的实施例中，所述基于路径轨迹的目的地预测方法，还包括：

[0052] 筛选在待预测订单的出发时间前后预设的时间范围内的样本订单；

[0053] 对所述样本订单按照起点位置采用K-Means算法进行聚类，并记录对应的聚类中心；

[0054] 根据待预测订单的起点位置找到最近的聚类中心，确定所属聚类；

[0055] 对所述对应的匹配结果进行筛选，保留与所述待预测订单在同个聚类的样本订单；

[0056] 根据相似度衡量公式计算匹配结果的路径相似度，选取同个聚类中的最高相似度的路径作为单个目的地预测结果。

[0057] 具体的，针对单个目的地预测问题，着重研究预测的目的地与实际目的地的偏差。通过加入时间或地理距离远近的因素，对哈希模型的Query结果作进一步的筛选，接着使用改进的相似度衡量方式，从样本的筛选上降低预测的误差。在OffLine阶段为各个样本订单标上辅助筛选的类标签，OnLine阶段针对待预测样本完成筛选的过程以及相似度的比较。

[0058] 需要说明的是，筛选目的地实质上是一系列条件的设置，因而形式多变，针对不同的问题，有不同的方法或手段。在OffLine阶段及OnLine阶段均可能起作用，筛选条件则主要考虑时间属性的影响以及预聚类的效果。

[0059] 在优选的实施例中，所述数值转换处理，具体为：

[0060] 根据经纬线将地图分为若干个网格，并按照经纬度的顺序对若干个网格进行标号；

[0061] 将路径轨迹数据中的二维点序列进行数值转换，通过行扫面的方式，逐行读取后拼接转化成一维数组。

[0062] 在优选的实施例中，所述预设转换规则，具体为：保留路径轨迹数据中的原始序列中的各坐标点出现的顺序；利用网格标号代替原始序列中的各坐标点；若网格中出现连续的坐标点，则只保留一个坐标点。

[0063] 具体的，假定地球上的经纬线按照一定的度数将地球划分为一个个网格，人为的按照经纬度的顺序进行标号。对于一路径S＝{a,b,c,d,e,f,g,h,i,j,k}，这里通过网格的标号按照预设规则对路径进行数值转换，转换成一个一维数组；所述预设规则包括：保留原始序列各点出现的顺序；用网格标号代替各(坐标)点；若出现连续的点在网格中的情况，即存在连续多个重复的值，则只保留一个值。

[0064] 在优选的实施例中，所述局部敏感哈希模型，包括Offline阶段和Online阶段，其中，

[0065] 所述Offline阶段，具体为：通过设计的h个哈希函数对任意长度的样本轨迹进行MinHash转换，得到h维的向量；通过LSH算法将h维的数据平均划分为b个Band，其中每个Band中含有r个哈希函数的结果；对于每一个Band，将r个哈希值都相同的订单存入同一个Bucket，且该Bucket的索引值为对应的r个哈希值；存储LSH阶段的计算结果作为后续OffLine阶段待预测订单的匹配；

[0066] 所述Online阶段，具体为：对于一个待预测订单，在Query过程中，遍历各个Band，按照订单轨迹在该Band中的哈希值找到对应的Bucket，将所有的Buckets存储的样本订单作为为待预测订单在哈希模型中的匹配结果。

[0067] 具体的，局部敏感哈希模型分成Offline阶段和Online阶段。

[0068] 其中，在Offline阶段时，对于任意长度的样本轨迹，都通过设计的h个哈希函数(MinHash过程)，转化为h维的向量。接着，通过LSH算法，将h维的数据平均划分为b个Bands，每个Band中含有r个哈希函数的结果，此处满足h＝b*r。对于每一个Band，将r个哈希值都相同的订单存入同一个Bucket，且该Bucket的索引值为对应的r个哈希值。将“LSH阶段”的结果存储起来，以进行后续OffLine阶段待预测订单的匹配。

[0069] 在Online阶段时，局部敏感哈希模型对于一个待预测订单，在“Query过程”中，遍历各个Band，按照订单轨迹在该Band中的哈希值找到对应的Bucket，注意，每个Band中最多只会对应一个Bucket。最后，所有的这些Buckets存储的样本订单，即为待预测订单在哈希子模型中的匹配结果。需要注意的是，在本发明实施例中，本技术的LSH模型参数采用了50％的相似度阈值和256个哈希函数。

[0070] 在优选的实施例中，所述相似度衡量公式，具体为SIM(S1,S2)＝COMm(S1,S2)/len(S1)

[0071] 其中，S1为待预测订单的路径，S2为预测路径，COMm(S1,S2)为路径S2相对于路径S1的最大不连续公共长度，len(S1)为路径S1的长度。

[0072] 具体的，在本实施例中采取了两种计算相似度的方式：

[0073] (1)Jaccard相似度，这是在MinHash及LSH中筛选相似路径时使用的相似度。但这种计算方式有两个明显的不足。第一，计算相似度的时候会将两个路径的长度都计算在内，即使用了降维后的两条路径所含有的全部元素；第二，由于哈希的过程将原路径的时序打乱了，不利于目的地的准确预测。针对第二个问题，有两种解决方法：一是通过对起始点聚类进行路径筛选；二是自定义一种考虑时序的衡量标准，这种衡量标准同样克服了第一个问题。

[0074] (2)最长不连续相似度SIMm计算方式，如果将路径看做是字符串，我们可以将任务转化为求解两个字符串的最大不连续公共长度，常用动态规划求解。记路径S2相对于S1最大不连续公共长度为COMm(S1,S2)。由于我们需要寻找的是路径S1的相似路径，而Jaccard相似度在计算的时候会匹配双方的长度都考虑在内，如果路径S1较小而匹配的路径较长，则会被较长的路径所影响。为了提高合理性，既考虑路径顺序的问题，同时强调其他路径相对于路径S1的相似程度，对相似度计算进行了修改，改进后的相似度衡量公式为：

[0075] SIM(S1,S2)＝COMm(S1,S2)/len(S1)

[0076] 其中，len(S1)为路径S1的长度。

[0077] 本实施例提供的一种基于路径轨迹的目的地预测方法，包括：根据预设转换规则对待预测订单中的路径数据进行数值转换处理，得到对应的路径轨迹表示数据；将所述对应的路径轨迹表示数据输入至局部敏感哈希模型，根据LSH算法计算得到对应的匹配结果；采用K-Means算法对所述对应的匹配结果按照目的地个数进行聚类，根据相似度衡量公式计算每个聚类中的匹配结果的路径相似度，选取各个聚类中的最高相似度的路径作为多目的地预测结果。本发明能够通过基于最小哈希的局部敏感哈希算法对轨迹进行降维处理和匹配近似路径集合，针对预测唯一目的地与筛选多目的地等不同问题采取不同的方法，设计多参数评价不同方法的效果验证，提高基于路径轨迹的目的地预测能力，而不含有任何的个人属性特征信息，为用户或司机个人信息不可用的应用提供参考。

[0078] 本发明第二实施例

[0079] 请参阅图2。

[0080] 如图2所示，本发明的一个实施例还提供了一种基于路径轨迹的目的地预测系统，包括：

[0081] 路径预处理模块100，用于根据预设转换规则对待预测订单中的路径数据进行数值转换处理，得到对应的路径轨迹表示数据；

[0082] 具体的，对于路径预处理模块100，对于一条采用WGS-84坐标表示的路径轨迹，所有轨迹点都是二维的。为了将路径轨迹输入至哈希模型，要将二维的点序列转化为一维的数组，即通过行扫面的方式，一行一行读取拼接转化成一维数组。规定了路径表示方式后，也就确定了模型的输入格式，即一维数组。

[0083] 局部敏感哈希模型模块200，用于将所述对应的路径轨迹表示数据输入至局部敏感哈希模型，根据LSH算法计算得到对应的匹配结果；

[0084] 具体的，对于局部敏感哈希模型模块200，整个模型可以分为提前训练数据的OffLine阶段以及对于待预测订单的OnLine阶段。哈希模型的流程在OffLine阶段及OnLine阶段均起作用。在OffLine阶段，所有的样本订单在哈希模型被划分到桶中，这一过程称为“LSH过程”；在OnLine阶段，对于一个待预测订单，根据其经过哈希模型落在的桶得到路径高概率相似的样本订单，这一过程称为“Query过程”。这些订单往往有多个，但相比于所有的样本订单而言只是极小的一部分。

[0085] 多目的地预测模块300，用于采用K-Means算法对所述对应的匹配结果按照目的地个数进行聚类，根据相似度衡量公式计算每个聚类中的匹配结果的路径相似度，选取各个聚类中的最高相似度的路径作为多目的地预测结果。

[0086] 具体的，对于多目的地预测模块300，针对多个目的地预测问题，在挑选出高相似度的路径同时希望这些订单的终点相距较远，因此设计了新的衡量方式，采用K-Means对哈希子模型的匹配结果(样本订单集)按照目的地的个数进行聚类，并取各聚类中相似度最高的路径作为结果。

[0087] 对于相似度计算，本实施例中采用了两种计算相似度方式，包括：

[0088] (1)Jaccard相似度，这是在MinHash及LSH中筛选相似路径时使用的相似度。但这种计算方式有两个明显的不足。第一，计算相似度的时候会将两个路径的长度都计算在内，即使用了降维后的两条路径所含有的全部元素；第二，由于哈希的过程将原路径的时序打乱了，不利于目的地的准确预测。针对第二个问题，有两种解决方法：一是通过对起始点聚类进行路径筛选；二是自定义一种考虑时序的衡量标准，这种衡量标准同样克服了第一个问题。

[0089] (2)最长不连续相似度SIMm计算方式，如果将路径看做是字符串，我们可以将任务转化为求解两个字符串的最大不连续公共长度，常用动态规划求解。记路径S2相对于S1最大不连续公共长度为COMm(S1,S2)。由于我们需要寻找的是路径S1的相似路径，而Jaccard相似度在计算的时候会匹配双方的长度都考虑在内，如果路径S1较小而匹配的路径较长，则会被较长的路径所影响。为了提高合理性，既考虑路径顺序的问题，同时强调其他路径相对于路径S1的相似程度，对相似度计算进行了修改，改进后的相似度衡量公式为：

[0090] SIM(S1,S2)＝COMm(S1,S2)/len(S1)

[0091] 其中，len(S1)为路径S1的长度。

[0092] 在优选的实施例中，所述基于路径轨迹的目的地预测系统，还包括：

[0093] 样本筛选模块400，用于在OffLine阶段和OnLine阶段，筛选在待预测订单的出发时间前后预设的时间范围内的样本订单；对所述对应的匹配结果进行筛选，保留与所述待预测订单在同个聚类的样本订单；

[0094] 具体的，对于样本筛选模块400，包括针对哈希结果的样本筛选和对哈希模型匹配结果的聚类选取。

[0095] 其中，针对哈希结果的样本筛选应用于单目的地预测问题。LSH后得到的样本订单集在忽略时间因素下与待预测订单相似度较高，这些样本订单不直接根据相似度SIMm的大小进行订单筛选，而是先去除部分样本订单。这里提供两种进一步筛选样本订单的角度，并介绍本技术中的使用方式：1.基于时间的角度。每个待预测订单的出发时间都能被获取，可以尝试按照一定的时间范围，选定在待预测订单的出发时间前后的样本订单。2.基于空间的角度。对所有的样本订单按照起点位置使用K-Means进行聚类，并记录对应的聚类中心。待预测订单先根据起始点位置找到最近的聚类中心，确定所属聚类，同样，LSH得到的结果进一步筛选，只保留与待预测订单在同个聚类中的样本订单。

[0096] 而对哈希模型匹配结果聚类选取应用于多目的地预测问题。由于直接按照相似度SIMm的大小进行订单筛选会有很大的可能得到距离相近的几个结果，这并不利于在生活中的应用。这里再次使用了K-Means，但聚类对象是LSH得到的所有结果，聚类数量等同于需要的目的地个数，最后选择各个聚类中SIMm最高的目的地作为多目的地预测的结果。

[0097] 单目的地预测模块500，用于对所述样本订单按照起点位置采用K-Means算法进行聚类，并记录对应的聚类中心；根据待预测订单的起点位置找到最近的聚类中心，确定所属聚类；根据相似度衡量公式计算匹配结果的路径相似度，选取同个聚类中的最高相似度的路径作为单个目的地预测结果。

[0098] 具体的，对于单目的地预测模块500，针对单个目的地预测问题，着重关注预测的目的地与实际目的地的偏差。通过加入时间或地理距离远近的因素，对哈希子模型的Query结果作进一步的筛选，接着使用改进的相似度衡量方式，从样本的筛选上降低预测的误差。在OffLine阶段为各个样本订单标上辅助筛选的类标签，OnLine阶段针对待预测样本完成筛选的过程以及相似度的比较。具体步骤如下：筛选在待预测订单的出发时间前后预设的时间范围内的样本订单；对所述样本订单按照起点位置采用K-Means算法进行聚类，并记录对应的聚类中心；根据待预测订单的起点位置找到最近的聚类中心，确定所属聚类；对所述对应的匹配结果进行筛选，保留与所述待预测订单在同个聚类的样本订单；根据相似度衡量公式计算匹配结果的路径相似度，选取同个聚类中的最高相似度的路径作为单个目的地预测结果。

[0099] 在优选的实施例中，所述局部敏感哈希模型模块200，包括Offline单元和Online单元，其中，

[0100] 所述Offline单元，用于通过设计的h个哈希函数对任意长度的样本轨迹进行MinHash转换，得到h维的向量；通过LSH算法将h维的数据平均划分为b个Band，其中每个Band中含有r个哈希函数的结果；对于每一个Band，将r个哈希值都相同的订单存入同一个Bucket，且该Bucket的索引值为对应的r个哈希值；存储LSH阶段的计算结果作为后续OffLine阶段待预测订单的匹配；

[0101] 所述Online单元，用于对于待预测订单在Query过程中，遍历各个Band，按照订单轨迹在该Band中的哈希值找到对应的Bucket，将所有的Buckets存储的样本订单作为为待预测订单在哈希模型中的匹配结果。

[0102] 本实施例提供的一种基于路径轨迹的目的地预测系统，包括：根据预设转换规则对待预测订单中的路径数据进行数值转换处理，得到对应的路径轨迹表示数据；将所述对应的路径轨迹表示数据输入至局部敏感哈希模型，根据LSH算法计算得到对应的匹配结果；采用K-Means算法对所述对应的匹配结果按照目的地个数进行聚类，根据相似度衡量公式计算每个聚类中的匹配结果的路径相似度，选取各个聚类中的最高相似度的路径作为多目的地预测结果。本发明能够通过基于最小哈希的局部敏感哈希算法对轨迹进行降维处理和匹配近似路径集合，针对预测唯一目的地与筛选多目的地等不同问题采取不同的方法，设计多参数评价不同方法的效果验证，提高基于路径轨迹的目的地预测能力，而不含有任何的个人属性特征信息，为用户或司机个人信息不可用的应用提供参考。

[0103] 本发明的另一个实施例还提供了一种计算机可读存储介质，所述计算机可读存储介质包括存储的计算机程序，其中，在所述计算机程序运行时控制所述计算机可读存储介质所在设备执行如上述的基于路径轨迹的目的地预测方法。

[0104] 在本发明的上述实施例中，对各个实施例的描述都各有侧重，某个实施例中没有详述的部分，可以参见其他实施例的相关描述。

[0105] 在本申请所提供的几个实施例中，应该理解到，所揭露的技术内容，可通过其它的方式实现。其中，以上所描述的装置实施例仅仅是示意性的，例如所述模块的划分，可以为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个模块或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口，单元或模块的间接耦合或通信连接，可以是电性或其它的形式。

[0106] 所述作为分离部件说明的模块可以是或者也可以不是物理上分开的，作为模块显示的部件可以是或者也可以不是物理模块，即可以位于一个地方，或者也可以分布到多个模块上。可以根据实际的需要选择其中的部分或者全部模块来实现本实施例方案的目的。

[0107] 另外，在本发明各个实施例中的各功能模块可以集成在一个处理模块中，也可以是各个模块单独物理存在，也可以两个或两个以上模块集成在一个模块中。上述集成的模块既可以采用硬件的形式实现，也可以采用软件功能模块的形式实现。

[0108] 以上所述是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和变形，这些改进和变形也视为本发明的保护范围。

[0109] 本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的程序可存储于一计算机可读取存储介质中，该程序在执行时，可包括如上述各方法的实施例的流程。其中，所述的存储介质可为磁碟、光盘、只读存储记忆体(Read-Only Memory，ROM)或随机存储记忆体(Random Access Memory，RAM)等。