基于标准差圆半径的自适应网格划分模型计算机分析

本文是一篇计算机论文，本文对现有的基于差分隐私的空间数据集发布中的隐私保护研究做出分析，发现现研究没有充分的考虑到数据集的分布特征，进而没有合理的对网格进行隐私预算的分配，从而在添加噪声阶段产生较大的噪声误差。同时没有兼顾到用户的查询粒度，从而导致在网格划分的第二层易产生较大的查询误差，从而增大了相对误差和降低数据集的查询精度和可用性。因此，本文针对上述问题提出了基于标准差圆半径的自适应网格划分模型，并通过实验对其进行论证。

第一章 绪论

1.1研究背景及意义
随着互联网技术和大数据技术的快速发展以及移动终端的普及化，人们与移动终端的交互越来越频繁。人们的地理位置信息与这些终端时刻进行交互，这些设备可以向服务器报告用户的位置信息，这种位置信息（通常称为空间数据）。基于位置服务是未来互联网行业的重要组成部分，并给我们的生活带来了很多的便捷。例如：通过地理位置信息的共享我们可以随机通过互联网进行叫车、点餐、预定等服务；政府部门通过这些位置信息进行交通枢纽调度预警，可以有效的避免交通阻塞。同时这些数据的价值远远超出了我们的想象，对于许多的企业而言，这些数据就是无价的财富，他们可以根据用户的历史的地理空间数据来进行数据分析和数据挖掘得到用户的行为方式，通过推荐系统来推荐用户感兴趣的话题或者商品来达到自己的商业目的。因此为了能够获取用户的行为模式，这些企业首先要做的就是收集大量的用户历史地理空间信息，然后通过数据分析和挖掘出有价值的信息。然而，用户的地理位置信息通常伴随着大量的个人隐私信息，地理空间数据集受到非法分子的攻击、数据分析和挖掘可能导致个人的行为方式、出行方式、生活习惯等隐私信息的暴露。而对于空间数据集的隐私保护一直以来都是一个具有挑战性的问题和研究热点。
针对数据集的隐私保护出现了多种的隐私保护模型。例如：以 K-匿名算法为代表的早期隐私保护方法所定义的保护模型，忽略了攻击者对数据集背景知识的掌握，往往会遭受一致性攻击和背景知识攻击，使得用户数据的隐私信息没有得到有效的保护[1]。差分隐私[2,3,4,5,6]是一种新型的保护模型，它假设攻击者拥有所有的背景知识，通过添加噪声扰动的方式来对信息进行隐私保护。差分隐私保护模型定义了一个极其严格的攻击模型，并对隐私泄露风险给出了严谨的数学证明和定量化表示。对于空间数据集的隐私保护一般采用差分隐私保护模型，相比传统的隐私保护模型，差分隐私最显著的优点是能够抵御背景知识攻击且具有较好的隐私保护效果。当用户将自己的地理空间数据集共享在网络中，差分隐私通过扰动的隐私保护策略对用户的空间数据集中添加相应的噪声来达到隐私保护的效果，使得攻击者无法挖掘和分析出目标数据集的隐私信息。
...........................

1.2国内外研究现状
差分隐私是由 Dwork 等人在 2006 年提出的，相比传统的隐私保护方法不易受到一致性攻击和背景知识攻击，因此它遭受到的隐私暴露风险极小。所以差分隐私保护技术相比传统的隐私保护技术具有较好的保护效果，并且差分隐私理论上的可证明性和应用上的通用性，使得差分隐私得到了业界的广泛认可，并成为这些年隐私保护技术的研究热点。于是关于差分隐私的研究产生了大量的研究成果[8,9,10,11,12]，特别是广泛的运用到数据发布的隐私保护算法中。
基于差分隐私的数据发布研究在差分隐私的研究中的具有核心的地位，根据差分隐私保护数据发布的实现环境分为交互式和非交互式两种不同数据发布[13]。交互式数据发布方法主要有发布机制和基于直方图。发布机制是直接对数据集进行操作对查询进行响应。基于直方图是先将数据集建立直方图分布，从而根据数据直方图分布来响应查询。非交互式数据发布方法主要有划分、列联表发布、基于分组发布和净化数据集发布等。
LP 是基于直方图发布的早期方法。该方法结合拉普拉斯机制将数据分为等宽的直方图，该方法优点支持响应长范围查询，但是由于噪声的累加会导致发布误差大，直方图可用性低[13]。相比 LP，Boost1 通过一致性约束条件和后置处理来降低误差，该方法支持高精度的范围查询，但是仅适用于数据独立情况下的一维直方图，且不支持长范围查询[14]。Boost2 通过结合最小二乘法对 m-ary 树中的噪音计数进行约束推理提高查询精度，但是该方法同样仅限于一维的数据集发布[14]。NoiseFirst 利用 V-优化直方图技术对 LP 产生的直方图进行重构后置处理来降低误差，该方法支持长范围查询并且查询精度较高，但是该方法没有考虑重构带来的误差，没有均衡重构误差和噪声误差，并且该方法存在的另一个缺陷在于它仅适用于一维直方图[15]。P-HPartition 结合聚类技术和二等分策略自适应的对数据集自上而下进行分割，从而平衡重构误差和噪声误差，但是忽略了离群点对直方图发布的影响，且该方法也是只适用于一维的数据集发布[16]。FPA 是基于傅里叶变换来进行直方图发布，能够有效的提高查询精度，但是该方法扩展性差，且噪声误差大和重组误差大[16]。针对上述的问题 EFPA 通过发布的误差设计出一种打分函数，从而达到了均衡重构误差和噪声误差。以上二个方法也是仅适用于一维数据的发布。Cormode 等人针对特定数据类型，通过基于差分隐私的采样-过滤的数据发布技术简化步骤、降低敏感度，解决了由于数据稀疏添加过大的噪声而导致查询结果偏差很大的问题，但该算法的局限性在于返回结果的可用性较低[17]。 第三章  基于标准差圆半径的隐私预算分配模型（PBA） .................................. 21
3.1数据集分布特征的计算方法的分析与实现.......................................... 21
3.1.1  数据集分布特征的计算方法分析............................. 21
3.1.2  数据集分布特征的计算 ......................... 23
第四章  基于标准差圆半径的自适应网格划分模型（SDCAG） ............................. 29
4.1SDCAG 模型设计 ................................... 29
4.1.1  设计目标 ........................................ 29
4.1.2 SDCAG 流程设计 .................................. 29
第五章  实验与结果分析 .................................... 35
5.1实验环境与数据集 ...................................... 36
5.2实验方法 ................................ 36

第五章   实验与结果分析

5.1实验环境与数据集
本文所有的实验都是在 Windows10 的 64 位操作系统下进行的，CPU 型号为 1.6GHz 四核的第八代 Intel Core i7。实验的程序使用 java 语言进行编写，编译平台使用的是 IDEA，运行环境是 jdk1.8。
我们的实验对象是建立在三个真实的数据集上，将传统的隐私保护算法和本文提出的算法应用到这些数据集上，然后比较它们范围查询的查询精度，从而反映它们的隐私保护效果，得到相关的结论。
首先，将这三个来自真实的数据集映射到二维空间坐标系上，每个点表示一个数据点，如图 5.1 所示是三个数据集映射到二维平面坐标的可视化图。