(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210190712.9 (22)申请日 2022.02.28 (71)申请人 福建工程学院 地址 350118 福建省福州市闽侯县大 学新 区学府南路3 3号 (72)发明人 章静　李雁姿　林力伟　石思彤　 丁倩　邱浩宇　张廖如星 　 (74)专利代理 机构 福州元创专利商标代理有限 公司 35100 专利代理师 张灯灿　蔡学俊 (51)Int.Cl. G06F 21/62(2013.01) G06F 40/30(2020.01) G06K 9/62(2022.01) (54)发明名称 基于语义和预测的轨迹差分隐私保护方法 及系统 (57)摘要 本发明涉及一种基于语义和预测的轨迹差 分隐私保护方法及系统， 该方法包括： 语义敏感 度预处理： 根据距离和出入度将语义敏感位置的 语义敏感度分别辐射给附近节 点， 从而得到各位 置点的语义敏感度， 将用户在节 点的签到次数和 语义敏感度相结合作为节点的位置敏感度， 进而 确定各位置点的隐私级别； 然后根据轨迹集合以 及各位置点的位置敏感度和隐私级别构建前缀 树； 根据前缀树分配 隐私预算： 根据轨迹子序列 的平均敏感度分配轨迹子序列的隐私预算， 根据 位置点的隐私级别分配位置点的隐私预算； 通过 马尔科夫链调整隐私预算的分配； 根据隐私预算 添加噪声， 以改变位置的隐私级别， 进而保护用 户轨迹隐私。 该方法及系统有利于提高轨迹隐私 保护的效果。 权利要求书3页 说明书11页 附图5页 CN 114564747 A 2022.05.31 CN 114564747 A 1.一种基于语义和预测的轨 迹差分隐私保护方法， 其特 征在于， 包括以下步骤： 步骤S1、 对语义敏感度进行预处理： 根据距离和出入度将语义敏感位置的语义敏感度 分别辐射给附近节点， 从而得到各位置点的语义敏感度， 将用户在节点l的签到次数αl和语 义敏感度Seml相结合作为节点l的位置敏感度； 通过位置敏感度与预设的阈值之间的关系 确定各位置点的 隐私级别； 然后根据轨迹集合以及各位置点的位置敏感度和隐私级别构建 前缀树； 步骤S2、 根据前缀树分配隐私预算： 根据轨迹子序列的平均敏感度分配轨迹子序列的 隐私预算， 根据位置点的隐私级别分配位置点的隐私预算； 步骤S3、 调整隐私预算的分配： 通过马尔科夫链预测下一时刻的攻击概率， 并通过计算 概率来调整敏感度， 从而调整分配的隐私预算； 步骤S4、 根据隐私预算添加噪声， 以改变位置的隐私级别， 进 而保护用户轨 迹隐私。 2.根据权利要求1所述的基于语义和预测的轨迹差分隐私保护方法， 其特征在于， 所述 步骤S1中， 考虑位置点之间的整体连通性， 根据距离和出入度将语义敏感位置的敏感度分 别辐射给附近节点， 具体为： 首先， 获取任意位置a附近具有隐私级别的语义位置节点集， 即连接集neighborSet； 然 后， 将地图转化为无向图， 根据距离和出入度， 则语义位置gi与任意位置a的等价距离为 gi.eDis＝ED(c ‑1)， 其中， ED为gi与a的欧氏距离， c为两位置节点之间最短路径所经过的节 点数， c‑1为两位置节点之间最短路径所包括的线段数； neighborSet＝{gi|gi.eDis<b}， 其 中b为用户设置的阈值； 最后， 求得任意位置a的连接集neighborSet中的语义位置gi辐射的语义敏感度， 如式 (1)所示： 其中， Sema表示节点a分配的语义敏感度。 3.根据权利要求2所述的基于语义和预测的轨迹差分隐私保护方法， 其特征在于， 为了 便于计算， 将地图网格化； 然后， 利用上述计算过程计算地图中各区域的语义敏感度， 生成 语义敏感度地图mapsen。 4.根据权利要求1所述的基于语义和预测的轨迹差分隐私保护方法， 其特征在于， 所述 步骤S2中， 根据位置点的敏感度和隐私级别来分配隐私预算； 对于签到频率高的位置， 敏感 度就高， 则隐私级别就高， 相应的分配的 隐私预算就少， 从而 添加更多的噪声来保护位置信 息； 所述步骤S2主要包括轨迹子序列的 隐私预算分配和轨迹子序列上每个子节点的隐私预 算分配， 具体为： 首先， 分别计算每条轨迹子序列的平均敏感度， 从而计算子序列的访问频 率； 然后根据访问频率为轨迹子序列分配隐私预算， 访问频率越高， 敏感度就越高， 分配的 隐私预算与访问频率成反比； 其次， 根据每条轨迹子序列上 的各个节点隐私级别所占该轨 迹子序列隐私级别总和的比重， 为每个节点分配隐私预算； 最后， 由于部 分位置点出现在多 个轨迹子序列中， 合并重复分配的隐私预算。 5.根据权利要求1所述的基于语义和预测的轨迹差分隐私保护方法， 其特征在于， 所述 步骤S3中， 利用马尔可夫链的性质来预测位置点的攻击概率， 马尔可夫链的性质对应到轨 迹中， 就是下一时刻的位置点仅依赖于前一时刻位置点， 从而获得下一时刻的可能位置集权　利　要　求　书 1/3 页 2 CN 114564747 A 2合及位置受攻击概 率， 进而调整隐私预算。 6.根据权利要求5所述的基于语义和预测的轨迹差分隐私保护方法， 其特征在于， 所述 马尔可夫链最重要的两个组成部分： 初始状态概率分布和状态转移概率矩阵； 假设用户在 t‑1时 刻 产生的 可能 位 置 集 为 其 概 率 值 为 此即为初始状态概率分布； 假定某一个用户的轨迹有n个可能的位 置， 即l1,l2,...,ln， 记从位置li转变为位置lj的状态转移概率为P(li→lj)， 则矩阵 即为状态转移概 率矩阵； 然后通过状态转移概率矩阵计算出t时刻的可能位置为 其概率值 为 其中P(t)＝P(t‑1)P， 即为t时刻的可能位置的攻击概 率； 假设攻击者的攻击从该轨迹的初始位置点开始， 并沿着该轨迹的方向继续； 利用马尔 可夫链的性质来计算前缀树上节点的攻击概率， 并通过计算概率来调整敏感度， 从而调整 分配的隐私预算。 7.根据权利要求1所述的基于语义和预测的轨迹差分隐私保护方法， 其特征在于， 所述 步骤S4中， 使用Laplace机制将对应的噪声添加到位置的敏感度中， 以改变位置的隐私级 别； 随着位置隐私级别的变化， 攻击者难以发现用户对位置的真正偏好。 8.根据权利要求7所述的基于语义和预测的轨迹差分隐私保护方法， 其特征在于， 在位 置隐私级别改变之后， 通过公式(2)计算用户u在位置l上的兴趣分数IGu,l； 其中， S'u,l和 w'score分别表示添加噪声后的位置敏感度和位置 评分权重： IGu,l＝S'u,l×w'score (2) 对IGu,l进行归一化处理， 得到归一化处理后的位置得分IGNu,l， 然后构造用户和位置的 评分矩阵Mat rixIGN， IGNu,l如下所示： 得到评分矩阵MatrixIGN后使用皮尔森相关系数计算用户的相似度sim(u,v)， 并构建用 户相似度矩阵Mat rixsim， sim(u,v)表示用户u和用户v之间的相似度； 其中， l(u,v)表示用户u和用户v的共同签到位置集， 表示用户u的平均位置得分； 最后， 根据用户相似度矩阵Matr ixsim将与目标用户相似度最高的n个用户作为相似用户； 并 且将相似用户的位置集中目标用户未访问的位置按得分降序排列， 取前n个位置推荐给目 标用户。 9.根据权利要求1所述的基于语义和预测的轨迹差分隐私保护方法， 其特征在于， 所述 步骤S4中， 利用LBS中的位置推荐算法来验证所述轨迹差分隐私保护方法对于轨迹隐私保 护的可行性和有效性。权　利　要　求　书 2/3 页 3 CN 114564747 A 3