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

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