License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2018.40
URN: urn:nbn:de:0030-drops-83358
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8335/
Ailon, Nir ;
Bhattacharya, Anup ;
Jaiswal, Ragesh ;
Kumar, Amit
Approximate Clustering with Same-Cluster Queries
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?", where the answers to these queries are assumed to be consistent with a unique optimal solution. 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 to make O(k^2 log{k} + k log{n}) 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 by showing that a few of such same-cluster queries enables one to get a polynomial-time (1+eps)-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 by the algorithm is poly(k/eps) which is independent of the size n of the dataset. Our algorithm is based on the D^2-sampling technique, also known as the k-means++ seeding algorithm. 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 Omega (k/poly log k) same-cluster queries. Our algorithm can be extended for the case where the query answers are wrong with some bounded probability. Another result we show for the k-means++ seeding is that a small modification of the k-means++ seeding within the SSAC framework converts it to a constant factor approximation algorithm instead of the well known O(log k)-approximation algorithm.
BibTeX - Entry
@InProceedings{ailon_et_al:LIPIcs:2018:8335,
author = {Nir Ailon and Anup Bhattacharya and Ragesh Jaiswal and Amit Kumar},
title = {{Approximate Clustering with Same-Cluster Queries}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {40:1--40:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Anna R. Karlin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8335},
URN = {urn:nbn:de:0030-drops-83358},
doi = {10.4230/LIPIcs.ITCS.2018.40},
annote = {Keywords: k-means, semi-supervised learning, query bounds}
}
|
Keywords: |
|
k-means, semi-supervised learning, query bounds |
|
Collection: |
|
9th Innovations in Theoretical Computer Science Conference (ITCS 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
12.01.2018 |
