An approximation algorithm for the spherical k-means problem with outliers by local search
An approximation algorithm for the spherical k-means problem with outliers by local search
复制标题
一种基于局部搜索的异常值球形k均值问题的逼近算法
DOI：
10.1007/s10878-021-00734-0
复制
发表时间：
2021-04
影响因子：
1
通讯作者：
Zou Juan
中科院分区：
文献类型：
--
作者：
Wang Yishui;Wu Chenchen;Zhang Dongmei;Zou Juan
我们考虑带有离群点的球面k-均值问题，它是k-均值问题的推广。在这个聚类问题中，所有的样本点都在单位球面上。给定两个整数k和z，我们最多可以忽略z个点(离群点)，并且需要在单位球面上找到至多k个簇中心，并将剩余的点分配给这些中心以最小化k-均值目标。已经证明，任何有界逼近比的算法都不能返回该问题的可行解。我们的贡献是提出了球面k-均值问题的局部搜索双准则近似算法。
We consider the spherical k-means problem with outliers, an extension of the k-means problem. In this clustering problem, all sample points are on the unit sphere. Given two integers k and z, we can ignore at most z points (outliers) and need to find at most k cluster centers on the unit sphere and assign remaining points to these centers to minimize the k-means objective. It has been proved that any algorithm with a bounded approximation ratio cannot return a feasible solution for this problem. Our contribution is to present a local search bi-criteria approximation algorithm for the spherical k-means problem.
登录
查看更多内容
DOI：
--
发表时间：
2016-05
期刊：
--
影响因子：
--
作者：
Dennis Wei
通讯作者：
Dennis Wei
DOI：
10.1016/j.tcs.2020.06.029
发表时间：
2020-07
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
D. Zhang;Y. Cheng;Min Li;Yishui Wang;Dachuan Xu
通讯作者：
D. Zhang;Y. Cheng;Min Li;Yishui Wang;Dachuan Xu
DOI：
10.1007/978-3-319-23240-9_9
发表时间：
2015-09
期刊：
--
影响因子：
--
作者：
Y. Endo;S. Miyamoto
通讯作者：
Y. Endo;S. Miyamoto
DOI：
--
发表时间：
2001-01
期刊：
--
影响因子：
--
作者：
M. Charikar;S. Khuller;D. Mount;G. Narasimhan
通讯作者：
M. Charikar;S. Khuller;D. Mount;G. Narasimhan
影响因子：
2.5
作者：
Gupta, Shalmoli;Kumar, Ravi;Vassilvitskii, Sergei
通讯作者：
Vassilvitskii, Sergei