一种基于时空影响距离的K-means站点区域划分方法

摘要

本发明涉及一种基于时空影响距离的K‑means站点区域划分方法，S100获取某一城市轨道交通出行数据，并对数据进行预处理；S200将所有站点xi作为聚类数据集Ω，随机选取一个站点作为初始聚类中心，然后依次选出K个聚类中心；S300计算每个站点到各个聚类中心点的时空影响距离，站点到哪个聚类中心点的时空影响距离最小，就将站点划分到该聚类中心的类中；S400针对重新划分后的每个类别，新计算该类别的聚类中心；S500重复S300和S400，直到每个类别的聚类中心位置不再发生变化，输出聚类中心和各个类中的所有站点。本发明的分类方法不但考虑了站点之间的空间位置，而且还考虑了站点之间的实际位置，分类更准确。

权利要求

1.一种基于时空影响距离的K-means站点区域划分方法，其特征在于，包括如下步骤：S100：获取某一城市轨道交通出行数据，并对数据进行预处理；

所述S100中并对数据进行预处理：

通过清洗获取的某一城市轨道交通出行数据，求得以下各原始值：其中，Ta为平均相邻站点之间的旅程时间，Tb为平均每条线路的全程旅程时间，n为相邻站点对数，m为线路总数，ti为每个相邻站点之间的平均旅程时间，tx为每条线路的全程平均旅程时间；

S200：将所有站点xi作为聚类数据集Ω，从聚类数据集Ω中随机选取一个站点作为初始聚类中心C1，然后依次选出K个聚类中心作为聚类中心点集Θ，Θ＝{c1，c2，c3…ct…ck}；

所述S200中构建聚类中心点集Θ的过程如下：

设Ω＝{x1，x2，x3……}；

设站点xi与初始聚类中心点C1的欧式距离，用D(x)表示；然后再计算站点xi被选为下一个聚类中心点的概率其中，k是坐标参数维度，xik和cjk分别表示站点xi与聚类中心点Cj的第k维数据；

按照每一个站点xi的 的大小确定每一个站点的轮盘面积，再使用轮盘法选取一个聚类中心点；

S300：针对聚类数据集Ω中的每个站点，计算每个站点到各个聚类中心点的时空影响距离d，确定站点xi到哪个聚类中心点的时空影响距离最小，就将站点xi划分到该聚类中心的类中；

所述S300中计算每个站点到各个聚类中心点的时空影响距离具体方法为：两站点之间的时空影响距离由站点之间的平均旅程时间和站点之间的欧氏距离的归一化结果表示：Db＝max{D1，2，D1，3，D1，4……}

Da＝min{D1，2，D1，3，D1，4……}

其中，Ti，j和Di，j分别代表两个站点间的旅程时间和欧氏距离，Db和Da分别是所有站点间的最小欧式距离和最大欧氏距离，Tb和Ta分别是所有站点间的平均最小旅程时间和平均线路最大旅程时间，站点xi到哪个聚类中心点的时空影响距离最小，就将站点xi划分到对应聚类中心的类中；

S400：针对S300重新划分后的每个类别i，新计算该类别的聚类中心Ci；

S500：重复S300和S400，直到每个类别的聚类中心的位置不再发生变化，区域站点划分完成，输出聚类中心和各个类中的所有站点。

2.如权利要求1所述的基于时空影响距离的K-means站点区域划分方法，其特征在于，所述S400中对S300重新划分后的每个类别i，新计算该类别的聚类中心Ci的方法如下：其中，|m|表示的是该聚类中心点的站点总个数，x是Cm中的站点。

说明书

一种基于时空影响距离的K-means站点区域划分方法

技术领域

[0001] 本发明涉及轨道客流量预测方法，特别涉及一种基于时空影响距离的K-means站点区域划分方法。

背景技术

