Computer Engineering and Applications ›› 2021, Vol. 57 ›› Issue (2): 97-103.DOI: 10.3778/j.issn.1002-8331.1912-0215

Previous Articles     Next Articles

Differential Privacy Clustering Algorithm Based on Spatial Dynamic Partition

ZHANG Kehua, CHENG Weiqing   

  1. 1.School of Computer, Nanjing University of Posts & Telecommunications, Nanjing 210023, China
    2.Key Laboratory of Computer Network & Information Integration of Ministry of Education, Southeast University, Nanjing 211189, China
  • Online:2021-01-15 Published:2021-01-14



  1. 1.南京邮电大学 计算机学院,南京 210023
    2.东南大学 计算机网络和信息集成教育部重点实验室,南京 211189


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]均值