面向本地差分隐私的K-Prototypes聚类方法

doi:10.11772/j.issn.1001-9081.2021101724

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (12): 3813-3821.DOI: 10.11772/j.issn.1001-9081.2021101724

所属专题：网络空间安全

面向本地差分隐私的K-Prototypes聚类方法

张国鹏¹^,²^,³, 陈学斌¹^,²^,³(), 王豪石¹^,²^,³, 翟冉¹^,²^,³, 马征¹^,²^,³

^1.华北理工大学理学院, 河北唐山 063210
^2.河北省数据科学与应用重点实验室(华北理工大学), 河北唐山 063210
^3.唐山市数据科学重点实验室(华北理工大学), 河北唐山 063210

收稿日期:2021-10-08 修回日期:2021-12-27 接受日期:2022-01-05 发布日期:2022-01-24 出版日期:2022-12-10
通讯作者: 陈学斌
作者简介:张国鹏（1996—），男，甘肃武威人，硕士研究生，CCF会员，主要研究方向：数据安全、隐私保护
王豪石（1996—），男，河北邢台人，硕士研究生，CCF会员，主要研究方向：数据安全、隐私保护
翟冉（1998—），女，河北唐山人，硕士研究生，CCF会员，主要研究方向：数据安全、联邦学习
马征（1997—），男，河北唐山人，硕士研究生，CCF会员，主要研究方向：网络安全、隐私保护。
基金资助:
国家自然科学基金资助项目(U20A20179)

K-Prototypes clustering method for local differential privacy

Guopeng ZHANG¹^,²^,³, Xuebin CHEN¹^,²^,³(), Haoshi WANG¹^,²^,³, Ran ZHAI¹^,²^,³, Zheng MA¹^,²^,³

^1.College of Science，North China University of Science and Technology，Tangshan Hebei 063210，China
^2.Hebei Key Laboratory of Data Science and Application （North China University of Science and Technology），Tangshan Hebei 063010，China
^3.Tangshan Key Laboratory of Data Science （North China University of Science and Technology），Tangshan Hebei 063010，China

Received:2021-10-08 Revised:2021-12-27 Accepted:2022-01-05 Online:2022-01-24 Published:2022-12-10
Contact: Xuebin CHEN
About author:ZHANG Guopeng， born in 1996， M. S. candidate. His research interests include data security， privacy protection.
WANG Haoshi， born in 1996， M. S. candidate. His research interests include data security， privacy protection.
ZHAI Ran， born in 1998， M. S. candidate. Her research interests include data security， federated learning.
MA Zheng， born in 1997， M. S. candidate. His research interests include network security， privacy protection.
Supported by:
National Natural Science Foundation of China(U20A20179)

摘要/Abstract

摘要：

为了在聚类分析中保护数据隐私的同时确保数据的可用性，提出一种基于本地化差分隐私（LDP）技术的隐私保护聚类方案——LDPK-Prototypes。首先，用户对混合型数据集进行编码；其次，采用随机响应机制对敏感数据进行扰动，而第三方在收集到用户的扰动数据后以最大限度恢复原始数据集；然后，执行K-Prototypes聚类算法，在聚类过程中，使用相异性度量方法确定初始聚类中心，并利用熵权法重新定义新的距离计算公式。理论分析和实验结果表明，所提方案与基于中心化差分隐私（CDP）技术的ODPC算法相比，在Adult和Heart数据集上的平均准确率分别提高了2.95%和12.41%，有效提高了聚类的可用性。同时，LDPK-Prototypes扩大了数据之间的差异性，有效避免了局部最优，提高了聚类算法的稳定性。

关键词: 本地化差分隐私, K-Prototypes, 随机响应机制, 熵权法, 隐私保护

Abstract:

