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

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

Abstract

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

CLC Number:

O221.7

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.

Figures/Tables 3

References 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]	Jianping LI, Lijian CAI, Junran LICHEN, Pengxiang PAN. The constrained multi-sources eccentricity augmentation problems [J]. Operations Research Transactions, 2022, 26(1): 60-68.
[2]	Hua CHEN, Guochuan ZHANG. A survey on approximation algorithms for one dimensional bin packing [J]. Operations Research Transactions, 2022, 26(1): 69-84.
[3]	Jiachen JU, Qian LIU, Zhao ZHANG, Yang ZHOU. A local search analysis for the uniform capacitated $k$-means problem with penalty [J]. Operations Research Transactions, 2022, 26(1): 113-124.
[4]	Xiaowei LI, Xiayan CHENG, Rongheng LI. An approximation algorithm for Robust k-product facility location problem with linear penalties [J]. Operations Research Transactions, 2021, 25(4): 31-44.
[5]	Xiaoguang BAO, Chao LU, Dongmei HUANG, Wei YU. Approximation algorithm for min-max cycle cover problem on a mixed graph [J]. Operations Research Transactions, 2021, 25(1): 107-113.
[6]	Jianfeng REN, Xiaoyun TIAN. Squared metric facility location problem with outliers [J]. Operations Research Transactions, 2021, 25(1): 114-122.
[7]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[8]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.
[9]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.
[10]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[11]	LIAN Shujun, TANG Jiahui, DU Aihua. A new class of exact penalty functions for equality constrained smooth optimization [J]. Operations Research Transactions, 2018, 22(4): 108-116.
[12]	JIANG Yanjun, XU Dachuan, ZHANG Dongmei. An approximation algorithm for the squared metric dynamic facility location problem [J]. Operations Research Transactions, 2018, 22(3): 49-58.
[13]	CHEN Xingwen, PAN Shaohua. Equivalent Lipschitz optimization model for the group zero-norm regularized problem [J]. Operations Research Transactions, 2018, 22(3): 139-144.
[14]	WANG Yishui, XU Dachuan, WU Chenchen. A semidefinite programming rounding algorithm for correlation clustering problem [J]. Operations Research Transactions, 2018, 22(1): 67-76.
[15]	YANG Junfeng. An algorithmic review for total variation regularized data fitting problems in image processing [J]. Operations Research Transactions, 2017, 21(4): 69-83.

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 3

References 22

Related Articles 15

Recommended Articles

Metrics

Comments