|
一种基于线路轨迹的公交站点聚类算法 王进* 作者简介：王进，（1987-），男，硕士，数据挖掘和网络技术及其应用。 E-mail: wjinjob@126.com （北京邮电大学网络技术研究院，北京 100876） 5 摘要：随着移动互联网和手机定位技术的发展，出现了越来越多的基于地理位置的服务(LBS), 地图数据和公共交通数据是这些应用和服务的数据基础，数据聚类在该领域有着广泛的应 用。目前在公交站点位置聚类问题上存在识别率低和无法区分上下行线路站点的问题，本文 提出一种基于线路轨迹的公交站点聚类算法。本算法充分挖掘有效信息，通过线路站点信息 进行筛选，并采用K-MEANS 聚类思想对行车方向信息进行聚类分析。通过将其应用在北京 10 公交数据集上，验证了本算法的有效性。 关键词：数据挖掘；聚类；公交站点网络；线路轨迹 中图分类号：TP391 A bus station clustering algorithm based on line trajectory 15 WANG Jin (Beijing University of Posts and Telecommunications, State Key Lab of Switching & Networking Technology, Beijing 100876) Abstract: With the development of mobile Internet and mobile phone positioning technology, there appears more and more location-based services(LBS), in which map and public 20 transportation data location analysis is the base.Data clustering is broad-spectrum in the area. On issues of the bus station position clustering,there is the problem of the low recognition rate and not distinguishing between the uplink and downlink.In this paper,we proposed a bus stations clustering algorithm based on line trajectory. In the algorithm, we fully exert effective information by screening the line station information, and use the K-MEANS clustering idea on the line 25 direction information. Through the experiment on the Beijing public transport data set, the effectiveness of this algorithm is verified. Keywords: Data mining; Clustering; Bus station network; Line trajectory 0 引言 30 随着智能手机的普及，移动互联网以及定位技术（如GPS、北斗卫星导航系统）的日 渐成熟，出现了大量基于地理位置信息的应用和服务（LBS）。在这些应用中，充分利用了 移动网络和地理位置信息，以及其他的传感器，使得其功能更贴近于生活，并且可以帮助我 们解决生活的许多问题，如查找路线、查找地点、查看本地天气预报等等。 地图服务和公共交通数据是这些应用和服务的基础，目前公交数据的获取主要是通过人 35 工采集和公交车随车设备采集，由于采集方法误差和定位技术本身存在误差，各个站点的位 置数据不可能完全一致，如何将实际位置等价的公交站点合并成为一个必须解决的问题，否 则直接对每条线路的站点进行操作既消耗了大量计算机资源也不利于友好的用户展示。蔡永 旺提出了一种适用于公交站点聚类的DBSCA 改进算法[1]，改进了DBSCA 算法[2]对输入参 数敏感的问题，通过基于密度的聚类分析对公交站点进行聚类合并。考虑到公交线路的特殊 40 性，若需要进一步对上下行线路的公交站点进行区分聚类，由于不同道路的宽窄级别不同， 单纯基于距离或密度进行聚类分析，无法有效准确地进行聚类划分，本文基于公交线路的轨 迹数据和相关属性（站名、所在线路），通过对其进行聚类分析，有效地解决了上下行公交 站点区分聚类的问题，并通过对北京市实际公交数据的实验，验证了算法的正确性和有效性。 1 聚类算法 45 当前，许多学者提出了各种数据聚类的算法，主要有如下几种：划分法、层次法、基于 密度的方法、基于网格的方法和基于模型的方法。其中，划分法给定一个有N 个元组或者 纪录组成的数据集，该方法将构造K 个分组，每一个分组就代表一个聚类，对于给定的K， 算法首先给出一个初始的分组方法，以后通过反复迭代的方法改变分组，使得每一次改进之 后的分组方案都较前一次好，而所谓好的标准就是：同一分组中的记录越近越好，而不同分 50 组中的纪录越远越好，使用这个基本思想的算法有：K-MEANS 算法[3]、CLARANS[4]算法。 层次法对给定的数据集进行层次似的分解，直到某种条件满足为止。具体又可分为“自底向 上”和“自顶向下”两种方案。例如在“自底向上”方案中，初始时每一个数据纪录都组成 一个单独的组，在接下来的迭代中，它把那些相互邻近的组合并成一个组，直到所有的记录 组成一个分组或者某个条件满足为止，代表算法有：BIRCH 算法[5]、CURE 算法[6]、 55 CHAMELEON 算法[7]等。基于密度的方法能够克服基于距离的算法只能发现“类圆形”的 聚类的缺点，该方法的指导思想是，只要一个区域中的点的密度大过某个阈值，就把它加到 与之相近的聚类中去，代表算法有：DBSCAN 算法[8]、DENCLUE 算法[9]等。基于网格的方 法采用一个多分辨率的网格数据结构，首先将数据空间划分成为有限个单元的网格结构,所 有的聚类操作都在网格上进行，网格中的 数据压缩质量就决定了算法的聚类质量，代表算 60 法有：STING 算法[10]、WAVE-CLUSTER 算法[11]。基于模型的方法给每一个聚类假定一个 模型，然后去寻找能够很好地满足这个模型的数据集，其潜在的假定就是：目标数据集是由 一系列的概率分布所决定的。通常有两种尝试方向：统计的方案和神经网络的方案。 2 基于线路轨迹的公交站点聚类算法 本文针对基于距离或密度无法有效区分上下行公交线路站点聚类划分的问题，提出一种 65 基于公交线路的轨迹数据的公交站点聚类算法。 2.1 问题描述 大部分公交线路都存在上下行，同一线路不同行车方向的公交站点往往分布于道路的两 侧，区分上下行公交线路站点的难点在于：（1）不同站点所在的道路级别不同，其对应的 参数如距离、密度等都有所不同，仅通过基于距离和密度的聚类分析无法完成该工作；（2） 70 并非所有站点都存在上下行站点，部分站点只在道路的一侧存在，具有不对称性。图1 所示 为北京市明光桥北上下行线路车站，部分线路仅在道路东侧存在站点。 图1 上下行公交站点示例 Fig. 1 Example of bus station with different directions 75 2.2 算法思想 目前公交数据信息主要是通过各条线路沿途进行采集而获取，其中包括了线路信息、站 点信息和线路轨迹拐点信息。由于仅仅通过基于距离和密度的聚类分析无法对上下行公交站 点进行聚类分析，我们可以利用相关的公交线路和站点信息来增加算法的有效输入，首先通 80 过站点名称得到同名站点结果集合，然后通过查找该结果集中各站点所在线路轨迹中的前后 拐点信息，计算得到其对应的行车方向角，并根据各站点对应的线路名称集合是否存在交集 确定该站点是否存在上下行属性，若存在上下行公交站点则聚类参数k 为2，否则k 为1， 最后根据聚类参数k，采用经典的K-MEANS 算法思想，对该集合中各站点的行车方向角进 行聚类分析，最终得到区分上下行公交线路站点的聚类结果。 85 2.3 算法描述 输入：站点信息表stop、线路轨迹特征点表line_coordinate 输出：区分上下行线路的公交站点表 算法流程： For stop 表中一条记录 do 根据stopName 在stop 表查询，得到结果集result For 结果集result 中一条记录 do 在line_coordinate 表中查询对应站点的前后拐点经纬度计算行车方位角 Endfor For t=0,t<result.size do //确定该站点是否存在上下行属性 If (temp_id[t],temp[t+1]相邻且线路名相同) 将相邻线路名分别计入direction1[],direction2[] 设置angle 设为初始聚类中心 else 将线路名计入single[],将angle 计入single_angle[] //单行站点 Endfor If (direction1[]大小不为0) For single[]中有数值 do 将single_angle 与2 个聚类中心direction1[],direction2[]比较，计算相 似度，将其分配给与其最近似的聚类，加入相应数组，并更新angle Endfor else 依据上面方法区分single 中lid 的2 个方向 输出该站点的区分上下行聚类结果 取下一条记录 Endfor 3 实验验证与结果 90 本文使用C++语言实现该算法，并以存储于MySQL 数据库的2012 年北京市所有公交 和地铁数据为实验对象，通过上述算法对北京市1827 条公交线路、52744 个公交站点进行 实验，区分上下行后，共有15403 个站点，图2 为经过该算法聚类后不同出入度的站点分布 饼图。图3、图4 为北京邮电大学附近公交站点聚类前后效果对比，通过该算法聚类后，明 光桥北、明光桥南、明光桥东、蓟门桥东、蓟门桥西等车站上下行线路区分聚类符合实际， 95 算法有效且准确。 图2 站点出入度分布 Fig. 2 Degree distribution of bus stations 100 图3 聚类前公交站点示例 Fig. 3 Example of bus stations before clustering 图4 聚类后公交站点示例 105 Fig. 4 Example of bus stations after clustering 4 结论 本文总结了目前主流的聚类算法，通过分析上下行公交线路站点聚类的特点，针对基于 距离或密度无法有效进行区分上下行公交线路站点聚类划分的问题，提出一种基于公交线路 110 的轨迹数据的公交站点聚类算法。该算法有效利用公交线路数据中的信息对上下行线路公交 站点进行聚类，保证了聚类的高正确性。 由于本算法依赖于公交线路轨迹拐点的采集和线路的行车方向，若存在上下行线路方向 角非常近似的情况，将不能进行准确的聚类，作者下一步的工作是克服这种特殊情况，进一 步提高聚类结果的准确性。 115 [参考文献] (References) [1] 蔡永旺，杨炳儒. 适用于公交站点聚类的DBSCAN 改进算法[J]. 计算机工程，2008，10：190-192. [2] Lian Duana, Lida Xub, Feng Guoc, Jun Leea, Baopin Yana. A local-density based spatial clustering algorithm with noise[J]. Information Systems, 2007, 32(7): 978-986. 120 [3] Rousseeuw, Peter.J. Finding Groups in Data: An Introduction to Cluster Analysis[M]. Witerwoof Inc, 1990. [4] Ng, R.T., Jiawei Han. CLARANS: a method for clustering objects for spatial data mining[J]. IEEE Transactions on Knowledge and Data Engineering, 2002, 14(5):1003-1016. [5] Tian Zhang, Raghu Ramakrishnan, Miron Livny. BIRCH: an efficient data clustering method for very large databases[J]. ACM SIGMOD Record, 1996, 25(2): 103-114. 125 [6] Sudipto Guha, Rajeev Rastogi, Kyuseok Shim. CURE: an efficient clustering algorithm for large databases[J]. ACM SIGMOD Record, 1998, 27(2): 73-84. [7] Karypis, G., Eui-Hong Han, Kumar, V. Chameleon: hierarchical clustering using dynamic modeling[J]. 学术论文网Tag：代写硕士论文 代写论文 代写代发论文 代发论文 |