In order to protect data privacy while ensuring data availability in clustering analysis， a privacy protection clustering scheme based on Local Differential Privacy （LDP） technique called LDPK-Prototypes （LDP K-Prototypes） was proposed. Firstly， the hybrid dataset was encoded by users. Then， a random response mechanism was used to disturb the sensitive data， and after collecting the users’ disturbed data， the original dataset was recovered by the third party to the maximum extent. After that， the K-Prototypes clustering algorithm was performed. In the clustering process， the initial clustering center was determined by the dissimilarity measure method， and the new distance calculation formula was redefined by the entropy weight method. Theoretical analysis and experimental results show that compared with the ODPC （Optimizing and Differentially Private Clustering） algorithm based on the Centralized Differential Privacy （CDP） technique， the proposed scheme has the average accuracy on Adult and Heart datasets improved by 2.95% and 12.41% respectively， effectively improving the clustering usability. Meanwhile， LDPK-Prototypes expands the difference between data， effectively avoids local optimum， and improves the stability of the clustering algorithm.

Key words: Local Differential Privacy (LDC), K-Prototypes, random response mechanism, entropy weight method, privacy protection

中图分类号:

TP309

张国鹏, 陈学斌, 王豪石, 翟冉, 马征. 面向本地差分隐私的K-Prototypes聚类方法[J]. 计算机应用, 2022, 42(12): 3813-3821.

Guopeng ZHANG, Xuebin CHEN, Haoshi WANG, Ran ZHAI, Zheng MA. K-Prototypes clustering method for local differential privacy[J]. Journal of Computer Applications, 2022, 42(12): 3813-3821.

图/表 8

图1 数据隐私处理框架

Fig.1 Data privacy processing framework

图2 LDPK-Prototypes流程

Fig.2 Flow chart of LDPK-Prototypes

图3 LDPK-prototypes聚类方案

Fig.3 LDPK-prototypes clustering scheme

表1 不同数据集的特征

Tab.1 Characteristics of different dataset

数据集	特征	特征类型
Adult	Age	数值型
	Fnlwgt	数值型
	Education-num	数值型
	Hours-peer-work	数值型
	Workclass	分类型
	Education	分类型
	Marital-status	分类型
	Occupation	分类型
	Relationship	分类型
	Nativa-country	数值型
Heart	Age	数值型
	ChestPainType	分类型
	RestingBP	数值型
	Cholesterol	数值型
	RestingECG	分类型
	MaxHR	数值型
	ExerciseAngina	分类型
	ST_Slope	分类型

图4 不同数据集上不同ε下的NICV值比较

Fig. 4 Comparison of NICV value under different ε values on different datasets

图5 不同数据集上不同ε值下F-measure值的比较

Fig. 5 Comparison of F-measure value under different ε values on different datasets

图6 不同数据集上RI值与均值对比

Fig. 6 RI value and mean value comparison on different datasets

表2 不同数据集上RI值的对比

Tab. 2 RI value comparison on different datasets

数据集	算法	隐私预算ε
数据集	算法	0.01	0.10	0.20	0.50	1.00	1.50	2.00
Adult	ODPC	0.508	0.508	0.506	0.507	0.507	0.506	0.509
Adult	LDPK-Prototypes	0.448	0.448	0.530	0.536	0.507	0.534	0.549
Heart	ODPC	0.500	0.505	0.514	0.506	0.518	0.509	0.520
Heart	LDPK-Prototypes	0.532	0.543	0.550	0.540	0.583	0.621	0.646

参考文献 23

1	DWORK C. Differential privacy： a survey of results［C］// Proceedings of the 2008 International Conference on Theory and Applications of Models of Computation， LNCS 4978. Berlin： Springer， 2008：1-19.
2	HUANG Z X. Clustering large data sets with mixed numeric and categorical values［C］// Proceedings of the 1st Pacific-Asia Conference on Knowledge Discovery and Data Mining. Cham： Springer， 1997： 21-34.
3	王巧玲，乔非，蒋友好. 基于聚合距离参数的改进K-means算法［J］. 计算机应用， 2019， 39（9）： 2586-2590. 10.11772/j.issn.1001-9081.2019030485
	WANG Q L， QIAO F， JIANG Y H. Improved K-means algorithm based on aggregation distance parameter［J］. Journal of Computer Applications， 2019， 39（9）： 2586-2590. 10.11772/j.issn.1001-9081.2019030485
