基于差分隐私保护的谱聚类算法

doi:10.11772/j.issn.1001-9081.2018040888

计算机应用 ›› 2018, Vol. 38 ›› Issue (10): 2918-2922.DOI: 10.11772/j.issn.1001-9081.2018040888

基于差分隐私保护的谱聚类算法

郑孝遥^1,2, 陈冬梅^1,2, 刘雨晴^1,2, 尤浩^1,2, 汪祥舜^1,2, 孙丽萍^1,2

1. 安徽师范大学计算机与信息学院, 安徽芜湖 241002;
2. 网络与信息安全安徽省重点实验室(安徽师范大学), 安徽芜湖 241002

收稿日期:2018-04-28 修回日期:2018-07-12 出版日期:2018-10-10 发布日期:2018-10-13
通讯作者: 郑孝遥
作者简介:郑孝遥(1981-),男,安徽芜湖人,副教授,博士研究生,CCF会员,主要研究方向:信息安全、个性化推荐;陈冬梅(1994-),女,安徽天长人,硕士研究生,主要研究方向:信息安全、智能计算;刘雨晴(1994-),女,安徽阜阳人,硕士研究生,主要研究方向:信息安全、数据挖掘;尤浩(1997-),男,安徽颍上人,主要研究方向:信息安全、个性化推荐;汪祥舜(1992-),男,安徽安庆人,硕士研究生,主要研究方向:个性化推荐;孙丽萍(1980-),女,安徽芜湖人,教授,博士,CCF会员,主要研究方向:空间数据处理、智能计算。
基金资助:
国家自然科学基金资助项目（61772034，61602009）；安徽省自然科学基金资助项目（1808085MF172）。

Spectral clustering algorithm based on differential privacy protection

ZHENG Xiaoyao^1,2, CHEN Dongmei^1,2, LIU Yuqing^1,2, YOU Hao^1,2, WANG Xiangshun^1,2, SUN Liping^1,2

1. School Computer and Information, Anhui Normal University, Wuhu Anhui 241002, China;
2. Anhui Provincial Key Laboratory of Network and Information Security(Anhui Normal University), Wuhu Anhui 241002, China

Received:2018-04-28 Revised:2018-07-12 Online:2018-10-10 Published:2018-10-13
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61772034, 61602009), the Natural Science Foundation of Anhui Province (1808085MF172).

摘要/Abstract

摘要： 针对传统的聚类算法存在隐私泄露的风险，提出一种基于差分隐私保护的谱聚类算法。该算法基于差分隐私模型，利用累计分布函数生成满足拉普拉斯分布的随机噪声，将该噪声添加到经过谱聚类算法计算的样本相似度的函数中，干扰样本个体之间的权重值，实现样本个体间的信息隐藏以达到隐私保护的目的。通过UCI数据集上的仿真实验，表明该算法能够在一定的信息损失度范围内实现有效的数据聚类，也可以对聚类数据进行保护。

关键词: 差分隐私, 谱聚类, 敏感数据, 隐私泄露

Abstract: Aiming at the problem of privacy leakage in the application of traditional clustering algorithm, a spectral clustering algorithm based on differential privacy protection was proposed. Based on the differential privacy model, the cumulative distribution function was used to generate random noise that satisfies Laplasse distribution. Then the noise was added to the sample similarity function calculated by the spectral clustering algorithm, which disturbed the weight values between the individual samples and realized information hiding between sample individuals for privacy protection. Experimental results of UCI dataset verify that the proposed algorithm can achieve effective data clustering within a certain degree of information loss, and can also protect clustered data.

Key words: differential privacy, spectral clustering, sensitive data, privacy leakage

中图分类号:

TP309.2

郑孝遥, 陈冬梅, 刘雨晴, 尤浩, 汪祥舜, 孙丽萍. 基于差分隐私保护的谱聚类算法[J]. 计算机应用, 2018, 38(10): 2918-2922.

ZHENG Xiaoyao, CHEN Dongmei, LIU Yuqing, YOU Hao, WANG Xiangshun, SUN Liping. Spectral clustering algorithm based on differential privacy protection[J]. Journal of Computer Applications, 2018, 38(10): 2918-2922.

参考文献

