• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

Zhang, Dongmei (Zhang, Dongmei.) | Cheng, Yukun (Cheng, Yukun.) | Li, Min (Li, Min.) | Wang, Yishui (Wang, Yishui.) | Xu, Dachuan (Xu, Dachuan.) (Scholars:徐大川)

Indexed by:

CPCI-S EI Scopus SCIE

Abstract:

In the spherical k-means problem (SKMP), which is a well-studied clustering problem in text mining, we are given an n-point set D in d-dimensional unit sphere Sd, and an integer k <= n. The goal is to find a center subset S c Sd with vertical bar k vertical bar <= k that minimizes the sum of cosine dissimilarity measure for each point in D to the nearest center. We prove that any gamma-approximation algorithm for the k-means problem (KMP) can be adapted to the SKMP with 2 gamma-approximation ratio. It follows that there is a local search (18 + c)-approximation algorithm for the SKMP, by leveraging the classical local search (9 + c)-approximation algorithm for the KMP. Therefore, an interesting problem arises, that is whether there exists an approximation algorithm using local search scheme directly for the SKMP. In this paper, we present a local search approximation algorithm for the SKMP and prove its performance guarantee is (2(4 + root 7) + c). We also conduct numerical computation to show the efficiency of the local search approximation algorithm by single-swap operation in the end. (C) 2020 Elsevier B.V. All rights reserved.

Keyword:

Local search Spherical k-means Approximation algorithm Data mining

Author Community:

  • [ 1 ] [Zhang, Dongmei]Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China
  • [ 2 ] [Cheng, Yukun]Suzhou Univ Sci & Technol, Sch Business, Suzhou Key Lab Big Data & Informat Serv, Suzhou 215009, Peoples R China
  • [ 3 ] [Li, Min]Shandong Normal Univ, Sch Math & Stat, Jinan 250014, Peoples R China
  • [ 4 ] [Wang, Yishui]Chinese Acad Sci, Shenzhen Inst Adv Technol, Shenzhen 518055, Peoples R China
  • [ 5 ] [Xu, Dachuan]Beijing Univ Technol, Dept Operat Res & Sci Comp, Beijing 100124, Peoples R China

Reprint Author's Address:

  • [Cheng, Yukun]Suzhou Univ Sci & Technol, Sch Business, Suzhou Key Lab Big Data & Informat Serv, Suzhou 215009, Peoples R China

Show more details

Related Keywords:

Related Article:

Source :

THEORETICAL COMPUTER SCIENCE

ISSN: 0304-3975

Year: 2021

Volume: 853

Page: 65-77

1 . 1 0 0

JCR@2022

ESI Discipline: COMPUTER SCIENCE;

ESI HC Threshold:87

JCR Journal Grade:4

Cited Count:

WoS CC Cited Count: 3

SCOPUS Cited Count: 5

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 7

Affiliated Colleges:

Online/Total:1101/10563842
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.