车联网用户在使用基于位置的服务^[1]应用时会生成大量的轨迹数据，直接发布会引起严重的隐私泄露问题^[2-3]. k-匿名^[4]、l-多样性^[5]和t-近邻性^[6]技术通过将数据匿名化实现隐私保护，但无法抵御组合攻击、同质攻击、背景知识攻击等窃取隐私的方法. Dwork^[7]提出差分隐私（differential privacy，DP）技术，在数据中加入适量的噪声以实现隐私保护，可以抵御背景知识攻击. 若噪声添加过多，则会降低数据的可用性. Cheng等^[8]提出个性化轨迹聚类和差分隐私保护机制，在数据效用方面有一定的提升，但未考虑轨迹属性中的时空特征. 本文引入时间图卷积网络（temporal graph convolutional network，T-GCN）模型，在涉及复杂空间的结构中，能够充分提取轨迹的时空特征，在隐私保护中能够实现隐私预算的合理分配.

针对大多数聚类质量损失数据的问题，Cai等^[9]提出利用DBSCAN聚类的轨迹发布DPTD的机制，能够保护多数轨迹的隐私. Zhang等^[10]提出LGAN-DP算法，利用深度学习方法合成轨迹，使用k-means聚类对轨迹结果集进行处理，提高了数据的私密性. k-means、DBSCAN聚类高度依赖用户指定的参数，性能不够稳定. Guan等^[11]提出基于稳定隶属度的自动调优多峰值聚类SMMP算法，解决了参数调优问题，但只能应用在低维空间. 本文提出改进的稳定隶属度多峰值聚类(Improved stable-membership multi-peak clustering，ISMMPC)算法，可以自动调整聚类阈值，开展多原型聚类，解决多维度中应用的问题.

Kim等^[12]提出DPGeo框架，在对抗自编码器中使用DP收集的扰动数据集训练轨迹生成，局限性是轨迹精度级别不高于网格表示级别. 晏燕等^[13]提出时空长短期记忆模型，通过添加拉普拉斯噪声预测位置的结构,缺点是提供的隐私预算不够精确. 康海燕等^[14]使用基于时空密度聚类的轨迹预测隐马尔可夫模型，通过分析时空的相关性，预测时空序列数据的不同分布，但仅适用于平滑数据，无法捕捉轨迹中隐藏的非线性特征. 本文结合T-GCN模型与DP技术，既能够精确预测隐私预算，又能够对轨迹中隐藏的线性和非线性特征进行探索.

本文设计基于聚类和深度学习的轨迹隐私保护机制（trajectory privacy protection mechanism based on clustering and deep learning，PPCDL）. 考虑轨迹空间的时空特征，分析通过时间戳划分轨迹区域带来的数据稀疏性对轨迹隐私保护的影响，设计ISMMPC算法和T-GCN模型，提高隐私保护的效果和轨迹数据的可用性.

定义1 　网格图 $G$. $ G = \left( {V,E} \right) $， $E$为边的集合， $ V = \left\{ {{V_1},{V_2},\cdots,{V_{n \times n}}} \right\} $为网格位置上的节点， $n \times n$为网格区域位置的个数.

定义2 　特征矩阵 ${\boldsymbol{X}}$. 将网格上的轨迹信息作为网格中节点的属性特征，构成特征矩阵 ${\boldsymbol{X}}$. $ {{\boldsymbol{X}}_{{t_g}}} $表示 ${t_g}$时的轨迹信息， ${t_g}$为第g个时间戳.

时空轨迹是在 $G$和 ${\boldsymbol{X}}$下学习映射函数 $F$得到的 ${t_g}$时的轨迹数据，可以表示为

(1) $ \left[ {{{\boldsymbol{X}}_{{t_g}+1}},\cdots,{{\boldsymbol{X}}_{{t_g}+T}}} \right] = F\left( {G;\left( {{{\boldsymbol{X}}_{{t_g} - m}},\cdots,{{\boldsymbol{X}}_{{t_g} - 1}},{{\boldsymbol{X}}_{{t_g}}}} \right)} \right). $

式中：m为历史时间序列长度， $T$为预测时间序列步长.