4	李仁侃，叶东毅. 粗糙K-Modes聚类算法［J］. 计算机应用， 2011， 31（1）： 97-100. 10.3724/sp.j.1087.2011.00097
	LI R K， YE D Y. Rough K-Modes clustering algorithm［J］. Journal of Computer Applications， 2011， 31（1）： 97-100. 10.3724/sp.j.1087.2011.00097
5	叶青青，孟小峰，朱敏杰，等. 本地化差分隐私研究综述［J］. 软件学报. 2018， 29（7）： 1981-2005.
	YE Q Q， MENG X F， ZHU M J， et al. Survey on local differential privacy［J］. Journal of Software， 2018， 29（7）：1981-2005.
6	WANG T， ZHANG X F， FENG J Y， et al. A comprehensive survey on local differential privacy toward data statistics and analysis［J］. Sensors， 2020， 20（24）： No.7030. 10.3390/s20247030
7	ERLINGSSON Ú， PIHUR V， KOROLOVA A. RAPPOR： randomized aggregatable privacy-preserving ordinal response［C］// Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2014： 1054-1067. 10.1145/2660267.2660348
8	WARNER S L. Randomized response： a survey technique for eliminating evasive answer bias［J］. Journal of the American Statistical Association， 1965， 60（309）： 63-69. 10.1080/01621459.1965.10480775
9	NGUYÊN T T， XIAO X K， YANG Y， et al. Collecting and analyzing data from smart device users with local differential privacy［EB/OL］. （2016-06-16）［2021-10-08］..
10	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. New York： ACM， 2005： 128-138. 10.1145/1065167.1065184
11	REN J， XIONG J B， YAO Z Q， et al. DPLK-means： a novel differential privacy K-means mechanism［C］// Proceedings of the IEEE 2nd International Conference on Data Science in Cyberspace. Piscataway： IEEE， 2017： 133-139. 10.1109/dsc.2017.64
12	ZHANG Y L， LIU N， WANG S P. A differential privacy protecting K-means clustering algorithm based on contour coefficients［J］. PLoS ONE， 2018， 13（11）： No.e206832. 10.1371/journal.pone.0206832
13	陈恒恒，倪志伟，朱旭辉，等. 基于聚类分析的差分隐私高维数据发布方法［J］. 计算机应用， 2021， 41（9）： 2578-2585. 10.11772/j.issn.1001-9081.2020111786
	CHEN H H， NI Z W， ZHU X H， et al. Differential privacy high-dimensional data publishing method based on clustering analysis［J］. Journal of Computer Applications， 2021， 41（9）： 2578-2585. 10.11772/j.issn.1001-9081.2020111786
14	XIA C， HUA J Y， TONG W， et al. Distributed K-Means clustering guaranteeing local differential privacy［J］. Computers and Security， 2020， 90： No.101699. 10.1016/j.cose.2019.101699
15	彭春春，陈燕俐，荀艳梅. 支持本地化差分隐私保护的k-modes聚类方法［J］. 计算机科学， 2021， 48（2）： 105-113. 10.11896/jsjkx.200700172
	PENG C C， CHEN Y L， XUN Y M. k-modes clustering method supporting localized differential privacy protection［J］. Computer Science， 2021， 48（2）： 105-113. 10.11896/jsjkx.200700172
16	LV Z F， WANG L R， GUAN Z T， et al. An optimizing and differentially private clustering algorithm for mixed data in SDN-based smart grid［J］. IEEE Access， 2019， 7： 45773-45782. 10.1109/access.2019.2909048
17	DUCHI J C， JORDAN M I， WAINWRIGHT M J. Local privacy and statistical minimax rates［C］// Proceedings of the 51st Annual Allerton Conference on Communication， Control， and Computing. Piscataway： IEEE， 2013： 1592-1592. 10.1109/allerton.2013.6736718
18	McSHERRY F D. Privacy integrated queries： an extensible platform for privacy-preserving data analysis［C］// Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2009： 19-30. 10.1145/1559845.1559850
19	贾子琪，宋玲. 一种面向混合型数据聚类的k-prototypes聚类算法［J］. 小型微型计算机系统， 2020， 41（9）： 1845-1852. 10.3969/j.issn.1000-1220.2020.09.009
	JIA Z Q， SONG L. k-prototypes clustering algorithm for mixed data clustering［J］. Journal of Chinese Computer Systems， 2020， 41（9）： 1845-1852. 10.3969/j.issn.1000-1220.2020.09.009
