本发明公开了一种基于车辆历史轨迹的个性化路线推荐方法，该方法是：首先建立一个分场景路径时间预测模型，热门路径采用KNN预测，非热门路径采用GBDT算法预测；接着，采用最优化的思想，利用梯度下降方法建模用户偏好；最后根据用户偏好进行个性化推荐。推荐过程中，一方面，本发明将协同过滤思想引入了进来，通过寻找相似的用户，利用相似用户的历史轨迹进行推荐；另一方面，我们也可以将其认为是一个导航问题，只不过不是普通导航，而是一个个性化导航，此时，建立一个多权重道路网图，在这个多权重路网图上，根据用户偏好向量，利用迪杰斯特拉算法求得一条总开销最小的路径，即最满足用户偏好的路径。
1.一种基于车辆历史轨迹的个性化路线推荐方法，其特征在于，包括以下步骤：
1)对轨迹数据进行预处理：包括轨迹恢复、轨迹分割、去除浮动点、地图匹配；
2)分场景进行路径时间预测，热门路径采用KNN算法预测，非热门路径采用GBDT预测模型；
3)获取用户每条轨迹相对偏好，并对用户所有轨迹根据其相对偏好进行聚类，获得用户偏好场景；
4)在每个偏好场景下，利用最优化的思想，采用梯度下降的方法计算用户的偏好向量；
5)利用协同过滤思想，通过寻找相似用户，利用相似用户的历史轨迹进行推荐；如果相似用户没有相应历史轨迹，则建立多权重路网图，根据用户偏好向量，寻找一条开销最小的路径。
2.根据权利要求1所述的一种基于车辆历史轨迹的个性化路线推荐方法，其特征在于：在步骤1)中，首先进行轨迹恢复，轨迹原始数据大多是杂乱无章的GPX点数据，需要按照时间以及司机这两个属性来恢复原始轨迹；接着进行轨迹分割，当轨迹中某段停留时间超过预设阈值后，分割成两条独立路径来研究；再接着进行异常值处理，两个点之间的速度超过正常范围，就是异常值，需要去除；最后进行地图匹配，采用HMM算法将GPX点匹配到实际路网上。
3.根据权利要求1所述的一种基于车辆历史轨迹的个性化路线推荐方法，其特征在于：在步骤2)中，采用分场景分别预测的方法，对于热门路径采用KNN预测算法；而对于其它路径则采用GBDT预测模型进行预测，具体步骤如下：
2.1)对于所有轨迹的起点、终点进行K-MEANS聚类，得到热门区域；
2.2)对于热门区域之间的轨迹再进行K-MEANS聚类，得到热门轨迹；
2.3)对于每一条热门轨迹，分别采用KNN预测算法进行预测，特征为：“是否周末(是，否)，时间段(每30分钟为一个时间段，共48个时段)，天气状况(晴，多云，大雾，小雨，大雨，雪天)”，对特征采用“one-hot”处理，标签为时间；调整K的个数，使得预测效果达到一个最佳状态；
2.4)对于其它任意非热门路径，采用KNN预测代价很高，因为KNN寻找相似轨迹的时间开销成本很大，因此使用GBDT预测模型，虽然预测精度不如KNN，但是对任意一条路径都能够预测，首先构造特征，特征为：“路径上红绿灯数、路径上转弯数、路径最高时速限制、道路级别、车主ID、是否周末，时间段，轨迹总长度，轨迹GPX点个数，轨迹起始位置，轨迹中间位置，轨迹结束位置，起始点与城市中心距离，中间点与城市中心距离，终点与城市中心距离，天气状况”；其中非连续性特征“道路级别(高速、省道、普通道路)、车主ID、是否周末、时间段”采用“one-hot”处理；对于模型采用十折交叉验证，不断调整树的个数、深度、学习率参数，具体方法为采用单一变量原则，最终使得模型预测效果达到一个最优状态，将此预测模型序列化保存下来。
4.根据权利要求1所述的一种基于车辆历史轨迹的个性化路线推荐方法，其特征在于：在步骤3)中，首先获取同起点终点所对应的轨迹的各个开销的最小值，然后求取用户的每一条轨迹针对每一个开销的相对偏好比率，最后对用户所有轨迹的相对偏好进行聚类得到偏好场景，具体步骤如下：
3.1)首先获取同起点终点所对应的轨迹的各个开销的最小值；静态开销，能够利用Dijkstra算法获得；对于动态开销，检索出历史轨迹中所有同起点终点的轨迹，然后利用步骤2)中的预测模型分别预测出用户在每一条路径上的动态开销值，取最小值；这样就得到了各个开销的最小值，记为PCmin，PCmin＝{pc1min,pc2min,...,pcmmin}；
3.2)对用户偏好进行聚类；通过下面这个公式，计算用户当前轨迹P对于第j开销的偏好比率PRj， 式中pcjmin是对应用户当前轨迹的同起点终点的所有轨迹中，第j开销的最小值，pcj是用户当前轨迹的第j开销值，PRj越大，说明用户越偏好于这一个开销；
3.2.1)对偏好比率PR排序，偏好比率越大的排在越前面；
5.根据权利要求1所述的一种基于车辆历史轨迹的个性化路线推荐方法，其特征在于：在步骤4)中，计算用户每一个场景下的偏好向量，具体步骤如下：
4.1)对于场景内的每一条用户轨迹，对于用户来说，都是其认为是最好的，也就是满足下式：式中，PCuser＝{pcu1,pcu2,...,pcum}，PCuser为用户轨迹开销，PCother＝{pco1,pco2,...,pcom},PCother为其他跟PCuser同起点终点的轨迹开销，A＝{a1,a2,…,am},A是偏好向量，A中每个元素代表对应开销的权重；整个式子的意思就是用户的轨迹的开销与偏好向量A内积后，是所有同起点终点轨迹中的最小值；
为了求出用户偏好向量，将上式变为一个最优化问题，然后利用梯度下降方法求出目标函数最优解；目标函数为：上面式子的m表示同起点终点的轨迹数，式子中使用了softsign函数，
这样将一个线性的问题转化为了非线性问题；用户在一个场景下有n条
轨迹，为了获得此场景下的偏好向量，对于聚类中的n条轨迹，目标函数变为：
约束条件的意义为，用户对于每一个开销的偏好的值和为1，同时对于每一个开销的偏好为一个正值；
4.2)为了取得上面目标函数的最小值，首先设定一个初始向量A，然后采用梯度下降的方法不断更新A，直到收敛，此时的A就是用户在此场景下的偏好向量。
6.根据权利要求1所述的一种基于车辆历史轨迹的个性化路线推荐方法，其特征在于：在步骤5)中，根据获得的用户个人情况及偏好情况，为其选择一条符合其偏好的路径，包括如下步骤：
5.1)首先利用协同过滤思想，寻找相似用户，根据其历史轨迹进行推荐；提取车主的信息：“车主年龄”，“车主性别”，“车主驾龄”；提取车辆信息：“车的类型”；提取驾驶信息：“行车平均速度”，“驾驶偏好”；其中“车主年龄(岁)”分为“20-30，30-40，40-50，50-60”这几个段；“车主性别”为“男、女”两种情况；“车主驾龄(年)”分为“0-10，10-20，20-30，30-40”这几个段；“车的类型”分为“私家车，出租车，公交车，卡车”这几种类型；“行车平均速度”通过用户所走过的轨迹除以用户走过所有轨迹的时间得到；“驾驶偏好”即求出来的用户偏好向量；
对于“车主年龄”，“车主性别”，“车主驾龄”，“车的类型”，采用“one-hot”进行处理，然后对于上述信息特征，计算其余弦相似度，余弦相似度公式如下：最终根据余弦相似度的高低，找出用户的Top-N相似用户，然后根据相似用户的历史轨迹进行推荐，即是满足用户偏好的轨迹；
5.2)如果相似用户没有对应的历史轨迹，那么构建一个多权重路网图，根据用户偏好进行导航；多权重路网图中，每条边的权重不再是单个值，而是一个权重向量W，W＝<距离，时间，红绿灯数，油耗>，其中距离，红绿灯数这些静态的能够从开源地图Open Street Map中得到；时间，油耗这些动态的能够通过前面的预测模型预测得到；
在建立好多权重道路网图后，每一条边的权重即为一个权重向量；个性化导航时，将用户偏好向量与边的权重向量内积得到一个值，作为边的新的权重，然后利用传统迪杰斯特拉算法得出一条开销最小的路径，这条路径就是最满足用户偏好的路径。
一种基于车辆历史轨迹的个性化路线推荐方法
技术领域
[0001] 本发明涉及智能交通以及数据挖掘领域，尤其是指一种基于车辆历史轨迹的个性化路线推荐方法。
背景技术
[0002] 随着智能手机、全球定位系统(Global Positioning System，GPS)设备、物联网通信、WIFI等定位技术的迅速发展和广泛普及，基于位置的信息服务得到了迅猛发展。路径导航作为智能交通的重要组成部分，在我们的日常生活中伴有重要角色，目前市面上已经涌现出了很多优秀的导航软件，比如高德，凯立德，百度地图等等。这些导航软件通过精准的定位可以给人们提供非常详细的导航信息，极大地方便了人们出行。然而随着科学技术不断发展，人们生活水平的不断提高，现在人们已经不再满足于一种“一视同仁”的导航服务了，而更希望获得一种“量身定做”的路径导航体验，个性化路线推荐成为大势所趋。
[0003] 现在人们出行时，除了考虑距离、时间情况外，还有可能会考虑油耗、拥堵情况、收费情况、路面整洁情况、红绿灯情况甚至路径上是否有上下坡等等情况。众多的考虑因素，对应了不同的偏好人群。如果能有效的捕获用户的驾驶偏好，从而进行一个“量身定做”的出行路线推荐，那么人们出行的导航服务体验将会得到一个质的提升。
[0004] 轨迹挖掘作为数据挖掘技术在智能交通中一个最典型的应用，已经成功被应用到了城市热点发现，出租车乘客发现等领域，并取得了不错效果。基于轨迹的个性化路线推荐作为近两年的一个研究热点，已有不少人开始研究。大家的主要研究点为：1)如何准确的预测出用户在某条路径的动态开销值(动态，就是随着时间变化而不固定的值，比如时间，油耗等)，从而便于建模用户偏好；2)寻找出一种好的建模用户偏好的方法，能够准确建模用户驾驶偏好；3)根据用户偏好情况，进行个性化推荐。
[0005] 本专利针对个性化路线推荐问题，提出了自己的解决方法。首先建立一个分场景路径时间预测模型，热门路径采用KNN预测，非热门路径采用GBDT算法预测；接着，采用最优化的思想，利用梯度下降方法建模用户偏好；最后根据用户偏好进行个性化推荐。推荐过程中，一方面，本专利将协同过滤思想引入了进来，通过寻找相似的用户，利用相似用户的历史轨迹进行推荐；另一方面，我们也可以将其认为是一个导航问题，只不过不是普通导航，而是一个个性化导航，此时，建立一个多权重道路网图，在这个多权重路网图上，根据用户偏好向量，利用迪杰斯特拉算法求得一条总开销最小的路径，即最满足用户偏好的路径。
发明内容
[0006] 本发明的目的在于对现有的导航软件做一个补充，提出了一种基于车辆历史轨迹的个性化路线推荐方法。本发明首先提出自己的时间预测模型，接着分场景建模用户偏好，最后从两方面实现个性化推荐，一方面利用协同过滤思想寻找相似用户，利用相似用户轨迹进行推荐；另一方面，根据偏好向量在路网图上导航出最满足偏好的路径。第一种情况适用于有相似用户以及有相应历史轨迹的情况；第二种情况适用于没有相应历史轨迹的情况。
[0007] 为实现上述目的，本发明所提供的技术方案为：一种基于车辆历史轨迹的个性化路线推荐方法，包括以下步骤：
[0008] 1)对轨迹数据进行预处理：包括轨迹恢复、轨迹分割、去除浮动点、地图匹配等；
[0009] 2)分场景进行路径时间预测，热门路径采用KNN算法预测，非热门路径采用GBDT预测模型；
[0010] 3)获取用户每条轨迹相对偏好，并对用户所有轨迹根据其相对偏好进行聚类，获得用户偏好场景；
[0011] 4)在每个偏好场景下，利用最优化的思想，采用梯度下降的方法计算用户的偏好向量；
[0012] 5)利用协同过滤思想，通过寻找相似用户，利用相似用户的历史轨迹进行推荐；如果相似用户没有相应历史轨迹，则建立多权重路网图，根据用户偏好向量，寻找一条开销最小的路径。
[0013] 在步骤1)中，首先进行轨迹恢复，轨迹原始数据大多是杂乱无章的GPX点数据，需要按照时间以及司机这两个属性来恢复原始轨迹；接着进行轨迹分割，当轨迹中某段停留时间超过一定阈值后，分割成两条独立路径来研究；再接着进行异常值处理，两个点之间的速度超过正常范围，就是异常值，需要去除；最后进行地图匹配，采用HMM(Hidden Markov Model)算法将GPX点匹配到实际路网上。
[0014] 在步骤2)中，因为本发明不是针对某一条特定路线，比如高速或者公交路线等单一路线，而是针对整个城市中的任意路线，因此我们采用分场景分别预测的方法，对于热门路径采用KNN(K-Nearest Neighbor)预测算法；而对于其他路径则采用GBDT(Gradient Boosting Decision Tree)进行预测，具体步骤如下：
[0015] 2.1)对于所有轨迹的起点、终点进行K-MEANS聚类，得到热门区域；
[0016] 2.2)对于热门区域之间的轨迹再进行K-MEANS聚类，得到热门轨迹；
[0017] 2.3)对于每一条热门轨迹，分别采用KNN预测算法进行预测，特征为：“是否周末(是，否)，时间段(每30分钟为一个时间段，共48个时段)，天气状况(晴，多云，大雾，小雨，大雨，雪天)”，对特征采用“one-hot”处理，标签为时间。调整K的个数，使得预测效果达到一个最佳状态；
[0018] 2.4)对于其他任意非热门路径，采用KNN预测代价很高，因为KNN寻找相似轨迹的时间开销成本很大，因此使用GBDT预测模型，虽然预测精度不如KNN，但是对任意一条路径都可以预测，首先构造特征，特征为：“路径上红绿灯数、路径上转弯数、路径最高时速限制、道路级别、车主ID、是否周末，时间段，轨迹总长度，轨迹GPX点个数，轨迹起始位置，轨迹中间位置，轨迹结束位置，起始点与城市中心距离，中间点与城市中心距离，终点与城市中心距离，天气状况”。其中非连续性特征“道路级别(高速、省道、普通道路)、车主ID、是否周末、时间段”采用“one-hot”处理。对于模型采用十折交叉验证，不断调整树的个数，深度，学习率等参数，具体方法为采用单一变量原则，最终使得模型预测效果达到一个最优状态。将此预测模型序列化保存下来。
[0019] 在步骤3)中，首先获取同一个起点终点所对应的轨迹的各个开销的最小值，然后求取用户的每一条轨迹针对每一个开销的相对偏好比率，最后对用户所有轨迹的相对偏好进行聚类得到偏好场景，具体步骤如下：
[0020] 3.1)首先获取同一个起点终点所对应的轨迹的各个开销的最小值。静态开销，比如距离，可以利用Dijkstra算法获得；对于动态开销，比如时间或者油耗，检索出历史轨迹中所有同起点终点的轨迹，然后利用2)中的预测模型分别预测出用户在每一条路径上的动态开销值，取最小值。这样就得到了各个开销的最小值，记为PCmin，PCmin＝{pc1min,pc2min,...,pcmmin}。
[0021] 3.2)对用户偏好进行聚类。通过下面这个公式，计算用户当前轨迹P对于第j开销的偏好比率PRj， 式中pcjmin是对应用户当前轨迹的同起点终点的所有轨迹中，第j开销的最小值，pcj是用户当前轨迹的第j开销值，PRj越大，说明用户越偏好于这一个开销。然后对用户的偏好进行聚类，聚类方法如下：
[0022] 3.2.1)对偏好比率PR排序，偏好比率越大的排在越前面；
[0023] 3.2.2)利用最长公共前缀来进行聚类。
[0024] 在步骤4)中，计算用户每一个场景下的偏好向量，具体步骤如下：
[0025] 4.1)对于场景内的每一条用户轨迹，对于用户来说，都是其认为是最好的，也就是满足下式：
[0026]
[0027] 式中PCuser＝{pcu1,pcu2,...,pcum}，PCuser为用户轨迹开销，PCother＝{pco1,pco2,...,pcom},PCother为其他跟PCuser同起点终点的轨迹开销，A＝{a1,a2,…,am},A是偏好向量，A中每个元素代表对应开销的权重。整个式子的意思就是用户的轨迹的开销与偏好向量A内积后，是所有同起点终点轨迹中的最小值；
[0028] 为了求出用户偏好向量，将上式变为一个最优化问题，然后利用梯度下降方法求出目标函数最优解。目标函数为：
[0029]
[0030] 上面式子的m表示同起点终点的轨迹数，式子中使用了softsign函数，这样将一个线性的问题转化为了非线性问题。用户在一个场景下有n条
轨迹，为了获得此场景下的偏好向量，对于聚类中的n条轨迹，目标函数变为：
[0031]
[0032] 约束条件为：
[0033]
[0034] 约束条件的意义为，用户对于每一个开销的偏好的值和为1，同时对于每一个开销的偏好为一个正值。
[0035] 4.2)为了取得上面目标函数的最小值，首先设定一个初始向量A，然后采用梯度下降的方法不断更新A，直到收敛，此时的A就是用户在此场景下的偏好向量。
[0036] 在步骤5)中，根据获得的用户个人情况及偏好情况，为其选择一条符合其偏好的路径，包括如下步骤：
[0037] 5.1)首先利用协同过滤思想，寻找相似用户，根据其历史轨迹进行推荐。提取车主的信息：“车主年龄”，“车主性别”，“车主驾龄”；提取车辆信息：“车的类型”；提取驾驶信息：“行车平均速度”，“驾驶偏好”。其中“车主年龄(岁)”分为“20-30，30-40，40-50，50-60”这几个段；“车主性别”为“男、女”两种情况；“车主驾龄(年)”分为“0-10，10-20，20-30，30-40”这几个段；“车的类型”分为“私家车，出租车，公交车，卡车”这几种类型；“行车平均速度”通过用户所走过的轨迹除以用户走过所有轨迹的时间得到；“驾驶偏好”即求出来的用户偏好向量。
[0038] 对于“车主年龄”，“车主性别”，“车主驾龄”，“车的类型”，我们采用“one-hot”进行处理，然后对于上述信息特征，我们计算其余弦相似度，余弦相似度公式如下：
[0039]
[0040] 最终根据余弦相似度的高低，找出用户的Top-N相似用户，然后根据相似用户的历史轨迹进行推荐，即是满足用户偏好的轨迹。
[0041] 5.2)如果相似用户没有对应的历史轨迹，那么构建一个多权重路网图，根据用户偏好进行导航。多权重路网图中，每条边的权重不再是单个值，而是一个权重向量W，W＝<距离，时间，红绿灯数，油耗>，其中距离，红绿灯数等静态的可以从开源地图Open Street Map中得到；时间，油耗等动态属性可以通过前面的预测模型预测得到。
[0042] 5.3)利用迪杰斯特拉寻找最小开销值路径
[0043] 在建立好了多权重道路网图后，每一条边的权重即为一个权重向量。个性化导航时，将用户偏好向量与边的权重向量内积得到一个值，作为边的新的权重，然后利用传统迪杰斯特拉算法得出一条开销最小的路径，这条路径就是最满足用户偏好的路径。
[0044] 本发明与现有技术相比，具有如下优点与有益效果：
[0045] 1、本发明通过开源地图以及气象网站等多种途径挖掘到了丰富的特征信息。对于城市中的任意路径的时间预测，我们分为了热门路径，以及非热门路径两种场景，对于热门路径采用KNN算法预测，对于非热门路径采用GBDT模型预测，这样分别对待，可以对人们最关心的路径时间提供准确的预测，同时对其他非热门路径也可以提供一个近似预测。
[0046] 2、本发明为了更加具体的建模用户的偏好，首先建模了用户偏好场景，接着在每个场景中，分别求取用户偏好，这样可以更加准确的捕获用户偏好情况；求偏好的过程本是一个线性的过程，本专利中将其转化为了一个最优化问题，这样可以得到一个具体的偏好向量。
[0047] 3、本发明在个性化推荐过程中，将协同过滤思想引入了进来，通过车主自身信息以及其驾驶偏好信息两方面寻找相似用户，利用相似用户的轨迹进行推荐；而对于没有相似轨迹的场景，本专利构建了一个多权重道路网图，在此道路网图的基础上利用迪杰斯特拉算法，可求得一条总开销最小的路径，即最满足用户偏好的路径。
[0048] 4、本发明方法可以自动捕获用户偏好，同时可以为其选择一条满足其偏好的路径，可以提高用户出行体验，在导航领域，有较大价值。
附图说明
[0049] 图1为本发明方法整体流程图。
[0050] 图2为用户偏好建模流程图。
具体实施方式
[0051] 下面结合附图以及实例对本发明作进一步说明。
[0052] 本发明主要目的就是根据历史轨迹进行个性化路线推荐，辅助现有路径导航软件，提升用户的出行导航体验。从原始轨迹数据中提取轨迹特征，训练动态开销预测模型，然后建模用户偏好，最后进行个性化路线推荐(整体流程如图1所示)。具体包含以下步骤：
[0053] 一、轨迹预处理
[0054] 对轨迹数据进行预处理：包括轨迹恢复、轨迹分割、去除浮动点、地图匹配等。轨迹恢复，轨迹原始数据大多是无序的GPX点数据，按照时间以及司机这两个属性来恢复原始轨迹；轨迹分割，当轨迹中某段停留时间超过一定阈值后，分割成两条独立路径来研究；异常值处理，两个点之间的速度超过正常范围，就是异常值，需要去除；地图匹配，采用HMM算法将GPX点匹配到实际路网上。经过预处理后的轨迹记为P,P(e)＝{e1,e2,...,en)，其中e为路段ID。
[0055] 二、分场景进行路径时间预测
[0056] 本发明不是针对某一条特定路线，比如高速或者公交路线，而是针对整个城市中的任意路线，因此我们采用分场景分别预测的方法，对于热门路径采用KNN预测算法；而对于其他路径则采用GBDT(Gradient Boosting Decision Tree)进行预测，具体步骤如下：
[0057] 对于所有轨迹的起点、终点进行K-MEANS聚类，得到热门区域；
[0058] 对于热门区域之间的轨迹再进行K-MEANS聚类，得到热门轨迹；
[0059] 对于每一条热门轨迹，分别采用KNN预测算法进行预测，特征为：“是否周末，时间段，天气状况”，标签为时间。调整K的个数，使得预测效果达到一个最佳状态；
[0060] 对于其他任意非热门路径，采用KNN预测代价很高，因此使用GBDT预测模型，首先构造特征，特征为：“路径上红绿灯数、路径上转弯数、路径最高时速限制、道路级别、车主ID、是否周末，时间段，轨迹总长度，轨迹GPX点个数，轨迹起始位置，轨迹中间位置，轨迹结束位置，起始点与城市中心距离，中间点与城市中心距离，终点与城市中心距离，天气状况”。
[0061] 对其中部分特征进行说明，每一天的不同时间段，道路交通状况不同，因此将一天按照每三十分钟为一个时间段，分成48个时段；工作日和周末，道路状况也不同，周末不用上班，大家一般在家里；道路上红绿灯会导致停留，会对时间和油耗有很大影响；道路级别不同，最高时速限制也不同，会影响行驶时间。
[0062] 对于特征中的“车辆ID，是否周末,时间段，道路级别，轨迹起始位置，轨迹中间位置,轨迹结束位置”这几个特征并不能直接放入模型中进行训练，需要进行“one-hot”处理。比如，“天气状况”，有“晴，多云，大雾，小雨，大雨，雪天”六种情况，对于“晴天”的情况，特征将变为[1,0,0,0,0,0]，对于“多云”的情况，特征变为[0,1,0,0,0,0]。“轨迹起始位置，轨迹中间位置,轨迹结束位置”这三个特征为地图匹配后的路段ID值，那么对于整个城市，路段很多，那么“one-hot”后，这三个特征可能会使得整个特征维度很大，此时，将城市分区域进行训练，比如划分为16个区域，即可解决维度大的问题。
[0063] 训练模型过程中，本专利采用十折交叉验证，通过不断调整树的个数，深度，学习率等参数，具体方法为采用单一变量原则，最终使得模型预测效果达到一个最优状态。将此预测模型序列化保存下来。
[0064] 三、建模用户偏好
[0065] 建模用户偏好时，首先需要获取用户偏好场景，然后在此场景下进行用户偏好向量求取，流程图如图2所示，具体过程如下：
[0066] 1、获取各个开销最小值。开销包含静态开销和动态开销，对于静态开销，用Dijkstra算法或者A*算法计算出针对此开销的“最短”路径，从而得到最小值；对于动态开销，开销随时间变化，不是一个常值，因此没法用上面的办法。本专利采取的方法是检索出当前轨迹同起点终点的所有历史轨迹，然后利用我们的预测模型预测出用户在此路径上的动态开销值，取所有开销中的最小值。这样就得到了各个开销的最小值，记为PCmin，PCmin＝{pc1min,pc2min,...,pcmmin}。。
[0067] 2、对偏好进行聚类。通过下面这个公式，计算用户当前轨迹P对于第j开销的偏好比率PRj， 式中pcjmin是对应用户当前轨迹的同起点终点的所有轨迹中，第j开销的最小值，Pcj是用户当前轨迹的第j开销值，PRj越大，说明用户越偏好于这一个开销。然后对用户的偏好进行聚类，聚类方法如下：
[0068] 1)对偏好比率PR排序，偏好比率越大的排在越前面；
[0069] 2)利用最长公共前缀来进行聚类。比如两条轨迹偏好属性排序后结果为{时间，油耗，距离，红绿灯}，以及{时间，油耗，红绿灯，距离}，那么可以得出这两条路径都属于偏向于时间短和油耗少的路径，因此为一个偏好类别“时间，油耗”。
[0070] 3)用上述聚类方法对用户所有的轨迹进行聚类，这样得出的偏好聚类就对应了具体的某个场景，比如上下班等。当然存在用户没有偏好的场景，此时利用常规导航方法比如最短路径或者最短时间即可。
[0071] 3、计算用户偏好向量
[0072] 对于场景内的每一条用户轨迹，对于用户来说，都是其认为是最好的，也就是满足下式：
[0073]
[0074] 式中PCuser＝{pcu1,pcu2,...,pcum}，PCuser为用户轨迹开销，PCother＝{pco1,pco2,...,pcom},PCother为其他跟PCuser同起点终点的轨迹开销，A＝{a1,a2,…,am},A是偏好向量，A中每个元素代表对应开销的权重，如轨迹开销顺序为{路程，时间，油耗}，A＝{0.6,0.2,0.2},那么路程的权重就为0.6，时间权重为0.2，油耗权重为0.2。整个式子的意思就是用户的轨迹的开销与偏好向量A内积后，是所有同起点终点轨迹中的最小值；
[0075] 为了求出用户偏好向量，将上式变为一个最优化问题，然后利用梯度下降方法求出目标函数最优解。目标函数为：
[0076]
[0077] 上面式子的m表示同起点终点的轨迹数，式子中使用了softsign函数，这样将一个线性的问题转化为了非线性问题。用户在一个场景下有n条
轨迹，为了获得此场景下的偏好向量，对于聚类中的n条轨迹，目标函数变为：
[0078]
[0079] 约束条件为：
[0080]
[0081] 约束条件的意义为，用户对于每一个开销的偏好的值和为1，同时对于每一个开销的偏好为一个正值。
[0082] 为了取得上面目标函数的最小值，首先设定一个初始向量A，比如A＝{0.25,0.25,0.25,0.25}，然后采用梯度下降的方法不断更新A，即A中每一个元素都朝着这个函数关于此分量元素的导数(即梯度)方向变化，每次变化一个步长(比如0.02)，直到目标函数收敛，那么此时得到一个偏好向量A，就是用户在此场景下的偏好向量。
[0083] 四、个性化路线推荐
[0084] 1、利用协同过滤思想，寻找相似用户，根据其历史轨迹进行推荐
[0085] 首先我们寻找相似用户，利用相似用户的轨迹进行推荐。用相似用户轨迹的好处有：首先可以确保是满足自身偏好的；同时，其历史轨迹也包含了一些的经验主义在里面。过程为，提取车主的信息：“车主年龄”，“车主性别”，“车主驾龄”；提取车辆信息：“车的类型”；提取驾驶信息：“行车平均速度”，“驾驶偏好”。其中“车主年龄(岁)”分为“20-30，30-
40，40-50，50-60”这几个段；“车主性别”为“男、女”两种情况；“车主驾龄(年)”分为“0-10，
10-20，20-30，30-40”这几个段；“车的类型”分为“私家车，出租车，公交车，卡车”这几种类型；“行车平均速度”通过用户所走过的轨迹除以用户走过所有轨迹的时间得到；“驾驶偏好”即求出来的用户偏好向量。
[0086] 对于“车主年龄”，“车主性别”，“车主驾龄”，“车的类型”，我们采用“one-hot”进行处理，然后对于上述特征，我们计算其余弦相似度，余弦相似度公式如下：
[0087]
[0088] 最终根据余弦相似度的高低，找出用户的Top-N相似用户，然后根据相似用户的历史轨迹进行推荐，即是满足用户偏好的轨迹。
[0089] 2、构建多权重路网图
[0090] 如果相似用户没有对应的历史轨迹，那么构建一个多权重路网图，根据用户偏好进行导航。针对每个用户构建一个多权重路网图，并且只需要构建一个局部的道路网图即可，也就是用户起点终点间的路网图。传统的道路网图的边的权重一般为距离或者时间，这样就可以得出最短，最快路径，然而在我们个性化推荐模型中，这样的道路网图是不能满足我们的需求的。因此，需要构建新的路网图，称为多权重路网图。多权重路网图中，每条边的权重不再是单个值，而是一个权重向量W，W＝<距离，时间，红绿灯数，油耗>，其中距离，红绿灯数等静态的可以从开源地图Open Street Map中得到；时间，油耗等动态属性可以通过前面的预测模型预测得到，此时要预测的是一个路段的时间或者油耗值，那么预测模型中的“轨迹起始位置，轨迹中间位置,轨迹结束位置”将不再起作用，都为此路段ID，其他特征不变，这样即可得到用户在此条路段(也就是路网图中的边)的动态开销。
[0091] 3、利用迪杰斯特拉寻找最小开销值路径
[0092] 在建立好了多权重道路网图后，每一条边的权重即为一个权重向量。这时，直接利用传统迪杰斯特拉算法进行导航是不行的。因此，对这个道路网图的边权进行一下处理，将边的权重变成用户偏好向量与边的权重向量的乘积值，这样就可以利用传统迪杰斯特拉算法得出一条综合开销最小的路径，这条路劲就是最满足用户偏好的路径。
[0093] 以上所述实施例只为本发明之较佳实施例，并非以此限制本发明的实施范围，故凡依本发明之形状、原理所作的变化，均应涵盖在本发明的保护范围内。
