一种基于隐私保护的分布式聚类算法.pdfVIP

第 36 卷 　第 3 期 计 算 机 科 学 Vol . 36 No . 3 2009 年 3 月 Co mp ut er Science Mar . 2009 一种基于隐私保护的分布式聚类算法 姚 　瑶 　吉根林 (南京师范大学计算机系 　南京 2 10097) 　 摘 　要 　针对水平划分的分布式数据库提出了一种基于隐私保护的分布式聚类算法 P PD KMean s ,该算法基于 K Mean s 的思想实现分布式聚类 ,并且聚类过程中引入半可信第三方 ,应用安全多方技术保护本站点真实数据不被传送 到其他站点 ,从而达到隐私保护的目的。理论分析和实验结果表明 PPD KMean s 算法是有效的。 关键词 　分布式聚类 ,隐私保护 ,安全多方计算 　 Distributed Clustering Algorithm Based on Privacy Protection YAO Yao 　J I Genlin (Dep art ment of Comp ut er ,Nanj ing Nor mal U niver sit y ,Nanj ing 2 10097 ,China) 　 Abstract 　Thi s p ap er p ropo sed algorit hm P PD KMean s for p rivacyp reserving KMean s clu st ering over horizont al p ar titioned dat abase . U sing semit ru st ed t hir d p art y and secure multip art y t echnology ,P PD KMean s does not t ran sfer real dat a to ot her sit es in clu st ering p rocedure . Theoretical analysi s and exp eriment al result s show t hat algorit hm P PD K Mean s i s effective and p rivacy p reserving . Keywords 　Di st ribut ed clu st ering , Privacy p reserving , Secure multip art y comp ut ation 　 　　人们提出了一些分布式聚类算法 ,如 KDMean s[ 1] ,D K 信息 ,则此计算视为安全的。分布式计算的要求是各个站点 Mean s[2 ] ,DCombing[3 ] , DBDC[4 ] , SDBDC[5 ] 等 , 这些算法不 之间进行通信共同参与计算 。安全多方计算的关键是如何保 具有隐私保护功能 ,它们在聚类过程中将本站点有关真实数 证站点在共同参与计算的情况下 ,它们之间的通信数据没有 据传送给其他站点 ,从而导致信息泄露 。在实际分布式聚类 揭示出任何私有信息 。 应用中 ,有时候需要保护本站点的真实信息不被传送给其他 (2) 半可信第三方 站点 ,即需要进行隐私保护 ,为此 , 需要研究基于隐私保护的 安全多方计算的一种方法是 ,假设有一个完全可信第三 分布式聚类算法 。 方 ,每个站点把自己的信息发送给可信方 ,可信方进