康瑞部落

随着定位技术的进步和城市地理信息的深入挖掘，越来越多的时空数据被采集，其中聚类是对大规模数据处理的一项基础操作。然而，大多数现有的算法只关注空间信息，而往往忽略了许多现实应用中至关重要的时间属性。本次为大家带来重庆大学时空实验室在数据库领域顶级期刊TKDE 2025发表的文章《DiST: Efficient Distributed Spatio-Temporal Clustering with Automatic Parameter Optimization》。

一. 背景

图1 疫情防控案例

尽管如此，要在大规模数据集上高效实现分布式时空聚类仍面临诸多挑战。挑战1：数据分布不均衡。时空数据在空间维度上天然存在不均衡性，引入时间维度后不仅使聚类设计更复杂，还进一步加剧了负载不均衡，导致难以实现均匀划分。挑战2：通信开销高。分布式存储环境下，同一聚类内的数据点可能分布在不同节点，频繁的数据传输带来显著的通信负担。挑战3：参数空间庞大。聚类性能高度依赖于参数选择，包括算法参数与分布式环境参数。在巨大的参数空间中为每个任务手动调优几乎不可行。

针对上述问题，本文提出DiST——首个基于 Spark 的自动调参分布式时空聚类方法。DiST 由参数调优与分布式聚类两大核心模块组成：前者能够结合系统资源与任务特征，自动配置聚类与环境参数，以最大化性能；后者通过数据划分—局部聚类—全局合并三个阶段，有效整合时空属性，降低通信开销并缓解数据不均衡问题。具体而言，数据划分阶段引入基于图的划分策略以聚合强连接区域；局部聚类阶段在各分区内独立执行时空聚类；最终全局合并阶段整合局部结果，生成完整的全局聚类。

二. 方法介绍

2.1 总体框架

如图2所示，本文提出的DiST 框架主要由两个核心模块构成：分布式聚类与参数调优。前者聚焦于时空数据的高效聚类过程，后者则面向性能优化与参数自动配置。

图2 整体框架

l分布式聚类

该模块包括三个阶段：

(1) 数据划分（Data Partitioning）：首先，将原始数据集D划分为多个时空分区P = P₁∪P₂∪...∪P_k。划分目标是：尽可能将属于同一聚类的数据点分配到同一个分区中；保持各分区的数据量大致均衡，以实现负载均衡。为此，我们设计了一种基于图的划分策略，包括图构建、图划分、数据点重新分配三个步骤。

(2) 局部聚类（Local Clustering）：在数据划分完成后，每个分区将独立执行时空聚类算法。我们采用了一种基于密度的时空聚类算法（Density-Based ST-Clustering），专门针对分区内的数据特性进行处理。

(3) 全局合并（Global Merging）：最后，将各个分区的局部聚类结果整合为全局聚类结果。该阶段包括：对聚类标签进行映射与合并；对跨分区的数据点重新分配标签，以保证聚类结果的一致性。

l参数调优

参数调优模块的目标是实现性能最优。具体而言，它会基于历史数据与离线训练模型，结合用户提交的任务需求、指定的聚类参数、数据集的特征属性、系统的可用计算资源等从而自动选择最优的参数组合，提高整体执行效率。

2.2 分布式聚类

分布式聚类框架包含三个核心步骤：数据分区、本地聚类和全局合并，如图3 所示。

图3 分布式时空聚类

2.2.1 数据划分

在分布式时空聚类中，数据划分是关键的第一步。它通过将大规模数据集切分为多个更小的分区，使各个计算节点仅需处理自己负责的部分，从而提升整体效率。一个理想的划分策略需要同时满足以下两点：

l负载均衡：保证各个分区的数据量大致相当，避免节点间的计算不均衡，提高资源利用率；

l簇内聚合性：尽量把可能属于同一聚类的数据点分配到同一个分区，以减少跨分区通信和数据传输开销。

现有方法大多只关注负载均衡，却忽视了簇内聚合性；而如果要兼顾聚合性，往往需要计算全局范围内的点对距离，代价极高。为此，本文提出了一种基于图的时空数据划分方法，能够在保持负载均衡的同时，兼顾簇内聚合性，并有效降低计算复杂度。

