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

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

第一章 绪论

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]。
.............................

第二章 相关背景知识介绍

2.1隐私泄露和隐私保护
在用户进行浏览网站和网上消费时,用户无意的将自己的相关信息保留在互联网中。那么当攻击者获取到这些信息时,通过数据分析和挖掘就会得到数据中有用的信息,这些信息可能会导致用户的隐私信息泄露。
2.1.1 隐私泄露
隐私的概念最早可以追溯到社会学[25,26],隐私是指个人、组织机构等实体不愿意被外部知晓的信息[27]。例如,个人的家庭住址、健康情况等。用户在使用不同的移动设备和网络应用时自身的信息会共享在网络上,同时数据收集者公开发布的用户者的数据,这些都有可能存在着被非法分子攻击的风险。而攻击者通过自身已知的用户信息对获取到的数据进行定位到与用户相关的数据,从而导致用户的隐私泄露。攻击者还可以对获取到的数据进行数据分析得到与该用户的群体关联信息和特征信息,然后通过自身的用户背景知识对这些关联信息和特征信息进行数据挖掘出用户的隐私信息。
2.1.2 隐私保护
随着互联网和大数据技术的快速发展,隐私泄露的途径也变的多种多样,攻击者的手段也是越来越多。因而,隐私泄露的问题也是越来越严重,所以对数据的隐私保护发布技术研究成为现在的学术热点。用户的数据记录由敏感属性和非敏感属性组成,一般用户个体可以通过非敏感属性与敏感属性建立联系,无法直接与敏感属性的某一属性值建立联系。因此,攻击者需要通过获取部分或者全部非敏感属性的属性值来与敏感属性的属性值建立起联系。所以隐私保护的技术需要切断用户与这些敏感属性之间的联系来达到隐私保护。目前的隐私保护方法通常都是通过切断用户和非敏感属性之间的联系或者是切断非敏感属性和敏感属性之间的联系来达到隐私保护的效果。数据挖掘的隐私保护通常都是切断非敏感属性值与敏感属性值之间的联系,在隐私保护的过程中对其可能泄露的敏感属性进行规则隐藏,然后将非敏感属性直接发布。数据发布的隐私保护通常是通过隐私保护方法处理得到匿名数据再将其发布。因此对于以上的二种方法目前的隐私保护发布算法都有用到。研究者一般利用以上的一种或者两种方法组合对原始数据进行处理,切断目标用户和其敏感属性值之间的联系。
.............................

2.2 差分隐私及数据发布概述
差分隐私是由 Dwork 等人在 2006 年提出,该模型主要的核心思想是对原始数据集划分后的数据集或者对其查询的结果添加噪声来达到隐私保护的效果。这种通过添加噪声对数据集进行扰动作用就是一种数据发布技术,对于数据集的隐私发布一般都是要借助数据发布技术来实现对数据的隐私保护。
2.2.1 差分隐私定义与相关概念
随着信息时代的到来,数据隐私得到人们的广泛关注以及成为学术界的热点问题,虽然也出现了诸多的隐私保护框架的保护方法,例如,
k-匿名[28]、l-diversity[29]、t-closeness[30]等。但是这些方法都需要特殊的攻击假设和背景知识。而差分隐私模型定义了一个极强的攻击模型,假设攻击者拥有除了目标记录外的所有信息,通过分析和挖掘也无法得到目标记录的任何隐私信息,并且对某一个数据集中插入和删除一条记录确保不影响查询的结果。
如图 2.1 所示,描述了随机算法 A 利用对输出结果随机化提供隐私保护,通过对参数来确保在删除数据集中一条记录输出同一结果的概率不会发生显著的变化。因此对于隐私预算的合理分配也是非常的关键,也是本文研究的重点之一。
图 2.1 随机算法在邻近数据集上的输出概率图
.................................
 
第三章  基于标准差圆半径的隐私预算分配模型(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 所示是三个数据集映射到二维平面坐标的可视化图。
图 5.1 数据集可视化结果图
............................
 
第六章 总结与展望

6.1总结
随着大数据技术的快速发展,数据集的共享需求也是不断的增加,这让数据集的隐私保护得到了重视。因而针对基于差分隐私的数据集发布的隐私保护模型和算法的研究已成为学术领域广泛关注的热点。因此,本文对现有的基于差分隐私的空间数据集发布中的隐私保护研究做出分析,发现现研究没有充分的考虑到数据集的分布特征,进而没有合理的对网格进行隐私预算的分配,从而在添加噪声阶段产生较大的噪声误差。同时没有兼顾到用户的查询粒度,从而导致在网格划分的第二层易产生较大的查询误差,从而增大了相对误差和降低数据集的查询精度和可用性。因此,本文针对上述问题提出了基于标准差圆半径的自适应网格划分模型,并通过实验对其进行论证,本文的主要的研究成果和工作总结如下:
(1)  对数据集分布特征的研究和分析,针对现有的隐私保护研究中,没有给出一种能够对数据集分布特征定量计算的方法。本文通过借助标准差圆半径来刻画数据集的离散程度,从而对数据集的分布特征进行描述。并将其引入到本文提出的算法模型中,在对数据集进行网格划分的同时计算出划分后的网格的标准差圆半径,从而表示该网格中数据集的离散程度,以此来描述数据集的分布特征。最终,给出了一种定量计算数据集分布特征的方法,实现了对数据集的分布特征进行定量的描述。
(2)  对数据集的隐私预算分配进行研究和分析,针对现有差分隐私保护研究中,没有给出一种能定量的对数据集的隐私保护需求进行计算的方法。本文在对数据集的分布特征描述的基础上,在对数据集划分后,计算出每个数据网格的标准差圆半径在当层数据层中的占比来表示数据集的隐私保护需求,即隐私保护需求力度。通过引入隐私保护需求力度的概念,以此来定量的描述数据集的隐私保护需求,然后根据隐私保护需求按需的对其进行分配隐私预算
(3)  对数据集进行降噪的研究和分析,针对现有的基于差分隐私的数据集发布的研究中,没有充分的考虑到数据集的分布特征,从而没有对隐私预算进行合理的分配,从而导致在添加噪声阶段产生较大的噪声误差,进而使得数据集的可用性大大降低。同时没有兼顾到用户的查询粒度,导致在网格划分的第二层网格易产生较大的查询误差。本文在定量的对数据集的隐私保护需求描述基础上,通过隐私保护需求力度来对数据集的隐私预算进行按需分配,从而在添加噪声阶段,根据不同的隐私预算添加相应的噪声,有效降低了噪声误差。针对用户的查询粒度,在第二层网格的划分,通过过滤和分桶的处理,能够有效的降低产生额外的噪声误差,最后通过后置处理能够提高查询精度。这些操作大大的降低了噪声误差,提高了数据集的可用性,从而实也提高了数据集的可用性。
参考文献(略)


原文地址:http://www.sblunwen.com/jsjlw/29721.html,如有转载请标明出处,谢谢。

您可能在寻找计算机论文方面的范文,您可以移步到计算机论文频道(http://www.sblunwen.com/jsjlw/)查找