[0002] 目前在全世界都在大力发展城市轨道交通的大环境下，城市轨道交通在城市公共交通中所占载客量比重越来越大。城市轨道交通客流的增大，既为城市轨道交通带了新的发展机遇也带了巨大的挑战。

[0003] 城市轨道交通的网络化复杂程度不断增加，未来交通趋势分析越来越受到重视，基于客流预测的分析结果，我们可以制定交通运营计划，做出拥堵或异常的预警，来改善轨道交通的运营效率和服务质量，所以它已成为智能交通系统(ITS)的关键技术之一。但由于客流受天气、节假日、地理位置等多方面因素的影响，高度的非线性和不确定性给客流预测带来了巨大的挑战。为了能够统筹轨道整体规划，就需要实现更好的区域客流预测。而进行城市的区域客流测首先就需要一个科学有效的城市站点区域分类方法来保证预测的有效性。

[0004] 聚类是非监督学习中重要的算法，聚类分析通过将原始样本划分为多个独立不想交的簇，簇样本具有相同或者类似的特征。常言道“物以类聚，人以群分”，同样在大数据时代的自然科学以及社会科学，存在着大量的数据分类问题，而聚类根据样本的相似性将样本进行分类，在同一个簇中的样本比不在同一个簇中的样本更具有相似性。

[0005] 复杂的线网需要合理科学的运营规划，区域OD客流预测常常可以为线网站点布置提供数据支撑，由此可见区域OD预测的重要性和必要性。而此前的许多区域OD客流预测都是直接使用类似K-means算法的聚类算法通过GPS地理位置聚类完成的区域划分。但是这种仅以地理距离为聚类分类标准的K-means算法对于城市的轨道交通站点分类是有很大局限性的。首先轨道距离与地理距离在多数情况下都有较大偏差，其次在类似重庆一类的城市，复杂错乱的城市地势地貌会给区域划分带来很大的麻烦。

发明内容

[0006] 针对现有技术存在的上述问题，本发明要解决的技术问题是：提出一个基于时空影响距离的K-means站点区域划分算法来更好地规避原始K-means算法的弊端，更加科学合理地完成城市站点区域分割。

[0007] 为解决上述技术问题，本发明采用如下技术方案：一种基于时空影响距离的K-means站点区域划分方法，包括如下步骤：

[0008] S100：获取某一城市轨道交通出行数据，并对数据进行预处理；

[0009] S200：将所有站点xi作为聚类数据集Ω，从聚类数据集Ω中随机选取一个站点作为初始聚类中心C1，然后依次选出K个聚类中心作为聚类中心点集Θ，Θ＝{c1,c2,c3…ct…ck}；

[0010] S300：针对聚类数据集Ω中的每个站点，计算每个站点到各个聚类中心点的时空影响距离d，确定站点xi到哪个聚类中心点的时空影响距离最小，就将站点xi划分到该聚类中心的类中；

[0011] S400：针对S300重新划分后的每个类别i，新计算该类别的聚类中心Ci；

[0012] S500：重复S300和S400，直到每个类别的聚类中心的位置不再发生变化，区域站点划分完成，输出聚类中心和各个类中的所有站点。

[0013] 作为改进，所述S100中并对数据进行预处理：

[0014] 通过清洗获取的某一城市轨道交通出行数据，求得以下各原始值：

[0015]

[0016]

[0017] 其中，Ta为平均相邻站点之间的旅程时间，Tb为平均每条线路的全程旅程时间，n为相邻站点对数，m为线路总数，ti为每个相邻站点之间的平均旅程时间，tx为每条线路的全程平均旅程时间。

[0018] 作为改进，所述S200中构建聚类中心点集Θ的过程如下：

[0019] 设Ω＝{x1,x2,x3……}；

[0020] 设站点xi与初始聚类中心点C1的欧式距离，用D(x)表示；然后再计算站点xi被选为下一个聚类中心点的概率

[0021]

[0022]

[0023] 其中，k是坐标参数维度，xik和cjk分别表示站点xi与聚类中心点C1的第k维数据；