定义3 　总数矩阵 ${\boldsymbol{S}}$. 设 ${t_g}$划分后的区域为 ${A_g}$，根据 ${A_g}$进行划分得到n×n个网格区域，构造矩阵 ${\boldsymbol{S}}$记录 ${A_g}$的轨迹数. 矩阵元素 ${s_{ij}}\left( {i,j = 1,2,\cdots,n} \right)$为对应网格区域内的累计轨迹数，i、j为元素下标. ${\max _S}$为最大的 ${s_{ij}}$. ${\boldsymbol{S}}$可以表示为

(2) $ {\boldsymbol{S}} = \left[ {\begin{array}{*{20}{c}} {{s_{11}}}& \cdots &{{s_{1n}}} \\ \vdots & & \vdots \\ {s{}_{n1}}& \cdots &{{s_{nn}}} \end{array}} \right]. $

定义4 　密度矩阵 ${\boldsymbol{P}}$. 构造矩阵 ${\boldsymbol{P}}$表示 ${A_g}$的轨迹密度. 矩阵元素 $\;{\rho _{ij}}\left( {i,j = 1,2,\cdots,n} \right)$表示对应网格区域内轨迹的密度，其中 $\;{\rho _{ij}} = {{{s_{ij}}} /{{a_{{A_g}}}}}$，其中 ${a_{{A_g}}}$为 ${A_g}$的面积. ${\boldsymbol{P}}$可以表示为

(3) $ {\boldsymbol{P}} = \left[ {\begin{array}{*{20}{c}} {{\rho _{11}}}& \cdots &{{\rho _{1n}}} \\ \vdots & & \vdots \\ {\rho {}_{n1}}& \cdots &{{\rho _{nn}}} \end{array}} \right]. $

定义5 　隐私预算矩阵 ${\boldsymbol{E}}$. 构造矩阵 ${\boldsymbol{E}}$表示为 ${A_g}$分配的隐私预算，矩阵元素 ${\varepsilon _{ij}}\left( {i,j = 1,2,\cdots,n} \right)$表示对应网格区域内的隐私预算分配大小. ${\varepsilon _{ij}}$的初始值为0. ${\boldsymbol{E}}$可以表示为

(4) $ {\boldsymbol{E}} = \left[ {\begin{array}{*{20}{c}} {{\varepsilon _{11}}}& \cdots &{{\varepsilon _{1n}}} \\ \vdots & & \vdots \\ {\varepsilon {}_{n1}}& \cdots &{{\varepsilon _{nn}}} \end{array}} \right]. $