[1] SHMUELI E, TASSA T. Privacy by diversity in sequential releases of databases[J]. Information Sciences, 2015, 298:344-372.
[2] NI W, GU M, CHEN X. Location privacy-preserving k nearest neighbor query under user's preference[J]. Knowledge-Based Systems, 2016, 103(1):19-27.
[3] TRUJILLO-RASUA R, DOMINGO-FERRER J. On the privacy offered by (k, δ) -anonymity[J]. Information Systems, 2013, 38(4):491-494.
[4] 张啸剑, 孟小峰. 面向数据发布和分析的差分隐私保护[J]. 计算机学报, 2014,37(4):927-949. (ZHANG X J, MENG X F. Differential privacy in data publication and analysis[J]. Chinese Journal of Computers, 2014,37(4):927-949.)
[5] OLIVEIRA S R M, ZAÏANE O R. Achieving privacy preservation when sharing data for clustering[M]//JONKER W, PETKOVIC M. Secure Data Management. Berlin:Springer, 2004:67-82.
[6] MUKHERJEE S, CHEN Z, GANGOPADHYAY A. A privacy-preserving technique for Euclidean distance-based mining algorithms using Fourier-related transforms[J]. VLDB Journal, 2006, 15(4):293-315.
[7] BLUM A, DWORK C, McSHERRY F, et al. Practical privacy:the SuLQ framework[C]//Proceedings of the Twenty-Fourth ACM Sigmod-Sigact-Sigart Symposium on Principles of Database Systems. New York:ACM, 2005:128-138.
[8] DWORK C, NAOR M, PITASSI T, et al. Pan-private streaming algorithms[EB/OL].[2018-01-10]. http://nebula.wsimg.com/e2c5b9c40e7ca5ee436f9cb470b3ea7b?AccessKeyId=0EF19C92671ED94CE585&disposition=0&alloworigin=1.
[9] 李杨, 郝志峰, 温雯, 等. 差分隐私保护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.)
[10] 李洪成, 吴晓平, 陈燕. MapReduce框架下支持差分隐私保护的k-means聚类方法[J]. 通信学报. 2016, 37(2):124-130. (LI H C, WU X P, CHEN Y. k-means clustering method preserving differential privacy in MapReduce framework[J]. Journal on Communications, 2016, 37(2):124-130.)
[11] 吴伟民, 黄焕坤. 基于差分隐私保护的DP-DBScan聚类算法研究[J]. 计算机工程与科学, 2015, 37(4):830-834. (WU W M, HUANG H K. A DP-DBScan clustering algorithm based on differential privacy preserving[J]. Computer Engineering and Science, 2015, 37(4):830-834.)
[12] 刘晓迁, 李千目. 基于聚类匿名化的差分隐私保护数据发布方法[J]. 通信学报, 2016, 37(5):125-129. (LIU X Q, LI Q M. Differentially private data release based on clustering anonymization[J]. Journal on Communications, 2016, 37(5):125-129.)
[13] MATKOVIC Y, MATKOVIC Y. Robust spectral clustering for noisy data:modeling sparse corruptions improves latent embeddings[C]//Proceedings of the 2017 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2017:737-746.
[14] 熊平, 朱天清, 王晓峰. 差分隐私保护及其应用[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.)
[15] DWORK C. Differential privacy:a survey of results[C]//Proceedings of the 2008 International Conference on Theory and Applications of Models of Computation. Berlin:Springer, 2008:1-19.
[16] McSHERRY F, TALWAR K. Mechanism design via differential privacy[C]//Proceedings of the 2007 IEEE Symposium on Foundations of Computer Science. Piscataway, NJ:IEEE, 2007:94-103.

基于差分隐私保护的谱聚类算法

Spectral clustering algorithm based on differential privacy protection

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	陈恒恒, 倪志伟, 朱旭辉, 金媛媛, 陈千. 基于聚类分析的差分隐私高维数据发布方法[J]. 计算机应用, 2021, 41(9): 2578-2585.
[2]	李卓, 宋子晖, 沈鑫, 陈昕. 边缘计算支持下的移动群智感知本地差分隐私保护机制[J]. 计算机应用, 2021, 41(9): 2678-2686.
[3]	祝承, 赵晓琦, 赵丽萍, 焦玉宏, 朱亚飞, 陈建英, 周伟, 谭颖. 基于谱聚类半监督特征选择的功能磁共振成像数据分类[J]. 计算机应用, 2021, 41(8): 2288-2293.
[4]	金波, 张志勇, 赵婷. 基于差分隐私的社交网络位置近邻查询方法[J]. 计算机应用, 2020, 40(8): 2340-2344.
[5]	李杏峰, 黄玉清, 任珍文. 联合低秩稀疏的多核子空间聚类算法[J]. 计算机应用, 2020, 40(6): 1648-1653.
[6]	涂子璇, 刘树波, 熊星星, 赵晶, 蔡朝晖. 可穿戴设备的数值型流数据差分隐私均值发布[J]. 计算机应用, 2020, 40(6): 1692-1697.
[7]	罗惠雯, 龙士工. 基于用户感兴趣区域的地理不可区分性的位置扰动算法[J]. 计算机应用, 2020, 40(3): 760-764.
[8]	刘静姝, 王莉, 刘惊雷. 无需特征分解的快速谱聚类算法[J]. 计算机应用, 2020, 40(12): 3413-3422.
[9]	宋艳, 殷俊. 基于共享近邻的多视角谱聚类算法[J]. 计算机应用, 2020, 40(11): 3211-3216.
[10]	李昆明, 王超迁, 倪巍伟, 鲍晓涵. 基于差分隐私的高精度直方图发布方法[J]. 计算机应用, 2020, 40(11): 3242-3248.
[11]	崔艺馨, 陈晓东. Spark框架优化的大规模谱聚类并行算法[J]. 计算机应用, 2020, 40(1): 168-172.
[12]	马方方, 刘树波, 熊星星, 牛晓光. 可穿戴设备数值型敏感数据本地差分隐私保护[J]. 计算机应用, 2019, 39(7): 1985-1990.
[13]	张书旋, 康海燕, 闫涵. 基于Skyline计算的社交网络关系数据隐私保护[J]. 计算机应用, 2019, 39(5): 1394-1399.
[14]	毛伊敏, 刘银萍, 梁田, 毛丁慧. 基于模糊谱聚类的不确定蛋白质相互作用网络功能模块挖掘[J]. 计算机应用, 2019, 39(4): 1032-1040.
[15]	霍峥, 张坤, 贺萍, 武彦斌. 满足本地化差分隐私的众包位置数据采集[J]. 计算机应用, 2019, 39(3): 763-768.