[0024] 按照每一个站点xi的 的大小确定每一个站点的轮盘面积，再使用轮盘法选取一个聚类中心点。

[0025] 作为改进，所述S300中计算每个站点到各个聚类中心点的时空影响距离具体方法为：

[0026] 两站点之间的时空影响距离由站点之间的平均旅程时间和站点之间的欧氏距离的归一化结果表示：

[0027] Db＝max{D1,2,D1,3,D1,4……}   (3-3)；

[0028] Da＝min{D1,2,D1,3,D1,4……}   (3-4)；

[0029]

[0030] 其中，Ti,j和Di,j分别代表两个站点间的旅程时间和欧氏距离，Db和Da分别是所有站点间的最小欧式距离和最大欧氏距离，Tb和Ta分别是所有站点间的平均最小旅程时间和平均线路最大旅程时间，站点xi到哪个聚类中心点的时空影响距离最小，就将站点xi划分到对应聚类中心的类中。

[0031] 作为改进，所述S400中对S300重新划分后的每个类别i，新计算该类别的聚类中心Ci的方法如下：

[0032]

[0033] 其中，|m|表示的是该聚类中心点的站点总个数，x是Cm中的站点。

[0034] 相对于现有技术，本发明至少具有如下优点：

[0035] 本发明的站点区域划分方法中结合站点到聚类中心的欧氏距离和旅行时间来确定站点的时空影响距离，然后再通过时空影响距离来对站点进行分类，这种分类方法考虑了不但考虑了站点之间的空间位置，而且还考虑了站点之间的实际位置，分类更准确。对后期的站点流量测评和站点规划更具指导和参考意义。

附图说明

[0036] 图1为基于时空影响距离的K-means站点区域划分方法聚类结果。

[0037] 图2为基于时空影响距离的K-means站点区域划分图。

[0038] 图3为基于传统地理距离的K-means站点区域划分图。

具体实施方式

[0039] 下面对本发明作进一步详细说明。

[0040] 一种基于时空影响距离的K-means站点区域划分方法，包括如下步骤：

[0041] S100：获取某一城市轨道交通出行数据，并对数据进行预处理。

[0042] 具体地，通过清洗获取的某一城市轨道交通出行数据，求得以下各原始值：

[0043]

[0044]

[0045] 其中，Ta为平均相邻站点之间的旅程时间，Tb为平均每条线路的全程旅程时间，n为相邻站点对数，m为线路总数，ti为每个相邻站点之间的平均旅程时间，tx为每条线路的全程平均旅程时间。

[0046] S200：将所有站点xi作为聚类数据集Ω，从聚类数据集Ω中随机选取一个站点作为初始聚类中心C1，然后依次选出K个聚类中心作为聚类中心点集Θ，Θ＝{c1,c2,c3…ct…ck}。

[0047] 所述S200中构建聚类中心点集Θ的过程如下：

[0048] 设Ω＝{x1,x2,x3……}；

[0049] 设站点xi与初始聚类中心点C1的欧式距离，用D(x)表示；然后再计算站点xi被选为下一个聚类中心点的概率

[0050]

[0051]

[0052] 其中，k是坐标参数维度，xik和cjk分别表示站点xi与聚类中心点C1的第k维数据；

[0053] 按照每一个站点xi的 的大小确定每一个站点的轮盘面积，再使用轮盘法选取一个聚类中心点。

[0054] S300：针对聚类数据集Ω中的每个站点，计算每个站点到各个聚类中心点的时空影响距离d，确定站点xi到哪个聚类中心点的时空影响距离最小，就将站点xi划分到该聚类中心的类中。

[0055] 所述S300中计算每个站点到各个聚类中心点的时空影响距离具体方法为：

[0056] 两站点之间的时空影响距离由站点之间的平均旅程时间和站点之间的欧氏距离的归一化结果表示：