核心思路：我们将时空域划分为多个子空间，并将这些子空间映射为图中的节点，从而将数据划分问题转化为图划分问题。其中：每个节点代表一个时空立方体；节点之间的边表示空间或时间上的相邻关系；节点的点数代表计算开销，边的权重代表聚合强度。

划分目标：在保证各分区规模大致相当的同时，尽量减少跨分区的连接，从而同时实现负载均衡与簇内聚合性。

整个划分过程包括三个步骤：

(1) 图构建（Graph Building）：首先从原始数据集中抽取子集，用于近似整体分布，然后将子集划分为多个立方体（由预设参数控制空间与时间粒度）。之后，每个立方体作为图的节点，若两个立方体在时空上足够接近，则在节点间建立边，边权重由立方体内点数决定，以刻画连接强度。

(2) 图划分（Graph Partitioning）：这一步在加权图上执行划分，要求保持不同分区内的点数尽量均衡同时最小化跨分区的边权重，保证相关立方体被划分到同一分区。我们采用k-KL算法，通过迭代优化分区结果，实现负载均衡与簇内聚合性之间的平衡。最终得到由多个立方体组成的时空分区。

(3) 重新分配（Reassignment）：得到初步分区后，需要将全部时空数据映射到对应的分区。

通过上述步骤，数据被切分为既均衡又具聚合性的多个时空分区，为后续的局部聚类和全局合并奠定了基础。 

2.2.2 局部聚类

在完成数据划分后，每个分区会独立执行局部聚类操作。我们将数据按照分区标识进行分组，然后在各分组内应用DBSCAN聚类算法。我们在处理的过程中同时考虑空间距离与时间距离，从而能够更准确地捕捉到具有实际意义的聚类模式，具体过程如算法1所示。

算法1 时空聚类

算法初始为所有点分配默认标签，并建立聚类计数器。接下来进行邻域查询，针对每个未标记的数据点，计算其在空间半径和时间窗口内的邻居集合。若邻居数不少于目标阈值，则该点被标记为核心点，并创建新的聚类。随后，将其邻居依次纳入聚类中。若邻居此前被标记为噪声，则更新其标签；若邻居未被分配任何聚类，则继续扩展其邻居集合，实现聚类的递归扩展。重复上述过程，直到所有数据点都被分配至某个聚类或标记为噪声点。

通过这种方式，每个分区都能在本地完成时空聚类，既保证了计算的并行性，又能够在局部范围内充分利用空间与时间特征。最终，这些局部聚类结果将在后续的全局合并阶段进一步整合为完整的聚类结构。

2.2.3 全局合并

在局部聚类完成后，还需将多个分区的结果整合为统一的全局聚类。由于相邻分区在边界处可能共享部分点，不同分区中独计算得到的聚簇有可能实际属于同一个全局聚簇，因此必须进行合并与统一标识。

每个分区在局部聚类阶段都会生成独立的聚类标签。在全局合并阶段，需要建立合并映射，将这些局部标签映射为统一的全局标签。例如，当两个分区在外部立方体区域存在重叠时，它们形成的局部聚类可能实际是同一个全局聚类，因此需要通过合并映射统一标识。

我们定义了一个重要原则：若两个聚类在交集区域共享至少一个核心点或边界点，则它们可被判定为同一聚类，这种点被称为合并点（merge point），详细说明见原论文Lemma 1。合并点的存在，保证了跨分区聚类的正确连接。

图4给出了两种典型场景：1）在第一种场景中，分区1的聚类LC₁和分区2的聚类 LC₂通过共享的边界点p₁建立联系，从而被合并为一个全局聚类GC₁；2）在第二种场景中，分区2的LC₃与分区3的LC₄共享核心点p₂，因此可直接合并为GC₂。

图4 全局合并

在完成合并映射后，需要对所有数据点的聚类标签进行更新，对于处于交集区域的点，直接用全局标签替换局部标签。对于跨分区的点，如果它在一个分区中是边界点，而在另一个分区中是核心点，则在最终结果中更新为核心点，以确保全局一致性。

