Linear-time approximation scheme for k-means clustering of axis-parallel affine subspaces
Kyungjin Cho, Eunjin Oh · Computational Geometry · 2023
In this paper, we present a linear-time approximation scheme for k -means clustering of incomplete data points in d -dimensional Euclidean space . An incomplete data point with Δ > 0 unspecified entries is represented as an axis-parallel affine subspace of dimension Δ. The distance between two incomplete data points is defined as the Euclidean distance between two closest points in the axis-parallel affine subspaces corresponding to the data points. We present an algorithm for k -means clustering of n axis-parallel affine subspaces of dimension Δ that yields an ( 1 + ϵ ) -approximate solution in O ( n d ) time. The constants hidden behind O ( ⋅ ) depend only on Δ , ϵ and k . This improves the O ( n 2 d ) -time algorithm by Eiben et al. (2021) [7] by a factor of n .