收录:
摘要:
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.
关键词:
通讯作者信息:
电子邮件地址: