(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210566453.5 (22)申请日 2022.05.25 (71)申请人 江苏师范大学 地址 221116 江苏省徐州市铜山 新区 (72)发明人 王娜娜　 (51)Int.Cl. G06F 21/62(2013.01) G06N 7/00(2006.01) (54)发明名称 满足差分隐私的轨 迹发布方法 (57)摘要 本发明提出一种满足差分隐私的轨迹发布 方法， 该方法将原始轨迹表示为相邻网格的锚点 轨迹， 利用前缀树和马尔科夫过程为其构建模 型， 通过在前缀树和马尔科夫过程的转移矩阵中 添加拉普拉斯噪声以满足差分隐私， 然后从含噪 声的模型中生成待发布的轨迹数据。 一方面， 本 发明利用前缀树和马尔科夫过程为锚点轨迹建 模， 能保持更多的原始数据特征， 获得较高的数 据可用性； 另 一方面， 本发明为前缀树和马尔科 夫过程的转移矩 阵设计了添加拉普拉斯噪声的 方法， 满足差分隐私， 能够保护轨迹数据的隐私， 是一种保障轨迹数据的安全可靠发布和应用的 实用算法。 权利要求书3页 说明书5页 附图1页 CN 114925396 A 2022.08.19 CN 114925396 A 1.一种满足差分隐私的轨 迹发布方法， 其特 征在于： (1)生成锚点轨 迹； 将轨迹数据集所在空间范围划分为若干网格， 每个网格的中心点称为一个锚点， 将轨 迹数据映射 为相邻网格的锚点序列， 生成锚点轨 迹； 假设轨迹数据集D＝{Tri|i＝0,1, …,|D|‑1}由|D|条轨迹组成， |D|表示该轨迹数据集D 的轨迹数目， 为轨迹数据集D的第i条轨迹， 其包含t个采样点， 为Tri的第j个采样点， 和 分别为采样点 的经度和 纬度； 将轨迹数据集D的每个轨迹的采样点均映射为锚点； 将锚点轨迹数据集记为 为轨迹Tri对应的锚点轨迹， |Dc|为锚点轨迹数据集Dc 的轨迹数目； 若轨迹 中相邻的锚点位于非相邻的网格 中， 则通过插值的方法， 使得锚点轨 迹 中相邻的锚点均为相邻网格的锚点； 向轨迹 末尾添加轨迹结束标志； 将锚点轨迹 记 为 为 的第j个元素(锚点或轨迹结束标志)， 为轨迹 中元 素的个数； (2)构造前缀 树并添加噪声； 将步骤(1)中锚点轨迹数据集Dc的轨迹依据相同前缀进行分组， 构造前缀树PT， 并向其 添加拉普拉斯噪声， 以满足差分隐私； (3)构造马尔科 夫过程转移矩阵并添加噪声； 依据步骤(1)中锚点轨 迹数据集Dc， 构造马尔科 夫过程转移矩阵Q， 以满足差分隐私； (4)生成待发的布轨 迹数据； 利用步骤(2)构造的前缀树PT和步骤(3)构造的马尔科夫过程转移矩阵Q， 生成待发布 轨迹数据。 2.根据权利要求1所述的一种 满足差分隐私的轨迹发布方法， 其特征在于： 将轨迹数据 集D的每个轨迹的采样点映射 为锚点， 具体步骤如下： (1.1)将轨迹数据集D所在空间范围记为矩形R， 该矩形R左下顶点和右上顶点坐标分别 记为(left,b ottom)和(right,b ottom)； 将矩形R划分为uh×uw个网格， uh为网格的行数， uw 为网格的列数； 将网格 集合记为Cell＝{celli,j|i＝0,1, …,uh‑1,j＝0,1, …,uw‑1},celli,j 为第i行第j列的网格； 将网格celli,j的锚点记为ci,j， 锚点集合记为AP＝{ci,j|i＝0,1, …, uh‑1,j＝0,1, …,uw‑1}； (1.2)假设轨迹采样点 位于网格cellrow,col,row＝0,1, …,uh‑1,col＝0, 1,…,uw‑1， 则row和col的计算方法如下： 锚点crow,col为轨迹采样点 映射的锚点。 3.根据权利要求1所述的一种满足差分隐私的轨迹发布方法， 其特征在于： 定义前缀 为： 假设S＝p0p1…p|s|‑1为含有|S|个锚点的序列， pi(i＝1,2, …,|S|‑1)为S的第i个锚点,S ′权　利　要　求　书 1/3 页 2 CN 114925396 A 2＝p0′p1′ …p|s′|‑1′为含有|S ′|个锚点的序列， 当且仅当|S ′|≤|S|且 p′i＝pi 时， S′为S的前缀。 4.根据权利要求1所述的一种 满足差分隐私的轨迹发布方法， 其特征在于： 定义前缀树 为： 将待生成的前缀树记 为PT＝(V,E,Root)， 其中， V为前缀树PT的结点集合， 每个结点都与 一个前缀相关联， 并保存着该前缀的计数； E为前缀树PT的边集合， 表 示结点间的连接 关系， Root为前缀树PT的虚拟根结点； 假设结点v为前缀树PT的一个结点， 将与其关联的前缀记 为 prefix(v,P T)； 每个结点v∈V都保存一个二元组(tr(v),c(v))， 其中tr(v)表示锚点轨迹数 据集Dc前缀为pr efix(v,PT)的轨迹集合， 其数目为|tr(v)|； c(v)表示添加噪声后的|tr(v) |； 将PT的高度记为h， 虚拟根结点Ro ot位于PT的第0层， 最高层为第h ‑1层。 5.根据权利要求1所述的一种 满足差分隐私的轨迹发布方法， 其特征在于： 将锚点轨迹 数据集Dc的轨迹依据相同前缀进行分组， 构造前缀树PT， 并向其添加拉普拉斯噪声， 具体步 骤如下： (2.1)构建空前缀 树PT； (2.2)在前缀 树PT的第1层， 为锚点 集合AP的每 个锚点生成一个结点； (2.3)按照如下公式， 为第i(i ＝1,2,…,h‑1)层的每 个结点v∈V计算 其c(v)， c(v)＝|t r(v)|+Lap(1/ εp,i)， 其中， δ为可调参数， εp(0<εp<1)为分配给前缀树PT构造过程的隐 私预算， εp,i为分配给前缀树PT第i层结点的隐私预算， Lap(1/εp,i)为服从拉普拉斯分布的 随机数， 该拉普拉斯分布的密度函数为 若c(v)>1， 则不为该结点v生成子结点； 否则， 依据其关联前缀prefix(v,PT)末尾锚点 的相邻网格的锚点和轨 迹结束标志， 为结点v生成子结点； (2.4)重复步骤(2.3)直至前缀 树PT达到最大高度h； (2.5)将c(Root)置为|D|， 按照从顶至下的顺序， 利用如下公式， 为前缀树PT第i(i＝1, 2,…,h‑1)层的每 个结点v∈V更新 其c(v)， 其中， par(v)为结点v的父 结点， children(par(v) )为par(v)的子结点 集合。 6.根据权利要求1所述的一种满足差分隐私的轨迹发布方法， 其特征在于： 将长度为m 的锚点序列称为m ‑gram； 锚点轨迹数据集Dc每个m‑gram均由相邻网格的锚点构成； 将锚点 轨迹数据集Dc不同m‑gram的数目记为Fr。 7.根据权利要求1所述的一种 满足差分隐私的轨迹发布方法， 其特征在于： 依据锚点轨 迹数据集Dc， 构造马尔科 夫过程转移矩阵Q， 具体步骤为： (3.1)初始化矩阵FM和 FM＝{FMk,j＝0|k＝0,1, …,Fr‑1,j＝0,1, …,uh×uw}， 其中， FMk,j为矩阵FM第k行第j列的元素； 为矩阵 第k行第j列的元素； 矩阵FM每一行均与一个m ‑gram对应， 每一列均与一个锚点或 轨迹结束标志对应； 假设rk为矩阵FM第k行对应的m ‑gram， nj为矩阵FM第j列对 应的锚点或轨 迹结束标志， 则rknj为连接rk和nj得到的(m+1) ‑gram， 元素FMk,j用于存储rknj在锚点轨迹数权　利　要　求　书 2/3 页 3 CN 114925396 A 3