Abstract:

K-means algorithm is simple, fast and easy to implement. It is widely used in the field of data mining, but it is easy to cause privacy leakage in the process of clustering. Differential privacy has a strict definition of privacy protection, and it can be used for quantitative analysis of privacy protection. In order to solve the problem that the K-means clustering algorithm based on differential privacy has blindness in the selection of the initial center points, which results in low clustering availability, a BDPK-means clustering algorithm is proposed. The algorithm uses the distance and the sum of squared errors within the cluster to select the reasonable initial center points for clustering. The theory proves that the algorithm satisfies the ε-differential privacy. Through simulation experiments, BDPK-means algorithm is compared with DPK-means algorithm under the same conditions, and the results show that BDPK-means algorithm can improve the availability of clustering.

Key words: privacy protection, data mining, differential privacy, K-means clustering, SSE