为线段集的k均值聚类设计高效小规模核，支持实时应用。
Linear time small coresets for k-mean clustering of segments with applications
- 提出首个适用于任意线段输入的线性时间核构造方法。
- 核大小仅需O(log²n)，在nd时间内完成计算，精度损失小于ε。
- 适合需要快速聚类的大规模数据，如实时视频追踪系统。
我们研究了由n条线段组成的集合$\mathcal{S} \subseteq \mathbb{R}^d$上的k均值聚类问题，目标是找到k个中心$X \subseteq \mathbb{R}^d$以最小化$D(\mathcal{S},X) := \sum_{S \in \mathcal{S}} \min_{x \in X} D(S,x)$，其中$D(S,x) := \int_{p \in S} |p - x| dp$表示线段上所有点到中心的总距离。该问题可扩展至处理异常值、使用M-估计器等替代距离函数、加权距离以实现均衡聚类或强制唯一分配。对任意$\varepsilon > 0$，一个$\varepsilon$-核是$\mathbb{R}^d$中的加权子集$C$，使得对任意k个中心，$D(\mathcal{S},X)$的近似误差在$1 \pm \varepsilon$以内，从而支持高效流式、分布式或并行计算。本文首次提出可处理任意输入线段的核构造方法，在常数$\varepsilon$和$\varepsilon$下，核大小为$O(\log^2 n)$，可在$O(nd)$时间内计算。实验包括真实场景下的实时视频追踪，验证了显著加速与极小精度损失，证实方法兼具实际效率与理论保证。
原文摘要 · Abstract (English)
We study the $k$-means problem for a set $\mathcal{S} \subseteq \mathbb{R}^d$ of $n$ segments, aiming to find $k$ centers $X \subseteq \mathbb{R}^d$ that minimize $D(\mathcal{S},X) := \sum_{S \in \mathcal{S}} \min_{x \in X} D(S,x)$, where $D(S,x) := \int_{p \in S} |p - x| dp$ measures the total distance from each point along a segment to a center. Variants of this problem include handling outliers, employing alternative distance functions such as M-estimators, weighting distances to achieve balanced clustering, or enforcing unique cluster assignments. For any $\varepsilon > 0$, an $\varepsilon$-coreset is a weighted subset $C \subseteq \mathbb{R}^d$ that approximates $D(\mathcal{S},X)$ within a factor of $1 \pm \varepsilon$ for any set of $k$ centers, enabling efficient streaming, distributed, or parallel computation. We propose the first coreset construction that provably handles arbitrary input segments. For constant $k$ and $\varepsilon$, it produces a coreset of size $O(\log^2 n)$ computable in $O(nd)$ time. Experiments, including a real-time video tracking application, demonstrate substantial speedups with minimal loss in clustering accuracy, confirming both the practical efficiency and theoretical guarantees of our method.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。