杨理皓：基于差分隐私机制的位置数据隐私保护策略

基于差分隐私机制的位置数据隐私保护策略作者杨理皓,谷科,李威机构湖南理工学院计算机与通讯工程大学发表刊物《计算机应用研究》预排期卷2018年第35卷第3期访问地址发布日期2017-03-2109:21:36引用格式杨理皓,谷科,李威.基于差分隐私机制的位置数据隐私保护策略[J/OL].[2017-03-21].摘要位置定位服务技术作为一种全新的联通估算服务，在日常生活中应用广泛。一方面，数据信息共享极大的便捷了人们的日常生活，另一方面也存在因为泄漏个人敏感信息而形成的症结。因而怎样保护好位置数据是关键。因为位置数据具有价值高和低密度的特点，造成现有的隐私保护方式很难兼具数据的保护和数据的效用性。基于差分隐私机制的位置数据隐私保护策略通过采用多级查询树的结构来查询和发布保护后的数据，并保持了数据项间的联系。首先建立多级查询树(位置搜索树)，之后遍历查询树，使用差分隐私的指数机制来选定访问频度高的k项，最后通…关键词位置数据,访问频度,差分隐私保护,多级查询树中图分类号TP309.2基金项目网路出版时间：2017-03-2109:48:09网路出版地址：优先出版计算机应用研究第35卷基于差分隐私机制的位置数据隐私保护策略杨理皓1,2，谷科1,2，李威1,2(重庆理工学院a．计算机与通讯工程大学，b．综合交通运输大数据智能处理四川省重点实验室，广州410114)摘要：位置定位服务技术作为一种全新的联通估算服务，在日常生活中应用广泛。

一方面，数据信息共享极大的便捷了人们的日常生活，另一方面也存在因为泄漏个人敏感信息而形成的恶果。因而怎样保护好位置数据是关键。因为位置数据具有价值高和低密度的特点，造成现有的隐私保护方式很难兼具数据的保护和数据的效用性。基于差分隐私机制的位置数据隐私保护策略通过采用多级查询树的结构来查询和发布保护后的数据，并保持了数据项间的联系。首先建立多级查询树(位置搜索树)，之后遍历查询树，使用差分隐私的指数机制来选定访问频度高的k项，最后通过拉普拉斯机制给选定的k项进行加噪。实验表明，相比于其他保护策略，基于差分隐私机制的位置数据隐私保护策略可用性和数据保护程度高，算法运行时间少，效率更高。关键词：位置数据；访问频度；差分隐私保护；多级查询树中图分类号：TP309.2LocationdataprivacyprotectionbasedondifferentialprivacymechanismYangLihao1,2,GuKe1,2,LiWei1,2(1.SchoolofComputer&CommunicationEngineering,b.HunanProvincialKeyLaboratoryofIntelligentProcessingofBigDataonTransportation,SchoolofComputer&CommunicationEngineering,ChangshaUniversityofScience&Technology,Changsha410114)Abstract:Nowmanyapplicationsoflocationdatahavefacilitatedpeople’sdailylife,solocationdataserviceiscalledakindofnewmobilecomputingservice.However,publishinglocationdatamaydivulgeindividualsensitiveinformationandthenaffectpeople’snormallife.Ontheotherhand,iftheycannotmineandsharedatainformation,datawillloseitsvalueforservingoursociety.So,itisdouble-edgedswordthathowtouselocationdata.Currentlymanyexistingprivacyprotectionschemescannotprovidethebalanceofutilityandprotectionfordata.Furthermore,aslocationdataisdiscrete,someexistingprivacyprotectionschemesaredifficulttoprotectlocationdataindatamining.Theshortarticleproposethatalocationdataprivacyprotectionschemeisbasedondifferentialprivacymechanism,whichemploysthestructureofmultilevelquerytreetoqueryandpublishlocationdataresultondatabase.Intheproposedscheme,theyfirstconstructthestructureofmulti-levelquerytreeondatabase,andthenmakedoubleprocessesofselectingdataonaccessingfrequenciesbytheexponentialmechanismandoneprocessofaddingnoisestoaccessingfrequenciesbytheLaplace’smechanismonthemulti-levelquerytree.Comparedwithotherschemes,whattheexperimentsshowisthedata’savailabilityandprivacyprotectionleveloftheproposedschemeismorehigher,andtherunningtimeoftheproposedalgorithmsisless.KeyWords:locationdata;accessingfrequencies;differentialprivacyprotection;multi-levelquerytree0序言随着信息技术的发展，数据安全性保护越来越被人们注重,政府、企业以及个人对于隐私保护的认识也不断增强。