[0057] Db＝max{D1,2,D1,3,D1,4……}   (3-3)；

[0058] Da＝min{D1,2,D1,3,D1,4……}   (3-4)；

[0059]

[0060] 其中，Ti,j和Di,j分别代表两个站点间的旅程时间和欧氏距离，Db和Da分别是所有站点间的最小欧式距离和最大欧氏距离，Tb和Ta分别是所有站点间的平均最小旅程时间和平均线路最大旅程时间，站点xi到哪个聚类中心点的时空影响距离最小，就将站点xi划分到对应聚类中心的类中。

[0061] S400：针对S300重新划分后的每个类别i，新计算该类别的聚类中心Ci。

[0062] 对S300重新划分后的每个类别i，新计算该类别的聚类中心Ci的方法如下：

[0063]

[0064] 其中，|m|表示的是该聚类中心点的站点总个数，x是Cm中的站点。

[0065] S500：重复S300和S400，直到每个类别的聚类中心的位置不再发生变化，区域站点划分完成，输出聚类中心和各个类的所有站点。

[0066] 实验验证：

[0067] 本实验以重庆市为例，将重庆市区轨道交通数据作为实验原始数据集。采用基于时空影响距离的K-means聚类算法对重庆市轨道交通的所有站点进行了科学地分类，这样会便于重庆市地轨道交通区域OD客流分析预测，以及重庆市的轨道交通规划。

[0068] 从实验结果中可以很明确地看出优化后的聚类算法具有更强大的环境适应力，划分效果很好，避免了地理位置接近但是轨道距离较远的错误分类情况。

[0069] 本发明采用旅程时间与空间GPS相结合的划分方式。旅程时间数据来源于历史客流旅程时间的统计。区域OD客流的统计同样基于站点级别的历史OD客流数据。表1中包括卡ID、日期、初始站点、到达站点、初始时间、到达时间几个字段。本实验数据时间范围为2017年到2018年的数据。

[0070] 表1

[0071]

[0072]

[0073] 旅程时间数据如表2所示，属性依次是起始站点、到达站点、以及平均旅程时间。

[0074] 表2

[0075]

[0076] 本发明在对轨道站点进行空间聚类的时候使用的是站点的GPS定位数据，属性依次是：卡id、站点编号、站点名称、经度和纬度，详见表3。

[0077] 表3

[0078]

[0079] 对表1，表2和表3中的数据进行分析得到：

[0080] 图1是基于时空影响距离的K-means聚类算法的实验结果图，从图中可以明显的看到两点：首先聚类划分的地理因素影响依旧很明显，划分结果中每一个同聚类站点的地理位置距离都相对较近，不会出现为了满足时间维度影响而出现地理差距较大的聚类情况；其次聚类站点的分布并不完全依赖直线地理距离，从站点的分布来看都是处于轨道交通线路的相近位置。

[0081] 图2是基于时空影响距离的K-means站点区域划分方法的重庆市轨道交通划分结果，其聚类平均最小站点间距集合最大值为9.9站，小于传统K-means的10.5站，这说明基于时空影响距离的K-means站点区域划分方法在轨道站点的聚类效果上表现更好。所有站点区域的划分都合乎情理又科学有效。

[0082] 图3是原始K-means聚类算法的站点区域划分方法的重庆市轨道交通划分结果，其聚类平均最小站点间距集合最大值为10.5站。不是所有站点区域的划分都科学有效，例如把悦来站和龙头寺站归为同一个区域聚类就非常不合理，两站之间有18站的轨道交通旅程，虽然在地理距离上可以被分为一组，但是两地间的轨道距离远大于直线距离。

[0083] 最后说明的是，以上实施例仅用以说明本发明的技术方案而非限制，尽管参照较佳实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，可以对本发明的技术方案进行修改或者等同替换，而不脱离本发明技术方案的宗旨和范围，其均应涵盖在本发明的权利要求范围当中。