一种基于K-means聚类的车队出行诱导方法

1.一种基于K-means聚类的车队出行诱导方法，其特征在于：所述诱导方法包括以下步骤：
步骤1、从数据库中筛选，将车队中所有车辆最新上传的位置提取出来，形成一个GPS位置集合(L1,L2,L3.....Ln)，n为车辆总数；
步骤2、从GPS位置集合中选择3个点La、Lb与Lc，1≤a,b,c≤n，将以上3点作为初始中心点，通过K-means聚类算法将该集合中的数据聚类成3组，即对应当前车队中行驶在前方的车辆、中间的车辆以及后方的车辆，即将车队分成前中后3个梯队；
所述K-means聚类算法的实现过程为：
(2.1)设定聚簇收敛阈值Delta和最大迭代次数M；
(2.2)将3个初始中心点作为初始值，对集合中其他点Li逐一进行遍历，1≤i≤n并且i≠a,b,c，计算出各点到3个初始中心点的距离dia，dib，dic，并根据最小的距离将该点归类到3个初始中心点中的一个，GPS位置集合(L1,L2,L3.....Ln)最终将产生3个聚簇；
(2.3)更新3个聚簇的聚簇中心点，计算3个簇中每个点到簇中其他点的距离均值，距离均值最小的点被判定为该簇新的中心点；
(2.4)根据3个新的聚簇中心点重新聚类，过程与(2.1)中相同，计算出其余各点到3个中心点的距离，将各点归类到距离最短的中心点所属的簇中，依次类推，将集合重新聚类产生3个新的簇；
(2.5)各自比较上一次的3个聚簇中心与本次的3个聚簇中心的距离是否都小于收敛阈值Delta，若3个距离差均小于Delta，则判定整个K-means聚类过程收敛；反之，再查看迭代次数是否超过最大迭代次数M，若迭代次数超过M，算法结束，否则返回(2.2)；
步骤3、查看GPS位置集合分组后的3个梯队，获取数据最多的一个梯队中的中心点，依次计算与其他两个梯队中各个点的距离，得到该中心点与其他分组中各个点的距离，其距离公式如公式(1)所示：
d＝arccos(sin(y0)sin(ye)+cos(y0)cos(ye)cos(x0-xe))*Re (1)
其中，Re为地球半径，(x0,y0)和(xe,ye)分别为两个位置点的经纬度坐标；之后，将距离d与系统设定的车队掉队距离阈值进行比较，若距离超过阈值，则找到记录对应的车辆并通过后台消息发送向其发出掉队提醒；若没有超过阈值，则检查另外两个位置分组中下一个数据，直到检查完毕。
2.根据权利要求1所述一种基于K-means聚类的车队出行诱导方法，其特征在于：所述诱导方法还包括以下步骤：
步骤4、通过计时检查完成步骤1～步骤3的任务所花时间，若没有超过设定的掉队查询时间，后台中掉队检查线程暂停；当本次检查周期时间超过了设定的掉队查询时间，则返回步骤1进行下一轮的车辆掉队检查；
其中掉队查询时间是系统后台设定的掉队查询周期。
3.根据权利要求1或2所述一种基于K-means聚类的车队出行诱导方法，其特征在于：
所述步骤2中确定了初始中心点的数量为3，选择3个初始中心点的具体实现方法为：
①从GPS位置集合随机选取一个点作为第一个初始中心点；
②随机选取第二个点，选取后计算该第二个点到第一个初始中心点的距离，若距离小于某个距离阈值W，则重新选择，依次类推，若选择超过10次仍未获得符合条件的点，则将下一个随机获得的点作为初始中心点；设置该距离阈值的目的在于尽量分散K-means聚类的各个初始中心点，使得位置集合更快地完成聚类，作为经验值人为设定；
③随机选取第三个点，选取后计算该第三个点到前两个初始中心点的距离，若距离分别小于距离阈值W，则重新选择，依次类推，若选择超过10次仍未获得符合条件的点，则将下一个随机获得的点作为初始中心点。
4.根据权利要求1或2所述一种基于K-means聚类的车队出行诱导方法，其特征在于：
所述步骤3中，车队掉队距离阈值是当车队队长在后台新建车队时设定，不同车队根据实际情况自定义设置。
5.根据权利要求1或2所述一种基于K-means聚类的车队出行诱导方法，其特征在于：
所述步骤1中，车队内各车辆通过手机获取GPS位置并实时上传至后台服务器。

