Improved local search algorithms for Bregman k-means and its variants
2021
In this paper, we consider the Bregman k-means problem (BKM) which is a variant of the classical k-means problem. For an n-point set $${\mathcal {S}}$$
and $$k \le n$$
with respect to $$\mu $$
-similar Bregman divergence, the BKM problem aims first to find a center subset $$C \subseteq {\mathcal {S}}$$
with $$ \mid C \mid = k$$
and then separate $${\mathcal {S}}$$
into k clusters according to C, such that the sum of $$\mu $$
-similar Bregman divergence from each point in $${\mathcal {S}}$$
to its nearest center is minimized. We propose a $$\mu $$
-similar BregMeans++ algorithm by employing the local search scheme, and prove that the algorithm deserves a constant approximation guarantee. Moreover, we extend our algorithm to solve a variant of BKM called noisy $$\mu $$
-similar Bregman k-means++ (noisy $$\mu $$
-BKM++) which is BKM in the noisy scenario. For the same instance and purpose as BKM, we consider the case of sampling a point with an imprecise probability by a factor between $$1-\varepsilon _1$$
and $$1+ \varepsilon _2$$
for $$\varepsilon _1 \in [0,1)$$
and $$\varepsilon _2 \ge 0$$
, and obtain an approximation ratio of $$O(\log ^2 k)$$
in expectation.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
21
References
0
Citations
NaN
KQI