K-means聚类算法在公交IC卡数据分析中的应用研究

杨健兵

摘   要：文章通过收集南通市区公交线路名称和站点名称，在不依赖GPS定位数据的基础上，通过采用K-means聚类算法分析乘客上车时间序列来建立乘客上车站点的理论模型，并跟车记录该线路每站点的实际上车乘客人数，进而验证所提理论的可行性。

关键词：公共交通;IC卡;K-means;聚类

1    公交IC卡相关研究

在城市公共交通规划和管理的过程中，公交客流量特别是每个站点上车人数是城市公交线网规划和管理的基础数据，它为公交线网优化、站点设置、运营调度提供最可靠的数据支持。传统的公交客流调查大多数通过问卷调查获得，这种调查方法相对原始、落后，耗费大量的人力、物力和财力，并且最终获得的数据也不精确，往往为最终决策带来一定误差。而伴随着智能公共交通系统的发展和普及，公交IC卡收费系统、GPS监控系统、车辆监控系统中积累了大量原始的公交数据，特别是公交IC卡收费系统保存了每位乘客的上车刷卡信息，这些海量的刷卡信息内部蕴含真实、全面的公交客流信息[1-2]，如何利用数据挖掘技术从这些海量的公交IC卡数据中快速获取真实、全面的公交客流信息，特别是每个站点上车人数，从而发现隐含在其中的乘客乘车规律，也是研究的热点问题。

最近几年，国内外学者在公交IC卡数据分析中做了大量的研究工作。在国外，Jinhua结合AFC及AVC数据获取上车站点，然而国外的城市公交系统与国内的相差很大。在國内，戴宵等[3]提出了对公交卡乘客的刷卡时间进行聚类分析来判断乘客上车站点的方法，于勇等[4]结合公交运营调度时刻表所提供的车辆及其发车信息，推算各车次到达各站点的时间，提高了上车站点推算精度。周锐[5]提出了基于IC卡数据的公交站点客流推算方法。赵鹏[6]基于成都公交IC卡数据的乘客上下车站点推算方法进行研究。徐文远等[7]基于公交IC卡数据的公交客流统计方法进行研究。以上的研究存在数据不完整、准确率偏低等问题，研究的正确性很难得到保证。

目前国内大部分城市乘客乘车采用刷卡收费办法，乘客在坐车时刷卡，下车后不要刷卡，所以在IC数据库中仅记录乘客刷卡上车时间，没有乘客下车时间。在缺乏GPS定位数据的前提下，利用数据挖掘中聚类算法对IC卡刷卡数据进行聚类，将聚类结果结合公交线路信息和站点信息来推算公交乘客的上车站点，实现IC卡数据有效合理利用。

2    数据预处理

本文需要预处理的数据主要涉及公交IC卡刷卡数据、公交车辆基本信息数据和公交线路站点数据。公交IC卡刷卡数据包括运营公司、IC卡编号、刷卡时间、刷卡金额、卡类型、线路编号、IC卡设备编号、公交车辆编号等字段。在本文的研究过程中，选取IC卡编号、IC卡类型，刷卡时间、线路编号4个字段属性。公交刷卡数据库如表1所示。

由于公交车在行驶过程中依次停靠公交的各个站点，乘客刷卡上车，且公交IC卡刷卡消费数据所记录乘客刷卡时间具有一定的次序性，即刷卡时间早的乘客早于刷卡时间晚的乘客上车，因此，乘客上车的站点顺序只有两种状况。

（1）乘车站点相同：该站点所有的乘客刷卡时间相差不大，相邻两位乘客间的刷卡间隔非常短，大概在几秒之间。该站点第一个上车乘客和最后一个上车乘客刷卡时间差也不是很大。

（2）乘车站点不同：前面的站点刷卡时间早于后面站点刷卡时间。在这种情况下，由于公交车从一个站点行驶到另外一个站点，所以相邻两个刷卡间隔比较长。

通过分析乘客刷卡记录，可以看到公交乘客在相同站点乘车，刷卡时间间隔较短，乘客在不同站点乘车，其刷卡时间间隔较长，这样可以通过乘客刷卡记录用K-means方法进行聚类，使乘客的刷卡上车时间序列与公交线路的站点序列一一匹配，建立符合逻辑的乘客上车站点估计模型。

3    相关工作

3.1  数据挖掘

数据挖掘是知识发现中的一个步骤[8]。数据挖掘技术一般是指从海量的数据中通过一定的算法进行计算，在算法的帮助下发现隐藏于其中的、有规律信息的过程。数据挖掘技术和计算机科学技术密切相关，可以通过数据库技术、统计技术、在线分析技术、机器学习、模式识别等诸多方法来实现上述目标。

3.2  聚类算法和K-means聚类算法

聚类算法是一种非监督机器学习算法，其实质是将数据对象划分成子集的过程。聚类分析的算法有多种，如划分法、层次法、基于密度的方法、基于网格的方法、基于模型的方法[9]。K-means算法属于划分方法中的一种，采用距离作为相似性的评价指标，该算法认为簇是由距离靠近的对象组成的，因此，把得到紧凑且独立的簇作为最终目标。

