2016, Vol. 27
大数据时代,随着定位技术的发展,基于位置的服务越来越普及,用户的时空数据通过各种各样的服务发布出来.在用户通过签到等移动社交网络服务主动发布自己的时空行为的同时,大量记录人们行为的时空数据在人们使用手机进行通话、接发短信息时被移动通信商隐式收集[1].由于手机与移动通信商间的时空数据由手机的信号基站自动收集,这些隐式收集的数据具有数据量大、蕴含人类行为的特征,并且在疾病传播[2, 3]、贫困消除[4]、城市规划[5]等重大科学社会问题以及路线推荐[6]、乘车出行[7]等重要生活应用中发挥了关键作用.然而,这些隐式收集到的时空数据通过与用户主动发布的时空数据相互参照,会暴露用户有关个人身份、行动目的、健康状况、兴趣爱好等多方面的敏感隐私信息[8, 9].近年来,随着个人隐私观念的增强以及数据发布使用中法律法规的健全,这些隐式收集到的时空数据在供科学研究与数据挖掘前需要首先消除其中可能暴露用户隐私的记录.
为了确保这些个人敏感信息不被泄露,大量针对时空数据隐私保护的工作致力于匿名化可能暴露个人敏感信息的时空数据.例如,位置与轨迹数据上的k匿名等方法将用户位于特定时间范围和空间区域的位置记录泛化为相同的空间区域,从而让攻击者不能识别出某个时间范围与空间区域中的特定用户[2].但是,这些方法没有考虑到攻击者可以参照用户主动发布的时空数据从隐式收集到的时空数据中找到暴露用户隐私的记录,因此,经过这些方法保护的时空数据集依然会泄露用户隐私的数据.
例如,假设攻击者看到Alice在社交网络上主动广播了自己5月1日去海南、10月1日去哈尔滨的两次旅行,如果手机运营商收集到的时空数据集中在这两天分别去过海南和哈尔滨的记录都具有相同的用户ID,那么攻击者就可以推断这条记录中的用户ID在现实中对应用户Alice,从而根据数据库中同样ID的时空记录发现Alice去过的其他地方,并进而推断出她的兴趣爱好、行为习惯等隐私信息.
最新的研究[10]表明,现有的位置或轨迹隐私保护方法即使将待发布位置泛化为15平方公里,时间戳泛化为一个小时,95%以上的用户也可以被4个泛化后的时空记录唯一地确定.如果这些用户还通过签到服务主动发布了自己的若干行为,他们就很容易被攻击者识别出来.
在大数据时代,由于攻击者可以通过越来越多的位置社交网站同时收集用户主动发布的时空数据,隐式收集到的时空数据集更容易暴露用户隐私,这对保护这些时空记录在效果、效率和效用这3个方面提出了严重挑战:(1) 对时空数据集的保护效果如何不受攻击者收集用户主动发布的时空数据的能力的增强而减弱;(2) 由于数据集中可能暴露用户隐私的记录个数随着时空数据集的增大呈指数级增长,如何高效发现待保护的记录;(3) 为了发布时空数据而对时空点集进行保护时,如何保证较高的数据效用.
为了应对上述挑战,本文首先在隐式收集到的数据集上定义与用户主动发布数据无关的隐式隐私,以保证无论攻击者收集到多少用户主动发布的数据,经过隐私保护后的隐式收集到的时空数据集都不会泄露额外的信息.随后,本文提出发现和消除两个步骤来保护隐式收集到的时空数据.为了高效寻找可能暴露用户隐私的记录,本文提出基于前缀过滤的嵌套循环算法,并针对其可扩展性差的缺陷提出高效的反先验算法.为了避免这些记录暴露用户的隐私,我们设计了基于频繁移动对象的假数据添加算法,并针对其数据扭曲程度高的缺陷提出了基于图的假数据添加算法,以确保经过保护后的数据集具有高数据效用.
(1) 首次提出并定义时空数据中的隐式隐私,并提出保护该隐私的框架.我们首次定义了隐式收集到的时空数据中的(ε,k)隐私问题,并提出了发现-消除框架和相应算法确保经过保护的数据集不因为攻击者收集到更多用户主动发布的时空数据而泄露额外信息.
(2) 高效的发现算法.我们针对框架中的发现步骤提出了基于前缀过滤的嵌套循环的算法,并针对其扩展性差的缺陷设计了基于反先验算法的优化算法,高效地寻找暴露隐式隐私的时空点集合.
(3) 高效的保护算法.我们针对框架中的消除步骤提出了基于频繁移动对象的假数据添加算法,并针对其数据效用差的缺陷设计了基于图的假数据添加方法,大幅提高了数据效用.
(4) 真实数据集上的充分实验.我们使用两个真实数据集验证了我们方法的效果和效率.
本文第1节主要介绍时空数据发布中隐私保护的相关技术.第2节介绍隐式隐私问题及其发现-消除保护框架.第3节介绍相应的发现,消除算法.第4节是实验效果展示.
1 相关工作匿名方法[11, 12]被广泛应用于保护时空数据发布中的敏感信息,并取得了巨大成功.文献[13]对其进行了详细的综述.匿名方法可以分为位置k匿名和轨迹k匿名.
位置k匿名将每个要发布的时空数据从位置和时间两个维度进行泛化使得每个经过泛化后的时空区域包含至少k个移动对象[14].它的一些变种使用空间索引组织各个移动对象来提高泛化和查询的性能[15],另一些变种通过考虑每个时空数据在不同泛化区域之间进行移动的最大速度限制让泛化更成功[16].但是,位置k匿名不能解决大数据时代隐式位置信息收集与主动位置发布带来的身份泄露.例如,图 1(a)分别包括3个用户在4个时刻的位置记录,每个大圆圈表示同一时刻的位置数据经过k匿名方法的泛化,攻击者在没有任何背景知识的情况下,在这一时刻不能分辨其中的2个用户.但是如果u1将自己曾出现在第1个和最后一个时空点的信息通过签到服务公开在社交网络中,则攻击者很容易将u1与三角形表示的用户关联起来.
|
Fig. 1 Examples for privacy preserving methods 图 1 隐私保护方法举例 |
轨迹k匿名[17, 18]试图针对整条轨迹进行匿名保护,使得每条轨迹满足k匿名.然而由于移动对象轨迹的多样性,对所有轨迹完全匿名是不可能的[17, 19, 20],因此,现有方法只针对不同时间段将轨迹分片,对于分片后的轨迹进行k匿名处理.如图 1(b)所示,全部轨迹被分成两片,由于每片都包括两个用户的轨迹,这两个分片满足轨迹2匿名.然而,攻击者依然可以将三角形对应的用户和其被隐式收集到的时空数据中的标识关联起来:攻击者可以发现三角形用户同时出现在左右两个分片中,而在位置社交网络的公开数据中,也只有一个用户同时出现在左右两个分片的范围内进行了签到服务.因此,无论是位置k匿名还是轨迹k匿名,现有的方法均不能抵抗时空数据中的隐式隐私泄露.事实上,我们只要在此基础上增加两个时空假数据,即可消除与公开数据唯一关联的问题,如图 1(c)所示.
此外,文献[21]针对有关联的两个数据集(如同一家商店的消费者位置数据和购物数据)间的相互参照引起的隐私泄漏问题,提出了高效的解决方案.但该方法对攻击者的背景知识做了限定,不能适用于公开数据多来源化的大数据时代.同时,近年来差分隐私因其可针对任意背景知识进行保护而吸引了研究学者的注意[22, 23],但差分隐私的方法由于只能基于数据的统计值发布进行保护,并不适用于我们发布整个时空数据集进行分析的需求.另外一些基于云计算或众包的研究,通过将数据发布给不相互通信的攻击者保护准确数据发布中的隐私[24].但这些方法往往 采用整数规划在发布数据和隐私保护中寻求平衡,实际上暴露了位置隐私.
2 问题定义和隐私保护框架本节中,我们在被隐式收集的时空数据集上定义与攻击者的收集信息能力无关的(ε,k)隐式隐私,并证明在隐私保护过程中,最小化数据改变量是NP-hard问题.最后介绍发现-消除隐私保护框架.
2.1 问题定义当某个用户u在时间t在位置l使用手机进行收发短信息、接打电话时,形如三元组<u,l,t>的时空记录被手机移动运营商隐式收集,这些记录组成时空数据集D.其中,每个表示用户出现的具体位置和时刻的二元组<l,t>称为时空点.通过对在相同时空点出现的用户进行聚集,给定位置loc和时间time,时空点<loc,time>能够关联一个在这个时空点共现的用户集合Sploc,time={u|<u,l,t>∈,l=loc,t=time}.
由于针对同一行为,用户的时空记录根据收集方式的不同可能存在微小差异,攻击者可以使用两个参数ε1和ε2来分别表示时空点在时间和位置的差异.当隐式收集的数据集中有若干个(≥1)时空点在时间上相差不超过ε1、位置上相距不超过ε2时,攻击者可以将这些时空点视为同一时空点和公开数据集中的时空点相参照.如表1中的时空点
定义1(有效时空点). 给定隐式收集的时空数据集D,以及时空阈值ε1和ε2,对于任意时空点<li,ti>∈D,若
根据定义1,表 1共有6个有效时空点,分别是
|
Table 1 Example for valid spatio-temporal point (T2>T1+2ε1) 表 1 有效时空点示例(T2>T1+2ε1) |
如果一个用户u通过签到服务等方式主动公开了自己位于若干时空点集合{<l1,t1>,<l2,t2>,…,<ln,tn>}(n≥1)的事实,而在隐式收集到的时空数据集D中,这些时空点对应的用户集合Sp1,Sp2,…,Spn满足
基于将用户发布的时空点与隐式收集到的时空数据集合中的时空点关联的过程,我们给出时空数据隐式收集中的(ε,k)隐私问题.
定义2((ε,k)隐式隐私). 给定隐式收集的时空数据集合D、时间阈值与距离阈值
根据定义2,当攻击者收集到了Alice在两个时空点<A,T1>,<C,T2>的公开数据时,
首先,我们允许用户根据数据集的不同特点设置(ε,k)隐私问题中的参数.具体来说,当公开数据集是包含时空点的时效性较差的微博数据时,时间阈值、距离阈值可以比时效性较强的签到数据大;当待保护用户(群体)经常公开发布自己所在的时空点时,攻击者的攻击能力k可以设置得大一些.
值得注意的是,为了保护(ε,k)隐私,最小化需要更改的时空数据是一个NP-hard问题.
定理1. 最小化数据改变量来保护(ε,k)隐私问题是NP-hard问题.
证明:由于最小化数据改变量来保护k匿名问题是NP-hard问题,下面我们只需证明k匿名问题可以在多项式时间内规约到(ε,k)隐私保护问题.这对应着在(ε,k)隐私保护问题中,我们将ε设定为{0,0}.这样,任何k匿名问题的解都是ε设定为{0,0}后(ε,k)隐私保护问题的解,任何ε设定为{0,0}后(ε,k)隐私保护问题的解也是k匿名问题的解.这个映射可以在多项式时间内完成.由此可以得出,保护(ε,k)隐私问题是NP-hard问题.
基于定理1,为了高效保护(ε,k)隐私问题,我们采用发现-消除框架.如图 2所示,隐私保护框架分为3个模块:数据预处理模块、发现违反隐私模块、消除隐私泄露模块.
|
Fig. 2 Implicit privacy preservation framework 图 2 隐式隐私保护框架 |
根据隐式隐私的定义,我们首先在数据预处理模块中根据时间阈值和距离阈值ε构建全部时空点.由于我们事先不能确定用户公开发布了哪些时空点,而大数据时代攻击者通常可以从多个社交网络来源收集到同一用户发布的时空数据.为了确保用户的隐私不被泄露,在发现违反隐私模块中,我们寻找任何由i(1≤i≤k)个时空点组成的时空点组合,并检查攻击者是否可以匹配隐式收集到的时空数据中的某个用户.接下来,消除隐私泄露模块针对发现的时空点集合进行保护,消除隐式收集到的时空数据集对(ε,k)隐私的泄露.这样,无论用户主动发布的时空点是什么,都可以找到并消除导致(ε,k)隐私泄漏的时空数据.
3 算法与分析本节分别介绍发现以及消除(ε,k)隐私泄露的算法.
3.1 发现(ε,k)隐私泄露我们首先介绍发现(ε,k)隐私泄露的基于前缀过滤的嵌套循环算法,然后指出它在效率上的不足,并给出更高效的反先验算法.
3.1.1 基于前缀过滤的嵌套循环算法根据隐私保护参数ε和k,发现泄露(ε,k)隐私的时空点数据的基本想法是枚举全部k个时空点组成的集合,并检查每个组合是否与唯一用户关联.为此,基于前缀过滤的嵌套循环算法(prefix filter based nest loop,简称PF-NL算法),通过枚举k位不重复的数字实现对时空点的k重嵌套循环,并使用前缀过滤的方法在枚举中进行剪枝.首先,我们介绍(ε,k)隐私的重要性质.
性质1. 记Uk为暴露(ε,k)隐私的全部时空点集合,并记uk为大小为k的可以唯一关联移动对象的全部时空点集合,则Uk=u1∪…∪uk.
我们略去了性质1的平凡的证明,性质1说明,我们可以从大小为1的时空点集合开始,直到枚举全部大小不超过k的时空点集合.为此,我们把n个时空点从1开始编号,每个大小为k的时空点集合可以看成一个具有k位,进制为n的数字,且每个相同的时空点集合将k个代表时空点的数字按顺序排列后具有唯一的表达方式[25].
这样,大小为k(k>1)的时空点集合具有长度为{1,…,k-1}的前缀.例如,我们可以把表 1中的6个有效时空点
集合{1,2,3},它具有前缀{1,2}.我们知道,|Sp1∩Sp2|=0,因此,具有此前缀的时空点集合一定也不会暴露(0,3)隐私.在基于前缀过滤的方法中,我们避免枚举包含这种前缀的时空点集合.
结合上面的基本想法和基于前缀过滤的优化方法,我们提出了发现违反隐式隐私的基本算法PF-NL.
算法1. PF-NL算法.
输入:大小为n的时空点集合,隐私需求(ε,k).
输出:全部违反(ε,k)隐私的时空点集合R.
1. num=[0,…,k-1],bound=[n-k+1,…,n],R=∅
2. while true do
3. if violate(num)==1 then
4. R.add(num)
5. else
6. prefix=minpviolate(num[1…p])=0
7. endif
8.
9. if p<0
10. break
11. endif
12. num[p]=num[p]+1
13. num[p+1,..,k]=[num[p]+1,..,num[p]+kp+1]
14. endwhile
15. return R
在算法PF-NL中,我们依次枚举大小为k的时空点集合num,其每一位对应的最大值用bound数组表示(第1行).当某个时空点集合中包含的各个移动对象的集合相交后大小为1时,我们将它加入全部违反隐私需求的时空点集合R中(第3行、第4行).这样,产生新时空点集合的过程就是将数组中的某个元素增加的过程(第8行~第13行).值得注意的是,我们在检查某个时空点是否暴露(ε,k)隐私时计算它可能存在的前缀(第6行),并在产生新的时空点集合时过滤掉此前缀(第8行).当不能产生新的时空点时,算法PF-NL结束(第10行).
3.1.2 反先验算法算法PF-NL利用前缀过滤试图在枚举中过滤掉相交为空的时空点集合,加速了违反(ε,k)隐私的时空点集合的寻找过程.但由于可以用来过滤的前缀很多,我们不能一一记录,它还是做了很多不必要的工作.下面我们介绍反先验算法,利用广度优先搜索的思想,在搜索更大的时空点集合时避免包含不违反(ε,k)隐私的较小时空点集合.
算法2展示了反先验算法(reverse aprior,简称RA算法).其中,我们用ui,zi和ci分别表示大小为i的违反、不可能违反和在更大的时空点集合中有可能违反(ε,k)隐私的时空点集合.
在RA算法中,我们首先检查所有时空点,并把违反(ε,k)隐私的时空点加入到u1中;由于时空点中一定包含移动对象,它们也全部被加入c1(第1行).
接下来,我们考虑由更多时空点组成的集合.较大的时空点集合由较小的可能违反(ε,k)隐私的时空点集合组成(第5行).由于大小为i+1的集合有多种组合方式,不同的组合可能导致不同大小的待检验时空点集合,为了降低时间开销,我们选择笛卡尔积最小的两个时空点集合生成它(第4行).同时,用来进行检查是否违反(ε,k)隐私的时空点集合不应包含更小的不可能违反(ε,k)隐私的时空点集合(第6行).最后,violate将时空点集合中各个时空点包含的移动对象集合求交集,并返回其大小.那些交集大小为1的时空点集合违反了(ε,k)隐私,被加入ui+1 (第6行),而交集大小为0的时空点集合将不可能违反(ε,k)隐私,因此加入zi+1,并从ci+1中去除(第8行、第9行).
例1:针对表 1,我们首先检查其中包含的6个有效时空点独自组成的时空点集合是否有违反(ε,k)隐私的情况.首先,因为Sp1和Sp2各包含一个用户,u1={1,2},c1={3,4,5,6}.接下来,我们根据c1与c1的笛卡尔积生成大小为2的待检验的时空点集合,即{{3,4},{3,5},{3,6},{4,5},{4,6}…,{5,6}}.经检验,违反(ε,k)隐私的4对时空点集合是u2={{3,4},{3,5},{4,6},{5,6}}.而时空点集合{3,6},{4,5}中不包含相同移动对象,因此,包含它们的时空点集合不可能违反(ε,k)隐私,因此把他们从c2中去掉,最终得到c2=∅,z2={{3,6},{4,5}}.因此,算法RA至此结束.
算法2. RA算法
输入:隐私需求(ε,k).
输出:全部违反隐私需求的时空点集合R.
1. Scan database and form u1 and c1
2. i=1,R=∅
3. while (ci∅ and i≤k)
4.
5. ci+1=cwxci-w+1
6.
7. ui+1={ε|ε∈ci+1,violate(ε)=1}
8. zi+1={ε|ε∈ci+1,violate(ε)=0}
9. ci+1=ci+1-zi+1
10. endwhile
11. R=u1∪…∪uk
值得指出的是,一般来说,时空点集合越大,我们需要检验的时空点集合就越多.但在例1中,当时空点集合的大小变大时,需要检查的时空点集合并没有增多,这在直观上说明了RA算法的有效性.
3.2 消除违反(ε,k)隐私的时空数据在本节中,我们介绍添加假数据的方法来消除违反(ε,k)隐私的时空数据.特别地,我们分别介绍了不需要寻找违反(ε,k)隐私的时空点集合的基于频繁移动对象的假数据添加方法和基于图的可以实现较高数据效用的隐私泄露消除方法.
3.2.1 基于频繁移动对象的假数据添加方法 不考虑已找到的违反(ε,k)隐私的时空点集合,一个简单的隐私保护方法是为每个用户在其存在的各个时空点中添加具有相同用户id的假数据,比如对表 1中造成(0,2)隐私泄露的进行保护.这样添加假数据后得到
算法3(frequent moving object,简称FMO算法)展示了这个基于频繁移动用户添加假数据的过程.给定唯一性隐私参数(ε,k),我们首先找到最频繁出现的两个移动对象,此过程存在大量快速算法[26];其次,我们在每个时空点集合中加入这些移动对象.
算法3. FMO算法.
输入:隐私需求(ε,k),时空点集合D.
输出:满足(ε,k)隐私约束的发布数据P.
1. P=∅
2. F={{u1,u2}|óu∈{u3,…,un},count(u)>min{count(u1),count(u2)}}
3. for each <u,l,t>∈D
4. P.add(<u,l,t>)
5. P.add(<u1,l,t>)
6. P.add(<u2,l,t>)
7. endfor
3.2.2 基于图的假数据添加方法由于没有考虑到第3.1节中找到的暴露唯一性隐私的时空点集合,算法FMO对时空点不加区分地添加假数据,导致了很多不需要添加的数据.
例2:对于4个时空点:{u1,u6},{u2,u3},{u3,u4},{u7,u8},根据算法FMO添加假数据得到{u1,u6,u2,u3},{u2,u3},{u2,u3,u4},{u7,u8,u2,u3},添加了62.5%的数据.但是,第1个时空点显然不需要添加任何假数据.
基于第3.1节中找到的违反(ε,k)隐私的时空点集合,算法4展示了基于图的假数据添加(graph based dummy filling,简称G-DF算法)过程.在算法G-DF中,我们把位置数据看成一个图,其中每个时空点代表图中的一个节点,而如果两个时空点存在于某个暴露唯一性隐私的时空点集合中,我们就在图中为它们添一条边(第2行).我们只针对图中的每个连通分量运行算法3,即寻找每个连通分量中的最频繁的两个移动对象,把它们加入到此连通分量中的每个节点中(第3行~第5行).
例3:注意到例2中违反(ε,k)隐私的只有大小为2的时空点集合{{u2,u3},{u3,u4}},图 3是例2转化成图后的情况.这样,根据算法G-DF,例2中的数据被转化成{u1,u6},{u2,u3},{u2,u3,u4},{u7,u8},相比FMO算法增加了62.5%的数据,G-DF算法只增加了12.5%的数据.
|
Fig. 3 Transform the spatio-temportal point into graph 图 3 将时空点转化成图 |
算法4. G-DF算法.
输入:暴露唯一性隐私的时空点集合R.
输出:满足(ε,k)隐私约束的发布数据P.
1. P=∅
2. Transform D and R into Graph g
3. for each connectivity sg in g
4. Perform Algorithm 3
5. endfor
4 实 验我们使用了两个真实数据集对发现-消除框架中的两种发现违反(ε,k)隐式隐私的时空数据的算法和两种消除这种违反的算法进行了性能和效果的比较.特别地,我们将通过实验回答下述问题:
(1) 隐私保护参数(ε,k)如何影响时空数据中的(ε,k)隐私;
(2) 隐私保护参数(ε,k)对违反隐私发现算法性能的影响;
(3) 隐私保护参数(ε,k)对隐私保护算法的效果和性能的影响.
4.1 实验环境与数据集描述我们使用Java 1.7实现本文算法1~算法4,实验环境是一台Linux服务器,英特尔至强E5645 2.4Ghz处理器,128G内存,1T SATA硬盘.除了本文的PF-NL方法和RA方法用于发现违反(ε,k)隐私的时空点集合以及本文的FMO和G-DF方法用于消除违反(ε,k)隐私的时空点集合以外,其他对比方法包括:
· YCWA[18]:该方法是采用轨迹匿名技术保护时空数据隐私的最新方法,它将轨迹划分成停留点,并通过匿名化这些停留点保护隐私信息.该方法主要侧重轨迹隐私保护的性能.
· SEQ-ANON[19]:该方法侧重轨迹匿名技术的数据可用性,在对轨迹进行匿名化的同时,尽量减少被改变的时空点与原始时空点之间的距离.
我们将两个公开数据集GeoSocial[27]和GeoLife[28]当作用户被隐式收集的时空数据集进行实验.它们的数据大小和用户个数见表 2.
|
|
Table 2 Dataset 表 2 数据集 |
4.2 隐私保护效果对比
图 4显示了在GeoSocial和GeoLife数据集上,在较严格的(ε,k)隐私条件下(ε1=10min,ε2=1km,k=10)各个方法进行时空数据隐私保护的效果.我们的方法RA×G-DF在发现阶段使用性能最好的RA方法, 在消除阶段使用性能最好的G-DF方法.我们可以看到,经过YCWA和SQL-ANON处理后的轨迹依然有大量违反(ε,k)隐私的时空点集合.这是因为这些方法没有考虑到隐式收集到的时空数据与用户主动发布的时空数据相互参照造成的隐私泄露.
|
Fig. 4 Comparision on effect of privacy preservation 图 4 隐私保护效果对比 |
4.3 (ε,k)隐私
如图 5所示,当我们把ε2固定而调整ε1时,对3个数据集来说,随着k的增加,3个数据集中违反(ε,k)隐私的时空点集合所占比例逐步下降.这种现象为第3.1.2节中RA算法的高效提供了依据.
|
Fig. 5 Effect of ε and k on three datasets 图 5 3个数据集上ε,k的效果 |
另一方面,当ε2增大时,图 4(b)、图 4(d)显示,两个数据集上暴露(ε,k)隐私的时空点集合的比例逐渐增加.这是因为更多的有效时空点容易和某个用户的公开位置匹配起来,进而违反(ε,k)隐私.
4.4 发现违反(ε,k)隐私算法性能我们用真实数据集GeoLife和GeoSocial比较和验证我们提出的两个(ε,k)隐式隐私发现算法的运行效率.
图 6显示了两种算法在GeoSocial数据集,在不同的(ε,k)下寻找出全部违反(ε,k)隐私的运行时间.从图 6(a)和图 6(b)的比较可以看出,在相同的唯一性隐私参数(ε,k)下,RA算法在相同隐私参数下比PF-NL算法快1~2个数量级.特别地,PF-NL算法甚至不能计算出k>3的情形.
|
Fig. 6 Performance comparison of algorithm PF-NL and RA 图 6 PF-NL和RA算法性能对比 |
针对RA算法,我们调整GeoLife数据集的大小和移动对象个数对其性能进行了测试.图 6(c)显示,GeoLife数据集的大小对算法的影响最大,因为它改变了数据集中时空点个数;而移动对象个数对算法的影响不大.
4.5 (ε,k)隐私保护算法效果我们不断调整隐私参数ε和k,查看两个隐私保护算法对数据集进行隐私保护后发布的数据效用.
如图 7(a)、图 7(b)所示,FMO算法对这两个数据集进行保护后添加的假数据比例都超过了80%;而G-DF算法可以只添加10~20%的假数据.
|
Fig. 7 Performance comparison of algorithm of FMO and G-DF 图 7 FMO和G-DF算法性能对比 |
图 7(c)说明,隐私参数的变化不影响FMO算法的数据效用.这是因为FMO算法只为每个时空点添加2个假数据.图 7(d)说明,对于G-DF算法,当ε1减小时,需要添加的假数据量变大.这是因为如图 5(a)、图 5(c)所示,ε1减小时违反(ε,k)隐私的时空点集合变多.我们还可以看出,G-DF算法的数据效用远好于FMO算法.这是因为G-DF算法不添加不必要的假数据.
4.6 (ε,k)隐私保护算法性能我们使用最大的真实数据集GeoLife比较两个(ε,k)隐私保护算法的运行效率.
图 8(a)展示了FMO对(ε,k)隐私的保护性能.可以看出,给定数据集后,隐私参数对运行时间没有影响.图 8(b)中隐私保护算法的运行时间的趋势和图 6中违反(ε,k)隐私的时空点集合比例的变化趋势相似.这是因为算法G-DF需要对所有找出的违反(ε,k)隐私的时空点集合进行处理,因此其处理时间和在确定(ε,k)隐私参数(ε,k)下违反隐私的时空点集合个数正相关.
|
Fig. 8 Performance comparison of algorithm of FMO and G-DF under GeoLife dataset (ε2=1km) 图 8 Geolife数据集上FMO和G-DF算法性能对比(ε2=1km) |
5 结束语
本文首次针对用户主动发布的数据集与被隐式收集到的时空数据集相互参照的情况提出了时空数据中(ε,k)隐式隐私的定义,并提出了发现-消除隐私保护框架.特别地,本文提出了两种高效算法用于发现违反(ε,k)隐私的时空点集合.此外,本文提出了添加假数据的匿名保护方法.为了提高数据效用,本文进一步提出了基于图的假数据添加方法.真实数据集上的充分实验证明,本文算法是高效的.在未来的工作中,我们将进一步改进本文方法的性能.
| [1] | Nathan E, Alex P. Reality mining: Sensing complex social systems. Journal of Personal and Ubiquitous Computing, 2006, 10 (4) :255–268. [doi:10.1007/s00779-005-0046-3] |
| [2] | Le MA, Tatem AJ, Cohen JM, Hay SI, Randell H, Patil AP, Smith DL. Travel risk, malaria importation and malaria transmission in Zanzibar. Scientific Reports, 2011, 1 (7364) :271–275. [doi:10.1038/srep00093] |
| [3] | Wesolowski A, Eagle N, Tatem AJ, Smith DL, Noor AM, Snow RW, Buckee CO. Quantifying the impact of human mobility on malaria. Science, 2012, 338 (6104) :267–270. [doi:10.1126/science.1223467] |
| [4] | Hill S, Banser A, Berhan G, Eagle N. Reality mining Africa. In: Proc. of the AAAI Spring Symp. on Artificial Intelligence for Development. 2010. http://www.seas.upenn.edu/~ngns/docs/References/Hill%202010%20realityminingafrica.pdf |
| [5] | Yuan J, Zheng Y, Xie X. Discovering regions of different functions in a city using human mobility and POIs. In: Yang Q, Agarwal D, Pei J, eds. Proc. of the KDD. New York: ACM Press, 2012 . |
| [6] | Zheng K, Shang S, Yuan J, Yang Y. Towards efficient search for activity trajectories. In: Jensen CS, Jermaine CM, Zhou XF, eds. Proc. of the ICDE. Washington: IEEE Computer Society, 2013 : 230 -241. |
| [7] | Yuan NJ, Zheng Y, Zhang L, Xie X. T-Finder: A recommender system for finding passengers and vacant taxis. IEEE Trans. on Knowledge & Data Engineering, 2013, 25 (10) :2390–2403. [doi:10.1109/TKDE.2012.153] |
| [8] | Wicker SB. The loss of location privacy in the cellular age. Communications of the ACM, 2012, 55 (8) :60–68. [doi:10.1145/2240236.2240255] |
| [9] | Wang L, Meng XF, Information SO. Location privacy preservation in big data era: A survey. Ruan Jian Xue Bao/Journal of Software, 2014, 25 (4) :693–712(in Chinese with English abstract). [doi:10.13328/j.cnki.jos.004551] |
| [10] | Montjoye YAD, Hidalgo CA, Verleysen M, Blondel VD. Unique in the Crowd: The privacy bounds of human mobility. Open Access Publications from Université Catholique De Louvain, 2013, 3 (6) :776–776. |
| [11] | Bu GG, Liu L. A customizable k-anonymity model for protecting location privacy. In: Proc. of the Icdcs. 2004. 620-629. |
| [12] | Cicek AE, Nergiz ME, Saygin Y. Ensuring location diversity in privacy-preserving spatio-temporal data publishing. VLDB Endowment, 2014, 23 (4) :609–625. [doi:10.1007/s00778-013-0342-x] |
| [13] | Fung BCM, Wang K, Chen R, Yu PS. Privacy-Preserving data publishing: A survey of recent developments. ACM Computing Surveys, 2010, 42 (4) :2623–2627. [doi:10.1145/1749603.1749605] |
| [14] | Sweeney L. K-Anonymity: A model for protecting privacy. Int'l Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2008, 10 (5) :557–570. [doi:10.1142/S0218488502001648] |
| [15] | Mokbel MF, Chow CY, Aref WG. The new casper: Query processing for location services without compromising privacy. In: Dayal U, Whang KY, et al., eds. Proc. of the VLDB. New York: ACM Press, 2009 : 763 -774. |
| [16] | Pan X, Xu J, Meng X. Protecting location privacy against location-dependent attack in mobile services. IEEE Trans. on Knowledge & Data Engineering, 2011, 24 (8) :1506–1519. [doi:10.1109/TKDE.2011.105] |
| [17] | Abul O, Bonchi F, Nanni M. Never walk alone: Uncertainty for anonymity in moving objects databases. In: Alonso G, Blakeley J, Chen ALP, eds. Proc. of the ICDE. Washington: IEEE Computer Society, 2008 : 376 -385. |
| [18] | Huo Z, Meng X, Hu H, Huang Y. You can walk alone: Trajectory privacy-preserving through significant stays protection. In: Lee SG, Peng ZY, et al., eds. Proc. of the DASFAA. Berlin: Springer-Verlag, 2012 : 351 -366. |
| [19] | Poulis G, Skiadopoulos S, Loukides G, Gkoulalas-Divanis A. Apriori-Based algorithms for km-anonymizing trajectory data. Trans. on Data Privacy, 2014, 7 (2) :165–194. |
| [20] | Domingo-Ferrer J, Trujillo-Rasua R. Microaggregation- and permutation-based anonymization of movement data. Information Sciences, 2012, 208 (21) :55–80. [doi:10.1016/j.ins.2012.04.015] |
| [21] | Hu H, Xu J, On ST, Ng JKY. Privacy-Aware location data publishing. ACM Trans. Trans. on Database Systems, 2010, 35 (3) :53–56. [doi:10.1145/1806907.1806910] |
| [22] | Dwork C. Differential privacy. In: Bugliesi M, Preneel B, et al. Proc. of the ICALP, 2006 :1–12. [doi:10.1007/11787006_1] |
| [23] | Hay M, Rastogi V, Miklau G, Suciu D. Boosting the accuracy of differentially private histograms through consistency. VLDB Endowment, 2009, 3 (1) :66–69. [doi:10.14778/1920841.1920970] |
| [24] | Rekatsinas T, Deshpande A, Machanavajjhala A. SPARSI: Partitioning sensitive data amongst multiple adversaries. VLDB Endowment, 2013, 6 (13) :1594–1605. [doi:10.14778/2536258.2536270] |
| [25] | Knuth D. The art of computer programming. Vol.4, Fascicle 2: Generating all Tuples & Permutations. Addison-Wesley Professional, 2008. |
| [26] | Metwally A, Agrawal D, El Abbadi A. Efficient computation of frequent and top-k elements in data streams. In: Eiter T, Libkin L, eds. Proc. of the ICDT 2005. Berlin: Springer-Verlag, 2005 : 398 -412. |
| [27] | Geo H, Tang J, Liu H. Addressing the cold-start problem in location recommendation using geo-social correlations. Data Mining & Knowledge Discovery, 2015, 29 (2) :299–323. [doi:10.1007/s10618-014-0343-4] |
| [28] | Zheng Y, Xie X, Ma WY. GeoLife: A collaborative social networking service among user, location and trajectory. Bulletin of the Technical Committee on Data Engineering, 2010, 33 (2) :32–39. |
| [9] | 王璐, 孟小峰. 位置大数据隐私保护研究综述. 软件学报, 2014,25 (4) :693–712. http://www.jos.org.cn/1000-9825/4551.htm [doi:10.13328/j.cnki.jos.004551] |