Differentially Private k-Means Clustering based on Dynamic Space Partitioning using a Quad-Tree

Hanjun Goo, Woohwan Jung, Seongwoong Oh, Suyong Kwon, Kyuseok Shim

http://doi.org/10.5626/JOK.2018.45.3.288

There have recently been several studies investigating how to apply a privacy preserving technique to publish data. Differential privacy can protect personal information regardless of an attacker’s background knowledge by adding probabilistic noise to the original data. To perform differentially private k-means clustering, the existing algorithm builds a differentially private histogram and performs the k-means clustering. Since it constructs an equi-width histogram without considering the distribution of data, there are many buckets to which noise should be added. We propose a k-means clustering algorithm using a quad-tree that captures the distribution of data by using a small number of buckets. Our experiments show that the proposed algorithm shows better performance than the existing algorithm.