Abstract:

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.

Key words: differential privacy, quad tree, dynamic partition, [k]-means

摘要：

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

关键词: 差分隐私, 四分树, 动态划分, [k]均值