一种轨迹时间模式的差分隐私保护方法及系统
技术领域
本发明属于数据挖掘领域，涉及一种轨迹时间模式的差分隐私保护方法及系统。
背景技术
随着GPS和WIFI的快速发展，产生了大量的时空数据。轨迹是基于时间采样的时空数据，包括采样点位置、采样时间、采样速度等属性，由于时空轨迹数据在时间模式上具有周期性，对其进行聚类、关联分析可以获得大量的个人隐私信息。例如，通过观察用户从周一到周五的早高峰时期的固定位置，可以推断出该地点有很大概率是用户的家庭住址。近年来，由于轨迹时间模式所导致的隐私泄漏事件时有发生，对用户的财产安全造成了极大的威胁，因此，保护用户轨迹时间模式的隐私具有重要意义。
目前，用户轨迹时间模式的隐私保护技术大致分为三类:泛化(将用户的精确时间信息进行模糊化)、抑制(选择性发布用户时间数据)和假数据(将用户的真实时间信息通过一定的变换生成假信息)。其中，以基于泛化的k-匿名保护模型应用最为广泛，其基本思想是：设法切断准标识符与隐私属性之间的一对一关系，使得每条时间记录都无法和其他至少k-1条时间记录进行区分，从而达到保护时间模式的目的。但是该模型存在以下三个问题：
(1)k-匿名保护模型的安全性与攻击者的背景知识相关，只有在知晓攻击者背景知识的情况下，才能保证隐私保护算法的安全性；
(2)k-匿名保护模型的安全性与数据分布的稀疏程度相关，当数据分布过于稀疏时，攻击者很容易通过分布式攻击方式推测出用户的真实信息；
(3)k-匿名保护模型无法提供一种有效且严格的方法来证明其安全性，当k值改变时，无法定量分析其安全性。
为了克服k-匿名的缺陷，近年来，研究者开始利用差分隐私保护方法(对数据添加服从一定规律的干扰噪音)来保护轨迹的时间模式隐私。由于差分隐私能够抵御任意背景知识和任意攻击模型的攻击，并且有坚实的数学理论基础，自2006年由Dwork提出以来，差分隐私在轨迹保护方面的研究成果不断涌现。
尽管将差分隐私应用于轨迹数据发布的研究成果已经很多，但大多是基于轨迹形状模式以及OD(Origin-Destination)流模式的方法，针对轨迹时间模式隐私保护的研究却很少，尤其是结合用户活动区域推断其居住点和工作点方面的研究较少。针对轨迹时间模式的具体攻击方式为：根据个体轨迹遵循家—工作—家的规律，首先利用数据集提取活动区域，然后结合轨迹在不同时间的分布推断用户居住点及工作点，从而发现其出行规律，甚至可以推测出用户的身份。因此，如何针对带有时间戳的轨迹数据，在满足差分隐私的前提下从时间模式方面保护用户隐私仍是亟待解决的问题。
基于上述背景，本发明提出一种轨迹时间模式的差分隐私保护方法及系统，为由于轨迹时间模式的周期性所导致的个体隐私泄露问题的真正解决奠定基础。
发明内容
有鉴于此，本发明的目的在于提供一种轨迹时间模式的差分隐私保护方法及系统，满足差分隐私的保护需求，同时保护用户的时间模式，进而防止攻击者结合时间模式推断用户的工作和居住地点。
为达到上述目的，本发明提供如下技术方案：
一种轨迹时间模式的差分隐私保护方法，该方法包括以下步骤：
步骤S1，轨迹数据预处理及聚类。包括以下子步骤:
步骤S1-1，对待保护的轨迹数据进行清洗和规约，保留用户的经纬度数据和对应的时间戳作为新的轨迹数据集，记时间戳数据集为T＝{t1,…,tn}，Ti是T中的任一子集，则有Ti∈T，且Ti∈[tk,tm],tmin≤tk＜tm≤tmax，其中tk∈T,tm∈T,tmin是T中的最小值，tmax是T中的最大值；
步骤S1-2，将保留的轨迹数据集用DBSCAN算法进行密度聚类，得到聚类簇集C＝{c1,c2,...,cl}和对应的时间戳子集Tc＝{T1,T2,...,Tl}，其中，l是聚类簇的数目。
步骤S2，初始化参数，包括初始化匿名算法的参数k、隐私保护强度参数ε以及可接受的发布误差范围[-α,α]。其中初始化的k值需要判断是否合理，由步骤S1-2得到的时间戳子集Tc＝{T1,T2,...,Tl}计算k′,然后根据k′判断用户初始定义的k值是否合理。包括以下子步骤:
步骤S2-1，初始化隐私保护强度参数ε以及可接受的发布误差范围[-α,α]；
步骤S2-2，初始化匿名算法的参数k值；
步骤S2-3，选择步骤S1-2得到的其中一个时间戳子集Ti∈Tc,计算k′值：
步骤S2-4，判断步骤S2-2用户初始定义k值的合理性，若k∈[1,k′]且k为整数，则k合理，进入步骤S2-5；否则，返回步骤S2-2；
步骤S2-5，重复步骤S2-2、S2-3和S2-4，直到步骤S1中所有簇集对应的时间戳子集Ti都得到对应的计算结果k′，并与初始化的k值进行比较，得到最终合理的k值集合Kc＝{k1,k2,...,kl}。
步骤S3，利用k-匿名算法对时间戳进行粗粒度扰动。假设给定的簇集C对应的每一个时间数据子集Tc中共有n个时间戳，根据k匿名实现方法对所有时间戳子集Tc进行匿名处理，实现对时间戳的粗粒度扰动。包括以下子步骤：
步骤S3-1，选择步骤S1-2所得簇集对应的一个时间戳子集Ti∈Tc；
步骤S3-2，判断k值集Kc中的ki值所在区间，若ki＝1，则不做匿名处理，进入步骤S4；否则，对时间戳子集Ti中的每个数据ti做如下匿名处理：
步骤S3-3，重复步骤S3-1和S3-2，直到所有的时间戳子集Ti都进行了k-匿名处理,此时，得到时间戳子集Tc的粗粒度扰动结果Tc′＝{T1′,T2′,...,Tl′}。
步骤S4，利用差分隐私拉普拉斯噪声对时间戳进行细粒度扰动。根据初始化的隐私保护强度参数ε求出拉普拉斯噪声概率密度函数，生成对应的拉普拉斯噪声，对步骤S3-3得到的粗粒度扰动结果Tc′＝{T1′,T2′,...,Tl′}进行细粒度扰动，得到细粒度的扰动结果。包括以下子步骤：
步骤S4-1，根据初始化的隐私保护强度参数ε和时间戳的敏感度函数Δf计算得到拉普拉斯噪声的概率密度函数fLap(z)：
其中
步骤S4-2，选择粗粒度扰动结果Tc′＝{T1′,T2′,...,Tl′}中的任意一个子集Ti′∈Tc′，根据拉普拉斯噪声的概率密度函数fLap(z)生成对应数目的噪声数据集Zi；
步骤S4-3，将生成的拉普拉斯噪声Zi加入到粗粒度扰动结果任一子集Ti′中，得到细粒度的扰动结果Ti″：
Ti″＝Ti′+Zi
步骤S4-4，重复步骤S4-2和S4-3，直到粗粒度扰动结果Tc′＝{T1′,T2′,...,Tl′}中的所有子集都进行了细粒度扰动，得到对应的细粒度扰动结果Tc″＝{T1″，T2″,...,Tc″}。
步骤S5，利用截断拉普拉斯机制优化扰动结果。根据初始化的隐私保护强度参数ε求出截断拉普拉斯噪声概率密度函数，生成对应的截断拉普拉斯噪声，对步骤S4-3得到的细粒度扰动结果Tc″＝{T1″,T2″,...,Tc″}进行优化，得到优化结果
步骤S5-1，根据初始化的隐私保护强度参数ε和时间戳的敏感度函数Δf计算得到截断拉普拉斯噪声的概率密度函数fTLap(z)：
其中
步骤S5-2，选择细粒度扰动结果Tc″＝{T1″,T2″,...,Tc″}中的任意一个子集Ti″∈Tc″，根据截断拉普拉斯噪声的概率密度函数fTLap(z)生成对应数目的噪声数据集Zi′；
步骤S5-3，将生成的拉普拉斯噪声Z′i加入到粗粒度扰动结果任一子集Ti″中，得到优化结果
步骤S5-4，重复步骤S5-2和S5-3，直到细粒度扰动结果Tc′＝{T1′,T2′,...,Tl′}中的所有子集都进行了优化，得到优化后的扰动数据集
同时，本发明还相应提供了一种轨迹时间模式的差分隐私保护系统，如图3所示，包含：
轨迹数据预处理及聚类模块，用于对轨迹数据集进行预处理和聚类操作，包括以下子模块，
预处理子模块，用于对待保护的轨迹数据进行清洗和规约，保留用户的经纬度数据和对应的时间戳作为新的轨迹数据集；
聚类子模块，用于将保留的轨迹数据集用DBSCAN算法进行密度聚类，得到聚类簇集和对应的时间戳子集；
初始化参数模块，用于初始化参数，包括以下子模块,
初始参数设置子模块，用于初始化匿名算法的参数k、隐私保护强度参数ε以及可接受的发布误差范围[-α,α]；
判断子模块，用于判断设置的参数值k是否合理；
匿名处理模块，用于实现对时间戳进行粗粒度的扰动，包括以下子模块,
判断子模块，用于判断k值集合Kc中的ki值所在区间，若ki＝1，则不做匿名处理，直接进入差分隐私处理模块；否则，对时间戳子集Ti中的每个数据ti做如下匿名处理：
迭代子模块，用于迭代上述子模块中的过程，生成初步扰动结果Tc′＝{T1′,T2′,...,Tl′}。
差分隐私处理模块，用于实现对时间戳进行细粒度的扰动，包括以下子模块，
拉普拉斯噪声生成子模块，用于生成拉普拉斯噪声，根据隐私保护强度参数ε求出拉普拉斯噪声概率密度函数fLap(z)，生成对应数目的噪声数据集Zi；
拉普拉斯噪声添加子模块，将生成的拉普拉斯噪声Zi加入到粗粒度扰动结果任一子集Ti′中，得到细粒度的扰动结果Ti″；
迭代子模块，用于迭代上述子模块中的过程，生成细粒度扰动结果
截断拉普拉斯优化模块，用于对差分隐私处理模块得到的细粒度扰动结果进行优化处理，包括以下子模块，
截断拉普拉斯噪声生成子模块，用于生成截断拉普拉斯噪声，根据隐私保护强度参数ε求出拉普拉斯噪声概率密度函数fTLap(z)，生成对应数目的噪声数据集Zi′；
截断拉普拉斯噪声添加子模块，将生成的截断拉普拉斯噪声Zi′加入到细粒度扰动结果任一子集Ti″中，得到优化结果
迭代子模块，用于迭代上述子模块中的过程，生成细粒度扰动结果Tc″＝{T1″,T2″,...,Tc″}。
本发明为了保护轨迹时间模式的隐私，首先使用k-匿名对时间戳进行粗粒度的匿名化处理，然后使用差分隐私技术对时间戳进行细粒度扰动，最后利用截断拉普拉斯机制优化发布的扰动结果，从而提高发布数据的可用性，与现有技术相比，具有以下有益效果：
(1)本发明提出了由k-匿名进行粗粒度的匿名化处理到差分隐私进行细粒度扰动的轨迹时间模式方法，相比于现有的时间模式保护方法，不仅能够保护轨迹时间模式的隐私，还能够保护精确的时间和位置数据；
(2)本发明利用截断拉普拉斯机制，可以将发布结果的误差限制在特定范围内，大大提高了数据可用性，该方法不仅简单有效，且易于实现。
本发明的其他优点、目标和特征在某种程度上将在随后的说明书中进行阐述，并且在某种程度上，基于对下文的考察研究对本领域技术人员而言将是显而易见的，或者可以从本发明的实践中得到教导。本发明的目标和其他优点可以通过下面的说明书来实现和获得。
附图说明
为了使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明作优选的详细描述，其中：
图1是本发明实施例提供的总体方法流程图；
图2是本发明实施例提供的具体步骤流程图；
图3是本发明实施例时间数据扰动生成器的逻辑结构示意图；
图4是本发明实施例提供的原始簇集的时间分布直方图；
图5是本发明实施例提供的所选簇集的时间分布直方图；
图6是本发明实施例提供的所选簇集经过k-匿名处理后的时间分布直方图；
图7是本发明实施例提供的所选簇集经过差分隐私处理后的时间分布直方图；
图8是本发明实施例提供的所选簇集经过截断拉普拉斯优化处理后的时间分布直方图。
具体实施方式
以下通过特定的具体实例说明本发明的实施方式，本领域技术人员可由本说明书所揭露的内容轻易地了解本发明的其他优点与功效。本发明还可以通过另外不同的具体实施方式加以实施或应用，本说明书中的各项细节也可以基于不同观点与应用，在没有背离本发明的精神下进行各种修饰或改变。需要说明的是，以下实施例中所提供的图示仅以示意方式说明本发明的基本构想，在不冲突的情况下，以下实施例及实施例中的特征可以相互组合。
其中，附图仅用于示例性说明，表示的仅是示意图，而非实物图，不能理解为对本发明的限制；为了更好地说明本发明的实施例，附图某些部件会有省略、放大或缩小，并不代表实际产品的尺寸；对本领域技术人员来说，附图中某些公知结构及其说明可能省略是可以理解的。
本发明实施例的附图中相同或相似的标号对应相同或相似的部件；在本发明的描述中，需要理解的是，若有术语“上”、“下”、“左”、“右”、“前”、“后”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此附图中描述位置关系的用语仅用于示例性说明，不能理解为对本发明的限制，对于本领域的普通技术人员而言，可以根据具体情况理解上述术语的具体含义。
下面以微软亚洲研究院收集的GPS轨迹大数据集Geolife Trajectories 1.3数据集为例，来阐述本发明的具体实施步骤。本发明首先利用k-匿名对时间戳进行粗粒度的匿名处理，然后使用差分隐私技术对时间戳加噪处理，进行细粒度的扰动，最后利用截断拉普拉斯机制优化扰动后的时间戳数据，以达到保护轨迹时间模式的目的。
本发明技术方案所提供方法可采用计算机软件技术实现自动运行流程，图1和图2分别是本发明实施例的总体方法流程图和具体步骤流程图，结合图2中本发明实施例的具体步骤流程图，图3中本发明实施例时间数据扰动生成器的逻辑结构示意图，本发明一种轨迹时间模式的差分隐私保护方法及系统的实施例具体步骤包括：
步骤S1，轨迹数据预处理及聚类。包括以下子步骤：
步骤S1-1，对待保护的轨迹数据进行清洗和规约，保留用户的经纬度数据和对应的时间戳作为新的轨迹数据集，记时间戳数据集为T＝{t1,…,tn}，Ti是T中的任一子集，则有Ti∈T，且Ti∈[tk,tm],tmin≤tk＜tm≤tmax，其中tk∈T,tm∈T,tmin是T中的最小值，tmax是T中的最大值；
实施例中，对微软亚洲研究院收集的GPS轨迹大数据集Geolife Trajectories1.3中的一段轨迹进行数据清洗和规约，保留用户的经纬度数据和对应的时间戳作为新的轨迹数据集，新轨迹数据集对应的的时间戳数据集为{07:08,...,08:09}；
步骤S1-2，将保留的轨迹数据集用DBSCAN算法进行密度聚类，得到聚类簇集C＝{c1,c2,...,cl}和对应的时间戳子集Tc＝{T1,T2,...,Tl}，其中，l是聚类簇的数目。
实施例中，对两个轨迹数据集分别用DBSCAN算法进行密度聚类，得到聚类簇集C＝{c1,c2,...,cl}和对应的时间戳子集Tc＝{T1,T2,...,Tl}，画出簇集C1的时间分布直方图如图4所示。
步骤S2，初始化参数，包括初始化匿名算法的参数k、隐私保护强度参数ε以及可接受的发布误差范围[-α,α]。其中初始化的k值需要判断是否合理，由步骤S1-2得到的时间戳子集Tc＝{T1,T2,...,Tl}计算k′然后根据k′判断用户初始定义的k值是否合理。包括以下子步骤:
步骤S2-1，初始化隐私保护强度参数ε以及可接受的发布误差范围[-α,α]；
实施例中，初始化参数ε＝2，α＝0.5；
步骤S2-2，初始化匿名算法的参数k值；
实施例中，初始化参数k＝2；
步骤S2-3，选择步骤S1-2得到的其中一个时间戳子集Ti∈Tc,计算k′值：
实施例中，选择簇集C1对应的一个时间数据子集T12，求得
步骤S2-4，判断步骤S2-2用户初始定义k值的合理性，若k∈[1,k′]且k为整数，则k合理，进入步骤S2-5；否则，返回步骤S2-2；
实施例中，
步骤S2-5，重复步骤S2-2、S2-3和S2-4，直到步骤S1中所有簇集对应的时间戳子集Ti都得到对应的计算结果k′，并与初始化的k值进行比较，得到最终合理的k值集合Kc＝{k1,k2,...,kl}。
实施例中，仅分别选取两个簇集中的一个时间数据子集T12和T21经过计算比较，得到合理的k值集合Kc＝{k12,k21}＝{2,2}。
步骤S3，利用k-匿名算法对时间戳进行粗粒度扰动。假设给定的簇集C对应的每一个时间数据子集Tc中共有n个时间戳，根据k匿名实现方法对所有时间戳子集Tc进行匿名处理，实现对时间戳的粗粒度扰动。包括以下子步骤：
步骤S3-1，选择步骤S1-2所得簇集对应的一个时间戳子集Ti∈Tc；
实施例中，选择簇集C1对应的一个时间戳子集T12；
步骤S3-2，判断k值集Kc中的ki值所在区间，若ki＝1，则不做匿名处理，进入步骤S4；否则，对时间戳子集Ti中的每个数据ti做如下匿名处理：
实施例中，K12＝2≠1，对时间戳子集T12中的每个数据做如下匿名处理：
步骤S3-3，重复步骤S3-1和S3-2，直到所有的时间戳子集Ti都进行了k-匿名处理,此时，得到时间戳子集Tc的粗粒度扰动结果Tc′＝{T1′,T2′,...,Tl′}。
实施例中，仅分别选取两个簇集中的一个时间戳子集T12和T21，画出原始簇集C12和C21的时间分布直方图如图5所示，对其进行上述2-匿名处理，得到初步扰动结果T′＝{T12′,T21′}，画出簇集C12和C21经过2-匿名处理后的时间分布直方图如图6所示。
步骤S4，利用差分隐私拉普拉斯噪声对时间戳进行细粒度扰动。根据初始化的隐私保护强度参数ε求出拉普拉斯噪声概率密度函数，生成对应的拉普拉斯噪声，对步骤S3-3得到的粗粒度扰动结果Tc′＝{T1′,T2′,...,Tl′}进行细粒度扰动，得到细粒度的扰动结果。包括以下子步骤：
步骤S4-1，根据初始化的隐私保护强度参数ε和时间戳的敏感度函数Δf计算得到拉普拉斯噪声的概率密度函数fLap(z)：
其中
实施例中，步骤S2已给定ε＝2，并且Δf＝1，所以
步骤S4-2，选择粗粒度扰动结果Tc′＝{T1′,T2′,...,Tl′}中的任意一个子集Ti′∈Tc′，根据拉普拉斯噪声的概率密度函数fLap(z)生成对应数目的噪声数据集Zi；
实施例中，选择粗粒度扰动结果中的任意一个子集T12′，根据拉普拉斯噪声的概率密度函数fLap(z)生成对应数目的噪声数据集Z12；
步骤S4-3，将生成的拉普拉斯噪声Zi加入到粗粒度扰动结果任一子集Ti′中，得到细粒度的扰动结果Ti″：
Ti″＝Ti′+Zi
实施例中，将生成的拉普拉斯噪声Z12加入到粗粒度扰动结果任一子集T12′中，得到细粒度的扰动结果T12″：
步骤S4-4，重复步骤S4-2和S4-3，直到粗粒度扰动结果Tc′＝{T1′,T2′,...,Tl′}中的所有子集都进行了细粒度扰动，得到对应的细粒度扰动结果Tc″＝{T1″,T2″,...,Tc″}。
实施例中，仅分别选取粗粒度扰动结果集中的两个时间戳子T12′和T21′，对其添加步骤S4-2对应的拉普拉斯噪声Z12和Z21，得到细粒度扰动结果T″＝{T12″,T21″}，画出簇集C12和C21经过差分隐私处理后的时间分布直方图如图7所示。
步骤S5，利用截断拉普拉斯机制优化扰动结果。根据初始化的隐私保护强度参数ε求出截断拉普拉斯噪声概率密度函数，生成对应的截断拉普拉斯噪声，对步骤S4-3得到的细粒度扰动结果Tc″＝{T1″,T2″,...,Tc″}进行优化，得到优化结果
步骤S5-1，根据初始化的隐私保护强度参数ε和时间戳的敏感度函数Δf计算得到截断拉普拉斯噪声的概率密度函数fTLap(z)：
其中
实施例中，步骤S2已给定ε＝2，α＝0.5，并且Δf＝1，所以
步骤S5-2，选择细粒度扰动结果Tc″＝{T1″,T2″,...,Tc″}中的任意一个子集Ti″∈Tc″，根据截断拉普拉斯噪声的概率密度函数fTLap(z)生成对应数目的噪声数据集Zi′；
实施例中，选择细粒度扰动结果集中的任意一个时间戳子集T12″，利用根据截断拉普拉斯噪声的概率密度函数fTLap(z)生成对应数目的噪声数据集Z′12；
步骤S5-3，将生成的拉普拉斯噪声Z′i加入到粗粒度扰动结果任一子集Ti″中，得到优化结果
实施例中，将生成的拉普拉斯噪声Z′12加入到粗粒度扰动结果子集T12″中，得到细粒度的扰动结果
步骤S5-4，重复步骤S5-2和S5-3，直到细粒度扰动结果Tc′＝{T1′,T2′,...,Tl′}中的所有子集都进行了优化，得到优化后的扰动数据集
实施例中，仅分别选取细粒度扰动结果集中的两个时间数据子集T12″和T21″，对其添加上述对应的截断拉普拉斯噪声Z′12和Z′21，得到优化结果
最后说明的是，以上实施例仅用以说明本发明的技术方案而非限制，尽管参照较佳实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，可以对本发明的技术方案进行修改或者等同替换，而不脱离本技术方案的宗旨和范围，其均应涵盖在本发明的权利要求范围当中。
