学海网

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

目 录
摘要 I
Abstract II
目 录 IV
第1章 绪 论 1
1.1 课题背景与研究意义 1
1.2 国内外研究现状 2
1.2.1 国外研究现状 2
1.2.2 国内研究现状 3
1.2.3 国内外研究现状简析 4
1.3 主要研究内容以及组织结构 5
1.3.1 主要研究内容 5
1.3.2 论文组织结构 6
第2章 具有隐私保护的聚类算法理论基础 7
2.1 具有隐私保护的数据挖掘定义及分类 7
2.2 实现隐私保护聚类算法的常用技术 9
2.2.1 数据扰乱技术 9
2.2.2 数据加密技术 10
2.3 基于数据加密技术的具有隐私保护的聚类算法 11
2.3.1 云计算和云存储 11
2.3.2 安全多方计算 12
2.3.3 同态加密方案 13
2.4 聚类算法的常用数据划分 14
2.5 本章小结 16
第3章 具有隐私保护的K-means聚类算法 17
3.1 经典的K-means聚类算法 17
3.2 具有隐私保护的安全协议 18
3.2.1 安全乘法协议 18
3.2.2 安全距离计算协议 19
3.2.3 安全比较协议（两个密文） 21
3.2.4 安全比较协议（多个密文） 24
3.2.5 安全电路协议 24
3.3 具有隐私保护的K-means聚类算法设计 25
3.4 本章小结 29
第4章 算法实现与分析 30
4.1 环境搭建 30
4.1.1 数据集 30
4.1.2 环境配置 31
4.1.3 系统框架与实现 31
4.2 复杂度分析 36
4.3 安全性分析及证明 37
4.4 实验对比分析 38
4.4.1 评价标准 38
4.4.2 实验结果分析 39
4.5 本章小结 44
结论 45
参考文献 46
攻读硕士学位期间发表的学术论文及其他成果 50
哈尔滨工业大学学位论文原创性声明和使用权限 51
致谢 52