基于空间动态划分的差分隐私聚类算法

Differential Privacy Clustering Algorithm Based on Spatial Dynamic Partition

差分隐私算法作为当前研究较多的隐私保护机制之一,有着广泛应用。目前有多种基于差分隐私保护的k均值聚类算法,应用场景不一,各有缺陷。以往的算法通过均等划分数据集,构造等宽直方图进行聚类,这会导致没有数据分布的区域也被无差别插入噪声,影响聚类性能。针对这一点,提出了一种新的差分隐私聚类算法DPQTk-means,先通过构建差分隐私四分树,用大小不一的自适应存储桶动态划分数据空间,充分表示数据集同时减少噪声插入,再进行k均值聚类,证明了其满足ε-差分隐私保护。实验结果表明,DPQTk-means算法与以往的差分隐私聚类算法相比具有更好的聚类可用性,且能够在隐私保护水平较高的同时保持稳定的聚类性能。

As one of the most popular privacy protection mechanisms,the differential privacy algorithm has been widely used.At present,there are a variety of k-means clustering algorithms based on differential privacy protection.The application scenarios are different and each has its own defects.There is an algorithm that divides the data set and constructs the equal-width histograms for clustering.This causes the areas without data to be inserted into noise without any difference,which affects clustering performance.To solve this problem,a new differential privacy clustering algorithm DPQTk-means is proposed.By constructing a differential privacy quad tree,the data space is dynamically divided by adaptive buckets of different sizes to fully represent the data set and reduce noise insertion,and then do k-means clustering.It proves that it satisfiesε-differential privacy protection.Experimental results show that the DPQTk-means algorithm has better cluster availability than the previous differential privacy clustering algorithms,and can maintain stable clustering performance while maintaining a high level of privacy protection.