Greedy centroid initialization for federated K-means

Kun Yang, Mohammad Mohammadi Amiri, Sanjeev R. Kulkarni

Research output: Contribution to journalArticlepeer-review

Abstract

We study learning from unlabeled data distributed across clients in a federated fashion where raw data do not leave the corresponding devices. We develop a K-means clustering algorithm within this federated setting where the local datasets are clustered at the clients, and a server generates the global clusters after aggregating the local ones. Given the importance of initialization on the federated K̲-means algorithm (FKM), our objective is to find better initial centroids by utilizing the local data stored on each client. To this end, we start the centroid initialization at the clients, rather than at the server, since the server initially lacks any preliminary insight into the clients’ data. The clients first select their local initial clusters and subsequently share their clustering information (including cluster centroids and sizes) with the server. The server then employs a greedy algorithm to determine the global initial centroids based on the information received from the clients. We refer to this idea as G-FKM. Numerical results obtained from both synthetic and public datasets demonstrate that our proposed algorithm demonstrates accelerated convergence, exhibiting reduced within-cluster sum of squares (WCSS¯) and higher adjusted Rand Index compared to three distinct federated K-means variants. This improvement comes at a relatively low cost of sending limited additional information from the clients to the server, rather than conducting the initialization entirely at the server. Furthermore, we have also observed that the proposed algorithm performs better than the centralized algorithm for cases where the data distribution across the clients is highly skewed.

Original languageEnglish (US)
Pages (from-to)3393-3425
Number of pages33
JournalKnowledge and Information Systems
Volume66
Issue number6
DOIs
StatePublished - Jun 2024

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Human-Computer Interaction
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • Clustering
  • Federated learning
  • K-means
  • Machine learning

Fingerprint

Dive into the research topics of 'Greedy centroid initialization for federated K-means'. Together they form a unique fingerprint.

Cite this