Differential Privacy Protection [k]-means Algorithm Based on BWP Index

doi:10.3778/j.issn.1002-8331.2012-0457

Abstract

Abstract: Differential privacy is a privacy protection technology based on noise disturbance. In order to solve the problem of clustering center point deviation caused by noise under differential privacy protection, this paper proposes a differential privacy [k]-means algorithm based on BWP（between-within proportion） index. In this algorithm, BWP is introduced into the process of privacy budget allocation, and the traditional privacy budget allocation is weighted. In one iteration, different privacy budgets are allocated to the clusters with different density distributions, so as to add different random noises. Theoretical analysis shows that the new algorithm satisfies [ε]-differential privacy protection. The new algorithm is experimented on four standard data sets, and the experimental results show that the new algorithm has advantages in the availability of clustering results and the stability of the algorithm.

Key words: clustering, [k]-means algorithm, BWP index, differential privacy, privacy budget allocation

摘要： 差分隐私是一种基于噪声扰动的隐私保护技术，针对差分隐私保护下噪声导致的聚类中心点偏移较大的问题，提出了一种基于BWP（between-within proportion）指标的差分隐私[k]-means算法。算法将聚类有效性评价指标BWP引入到隐私预算分配过程中，对传统隐私预算分配进行加权处理，在一次迭代中为不同密度分布的簇分配不同的隐私预算，从而添加不同的随机噪声。理论分析表明新算法满足[ε]-差分隐私保护。基于四个标准数据集对新算法进行了实验，实验结果表明，在聚类结果的可用性以及算法的稳定性上新算法具有优势。

关键词: 聚类, [k]-means算法, BWP指标, 差分隐私, 隐私预算分配

ZHANG Yaling, QU Lingyu. Differential Privacy Protection [k]-means Algorithm Based on BWP Index[J]. Computer Engineering and Applications, 2022, 58(10): 108-115.

张亚玲, 屈玲玉. 应用BWP指标的差分隐私保护k-means算法[J]. 计算机工程与应用, 2022, 58(10): 108-115.

References

[1] GREENE C S，TAN J，UNG M，et al.Big data bioinformatics[J].Journal of Cellular Physiology，2014，229（12）：1896-1900.
[2] SWEENEY L.K-anonymity：a model for protecting privacy[J].International Journal of Uncertainty Fuzziness & Knowledge Based Systems，2002，10（5）：557-570.
[3] MACHANAVAJJHALA A，KIFER D，GEHRKE J，et al.L-diversity：privacy beyond k-anonymity[J].ACM Transactions on Knowledge Discovery from Data，2007，1（1）：3.
[4] GANTA S R，KASIVISWANATHAN S P，SMITH A.Composition attacks and auxiliary information in data privacy[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2008：265-273.
[5] DWORK C.Differential privacy[C]//Proceedings of the 33rd International Conference on Automata，Languages and Programming-Volume Part II.Berlin，Heidelberg：Springer，2006：1-19.
[6] 熊平，朱天清，王晓峰.差分隐私保护及其应用[J].计算机学报，2014，37（1）：101-122.
XIONG P，ZHU T Q，WANG X F.A survey on differential privacy and applications[J].Chinese Journal of Computers，2014，37（1）：101-122.
[7] DWORK C.Differential privacy：a survey of results[C]//International Conference on Theory and Applications of Models of Computation.Berlin，Heidelberg：Springer，2008：1-19.
[8] DWORK C，MCSHERRYF，NISSIM K，et al.Calibrating noise to sensitivity in private data analysis[C]//Theory of Cryptography Conference，2006：265-284.
[9] DWORK C，LEI J.Differential privacy and robust statistics[C]//Proceedings of the 41st Annual ACM Symposium on Theory of Computing，2009：371-380.
[10] DWORK C.Differential privacy[M]//Encyclopedia of cryptography and security.Berlin：Springer，2011：338-340.
[11] DWORK C.A firm foundation for private data analysis[J].Communications of the ACM，2011，54（1）：86-95.
[12] 何贤芒，王晓阳，陈华辉，等.差分隐私保护参数ε的选取研究[J].通信学报，2015，36（12）：124-130.
HE X M，WANG X Y，CHEN H H，et al.Study on choosing the parameter[ε]in differential privacy[J].Journal on Communications，2015，36（12）：124-130.
[13] BLUM A，DWORK C，MCSHERRY F，et al.Practical privacy：the SuLQ framework[C]//Proceedings of the 24th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems，2005：128-138.
[14] NISSIM K，RASKHODNIKOVA S，SMITH A.Smooth sensitivity and sampling in private data analysis[C]//Proceedings of the 39th Annual ACM Symposium on Theory of Computing，2007：75-84.
[15] 李杨，郝志峰，温雯，等.差分隐私保护K-means聚类方法研究[J].计算机科学，2013，40（3）：287-290.
LI Y，HAO Z F，WEN W，et al.Research on differential privacy preserving K-means clustering[J].Computer Science，2013，40（3）：287-290.
[16] YU Q，LUO Y，CHEN C，et al.Outlier-eliminated k-means clustering algorithm based on differential privacy pre-
servation[J].Applied Intelligence，2016，45（4）：1179-1191.
[17] REN J，XIONG J，YAO G，et al.DPLK-means：a novel differential privacy k-means mechanism[C]//2017 IEEE 2nd International Conferenceon Data Science in Cyberspace，2017：133-139.
[18] 胡闯，杨庚，白云璐.面向差分隐私保护的聚类算法[J].计算机科学，2019，46（2）：120-126.
HU C，YANG G，BAI Y L.Clustering algorithm in differential privacy preserving[J].Computer Science，2019，46（2）：120-126.
[19] 樊一康，刘建伟.支持差分隐私保护及离群点消除的并行K-means算法[J].计算机应用研究，2019，36（6）：1776-1781.
FAN Y K，LIU J W.Parallel K-means algorithm with differential privacy preservation and outlier pruning[J].Application Research of Computers，2019，36（6）：1776-1781.
[20] FAN Z，XU X.APDPK-means：a new differential privacy clustering algorithm based on arithmetic progression privacy budget allocation[C]//2019 IEEE 21st International Conference on High Performance Computing and Communications，IEEE 17th International Conference on Smart City，IEEE 5th International Conference on Data Science and Systems，Zhangjiajie，2019：1737-1742.
[21] MCSHERRY F.Privacy integrated queries：an extensible platform for privacy-preserving data analysis[C]//2009 ACM SIGMOD International Conference on Management of Data.New York：ACM，2009：19-30.
[22] AGGARWAL C C.Outlier analysis[M].Berlin：Springer，2015：237-263.
[23] 周世兵，徐振源，唐旭清.K-means算法最佳聚类数确定方法[J].计算机应用，2010，30（8）：1995-1998.
ZHOU S B，XU Z Y，TANG X Q.Method for determining optimal number of clusters in K-means clustering algorithm[J].Journal of Computer Applications，2010，30（8）：1995-1998.
[24] VALENTINI G，DIETTERICH T G.Bias-variance analysis of support vector machines for the development of SVM-based ensemble methods[J].Journal of Machine Learning Research，2004，5（7）：725-775.
[25] ANGIULLI F，FASSETTI F.DOLPHIN：an efficient algorithm for mining distance based outliers in very large datasets[J].ACM Transactions on Knowledge Discovery from Data，2009，3（1）：1-57.