隐私保护的快速聚类算法

Journal of Systems Engineering and Electronics ›› 2009, Vol. 31 ›› Issue (10): 2521-2526.

隐私保护的快速聚类算法

薛安荣¹, 姜冬洁^1,2, 鞠时光¹, 陈伟鹤¹, 马汉达¹

1. 江苏大学计算机科学与通信工程学院, 江苏, 镇江, 212013;
2. 炎黄职业技术学院, 江苏, 淮安, 223400

收稿日期:2008-05-22 修回日期:2009-05-21 出版日期:2009-10-20 发布日期:2010-01-03
作者简介:薛安荣(1964- ),男,副教授,博士,主要研究方向为数据挖掘、信息安全.E-mail:xuear@ujs.edu.cn
基金资助:
国家自然科学基金(60773049,60603041);江苏大学高级人才启动基金(09JDG041)资助课题

Fast privacy-preserving clustering algorithm

XUE An-rong¹, JIANG Dong-jie^1,2, JU Shi-guang¹, CHEN Wei-he¹, MA Han-da¹

1. School of Computer Science and Telecommunication Engineering, Jiangsu Univ., Zhenjiang 212013, China;
2. Progenitor Vocational and Technical Coll., Huai'an 223400, China

Received:2008-05-22 Revised:2009-05-21 Online:2009-10-20 Published:2010-01-03

摘要/Abstract

摘要： 针对基于安全多方计算聚类算法的低效问题,提出了基于聚类特征树结构的隐私保护的层次k-means聚类算法.算法基于半诚信模型,在第三方内存中保留对各记录的索引信息及聚类特征树的当前层信息,减少了I/O次数和通信量,克服了难以适应多数据方和因过于信赖第三方导致隐私泄漏等缺陷.算法通过基于安全多方计算的标准化协议、距离计算协议和聚类中心计算协议,实现了数据的有效保护,综合层次和k-means聚类算法的优点,提高了计算精度和算法的可伸缩性.理论证明了算法的安全性和高效性,实验结果表明所提算法优于同类算法.

Abstract: To improve the efficiency of a clustering algorithm based on secure multi-party computation,a privacy-preserving hierarchical k-means algorithm based on clustering feature tree and semi-honest model is proposed.The algorithm stores the index information of every record and current hierarchical information of the clustering feature tree in the third party's memory and reduces the I/O times and communication cost,it also overcomes the drawbacks of applying to multi-party difficultly and leaking privacy due to depending on the third party excessively.The algorithm introduces three secure protocols such as distance computation,clustering center computation and standardization to protect data privacy effectively and accurately,and improves the precision and flexibility by combining the merits of hierarchical and k-means clustering algorithms.Theoretic argument demonstrates that the algorithm is secure and completes with good efficiency.The experimental results show that the proposed algorithm outperforms the other existing algorithms in communication cost and computation cost.

中图分类号:

TP309

薛安荣, 姜冬洁, 鞠时光, 陈伟鹤, 马汉达. 隐私保护的快速聚类算法[J]. Journal of Systems Engineering and Electronics, 2009, 31(10): 2521-2526.

XUE An-rong, JIANG Dong-jie, JU Shi-guang, CHEN Wei-he, MA Han-da. Fast privacy-preserving clustering algorithm[J]. Journal of Systems Engineering and Electronics, 2009, 31(10): 2521-2526.

参考文献

[1] Agrawal R,Srikant R.Privacy-preserving data mining[C]//Proc.of the ACM SIGMOD Conference on Management of Data.Dallas,Texas,2000:439-450.
[2] Lindell Y,Pinkas B.Privacy preserving data mining[C]//Proc.of Advances in Cryptology-CRYPTO,Lecture Notes in Computer Science,Springer-Verlag,2000,1880:36-53.
[3] Kantarcioglu M,Clifton C.Privacy-preserving distributed mining of association rules on horizontally partitioned data[J].IEEE Trans.on Krartoedge & Data Engineering,2004,16(9):24-31.
[4] Vaidya J,Clifton C.Privacy preserving association rule mining in vertically partitioned data[C]//Proc.of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2002:639-644.
[5] Vaidya J,Clifton C.Privacy-preserving k-means clustering over vertically partitioned data[C]//Proc.of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Washington,DC,USA,2003:206-215.
[6] Jha S,Kruger L,McDaniel P.Privacy preserving clustering[C]//Proc.of 10th European Symposium on Research in Computer Security,Milan,Italy,2005:397-417.
[7] Inan Ali,Kaya SV,Saygin Y.Privacy preserving clustering on horizontally partitioned data[J].Data & Knowledge Engineering,2007,63(3):646-666.
[8] Jagannathan G,Pillaipakkaamnatt K,Wright R.A new privacypreserving distributed k-clustering algorithm[C]//Proc.of SIAM International Conference on Data Mining,2006:492-496.
[9] Trottini M,Feinberg SE.Modelling user uncertainty for disclosure risk and data utility[J].International Journal of Uncertainty,Fuzziness and Knowledge-Based Systems,2002,10(5):511-527.
[10] Goldreich O.Foundations of cryptography:basic applications[M].London:Cambridge University Press,2004.
[11] Clifton C,Vaidya J.Tools for privacy preserving distributed data mining[J].SIGKDD Explorations,2003,4(2):28-34.
[12] Hettich S,Bay S D.The UCI KDD archive[DB/OL].Irvine,CA:University of California,Department of Information and Computer Science,1999.http://kdd.ics.uci.edu.