英语原文共 12 页
基于用户时空移动轨迹的去匿名方法
摘 要
目前，除了其他类型的数据外，用户移动轨迹越来越倾向于对用户进行去匿名化。其中，基于模型的方法通常比基于特征定位的方法提供更精确的去匿名。最近，人们提出了一种基于马尔可夫模型(HMM)的方法来寻找用户移动轨迹的移动模式。然而，在关键的一步隐藏状态的定义，现有的模型依赖于固定的时间、空间或数量的分类，这很难适用于所有不同的用户。本文提出了一种基于隐马尔可夫模型(HMM)的用户重构方法。与现有的方法不同，该方法利用一种新的基于密度的隐马尔可夫模型，该方法利用基于密度的聚类从三维(时间、纬度和纬度)对数据进行分级处理，并提供更好的性能。此外，我们还提出了一种频率时空立方滤波器（FSTC-Filter，frequent spatio-temporal cube filter），大大减少了候选模型的数量，从而提高了效率。
关键词：去匿名化；基于密度的HMM；频率时空立方；移动轨迹
简介
随着智能手机的普及，应用服务提供商可以轻松地从数十亿用户那里收集个人活动信息，但这也带来了用户隐私泄露的巨大风险。通常，这些供应商程序在向公众发布它们之前都会采取相应的方法，例如，将用户(例如，名称，SSN)替换为化名，但是由于更深入的研究，用户身份仍然可能受到损害。一些著名的去匿名例子包括从查看历史和将帐户链接到真实用户中发现其政治立场[10]，通过比较图形结构的相似性来区分匿名社交网络中的用户[9][11]。最近，用户移动轨迹可以更好地用于预测未来的位置[5, 15, 14]，区分异常用户[6, 7]，也包括用户去匿名化。
早期研究[17, 3, 2, 8]通常将每个用户的几个特征位置(例如最频繁的位置)作为用户移动档案。一些研究[4, 13, 12, 18]建立统计概率模型(例如，马尔可夫链，HMM)作为用户移动档案。正如我们将在第2节中看到的，基于模型的方法通常比基于特征位置的方法提供更精确的匹配。最近，基于HMM的几种方法可以更好地找出用户移动轨迹的活动模式。在这些方法中，核心部分是隐藏状态的定义，这决定了模型的有效性。现有模型在时间和空间或EM群集的分类上选择隐藏状态，这不能同时处理所有不同的用户。
本文提出了一种新的基于密度的隐马尔可夫模型(HMM)，它利用隐式聚类从三维(时间、纬度和精度)数据中提取HMM的隐藏状态。与假设每个人都有相同的隐藏状态不同，我们基于密度的隐马尔可夫模型考虑到数据的时间和空间密度特征，自动从每个用户的移动轨迹中提取不同的隐藏状态。此外，我们还提出了一个频率时空立方滤波器（FSTC-Filter），以提高降维效率。
总之，本文的贡献总结如下：
- 我们定义了一个基于密度的HMM(DBHMM)来描述用户的移动性。通过为每个用户生成更个性化的隐藏状态，建立精确的移动模型。集群(隐藏状态)及其数量直接由每个用户的数据生成。
- 为了减少匿名轨迹匹配候选模型的数量，我们引入了一个频率时空立方滤波器（FSTC-Filter）。在保证精确性的同时，提高了攻击效率。
- 我们在两个真实的数据基础上进行实验。结果表明，对用户行为的描述比其他方法更准确，过滤器对大量不正确的用户进行了精确的过滤，提高了效率。
本文的其余部分如下所示。第二节重点介绍了相关的工作，并分析了现有的方法。第三节介绍了该方法的框架。第四节和第五节分别阐述了两个基本组成部分。第六节给出了广泛的实验评价。最后，第七节对本文进行了总结。
相关工作
现有的基于用户位置的分类方法可以分为两大类。一种工作通过提取他/她的特征位置建立用户移动档案，我们称之为基于特征位置的方法。另一种方法是从他/她的移动轨迹建立一个统计概率模型，我们称之为基于模型的方法。
基于特征位置的方法通过用户的特征位置(通常是频繁的位置)来描述用户的特征。Zang等人[17]对每个用户访问次数最多的地点进行了一项研究。De Montjoye等人[2]证明随机选取的4个个体-时间点能够唯一识别95%的个体。Freudiger等人[3]将家庭/工作对作为每个用户的准标识符。Naini等人[8]利用地点分布作为个人资料来确定用户。
基于特征位置的方法主要是计算效率高，但精度有限。造成这一缺陷的原因有三个：(1)它们都是基于时间顺序的，因此无法区分表1中用户A和B的特征位置，例如t1: l1→l2与用户A和B都匹配。(2)忽略了大量的非特征位置，在没有特征位置的情况下，无法找到轨迹的匹配点，如 t2: l3→l4；(3)移动轨迹包含许多用户的不同特征位置，例如t3: l1→l2→l3→l4可以将用户A与l1 ,l2匹配，并将用户C与l2、l3匹配。
表 ‑1 特征位置缺陷分析实例
|
用户 |
每日轨迹 |
特征位置 |
匿名移动轨迹 |
匹配结果 |
|
A |
l1 → l2 → l3 → l4, l1 → l2 → l4 |
l1,l2 |
t1: l1 → l2 (A) t2: l3 → l4 (A) t3: l1 → l2 → l3 → l4 (A) |
t1: A,B t2: null t3: A,C |
|
B |
l2 → l1 → l6, l2 → l1 |
l1,l2 |
||
|
C |
l2 → l3 → l6, l2 → l3 → l5 |
l2,l3 |
基于模型的方法将统计概率模型训练成用户的移动性特征。如果匿名用户与现有用户模型匹配的概率高于其他用户模型，则认为它们是同一个用户。Gambs等人[4]提出了移动马尔可夫链(MMC)用户移动档案。它只考虑位置信息，不考虑时间影响。Pan等人[12]为签入数据建立了一个马尔可夫调制的过程模型。它将轨迹状态变化作为马尔可夫跳变过程(马尔可夫跳变过程)，每个签入过程取决于状态，并且签入位置与高斯状态一致。
本文最相关的工作是这些与HMM相关的方法。Zhang等人[18]提出将用户分组和移动性建模相结合。它们使用EM算法为每个组生成隐马尔可夫模型的隐藏状态。但是，他们为任何群体提名了一个统一的隐藏群，而不考虑他们的差异。Wang等人[13]定义了描述用户移动行为的概念，并利用它发起反攻击。它将一天的时间划分为24次，作为24个隐藏状态。但用户行为并不完全与时间有关，它忽略了用户的主观能动性。
一般来说，基于模型的方法通过状态转换和捕获非特征位置作为观察来反映轨迹的时间序列。与基于特征位置的方法相比，它们提供了更精确的匹配。然而，它们仍有两个不足之处。首先，使用相同的规则将隐藏状态分配给所有用户，可能会给一些用户带来不便。其次，时间成本远远大于特征位置。我们将分别在第4节和第5节详细讨论和改进它们。
概述
在本文中，我们提出了一种基于密度的隐马尔可夫模型(HMM)和FSTC-Filter的去匿名攻击方法。如上所述，现有的隐马尔可夫模型(HMM)不够个性化，无法捕获用户的移动性特征，其时间开销太大。首先，我们通过生成更精确的隐藏状态来改进移动性建模。使用基于密度的聚类算法，无需指定统一的状态或状态数，就可以得到每个用户的隐藏状态。此外，我们还增加了一个隐式滤波器，以减少匿名移动轨迹匹配的候选模型的数量。滤波器的子阶段匹配和移动模型匹配分别能最大限度地减少时间开销和保证精度。
图 3‑1 我们的方法框架
图3-1是我们方法的框架，包括两个主要阶段：训练阶段和攻击阶段。训练阶段是去匿名化的准备阶段。它用来训练一个统计概率模型作为每个用户的移动性特征。首先利用基于密度的聚类算法生成个性化的隐状态，然后根据上述隐藏状态对基于密度的隐马尔可夫模型进行训练。攻击阶段是去匿名的执行阶段。它用来找出最有可能拥有匿名移动痕迹的用户。在此阶段，我们分三个步骤对匿名数据进行去匿名处理：首先，我们利用频率时空立方滤波器 (FSTC-Filter) 来减少匿名轨迹匹配的候选模型的数量。然后，利用该算法生成匿名轨迹和过滤候选模型之间的匹配概率。最后，通过排名和投票，我们从前k的候选集合中选出最终的匹配结果。
基于密度的HMM训练
在本节中，我们展示如何为每个用户精确地生成更精确的隐藏状态，并描述如何使用这些隐藏状态来构建用户HMM。
隐藏状态选择原则
隐藏状态生成的一个最重要的原则是，不应该事先指定隐藏状态。直接指定意味着所有用户的隐藏状态都是根据统一原则生成的。研究[13]将每小时指定为隐藏状态，研究[1]将网格指定为隐藏状态。这些方法可能产生不准确的隐藏状态，这会导致不准确的模型。如图4-1所示，如果我们将每个网格指定为隐藏状态，它就无法准确区分用户B的移动点，因为它的点位于不同的网格中。因此，这些指定的隐藏状态不能准确地对用户进行配置。此外，虽然可能有这样一个人很适合的分类，但绝对没有适合所有用户的划分。
图 ‑1 现有隐藏状态举例
- 用户的隐藏状态数应该是可变的，因为不同的人可能有不同的移动模式。EM聚类方法在一定程度上保证了当用户有相似模式时，隐藏状态与用户行为之间的精确对应[18][7]。它们指定一个统一的集群。所有用户都可以使用。然而，在实践中不同的用户可能具有不同数量的隐藏状态。如图4-1所示，用户B具有三个隐藏状态和离散点。如果我们指定对于用户B存在2个隐藏状态，则很可能大多数B的移动被群集为一个状态，而离散点作为另一个状态。EM算法不能解决给定错误用户状态数的问题。
隐藏状态的生成
显然，密度聚类发现高密度区域被区域分隔，可以解决上述问题。利用这些密度参数，可以自动获得所有具有不确定数和任意形状的高密度区域。另一方面，时空点的密集区域通常意味着用户移动性的模式，这对应于隐藏状态生成的目的。
通过将密度相似聚类算法(一种典型的基于密度的聚类算法[20])扩展到三维空间，建立了隐状态生成算法。初始聚类的主要思想是通过参数和ε生成初始聚类，然后逐步生成初始聚类，直至其停止。Minpts是创建初始群集所需的最小点数，而ε是初始群集的最大半径。准时态点(t1、t1)和(t2、t2)之间的距离d(等距d)是适用于测量这两个时态点之间的距离的。更具体而言，d(p1, p2)的定义如下：
(4-1)
其中a=111000，b=111000*cos((Lat1 Lat2)/2)是将距离测量单位转换为米的参数，以及时间测量单位（秒）。
在图4-2(a)和图4-2(b)中显示了这些点，则会生成四个隐藏状态，它们都是在红线中圈起来的。
(a)平面图 (b)立体图
图 ‑2 密集点与隐藏状态
基于密度的HMM训练
我们知道如何生成隐藏状态，我们可以为具有所有移动轨迹的用户构建基于密度的隐马尔可夫模型。更具体地，DBHMM＝{O, S, Pi;, A, E}定义如下：
1.隐藏状态集合S={s1, s2, hellip;, sm}是通过基于密度的聚类从用户轨迹生成的。
2.观察集O={O1，O2, ..., ON}，其中每个元素都是用户访问的一个点/记录。
3.初始概率集Pi;，是隐态的初始概率分布。隐藏状态si的初始概率定义为：
(-1)
其中，count(si)表示属于si的记录/点数的数目。
4.过渡概率集A={a1,1, a1,2, hellip;, ai,j, ...}，每个元素ai,j代表从si转移到sj的概率，其定义为：
(-2)
其中T(si)表示用户访问si中某个位置的次数和下一个位置(而不是si)，而T(si，sj)指示用户访问si中的地点的次数，并且访问sj中的下一地点。
5.发射概率集E={e1(olt;
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
