基于隐私保护聚类的分析与研究

论文摘要

隐私保护是数据挖掘领域中一个重要的研究方向,其目的是如何在不泄露私有数据的前提下,使用数据挖掘工具得到精确的挖掘结果。为了有效地保护分布式环境下的隐私,研究人员已经提出了一些隐私保护算法,包括水平分布数据和垂直分布数据,但隐私保护的聚类算法少,且算法复杂度较高、效率低、大多基于k-means算法,仅限于两方或第三方是完全诚信方,数据安全性和可靠性难以满足用户需求。隐私保护数据挖掘常用的方法主要有两种:安全多方计算和数据扰乱。安全多方计算以安全协议为基础,构造分布式环境下隐私保护算法,安全高效的隐私保护协议是安全多方计算方法的基础;而数据扰乱通过改变原始数据的分布来隐藏真实数据的值,高挖掘精度和隐私保护度是其追求目标。本文分别使用安全多方计算和数据扰乱方法,对以上提到的不足之处进行了一些改进,主要贡献如下:1、结合k-means聚类算法和层次聚类算法的优点,构造层次-k-means聚类算法,有效克服了k-means算法因随机选取聚类中心造成聚类结果不确定的缺陷。2、构造求距离、求聚类中心及标准化等安全协议,提出半诚实模型下基于聚类特征树结构的水平分布数据隐私保护的层次-k-means聚类算法。由数据方和第三方共同参与解决了半诚实模型下水平分布数据多方隐私保护的层次-k-means聚类问题。理论证明和实例分析表明了提出的算法的安全性和有效性。3、构造安全比较协议,并以安全标准化及安全比较协议为基础,提出半诚实模型下水平分布数据隐私保护的DBSCAN。理论证明和实例分析表明所提出算法的安全性与有效性,举例说明其应用。4、将基于正交变换的随机扰乱技术应用于垂直分布数据属性间点积计算和数据对象的层次-k-means聚类。选取满足一定条件的随机矩阵来减少误差,理论分析和实验表明这种随机数据扰乱方法能够在恶意方共谋情况下有效保护用户的隐私,扰乱前后的层次-k-means聚类精度损失及点积误差限定在一个较小的范围内。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1 研究背景和意义
• 1.2 隐私保护聚类挖掘的研究现状
• 1.3 论文主要工作
• 1.4 论文组织结构
• 第二章 数据挖掘及隐私保护概述
• 2.1 数据挖掘概述
• 2.2 数据挖掘中的隐私问题
• 2.2.1 何谓隐私
• 2.2.2 数据挖掘中的隐私保护问题
• 2.3 PPDM（PRIVACY-PRESERVING DATA MINING）使用的方法
• 2.3.1 安全多方计算（Secure multi-party Computation）
• 2.3.2 数据扰乱（Distorted data）
• 2.5 分布式隐私保护的数据挖掘
• 2.6 隐私保护数据挖掘的发展趋势
• 2.7 本章小结
• 第三章 数据挖掘中的聚类算法
• 3.1 数据挖掘对聚类方法的要求
• 3.2 几种经典聚类算法描述
• 3.2.1 K-MEANS聚类算法
• 3.2.2 层次聚类算法
• 3.2.3 DBSCAN
• 3.2.4 层次-K-MEANS聚类算法
• 3.3 本章小结
• 第四章 半诚实模型下水平分布数据隐私保护的聚类算法
• 4.1 相关定义
• 4.2 安全多方计算协议
• 4.2.1 （协议1）安全和协议
• 4.2.2 （协议2）点积协议
• 4.2.3 （协议3）百万富翁协议
• 4.2.4 （协议4）安全标准化协议
• 4.2.5 （协议5）距离计算的安全协议
• 4.2.6 （协议6）安全比较协议
• 4.2.7 （协议）7康类中心计算的安全协议
• 4.3 半诚实模型下水平分布数据隐私保护的层次-K-MEANS算法
• 4.3.1 算法思想
• 4.3.2 HPPHKC算法描述
• 4.3.3 算法安全性分析
• 4.3.4 通信代价和计算复杂度分析
• 4.3.5 k-means算法和层次-k-means算法实验
• 4.3.6 应用举例
• 4.4 水平分布数据环境下隐私保护的DBSCAN
• 4.4.1 算法描述
• 4.4.2 算法安全性分析
• 4.4.3 通信代价和计算复杂度分析
• 4.5 实例分析
• 4.6 本章小结
• 第五章 恶意方共谋情况下垂直分布数据的隐私保护
• 5.1 普通数据扰乱方法存在的缺陷
• 5.1.1 加法数据扰乱的缺陷
• 5.1.2 普通对角矩阵随机化方法存在的缺陷
• 5.1.3 ICA对普通的旋转正交变换的威胁
• 5.1.4 距离推理可攻破普通的旋转正交变换
• 5.2 普通正交变换在恶意方共谋情况下失去抵抗力
• 5.2.1 正交变换在半诚实模型下可有效保护隐私
• 5.2.2 半诚实模型下普通正交变换实验
• 5.2.3 恶意方共谋情况下普通正交变换存在的安全隐患
• 5.3 垂直分布数据属性间点积的计算
• 5.3.1 问题描述
• 5.3.2 垂直分布数据点积问题解决方法
• 5.3.3 随机矩阵的选择
• 5.4 数据扰乱在垂直分布数据层次-K-MEANS聚类算法中的应用
• 5.5 实验
• 5.5.1 恶意方共谋情况下垂直分布数据隐私保护的点积实验
• 5.5.2 垂直分布数据隐私保护的层次-k-means聚类实验
• 5.6 本章小结
• 第六章 结论与展望
• 6.1 工作总结
• 6.2 需进一步研究的工作
• 致谢
• 参考文献
• 攻读硕士学位期间发表的学术论文