20	廖纪勇，吴晟，刘爱莲. 基于相异性度量选取初始聚类中心改进的K-means聚类算法［J］. 控制与决策， 2021， 36（12）：3083-3090. 10.13195/j.kzyjc.2020.0554
	LIAO J Y， WU S， LIU A L. Improved K-means clustering algorithm for selecting initial clustering centers based on dissimilarity measure［J］. Control and Decision， 2021， 36（12）：3083-3090. 10.13195/j.kzyjc.2020.0554
21	JIANG H， YI S H， LI J， et al. Ant clustering algorithm with K-harmonic means clustering［J］. Expert Systems with Applications， 2010， 37（12）： 8679-8684. 10.1016/j.eswa.2010.06.061
22	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. New York： ACM， 2007： 75-84. 10.1145/1250790.1250803
23	李顺勇，顾嘉成. 一种增强的K-prototypes混合数据聚类算法［J］. 陕西科技大学学报， 2021， 39（2）：183-188. 10.3969/j.issn.1000-5811.2021.02.028
	LI S Y， GU J C. An enhanced K-prototypes mixed data clustering algorithm［J］. Journal of Shaanxi University of Science and Technology， 2021， 39（2）：183-188. 10.3969/j.issn.1000-5811.2021.02.028

[1]	陈学斌, 任志强, 张宏扬. 联邦学习中的安全威胁与防御措施综述[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1663-1672.
[2]	刘沛骞, 王水莲, 申自浩, 王辉. 基于轨迹扰动和路网匹配的位置隐私保护算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1546-1554.
[3]	高改梅, 张瑾, 刘春霞, 党伟超, 白尚旺. 基于区块链与CP-ABE策略隐藏的众包测试任务隐私保护方案[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 811-818.
[4]	马海峰, 李玉霞, 薛庆水, 杨家海, 高永福. 用于实现区块链隐私保护的属性基加密方案[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 485-489.
[5]	高瑞, 陈学斌, 张祖篡. 面向部分图更新的动态社交网络隐私发布方法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3831-3838.
[6]	贾淼, 姚中原, 祝卫华, 高婷婷, 斯雪明, 邓翔. 零知识证明赋能区块链的进展与展望[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3669-3677.
[7]	王一帆, 林绍福, 李云江. 基于区块链和零知识证明的高速公路自由流收费方法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3741-3750.
[8]	王伊婷, 万武南, 张仕斌, 张金全, 秦智. 基于SM9算法的可链接环签名方案[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3709-3716.
[9]	梁静, 万武南, 张仕斌, 张金全, 秦智. 面向主从链的慈善系统溯源存储模型[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3751-3758.
[10]	方鹏, 赵凡, 王保全, 王轶, 蒋同海. 区块链3.0的发展、技术与应用[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3647-3657.
[11]	陈学斌, 屈昌盛. 面向联邦学习的后门攻击与防御综述[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3459-3469.
[12]	周辉, 陈玉玲, 王学伟, 张洋文, 何建江. 基于生成对抗网络的联邦学习深度影子防御方案[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 223-232.
[13]	崔剑阳, 蔡英, 张宇, 范艳芳. 车载自组织网络中格基签密的可认证隐私保护方案[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 233-241.
[14]	黄硕, 李艳辉, 曹建秋. 本地化差分隐私下的频繁序列模式挖掘算法PrivSPM[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2057-2064.
[15]	蓝梦婕, 蔡剑平, 孙岚. 非独立同分布数据下的自正则化联邦学习优化方法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2073-2081.

面向本地差分隐私的K-Prototypes聚类方法

K-Prototypes clustering method for local differential privacy

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 23

相关文章 15

编辑推荐

Metrics