Improved local search algorithms for Bregman k-means and its variants

Xiaoyun Tian (), Dachuan Xu (), Longkun Guo () and Dan Wu ()
Additional contact information
Xiaoyun Tian: Beijing University of Technology
Dachuan Xu: Beijing University of Technology
Longkun Guo: Qilu University of Technology (Shandong Academy of Sciences)
Dan Wu: Henan University of Science and Technology

Journal of Combinatorial Optimization, 2022, vol. 44, issue 4, No 21, 2533-2550

Abstract: Abstract 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}}$$ S and $$k \le n$$ k ≤ n with respect to $$\mu $$ μ -similar Bregman divergence, the BKM problem aims first to find a center subset $$C \subseteq {\mathcal {S}}$$ C ⊆ S with $$ \mid C \mid = k$$ ∣ C ∣ = k and then separate $${\mathcal {S}}$$ S into k clusters according to C, such that the sum of $$\mu $$ μ -similar Bregman divergence from each point in $${\mathcal {S}}$$ 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$$ 1 - ε 1 and $$1+ \varepsilon _2$$ 1 + ε 2 for $$\varepsilon _1 \in [0,1)$$ ε 1 ∈ [ 0 , 1 ) and $$\varepsilon _2 \ge 0$$ ε 2 ≥ 0 , and obtain an approximation ratio of $$O(\log ^2 k)$$ O ( log 2 k ) in expectation.

Keywords: Seeding algorithm; Local search; k-means; $$\mu $$ μ -similar Bregman divergences (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00771-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:4:d:10.1007_s10878-021-00771-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00771-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().