支持差分隐私保护模型的数据发布算法研究

摘要

进入信息时代后，众多的服务提供商积累了大量的用户数据。数据共享可以避免由于雪藏数据带来的浪费，但是共享的数据往往涉及用户的隐私。因此，数据发布过程中的用户隐私保护问题逐渐受到了学术界和工业界的关注。差分隐私保护模型以其优秀的表现，被应用到众多领域。本文研究满足差分隐私保护模型的数据发布算法，并针对数据类型的不同，提出不同的解决方案。本文的研究目的是在保证发布算法满足差分隐私保护模型的基础上，提高发布数据的准确性。
　　针对数值型数据，本文提出了基于有序划分直方图的数据发布算法。该算法对直方图区间做第一重变换后，在保护直方图结构信息的前提下对区间顺序进行调整，借此消除了可能出现的“分区截断”问题。同时，本文使用基于贪婪思想的分区算法，综合考虑分区后添加的Laplace噪声对分区方案的影响。这避免了对分区个数的事先约定，提高了算法对不同数据集的适用性。本文提出的算法在保证发布的直方图满足差分隐私保护模型的基础上，提高了作用于该直方图的范围查询的准确性。
　　针对用复杂图表示的关联数据，本文提出了基于层次随机图分治的关联数据发布算法。本文的出发点是用户对这类数据的兴趣点往往集中在社区内。所以，结合社区发现的相关知识，本文提出对复杂图中的边进行不同程度的差分隐私保护的策略。本文提出的算法基于分治的思想，对社区进行层次随机图构建，然后合并子层次随机图。这解决了复杂图规模较大时，原始算法效率低下的问题。本文提出的算法对复杂图进行分块处理，并对数据发布的隐私性和数据可用性进行了权衡。在实验环节，按照节点度的分布和最短路径分布等衡量标准，本文的算法更好地保持了原始复杂图的性质。

目录

声明

摘要

第1章 绪论

1．1 课题研究的背景及意义

1．2 国内外研究现状

1．2．1 统计类数据的发布

1．2．2 关联类数据的发布

1．3 论文的主要工作及组织结构

第2章 相关技术介绍

2．1 差分隐私保护模型

2．1．1 Laplace机制

2．1．2 指数机制

2．1．3 组合性质

2．2 马尔科夫蒙特卡洛方法

2．2．1 马尔科夫链

2．2．2 蒙特卡洛方法

2．2．3 Metropolls-Hastlngs算法

2．3 层次随机图

2．3．1 定义与表示

2．3．2 评价指标

2．3．3 构建方法

2．4 社区发现

2．5 本章小结

第3章 基于差分隐私的数据发布算法

3．1 基础算法

3．1．1 基于直方图的数据发布算法

3．1．2 基于层次随机图的关联数据发布算法

3．2 基于有序划分的直方图数据发布

3．2．1 算法概述

3．2．2 分区算法

3．2．3 算法详述

3．2．4 隐私分析

3．3 基于HRG分治的关联数据发布

3．3．1 算法出发点

3．3．2 社区发现算法

3．3．3 算法详述

3．3．4 隐私分析

3．4 本章小结

第4章 实验设计与结果分析

4．1 实验环境

4．1．1 实验平台

4．1．2 实验数据

4．1．3 实验方案

4．1．4 评估度量

4．2 实验结果与分析

4．2．1 数值型数据发布算法

4．2．2 关联数据发布算法

4．3 本章小结

第5章 总结与展望

参考文献

攻读学位期间公开发表论文

致谢