Abstract:

The k-means++ clustering algorithm is proposed to solve the problem that the accuracy of the k-means clustering algorithm is greatly affected by the selection of its initial center point. In the clustering process, the related private data needs to be protected. The differential privacy model defines an attack model with the largest background knowledge and can quantify the privacy protection strength. This paper proposes a k-means++ clustering algorithm based on Laplace mechanism for differential privacy protection (DPk-means++ clustering algorithm), and in the process of initializing the selected center point and iterating the mean center point, the noise is added according to the Laplace mechanism, and the random selection initialization center of k-means++ clustering algorithm is solved. Point to privacy leaks and iterative clustering privacy issues. Comparative analysis of dynamic changes in privacy budgets and analysis of clustering accuracy results through experiments, the DPk-means++ clustering algorithm can provide different levels of protection for data privacy under the premise of privacy budget parameters and ensuring clustering accuracy.

Key words: differential privacy protection, Laplace mechanism, k-means++, clustering