定义6 　 $\varepsilon $-差分隐私. 设有随机算法 $K$，所有可能输出构成的集合 $O$的概率为 $P[ \cdot ]$，对于任意2个相邻数据集 $D$和 ${D'}$，若2个相邻集合的概率分布满足

(5) $ P\left[ {K\left( D \right) \in {O_K}} \right] \leqslant {{\rm{e}}^\varepsilon } \times P\left[ {K\left( {D'} \right) \in {O_K}} \right], $

则称算法 $K$提供 $\varepsilon $-差分隐私保护. 算法 $K$满足 $\varepsilon $差分隐私， $P[ \cdot ]$表示隐私泄露的概率. $\varepsilon $表示隐私保护的程度， $\varepsilon \in(0,1.0) $.

定义7 　全局敏感度. 设函数 $f:D \to {{\bf{R}}^d}$，对于任意的相邻数据集 $D$和 ${D'}$，全局敏感度为

(6) $ \Delta f = {{\rm{max}} _{D,D'}}{\left\| {f\left( D \right) - f\left( {D'} \right)} \right\|_1}. $

式中： $d$为函数 $f$的查询维数， ${\left\| { \cdot } \right\|_1}$表示 ${L_1}$范数.

定义8 　拉普拉斯机制. 对于给定数据集 $D$，假设有函数 $f:D \to {{\bf{R}}^d}$，敏感度为 $\Delta f$，随机算法 $K\left( D \right) = f\left( D \right)+Y$提供 $\varepsilon $-差分隐私，其中噪声数量 $Y$服从拉普拉斯分布.

(7) $ Y\sim {\rm{Lap}}\left( {\frac{{\Delta f}}{\varepsilon }} \right). $

$Y$与 $\Delta f$成正比，与 $\varepsilon $成反比.

时间图卷积网络模型包括图卷积网络（GCN）和门控循环单元（GRU），如图1所示.

T-GCN使用m个时间序列数据作为输入，利用2层GCN模型进行图卷积操作，捕获路网区域位置复杂的拓扑结构，以学习空间特征. 将得到的具有空间特征的时间序列输入到GRU模型中，通过单元间的信息传递获得动态变化，捕获时间特征. T-GCN可以充分学习时空依赖性，实现轨迹预测. 具体可以表示为

(8) $ \left. \begin{gathered} F\left( {{\boldsymbol{M}},{\boldsymbol{X}}} \right) = \sigma \left( {\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{M}}} {{\rm{Relu}}}\left( {\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{M}}} {\boldsymbol{XW}}_0} \right){{\boldsymbol{W}}_0}} \right) , \\ {u_{{t_g}}} = \sigma \left( {{{\boldsymbol{W}}_u}\left[ {F\left( {{\boldsymbol{M}},{{\boldsymbol{X}}_{{t_g}}}} \right),{{\boldsymbol{h}}_{{t_g} - 1}}} \right]+{{\boldsymbol{b}}_u}} \right) , \\ {r_{{t_g}}} = \sigma \left( {{{\boldsymbol{W}}_r}\left[ {F\left( {{\boldsymbol{M}},{{\boldsymbol{X}}_{{t_g}}}} \right),{{\boldsymbol{h}}_{{t_g} - 1}}} \right]+{{\boldsymbol{b}}_r}} \right) , \\ {{\boldsymbol{c}}_{{t_g}}} = \tanh \left( {{{\boldsymbol{W}}_c}\left[ {F\left( {{\boldsymbol{M}},{{\boldsymbol{X}}_{{t_g}}}} \right),\left( {{r_{{t_g}}} {{\boldsymbol{h}}_{{t_g} - 1}}} \right)} \right]+{{\boldsymbol{b}}_c}} \right) , \\ {{\boldsymbol{h}}_{{t_g}}} = {u_{{t_g}}} {{\boldsymbol{h}}_{{t_g} - 1}}+\left( {1 - {u_{{t_g}}}} \right) {{\boldsymbol{c}}_{{t_g}}} . \\ \end{gathered} \right\} $

式中： $F( \cdot )$为图卷积过程； $\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{M}}} $为拉普拉斯矩阵归一化， $\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{M}}} = {\tilde {\boldsymbol{U}}^{ - \frac{1}{2}}}\tilde {\boldsymbol{M}}{\tilde {\boldsymbol{U}}^{ - \frac{1}{2}}}$，其中 $\widetilde {\boldsymbol{M}} $为拉普拉斯矩阵， $\widetilde{{\boldsymbol{M}}} = {\boldsymbol{M}}+ {{\boldsymbol{I}}_{N\times N}}$； $\tilde {\boldsymbol{U}}$为图中与该节点相连边的数量的矩阵； ${{\boldsymbol{W}}_0}$和 ${{\boldsymbol{W}}_1}$为权重矩阵； ${{\boldsymbol{h}}_{{t_g}}}$和 ${{\boldsymbol{c}}_{{t_g}}}$为 ${t_g}$时输出和存储的数据信息； ${r_{{t_g}}}$和 ${u_{{t_g}}}$为 ${t_g}$时的复位门和更新门结果； $\sigma、{\rm{Relu}}、 \tanh$为激活函数.

车联网中许多保护轨迹数据的方法会忽略轨迹的时空特征. 地理空间的限制及时间序列上位置的相关性，使得攻击者有较大可能推断出用户的真实敏感位置和轨迹信息. 实际上，大多数的轨迹隐私保护机制只考虑单个位置点的隐私保护，忽略了连续位置点对轨迹隐私保护的影响. 这会使得攻击者很容易推断出2个位置点之间的地理位置关系，推断出用户经过或停留的位置点，导致用户的位置或轨迹隐私泄露. 轨迹中的位置是时间相关的，引入时间戳，用于获得不同时间的轨迹位置分布，探究位置之间的某种相关性及用户的行为模式. 时间戳的引入会使得轨迹数据变得稀疏，难以承受注入的噪声，降低了数据价值. 引入ISMMPC聚类，以减小时间戳导致的数据稀疏性. ISMMPC在对轨迹数据聚类的同时，保留了时间特征和空间特征. 根据聚类后的轨迹区域密度进行隐私预算预分配，形成隐私预算矩阵. 基于时间图卷积网络模型，对隐私预算矩阵进行预测. 在T-GCN模型的训练过程中，不断优化隐私预算的分配，在对数据减少注入噪声的同时，保护了轨迹数据的隐私安全.

