@article{M10D03764,
title = "Differentially Private k-Means Clustering based on Dynamic Space Partitioning using a Quad-Tree",
journal = "Journal of KIISE, JOK",
year = "2018",
issn = "2383-630X",
doi = "10.5626/JOK.2018.45.3.288",
author = "Hanjun Goo,Woohwan Jung,Seongwoong Oh,Suyong Kwon,Kyuseok Shim",
keywords = "differential privacy,k-means clustering,quad tree,histogram",
abstract = "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."
}