平码五不中公式规律
  • / 18
  • 下载费用:30 金币  

基于频率的轨迹抑制数据发布隐私保护的系统及其方法.pdf

关 键 ?#21097;?/dt>
基于 频率 轨迹 抑制 数据 发布 隐私 保护 系统 及其 方法
  专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
摘要
申请专利号:

CN201410088673.7

申请日:

2014.03.12

公开号:

CN103914659A

公开日:

2014.07.09

当前法律状态:

授权

有效性:

有权

法?#19978;?#24773;: 授权|||实质审查的生效IPC(主分类):G06F 21/60申请日:20140312|||公开
IPC分类号: G06F21/60(2013.01)I; G06F17/30 主分类号: G06F21/60
申请人: 西安电子科技大学
发明人: 李兴华; 张渊; 高胜; 邓凌娟; 赵婧; 王二蒙; 马建峰; 姚青松; 姜奇; 毛立强
地址: 710071 陕西省西安市太白南路2号西安电子科技大学
优?#28909;ǎ?/td>
专利代理机构: 北京科亿知识产权代理事务所(普通合伙) 11350 代理人: 汤东凤
PDF完整版下载: PDF下载
法律状态
申请(专利)号:

CN201410088673.7

授权公告号:

||||||

法律状态公告日:

2017.01.11|||2014.08.06|||2014.07.09

法律状态类型:

授权|||实质审查的生效|||公开

摘要

本发明公开了一种基于频率的轨迹抑制数据发布隐私保护的系统,所述系统具有若干发布消息的用户,用于收集所述用户的发布消息的数据收集服务器,所述系统还包括与所述数据收集服务器连接的匿名服务器,所述匿名服务器设有数据预处理模块,隐私保护模块,数据效用衡量模块。本发明利用所述系统提出一种方案,采用特定的轨迹局部抑制法进行匿名处理。该方案基于轨迹频率进行匿名处理,且在满足用户隐私需求的同时最大程度地提高了匿名数据的效用。并通过多次实验在同等隐私需求的情况下,匿名后的数据效用提升?#31169;?0%,使得方案在解决数据发布的问题?#22791;?#26377;现实意义。

权利要求书

权利要求书
1.  基于频率的轨迹抑制数据发布隐私保护的系统,所述匿名服务器设有数据预处理模块,隐私保护模块,数据效用衡量模块,其中
所述数据预处理模块:对收集到的原始数据进行预处理,即?#36816;?#36848;原始数据按照用户身份进行归类,并将同一用户身份的所有位置数据按照时间戳排序,最终形成用户的原始轨迹序列集合;
所述隐私保护模块:对预处理后的轨迹序列集合进行隐私保护处理,即根据用户的隐私需求,?#19994;?#19981;满足用户隐私容忍度的轨迹序列集合,然后将这些集合按照频率进行排序,从而得到安全的可发布的轨迹数据集合;
所述数据效用衡量模块:负责评估经过所述隐私保护模块处理后的轨迹数据集合的可用性,即统计匿名轨迹数据集的数据效用。

2.  根据权利要求1所述的系统,其特征在于,所述隐私保护模块对不满足用户隐私需求的轨迹序列集合进行排序后,可对即将发布的轨迹数据集进行轨迹局部抑制。

3.  一种根据权利要求1所述的系统实现抑制数据发布隐私保护的方法,其特征在于,所述方法包括:
S1收集并预处理原始数据,并最终形成若干用户的原始轨迹序列集合;
S2?#36816;?#36848;原始轨迹序列集合进行匿名处理,其中包括:
S2.1在所述原始轨迹序列集合中?#19994;?#19981;满足用户隐私容忍度的有问题的投影集VP;
S2.2将问题投影集VP中的所有轨迹按照其在原始轨迹序列集合中出现的频率进行降序排序,并将结果保存到集合FVP;
S3搜索所述集合FVP中前|PS|个出现频率最高的轨迹投影记?#36857;?#23545;其进行匿 名处理,其中,所述匿名处理包括轨迹抑制处理,直至或结束匿名处理;
S4对经过所述匿名处理后的轨迹序列集合可进行发布。

4.  根据权利要求3所述的方法,其特征在于,所述匿名处理还包括局部抑制处理,其中:
S100在所述集合FVP中?#19994;?#26368;小的违反隐私需求的轨迹序列集,并保存到轨迹集合MVP;
S101根据攻击者的知识计算所述轨迹序列集MVP?#20852;?#26377;轨迹点的R(PG(loci),UL(loci))值,每次?#19994;絉(PG(loci),UL(loci))?#21040;?#22823;的轨迹点loci,并在原始轨迹集中?#19994;?#19982;MVP中的所有包含位置信息的轨迹记录相对应的轨迹集,抑制该轨迹集中的位置信息loci,此处理需迭代进行,直至束。

5.  根据权利要求3所述的方法,其特征在于,若所述集合FVP为空集,则表?#38236;?#21069;原始轨迹序列集合为安全状态,可进行发布。

说明书