ISMMPC算法在时间戳划分后的区域实现聚类，捕获轨迹的位置分布. 根据轨迹的分布情况，形成任意形状和数量的子簇，无须预先确定聚类的子簇量. 图2给出ISMMPC聚类过程. 图中，n为子簇数量.

算法中的隶属度是聚类函数 $Q\left( {\delta ,\xi } \right)$，它以数据集 $\delta $和相似函数 $\xi $作为输入，返回描述为 ${\boldsymbol{\chi}} \in {{\bf{R}}^{n \times n}}$的隶属度逻辑矩阵结果. 其中，元素 ${z_{ij}} = 1$表示点 ${x_i}$和 ${x_j}$是同一聚类中的成员. 假设 ${x_i}$和 ${x_j}$的相似值为 ${v_\xi } = \xi \left( {{x_i},{x_j}} \right)$，设置聚类阈值 $\theta = {I_\theta } \subseteq \left[ {\min {{v_\xi }} , \max {{v_\xi }} } \right]$，其中 $ {I}_{\theta } $为聚类阈值 $ \theta $的范围. 若 $ \theta $超过Q的范围，使得 $ {v}_{\xi }\geqslant \theta $，则元素 ${z_{ij}} = 1$. 此时聚类函数可以拥有一致性的属性，衡量聚类的稳定性. 由 $ \theta $的范围给出假设：根据 ${x_i}$和 ${x_j}$的相似性，当改变 $ \theta $时，合理的聚类应该具有相对稳定的隶属度，因此设置 $ \theta $为

${I_\theta } = {\rm{mean}}\left( {I_\theta ^*} \right)，I_\theta ^* \to \left( {\mathop {\max }\limits_{{z_{ij}} = 0} {v_\xi },\mathop {\min }\limits_{{z_{ij}} = 1} {v_\xi }} \right).$

其中 $ {I}_{\theta }^{*} $为最优阈值子区间.

ISMMPC算法利用密度峰值聚类技术^[15]获取区域 $ {A_g} $的密度峰值集合，选取最高的密度峰值作为中心点，将中心点周围未分配的数据点分配到同一聚类中形成子簇 $\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{{C}}}$. 在所有数据点分配完成后，使用边界链接的连通性来评估 $\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{{C}}}$的内聚性. 在跨簇的边界点中，将未链接的边界点 ${\tau _i}$和最近未链接的跨簇边界点 ${\tau _j}$关联起来，作为边界链接 ${b_{li}} = \left\{ {{\tau _i},{\tau _j}} \right\}$，判断集群内聚性. 赋予每个边界点一个特定值 $\gamma \left( {\gamma \in \left[ {0,1.0} \right]} \right)$，定量评估子簇间的相邻关联度. 若高相似度的子簇链接良好，则表示具有多个高 $\gamma $值的边界链接. 采用马氏距离评价子簇之间的相似性，距离越近越相似. 马氏距离 ${D_{{\rm{ma}}}}$可以表示为

