2017/04/06 by Nir Ailon, Ailon, Nir, Anup Bhattacharya +5
Computer Science · #Advanced Clustering Algorithms Research #Advanced Graph Theory Research #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1704.01862
Updated version has results for faulty queries
openalex publication_date 2017/04/06 · arxiv created 2017/10/04 · arxiv updated 2017/10/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(k2 logk + k logn) same-cluster queries. This is interesting since the k-means problem, even with the margin assumption, is NP-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 + ε)-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 NP-hard to approximate within a factor (1 + c) for a fixed constant 0 < c < 1. The number of same-cluster queries used is \textrmpoly(k/ε) which is independent of the size n of the dataset. Our algorithm is based on the D2-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 Ω((k)/(poly log k) ) 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.