利用票务数据进行交通站点时空聚类：降维技术与元启发式优化方法的整合

《Big Data Research》：Integration of dimensionality reduction and metaheuristic optimization for spatiotemporal clustering of transit stops using ticketing data

　　尼什塔·拉瓦特|阿米特·阿加瓦尔
印度北方邦哈里德瓦尔鲁尔基印度理工学院数据科学与人工智能梅赫塔家族学校，邮编247667

摘要
本研究提出了一种用于时空数据的集成聚类框架，该框架考虑了诸如占用率、空间坐标以及时间使用模式等多种特征，以识别功能上相似的公交站点群。该框架将降维技术、聚类算法以及用于超参数调整的优化算法相结合。为确保所形成聚类的空间合理性，研究采用了莫兰指数作为目标函数。该方法在公共公交网络的电子票务系统数据上进行测试，将176个公交站点分为8个不同的群体，每个群体都呈现出独特的时间和使用方向特征。实验结果表明，统一流形近似与投影结合鲸鱼优化算法以及亲和传播算法能够有效捕捉复杂的空间模式，而在数据稀疏或不规则的情况下，统一流形近似与鲸鱼优化算法结合高斯密度层次聚类算法的表现更为优异。从关键性能指标来看，统一流形近似与鲸鱼优化算法在结构参数和空间一致性方面表现最佳，而统一流形近似与贝叶斯优化算法则在计算效率上更具优势，同时关键性能指标略有下降。这体现了聚类质量与运行效率之间的明显权衡。与传统聚类方法、基于深度学习的方法（如变分自编码器）以及利用贝叶斯技术的优化方法相比，所提出的框架在空间连贯性和可解释性方面表现更优。这些研究结果凸显了该框架在可扩展分析时空网络方面的潜力。

引言
随着公共交通领域中电子票务和智能卡技术的广泛应用，自动收费系统为运营方提供了宝贵的数据支持。然而，要充分利用这些数据，就需要进行多种数据聚合处理，从而实现服务的个性化优化。通常，针对包含占用率、路线、时段及站点等特征的这类数据集，需要一种能够根据数据间的相似性将其分类为指定数量群体的方法。虽然聚类通常作为一种无监督技术被使用（即在没有先验信息的情况下确定数据集中的相似结构），但也存在有监督聚类的例子，其中已知标记数据被用来指导聚类过程，为未知数据确定标签。聚类算法需增强同一群体内数据项的相似性，同时增加不同群体间数据项的差异性。这一技术广泛应用于交通、能源系统、网络、农业及医疗保健等领域[1]、[2]、[3]。在公共交通领域，聚类技术可用于对站点进行分类，使得每个群体内的相邻站点在考虑时空信息后的客流量模式具有高度相似性[4]。在大多数应用中，K均值、基于密度的空间聚类算法、高斯密度层次聚类算法以及亲和传播算法已被证明具有较好的效果[5]、[6]、[7]、[8]。然而，对于没有已知标签的数据集，这些传统聚类方法可能因群体间存在重叠而不够适用。这种复杂性往往需要更先进的聚类技术，能够在无需事先知道群体数量的情况下揭示数据结构。例如，K均值需要事先确定群体数量，而这并非总能明确知晓。此外，随着数据维度增加以及数据变得稀疏，传统聚类算法中数据点之间的距离意义逐渐减弱。面对这些挑战，就需要采用能够从多维稀疏数据中获取更清晰信息的聚类技术。为此，降维技术在其中起着关键作用，因为它能将数据降至低维空间，从而使群体更加清晰可辨[9]。在现实世界数据中，这些技术还有助于过滤噪声，从而在可视化后的低维空间中形成更清晰、更明确的群体边界。

最常用的降维技术包括统一流形近似与投影[10]、t分布随机邻域嵌入[11]、[12]以及主成分分析[13]。作为深度聚类的一部分，变分自编码器也通过将特征映射到潜在空间来实现降维[14]、[15]、[16]。尤其是统一流形近似，在将数据映射到低维空间时能够较好地保留数据结构，从而提升后续聚类的效果[17]。不过，这类方法面临的一个重大挑战是，超参数值的搜索空间极为广阔，这就引发了探索与利用之间的经典矛盾[18]。统一流形近似的性能取决于这些超参数，它们会显著影响最终的嵌入结果，进而影响聚类算法的输入。当前的研究趋势是通过将元启发式优化技术与聚类算法相结合来寻找最优参数。像基于群体智能的算法这类元启发式方法，能够更高效地在庞大的参数空间中导航，从而精细调整聚类过程。最近，类似元启发式的粒子群优化技术也被用于选择机器学习算法的参数[19]。同样，贝叶斯优化也是另一种高效的参数优化技术[20]、[21]。

