Faster algorithms for the constrained k-means problem

DOI10.4230/LIPICS.STACS.2016.16MaRDI QIDQ4601868zbMATH OpenOpenAlexFDO

Authors Anup Bhattacharya, Ragesh Jaiswal, Amit Kumar

Publication date 24 January 2018

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

zbMATH Keywords

\(k\)-means\(k\)-medianapproximation algorithmsampling

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Randomized algorithms (68W20) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Abstract: The classical center based clustering problems such as $k$-means/median/center assume that the optimal clusters satisfy the locality property that the points in the same cluster are close to each other. A number of clustering problems arise in machine learning where the optimal clusters do not follow such a locality property. Consider a variant of the $k$-means problem that may be regarded as a general version of such problems. Here, the optimal clusters $O_1,\mathrm{...},O_k$ are an arbitrary partition of the dataset and the goal is to output $k$-centers $c_1,\mathrm{...},c_k$ such that the objective function $su{m}_{i=1}^{k}su{m}_{xin{O}_i}||x-c_i|{|}^2$ is minimized. It is not difficult to argue that any algorithm (without knowing the optimal clusters) that outputs a single set of $k$ centers, will not behave well as far as optimizing the above objective function is concerned. However, this does not rule out the existence of algorithms that output a list of such $k$ centers such that at least one of these $k$ centers behaves well. Given an error parameter $varepsilon>0$, let $ell$ denote the size of the smallest list of $k$-centers such that at least one of the $k$-centers gives a $(1+varepsilon)$ approximation w.r.t. the objective function above. In this paper, we show an upper bound on $ell$ by giving a randomized algorithm that outputs a list of $2^{ildeO(k/varepsilon)}$ $k$-centers. We also give a closely matching lower bound of $2^{ildeOmega(k/sqrtvarepsilon)}$. Moreover, our algorithm runs in time $Oleft(ndcdot{2}^{ildeO(k/varepsilon)}ight)$. This is a significant improvement over the previous result of Ding and Xu who gave an algorithm with running time $Oleft(ndcdot(logn{)}^{k}cdot{2}^{poly(k/varepsilon)}ight)$ and output a list of size $Oleft((logn{)}^{k}cdot{2}^{poly(k/varepsilon)}ight)$.

Recommendations

• Faster algorithms for the constrained k-means problem
• Improved PTAS for the constrained \(k\)-means problem
• scientific article; zbMATH DE number 1303609
• Exact and approximation algorithms for clustering
• A unified framework for clustering constrained data without locality property

Cited in

(9)

• Faster algorithms for the constrained k-means problem
• A unified framework for clustering constrained data without locality property
• Improved PTAS for the constrained \(k\)-means problem
• Nearly tight bounds on the price of explainability for the \(k\)-center and the maximum-spacing clustering problems
• Clustering in the Boolean hypercube in a list decoding regime
• A unified framework for clustering constrained data without locality property
• scientific article; zbMATH DE number 2247697 (Why is no real title available?)
• Algorithms and Computation
• Order-constrained solutions in \(K\)-means clustering: even better than being globally optimal

This page was built for publication: Faster algorithms for the constrained \(k\)-means problem

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