位置数据主要来始于车联网、移动社交网路、新微博等网路平台，具有种类多、数量大、复杂而又稀疏（低密度性）的大数据特性[1]。一方面，位置数据技术为本文提供了方便的位置服务，带来生活上的便利，如车载导航、智能定位服务等；另一方面，位置服务也会泄漏个人隐私，如功击者依据某人的轨迹，推断出某人出现在某市的频度。目前，位置数据以及位置数据技术应用广泛。在数据挖掘方面，如网店、百度等通过数据挖掘，来推荐相应的产品或则服务；在数据发布方面，联通设备、卫星定位系统和社交网路等获得用户的数据发布出去。研究的前景巨大，但个人隐私泄漏的风险也极大，目前的隐私保护方式很难在数据的保护和数据的效用性间兼具；这么，如何在保护数据的同时又能挺好的为本文提供服务是位置数据隐私保护的优先出版计算机应用研究第35卷关键。位置数据蕴涵了联通对象、空间座标、当前时间和个别独有特征等，离散而又价值高，匿名或则基于匿名的大部份隐私保护方式主要是对非位置数据的保护，而不适宜位置数据的隐私保护，其缘由主要有二点：一是位置数据的复杂性使数据难于表示；二是对背景知识敏感，随着功击者对某人有关位置数据认知的降低，可以剖析出其隐私。

所以，好多隐私保护方式要么是不能保护数据，如匿名方式；要么就是数据的效用性不足，如加密方式。隐私保护的关键是保护数据的同时又具有较高的数据效用性，怎么兼具数据的保护和数据的效用性，是研究的难点。Samarati等人[2,3]首次提出了k-匿名方式以及大量基于k-匿名的方式[4~14]，在好多保护系数不高的领域起着很大的作用。文献[13~15]的研究表明，匿名方式并不能挺好的保护这些来源广泛、数量大的数据；文献[16]提出了加密的通透性保护方式，才能完全保护数据，但数据的可用性不足。传统的位置数据隐私保护技术发展经历了三个阶段：由文献[17]提出的“知情与同意”方法发展到针对单个位置的匿名化处理差分隐私拉普拉斯机制代码，再到对轨迹数据的匿名化处理。因为企业因未能承当预先恳求用户对某位置数据创新性用途后通知用户同意的损失，所以“知情与同意”方法的效用性不足。启发式隐私测度方式[18]、基于机率推论[18]和基于隐私信息检索方式[18]是保护位置数据的常用方式，启发式隐私测度方式主要是对于一些隐私保护不严格的用户进行保护，如k匿名[19]、t紧密型[20]、m不变性[21]、l多样性[22]等技巧；基于信息检索的隐私保护方式能对用户实现完美隐私保护，但因为数据发布都会存在或多或少的隐私信息，所以这方式将造成没有数据可以发布；而基于机率推论的方式在一定条件下能保护数据和实现数据较好的效用性。

但这三种方式都是基于文献[18]提出的统一的功击模型，是在一定背景知识的前提下对位置数据进行保护，但随着功击者对背景知识的降低，这种方式就不能有效地保护数据了，而文献[2-12]也表明了这些关系型的隐私保护方式在通透性保护方面的不足。只有找到一种对背景知识不敏感的保护方式能够肩负起对位置数据保护的重担，而文献[23]提出的差分隐私保护方式因其对背景知识不敏感性正好符合这点。文献[24]应用压缩感知理论提出了一种感知机制，是一种能解决效用性不足的问题，但它破坏了数据之间的联系；而文献[25]提出了一种基于压缩感知机制的一种事务数据发布策略（TDPS）算法，它通过构建查询树把事务中的项与项联系在一上去提升效用性，而且它既缺少效用性上的严谨定义；文献[26]提出DP-topkP方式，在效用上有较为严谨定义，但忽视了事务数据间的联系和单独处理数据的低效处理方法，算法可用性不高。本文提出的LQ-Trie-DPK算法为一种较为严谨的差分隐私保护方式，既能保证数据的高可用性，能够提高算法的可用性，满足位置数据保护的需求。差分隐私的功击模型可以通过严谨的物理推理和定量剖析，通过在查询结果或则输出结果中加入噪音使数据失真，来达到隐私保护的疗效，保证了最小的通透性泄漏和最大的效用性[27]。

