TY  - JOUR
T1  - Differentially Private k-Means Clustering based on Dynamic Space Partitioning using a Quad-Tree
AU  - Goo, Hanjun 
AU  - Jung, Woohwan 
AU  - Oh, Seongwoong 
AU  - Kwon, Suyong 
AU  - Shim, Kyuseok 
JO  - Journal of KIISE, JOK
PY  - 2018
DA  - 2018/1/14
DO  - 10.5626/JOK.2018.45.3.288
KW  - differential privacy
KW  - k-means clustering
KW  - quad tree
KW  - histogram
AB  - 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.