Approximate Clustering with Same-Cluster Queries

DOI10.4230/LIPICS.ITCS.2018.40MaRDI QIDQ4993306zbMATH OpenOpenAlexFDO

Authors Nir Ailon, Anup Bhattacharya, Ragesh Jaiswal, Amit Kumar

Publication date 15 June 2021

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

zbMATH Keywords

\(k\)-meanssemi-supervised learningquery bounds

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Abstract: Ashtiani et al. proposed a Semi-Supervised Active Clustering framework (SSAC), where the learner is allowed to make adaptive queries to a domain expert. The queries are of the kind "do two given points belong to the same optimal cluster?" There are many clustering contexts where such same-cluster queries are feasible. Ashtiani et al. exhibited the power of such queries by showing that any instance of the $k$-means clustering problem, with additional margin assumption, can be solved efficiently if one is allowed $O(k^{2}logk+klogn)$ same-cluster queries. This is interesting since the $k$-means problem, even with the margin assumption, is $mathsfNP$-hard. In this paper, we extend the work of Ashtiani et al. to the approximation setting showing that a few of such same-cluster queries enables one to get a polynomial-time $(1+varepsilon)$-approximation algorithm for the $k$-means problem without any margin assumption on the input dataset. Again, this is interesting since the $k$-means problem is $mathsfNP$-hard to approximate within a factor $(1+c)$ for a fixed constant $0<c<1$. The number of same-cluster queries used is $extrmpoly(k/varepsilon)$ which is independent of the size $n$ of the dataset. Our algorithm is based on the $D^2$-sampling technique. We also give a conditional lower bound on the number of same-cluster queries showing that if the Exponential Time Hypothesis (ETH) holds, then any such efficient query algorithm needs to make $Omegaleft(frackpolylogkight)$ same-cluster queries. Our algorithm can be extended for the case when the oracle is faulty. Another result we show with respect to the $k$-means++ seeding algorithm is that a small modification to the $k$-means++ seeding algorithm within the SSAC framework converts it to a constant factor approximation algorithm instead of the well known $O(logk)$-approximation algorithm.

Recommendations

• Approximate correlation clustering using same-cluster queries
• Correlation clustering with same-cluster queries bounded by optimal cost
• Approximate range queries for clustering
• Approximation schemes for clustering problems
• Clustering with or without the approximation
• Clustering with or without the approximation
• Exact and approximation algorithms for clustering
• Approximate clustering via metric partitioning

Cites work

• scientific article; zbMATH DE number 6381735 (Why is no real title available?)
• scientific article; zbMATH DE number 1398082 (Why is no real title available?)
• A PTAS for k-means clustering based on weak coresets
• A bad instance for \texttt{k-means++}
• A local search approximation algorithm for \(k\)-means clustering
• A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
• Active clustering of biological sequences
• Adaptive Sampling for k-Means Clustering
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Center-based clustering under perturbation stability
• Clustering under approximation stability
• Clustering with Interactive Feedback
• Improved analysis of D^2-sampling based PTAS for k-means and other clustering problems
• Improved and simplified inapproximability for \(k\)-means
• Iterative and active graph clustering using trace norm minimization without cluster size constraints
• Linear-time approximation schemes for clustering problems in any dimensions
• Local algorithms for interactive clustering
• On the complexity of k-SAT
• The PCP theorem by gap amplification
• The effectiveness of Lloyd-type methods for the \(k\)-means problem
• The hardness of approximation of Euclidean k-means
• The planar \(k\)-means problem is NP-hard
• Tight lower bound instances for k-means++ in two dimensions
• Which problems have strongly exponential complexity?
• \(k\)-means requires exponentially many iterations even in the plane

Cited in

(7)

• scientific article; zbMATH DE number 7525518 (Why is no real title available?)
• On sampling based algorithms for k-means
• Clustering under perturbation stability in near-linear time
• Exact \(k\)-NN queries on clustered SVD datasets
• FPT approximation for capacitated sum of radii
• Semi-supervised algorithms for approximately optimal and accurate clustering
• Approximate correlation clustering using same-cluster queries

Describes a project that uses

Uses Software

• k-means++

This page was built for publication: Approximate Clustering with Same-Cluster Queries

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