一种用户轨迹的隐私保护方法和装置与流程

1.本说明书一个或多个实施例涉及数据安全和隐私保护领域，尤其涉及一种用户轨迹 的隐私保护方法和装置。


背景技术：

2.近年来，随着移动手机等智能终端的普及和移动计算技术的发展，位置服务(locationbased service，lbs)越来越受到人们的青睐，它给人们带来方便的同时，也增加了隐私 泄露的风险。攻击者可以很轻易地从位置信息中提取出用户的家庭地址、健康状况、收入 等信息。因此,一些解决方案被业界提出来用于保护lbs中用户的位置隐私。这些解决 方案通过简单地修改敏感数据或构造合成数据来保护位置隐私，但是面对重新识别攻 击和合成数据区分，这些方案无法达到预期的效果。
3.因此，需要改进的方案，更好地对用户位置信息和轨迹信息进行隐私保护。


技术实现要素：

4.本说明书中的实施例旨在提供更有效地对用户位置信息进行隐私保护的方法，解决 现有技术中的不足。
5.根据第一方面,提供了一种用户轨迹的隐私保护方法，包括，
6.获取用户当前的真实轨迹，其中包括多个真实位置点；
7.获取多个位置类簇，所述多个位置类簇根据历史轨迹集合中的多个历史位置点的 位置语义，对所述多个历史位置点进行聚合处理而得到；
8.对于所述多个真实位置点中任意的目标位置点，从所述多个位置类簇中确定所述 目标位置点对应的目标类簇；
9.根据目标位置点的位置语义，从所述目标类簇中确定出若干候选位置点；
10.根据用户在所述目标位置点的移动状态，从所述若干候选位置点中确定出该目标 位置点的若干替代位置点；
11.利用所述多个真实位置点各自对应的若干替代位置点，生成若干个合成轨迹。
12.在一个实施例中，所述方法还包括，
13.将所述合成轨迹和所述真实轨迹，共同提供给用户。
14.在一个实施例中，所述位置语义包括，相应位置点的访问时间和访问持续时长。
15.在一个实施例中，从所述多个位置类簇中确定所述目标位置点对应的目标类簇， 包括：
16.根据各个位置类簇包含的位置点的位置语义，计算各个位置类簇的集合语义；
17.通过比较目标位置点的位置语义与所述各个位置类簇的集合语义，从所述多个位 置类簇中，确定所述目标类簇。
18.在一个实施例中，所述集合语义为所述位置类簇包括的位置点的位置语义的均值。
19.在一个实施例中，通过比较目标位置点的位置语义与所述各个位置类簇的集合语 义，从所述多个位置类簇中，确定所述目标类簇，包括：
20.从所述多个位置类簇中，选择其集合语义与所述目标位置点的位置语义相差最小 的位置类簇，作为所述目标类簇。
21.在一个实施例中，根据目标位置点的位置语义，从所述目标类簇中确定出若干候 选位置点,包括：
22.对于所述目标类簇包含的各个位置点，确定该位置点的位置语义的概率分布与所 述目标位置点的位置语义的概率分布的分布距离；
23.将分布距离小于或等于预定阈值的若干位置点，作为所述若干候选位置点。
24.在一个实施例中，所述分布距离为wasserstein距离。
25.在一个实施例中，所述位置语义包括访问时间和访问持续时长；所述确定该位置 点的位置语义的概率分布与所述目标位置点的位置语义的概率分布的分布距离，包括：
26.确定该位置点的访问时间的第一概率分布与所述目标位置点的访问时间的第二 概率分布之间的第一分布距离；以及
27.确定该位置点的访问持续时长的第三概率分布与所述目标位置点的访问持续时长 的第四概率分布之间的第二分布距离；
28.所述将分布距离小于或等于预定阈值的若干位置点，作为所述若干候选位置点， 包括：
29.确定所述第一分布距离小于或等于预定的第一阈值，且所述第二分布距离小于或 等于预定的第二阈值的若干位置点，作为所述若干候选位置点。
30.在一个实施例中，根据用户在所述目标位置点的移动状态，从所述若干候选位置 点中确定出该目标位置点的若干替代位置点，包括：
31.根据目标位置点在所述真实轨迹中与其相邻前一位置点的距离，确定用户在所述 目标位置点的移动粒度；
32.根据所述目标位置点与所述若干候选位置点关于移动粒度的粒度相似度，从所述 若干候选位置点中，确定出第一位置集合，将其中的位置点作为所述若干替代位置点。
33.在一个实施例中，根据所述目标位置点与所述若干候选位置点关于移动粒度的粒 度相似度，从所述若干候选位置点中，确定出第一位置集合,包括：
34.根据所述目标位置点与其若干候选位置点的所述粒度相似度和语义相似度，确定 所述目标位置点与其若干候选位置点的第一综合相似度；
35.根据所述第一综合相似度，从所述候选位置点中，确定出所述第一位置集合。
36.在一个实施例中，根据所述目标位置点与其若干候选位置点关于移动粒度的粒度 相似度、和语义相似度，确定所述目标位置点与其若干候选位置点的第一综合相似度， 包括，
37.根据所述目标位置点与其若干候选位置点的粒度相似度和语义相似度的加权和， 确定所述目标位置点与其若干候选位置点的第一综合相似度。
38.在一个实施例中，所述若干候选位置点包括第一候选位置点，所述目标位置点与 该第一候选位置点的所述粒度相似度，基于目标位置点的移动粒度与该第一候选位置 点的移动粒度中，值高者与值低者的比值而确定。
39.在一个实施例中，根据用户在所述目标位置点的移动状态，从所述若干候选位置 点中确定出该目标位置点的若干替代位置点，包括：
40.确定用户在目标位置点的移动方向；
41.根据所述目标位置点与所述若干候选位置点关于移动方向的方向相似度，从所述 若干候选位置点中，确定出第二位置集合，将其中的位置点作为所述若干替代位置点。
42.在一个实施例中，所述若干候选位置点包括第一候选位置点，所述目标位置点与 该第一候选位置点的方向相似度，负相关于所述目标位置点的移动方向与所述第一候 选位置点的移动方向之间的方向差值。
43.在一个实施例中，根据用户在所述目标位置点的移动状态，从所述若干候选位置 点中确定出该目标位置点的若干替代位置点，包括：
44.根据目标位置点在所述真实轨迹中与其相邻前一位置点的距离，确定用户在所述 目标位置点的移动粒度；
45.根据所述目标位置点与所述若干候选位置点关于移动粒度的粒度相似度，从所述 若干候选位置点中，确定出第一位置集合；
46.确定用户在目标位置点的移动方向；
47.根据所述目标位置点与所述第一位置集合中各个位置点关于移动方向的方向相 似度，从所述第一位置集合中，确定出第二位置集合，将其中的位置点作为所述若干 替代位置点。
48.在一个实施例中，根据所述目标位置点与所述若干候选位置点关于移动粒度的粒 度相似度，从所述若干候选位置点中，确定出第一位置集合,包括：
49.根据所述目标位置点与其若干候选位置点的所述粒度相似度和语义相似度，确定 所述目标位置点与其若干候选位置点的第一综合相似度；
50.根据所述第一综合相似度，从所述候选位置点中，确定出所述第一位置集合。
51.在一个实施例中，根据所述目标位置点与其若干候选位置点的所述粒度相似度和 语义相似度，确定所述目标位置点与其若干候选位置点的第一综合相似度,包括，
52.根据所述目标位置点与其若干候选位置点的所述粒度相似度和语义相似度的加 权和，确定所述目标位置点与其若干候选位置点的第一综合相似度。
53.在一个实施例中，根据所述目标位置点与所述第一位置集合中各个位置点关于移 动方向的方向相似度，从所述第一位置集合中，确定出第二位置集合,包括：
54.根据所述目标位置点与所述第一位置集合中各个位置点的所述第一综合相似度 和所述方向相似度，确定所述目标位置点与该各个位置点的第二综合相似度；
55.根据所述第二综合相似度，从所述第一位置集合中，确定出所述第二位置集合。
56.在一个实施例中，确定用户在目标位置点的移动方向,包括，
57.根据目标位置点在所述真实轨迹中与其相邻后一位置点的连线和水平线的夹角， 确定用户在所述目标位置点的移动方向。
58.在一个实施例中，根据所述目标位置点与所述第一位置集合中各个位置点关于移 动方向的方向相似度，从所述第一位置集合中，确定出第二位置集合,包括：
59.根据所述目标位置点与所述第一位置集合中各个位置点的粒度相似度、方向相似 度和语义相似度，确定所述目标位置点与该各个位置点的第三综合相似度；
(location
‑
based
‑
service)中用户的位置隐私。有些方案通常通过删除标识符或构 造数据特征来简单地修改敏感数据，但是其存在面对重新识别攻击，无法达到预期的 效果。例如，攻击者通过去匿名处理，可以从用户的运动模式中提取出个人习惯，兴 趣和人际关系。另一些技术方案通过将合成轨迹和真实轨迹一同发布进行轨迹隐私保 护。但是，基于这些方案生成的合成轨迹仍然缺乏全面和系统的设计，攻击者可以很 容易地将生成的轨迹与实际轨迹区分开。例如，用户总是在11：00
‑
13：00之间在饭 店用餐，而合成轨迹显示他在这段时间里在超市或便利店。显然，攻击者可以很容易 地区分这种情况并确定其真实轨迹。
81.此外,一些技术方案可以使得合成轨迹和真实轨迹具有相似的统计特征，但是无 法保证轨迹在用户运动方向、幅度等方面的相似性。因此，其合成的轨迹数据集与真 实估计本质上是异构的，这种异构性会对轨迹相似性的评估产生负面影响,从而影响合 成轨迹的保护隐私的效果。
82.发明人为了解决上述技术问题，在本说明书中的实施例中，提出一种用户轨迹的隐 私保护方法及其装置。该方法的基本思想是：首先，对历史轨迹数据集中包含的所有位置 点,根据其位置语义进行聚类处理,得到一系列语义相似的位置点的集合。然后，将用户真 实轨迹的每个位置与这些语义集合进行匹配，获取该真实位置的对应集合，并从对应集合 中选择多个候选位置作为与该真实位置匹配的虚假位置。接着，它从候选位置集中选出与 用户的真实位置在移动幅度和运动方向上最接近的若干个虚假位置。最后，将选出来的这 些位置点，替换真实轨迹中的对应位置点，生成合成轨迹。
83.根据一种实施方式，图1示出根据本说明书实施例的一种用户轨迹的隐私保护方法 的原理示意图。如图1所述，该方法例如可以包括四个部分：基于语义的历史位置聚类， 基于语义的位置匹配，基于移动幅度的位置匹配和基于移动方向的位置匹配。
84.首先，获取历史轨迹数据集的语义信息，然后基于这些语义信息使用聚类算法将这些 数据集分为一系列集合c1...cm(如图1(a)所示)，或称为类簇。接着，将真实轨迹的每 个位置映射到具有相似语义信息的集合中，并根据其到集合中各位置点之间的例如 wasserstein距离，挑选例如为4k个候选位置以进行后续操作(如图1(b)所示)。然 后，从这4k个候选位置集合中选择与真实位置具有最大移动幅度相似度的例如为2k个位 置(如图1(c)所示)。最终，通过方向匹配保留候选位置中的例如k个位置，以使用户在 这些位置点的运动方向，尽可能与真实轨迹中用户在对应位置点的运动方向相同(如图1 (d)所示)。通过这种方式，在用户例如使用lbs服务时，可以合成例如为k条虚假轨迹 以保护用户的位置隐私。
85.综上，本方法的核心思想是合成相对于真实轨迹“似是而非”的轨迹，以便隐藏用户 的敏感信息，保护用户的位置隐私。为了实现该目标，该方法利用了一系列在语义信息、 移动幅度和运动方向与真实轨迹中的位置十分相似的虚假位置，来合成虚假轨迹。从而使 得，攻击者即使在掌握一定的背景知识的前提下，也很难区别真实轨迹和合成的轨迹。并 且，由于这些虚假位置并不是人工生成或凭空捏造的，均是原始数据集中真实存在的，所 以其统计特性并不会受到大的影响。
86.下面阐述该方法的详细过程。图2示出根据本说明书实施例的一种用户轨迹的隐私 保护方法的流程图。如图2所述，该方法至少包括如下步骤：
87.步骤21，获取用户当前的真实轨迹，其中包括多个真实位置点；
88.步骤22，获取多个位置类簇，所述多个位置类簇根据用户历史轨迹集合中的多个 历史位置点的位置语义，对所述多个历史位置点进行聚合处理而得到；
89.步骤23，对于所述多个真实位置点中任意的目标位置点，从所述多个位置类簇中 确定所述目标位置点对应的目标类簇；
90.步骤24，根据目标位置点的位置语义，从所述目标类簇中确定出若干候选位置点；
91.步骤25，根据用户在所述目标位置点的移动状态，从所述若干候选位置点中确定 出该目标位置点的若干替代位置点；
92.步骤26，利用所述多个真实位置点各自对应的若干替代位置点，生成若干个合成 轨迹。
93.首先，在步骤21，获取用户当前的真实轨迹。该真实轨迹中通常包括用户依照时 间顺序前往的多个位置点。在一个实施例中，当用户使用lbs的过程中，用户携带的 终端设备中的定位模块，可以每隔一特定时间间隔(例如，1s)采集一次用户的当前 位置信息，从而得到多个位置点，这些位置点按照时间顺序组合形成该用户当前的真 实轨迹。在另一个实施例中，还可以根据其他方式获取用户当前的真实轨迹。对于获 取用户当前的真实轨迹的具体方式，本说明书不做限定。
94.然后，在步骤22，获取多个位置类簇。所述多个位置类簇根据历史轨迹集合中的 多个历史位置点的位置语义，对所述多个历史位置点进行聚合处理而得到。
95.该步骤中，利用历史轨迹集中的位置点进行聚类。该历史轨迹集合中的历史轨迹， 可以来自于大量用户的数据积累，也可以来自于步骤21中提及的当前待处理的用户。 并且，历史轨迹集合中的历史位置点，是对应用户历史上曾经真实到达的位置点。相 对于人工生成的位置点，这样的历史位置点，其统计特性更符合用户位置的真实特性。
96.该步骤中，基于历史轨迹集合进行聚类处理，可以得到多个位置类簇。位置聚类 的目的是将历史轨迹数据集中包含的位置点基于语义信息分为一系列集合，将具有较 高语义相似性的位置组合在一起表示一个位置语义集，即位置类簇。
97.一个位置点的位置语义，可以包括该位置点所代表的可理解的含义。在不同实施 例中，位置语义可以有不同的表达。在一个实施例中，位置语义包括，该位置点所在 区域的功能类型，例如，办公区域，餐饮区域，商圈/商场，公园，等等。在一个实施 例中，位置语义可以包括，相应位置点的访问时间和访问持续时长。
98.下面结合位置语义包括访问时间和访问持续时长的实施例，描述对历史位置点进 行聚合处理(或聚类)的过程。
99.在一个具体实施例中，可以提取历史轨迹集合中的多个历史位置点，获取各个历 史位置点的位置语义，然后
100.根据如下的聚类条件，对该多个历史位置点进行聚类，该聚类条件的数据表达式 为，
[0101][0102]
其中，ξ和δ分别表示第一聚类阈值和第二聚类阈值，在一种实施例中，其取值 可
以预先设定，且取值范围可以在[0,1]区间。l
p
和l
k
为任意的历史位置点，t
lp
、t
lk
分别为l
p
和l
k
的访问时间，δt
lp
、δt
lk
分别为l
p
和l
k
的访问持续时长。当l
p
和l
k
的访 问时间和访问持续时长满足公式(1)时，l
p
和l
k
可以归属于同一位置类簇。
[0103]
在一个实施例中，可以对从历史轨迹集合中提取的多个历史位置点按公式(1) 进行扫描聚类后，获得若干位置类簇。
[0104]
在另一个实施例中，在扫描聚类过程中，还可以参照以下的区分条件，区分归属 于不同类簇或不同语义集合的位置点，该区分条件定义，分别在两个语义集合中的任 意两个位置，它们的位置语义满足如下的数学表达式：
[0105][0106]
其中，ξ’和δ’分别表示第三聚类阈值和第四聚类阈值，在一种实施例中，其取值 可以预先设定，且取值范围可以在[0,1]区间。在不同的实施例中，其可以分别等于或 不等于上述公式(1)中的第一聚类阈值和第二聚类阈值。l
p’和l
k’分别为在两个语义 集合中的任意两个位置，t
lp’、t
lk’分别为l
p’和l
k’的访问时间，δt
lp’、δt
lk’分别为l
p’和 l
k’的访问持续时长。
[0107]
通过以上方式，可以基于位置语义对多个历史位置点进行聚类或聚合处理，得到 多个位置类簇。在一个实施例中，以上聚类的过程可以离线预先进行。步骤22中可以 读取预先通过聚类得到的多个位置类簇。
[0108]
接着，在步骤23，对于多个真实位置点中任意的目标位置点，从多个位置类簇中 确定所述目标位置点对应的目标类簇。
[0109]
该步骤中，为各个真实位置点匹配对应的目标类簇。
[0110]
所述匹配可以依据真实位置点和位置类簇的位置语义进行。位置类簇的位置语义， 可以是其包含的多个位置点的集合语义。因此，在一个实施例中，可以通过以下步骤 确定目标位置点对应的目标类簇：根据各个位置类簇包含的位置点的位置语义，计算 各个位置类簇的集合语义；通过比较目标位置点的位置语义与所述各个位置类簇的集 合语义，从所述多个位置类簇中，确定所述目标类簇。
[0111]
在一个实施例中，集合语义可以为所述位置类簇包括的位置点的位置语义的均值。 仍以位置语义包括访问时间和访问持续时长为例，该实施例中，所述集合语义的数学 表达式可以为，
[0112][0113]
其中，t
ci
和δt
ci
分别为位置类簇ci的访问时间和访问持续时长，ζ为位置类簇 ci包含的位置点数量，ti和δti分别为位置类簇ci中索引为i的位置点的访问时间 和访问持续时长。
[0114]
在一个实施例中，可以从所述多个位置类簇中，选择其集合语义与所述目标位置 点的位置语义相差最小的位置类簇，作为所述目标类簇。在一个具体的例子中，可以 将同
时满足下列公式(4)、公式(5)的位置类簇作为目标类簇，
[0115][0116][0117]
其中，t
l
、δt
l
分别为目标位置点的访问时间和访问持续时长，t
cj
和δt
cj
分别为 序数为j的位置类簇cj的访问时间和访问持续时长。和o分别为第一筛选聚类阈值 和第二筛选阈值，通过和o可以确定成为目标类簇的最低条件。c1...cm为满足公式 (4)的位置类簇,min{}为取最小值函数，通过公式(5)，可以从c1...cm中选取与 目标位置的位置语义相差最小的位置类簇，作为目标类簇。
[0118]
基于确定出的目标类簇，在步骤14，根据目标位置点的位置语义，从所述目标类 簇中确定出若干候选位置点。
[0119]
该步骤中，可以从目标类簇中，选择其位置语义与目标位置点接近的若干位置点， 作为目标位置点的候选位置点。
[0120]
在一个实施例中，可以通过以下步骤从目标类簇中确定出若干候选位置点：对于 所述目标类簇包含的各个位置点，确定该位置点的位置语义的概率分布与所述目标位 置点的位置语义的概率分布的分布距离；将分布距离小于或等于预定阈值的若干位置 点，作为所述若干候选位置点。在一个实施例中，分布距离可以为wasserstein距离。 wasserstein距离又称为推土距离emd(earth mover's distance),表示将一个概率 分布转换到另一个概率分布所需要的最小代价，可以用来衡量不同的概率分布之间的 差别。在其他的实施例中，也可以使用例如为欧式距离、交叉熵的其他类型的用于衡 量概率分布差别的度量方式。
[0121]
延续位置语义包含访问时间和访问持续时长的例子，在一个具体的实施方式中， 确定候选位置点的步骤可以具体为：确定某个位置点的访问时间的第一概率分布与所 述目标位置点的访问时间的第二概率分布之间的第一分布距离；以及，确定该位置点 的访问持续时长的第三概率分布与所述目标位置点的访问持续时长的第四概率分布之 间的第二分布距离。然后，从目标类簇包含的各个位置点中，确定第一分布距离小于 或等于预定的第一阈值，且第二分布距离小于或等于预定的第二阈值的若干位置点， 作为所述若干候选位置点。在一个例子中，可以利用下列公式所表示的条件，确定候 选位置点：
[0122][0123][0124]
其中，d
emd
()为分布距离函数，pt
la
为第一概率分布，pt
lb
为第二概率分布、pδ l
ta
为第三概率分布、pδt
lb
为第四概率分布、σ为第一阈值，ε为第二阈值，s
emd
()为 候选决策函数。当s
emd
(pt
la
，pt
lb
)和s
emd
(pδt
la
，pδt
lb
)均为1时，位置点l
a
可以 作为目标位置点l
b
的候选位置点。
[0125]
接着，在步骤25，根据用户在所述目标位置点的移动状态，从所述若干候选位置 点中确定出该目标位置点的若干替代位置点。
[0126]
该步骤中，依据用户在所述目标位置点的移动状态，从步骤24获得的若干候选 位置点中，选择目标位置点的若干替代位置点。在不同的实施例中，用户在目标位置 点的移动状态，可以包括用户在目标位置点的移动幅度和/或移动方向，其中所述移动 幅度用于表征用户在一定时间内的移动距离大小，与移动速度相类似。在本说明书的 上下文中，又将该移动幅度称为移动粒度(granularity)，两者在本文中可以等同替 换使用。
[0127]
在一个实施例中，由于对用户位置点进行采样的间隔时间为固定的，因此，可以 利用用户运行轨迹(可以包括合成和真实轨迹)上两个相邻位置之间的距离，表示用 户的后一位置上的移动粒度。在一个具体的实施例中，位置点l
k
的移动粒度g(l
k
) 的数学表示式可以为，
[0128][0129]
其中，d(l
k
，l
k
‑1)为位置点l
k
和其轨迹中相邻前一位置点l
k
‑1的距离，x
k
、x
k
‑1、 y
k
、y
k
‑1分别表示l
k
、l
k
‑1的x轴和y轴位置坐标。
[0130]
根据一种实施方式，可以根据用户在候选位置点和目标位置点的移动粒度，从候 选位置点中确定出目标位置点的替代位置点。具体地，在该实施方式中，可以根据目 标位置点在所述真实轨迹中与其相邻前一位置点的距离，确定用户在所述目标位置点 的移动粒度；根据所述目标位置点与所述若干候选位置点关于移动粒度的粒度相似度， 从所述若干候选位置点中，确定出第一位置集合，将其中的位置点作为所述若干替代 位置点。
[0131]
在一个实施例中，若干候选位置点中可以包括任意的第一候选位置点。目标位置 点与该第一候选位置点的粒度相似度，可以基于目标位置点的移动粒度与该第一候选 位置点的移动粒度中，值高者与值低者的比值而确定。该实施例中，确定粒度相似度 的数学表示可以为，
[0132][0133]
其中，s
grd
(l
k
，l
q
)为位置点l
k
和第一候选位置点l
q
的粒度相似度，g(l
k
)和g (l
q
)分别表示l
k
、l
q
的移动粒度。
[0134]
在例如根据公式(9)确定出目标位置点与各个候选位置点的粒度相似度的基础 上，可以从各个候选位置点中选择与目标位置点的粒度相似度较大的一些(例如预定 数目，或预定比例)位置点构成上述第一位置集合，从而得到目标位置点的若干替代 位置点。
[0135]
在根据该实施方式的另一个实施例中，还可以根据所述目标位置点与其若干候选 位置点的所述粒度相似度和语义相似度，确定所述目标位置点与其若干候选位置点的 第一综合相似度；根据所述第一综合相似度，从所述候选位置点中，确定出所述第一 位置集合。更具体的，可以根据所述目标位置点与其若干候选位置点的粒度相似度和 语义相似度的加权和，确定所述目标位置点与其若干候选位置点的第一综合相似度。 该实施例中，第一综合相似度的确定可以以数学方式表示为：
[0136]
m
s,g
(l
k
,l
q
)＝α*d
emd
(pl
k
,pl
q
) β*s
grd
(l
k
,l
q
)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(10)
[0137]
其中，m
s,g
()为第一综合相似度，l
k
为目标位置点，l
q
为候选位置点，d
emd
(pl
k
， pl
q
)和s
grd
(l
k
，l
q
)分别为l
k
和l
q
的语义相似度和粒度相似度，α、β分别为语义相 似度和粒度相
似度的权重。
[0138]
基于粒度相似度的比较来得到替代位置点，可以在后续步骤中合成轨迹后，避免 攻击者通过粒度信息识别出真实轨迹。为了表现该合成效果，图3示出根据本说明书实 施例的不计量移动粒度的合成轨迹示意图。如图3所示，假设驾驶员在限速80km/h 的高速公路上行驶。他在时刻t0从位置l0开始行驶，并在t1时刻到达位置l1。虚 线轨迹为忽略了位置粒度得到的合成轨迹，从中可以获知他在时间t0从位置l01开始， 在时间t2到达位置l11。l01和l11之间的距离已超过80*(t1
‑
t0)。显然，攻击者 很容易通过位置之间的时空关系来区分合成轨迹和真实轨迹。而本说明书实施例中， 依据移动粒度来确定替代位置，可以避免这种问题发生。
[0139]
根据另一种实施方式，还可以通过如下步骤，从若干候选位置点中确定出该目标 位置点的若干替代位置点：确定用户在目标位置点的移动方向；根据所述目标位置点 与所述若干候选位置点关于移动方向的方向相似度，从所述若干候选位置点中，确定 出第二位置集合，将其中的位置点作为所述若干替代位置点。
[0140]
在一个实施例中，若干候选位置点中可以包括任意的第一候选位置点。目标位置 点与该第一候选位置点的方向相似度，可以负相关于所述目标位置点的移动方向与所 述第一候选位置点的移动方向之间的方向差值。也就是说，目标位置点与第一候选位 置点的移动方向的方向差值越小，两者之间的方向相似度越大，移动方向越相似。
[0141]
基于方向相似度的比较来得到替代位置点，可以在后续步骤中合成轨迹后，避免 攻击者通过方向信息识别出真实轨迹。为了表现该合成效果，图4示出根据本说明书实 施例的不计量移动方向的合成轨迹示意图。从图4中可以看出，当道路为单向限行通道， 由虚线表示的合成轨迹运动方向与限行方向相反，攻击者可以很轻易将其与真实轨迹 区分出来。而本说明书实施例中，依据移动方向来确定替代位置，可以避免这种问题 发生。
[0142]
根据又一种实施方式，还可以综合考虑移动粒度和移动方向两者，从候选位置点 中确定出目标位置点的替代位置点。具体的，可以通过如下步骤，确定目标位置点的 替代位置点：根据目标位置点在所述真实轨迹中与其相邻前一位置点的距离，确定用 户在所述目标位置点的移动粒度；根据所述目标位置点与所述若干候选位置点关于移 动粒度的粒度相似度，从所述若干候选位置点中，确定出第一位置集合；确定用户在 目标位置点的移动方向；根据所述目标位置点与所述第一位置集合中各个位置点关于 移动方向的方向相似度，从所述第一位置集合中，确定出第二位置集合，将其中的位 置点作为所述若干替代位置点。
[0143]
该实施方式中,采用的分步筛选的方式可以减少计算开销，在筛选的各分步中仅 分别选择部分候选位置来拟合真实轨迹上的位置点，而不是将目标位置所属的目标类 簇中所有位置点的语义，粒度和方向相似度都计算出来进行筛选；在分步筛选的任意 步骤中，与真实位置差异较大的位置点直接被舍弃，不参与后续过程，减少了大量不 必要的计算。
[0144]
根据一种具体的实施方式，可以通过如下步骤确定出第一位置集合：根据所述目 标位置点与其若干候选位置点的所述粒度相似度和语义相似度，确定所述目标位置点 与其若干候选位置点的第一综合相似度；根据所述第一综合相似度，从所述候选位置 点中，确定出所述第一位置集合。第一综合相似度的确定，例如可以采用前述公式(10) 的方式。
[0145]
进一步地，可以根据所述目标位置点与所述第一位置集合中各个位置点的所述第 一综合相似度和所述方向相似度，确定所述目标位置点与该各个位置点的第二综合相 似度；根据所述第二综合相似度，从所述第一位置集合中，确定出所述第二位置集合。 在一个具体的实施例中，第二综合相似度的数学表达式可以为，
[0146][0147]
其中，m
f
(l
p
,l
q
)为目标位置点l
p
和第一位置集合中位置点l
q
的第二综合相似度， m
s,g
(l
p
,l
q
)为l
p
和l
q
的第一综合相似度，m
dir
(l
p
,l
q
)为l
p
和l
q
的方向相似度，为l
p
和 第一位置集合中各位置点的第一综合相似度中之最大值，γ为方向相似度的权重。
[0148]
在不同的实施例中，所述方向相似度可以具有不同的确定方式。在一个具体的实施 例中，方向相似度的数学表达式可以为，
[0149][0150]
其中，m
dir
(l
p
,l
q
)为目标位置点l
p
和第一位置集合中位置点l
q
的方向相似度，θ
dir (l
p
,l
q
)为用户在l
p
和l
q
的移动方向之差。在一个例子中，用户在某个位置点的移动 方向，可以根据该位置点与其对应轨迹中的相邻后一位置点的连线和水平线的夹角来 确定。
[0151]
在不同的实施例中，也可以使用粒度相似度、方向相似度和语义相似度的其他组 合，确定目标位置点与第一位置集合中各个位置点的其他综合相似度，进而利用该综 合相似度，确定出第二位置集合。因此，在一个实施例中，还可以通过如下步骤确定 出第二位置集合：根据所述目标位置点与所述第一位置集合中各个位置点的粒度相似 度、方向相似度和语义相似度，确定所述目标位置点与该各个位置点的第三综合相似 度；根据所述第三综合相似度，从所述第一位置集合中，确定出所述第二位置集合。
[0152]
最后，在步骤26，利用所述多个真实位置点各自对应的若干替代位置点，生成若 干个合成轨迹。
[0153]
该步骤中，利用步骤25得到的各真实位置点对应的替代位置点，生成合成轨迹。 图5示出根据本说明书实施例的生成合成轨迹的示意图。如图5所示的实施例中，其中 的实线表示的真实轨迹由位置a、b、c、d和e组成。其中，类簇1中有k(k＝2)个 虚假位置a1和a2用于伪装为位置a。真实轨迹中a和位置b之间的距离，代表b相 对于a的粒度(即用户在b点的速度)。它们的连线和水平方向之间的角度代表用户 在a的运动方向。然后，根据类簇2中各个候选位置点与a，a1和a2之间的粒度相似 度和运动方向，分别选择b1和b2作为合成轨迹1和2上与b对应的虚假位置。重复 此操作以获得c1、c2、d1、d2和e1、e2，从而生成两条完整的合成轨迹。
[0154]
在一个实施例中，还可以将合成轨迹和真实轨迹，共同提供给用户。
[0155]
将合成轨迹和真实轨迹一同提供给用户，由于合成轨迹中的虚假位置，在语义信息、 移动幅度和运动方向上，与真实轨迹中的位置均十分相似，因此攻击者即使掌握一定的背 景知识，也很难从中分辨出真实轨迹，因此具有降低用户隐私泄露的风险的作用。并且， 由于合成轨迹上的虚假位置点是历史轨迹数据集中真实存在的，所以合成轨迹和历史 轨迹具有相似的统计特性，这种相似性也会导致攻击者的识别难度提高。
[0156]
上面描述了本说明书实施例提供一种用户轨迹的隐私保护方法。本说明书另一方
面 的实施例，还提供一种用户轨迹的隐私保护装置。图6示出根据本说明书实施例的一种 用户轨迹的隐私保护装置的结构图。如图6所示，该装置600包括：
[0157]
真实轨迹获取单元61，配置为，获取用户当前的真实轨迹，其中包括多个真实位 置点；
[0158]
位置类簇获取单元62，配置为，获取多个位置类簇，所述多个位置类簇根据用户 历史轨迹集合中的多个历史位置点的位置语义，对所述多个历史位置点进行聚合处理 而得到；
[0159]
目标类簇匹配单元63，配置为，对于所述多个真实位置点中任意的目标位置点， 从所述多个位置类簇中确定所述目标位置点对应的目标类簇；
[0160]
候选位置确定单元64，配置为，根据目标位置点的位置语义，从所述目标类簇中 确定出若干候选位置点；
[0161]
替代位置确定单元65，配置为，根据用户在所述目标位置点的移动状态，从所述 若干候选位置点中确定出该目标位置点的若干替代位置点；
[0162]
合成轨迹生成单元66，配置为，利用所述多个真实位置点各自对应的若干替代位 置点，生成若干个合成轨迹。
[0163]
在一个实施例中，该装置600还可以包括，输出模块，配置为，将所述合成轨迹 和所述真实轨迹，共同提供给用户。
[0164]
本说明书又一方面提供一种计算机可读存储介质，其上存储有计算机程序，当所 述计算机程序在计算机中执行时，令计算机执行上述任一项方法。
[0165]
本说明书再一方面提供一种计算设备，包括存储器和处理器，所述存储器中存储 有可执行代码，所述处理器执行所述可执行代码时，实现上述任一项方法。
[0166]
需要理解，本文中的“第一”，“第二”等描述，仅仅为了描述的简单而对相似 概念进行区分，并不具有其他限定作用。
[0167]
本领域技术人员应该可以意识到，在上述一个或多个示例中，本发明所描述的功 能可以用硬件、软件、固件或它们的任意组合来实现。当使用软件实现时，可以将这 些功能存储在计算机可读介质中或者作为计算机可读介质上的一个或多个指令或代码 进行传输。
[0168]
以上所述的具体实施方式，对本发明的目的、技术方案和有益效果进行了进一步详 细说明，所应理解的是，以上所述仅为本发明的具体实施方式而已，并不用于限定本发明 的保护范围，凡在本发明的技术方案的基础之上，所做的任何修改、等同替换、改进等， 均应包括在本发明的保护范围之内。