A convergent differentially private k-means clustering algorithm

Zhigang Lu, Hong Shen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

12 Citations (Scopus)

Abstract

Preserving differential privacy (DP) for the iterative clustering algorithms has been extensively studied in the interactive and the non-interactive settings. However, existing interactive differentially private clustering algorithms suffer from a non-convergence problem, i.e., these algorithms may not terminate without a predefined number of iterations. This problem severely impacts the clustering quality and the efficiency of the algorithm. To resolve this problem, we propose a novel iterative approach in the interactive settings which controls the orientation of the centroids movement over the iterations to ensure the convergence by injecting DP noise in a selected area. We prove that, in the expected case, our approach converges to the same centroids as Lloyd’s algorithm in at most twice the iterations of Lloyd’s algorithm. We perform experimental evaluations on real-world datasets to show that our algorithm outperforms the state-of-the-art of the interactive differentially private clustering algorithms with a guaranteed convergence and better clustering quality to meet the same DP requirement.

Original languageEnglish
Title of host publicationAdvances in Knowledge Discovery and Data Mining - 23rd Pacific-Asia Conference, PAKDD 2019, Proceedings
EditorsZhi-Hua Zhou, Sheng-Jun Huang, Min-Ling Zhang, Zhiguo Gong, Qiang Yang
PublisherSpringer Verlag
Pages612-624
Number of pages13
ISBN (Print)9783030161477
DOIs
Publication statusPublished - 2019
Externally publishedYes
Event23rd Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2019 - Macau, China
Duration: 14 Apr 201917 Apr 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11439 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference23rd Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2019
Country/TerritoryChina
CityMacau
Period14/04/1917/04/19

Keywords

  • Adversarial machine learning
  • Differential privacy
  • k-means clustering

Fingerprint

Dive into the research topics of 'A convergent differentially private k-means clustering algorithm'. Together they form a unique fingerprint.

Cite this