分布式数据隐私保护聚类算法的研究

摘要

分布式或网格环境中隐私保护数据挖掘是近年来的一个热点研究课题。分布式环境中,与传统的集中式数据挖掘不同,隐私保护的数据挖掘需要解决如下矛盾:一方面,各数据持有方都希望保持自己的私有数据不为其他任何一方所知;另一方面,它们又希望通过合作获得全局数据模型。因此,需要研究新的算法使得各方在不共享原始数据的情况下进行正确的数据挖掘,称为隐私保护数据挖掘(Privacy-Preserving Data Mining,PPDM)。保护隐私的数据挖掘方法有两大类,基于密码学的方法和随机化方法,本文关注前者。安全多方计算(Secure Multi-party Computation,SMC)是近年来在信息安全与分布式计算领域迅速崛起的一个活跃的研究方向,在理论与应用上都有非常重要的研究意义。安全多方计算是指在一个互不信任的多用户网络中,两个或多个用户能够在不泄漏私有信息而协同合作执行某项计算任务。隐私保护数据挖掘解决方案已经涉及到水平分布和垂直分布的数据库,即各参与方针对相同的属性拥有不同的数据对象,或拥有相同的数据对象但所拥有的属性不同。
　　本文引进任意分布数据,即水平分布和垂直分布数据的推广。在任意分布数据中,不同项目的不同属性可以由任意一方拥有。虽然极端拼凑的数据在实践中不可能存在,但是基于任意分布数据考虑的协议更适用于水平分布和垂直分布数据;以及混合型,即并不是完全的垂直或水平分布。
　　针对任意分布的数据集,本文提出了任意分布数据的隐私保护K-均值聚类算法。针对数据挖掘面临的超大数据集问题,本文提出了任意分布数据库隐私保护BIRCH算法。所提的算法通过采用点积协议,向量和最小值的索引协议,安全多方除法协议,以及安全比较等协议达到隐私保护。通过实验,与集中式数据挖掘算法的结果进行比较,验证了基于本文提出的算法的正确性。同时,运行时间开销的比较结果也表明了本文提出的算法的可行性。最后,论文还对算法的传输开销和计算复杂度进行了分析。

目录

摘要

Abstract

第一章 绪论

1.1 研究背景及意义

1.2 分布式数据隐私保护研究进展

1.3 论文的工作和组织结构

1.3.1 论文的工作

1.3.2 论文的组织结构

第二章 基本概念和相关协议

2.1 数据挖掘的概述

2.2 聚类分析的概述

2.2.1 聚类分析中的数据结构

2.2.2 聚类分析中的数据类型

2.2.3 聚类算法—k-均值算法

2.2.4 聚类算法—BIRCH算法

2.3 分布式数据挖掘概述

2.3.1 水平划分的数据

2.3.2 垂直划分的数据

2.3.3 任意划分的数据

2.4 隐私保护技术的概述

2.4.1 隐私保护的概述

2.4.2 分布式数据隐私保护技术概述

2.5 安全多方计算的概念及相关协议

2.5.1 点积协议

2.5.2 向量和的最小值的索引协议

2.5.3 安全多方实数加、乘混合计算协议

2.5.4 安全多方除法协议

2.5.5 叉积协议

2.5.6 一个高效的秘密比较协议

2.5.7 安全比较协议

2.6 隐私保护算法的评价

2.7 本章小结

第三章 任意分布数据隐私保护k-均值聚类算法

3.1 问题的引出

3.2 任意划分的数据隐私保护k-均值聚类算法

3.2.1 任意划分的数据隐私保护k-均值聚类算法

3.2.2 安全计算最近簇协议

3.2.3 安全计算平均值协议

3.2.4 安全终止迭代协议

3.3 任意分布数据隐私保护k-均值聚类算法实现

3.3.1 算法的实现

3.3.2 算法中主要函数描述

3.4 实验结果及分析

3.5 传输开销与计算复杂度

3.6 本章小结

第四章 任意分布数据隐私保护BIRCH算法

4.1 问题的引出

4.2 相关定义

4.2.1 聚类特征及CF-树

4.2.2 CF条目插入到CF-树的算法

4.2.3 BIRCH聚类算法的实现

4.2.4 算法时间复杂度分析

4.3 任意分布数据库隐私保护BIRCH算法

4.3.1 任意分布数据聚类特征和聚类特征树

4.3.2 安全距离向量

4.3.3 安全构造CF树

4.3.4 安全分拆节点

4.3.5 安全BIRCH算法

4.4 任意分布数据库隐私保护BIRCH算法实现

4.4.1 算法的主要数据结构

4.4.2 部分算法的实现

4.4.3 算法中主要函数描述

4.5 实验结果及分析

4.6 传输开销与计算复杂度

4.7 本章小结

第五章 总结与展望

5.1 总结

5.2 主要工作和贡献

5.3 展望

参考文献

攻读学位期间发表的学术论文

后记