K-means算法把对象组织成多个互斥的组或簇，采用距离作为相似性的评价指标。假设数据集D包含n个欧式空间中的对象。聚类的目的是把D的对象分配到k个簇C1，…，Ck中，使得对于1≤i，j≤k，Ci∈D且Ci∩Cj=￠。聚类的划分的目的使得簇内高相似性和簇间低相似性为目标。

设数据集集合D={x1，x2，…，xn}，xi={xi1，xi2，…，xir}，xj={xj1，xj2，…，xjr }，则样本xi和xj之间的欧式距离为：

误差函数平方和如下：

其中，k为聚类数目，ri是第i类样本的个数，ni是i类样本的平均值。

K-mean均值的算法复杂度为O（nkt），其中，n是对象总数，k是用户指定的簇数，t为迭代次数。通常情况下，k<

K-means算法的优点是算法简单，易于实现，而且收敛速度快，计算工作很快就能完成。

3.3  乘客上车站点判断

由于我国绝大多数城市公交乘车采用上车刷卡的形式，并且刷卡记录只是记录上车时刻，并无上车站点，所以可以通过K-means聚类算法对居民上车站点进行判断，计算得出每个站点上车人数。在进行K-means聚类算法之前，先要对原始IC卡数据进行预处理，具体步骤如下。

（1）读取数据库中乘客刷卡数据，并将单个乘客刷卡记录匹配到各线路。

（2）将乘客的刷卡记录分线路车辆按照刷卡时间进行排序。

（3）读取驾驶员刷卡时间，位于两次驾驶员刷卡时间之间记录就是该线路，该车次乘客刷卡记录如表2所示，该记录就是要用K-means聚类算法进行计算的记录。

（4）由于表2乘客刷卡记录表中刷卡时间是时间格式，为了便于聚类，需要把它转换成文本格式，设时间格式为HH∶MM∶SS，时间字段值为3 600×HH+60×MM+SS，并且删除其他字段表，转换后的刷卡记录如表3所示。

（5）聚类计算：根据南通18路公交线路营运情况，南通18路公交共有23个站点，假设除了终点没有人刷卡以外，其他线路都有人上车刷卡，这样使用K-means聚类时k的值为22。

根据给定的公式，K-means算法的具体实现过程如下。在初始化的过程中，在数据集中任意选择k个对象，k的值为22，每个对象代表该簇的中心点，对其余的每个对象，根据其与各簇中心的距离，将该对象划分到最近的簇。然后对于k个簇，重新计算其均值。更新后的均值作为该簇新的簇中心。迭代继续，直到分配稳定，K-means聚类算法的串行计算流程如图1所示。

4    实验结果

4.1  实验环境

在本实验中，使用2台服务器搭建hadoop集群，每台机器CPU为Intel Xeon E5520×2，内存32 G。机器上安装Centos7操作系统，搭建ambari大数据管理平台，在ambari平台下安装mahout数据挖掘系统，来运行K-means数据挖掘算法。

4.2  实验结果

实验数据选取南通18路公交2018年7月18日一次行驶过程的刷卡记录，数据记录共81条，通过匹配南通18路公交22个站点，经过分析后得出每个站点刷卡人数，具体如表4所示。

5     结语

本文针对南通公交缺乏GPS调度数据的情况，利用公交IC卡刷卡记录，通过聚类算法来对刷卡记录进行聚类，根据聚类的结果来推算每个站点刷卡人数，实验表明，该算法可靠、有效，可以精确地匹配到每个站点上车人数。通过对数据的研究，可以合理地安排公交调度，极大地提高公交的运行效率。

[参考文献]

[1]孙慈嘉，李嘉伟，凌兴宏.基于云计算的公交OD矩阵构建方法[J].江苏大学学报（自然科学版），2016（4）：456-461.

[2]陈锋，刘剑锋.基于IC卡数据的公交客流特征分析—以北京市为例[J].城市交通，2016（1）：51-58，64.

[3]BARRY J J，FREIMER R，SLAVIN H.Use of entry-only automatic fare collection data to estimate linked transit trips in New York City[J].Transportation Research Record，2009（6）：28-33.

[3]戴霄，陳学武，李文勇.公交IC卡信息处理的数据挖掘技术研究[J].交通与计算机，2006（24）：40-42.

[4]于勇，邓天民，肖裕民.一种新的公交乘客上车站点确定方法[J].重庆交通大学学报，2009（1）：121-125.

[5]周锐.基于IC卡数据的公交站点客流推算方法[D].北京：北京交通大学，2012.

[6]赵鹏.基于成都公交IC卡数据的乘客上下车站点推算方法研究[D].成都：西南交通大学，2012.

[7]徐文远，邓春瑶，刘宝义.基于公交IC卡数据的公交客流统计方法[J].中国公路学报，2013（5）：158-163.

[8]JIAWEI H，MICHELINE K，JIANPEI.数据挖掘概念与技术[M].北京：机械工业出版社，2012.

[9]谢雪莲，李兰友.基于云计算的并行K-means聚类算法研究[J].计算机测量与控制，2014（5）：1510-1512.

Abstract：By collecting the name of the bus line and the name of the site of the city of Nantong， on the basis of not relying on the GPS location data， the K-means clustering algorithm is used to analyze the passenger traffic time sequence and establish the theoretical model of the passenger boarding station， and record the number of passengers on the bus in the actual station， and then verify the feasibility of the proposed theory.

Key words：public transport; IC card; K-means; clustering