说明书基于频率的轨迹抑制数据发布隐私保护的系统及其方法
技术领域
本发明涉及通信领域中的数据发?#36857;?#20855;体涉及一种基于频率的轨迹抑制数据发布隐私保护的系统及其方法。 
背景技术
随着由于移动设备和定位技术的广泛使用,会产生大量的移动对象轨迹数据;轨迹数据含有丰富的时空信息,对其分析和挖掘可以支持多种与移动对象相关的应用,这一?#29575;?#24050;经激发了数据挖掘的研究,并应用于实际生活中,如城市交通管理等。然而,这些轨迹数据中往往包含了关系到个人敏?#34892;?#24687;的隐私数据。若数据发布者者对数据不做任?#26410;?#29702;直接发?#36857;?#23545;个人来说,其敏?#34892;?#24687;会被泄露。然而,随着个人对其隐私信息保护需求的增长,数据发布中隐私保护问题目前已成为数据挖掘领域研究热点之一。由于个人对隐私的关注,数据发布者对数据进行发布?#20445;?#19968;方面要使得发布的匿名数据不泄露个体的隐私信息,即保证攻击者不能以高置信度推测出目标个体的敏?#34892;?#24687;;另一方面需要保证发布的匿名数据具有高可用性,即仍然能够根据发布的匿名数据进行较准确的数据分析,如集合查询等,这就要求匿名后的数据效用要尽可能的高。因此,如何在满足用户隐私需求的情况下尽可能地提升匿名数据的利用率是必须要解决的问题。 
目前大部分方案都采用轨迹k-匿名技术实现轨迹匿名。基于GPS定位的不精确性,Abul“Never wa lk a lone:uncerta inty for anonymity in moving  objects databases”等提出NWA匿名算法通过轨迹聚簇和空间转换来实现所提出的(k,δ)-匿名模型,其中表示定位误差。通过将轨迹k-匿名集合的构建问题抽象为图模型,Huo“History trajectory privacy-preserving through graph partition”等提出根据轨迹间的距离来划分合适的轨迹k-匿名集合。考虑到用户对轨迹隐私和数据效用的不同需求,Gao“Balancing Trajectory Privacy and Data Utility using a Personalized Anonymization Model”等提出一种个性化匿名模型以构建合适的匿名集合用来均衡两者的关系。此外,与本发明最相关的工作“Privacy preservation in the publication of trajectories”采用轨迹抑制技术来解决。引文“Privacy preservation in the publication of trajectories”等研究了轨迹数据发布过程中的隐私保护问题。数据库中的轨迹集记录了大量用户的交易位置序列信息,交易位置序列通过他们使用的信用卡或RFID借?#24378;?#33719;取。例如:一个智能RFID卡公司(拥有该智能卡的用户可以在很多场所进行各?#32440;?#26131;如商店,停车场,餐馆等)能够发行一种智能卡,通过智能卡能够跟踪所有用户的交易记?#36857;?#21487;统计大量用户的日常轨迹数据。在本例中,数据发布者是该智能卡公司,而攻击者是交易的各种场所如商店等,如果?#33945;?#24215;是连锁店,则攻击者可能知道用户轨迹数据中的多个数据。上文引文“Privacy preservation in the publication of trajectories”证明了如果这样的轨迹数据完全公布(仅隐藏用户的身份),对于持有部分轨迹信息的攻击者来说,这无疑是一个高风险的泄露用户隐私的行为。针对这一问题,文中引文“Privacy preservation in the publication of trajectories?#24065;?#20837;了有问题的投影集概念,且提出以部分轨迹作为一个准标识符来标识其它位置的一种轨迹抑?#39057;?#26041;案来解决用户隐私泄露的问题。但该方案存在以下问题:1、采用全 局抑制方案对数据进行处理,导致匿名数据的效用?#31995;停?、没有考虑到频率,从而匿名数据对于基于统?#39057;?#25968;据挖掘效用较差。 
近年来,研究人员针对数据发布中隐私保护问题,提出了多?#32440;?#20915;方案,如K-匿名,L-多样性及与RFID相关的匿名轨迹数据隐私保护技术等。 
K-匿名和L-多样性 
在轨迹发布的研究中,关于保护用户隐私的问题已进入微观数据库,例如,一家医院公布病人的诊断记?#36857;?#20197;便于研究人员研究各种疾病的特征,但是每一条记录中通常包含一个或多个敏感的属性(例如疾病),且包含个人的身份属性(如姓名),为了保护个人的隐私信息不被泄漏,往往会在信息发布之前去掉身份属性,从而认为个人隐私信息是安全的。但是这种想法是错误的,因为存在其他一些属性的组合仍然可以唯一地或近似标识出某一元组,这些属性如果与得到的其他公开发布的信息进行链接往往会导致个人隐私信息的泄露。引文“k-anonymity:A model for protecting privacy”证明了在发布这些数据前,只隐藏明确的身份(如姓名,身份证)是?#36824;?#30340;。特别是通过将一组非敏感属性集作为一个人的属性,即准标识符(如(性别,年龄,?#25910;?#32534;码)),恶意攻击者根据准标识符能够推断出他/她的记录。例如通过加入公共投票登记数据库,数据库中病人的身份是匿名的,但是通过比较准标识符表,人?#24378;?#20197;很容易地推断出病人的身份。为了防止这种链接攻击,即属性链接攻击,很多学者提出K-匿名“Protecting respondents’ident ities in micro data release?#20445;癎eneralizing data to provide anonymity when disclosing information”的方法,在发布这些数据库中的记?#25216;?#20043;前,先抑制或是概括准标示符的属性值,从而使每条记录至少有K-1个人拥有相同的准标示符值。 
尽管通过K-匿名可以防止属性链接攻击,但是攻击者无须准确匹配目标对象在发布数据表中的记?#36857;?#26681;据准标识符,按照其所在的等价类仍能够推断出其敏感属性的取值,同样会导致个人隐私的泄露。为了防?#26500;?#20987;者进行该类攻击,近来的许多学者又提出另一?#32440;?#20915;方案:L-多样性‘L-diversity:privacy beyond k-anonymity”。L-多样性模型要求每个QID分组中对应的敏感属性至少有L个well-represented取值,即要求发布者应使得按QID得到的记录分组中的敏感属性取值多样化,即分布尽可能的均?#21462;?#26412;发明处理的问题和上述问题存在两方面的不同:1、敏感属性取值并不是绝对的,而是和攻击者相关联的,即对于一条记录来说,考虑某一攻击者?#20445;?#35760;录中该攻击者知道的信息标记为准标识符,其余的标记为敏感属性值。2、通过本发明的定义可知,这里的准标识符对应轨迹投影,其长度?#24378;?#21464;的。因此本发明要解决的问题不同于以往的问题。 
匿名轨迹数据隐私保护技术 
近年来,学者从不同的角度研究轨迹数据的匿名技术。引文“Never walk alone:uncertainty for anonymity in moving objects databases”提出(K,D)-匿名技术,其基于采样和定位系统的不精确性,其中d表示位置的不精确度,总体思想是基于空间平?#35780;?#20462;改路径的轨迹,使得k个不同轨迹共同存于一个半径为d的圆柱体。然而当轨迹数据来源于交易记?#36857;琑FID数据及购买记录?#20445;?#19981;精确的假设可能不成立。由于轨迹数据的高维性,引文“Pattern-preserving k-anonymization of sequences and its application to mobility datamining?#20445;癙rivacy preservation in the publication of trajectories?#20445;癆nonymizing moving objects:How to hide a MOB in a crowd?”研究了基于一种简化?#38382;?nbsp;的轨迹数据的匿名问题,仅考虑时间的顺序即序列轨迹。引文 
“Pattern-preserving k-anonymization of sequences and its application to mobility data mining”提出一种顺序数据的变型K-匿名模型,主要通过插入、删除或替换某些数据项实现K-匿名。引文“Privacy preservation in the publication of trajectories”进一步假设不同的对手可能拥有不同的背景知识,且数据发布者要知道所有这些对抗性知识,其目的是防止对手从公布的顺序数据中获得额外的信息。引文“Anonymizing moving objects:How to hide a MOB in a crowd?”提出了一种新的基于移动物体的K-匿名概念,不同的移动物体可以具有不同QID。然而他们仅是通过防止身份链接攻击来实现隐私保护,而本发明要求不仅可以防止身份链接的攻击,同?#24065;?#35201;能够防止属性攻击,以适应新兴的轨迹数据发布方案。 
引文“Privacy preservation in the publication of trajectories?#20445;癇alancing Trajectory Privacy and Data Utility using a Personalized Anonymization Model?#20445;癙rivacy-preserving trajectory data publishing by local suppression”针对属性攻击问题,提出了通过对轨迹数据集进行抑制实现K-匿名。引文“Privacy preservation in the publication of trajectories?#24065;?#20837;了有问题的投影集概念,并采用全局抑制对其进行处理,?#28304;?#21040;满足用户隐私需求的目的;引文“Balancing Trajectory Privacy and Data Ut ility us ing a Personalized Anonymization Model?#20445;癙rivacy-preserving trajectory data publishing by local suppression”研究了与RFID相关的轨迹数据发布的隐私安全问题。提出了LKC-匿名隐私模型,其中L代表攻击者可获取的轨迹序列长度,C代表隐私需求;通过对轨迹集进行处理?#19994;?#36829;反隐私需求的轨迹序列集, 并采用局部抑制方法实现隐私保护。然而引文“Balancing Trajectory Privacy and Data Utility using a Personalized Anonymization Model?#20445;?nbsp;
“Privacy-preserving trajectory data publishing by local suppression”所解决的问题不同于本发明的问题,其更关注解决轨迹发布的高维性问题,且并没有考虑攻击者的数量;而引文“Privacy preservation in the pub lication of trajectories”中攻击者数量?#24378;?#21464;的,但是其所采用保护用户隐私的轨迹抑制方法,导?#29575;?#25454;效用?#31995;汀?nbsp;
发明内容
鉴于现有技术的不足,本发明旨在于提供一种基于频率的轨迹抑制数据发布隐私保护的系统及其方法,提出?#31169;?#20915;用户轨迹发布中隐私保护的一种方案,通过对有问题的投影集进行局部抑制防止多个攻击者进行属性攻击保证用户轨迹隐私需求。 
需要说明的是,本发明提出一种匿名方案,通过求解隐私关联度和数据效用之间的关系对轨迹数据进行局部抑制,在每?#25991;?#21517;处理过程中,将对整条轨迹记录的抑制改为抑制轨迹中的某一位置数据,有效地提升了数据效用和性能,并通过多次仿真实验,在满足用户隐私需求的情况下,将匿名数据的效用提升?#31169;?0%。 
需要进一步说明的是,轨迹数据集相关定义如下: 
轨迹数据集T是所有用户轨迹序列的集合,?#38382;?#21270;表示为: 

