带惩罚μ-相似Bregman散度k-均值问题的初始化算法

doi:10.15960/j.cnki.issn.1007-6093.2022.01.007

运筹学学报 ›› 2022, Vol. 26 ›› Issue (1): 99-112.doi: 10.15960/j.cnki.issn.1007-6093.2022.01.007

带惩罚μ-相似Bregman散度k-均值问题的初始化算法

刘文杰¹, 张冬梅^1*^,*(), 张鹏², 邹娟³

1. 山东建筑大学计算机科学与技术学院, 山东济南 250101
2. 山东大学软件学院, 山东济南 250101
3. 曲阜师范大学数学科学学院, 山东曲阜 273165

收稿日期:2021-07-21 出版日期:2022-03-15 发布日期:2022-03-14
通讯作者: 张冬梅 E-mail:zhangdongmei@sdjzu.edu.cn
作者简介:张冬梅 E-mail: zhangdongmei@sdjzu.edu.cn
基金资助:
国家自然科学基金(11871081);国家自然科学基金(61972228);国家自然科学基金(11801310);山东省自然科学基金(ZR2021MF006)

The seeding algorithm for $\mu$-similar Bregman divergences $k$-means problem with penalties

Wenjie LIU¹, Dongmei ZHANG^1*^,*(), Peng ZHANG², Juan ZOU³

1. School of Computer Science and Technology, Shandong Jianzhu University, Jinan 250101, Shandong, China
2. School of Software, Shandong University, Jinan 250101, Shandong, China
3. School of Mathematical Sciences, Qufu Normal University, Qufu 273165, Shandong, China

Received:2021-07-21 Online:2022-03-15 Published:2022-03-14
Contact: Dongmei ZHANG E-mail:zhangdongmei@sdjzu.edu.cn

摘要/Abstract

摘要：

$k$-均值问题是聚类中的经典问题，亦是NP-难问题。如果允许数据点不聚类，而是支付惩罚费用，则引出带惩罚的$k$-均值问题。本文将带惩罚的$k$-均值问题从欧氏距离推广到更一般的$\mu$-相似Bregman散度，研究了带惩罚$\mu$-相似Bregman散度$k$-均值问题的初始化算法。本文给出的初始化算法，近似比与$\mu$和数据点惩罚最大值与最小值的比例$r$相关。

关键词: 近似算法, $k$-均值, 惩罚, $\mu$-相似Bregman散度, 初始化算法

Abstract:

The $k$-means problem is a classic NP-hard problem in clustering analysis. If somedata points are allowed not to be clustered but to pay some penalty, the $k$-means problem with penalty is induced. In this paper, weextend the $k$-means problem with penalty from Euclidean distance tothe more general $\mu $-similar Bregman divergences, and study theinitialization algorithm for the $\mu $-similar Bregman divergences $k$-means problem with penalty. The seeding algorithm is given wherethe approximation ratio is only related to $\mu $ and the ratio ofthe maximum value to the minimum value of the data point penalty.

Key words: approximation algorithm, $k$-means, penalty, $\mu$-similar Bregman divergences, seeding algorithm

中图分类号:

O221.7

刘文杰, 张冬梅, 张鹏, 邹娟. 带惩罚μ-相似Bregman散度k-均值问题的初始化算法[J]. 运筹学学报, 2022, 26(1): 99-112.

Wenjie LIU, Dongmei ZHANG, Peng ZHANG, Juan ZOU. The seeding algorithm for $\mu$-similar Bregman divergences $k$-means problem with penalties[J]. Operations Research Transactions, 2022, 26(1): 99-112.

图/表 3

参考文献 22