这些优化技术中常用的目标函数包括最大化轮廓系数或最小化平方误差之和[22]。但在本研究中，为了考虑空间自相关性，采用了莫兰指数[23]、[24]，以确保在时空公共交通数据中聚类结果合理形成。莫兰指数已被用于评估高度时空相关的数据的空间分散程度[25]。对于这类数据，诸如K均值或亲和传播之类的无约束聚类方法往往无法得到最优结果，因为由于公交站点彼此邻近，总会存在一定程度的空间相关性，这意味着地理位置相近的站点往往具有相似的特征。因此，这些传统方法生成的群体可能在地理上并不一致，这对于那些要求群体具有相似模式的公共交通应用来说是不够实用的。本研究采用莫兰指数作为目标函数，以保持空间自相关性，这对交通数据而言至关重要。如表7所示，那些在轮廓系数方面得分较高的聚类方法（例如基础版的亲和传播算法）并不一定具有较高的莫兰指数值，这说明这些指标可能忽略了空间结构。

本研究提出了一种系统化的聚类框架，通过三步聚类流程整合空间和时间信息：首先，使用统一流形近似对选定特征进行降维，然后对降维后的变量应用不同的聚类算法，并对这些算法进行测试；其次，基于莫兰指数构建目标函数，以突出聚类过程中空间自相关性的影响；最后，利用元启发式技术确定统一流形近似和聚类算法的超参数，从而优化目标函数。该框架既应用于合成数据集，也应用于真实的公共交通数据。总体而言，本研究的主要贡献如下：
• 一种混合聚类框架，它整合了降维技术（统一流形近似）、多种聚类算法（K均值、高斯密度层次聚类算法、亲和传播算法）以及元启发式优化技术，能够自动确定时空交通数据中的最优群体配置。
• 采用鲸鱼优化算法进行元启发式驱动的超参数调优，从而同时优化统一流形近似和聚类算法的参数。这种方法通过优化算法调节探索与利用之间的平衡，确保这些降维和聚类算法得到精确校准，从而实现最佳性能。
• 采用莫兰指数作为目标函数，将空间自相关性明确纳入聚类评估之中，弥补了以往研究主要依赖轮廓系数等几何度量指标的不足，有助于把握空间自相关性对真实数据集的影响。
• 实现双向公交线路分析，考虑到公交线路上下行方向的差异，本研究将每条线路的上下行方向的票务数据一起进行分析，据作者所知，此前尚未有人这样做，而这种方法在揭示不同的使用模式方面非常有效。此外，该方法还在合成数据集和真实数据集上都进行了验证，证明了其在不同类型数据中的稳健性和适应性。

第2节回顾了相关文献。第3节介绍了所提出聚类框架的各个步骤。第4节展示了合成数据集和真实数据集以及特征准备过程。第5节通过各种关键性能指标评估，确定最优算法。第6节对结果及图表进行分析，探讨其对真实数据聚类类型的影响和意义。第7节对整个研究进行总结。

相关研究
聚类的多功能性使其成为揭示数据集中内在模式和结构的有效工具。然而，传统聚类技术难以直接应用于高维数据。这是因为随着维度增加，固定数量的样本会变得越来越稀疏，而那些基于距离或相似性的聚类技术也会受到影响。为总结现有研究中的相关方法，表1列出了各类相关研究。

方法论
所提出的混合聚类算法的伪代码见算法1。该算法整合了降维技术（统一流形近似）和元启发式优化技术（鲸鱼优化算法），并结合了不同的聚类方法。这些内容将在后续章节中详细说明。为保持一致性，本研究采用以下符号规则：常数用斜体大写字母表示，如N=5；随机变量用X表示。

数据集与特征准备
为展示所提出聚类框架的潜力和可行性，首先将其应用于知名的UCI数据集和合成数据集（见第4.1节），随后再应用于真实数据集（见第4.2节）。前者便于进行基准测试，后者则体现了该方法在真实应用中的适用性及其在不同领域的迁移能力。

结果
在本节中，使用了来自UCI和合成数据集的六个数据集，以及来自公共交通自动收费系统的时空电子票务数据，来评估所提算法的有效性和性能。

讨论
本研究提出了一种混合聚类框架，该框架将统一流形近似作为降维技术，鲸鱼优化算法用于超参数调优。研究开发了多种聚类算法，并对其性能进行了比较。根据图5和图6的分析结果，可以得出这样的结论：不同的聚类方法根据数据特性各有优缺点。在数据复杂且结构化程度高的情况下，统一流形近似结合鲸鱼优化算法和亲和传播算法表现出较强的性能。

结论与未来工作
所提出的框架成功解决了传统聚类方法在高维且含噪声的时空数据集中的局限性。那些将降维技术（如统一流形近似）作为预处理步骤的聚类方法，在超参数确定方面往往存在不足。本文提出的一种混合聚类算法具备处理时空数据的能力。本研究的主要贡献包括：

CRediT作者贡献声明
尼什塔·拉瓦特：撰写——初稿、可视化、方法论、数据整理、概念设计、撰写——审阅与编辑。阿米特·阿加瓦尔：撰写——初稿、指导、方法论、概念设计、数据整理、可视化、撰写——审阅与编辑。

利益冲突声明
作者声明不存在任何可能影响本文研究的已知财务利益或个人关系。