基于距离与误差平方和的差分隐私K-means聚类算法

K-means Clustering Algorithm Based on Differential Privacy with Distance and Sum of Square Error

K-means算法具有简单、快速、易于实现等优点,被广泛应用于数据挖掘领域,但在聚类过程中容易造成隐私泄露。差分隐私对隐私保护做了严格定义,且能够对隐私保护量化分析。为解决差分隐私保护中K-means聚类算法在初始中心点选择上具有盲目性而造成聚类可用性低的问题,文章提出一种BDPK-means聚类算法,该算法利用距离与簇内误差平方和的方法选取合理的初始中心点进行聚类。理论分析证明,该算法满足ε-差分隐私。实验证明,相同条件下与现有DPK-means算法相比,BDPK-means算法可提高聚类的可用性。

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.