2018/03/02 by Buddhima Gamlath, Gamlath, Buddhima, Sangxia Huang +3 · 1 citation
Computer Science · Engineering · #Automated Road and Building Extraction #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1803.00926
openalex publication_date 2018/03/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study k-means clustering in a semi-supervised setting. Given an oracle\nthat returns whether two given points belong to the same cluster in a fixed\noptimal clustering, we investigate the following question: how many oracle\nqueries are sufficient to efficiently recover a clustering that, with\nprobability at least (1 - \δ), simultaneously has a cost of at most (1 +\n\ε) times the optimal cost and an accuracy of at least (1 - \ε)?\n We show how to achieve such a clustering on n points with O((k2 \log n)\n\⋅ m(Q, \ε4, \δ / (k\log n))) oracle queries, when the k\nclusters can be learned with an \ε' error and a failure probability\n\δ' using m(Q, \ε',\δ') labeled samples in the supervised\nsetting, where Q is the set of candidate cluster centers. We show that m(Q,\n\ε', \δ') is small both for k-means instances in Euclidean space\nand for those in finite metric spaces. We further show that, for the Euclidean\nk-means instances, we can avoid the dependency on n in the query complexity\nat the expense of an increased dependency on k: specifically, we give a\nslightly more involved algorithm that uses O(k4/(\ε2 \δ) +\n(k9/\ε4) \log(1/\δ) + k \⋅ m(\ℝr, \ε4/k,\n\δ)) oracle queries.\n We also show that the number of queries needed for (1 - \ε)-accuracy\nin Euclidean k-means must linearly depend on the dimension of the underlying\nEuclidean space, and for finite metric space k-means, we show that it must at\nleast be logarithmic in the number of candidate centers. This shows that our\nquery complexities capture the right dependencies on the respective parameters.\n