2.3 自动参数调优

2.3.1 调优过程

在大规模分布式聚类任务中，系统的运行效率不仅依赖于算法自身的超参数，还受到Spark配置参数的显著影响。传统方法往往将这两类参数分开调优，忽视了它们之间的潜在耦合关系，因而难以找到真正高效的组合配置。为此，我们提出了一种联合调优框架，能够在同一过程中同时优化算法超参数与 Spark 配置参数，从而全面提升系统性能。为了降低调优开销，我们重点关注了30个在经验上被证实对性能影响最大的Spark 参数。同时，考虑到手动微调在大规模环境下几乎不可能完成，我们设计了一个自动参数调优系统，通过排序学习来智能发现最佳参数组合，从而实现高效的分布式聚类执行。

参数调优本质上可以视为一个优化问题：在给定的数据和资源约束下，如何选择一组配置，使得系统的执行性能最优。综合对比后，我们提出的方案采用排序学习的思想，它不仅能在探索和利用之间取得平衡，还能支持并行评估，极大提升了调优效率。不同于预测执行时间的传统模型，排序学习只需判断“哪个参数组合更优”，通过成对比较（pairwise comparison）的方式即可完成，这大大减少了建模复杂度和误差传播。

如图 5 所示，我们的调优系统包含Offline Process与Online Process两个环节：

lOffline Process：在系统资源充足时，调优器会自动生成一系列参数组合进行实验，记录执行时间及相关特征。这些数据会存入历史仓库，用于不断训练和更新排序模型。这样，模型可以在不影响实际任务的情况下持续进化。

lOnline Process：当用户提交任务时，调优器会根据最新的模型快速推荐一组最优参数组合。这些参数被用于配置聚类程序和 Spark 系统，任务执行完成后，结果会反馈给用户。

通过离线和在线的双轨设计，系统既能在后台持续学习，又能在前台高效响应用户任务，从而实现高性能、低开销的全自动调优。

图5 调优流程

2.3.2 Offline Process

如图 5 所示，Offline Process的核心目标是为调优模型积累高质量的历史经验。在系统资源空闲时，我们会周期性地从全局数据集中抽取子集，并在不同参数配置下执行聚类任务，收集特征与性能表现。这些信息被用于训练和更新调优模型，使其能够更好地预测和推荐最优配置。整个过程包含三个主要环节：采样、特征提取与聚类执行。

为了保证训练样本的多样性和代表性，我们在采样阶段设计了多层次的策略，使离线积累的知识能够更好地适应用户在实际场景中提交的多样化任务，增强模型的泛化能力。在得到子数据集后，我们利用特征提取器生成特征向量。这些特征反映了影响配置与性能之间关系的关键因素，包括空间范围、时间跨度、数据规模、时空分布及用户设定参数。在特征提取之后，系统会接收数据集及相应的配置参数（包括聚类参数与 Spark 系统参数），执行时空聚类任务，并记录实际运行时间。通过在不同配置组合下重复执行，该模块逐步积累历史记录，为后续的排序学习模型提供了坚实的数据支撑。

2.3.3 Online Process

当用户提交一个时空聚类任务时，系统会自动启动在线调优流程，以在执行前为该任务生成最优参数配置。用户输入的数据集会首先交由特征提取器（Feature Extractor）处理，提取与任务相关的特征向量。这一过程与离线训练阶段保持一致，确保特征表征具有可比性和稳定性。在得到任务特征后，系统会调用参数生成器，基于历史记录和随机探索共同构建候选参数集合。该模块的目标是在保证参数质量的同时维持必要的多样性：系统从历史数据库中挑选与当前任务特征相似的任务，并收集这些任务的高质量参数组合。直观上，相似任务往往在性能最优时也会使用相近的配置。为避免陷入局部最优，参数生成器还会在受约束的有效参数空间中进行随机采样。该空间由历史任务的投票机制确定，既保证了配置的潜在有效性，又避免了盲目扩展。最终输出的候选参数集合同时包含了历史经验与随机探索两类来源，兼顾了收敛性与探索性。

