• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

Tian, Xiaoyun (Tian, Xiaoyun.) | Xu, Dachuan (Xu, Dachuan.) (Scholars:徐大川) | Guo, Longkun (Guo, Longkun.) | Wu, Dan (Wu, Dan.)

Indexed by:

EI Scopus SCIE

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 S and k <= n with respect to mu-similar Bregman divergence, the BKM problem aims first to find a center subset C subset of S with vertical bar C vertical bar= k and then separate S into k clusters according to C, such that the sum of mu-similarBregman divergence from each point in 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- epsilon(1) and 1+ epsilon(2) for epsilon(1) is an element of epsilon[0, 1) and epsilon(2) >= 0, and obtain an approximation ratio of O(log(2) k) in expectation.

Keyword:

k-means m-similar Bregman divergences Local search Seeding algorithm

Author Community:

  • [ 1 ] [Tian, Xiaoyun]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China
  • [ 2 ] [Xu, Dachuan]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 3 ] [Guo, Longkun]Qilu Univ Technol, Shandong Acad Sci, Sch Comp Sci & Technol, Jinan 250353, Peoples R China
  • [ 4 ] [Wu, Dan]Henan Univ Sci & Technol, Sch Math & Stat, Luoyang 471023, Peoples R China

Reprint Author's Address:

  • [Guo, Longkun]Qilu Univ Technol, Shandong Acad Sci, Sch Comp Sci & Technol, Jinan 250353, Peoples R China

Show more details

Related Keywords:

Related Article:

Source :

JOURNAL OF COMBINATORIAL OPTIMIZATION

ISSN: 1382-6905

Year: 2021

Issue: 4

Volume: 44

Page: 2533-2550

1 . 0 0 0

JCR@2022

ESI Discipline: MATHEMATICS;

ESI HC Threshold:31

JCR Journal Grade:3

Cited Count:

WoS CC Cited Count: 0

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 10

Affiliated Colleges:

Online/Total:1039/11215221
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.