(9) $ {D_{{\rm{ma}}}}\left( {{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_i},{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_j}} \right) = \sqrt {{{\left( {{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_i} - {{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_j}} \right)}^{\rm{T}}}{{\boldsymbol{W}}_\gamma }^{ - 1}\left( {{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_i} - {{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_j}} \right)} . $

式中： ${{\boldsymbol{W}}_\gamma }$为特征值的权重.

用 ${n_\gamma }$表示所有边界链接数量， $\varGamma \left( {{D_{{\rm{ma}}}}} \right)$返回所有 ${D_{{\rm{ma}}}}$值与 ${D_{{\rm{ma}}}}$最大值的均一度，可以表示为

(10) $ \varGamma \left( {{D_{{\rm{ma}}}}} \right) = 1 - \dfrac{{{{{n_\gamma }^{-1}}}\displaystyle\sum\nolimits_{i = 1}^{{n_\gamma }} {\left| {{D_{{\rm{ma}}}}_{_i} - \max \left( {{D_{{\rm{ma}}}}\left( {{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_i},{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_j}} \right)} \right)} \right|} }}{{\max \left( {{D_{{\rm{ma}}}}\left( {{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_i},{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_j}} \right)} \right)}}. $

对于2个相交的子簇，若所有边界链接样本的特定值几乎一样大，则它们是高相似的. 根据式(11)可知，相似矩阵中 $\left( {{x_i},{x_j}} \right)$元素为相似值 $\xi \left( {{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_i},{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_j}} \right)$. 在得到子簇的相似矩阵 ${{\boldsymbol{\xi}} _{\rm{m}}} \in {{\bf{R}}^{n \times n}}$后，根据子簇间的相似性，将子簇 $\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{{C}}}$合并为最终的簇C.

(11) $ \begin{split} \\ \xi \left( {{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_i},{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_j}} \right) = \max \left( {{D_{{\rm{ma}}}}\left( {{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_i},{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_j}} \right)} \right) \times \varGamma \left( {{D_{{\rm{ma}}}}\left( {{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_i},{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_j}} \right)} \right). \end{split} $

算法1给出ISMMPC聚类的实现过程.

算法1 　ISMMPC聚类算法的实现

输入：数据轨迹集 $\left\{{{\boldsymbol{X}}}_{{t}_{g}+1},\cdots ,{{\boldsymbol{X}}}_{{t}_{g}+T}\right\}$

输出：聚类结果集C

1）获得 $\left\{ {{{\boldsymbol{X}}_{{t_g}+1}}, \cdots ,{{\boldsymbol{X}}_{{t_g}+T}}} \right\}$和 $k = \left\lceil {\sqrt{{t_g}+T} } \right\rceil $

2） ${I_k} = \left\{ {1,2,\cdots ,k} \right\},\;{\rm{gap}} = \left\lceil {\dfrac{{{\rm{range}}\left( {{I_k}} \right)}}{{20}}} \right\rceil$

3） for $k = \min {{I_k}} :{\rm{gap}}:\max {I{}_k} $

4）计算每个区域的密度 $\rho $

5）end for

6） for ${x_i} \in \left\{ {{{\boldsymbol{X}}_{{t_g}+1}}, \cdots ,{{\boldsymbol{X}}_{{t_g}+T}}} \right\}$

7） ${P_k} = \max \;\rho$， ${\gamma _i} = 1$ || ${P_k}$是密度峰值

8）end for

9） if $ \;{\rho _j} > {\rho _i} $ || 进行子簇间的关联度度量

10） ${\gamma _i} \leftarrow {\gamma _j} {{{\rho _i}} / {{\rho _j}}}$

11） end if

12） 具有相同 $\gamma $的点形成子聚类 $\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{{C}}} $

13） for 每对密度峰 ${\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} _i},\;{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} _j} \in \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{{C}}} $

14 ） 根据式（9）计算 ${D_{{\rm{ma}}}}$

15） 计算相似性 $\xi \left( {{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_i},{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_j}} \right)$

16） end for

17） ${I_\theta } \leftarrow \left[ {\min \left( {\xi \left( {{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_i},{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_j}} \right)} \right),\max \left( {\xi \left( {{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_i},{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{\boldsymbol{C}}} }_j}} \right)} \right)} \right] \subseteq \left[ {0,1.0} \right]$

18） for $\theta = \min {{I_\theta }} :{\rm{gap}}:\max {I{}_\theta } $ || gap是迭代步长

19） 统计聚类数量 count

20） end for

21）自动调整θ = mean ( $I_\theta ^*$)

22）自适应合并子簇 $ {{C}}\leftarrow\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{{{C}}} $

23） return 聚类结果 ${{C}} = \left\{ {{{\boldsymbol{C}}_1},{{\boldsymbol{C}}_2}, \cdots ,{{\boldsymbol{C}}_{{\rm{count}}}}} \right\}$

