APDPk-Means: A New Differential Privacy Clustering Algorithm Based on Arithmetic Progression Privacy Budget Allocation

How to protect users' private data during network data mining has become a hot issue in the fields of big data and network information security. Most current researches on differential privacy k-means clustering algorithms focus on optimizing the selection of initial centroids. However, the traditional privacy budget allocation has the problem that the random noise becomes too large as the number of iterations increases, which will reduce the performance of data clustering. To solve the problem, we improved the way of privacy budget allocation in differentially private clustering algorithm DPk-means, and proposed APDPk-means, a new differential privacy clustering algorithm based on arithmetic progression privacy budget allocation. APDPk-means decomposes the total privacy budget into a decreasing arithmetic progression, allocating the privacy budgets from large to small in the iterative process, so as to ensure the rapid convergence in early iteration. The experiment results show that compared with the other differentially private k-means algorithms, APDPk-means has better performance in availability and quality of the clustering result under the same level of privacy protection.