论文部分内容阅读
众所周知,K-means聚类是数据挖掘中非常经典和常用的方法之一,它通过计算数据项之间的距离可以把相似的数据项聚集在一起。随着信息化、数字化、网络化进程加速,经济全球化已成为一种不可逆的趋势,聚类算法中的数据来源越来越多样化,数据安全越来越重要。考虑到数据会来自多个参与方,在这些数据中可能包含关于参与方的敏感信息或私人信息,如果这些信息在多个参与方之间共享,那么数据的隐私性将不能得到保证。具有隐私保护的联合数据挖掘可以在保护用户数据和挖掘结果隐私性的同时,对多个参与方的联合数据库进行数据挖掘,进一步提取出有用的信息。因此,如何设计出具有隐私保护的联合数据挖掘算法成为一个需要解决的难题。半诚实模型在许多情况下是符合实际场景的,该模型下数据的隐私性是通过各个参与方始终遵循协议来保证的。但是为保证数据的隐私性,该模型下的解决方案通常因为计算消耗和通信消耗较高,所以实际中并不可行。如今,随着科学技术的进步,越来越多的企业将数据存储在云平台,同时分布式云计算框架也为处理大数据提供强大的计算能力。本论文将借助云计算强大的计算能力提升算法的效率,保证算法的可行性。针对具有隐私保护的数据挖掘中存在的性能问题,本论文开展了对现有具有隐私保护的数据挖掘算法的深入研究,进而在水平划分的数据集上提出一种高效的具有隐私保护的K-means聚类算法,该算法支持有两个数据拥有者和云平台同时存在的存储外包和计算外包。数据以密文形式存储在云端,云平台通过与两个数据拥有者交互,完成在双方的联合数据集上K-means聚类数据挖掘的任务。本论文分别设计不同的安全协议解决具有隐私保护的K-means聚类算法中的三个技术难题:解决密文距离计算问题的安全距离计算协议、解决密文比较问题的安全比较协议和解决密文除法问题的安全电路协议。进而将这些安全协议应用到聚类算法框架中,实现具有隐私保护的K-means聚类算法。本论文从理论上分析了该算法的时间复杂度、空间复杂度和通讯复杂度,给出该算法在半诚实模型下的安全性证明,并且证明该算法在重计算质心点阶段允许参与方中最多有一个方为恶意方的安全性,最后通过实验计算加密数据的时间消耗和一次迭代过程中各参与方的时间消耗,验证了算法的可行性。