arXiv:2608.14215cs.LG2026-08

提出一种连通子空间聚类方法,用于识别海平面变化中的物理连续区域。

Connected Subspace Clustering: Hardness, a Scalable Heuristic, and an Application to Sea Level Geodesy

论文配图:Connected Subspace Clustering: Hardness, a Scalable Heuristic, and an Application to Sea Level Geodesy
图 1 · 摘自论文原文
  • 通过迭代合并实现连通性约束,结合子空间拟合优化聚类
  • 在160组全球海平面数据中,73.75%情况下优于四种对比策略
  • 适用于气候、遥感等具有空间结构的多变量时序数据

受限优化通过引入辅助信息扩展了经典优化,广泛应用于科学与工程领域。当在不同物理位置测量变量时,常需聚类既内部相似又物理连贯。为此,我们提出连通子空间聚类问题:给定高维点与连通图,将它们划分为 $k$ 个连通簇,使各簇点到其最优 $m'$-维仿射子空间的总平方距离最小。证明即使 $m' = 0$ 且图为带孔网格图,该问题在 $n$ 个测量值下无法在 $Ω(n^{1/2-})$ 内近似,其中 $n$ 为测量数。随后提出一种类似Lloyd的高效启发式算法,交替进行子空间拟合与迭代合并以保证连通性。该方法构造出恰好 $k$ 个连通区域,而无约束方法最多产生 $1{,}966$ 个不连通片段且代价更高。在160组全球海平面时间序列配置中,我们的合并修复策略在 $73.75\%$ 情况下表现最优,并持续优于(连通)Ward法。结果区域能有效分离与厄尔尼诺-南方涛动、印度洋偶极子等气候指数相关的信号。尽管源于大地测量学应用,该方法亦适用于其他空间嵌入型多变量时序数据,如气候场、遥感、脑成像与传感器网络。

原文摘要 · Abstract (English)

Constrained optimization extends classical optimization by integrating side information, making it widely applicable across scientific and engineering domains. Consider a setting where we measure variables at different physical locations. When grouping these measurements, we often want clusters that are both internally similar and physically coherent. Thus, we have a constrained clustering problem where the constraint models coherence. Motivated by an application in geodesy, where contiguous regions of the sea surface must be identified for principal component analysis, we introduce the Connected Subspace Clustering problem: given high-dimensional points and a connectivity graph, partition them into $k$ connected clusters, minimizing their total squared distance to the clusters' best-fit $m'$-dimensional affine subspaces. We prove that, even for $m' = 0$ and a grid graph with holes, the problem is NP-hard to approximate within $Ω(n^{1/2-\varepsilon})$ for every $\varepsilon>0$, where $n$ is the number of measurements. We then introduce an efficient Lloyd-style heuristic that alternates subspace fitting with an iterative merging procedure to enforce connectivity. Our method returns exactly $k$ connected regions by construction, whereas unconstrained methods leave up to $1{,}966$ disconnected fragments at higher cost. In a study of 160 configurations on global sea level time series, our merging-based repair is the strongest of four strategies in $73.75\%$ of cases, and consistently outperforms competitors such as (connected) Ward's method across all tested cluster counts. The resulting regions isolate signals aligning with climate indices such as the El Nino-Southern Oscillation and Indian Ocean Dipole. Although developed for geodesy, the approach applies to other spatially embedded multivariate time series, such as climate fields, remote sensing, neuroimaging, and sensor networks.

聚类空间数据时序分析大地测量

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。