主要有拉普拉斯机制和指数机制[28]，后者是针对实数型数据，而前者是针对于非实数型数据。首先是构建位置搜索树[29]（LocationquerytreeLQ-Trie)，其次遍历该树，选定位置访问频度小于min_Count（指定的最小访问值）的N个模式记录，再依据指数机制在N个模式记录中提取其中的k个频繁模式记录，最后基于差分隐私保护的拉普拉斯机制对位置访问频度加入噪音，最后返回加噪的位置搜索树LQ-Trie。本文贡献如下：a）通过构建位置搜索树（LQ-Trie）来表示位置数据，有几大优点：保持了位置数据项间关联；加躁扰动的对象是节点，而不是节点中单独的位置数据，降低了加躁次数和提升了处理数据的效率，增强了位置数据的可用性；处理数据的对象是节点，也提升了位置数据处理的效率。b）差分隐私保护策略因其对背景知识不敏感而适宜于位置数据的保护，具有较好的保护疗效。同时，差分隐私的指数机制和拉普拉斯机制都可以通过隐私预算的分配来抒发隐私保护的程度，比较严谨。c）实验证明，本文的方式比其他方式在数据的可用性和数据的保护程度上要高，但是本文算法的运行时间也更少，效率更高。

1预备工作定义1给定任意相邻的数据集D和’D，且二者之间最多一条记录不同，即1’DD，对于任意算法M，其值域是Range（M），假如算法M在相邻数据集上任意输出结果S（S属于Range（M））满足如下不方程，本文说M满足-差分隐私。SDMeSDM)'(Pr.)(Pr(1)其中，Pr[.]表示算法M在数据集D和’D上的随机性，表示隐私披露的风险几率。隐私保护参数表示隐私预算程度，越大，则表示用户通透性信息保护程度越低，反之，保护程度越高。义定义22差分隐私保护是通过添加噪音实现的方式，假如其敏感度小，这么虽然引入少量的噪音，对查询或则输出结果的变化也小，能挺好的实现数据隐私保护；反之，则须要加入大量的噪音能够对数据实现保护。其中敏感度分为全局敏感度和局部敏感度，设Q为查询函数，dRD，则函数Q的全局敏感度定义如下1′,)'()(maxDQDQQDD(2)其中D和’D表示相邻数据集，Q表示输出结果变化的最大值。

义定义33差分隐私中拉普拉斯机制通过添加拉普拉斯分布优先出版计算机应用研究第35卷的噪音来扰动数据。设基于拉普拉斯机制的隐私保护算法M，噪音服从残差为Q、均值为0的拉普拉斯分布，如式（3）所示噪音的机率密度函数为-ePr,2xx(3)其中x表示具体的变量，参数=Q。在隐私保护对数据进行保护的过程中差分隐私拉普拉斯机制代码，常常会多次用到隐私保护，须要把隐私预算ε分配到各个步骤中去，则须要用到隐私保护的序列组合性质，差分隐私保护序列组合性质如下:质性质1对于同一数据集，隐私保护算法分别为1M、2M、3M,…,nM，隐私预算分别为n,…,,,321，则整个过程的隐私保护预算1nii须要满足差分隐私保护。质性质22对于不相交的数据集，隐私保护算法分别为1M、2M、3M,…,nM,隐私预算分别为n,…,,,321，则整个过程的隐私保护预算}max{i须要满足差分隐私保护。2基于差分隐私机制的位置数据隐私保护方案在频繁模式的数据保护过程中，位置数据的来源广泛且数目大，位置数据模式的项间既独立又互相关联，要提升数据处理的效率和保护后数据的效用性。

首先，构建位置搜索树来保持数据间的联系，降低加躁次数，提升处理数据的效率和数据效用性；其次，只选定访问频度高的位置加噪，突出保护的数据是最容易泄漏隐私的敏感位置。该算法步骤描述如表1所示。表1算法1LQ-Trie-DPK算法基于差分隐私机制的位置数据隐私保护策略(1)输入位置数据集D、差分隐私参数1、2、k、Countmin_，21；(2)基于I（覆盖D的数据集），建立Ｄ的完整位置搜索树（LQ-Trie）IDLST，见2.1节；(3)按层遍历IDLST获得所有满足访问频度不大于Countmin_的频繁模式记录集合A；(4)采用指数机制选出访问频度满足机率为1.Pr.iiNjjaweightaaweight的k个频繁模式记录ia，该集合记为B，见2.2节；(5）对集合B中选择出的k个模式记录ib的访问频度添加服从拉…