一种基于K-means聚类的车队出行诱导方法\n技术领域\n[0001] 本发明涉及到一种基于K-means聚类的车队出行诱导方法。\n技术背景\n[0002] 目前，全球定位系统（Global Positioning System，GPS）在交通方面的应用越来越多，车载定位设备通过接收GPS卫星的数据信息，并结合相应软件的电子地图，可将车辆较为精确的位置显示在电子地图上。\n[0003] 在人们日常生活中，车队常有集体出行的情况，如团体自驾游、行业车辆进行运输任务等。在车队出行过程中，不同的司机对路况和行驶路线了解也不同，因此车队成员需要在行驶过程中保持通信以便清楚地了解车队中其他成员的情况。当前车队间完成通讯的手段主要依靠对讲机，这种做法的缺陷在于十分不直观，各成员间无法了解相互之间具体的位置，一旦有人掉队，需要花费较长时间沟通才能使掉队成员重新返回队伍，大大影响了车队行驶进度。\n发明内容\n[0004] 为了克服现有的车队出行过程中的无法有效提醒掉队现象、出行诱导性能较差的不足，本发明提供一种能否有效地提醒掉队信息、出行诱导性能良好的基于K-means聚类的车队出行诱导方法。\n[0005] 本发明所采用的技术方案是：\n[0006] 一种基于K-means聚类的车队出行诱导方法，包括以下步骤：\n[0007] 步骤1、从数据库中筛选，将车队中所有车辆最新上传的位置提取出来，形成一个GPS位置集合（L1,L2,L3.....Ln），n为车辆总数；\n[0008] 步骤2、从GPS位置集合中选择3个点La、Lb与Lc，1≤a,b,c≤n，将以上3点作为初始中心点，通过K-means聚类算法将该集合中的数据聚类成3组，即对应当前车队中行驶在前方的车辆、中间的车辆以及后方的车辆，即将车队分成前中后3个梯队；\n[0009] 所述K-means聚类算法的实现过程为：\n[0010] （2.1）设定聚簇收敛阈值Delta和最大迭代次数M；\n[0011] （2.2）将3个初始中心点作为初始值，对集合中其他点Li逐一进行遍历，1≤i≤n并且i≠a,b,c，计算出各点到3个初始中心点的距离dia，dib，dic，并根据最小的距离将该点归类到3个初始中心点中的一个，GPS位置集合（L1,L2,L3.....Ln）最终将并产生3个聚簇；\n[0012] （2.3）更新3个聚簇的聚簇中心点，计算3个簇中每个点到簇中其他点的距离均值，距离均值最小的点被判定为该簇新的中心点；\n[0013] （2.4）根据3个新的聚簇中心点重新聚类，过程与（2.1）中相同，计算出其余各分别点到3个中心点的距离，将各点归类到距离最短的中心点所属的簇中，依次类推，将集合重新聚类产生3个新的簇；\n[0014] （2.5）各自比较上一次的3个聚簇中心与本次的3个聚簇中心的距离是否都小于收敛阈值Delta，若3个距离差均小于Delta，则判定整个K-means聚类过程收敛；反之，再查看迭代次数是否超过最大迭代次数M，若迭代次数超过M，算法结束，否则返回（2.2）；\n[0015] 步骤3、查看GPS位置集合分组后的3个梯队，获取数据最多的一个梯队中的中心点，依次计算与其他两个梯队中各个点的距离，得到该中心点与其他分组中各个点的距离，其距离公式如公式1所示：\n[0016] d＝arccos(sin(y0)sin(ye)+cos(y0)cos(ye)cos(x0-xe))*Re (1)[0017] 其中，Re为地球半径，(x0,y0)和(xe,ye)分别为两个位置点的经纬度坐标；之后，将距离d与系统设定的车队掉队距离阈值进行比较，若距离超过阈值，则找到该记录对应的车辆并通过后台消息发送向其发出掉队提醒；若没有超过阈值，则检查另外两个位置分组中下一个数据，直到检查完毕。\n[0018] 进一步，所述诱导方法还包括以下步骤：步骤4、通过计时检查完成以上任务所花时间，若没有超过设定的掉队查询时间，后台中掉队检查线程暂停；当本次检查周期时间超过了设定的掉队查询时间，则返回步骤1进行下一轮的车辆掉队检查；\n[0019] 其中掉队查询时间是系统后台设定的掉队查询周期。\n[0020] 更进一步，所述步骤2中确定了初始中心点的数量为3，选择3个初始中心点的具体实现方法为：\n[0021] ①从GPS位置集合随机选取一个点作为第一个初始中心点；\n[0022] ②随机选取第二个点，选取后计算该点到第一个初始中心点的距离，若距离小于某个距离阈值W，则重新选择，依次类推，若选择超过10次仍未获得符合条件的点，则将下一个随机获得的点作为初始中心点；设置该距离阈值的目的在于尽量分散K-means聚类的各个初始中心点，使得位置集合更快地完成聚类，作为经验值人为设定；\n[0023] ③随机选取第三个点，选取后计算该点到前两个初始中心点的距离，若距离分别小于距离阈值W，则重新选择，依次类推，若选择超过10次仍未获得符合条件的点，则将下一个随机获得的点作为初始中心点。\n[0024] 所述步骤3中，车队掉队距离阈值是当车队队长在后台新建车队时设定，不同车队根据实际情况自定义设置。\n[0025] 所述步骤1中，车队内各车辆通过手机获取GPS位置并实时上传至后台服务器。\n[0026] 本发明的技术构思为：各车主均需要配备一个带有GPS定位功能的智能手机，并在系统中注册用户，然后创建或加入一个车队。车队队长可在系统中创建一个旅程，其他用户可选择加入该旅程。在车队出行过程中，车队内各车辆通过手机获取GPS位置并实时上传至后台服务器，车队各成员从服务器获取车队所有成员的实时位置并在电子地图上显示；各成员可在车队内进行文字、语音、图片的通讯，方便交流；该方法自动检查车队中各车辆的实时位置，通过K-means聚类算法计算出是否有车辆掉队，若发生掉队则自动向掉队车辆发出提醒，实现出行诱导。通过以上手段，本方法可解决车队出行过程中通讯不便、指挥难等问题，实现更为智能的出行诱导。\n[0027] 在车队出行过程中，车队内各车辆通过手机获取GPS位置并实时上传至后台服务器，系统后台根据车队内所有车辆的实时位置，基于K-means聚类算法计算出车队内是否存在车辆发生了掉队状况，若发生掉队，系统自动向掉队的车辆发出提醒，提醒消息可在手机上查看。\n[0028] 该方法可以保证车队在出行的过程中，各个成员通过手机便能在电子地图上直观地查看整个车队的实时位置信息，并可方便地进行文字、声音、图片的交流。同时该方法实现了成员掉队后的自动提醒，确保掉队成员可快速自助地返回车队，为整个车队的正常行驶提供了便利。\n[0029] 本发明的有益效果主要表现在：可向车队中掉队车辆发出自动提醒，并且结合电子地图使该车更容易快速归队，减少车队在路途中耽误的时间。\n附图说明\n[0030] 图1为本发明实现基于K-means聚类的车队出行诱导方法的流程图。\n[0031] 图2为车队行驶示意图。\n具体实施方式\n[0032] 下面结合附图对本发明作进一步描述。\n[0033] 参照图1和图2，一种基于K-means聚类的车队出行诱导方法，在车队出行过程中，车队内各车辆通过手机获取GPS位置并实时上传至后台服务器，系统后台根据车队内所有车辆的实时位置，基于K-means聚类算法计算出车队内是否存在车辆发生了掉队状况，若发生掉队，系统自动向掉队的车辆发出提醒，提醒消息可在手机上查看，所述诱导方法包括以下步骤：\n[0034] 步骤1、系统后台从数据库中筛选，将车队中所有车辆（假设n辆车）最新上传的位置提取出来，形成一个GPS位置集合（L1,L2,L3.....Ln），如表1所示。\n[0035] \n序号 经度 纬度 车牌号码\n1 120.122 30.11 浙A12345\n2 120.123 30.41 浙A12344\n3 120.121 30.45 浙A12343\n4 120.122 30.50 浙A12342\n5 120.124 30.93 浙A12341\n6 120.123 30.89 浙A12346\n… … …. …\ni 120.122 30.51 浙A12347\ni+1 120.124 30.94 浙A12348\ni+2 120.123 30.13 浙A12349\n… … ….. …\nn … … …\n[0036] 表1\n[0037] 步骤2、从GPS位置集合中选择3个点La、Lb与Lc（1≤a,b,c≤n），将以上3点作为初始中心点，通过K-means聚类算法可将该集合中的数据聚类成3组，即对应当前车队中行驶在前方的车辆、中间的车辆以及后方的车辆，可将车队分成前中后3个梯队；\n[0038] 步骤2中所提到的K-means聚类算法的特点在于需要事先确定聚类个数k，由于在本系统的实际应用中需要将一个车队分成前中后3个梯队，从而计算出车辆掉队的实时情况，基于以上两点，步骤2中确定了初始中心点的数量为3。\n[0039] 其中选择3个初始中心点的具体实现方法为：\n[0040] ①从GPS位置集合随机选取一个点作为第一个初始中心点。\n[0041] ②随机选取第二个点，选取后计算该点到第一个初始中心点的距离，若距离小于某个距离阈值W，则重新选择，依次类推，若选择超过10次仍未获得符合条件的点，则将下一个随机获得的点作为初始中心点。设置该距离阈值的目的在于尽量分散K-means聚类的各个初始中心点，使得位置集合更快地完成聚类，作为经验值人为设定。\n[0042] ③随机选取第三个点，选取后计算该点到前两个初始中心点的距离，若距离分别小于距离阈值W，则重新选择，依次类推，若选择超过10次仍未获得符合条件的点，则将下一个随机获得的点作为初始中心点\n[0043] 其中K-means聚类算法的实现过程为：\n[0044] （2.1）设定聚簇收敛阈值Delta和最大迭代次数M；\n[0045] （2.2）将3个初始中心点作为初始值，对集合中其他点Li（1≤i≤n并且i≠a,b,c）逐一进行遍历，计算出各点到3个初始中心点的距离dia，dib，dic，并根据最小的距离将该点归类到3个初始中心点中的一个。如点L4到初始中心点La,Lb,Lc的距离分别为d4a，d4b，d4c，L4找到距离最近的中心点后将自动归类到该聚簇。依次类推，GPS位置集合（L1,L2,L3.....Ln）最终将并产生3个聚簇；\n[0046] （2.3）更新3个聚簇的聚簇中心点。计算3个簇中每个点到簇中其他点的距离均值，距离均值最小的点被判定为该簇新的中心点。\n[0047] （2.4）根据3个新的聚簇中心点重新聚类，过程与（2.1）中相同，计算出其余各分别点到3个中心点的距离，将各点归类到距离最短的中心点所属的簇中，依次类推，将集合重新聚类产生3个新的簇；\n[0048] （2.5）各自比较上一次的3个聚簇中心与本次的3个聚簇中心的距离是否都小于收敛阈值Delta，若3个距离差均小于Delta，则整个K-means聚类过程收敛了，算法结束。反之，再查看迭代次数是否超过最大迭代次数M，若迭代次数超过M，算法结束，否则返回（2.2），继续执行该算法。\n[0049] 根据表1数据，本方法可得到最终的三个分组结果如表2所示。\n[0050] \n[0051] 表2\n[0052] 步骤3、查看GPS位置集合分组后的3个梯队，获取数据最多的一个梯队中的中心点，依次计算与其他两个梯队中各个点的距离，得到该中心点与其他分组中各个点的距离，其距离公式如公式（1）所示：\n[0053] d＝arccos(sin(y0)sin(ye)+cos(y0)cos(ye)cos(x0-xe))*Re (1)[0054] 其中，Re为地球半径，(x0,y0)和(xe,ye)分别为两个位置点的经纬度坐标。之后，将距离d与系统设定的车队掉队距离阈值进行比较，若距离超过阈值，则找到该记录对应的车辆并通过后台消息发送向其发出掉队提醒；若没有超过阈值，则检查另外两个位置分组中下一个数据，直到检查完毕。\n[0055] 步骤4、系统后台程序通过计时检查完成以上任务所花时间，若没有超过设定的掉队查询时间，后台中掉队检查线程暂停；当本次检查周期时间超过了设定的掉队查询时间，则返回步骤1进行下一轮的车辆掉队检查；\n[0056] 其中掉队查询时间是系统后台设定的掉队查询周期，默认设定为15秒钟。\n[0057] 进一步，一种基于K-means聚类的车队出行诱导方法中，车队掉队距离阈值是当车队队长在后台新建车队时设定，不同车队可根据实际情况自定义设置。\n[0058] 本实施例中，车队掉队距离阈值设定为1000米，其中掉队查询时间，即系统后台设定的掉队查询周期，设定为15秒钟，聚簇收敛阈值Delta为100米，最大迭代次数为10次。\n[0059] 本实施例中，如图1所示，车队各成员的手机实时地将车辆的位置信息上传至系统后台，系统后台根据车队内所有车辆的实时位置，基于K-means聚类方法计算出车队内是否存在车辆发生了掉队状况，若发生掉队，系统自动向掉队的车辆发出提醒，提醒消息可在手机上查看。其中车辆掉队自动检测、提醒方法的实现步骤包括：\n[0060] 第一步，系统后台从数据库中筛选，将车队中所有车辆（假设n辆车）最新上传的位置提取出来，形成一个GPS位置集合（L1,L2,L3.....Ln）；\n[0061] 第二步，从GPS位置集合中选择3个点La、Lb与Lc（1≤a,b,c≤n），将以上3点作为初始中心点，通过K-means聚类算法可将该集合中的数据聚类成3组，即对应当前车队中行驶在前方的车辆、中间的车辆以及后方的车辆，可将车队分成前中后3个梯队；\n[0062] 第二步中所提到的K-means聚类算法的特点在于需要事先确定聚类个数k，而在本系统的实际应用中需要将一个车队分成前中后3个梯队，便于计算出车辆掉队的实时情况，基于以上两点，第二步中确定了初始中心点的数量为3。\n[0063] 其中选择3个初始中心点的具体实现方法为：\n[0064] ①从GPS位置集合随机选取一个点作为第一个初始中心点。\n[0065] ②随机选取第二个点，选取后计算该点到第一个初始中心点的距离，若距离小于某个距离阈值W，则重新选择，依次类推，若选择超过10次仍未获得符合条件的点，则将下一个随机获得的点作为初始中心点。设置该距离阈值的目的在于尽量分散K-means聚类的各个初始中心点，使得位置集合更快地完成聚类，作为经验值人为设定。\n[0066] ③随机选取第三个点，选取后计算该点到前两个初始中心点的距离，若距离分别小于距离阈值W，则重新选择，依次类推，若选择超过10次仍未获得符合条件的点，则将下一个随机获得的点作为初始中心点\n[0067] 其中K-means聚类算法的实现过程为：\n[0068] （2.1）获得聚簇收敛阈值100米和最大迭代次数10次。\n[0069] （2.2）将3个初始中心点作为初始值，对集合中其他点Li（1≤i≤n并且i≠a,b,c）逐一进行遍历，计算出各点到3个初始中心点的距离dia，dib，dic，并根据最小的距离将该点归类到3个初始中心点中的一个。如点L4到初始中心点La,Lb,Lc的距离分别为d4a，d4b，d4c，L4找到距离最近的中心点后将自动归类到该聚簇。依次类推，GPS位置集合（L1,L2,L3.....Ln）最终将并产生3个聚簇；\n[0070] （2.3）更新3个聚簇的聚簇中心点。计算3个簇中每个点到簇中其他点的距离均值，距离均值最小的点被判定为该簇新的中心点。\n[0071] （2.4）根据3个新的聚簇中心点重新聚类，过程与（2.1）中相同，计算出其余各分别点到3个中心点的距离，将各点归类到距离最短的中心点所属的簇中，依次类推，将集合重新聚类产生3个新的簇；\n[0072] （2.5）各自比较上一次的3个聚簇中心与本次的3个聚簇中心的距离是否都小于收敛阈值100米，若3个距离差均小于100米，则整个K-means聚类过程收敛了，算法结束。\n反之，再查看迭代次数是否超过最大迭代次数，若迭代次数超过10次，算法结束，否则返回（2.2），继续执行该算法。\n[0073] 第三步，查看GPS位置集合分组后的3个梯队，获取数据最多的一个梯队中的中心点，依次计算与其他两个梯队中各个点的距离，得到该中心点与其他分组中各个点的距离，其距离公式如公式（1）所示：\n[0074] d＝arccos(sin(y0)sin(ye)+cos(y0)cos(ye)cos(x0-xe))*Re (1)[0075] 其中，Re为地球半径，(x0,y0)和(xe,ye)分别为两个位置点的经纬度坐标。之后，将距离d与系统设定的车队掉队距离阈值进行比较，若距离超过阈值，则找到该记录对应的车辆并通过后台消息发送向其发出掉队提醒；若没有超过阈值，则检查另外两个位置分组中下一个数据，直到检查完毕。\n[0076] 第四步，系统后台程序通过计时检查完成以上任务所花时间，若没有超过设定的掉队查询时间，后台中掉队检查线程暂停；当本次检查周期时间超过了设定的掉队查询时间，则返回第一步进行下一轮的车辆掉队检查；\n[0077] 本技术领域中的普通技术人员应当认识到，以上内容仅是用来说明本发明，而并非用作为对本发明的限定，只要在本发明的实质精神范围内，对以上实例的变化、变型都将落在本发明的权利要求书范围内。