其中,ti表示用户i的运动轨迹,代表用户i的历史足迹。 
对每个用户i,其运动轨迹ti是由n个不同时刻timei的位置序列组成,可表示 为: 
ti={<loc1(x1,y1),time1?#23613;糽ocn(xn,yn),timen>} 
其中<loci(xi,yi),timei>代表timei时刻用户i所在的具体位置。 
为了简化处理,轨迹序列包含用户的位置信息,且位置信息按照时间timei升序排列;Table3.1、Table3.2、Table3.3及Table3.4是为了方便理解,在后续部?#21482;嵋源宋?#20363;进?#20852;?#26126;,这里仅有两个攻击者a,b,且用户的隐私容忍度Pbr设置为0.5。 
定义3.1轨迹记?#36857;?#36712;迹记录是由n个位置信息按照时间顺序组成的长度为n的一条记录t=<loc1,loc2,......,locn>,其中loci∈A。 
A是数据发布?#34892;?#21487;以掌控的所有位置,这里我们假设A={a1,a2,a3,b1,b2,b3),如智能卡公司(相当于数据发布?#34892;?可以发行一种智能卡,A代表的?#24378;梢运?#35813;种卡的所有位置,如商店,停车场等;由于存在商业垄断,一个商店可能拥有不同的分商店。A被分为m个互不相交的?#24378;?#23376;集,即根据表1有A=A1∪A2,A1={a1,a2,a3},A2={b1,b2,b3}; 
表1轨迹数据集T 
τidrajectory τ1a1→O1→a2τ2a1→O1→a2→O3τ3a1→O2→a2τ4a1→a2→O2τ5a1→a3→o1τ6a2→a3→O1τ7a2→a3→O2t3a2→a3→o2→o3
表2攻击者va的知识TPa
τidrajectory τ1a1→a2τ2a1→a2τ3a1→a2τ4a1→a2τ5a1→a3τ6a2→a3τ7a2→a3τ3a2→a3
表3匿名轨迹集T2′ 
τidrajectory t1a1→o1→a2t2a1→o2→a2t3a1→o2→a2t4a1→a2→o2t5a3→O1 t6a3→O1t7a3t3a3→O2t9a3→o2
攻击者模型 
这里我们假定潜在的攻击者数量为m个,则有其中V为攻击者集合;每个攻击者vi可以掌控Ai中包含的所有位置信息,则有:且针对每一条轨迹记录t∈T,每一个攻击者vi∈V?#21152;?#26377;一个投影知识 定义如下。 
定义3.2投影:若仅考虑一个攻击者v,则一条轨迹记录t=<loc1,loc2,......,locn>的投影为称tv为t相对于攻击者v的投影。 
这里,tv即称之为攻击者v的投影知识,投影tv是t的一个子轨迹记?#36857;?#20165;由t中属于Av的所有位置数据点组成。因此,每一个攻击者将会拥?#20852;?#26377;轨迹数据集T中的投影集TPv,且如攻击者v的投影集TPa(如表3.2)就是根据定义2通过轨迹记?#25216;疶(如表3.1)得到。 
攻击者v所拥有的知识仅是TPv,攻击者可以根据其拥有的知识TPv很容易地推断出经过tv中全部位置的所有用户的身份信息,进而推断出其他信息。对该问题,我们进行如下定义: 
定义3.3给定原始轨迹数据集T,T′是T经过处理后要公布的轨迹数据集;若每一个攻击者v都不能以高于Pbr概率准确地推断出?#25105;?#20301;置信息locj,这里则认为T′是安全的,可以公开发?#36857;?#21542;则就不安全,不能公开发布。 
本部分主要考虑攻击者可能发起的攻击:(1)身份连接攻击:由于攻击者掌握用户的部分信息和对应的用户身份信息,所以攻击者可以根据这些局部信息实行身份连接攻击,从而推断出用户的身份;(2)属性链接攻击:攻击者根据掌握的用户的局部信息作为用户的准标识符发起属性连接攻击,从而推断出用户的其他属性信息; 
我们不希望攻击者v,拥有关于轨迹记录t的投影tv的知识,从即将要发布的轨迹数据集T′中推断出其他任何不属于tv的位置信息或者用户的身份信息,即进行身份连接攻击和属性连接攻击;这一问题类似于1-多样性问题“Privacy protection for RFID data?#20445;癢alking in the crowd:anonymizing trajectory  data for pattern analysis?#20445;?#20854;中tv中的位置信息类似于准标识符QID,而其他的位置信息则类似于敏感属性S。该问题和以往的轨迹数据发布问题相比,有很大不同;随着攻击数量的变化,从不同攻击者的角度出发,每一个攻击者的投影知识tv∈TPv都可以作为轨迹记录t的准标识符QID,由于tv的长度?#24378;?#21464;长的,因此,每一条轨迹记录t∈T的准标示符?#38469;强?#21464;长的,且可能有多个;对于每一条轨迹记录t∈T,其敏感属性S也是不唯一的,可能有多个;综上所述,本文研究的问题和以往不同的是:(a)准标识符QID?#24378;?#21464;长的,且可能有多个;(b)敏感属性S不是唯一的,可能是多个;(c)攻击者也是不唯一的,可能有多个。 
隐私保护模型 
由于攻击者拥有局部的轨迹信息,仅移除或隐藏原始轨迹集集中的身份信息如ID,攻击者仍然能够以一定的概率推断出用户的身份和其他敏?#34892;?#24687;,从而导致用户的隐私受到威?#30149;?#20026;了保护用户的隐私在其可容忍度Pbr范围内,我们定义了如下隐私模型Pbr-privacy,该模型保证了攻击者不会以高于Pbr的概率推断出?#25105;?#29992;户的身份信息和其它不?#36824;?#20987;者所掌握的位置信息(亦称之为敏?#34892;?#24687;)。 
S(tv,TPv):根据定义3.2从轨迹数据集T中?#19994;?#25915;击者v的投影知识TPv,并从TPv中?#19994;?#28385;足特定条件的所有轨迹记?#25216;疭(tv,TPv),S(tv,TPv)={t′|t′∈TPv∧t′=tv}。 
S(tv,TPv)是攻击者v的投影知识TPv?#20852;?#26377;与轨迹tv相同的轨迹形成的集合,如攻击者a的投影集TPa如表2,若ta={a1→a2},则S(ta,TPa)是用户t1→t4的轨迹集合。攻击者v根据S(tv,TPv)推断出其他位置locj的概率为p(locj,tv,T′)=sup(locj,tv,T′)/|S(TV,T′)|,为了使匿名的数据T′在一定程度上保护用户的隐私(假设用户的隐私容忍度为Pbr), 我们进行如下定义: 
Pbr-privacy:若且若p(locj,tv,T′)<Pbr成立,则认为T→T′的转换是安全的,可以公开发布T′;若p(locj,tv,T′)>Pbr,则认为T→T′的转换是不安全的,并标记tv为有问题的投影轨迹,根据特定匿名算法对有问题的投影记录作处理,使得T→T′的转换是安全的。 
如果所有的攻击者从T′中推断出?#25105;?#19981;被自身掌握的位置信息的概率都小于用户的隐私容忍度Pbr,则表明该轨迹数据集T′满足了用户的隐私需求,是安全的数据集,可以进行发布。如表1中数据集T不能够直接发?#36857;?#32780;经过匿名处理的数据集T′则是安全的,可以发布。 
数据效用 
数据发布者发布轨迹数据的目的是为了让接?#29031;?#36827;行数据挖掘;为了尽可能满足多个接?#29031;?#23436;成不同的数据挖掘任务,使其更好的服务于社会,我们不得不考虑如何提高数据效用UL。本部分给出一种数据效用的定义。(当然UL?#37096;?#20197;根据不同的需求进行不同的定义): 
若原始轨迹数据集T的足迹个数记作|T|,匿名的轨迹数据集T′中的足迹个数记作|T′|,则有: 

若UL的值越小,数据效用越好;若UL的值越大,数据效用越差。 
基于上述描述,本发明采用的技术方案如下: 
基于频率的轨迹抑制数据发布隐私保护的系统,所述系统具有若干发布消息的用户,用于收集所述用户的发布消息的数据收集服务器,所述系统还包括与所述数据收集服务器连接的匿名服务器,所述匿名服务器设有数据预处理模 块,隐私保护模块,数据效用衡量模块,其中 
所述数据预处理模块:对收集到的原始数据进行预处理,即?#36816;?#36848;原始数据按照用户身份进行归类,并将同一用户身份的所有位置数据按照时间戳排序,最终形成用户的原始轨迹序列集合; 
所述隐私保护模块:对预处理后的轨迹序列集合进行隐私保护处理,即根据用户的隐私需求,?#19994;?#19981;满足用户隐私容忍度的轨迹序列集合,然后将这些集合按照频率进行排序,从而得到安全的可发布的轨迹数据集合; 
所述数据效用衡量模块:负责评估经过所述隐私保护模块处理后的轨迹数据集合的可用性,即统计匿名轨迹数据集的数据效用。 
需要说明的是,所述隐私保护模块对不满足用户隐私需求的轨迹序列集合进行排序后,可对即将发布的轨迹数据集进行轨迹抑制并适时添加假数据;可对即将发布的轨迹数据集进行轨迹局部抑制。 
一种实现抑制数据发布隐私保护的方法,所述方法包括: 
S1收集并预处理原始数据,并最终形成若干用户的原始轨迹序列集合; 
S2?#36816;?#36848;原始轨迹序列集合进行匿名处理,其中包括: 
S2.1在所述原始轨迹序列集合中?#19994;?#19981;满足用户隐私容忍度的有问题的投影集VP; 
S2.2将问题投影集VP中的所有轨迹按照其在原始轨迹序列集合中出现的频率进行降序排序,并将结果保存到集合FVP; 
S3搜索所述集合FVP中前|PS|个出现频率最高的轨迹投影记?#36857;?#23545;其进行匿名处理,其中,所述匿名处理包括轨迹抑制处理,直至或结束匿名处理; 
S4对经过所述匿名处理后的轨迹序列集合可进行发布。 
需要说明的是,所述匿名处理还包括局部抑制处理,其中: 
S100在所述集合FVP中?#19994;?#26368;小的违反隐私需求的轨迹序列集,并保存到轨迹集合MVP; 
S101根据攻击者的知识计算所述轨迹序列集MVP?#20852;?#26377;轨迹点的R(PG(loci),UL(loci))值,每次?#19994;絉(PG(loci),UL(loci))?#21040;?#22823;的轨迹点loci,并在原始轨迹集中?#19994;?#19982;MVP中的所有包含位置信息的轨迹记录相对应的轨迹集,抑制该轨迹集中的位置信息loci,此处理需迭代进行,直至束。 
需要说明的是,若所述集合FVP为空集,则表?#38236;?#21069;原始轨迹序列集合为安全状态,可进行发布。 
本发明有益效果在于,在满足用户隐私需求的同?#20445;?#26174;著地改善了匿名的数据质量,不同程度地提升了数据效用,很好地解决了数据发布中用户的隐私需求和数据效用之间的均衡问题;本发明通过多次实验证明了在同等隐私需求的情况下,匿名后的数据效用提升?#31169;?0%,使得方案在解决数据发布的问题?#22791;?#26377;现实意义。 
附图说明
图1为本发明方案与对比方案的比较?#36857;?nbsp;
图2为本发明方案与对比方案的另一种比较?#36857;?nbsp;
图3为本发明方案与对比方案的另一种比较图。 
具体实施方式
下面将结合附图对本发明作进一步的描述。需要说明的是,本实施例在以本发明技术方案为前提下进行实施,给出了详细的实施方式和具体的操作过程,但本发明的保护范围不限于?#29575;?#30340;实施例。 
本发明为一种基于频率的轨迹抑制数据发布隐私保护的系统,所述系统具有若干发布消息的用户,用于收集所述用户的发布消息的数据收集服务器,所述系统还包括与所述数据收集服务器连接的匿名服务器,所述匿名服务器设有数据预处理模块,隐私保护模块,数据效用衡量模块,其中 
所述数据预处理模块:对收集到的原始数据进行预处理,即?#36816;?#36848;原始数据按照用户身份进行归类,并将同一用户身份的所有位置数据按照时间戳排序,最终形成用户的原始轨迹序列集合; 
所述隐私保护模块:对预处理后的轨迹序列集合进行隐私保护处理,即根据用户的隐私需求,?#19994;?#19981;满足用户隐私容忍度的轨迹序列集合,然后将这些集合按照频率进行排序,从而得到安全的可发布的轨迹数据集合; 
所述数据效用衡量模块:负责评估经过所述隐私保护模块处理后的轨迹数据集合的可用性,即统计匿名轨迹数据集的数据效用。 
需要说明的是,所述隐私保护模块对不满足用户隐私需求的轨迹序列集合进行排序后,可对即将发布的轨迹数据集进行轨迹抑制并适时添加假数据;可对即将发布的轨迹数据集进行轨迹局部抑制。 
一种实现抑制数据发布隐私保护的方法,所述方法包括: 
S1收集并预处理原始数据,并最终形成若干用户的原始轨迹序列集合; 
S2?#36816;?#36848;原始轨迹序列集合进行匿名处理,其中包括: 
S2.1在所述原始轨迹序列集合中?#19994;?#19981;满足用户隐私容忍度的有问题的投影集VP; 
S2.2将问题投影集VP中的所有轨迹按照其在原始轨迹序列集合中出现的频率进行降序排序,并将结果保存到集合FVP; 
S3搜索所述集合FVP中前|PS|个出现频率最高的轨迹投影记?#36857;?#23545;其进行匿名处理,其中,所述匿名处理包括轨迹抑制处理,直至或结束匿名处理; 
S4对经过所述匿名处理后的轨迹序列集合可进行发布。 
需要说明的是本发明提出一种局部抑?#39057;?#26041;案,通过求解隐私关联度和数据效用之间的关系对轨迹数据进行局部抑制,在每?#25991;?#21517;处理过程中,将对整条轨迹记录的抑制改为抑制轨迹中的某一位置数据,有效地提升了数据效用和性能。 
需要进一步说明的是,所述匿名处理还包括局部抑制处理,其中: 
S100在所述集合FVP中?#19994;?#26368;小的违反隐私需求的轨迹序列集,并保存到轨迹集合MVP; 
S101根据攻击者的知识计算所述轨迹序列集MVP?#20852;?#26377;轨迹点的R(PG(loci),UL(loci))值,每次?#19994;絉(PG(LOci),UL(loci))?#21040;?#22823;的轨迹点loci,并在原始轨迹集中?#19994;?#19982;MVP中的所有包含位置信息的轨迹记录相对应的轨迹集,抑制该轨迹集中的位置信息loci,此处理需迭代进行,直至束。 
需要进一步说明的是,所述局部抑制处理包含: 
(1)IVPA处理,从原始轨迹数据集T中?#19994;?#19981;满足用户的隐私容忍度Pbr的有问题的投影集VP; 
(2)FVPA处理:将有问题的投影集VP中的所有轨迹按照其在轨迹集T中出现的频率进行排序,并将结果保存到集合FVP; 
(3)IMVA处理:在有问题的投影集FVP中?#19994;?#26368;小的违反隐私需求的轨迹序列集,并保存到轨迹集合MVP的算法IMVA; 
(4)TAA_1处理:根据攻击者v的知识Av计算轨迹序列集MVP?#20852;?#26377;轨迹点的R(PG(loci),UL(loci))值,每次?#19994;絉(PG(loci),UL(loci))?#21040;?#22823;的轨迹点loci,并在原始轨迹集T中?#19994;?#19982;MVP中的所有包含位置信息的轨迹记录相对应的轨迹集,抑制该轨迹集中的位置信息loci,此步骤需迭代进行,直至结束。 
IVPA处理 
为了更好的理解对原始轨迹数据集T所采用的匿名处理过程,进行以下定义: 
VPv:攻击者v推断出其他位置locj的概率为P(locj,tv,T′);若P(locj,tv,T′)>Pbr,则记录tv为有问题的轨迹投影,VPv={tv|tv∈TPV∧P(locj,tv,T′)>Pbr}。 
这里VPv是攻击者v的投影知识TPv中有问题的投影集,即攻击者能够以高于用户的隐私容忍度Pbr的概率推断出与VPv中的轨迹记录相对应的原始轨迹中其他的位置信息;这样的轨迹记录对于用户来说,是不安全的,所以需对其进行匿名处理。由于这里有m个攻击者,所以有: 

例如:对于攻击者a,b来说,由表1、表2及上述定义可知,有问题的投影集为: 
VPa={a1→a3,a2→a3}, 
VPb={b1,b1→b3,b2,b2→b3} 
VP={a1→a3,a2→a3,b1,b1→b3,b2,b2→b3}。 
IVPA处理描述: 
IVPA伪代码描述: 
输入:原始轨迹集T,用户容忍度Pbr,每一个攻击者v所掌握的位置集合Av; 
输出:违背用户隐私需求的投影集合VP; 
for all v in V and t in T 
//根据定义3.2,求取每一攻击者v的投影知识TPv; 
for all tv∈TPv do 
sup(locj,tv,T):=0;//初始化sup(locj,tv,T)为0; 
for all v∈V do 

calculate sup(locj,tv,T);//统计原始轨迹集?#20852;?#26377;不属于攻击者v的位置数据出现的次数; 
for all v∈V do 
calcula teS(tv,TPv)oftvin TPV;//统计轨迹投影记录tv在集合TPv出现的次数; 
for all tv∈TPv do 
p(locj,tv,T)=sup(locj,tv,T)/|S(tv,T)|; 
If P(locj,tv,T)>Pbr then 
VPv:=push_back(VPv);//?#19994;?#25152;有不满足用户隐私需求的轨迹影tv,并将其保存到集合VPv中; 
for all v in V do 
VP:=push_bACk(VPV);//?#19994;?#25152;有有问题的投影集合VP; 
FVPA处理 
该处理基于IVPA,将有问题的投影集VP中的轨迹序列按照其在原始轨迹集T中出现的次数降序排列,使出现频率较高的轨迹序列优先得到处理,通过多次实验,发现该算法在一定程度上可以减少被抑?#39057;?#28857;数。 
例如:对攻击者a来说,其轨迹序列{a1→a2}、{a1→a3}、{a2→a3},分别出现的次数为4、1、3,排序后的结果是: 
{a1→a2}→{a2→a3}→{a1→a3}。 
FVPA处理描述: 
FVPA伪代码描述: 
输入:违背用户隐私需求的投影集合VP 
输出:依据频率降序排列有问题的轨迹投影集合FVP, 
for all v in V do 
for all tv∈VPv do 
f(tv,VPv):=0;//初始化f(tv,VPv),该集合用于保存轨迹投影记 
录tv在VPv中出现的次数; 
for all v∈V do 
for alltv∈VPv do 
calculate the frequency f(tv,VPv)oftvwhich occurs inVPv;//统计 
所有的轨迹投影记录tv在集合VPv中出现的次数; 
F(tv,frequency):=push_back(tv,f(tv,VPv));//将轨迹投影和对应出现的次数保存到集合FVPv中; 
for all v∈V do 
sort al l trajectories inVPvindescending order according to the frequency F(tv,VPv),and save them inFVPv;//将所有有问题的投影轨迹记?#21450;?#29031;频率降序排列; 
FVP:=push_back(FVPv); 
IMVA算法 
MVPv:若或?#20445;?#21017;将合并为则有
为了提升匿名数据的效用,该处理仅通过对有问题的投影集FVPv进行合并,将集合FVPv缩小,从而得到最小的有问题的投影集MVPv。由于这里有m个攻击者,所以有: 

例如:对于攻击者a,b来说,FVPa={a2→a3,a1→a3},FVPb={b1,b2,b1→b3,b2→b3};通过算法IMVA,得到MVPa={a2→a3,a1→a3},MVPb={b1,b2}。 
IMVA处理描述: 
MVPA伪代码描述: 
输入:依据频率降序排列的有问题的轨迹投影集合FVP; 
输出:最小的有问题的轨迹投影集合MVP; 
for all vin V do 
for alldo 
Iforthen 

replace all the trajectoriesandin FVPvwith
call Alg.IVPA and Alg.FVPA;//将集合FVPv?#20852;?#26377;包含关系或子集关系的投影记录和用代替; 
else do 
//若找不到包含关系或子集关系?#20445;?#21017;轨迹记录保存到集合MVPv; 
for all v∈V do 
MVP:=push_back(MVPv); 
TAA_1处理: 
在对数据集T进行匿名处理前,我们需要进行如下定义: 
R(PG(loci),UL(loci))=PG(loci)/(UL(loci)+1) 
PG(loci):我们定义其为与位置loci相关的隐私关联度,代表由删除点loci所带来的隐私收益,其值为集合MVPv中包含点loci的不同的轨迹个数;但是当某一位置点仅和自身关联?#20445;?#20854;隐私关联度仍定义为1。因为若将隐私关联度定义为0,当多个位置都和自身关联,导致多个位置的R值是相同的,会造成对位置点的随机删除,因此,为了避免该种情况的出现,将其定义为1,那么出现次数较少的点便会优先被抑制,从而提升数据的效用。UL(loci):代表由删除位置点loci的所带来的信息损失量,其值为MVPv?#20852;?#26377;的轨迹中包含点loci的总数;PG(loci)的值越大,代表由删除点loci所带来的隐私收益越大,且信息损失量越小。 
该匿名算法不同于以往的轨迹匿名算法,这里我们采用局部抑制轨迹集MVP?#26800;?#30340;方法对轨迹数据集T进行匿名处理;为了获得好的隐私收益和较高的数 据效用,在处理轨迹集MVP中的位置信息?#20445;?#20248;先抑制PG(loci)最大的点loci,从而使得?#21487;?#38500;一个点loci所带的隐私保护和数据效用都同时达到最优。具体处理描述如下: 
表4R(PG,UL)值 
位置数据 PG UL R(PG,UL) a11 1 1 a21 3 0.33 a32 4 0.5 O11 4 0.25 O21 4 0.25
例如:对于攻击者a,b来说,MVPa={a2→a3,a1→a3},MVPb={b1,b2}。按照上述定义计算得到表4;由表4知R(PG(a1)1UL(a1))最大,由于轨迹a1→a3对应T′中的轨迹a1→a3→b1,所以删除轨迹a1→a3→b1中的点a1,即a1→a3→b1变为a3→b1,循环迭代,直至结束,最终结果如表3。 
TDA_2处理描述: 
TDA_2伪代码描述: 
输入:原始轨迹集T,用户容忍度Pbr,每一个攻击者v所掌握的位置集合Av; 
输出:可发布的安全的轨迹数据集T′; 
construct projection TPv for every attacker v∈V; 
initial T′:=T; 
whiledo 
call Alg.IVPA,Alg.FVPA and Alg.MVPA; 
for all v in V do 
calculate the R(PG,UL)s of all the points inAvaccording to MVPvby  definition4.3,and select the highes t R(PG,UL).//根据定义4.3及集合MVPv,计算所有位置数据的R(PG,UL); 
for alltv∈MVPv
find all trajectories T1which include the point with highest 
R(PG,UL);//在集合MVPv?#19994;?#25152;有包含R(PG,UL)最高位置数据的轨迹记?#36857;?nbsp;
for all t∈TPv
find all trajectoriesT2which contain the trajectories inT1.//在投影集TPv?#19994;?#25152;有包含T1中的轨迹投影,并保存到集合T2中; 
for allt∈T′do 
find all trajectories T3with the project ions the same with the trajectories in T2,and delete the point wi th highes t R(PG,UL)in all trajectories inT3.//根据集合T2,在轨迹集T′中?#19994;?#23545;应的轨迹记?#36857;?#24182;保存到集合T3中,抑制集合T3?#20852;?#26377;轨迹记录中的对应R(PG,UL)值最高的位置数据; 
OUtput T′;//输出安全的可发布数据集; 
需要说明的是,若所述集合FVP为空集,则表?#38236;?#21069;原始轨迹序列集合为安全状态,可进行发布。 
实验评估及结果 
为验证所提方案的有效性,我们进行了一系列的实验:在相同轨迹数据集的情况下,通过设置不同的攻击者数量和用户的隐私容忍度,采用“Privacy preservation in the publication of trajectories”(下称“对比方案”)的匿名方法和本发明所提的匿名方案分别进行实验,并根据实验结果,进行对比分析。 
实验环境和实验数据 
实验环境为2.83GHz的Intel双核CPU,2GB内存,操作系统平台为windows XP。在VC编程环境下,通过C++编程实现匿名算法;通过Brinkoff生成器在Oldenburg地图上模拟产生移动用户的坐标信息,经过简单地处理得到用户的轨迹数据集T。在这里,我们将Oldenburg地图均分成100个区域,通过随机算法产生每一个区域的攻击者,每个区域的?#34892;?#20301;置作为用户穿越该区域的足迹信息。用户的平均轨迹长度为6,收集到的轨迹集T的总数为15000。 
在相同数据集T的情况下,分别采用本方案及对比方案中的匿名算法分别对数据集T进行处理,并根据匿名后的数据效用对匿名结果进行对比分析。 
数据效用通过数据损失率UL表示,UL值越大代表数据效用越差,反之,数据效用越好。 
通过图1,我们发现本文所提的方案(局部抑制)明显优于对比方案;在用户隐私容忍度设置同为Pbr=0.5?#20445;?#26412;文所提方案明显提升了数据效用,且随着轨迹集T的增大,数据效用趋向于更好。 
现实中用户的隐私需求可能是变化的,通过改变Pbr可实现用户的隐私需求,且用户的数量?#37096;?#33021;是变化的,因此,我们测试了这两种方案在Pbr、|T|同?#22791;?#21464;时的匿名结果如图2所示。通过对比我们发现: 
1、仅改变Pbr?#20445;?#26412;文所提方案的UL下?#21040;?#24555;,这?#19988;?#20026;本文所提方案在每?#25991;?#21517;处理过程中,将“Privacy preservation in the publication of trajectories”中的对整条轨迹记录的抑制改为对轨迹中的某一位置数据的抑制,有效地提升了数据效用。 
2、仅改变|T|?#20445;?#26412;文所提方案的UL变化较不明显,比较稳定,这?#19988;?#20026; 随着|T|的增多,导致有问题的投影集相对也增多,但|T|变化较快,此?#20445;?#23545;比方案的方法对UL的影响大于对投影集进行局部抑?#39057;?#26041;法,因此,本文所提方案稳定性较好。 
由图3得知,随着攻击者数量|V|的增加,本文所提方案的数据效用UL优于对比方案的实验结果。对比方案的实验结果变化幅度较大,而本文所提方案的结果变化则较?#20132;海?#30001;此可见,所提方案的稳定性更好。 
综上所述当同?#22791;?#21464;Pbr、|T|?#20445;?#26412;文所提方案的实验结果均优于“Privacy preservation in the publication of trajectories”的方案,?#20918;?#26041;案明显优于对比方案,且在同等隐私需求的情况下,将匿名后的数据效用提升?#31169;?0%。 
对于本领域的技术人员来说,可根据以上描述的技术方案以及构?#36857;?#20570;出其它各种相应的改变以及变形,而所有的这些改变以及变形?#21152;?#35813;属于本发明权利要求的保护范围之内。 

关于本文
本文标题:基于频率的轨迹抑制数据发布隐私保护的系统及其方法.pdf
链接地址:http://www.pqiex.tw/p-6115744.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
平码五不中公式规律 排球英语怎么写 股票涨跌情况 两组平码三中三免费开 二分彩计划软件 怎么看五分彩走势图 半全场胜平负 娱网棋牌步步为赢官网 四川成都福彩中心地址 中国体彩篮彩 云南11选5开奖号码号码