K-Prototypes clustering method for local differential privacy

doi:10.11772/j.issn.1001-9081.2021101724

Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (12): 3813-3821.DOI: 10.11772/j.issn.1001-9081.2021101724

• Cyber security • Previous Articles

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)

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

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

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

通讯作者: 陈学斌
作者简介:张国鹏（1996—），男，甘肃武威人，硕士研究生，CCF会员，主要研究方向：数据安全、隐私保护
王豪石（1996—），男，河北邢台人，硕士研究生，CCF会员，主要研究方向：数据安全、隐私保护
翟冉（1998—），女，河北唐山人，硕士研究生，CCF会员，主要研究方向：数据安全、联邦学习
马征（1997—），男，河北唐山人，硕士研究生，CCF会员，主要研究方向：网络安全、隐私保护。
基金资助:
国家自然科学基金资助项目(U20A20179)

Abstract

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

摘要：

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

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

CLC Number:

TP309

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.

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

Figures/Tables 8

References 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

数据集	特征	特征类型
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	分类型

数据集	特征	特征类型
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	分类型

数据集	算法	隐私预算ε
数据集	算法	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

数据集	算法	隐私预算ε
数据集	算法	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

[1]	Tiankai LIANG, Bi ZENG, Guang CHEN. Federated learning survey：concepts， technologies， applications and challenges [J]. Journal of Computer Applications, 2022, 42(12): 3651-3662.
[2]	Rui SUN, Chao LI, Wei WANG, Endong TONG, Jian WANG, Jiqiang LIU. Research progress of blockchain‑based federated learning [J]. Journal of Computer Applications, 2022, 42(11): 3413-3420.
[3]	Dong ZHU, Xinchun YIN, Jianting NING. Certificateless signature scheme with strong privacy protection for internet of vehicles [J]. Journal of Computer Applications, 2022, 42(10): 3091-3101.
[4]	LI Zhuo, SONG Zihui, SHEN Xin, CHEN Xin. Local differential privacy protection mechanism for mobile crowd sensing with edge computing [J]. Journal of Computer Applications, 2021, 41(9): 2678-2686.
[5]	QIN Jing, AN Wen, JI Changqing, WANG Zumin. Review of privacy protection mechanisms in wireless body area network [J]. Journal of Computer Applications, 2021, 41(4): 970-975.
[6]	LIU Xiangyu, XIA Guoping, XIA Xiufeng, ZONG Chuanyu, ZHU Rui, LI Jiajia. Personalized privacy protection for spatio-temporal data [J]. Journal of Computer Applications, 2021, 41(3): 643-650.
[7]	Liu YANG, Yun LI. Hybrid K-anonymous feature selection algorithm [J]. Journal of Computer Applications, 2021, 41(12): 3521-3526.
[8]	CHEN Jinyu, LIU Zhaowei. Internet of vehicles system based on improved proof of vote consensus protocol [J]. Journal of Computer Applications, 2021, 41(1): 170-176.
[9]	LYU Jiayu, ZHU Zhirong, YAO Zhiqiang. Two-channel dynamic data encryption strategy in cloud computing environment [J]. Journal of Computer Applications, 2020, 40(8): 2268-2273.
[10]	YANG Yang, WANG Ruchuan. Location based service location privacy protection method based on location security in augmented reality [J]. Journal of Computer Applications, 2020, 40(5): 1364-1368.
[11]	BAI Yameng, MAN Junfeng, ZHANG Hong. Secure storage model of electronic health records based on blockchain [J]. Journal of Computer Applications, 2020, 40(4): 961-965.
[12]	LUO Huiwen, LONG Shigong. Location perturbation algorithm based on geo-indistinguishability of user’s region of interest [J]. Journal of Computer Applications, 2020, 40(3): 760-764.
[13]	Meishu ZHANG, Yabin XU. Personalized privacy protection method for data with multiple numerical sensitive attributes [J]. Journal of Computer Applications, 2020, 40(2): 491-496.
[14]	Xiangyu LIU, Jinmei CHEN, Xiufeng XIA, Manish Singh, Chuanyu ZONG, Rui ZHU. Preventing location disclosure attacks through generating dummy trajectories [J]. Journal of Computer Applications, 2020, 40(2): 479-485.
[15]	LI Gongli, LI Yu, ZHANG En, YIN Tianyu. Efficient genetic comparison scheme for user privacy protection [J]. Journal of Computer Applications, 2020, 40(1): 136-142.

K-Prototypes clustering method for local differential privacy

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 23

Related Articles 15

Recommended Articles

Metrics