候选参数集合生成后，系统会通过参数比较器进行筛选。该模块采用了基于成对排序学习（pairwise learning-to-rank）的方法，对参数组合逐对比较，判断在当前任务特征下哪个参数组合更优。与依赖序列迭代的贝叶斯优化不同，这种基于比较的方式支持并行评估，显著提升了调优效率。通过多轮比较，系统最终确定最优参数，并将其输入到时空聚类执行中，用于完成任务配置与聚类计算。

三. 实验

3.1实验设置

集群. 所有实验均在一个由 3 个节点组成的集群上进行，每个节点配置为 CentOS 7.4 操作系统、24 核 CPU 和 128GB 内存。

数据集. 论文使用了两个真实数据集NYTrip和DidiTraj，其数据分布如图6所示。

图6 数据分布

3.2 性能比较

图7中的柱状图展示了DiST和MR-DBSCAN在不同数据量下性能的综合比较，可以明显看出，DiST在各种数据量下始终优于MR-DBSCAN。随着数据量的增加，DiST与MR之间的性能差距也变得越来越显著，说明DiST在处理大规模数据集时所具备的优越扩展性与高效性。

此外我们将所提出的分区方法与当前最先进的方法进行了比较，包括平均划分算法（ESP）、边界压缩分区法（RBP）以及我们提出的变体（Greedy）。如图7所示，折线图展示了在不同数据集规模下，各种分区方法的执行时间。随着数据集规模的增大，我们的分区方法始终展现出优越的性能。结果说明本方法在处理大规模数据时有较好的扩展性。

图7 性能比较

3.3 参数影响

本文进行了大量实验探究不同参数参数对程序性能的影响以及不同参数之间的联合影响，包括DBSCAN聚类的时空距离阈值、核心点界定阈值、时空划分尺度、分区数量以及负载均衡参数。结果如图8所示，可以看到各参数以及不同参数之间的组合都会对程序性能产生显著影响，因此设计自适应的调参系统以提升性能非常重要。 

图8 参数影响

3.4 调优方法比较

在实验对比中，我们将手动调优（M）、贝叶斯优化（BO）和基于排序学习的方法（R）应用于不同数据规模的任务，结果表明：即便将调参时间计入，总耗时上排序学习方法始终优于手动调优和贝叶斯优化，且随着数据规模的增加，其优势愈加显著；与此同时，从调参开销来看，排序学习在所有数据规模下均明显优于贝叶斯优化。整体而言，排序学习方法不仅能够在较短时间内找到高质量参数配置，还在大规模数据场景下有更突出的效率和实用价值。

图9 调优方法比较

3.4 调优方法比较

图10展示了在New York 子数据集上，手动调参与我们基于排序学习的调参框架在不同节点数量下的变化趋势。从图中可以明显看出，在不同数量的节点条件下，我们的调参系统能够最有效且平稳地优化程序的执行时间。同时，随着节点数量的增加，我们的系统依然能够保持稳定性。

图10 节点数量影响 

四．总结

本文提出了一种面向大数据环境的分布式密度聚类方法，在同时兼顾时间与空间维度的基础上，设计了新颖的数据划分策略，有效缓解了边界效应并实现了负载均衡。同时，我们构建了一个基于排序学习的自动调参框架，能够高效完成参数优化。实验结果表明，该方法在 Apache Spark平台上运行时，分区效率较基线方法提升近 100%，调参效率则达到人工调参的两倍。未来，我们将重点提升实时数据处理中的负载均衡能力，并在自动调参过程中引入可解释性机制，使参数选择更加透明。同时，我们还将探索更稳健的策略，以缓解潜在风险，进一步增强方法在多样化应用场景下的适应性与稳定性。

本文作者 李佳俊 重庆大学计算机学院2023级硕士生，重庆大学Start Lab团队成员。 主要研究方向：时空数据挖掘、AI4DB

       

              图文｜李佳俊

              校稿｜苏赛男

              编辑｜周钦钦

              审核｜李瑞远

              审核｜杨广超