1	Aloise D , Deshpande A , Hansen P , et al. NP-hardness of Euclidean sum-of-squares clustering[J]. Machine Learning, 2009, 75, 245- 248. doi: 10.1007/s10994-009-5103-0
2	Drineas P , Frieze A , Kannan R , et al. Clustering large graphs via the singular value decomposition[J]. Machine Learning, 2004, 56, 9- 33. doi: 10.1023/B:MACH.0000033113.59016.96
3	Awasthi P, Charikar M, Krishnaswamy R, et al. The hardness of approximation of Euclidean k-means[C]//Proceedings of SoCG, 2015: 754-767.
4	Bachem O, Lucic M, Hassani S H, et al. Approximate k-means++ in sublinear time[C]//Proceedings of AAAI, 2016: 1459-1467.
5	Blömer J, Lammersen C, Schmidt M, et al. Theoretical analysis of the k-means algorithm\|A survey[M]//Algorithm Engineering\|Selected Results and Surveys, Cham: Springer, 2016: 81-116.
6	Kanungo T , Mount D M , Netanyahu N S , et al. A local search approximation algorithm for k-means clustering[J]. Computational Geometry: Theory and Applications, 2004, 28, 89- 112. doi: 10.1016/j.comgeo.2004.03.003
7	Lee E , Schmidt M , Wright J . Improved and simplified inapproximability for k-means[J]. Information Processing Letters, 2017, 120, 40- 43. doi: 10.1016/j.ipl.2016.11.009
8	Xu D , Xu Y , Zhang D . A survey on algorithm for k-means problem and its variants[J]. Operations Research Transactions, 2017, 21, 101- 109.
9	Ahmadian S, Norouzi-Fard A, Svensson O, et al. Better guarantees for k-means and Euclidean k-median by primal-dual algorithms[C]//Proceedings of FOCS, 2017: 61-72.
10	Lloyd S . Least squares quantization in PCM[J]. IEEE Transactions on Information Theory, 1982, 28, 21- 33.
11	Arthur D, Vassilvitskii S. k-means++: The advantages of careful seeding[C]//Proceedings of SODA, 2007: 1027-1035.
12	Aggarwal A, Deshpande A, Kannan R. Adaptive sampling for k-means clustering[C]//Proceedings of APPROX and RANDOM, 2009: 15-28.
13	Bachem O, Lucic M, Hassani S H, et al. Fast and provably good seedings for k-means[C]//Proceedings of NIPS, 2016: 55-63.
14	Bachem O, Lucic M, Krause A. Distributed and provably good seedings for k-means in constant rounds[C]//Proceedings of ICML, 2017: 292-300.
15	Bahmani B, Moseley B, Vattani A, et al. Scalable k-means++[C]//Proceedings of the VLDB Endowment, 2012: 622-633.
16	Ostrovsky R , Rabani Y , Schulman L , et al. The effectiveness of Lloyd-type methods for the k-means problem[J]. Journal of the ACM, 2012, 59, 1- 22.
17	Tseng G C . Penalized and weighted k-means for clustering with scattered objects and prior information in high-throughput biological data[J]. Bioinformatics, 2007, 23, 2247- 2255. doi: 10.1093/bioinformatics/btm320
18	Zhang D, Hao C, Wu C, et al. A local search approximation algorithm for the k-means problem with penalties[C]//Proceedings of COCOON, 2017: 568-574.
19	Chang X Y, Wang Y, Li R, et al. Sparse k-means with l_∞/l₀ penalty for high-dimensional data clustering[EB/OL]. (2014-03-31)[2021-07-08]. https://arxiv.org/pdf/1403.7890.pdf.
20	Ackermann M R. Algorithms for the Bregman k-Median problem[D]. Paderborn: University of Paderborn, 2009.
21	Banerjee A , Merugu S , Dhillon I S , et al. Clustering with Bregman divergences[J]. Journal of Machine Learning Research, 2005, 6, 1705- 1749.
22	Li M , Xu D , Yue J , et al. The seeding algorithm for k-means problem with penalties[J]. Journal of Combinatorial Optimization, 2020, 39, 15- 32. doi: 10.1007/s10878-019-00450-w

[1]	李建平, 蔡力健, 李陈筠然, 潘鹏翔. 限制性多源点偏心距增广问题[J]. 运筹学学报, 2022, 26(1): 60-68.
[2]	陈婳, 张国川. 经典一维装箱问题近似算法的研究进展[J]. 运筹学学报, 2022, 26(1): 69-84.
[3]	剧嘉琛, 刘茜, 张昭, 周洋. 带惩罚的相同容量$k$-均值问题的局部搜索算法[J]. 运筹学学报, 2022, 26(1): 113-124.
[4]	李小玮, 成夏炎, 李荣珩. 带有线性惩罚的鲁棒k-种产品设施选址问题的近似算法[J]. 运筹学学报, 2021, 25(4): 31-44.
[5]	包晓光, 路超, 黄冬梅, 余炜. 混合图上最小-最大圈覆盖问题的近似算法[J]. 运筹学学报, 2021, 25(1): 107-113.
[6]	任建峰, 田晓云. 带有异常点的平方度量设施选址问题[J]. 运筹学学报, 2021, 25(1): 114-122.
[7]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[8]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[9]	王翼展, 张安, 陈永, 陈光亭. 堆取料机调度问题的一个近似算法[J]. 运筹学学报, 2020, 24(1): 147-154.
[10]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[11]	姜燕君, 徐大川, 张冬梅. 平方度量动态设施选址问题的近似算法[J]. 运筹学学报, 2018, 22(3): 49-58.
[12]	余善恩, 徐文洋, 刘光宇. 圆形区域分散布局问题研究[J]. 运筹学学报, 2018, 22(3): 132-138.
[13]	王一水, 徐大川, 吴晨晨. 关联聚类问题的半定规划舍入算法[J]. 运筹学学报, 2018, 22(1): 67-76.
[14]	陈中文, 赵奇, 卞凯. 非线性半定规划的逐次线性化柔性惩罚法[J]. 运筹学学报, 2017, 21(2): 84-100.
[15]	陈光亭, 陈蕾, 张安, 陈永. 可转包两台流水作业机排序的近似算法[J]. 运筹学学报, 2016, 20(4): 109-114.

带惩罚μ-相似Bregman散度k-均值问题的初始化算法

The seeding algorithm for $\mu$-similar Bregman divergences $k$-means problem with penalties

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 22

相关文章 15

编辑推荐

Metrics

本文评价