摘 要：提出一种基于改进粒子群算法的聚类算法来实现城市出行热点挖掘。首先对轨迹数据进行清洗、标准化、分割等预处理；其次采用改进粒子群的聚类算法分析热点区域；最后以这些热点作为网络节点，以道路作为连接边建立网络模型，从节点和连接边出发，实现出行热点可视化。算法的全局寻优能力和分布式随机搜索特性能够解决传统聚类算法易陷入局部最优的问题，算法引入了压缩因子，能通过配置最优参数控制粒子群更新速度，从而有效改进粒子群算法准确率和全局收敛性。
关键词：轨迹数据；压缩因子；改进粒子群算法；聚类算法；热点挖掘
中图分类号：TP319 文献标识码：A 文章编号：2096-4706（2024）15-0047-04
Method of Extracting Travel Hotspots Based on Improved Particle Swarm Optimization Cluster Algorithm
CHEN Ying， WU Mingzhu
（Information Technology and Engineering Department of Guangzhou Institute of Technology， Guangzhou 510075， China）
Abstract： This paper proposes a clustering algorithm based on improved Particle Swarm Optimization to achieve urban travel hotspot mining. Firstly， it preprocesses the trajectory data through cleaning， standardization， and segmentation. Then， an improved Particle Swarm Optimization clustering algorithm is used to analyze the hotspot area. Finally， it takes the hotspots as network nodes and takes the roads as connecting edges to establish network model. Starting from the nodes and connecting edges， it achieves visualization of travel hotspots. The global optimization ability and distributed random search characteristics of the algorithm can solve the problem of traditional clustering algorithms easily falling into local optima. The algorithm introduces a compression factor and can control the update speed of the particle swarm by configuring the optimal parameters， so as to effectively improve the accuracy and global convergence of the Particle Swarm Optimization algorithm.
Keywords： trajectory data; compressibility factor; improved Particle Swarm Optimization algorithm; cluster algorithm; hotspot mining
0 引 言
移动定位技术和无线通信技术的快速发展，为城市交通领域积累了大量的移动轨迹数据，这些数据是智慧城市发展的重要研究对象之一，具有重要的社会和经济价值。海量轨迹数据在实时记录城市交通状况的同时，不仅在交通预测、位置服务、推荐系统等各个应用领域有着重要作用，也反映了城市居民出行规律和城市空间结构等信息。出行热点区域的时空分布及动态演化，直观展示了居民在城市的流动性和城市区域的功能分布[1]。因此，基于城市轨迹数据挖掘热点区域分析居民出行行为，一直受到众多学者的关注，成为数据挖掘领域的重要研究方向，通过对移动对象轨迹数据及相关信息的研究，我们可以更好地分析移动对象运动的特点和规律，进而发现移动行为模式[2]。
1 研究现状
随着物联网技术、大数据技术、通信技术、人工智能等为代表的新一代技术的发展和完善，利用地理时空大数据探测城市热点并探讨其应用已成为城市热点研究的主流趋势。
Mou等[3]从车辆轨迹数据中提取“起点—终点”数据进行聚类，提出一种基于网格密度混合的聚类方法，旨在挖掘出行行为与城市功能区的联系。Qin等[4]基于时空数据场理论，将聚类分析方法引入到出租车轨迹数据中，以识别居民出行的持续热点区和非持续热点区。Yuan等[5]提出一种基于城市活动人群潜在移动轨迹的城市功能区识别方法。周勍等[6]基于出租车轨迹数据，提出利用数据场势值域值方法探测城市热点区域，并对比分析了节假日和非节假日的差异。胡庆武等[7]使用社交网络位置签到数据，提出一种城市商圈挖掘方法，但该方法缺乏对各商圈间联系的深入分析。李文明等[8-9]通过对交通轨迹数据建立时空索引结构和反向索引结构，完成数据分析与挖掘，实现预测出行时间及路线推荐。陈凯等[10]提出一种基于城市交通监控数据的出行位置范围推理方法，将城市交通监控数据与上下文兴趣点数据相结合，来探索挖掘车辆的移动模式。
出行热点区域的提取通常是基于轨迹数据中的关键轨迹点进行聚类分析。聚类算法的工作原理是先对预处理过的原始数据集进行初始划分，然后通过迭代的方法不断更新类簇中心和类簇对象，直至满足聚类条件时，停止迭代。尽管该算法原理简洁且时间效率高，但其聚类结果受初始点选择影响较大，合理选择初始聚类数目及类中心较为困难，容易导致结果的不稳定性。此外，一般聚类算法难以有效识别噪声点，不适合处理非凸形状和密度差异较大的数据集。
2 基于改进粒子群聚类的出行热点提取方法
2.1 算法主要思想
针对上述现有技术的缺点，本算法提出一种基于改进粒子群算法的聚类算法，以实现城市出行热点的有效挖掘。首先，对交通轨迹数据进行清洗、标准化、分割等预处理。然后，采用改进粒子群的聚类算法分析热点区域，并以这些热点作为网络节点，以道路作为连接边建立网络模型，实现出行热点可视化。算法流程如图1所示。
本算法提出的改进粒子群聚类算法，通过全局寻优能力和分布式随机搜索特性，有效解决了传统聚类算法易陷入局部最优问题。算法中引入了压缩因子，能通过配置最优参数控制粒子群更新速度，有效改进粒子群算法准确率和全局收敛性。
2.2 算法具体步骤
2.2.1 交通轨迹数据预处理
1）数据清洗。本算法采用上海2020年7月3 000辆出租车的轨迹数据作为研究基础。原始轨迹数据可能包含缺失值、异常值或错误数据。在对数据进行聚类分析之前，需要对数据进行清洗，包括去除缺失值、异常值、重复值，纠正可能存在的错误数据，确保数据的准确性和完整性，减少由错误数据引起的误导和偏差，以提高聚类质量和可解释性。
对采样数据中的关键数据有缺失的情况下，应该将记录删KpZiynsgZ2l7WV/JOK6mfchOYoglnaT5AzIsMuzX7XM=除。GPS在采集出租车轨迹数据的过程中，可能因为信号不良、设备故障或数据传输丢失数据包等问题，导致数据没有采集完整，故而在原始轨迹数据中记录为空值。在数据分析前，需进行剔除。
对采样数据中存在异常值的情况，应做相应处理。如经纬度缺失部分位置信息时，可认为是运动对象在移动过程中，仪器未检测到位置数据的异常。可通过线性插值的方法，即根据前后两个非缺失数据拟合一个线性函数对缺失数据进行预测，补充缺失数据。如轨迹记录每个数据字段都有有效的值域范围，不在值域范围的数据应视为异常数据进行处理。如速度字段，速度的单位是千米每小时，值域为[0，160]，将采样记录中速度不在[0，160]范围内的数据均作为异常数据加以剔除。
对于采样数据中的大量重复数据，应该予以删除。GPS设备每隔一段时间对出租车信息进行一次采样，如果出租车当日处于停运静止状态，整个轨迹文件除了时间字段，其他的位置、速度、角度等数据完全相同，这种大量重复数据会对聚类、热点提取等分析造成不良影响，所以在进行相应分析之前，应予删除。同理，某个整个轨迹文件有行车轨迹变化，但其中有一大段时间内，位置信息无任何变化，此时出租车应该处于临时停车、司机休息或者进餐状态，这种重复数据也会对聚类、热点等分析造成不良影响，所以在进行相应分析之前，应予去除。
2）数据标准化。标准化的目的是消除数据的度量单位的影响，使不同单位或量级的指标能够进行比较和加权。对轨迹数据进行标准化处理，使得属性的不同度量具有相同的尺度或分布，包括经度与纬度数据标准化、时间标准化。如速度通常以千米/小时、米/秒等表示，因此需要进行数据标准化，标准化后的速度数据具有统一的标准，才能作为模型输入的训练数据。
3）轨迹分割。根据特定的轨迹标识对轨迹进行分割，以降低数据处理的复杂性，提高分析精度和增强适应性。轨迹分割可以基于车辆编号、时间段、车辆状态变化等进行。按车辆编号进行分割，形成车辆的轨迹数据集；按时间段进行分割，形成时间分布轨迹数据集；按车辆状态变化进行分割，形成空车数据集与载人数据集。
2.2.2 基于改进粒子群聚类算法的出行热点提取
经典粒子群聚类算法（Particle Swarm Optimiz-ation， PSO）通过模拟鸟群中的个体通过协作和信息共享来寻找食物的过程，将每个鸟类比为“粒子”，每个粒子都代表问题的一个潜在解。PSO算法通过搜索粒子跟踪“个体最优解”和“全局最优解”来更新自己的位置和速度，通过不断地更新粒子的速度和位置，在搜索空间中寻找最优的聚类中心点，从而实现数据的聚类。PSO算法原理简单、易于实现，但容易陷入局部最优解，导致收敛精度低和不稳定性。因此，本算法基于经典粒子群聚类算法，在计算粒子速度时增加了压缩因子进行算法改进。
本算法将轨迹数据随机划分成若干个互不相交的簇，分别随机选择1个数据点作为每个簇的初始聚类中心。通过计算每个轨迹数据点到各簇中心的距离，根据最近邻原则重新分配到距离它最近的簇中心。然后对新簇中的数据点做均值优化，重新计算得到新生成簇的聚类中心。
比较新旧聚类中心的距离，若距离在阈值内，则认为算法收敛并输出结果；否则，继续根据新的聚类中心重新迭代，直至收敛。
聚类中心点移动的下一位置速度公式为：
（1）
聚类中心点移动的下一位置公式为：
=xid+vid （2）
在本算法中，聚类中心点的维度包括经度、纬度、时刻三个维度。其中，表示中心点i在第d个维度上的下一个速度，xid表示中心点i在第d个维度上当前的位置，w表示惯性权重，pid表示中心点i当前搜索到的最优解，pgd表示整个中心点群当前的最优解，c1和c2表示加速系数，调节pid与pgd的相对重要性，rand（）为值在[0，1]之间的随机数，增加一定的随机扰动，以避免算法陷入局部最优解。w惯性权重的取值较大时，有利于在更大的范围内进行搜索，而较小的w能保证最终收敛到最优位置。所以本算法将w设置为由0.9向0.4线性减小的变化取值，从而能够使算法一开始全局搜索而后精确收敛，达到较优的效果。对于加速系数c1和c2，c1影响本身历史信息对于聚类中心点运动的轨迹，c2影响其他中心点的历史信息对中心点运动的轨迹，都不宜过大，本算法选取c1、c2为2.05。
对比经典粒子群算法，本算法通过压缩因子φ对惯性权重和加速系数的控制，使算法能够很好地在整体搜索和局部收敛之间达到均衡，防止加速系数c1或c2一方增长过大，同时也保证速度增长不致过大，从而在不增加时间成本的基础上，使聚类算法在搜索全局性和收敛性上得到提高。为了算法顺利求解，ρ必须大于4。
算法流程图如图2所示。
2.2.3 聚类中心个数K的确定
聚类算法聚类中心的个数直接影响聚类结果的质量和可解释性。在确定聚类中心个数时，预设聚类中心个数为5至30，从中选择最佳的K值。每次聚类后，通过计算误差平方和（Sum of Squared Errors， SSE）来评估聚类效果，SSE值越小，表示聚类效果越好，即聚类内部的样本点更加紧密，聚类间的差异较小。通过观察每次聚类的K值和SSE值的关系图，我们确定了最佳的K值为20时，SSE值达到最佳。
3 可视化模块
出行热点提取算法可设置聚类中心集合元素个数，本算法将数据划分成20个簇，并获取每个聚类中心点的经纬度坐标。采用Python第三方库Folium提供的接口，通过多图层绘制路线段和聚类中心，配合地图实现可视化。
首先创建一个地图对象并设置中心位置的经纬度。然后创建一个点图层和一个线路图层，将所有聚类点添加到点图层，将相关路线段添加到线路图层。最后，将点图层和线路图层通过add_to方法添加到地图对象中，并显示地图。例如将车辆的轨迹数据映射到地图上，可以绘制出一辆车一天的行车路线，如图3所示。
提取数据的时间属性，按不同的时间粒度（一小时或半小时），基于改进的粒子群聚类算法对居民出行热点挖掘，分析早高峰和晚高峰的时间区间，以及不同时间区间车辆行驶的热点变化。图4为上午8：00轨迹数据聚类结果，图5为凌晨3：00轨迹数据聚类结果。
提取全天车辆轨迹的起点终点数据，基于改进的粒子群聚类算法对居民出行进行热点挖掘，结果如图6所示。
4 结 论
本算法首先对交通轨迹数据进行清洗处理，随后深入研究基于清洗后轨迹数据的城市出行热点提取算法，通过压缩因子φ对聚类算法惯性权重和加速系数进行控制。在保证时间开销不提高的基础上，使得算法在搜索全局性和收敛性上得到提高。此外，算法还实现了多图层绘制功能，能够直观地展示路线段和聚类中心，实现对不同时间区间的出行热点提取结果的可视化呈现。
随着大数据和人工智能技术的不断发展，城市出行热点提取将变得更加智能和精准，如利用深度学习算法对出行数据进行挖掘和分析。在出行热点的应用上，可以预测出行趋势、实施对城市交通的实时监控和调度等。这表明，城市出行热点的提取具有广阔的应用前景和重要的社会价值。
参考文献：
[1] 颜亮.基于出租车载客数据的纽约市交通热点分析与挖掘 [D].青岛：山东科技大学，2020.
[2] 彭定永.基于轨迹数据的城市居民出行热点与出行模式研究 [D].赣州：江西理工大学，2021.
[3] MOU N，LI J，ZHANG L，et al. Spatio-Temporal Characteristics of Resident Trip Based on Poi and OD Data of Float Car in Beijing [C]//ISPRS Geospatial Week.Wuhan：ISPRS，2017，XLII-2/W7：99-105.
[4] QIN K，ZHOU Q，WU T，et al. Hotspots Detection from Trajectory Data Based on Spatiotemporal Data Field Clustering [C]//ISPRS Geospatial Week.Wuhan：ISPRS，XLII-2/W7：1319-1325.
[5] YUAN N J，ZHENG Y，XIE X，et al. Discovering Urban Functional Zones Using Latent Activity Trajectories [J].IEEE Transactions on Knowledge and Data Engineering，2015，27（3）：712-725.
[6] 周勍，秦昆，陈一祥，等.基于数据场的出租车轨迹热点区域探测方法 [J].地理与地理信息科学，2016，32（6）：51-56+127.
[7] 胡庆武，王明，李清泉.利用位置签到数据探索城市热点与商圈 [J].测绘学报，2014，43（3）：314-321.
[8] 李文明.基于交通监控大数据的路线推荐与行程时间评估 [D].烟台：烟台大学，2021.
[9] 李文明，刘芳，吕鹏，等.基于城市交通监控大数据的行程时间估计 [J].大数据，2021，7（1）：107-123.
[10] 陈凯，于彦伟，赵金东，等.基于城市交通监控大数据的工作位置推理方法 [J].计算机应用，2021，41（1）：177-184.
作者简介：陈瑛（1979—），女，汉族，广东揭阳人，副教授，本科，主要研究方向：信息化技术、新型数据管理技术及其在学情数据、交通数据中的理论与应用。
