The Spherical k-means++ Algorithm via Local Search

Xiaoyun Tian, Dachuan Xu, Donglei Du, Ling GaiAAIM 2020 · OpenReview

Abstract

We consider the spherical k-means problem (SKMP), a generalization of the k-means clustering problem (KMP). Given a data set of n points \({\mathcal {P}}\) in d-dimensional unit sphere \({\mathbb {R}}^d\), and an integer \(k \le n\), it aims to partition the data set \({\mathcal {P}}\) into k sets so as to minimize the sum of cosine dissimilarity measure from each data point to its closest center. We present a constant expected approximation guarantee for this problem based on integrating the k-means++ seeding algorithm for the KMP and the local search technique.
BibTeX
@inproceedings{tian2020spherical,
  author = {Xiaoyun Tian and Dachuan Xu and Donglei Du and Ling Gai},
  title = {{The Spherical k-means++ Algorithm via Local Search}},
  booktitle = {AAIM},
  year = {2020},
  url = {https://openreview.net/forum?id=zU6c3XhoZE},
}

Loading related content...

Figure