第1行是获取数据集. 第2~8行是开展每一点的k个周围点的选取，时间复杂度为O( $n\tilde k$)， $\tilde k$表示平均k个点的最近高密度点. 得到每个区域的密度峰值及子簇数量，时间复杂度为O(n). 第9~11行是显示边界链接特定值的计算，定量评估子簇间的关联度，复杂度为O( $n{k_{\rm{b}}}$)，其中k_b = min {k/2, 2ln n}. 第12~16行是计算马氏距离和估计子簇间的相似性，时间复杂度为O(n²). 第17~23行是对子簇的自适应合并，得到聚类结果集C，时间复杂度为O(n²). ISMMPC聚类的总时间复杂度为O( $n\left( {\tilde k+{k_{\rm{b}}}} \right)+{n^2}$).

图3给出T-GCN组成结构，T-GCN模型可以从交通数据中学习空间特征. GRU以 ${{\boldsymbol{h}}_{{t_g} - 1}}$和当前的流量信息作为输入，得到 ${t_g}$时的流量信息. 该模型在捕获当前时刻的交通信息的同时，保留历史交通信息的变化趋势. 假设节点5为某轨迹点，利用GCN模型可以得到该轨迹点与周围轨迹点之间的拓扑关系，对路网拓扑结构和轨迹上的属性进行编码，得到空间依赖关系. 对节点的特征矩阵进行图卷积操作，再将结果输入GRU中提取时序上的特征.

将通过时间戳划分获得的每个区域的轨迹数据输入到T-GCN模型中. 在空间依赖关系和时序特征的作用下，由定义1、2得到区域轨迹的时空信息 $\left[ {{{\boldsymbol{X}}_{{t_g}+1}},\cdots,{{\boldsymbol{X}}_{{t_g}+T}}} \right]$. 将信息作为ISMMPC聚类的输入，重新形成轨迹数据集 $C$. 通过 $C$得出每个区域的总数矩阵集 $\left\{{{\boldsymbol{S}}}_{ij}|i=1,\cdots ,x;j=1,\cdots ,y\right\}$. 由定义4得到区域的局部密度 ${\rho _i}$，按照密度自上而下对区域进行排序，得到相应的密度矩阵集合 $\{ {{\boldsymbol{P}}_{ij}}|i = 1, \cdots , x;j = 1, \cdots ,y \}$. 按照式（12）进行隐私预算预分配，得到隐私预算矩阵集合 $\left\{ {{{\boldsymbol{E}}_{ij}}|i = 1, \cdots ,x;j = 1, \cdots ,y} \right\}$.

根据差分隐私的定义，对于密集区域， $\varepsilon_{ij} $期望分配较小的数值. 对于稀疏区域， $\varepsilon_{ij}$期望分配较大的数值. 隐私预算分配公式为

(12) $ {\varepsilon _{ij}} = \frac{{{\alpha _{ij}}}}{{\displaystyle\sum\nolimits_{i = 1}^x {\displaystyle\sum\nolimits_{j = 1}^y {{\alpha _{ij}}} } }}\varepsilon . $

式中： ${\alpha _{ij}} = {{ij\left( {ij+1} \right)}}/{2}$， $\varepsilon $为总隐私预算.

结合T-GCN模型提取数据的时间和空间特征，预测隐私预算矩阵 ${{\boldsymbol{E}}}_{ij}^{}$，图4给出T-GCN模型的时空预测过程. 将获得的初始隐私预算矩阵 ${\boldsymbol{E}}_{ij}^{}$按时间顺序组织为时空序列矩阵集合 ${\boldsymbol{J}}_{ij}$. 将时空数据 ${\boldsymbol{J}}_{ij}$输入到深度学习模型中，不断地进行T-GCN小单元的学习、训练，预测最终的隐私预算矩阵 ${\boldsymbol{E}}_{ij}^{'}$. 根据 ${\boldsymbol{E}}_{ij}^{'}$在每个总数矩阵 ${{\boldsymbol{S}}_{ij}}$中按照式（13）计算得到相应的拉普拉斯噪声 $N_{ij}^*$. 将 $ {N}_{ij}^{*} $添加到每个区域的轨迹信息中，对扰动后的轨迹数据进行发布.

(13) $ {N}_{ij}^{*}={\rm{Lap}}\left(\frac{{\mathrm{max}}_{S}}{{\varepsilon }_{l}}\right),\;\;l\in \{1,\cdots,i\}. $

