Coresets for (k, ) -median clustering under the Fréchet distance

DOI10.1007/978-3-030-95018-7_14MaRDI QIDQ6102274zbMATH OpenOpenAlexFDO

Authors Maike Buchin

Publication date 8 May 2023

Published in Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2104.09392

zbMATH Keywords

clusteringcoresetsMedianpolygonal curves

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: We present an algorithm for computing $epsilon$-coresets for $(k,ell)$-median clustering of polygonal curves in $mathbb{R}^d$ under the Fr'echet distance. This type of clustering is an adaption of Euclidean $k$-median clustering: we are given a set of $n$ polygonal curves in $mathbb{R}^d$, each of complexity (number of vertices) at most $m$, and want to compute $k$ median curves such that the sum of distances from the given curves to their closest median curve is minimal. Additionally, we restrict the complexity of the median curves to be at most $ell$ each, to suppress overfitting, a problem specific for sequential data. Our algorithm has running time linear in $n$, sub-quartic in $m$ and quadratic in $epsilo{n}^{-1}$. With high probability it returns $epsilon$-coresets of size quadratic in $epsilo{n}^{-1}$ and logarithmic in $n$ and $m$. We achieve this result by applying the improved $epsilon$-coreset framework by Langberg and Feldman to a generalized $k$-median problem over an arbitrary metric space. Later we combine this result with the recent result by Driemel et al. on the VC dimension of metric balls under the Fr'echet distance. Furthermore, our framework yields $epsilon$-coresets for any generalized $k$-median problem where the range space induced by the open metric balls of the underlying space has bounded VC dimension, which is of independent interest. Finally, we show that our $epsilon$-coresets can be used to improve the running time of an existing approximation algorithm for $(1,ell)$-median clustering.

Cites work

• \(k\)-median clustering under discrete Fréchet and Hausdorff distances
• A unified framework for approximating and clustering data
• Approximating \((k,\ell)\)-center clustering for curves
• Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers
• Clustering time series under the Fréchet distance
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• Core-sets: updated survey
• Geometric approximation algorithms
• scientific article; zbMATH DE number 4074316 (Why is no real title available?)
• On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
• On coresets for k-means and k-median clustering
• On the Hardness of Computing an Average Curve.
• On the sensitivity of shape fitting problems
• Relative (p, )-approximations in geometry
• Smaller coresets for k-median and k-means clustering
• The VC dimension of metric balls under Fréchet and Hausdorff distances
• Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
• Universal \({\epsilon}\)-approximators for integrals

Cited in

(5)

• On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
• On coresets for k-means and k-median clustering
• Coresets for Fuzzy K-Means with Applications
• Approximating ( k,ℓ )-Median Clustering for Polygonal Curves
• Fast approximations and coresets for (k,)-median under dynamic time warping

This page was built for publication: Coresets for \((k, \ell ) \)-median clustering under the Fréchet distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6102274)