The spherical k-means plus plus algorithm via local search scheme

被引：2

作者：

Tian, Xiaoyun ^{[1
]}

Xu, Dachuan ^{[1
]}

Du, Donglei ^{[2
]}

Gai, Ling ^{[3
]}

机构：

[1] Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China

[2] Univ New Brunswick, Fac Management, Fredericton, NB E3B 9Y2, Canada

[3] Donghua Univ, Glorious Sun Sch Business & Management, Shanghai 200051, Peoples R China

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2022年 / 44卷 / 04期

基金：

北京市自然科学基金; 中国国家自然科学基金; 加拿大自然科学与工程研究理事会;

关键词：

Spherical k-means; Local search; Seeding algorithm; Approximation algorithm; CLUSTERING-ALGORITHM;

D O I：

10.1007/s10878-021-00737-x

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The spherical k-means problem (SKMP) is an important variant of the k-means clustering problem (KMP). In this paper, we consider the SKMP, which aims to divide the n points in a given data point set S into k clusters so as to minimize the total sum of the cosine dissimilarity measure from each data point to their respective closest cluster center. Our main contribution is to design an expected constant approximation algorithm for the SKMP by integrating the seeding algorithm for the KMP and the local search technique. By utilizing the structure of the clusters, we further obtain an improved LocalSearch++ algorithm involving epsilon k local search steps.

引用

页码：2375 / 2394

页数：20

共 14 条

[1] [Anonymous], P 58 ANN S FDN COMP, P61
[2] Arthur D, 2007, PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P1027
[3] Concept decompositions for large sparse text data using clustering
Dhillon, IS
Modha, DS
[J]. MACHINE LEARNING, 2001, 42 (1-2) : 143 - 175
[4] TURNING BIG DATA INTO TINY DATA: CONSTANT-SIZE CORESETS FOR k-MEANS, PCA, AND PROJECTIVE CLUSTERING
Feldman, Dan
Schmidt, Melanie
Sohler, Christian
[J]. SIAM JOURNAL ON COMPUTING, 2020, 49 (03) : 601 - 657
[5] Hornik K, 2012, J STAT SOFTW, V50, P1
[6] Jain A. K., 1988, ALGORITHMS CLUSTERIN, V6
[7] Data clustering: A review
Jain, AK
Murty, MN
Flynn, PJ
[J]. ACM COMPUTING SURVEYS, 1999, 31 (03) : 264 - 323
[8] A local search approximation algorithm for k-means clustering
Kanungo, T
Mount, DM
Netanyahu, NS
Piatko, CD
Silverman, R
Wu, AY
[J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2004, 28 (2-3): : 89 - 112
[9] An efficient k-means clustering algorithm:: Analysis and implementation
Kanungo, T
Mount, DM
Netanyahu, NS
Piatko, CD
Silverman, R
Wu, AY
[J]. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2002, 24 (07) : 881 - 892
[10] The seeding algorithms for spherical k-means clustering
Li, Min
Xu, Dachuan
Zhang, Dongmei
Zou, Juan
[J]. JOURNAL OF GLOBAL OPTIMIZATION, 2020, 76 (04) : 695 - 708

← 1 2 →