采用真实数据集Divvy Bikes和T-drive进行仿真实验，验证PPCDL的数据有效性、时间开销，评估差分隐私的保护效果.

T-GCN训练模型使用Adam优化器进行训练，激活函数为Elu. 对于输入层，将数据集的80%数据作为输入，其余数据作为测试过程的输入. 将PPCDL与DPTD^[9]、LGAN-DP^[10]、DPGeo^[12]进行对比分析. Divvy Bikes数据集包含了芝加哥生活中的共享单车自2015年至2020年骑行使用的数据，其中有每次骑行的起始点和时间戳、起始时间、起始经纬度等. T-drive数据集包含北京市出租车的轨迹总距离约为900万km，位置点超过1 500万个，轨迹数据由每辆出租车的ID、时间戳、经度和纬度信息表示的GPS位置点序列组成. 在实验预处理中，数据集选用轨迹密度相对较大的区域.

隐私保护的目的是发布有用信息，同时隐藏敏感的信息. 当进行隐私保护时，既要保护用户的隐私安全，又要保证用户享受到较高的服务质量. 采用3种度量方法，量化原始数据和发布数据之间的差异.

使用均方根误差(root mean square error，RMSE)，评估PPCDL的数据有效性. RMSE是衡量原始数据与发布数据间的差异，是评估发布数据准确性的常用方法. 设隐私预算矩阵的真实值为 ${\boldsymbol{E}}$，预测值为 $\widehat {\boldsymbol{E}}$，样本量为N，RMSE越小，预测越准确，则指标的公式为

(14) $ {\rm{RMSE}} = \sqrt {\frac{1}{N}\sum\nolimits_{n = 1}^N {{{({{{E}}_n} - {{\widehat {{E}}}_n})}^2}} } . $

使用查询误差（query error，QE），评估差分隐私的保护效果. 给定查询函数 $f$， $ f\left(A\right) $为查询区域 $ A $的正确结果，其中 $ \left|A\right| $为查询区域的大小. $ f\left(\tilde{A}\right) $为有噪声的查询结果，则查询错误定义为

(15) $ {\rm{QE}} = \frac{{\left| {f\left( A \right) - f\left( {\tilde A} \right)} \right|}}{{\max \left\{ {f\left( A \right),0.01 \left| A \right|} \right\}}}. $

使用JS(Jensen-Shannon divergence)散度，评估真实轨迹和加噪后轨迹间的相似性. 给定已发布的原始数据和加噪数据的概率分布函数 $\phi $、 $\varpi $， ${\varphi _i}$、 ${\omega _i}$为函数 $\phi $和 $\varpi $的概率，则JS散度定义为

(16) $ \begin{split} {\rm{JS}}\left( {\phi \|\varpi } \right) = &\frac{1}{2}\sum\nolimits_{i = 1}^n {{\varphi _i}} \ln \frac{{{\varphi _i}}}{{{\varphi _i}+{\omega _i}}}+ \\ & \frac{1}{2}\sum\nolimits_{i = 1}^n {{\omega _i}} \ln \frac{{{\omega _i}}}{{{\varphi _i}+{\omega _i}}}+\ln 2. \end{split} $

为了验证轨迹数据集获得的隐私保护效果，使用T-GCN模型预测隐私预算矩阵，给定总隐私预算ε = {0.1, 0.3, 0.5, 0.7, 0.9}. 对原始轨迹数据和添加噪声的轨迹数据进行查询，得到测试数据的RMSE误差、QE误差和JS散度. 通过修改ε来评估不同总隐私预算下数据集的保护程度，实验结果如图5、6所示.

从图5(a) 可以看出，PPCDL的RMSE小于其他3个机制. 随着隐私预算的增加，RSME逐渐较小. 原因是 $\varepsilon $的增加使得注入数据中的噪声减少，数据可用性增加. PPCDL使用时空特征，利用T-GCN算法可以预测隐私预算矩阵，隐私预算矩阵不断迭代的过程使得预算在该轨迹区域有更合理的分配，较好地均衡了噪声误差和数据可用性. DPTD使用前缀树存储轨迹数据，随着轨迹序列长度的增大，前缀树节点不断增加，使得实用性变差. LGAN-DP和DPGeo都没有精确地提供隐私预算. 对比2个数据集的RSME结果可知，T-drive数据集上的RSME更小. 原因是在T-drive中选择的轨迹密度相对更大，T-drive中是北京市几个临近区域的出租车轨迹数据，Divvy Bikes中是芝加哥市公开的共享单车行程数据，相对而言，Divvy Bikes中的轨迹分布更加分散. PPCDL的隐私预算预分配是按密度分配的，因此稠密区域的拉普拉斯噪声比稀疏区域大，在合理的轨迹位置添加噪声，实现了个性化的隐私保护.

