• 综合
  • 标题
  • 关键词
  • 摘要
  • 学者
  • 期刊-刊名
  • 期刊-ISSN
  • 会议名称
搜索

作者:

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

收录:

SCIE

摘要:

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.

关键词:

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

作者机构:

  • [ 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

通讯作者信息:

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

查看成果更多字段

相关关键词:

相关文章:

来源 :

JOURNAL OF COMBINATORIAL OPTIMIZATION

ISSN: 1382-6905

年份: 2021

1 . 0 0 0

JCR@2022

ESI高被引阀值:5

被引次数:

WoS核心集被引频次: 0

SCOPUS被引频次:

ESI高被引论文在榜: 0 展开所有

万方被引频次:

中文被引频次:

近30日浏览量: 0

归属院系:

在线人数/总访问数:65/3278409
地址:北京工业大学图书馆(北京市朝阳区平乐园100号 邮编:100124) 联系我们:010-67392185
版权所有:北京工业大学图书馆 站点建设与维护:北京爱琴海乐之技术有限公司