从图5(b)可以看出， $\varepsilon $的增加，减少了添加的拉普拉斯噪声，使得有噪声区域的查询结果逐渐向无噪声区域的查询结果趋近，所以QE减小. 对于按时间戳划分后的区域，进行聚类后的稠密区域的拉普拉斯噪声比稀疏区域大. 当使用数据计算平均查询误差时，QE随着噪声的增加而增大，降低了数据排序的一致性. PPCDL的优势是使用聚类和T-GCN算法可以更精确地预测隐私预算，合理地为轨迹数据添加拉普拉斯噪声，有效地实现差分隐私保护. 随着 $\varepsilon $的增加，PPCDL的QE变化慢的原因是在区域的隐私预算的预测训练过程中，训练分配的预算结果逐渐趋于稳定化，添加的噪声浮动变缓.

从图5(c)可以看出，2个数据集上的JS散度随着 $\varepsilon $的增加而减小，原始数据的概率分布和加噪数据的概率分布越来越相似. 这是因为随着 $\varepsilon $的增加，添加的噪声会逐渐减小，使得轨迹间的相似度增大. 较小的JS散度可以保证较强的隐私性，对真实位置引入较大的扰动. 相反，较大的JS散度通过向真实位置引入较小的噪声，保证较弱的隐私性. JS 散度结果表明，PPCDL 的数据可用性大于对比机制.

对T-drive数据集开展划分细粒度的实验. 在T-drive数据集上设置不同间隔的5个时间戳，设置相同的隐私预算，通过逐步加大时间戳的长度，查询当天的轨迹数据，得到指标的平均性能. 从图7可以看出，通过改变时间戳来验证划分对隐私保护的影响，PPCDL的RMSE误差、QE误差和JS散度都优于对比机制. 这是因为PPCDL合理地分配了隐私预算. 稠密区域的拉普拉斯噪声比稀疏区域大. 在每个位置合理添加噪声，实现了不同程度的隐私保护，提高了轨迹数据的可用性. 随着时间戳的不断增大，轨迹序列长度增大，RMSE误差呈现增大趋势，导致噪声不断增加，影响数据的可用性. 在时间戳延长到一定程度后，RSME减小，这是因为此时覆盖的轨迹序列长度比其他时间段大几倍，此时数据会受到非轨迹区域的噪声数据干扰，当计算平均指标时，RSME会减小. 对于QE误差来说，查询密集区域位置较容易实现，但加入的噪声量较大. 当计算QE误差时，QE随着噪声的增加而增大. 由于原始数据和发布数据的差异，JS散度随着噪声的增加而增大. 当JS散度较小时，表明该区域包含了大量不属于轨迹序列的位置.

为了验证PPCDL的效率，在数据集中将轨迹划分成不同数量的分组，在 $\varepsilon = 0.1$的情况下，将PPCDL与其他机制进行时间开销的对比，实验结果如图8所示. 图中，n_t为参与训练轨迹的组数，逐步递增；t为平均轨迹生成时间，每个值重复20次，取平均值. 随着参与者轨迹数据个数的不断增加，运行时间不断增大，更大的分组数意味着更复杂的集群过程，需要更多的时间，因此平均轨迹生成时间随着分组数量的增加而增大. PPCDL的运行时间相较于对比机制更短，得出结果的速度更快.

（1）在相同的隐私预算下，PPCDL的隐私预算利用率和发布的轨迹数据集的有效性均优于对比机制. 预测的隐私预算可以防止攻击者利用数据发布的时间差来获取真实的轨迹.

（2）在未来的工作中，将关注如何更好地对隐私预算初始化，以提升深度学习的训练速度，更好地实现车联网轨迹隐私保护.