[發明專利]一種滿足LKC模型的分類樹差分隱私保護方法

在審

• 申請號: 202011227876.1
• 申請日: 2020-11-06
• 公開（公告）號: CN112131608A
• 公開（公告）日: 2020-12-25
• 發明（設計）人: 李曉會;白雨靚;李波;伊華偉;賈旭;李銳
• 申請（專利權）人: 遼寧工業大學
• 主分類號: G06F21/62
• 分類號: G06F21/62;G06F16/906;G06F16/29
• 代理公司: 北京遠大卓悅知識產權代理有限公司 11369
• 代理人: 劉小嬌

1.一種滿足LKC模型的分類樹差分隱私保護方法，其特征在于，包括如下步驟：

步驟1、根據待發布數據確定需要全局抑制的序列集合；

步驟2、根據所述序列集合中的軌跡數據計算新產生的最小違反序列；

其中，當產生新的最小違反序列時，舍棄所述最小違反序列；

步驟3、當未產生新的最小違反序列時，根據所述序列集合中的軌跡數據建立分類樹并通過拉普拉斯機制對數據進行添加噪聲得到發布數據。

2.如權利要求1所述的滿足LKC模型的分類樹差分隱私保護方法，其特征在于，在所述步驟2中，計算新產生的最小違反序列包括：

步驟2.1、在所述序列集合找出軌跡數據集中的最小違反序列集，并根據給定的頻繁閾值，確定最大頻繁序列集；

步驟2.2、構建MFS樹，根據位置點的抑制優先級得分確定抑制的順序；

步驟2.3、根據所述抑制的順序更新MFS；

步驟2.4、重新計算其余位置點的抑制優先級得分，更新最小違反序列集后，得到所述最小違反序列。

3.如權利要求2所述的滿足LKC模型的分類樹差分隱私保護方法，其特征在于，在所述步驟2.2中，所述抑制優先級得分為

式中，Eliminate(p)為位置點p可以消除的最小違反序列數目，Loss(p)為位置點p帶來的有用性損失。

4.如權利要求3所述的滿足LKC模型的分類樹差分隱私保護方法，其特征在于，在所述步驟2.2中，選擇每次抑制優先級得分最高的點實施抑制，確定所述抑制的順序。

5.如權利要求1所述的滿足LKC模型的分類樹差分隱私保護方法，其特征在于，在所述步驟2中，還包括：當產生新的最小違反序列時，還需要驗證所述軌跡數據的軌跡數據集是否滿足LKC-隱私模型，如果軌跡數據集中存在的數據序列不能滿足LKC-隱私模型，則需要更新最小違反序列，直到所有的數據序列都滿足LKC-隱私模型為止；

其中，當滿足如下條件時，所述軌跡數據的軌跡數據集滿足LKC-隱私模型：

|p|＜L；

|T(p)|≥K；以及

Conf(s|T(p))≤C；

式中，Conf(s|T(p))＝|T(p∪s)|/|T(p)|，Conf為不同條件下計算得出的置信度閾值，L為攻擊者掌握的最大軌跡長度值，T為所有用戶的軌跡數據集，S為數據集T中的敏感屬性值，P為數據集T中任意子序列，0≤C≤1，s∈S，C為匿名集的置信度閾值，K為序列中的匿名數。

6.如權利要求1所述的滿足LKC模型的分類樹差分隱私保護方法，其特征在于，在所述步驟3中，建立分類樹過程包括如下步驟：

步驟3.1、初始化所有用戶的軌跡數據集，在所述所有用戶的軌跡數據集選出兩組頻繁序列構造一棵分類樹；

步驟3.2、根據每條軌跡記錄中任意兩個位置點出現的次數，選出次數最多位置點所對應的軌跡序列作為第一組；

步驟3.3、在所述次數最多位置點出現的所有序列中挑出次數最少的序列，再在這個序列所在的軌跡挑出最頻繁的位置點作為第二組；

步驟3.4、重復進行所述步驟3.2、所述步驟3.3，挑選其他軌跡放入所述第一組和所述第二組中，直到所有的軌跡都放入分類樹中，得到最終構建的分類樹。

7.如權利要求6所述的滿足LKC模型的分類樹差分隱私保護方法，其特征在于，在所述步驟3中通過拉普拉斯機制對數據進行添加噪聲過程包括：

用于所述分類樹迭代分割過程中的隱私預算ε以拉普拉斯機制進行細化分割，將ε平均分配給每個增量更新數據集ε_m′，將ε_m′平均分為兩部分分別用于數據迭代過程中拉普拉斯機制和向葉子結點中添加拉普拉斯噪聲；

對于任一函數f:T→R^d，如果算法A的輸出結果滿足不等式A(T)＝f(T)+Lap₁(Δf/ε),Lap₂(Δf/ε),…,Lap_i(Δf/ε)，則A滿足ε差分隱私；

式中，T為軌跡數據集，R為映射的實數閾，d為f:T→R^d的查詢維度，A(T)為算法A在軌跡數據集T上的輸出結果，f(T)為函數f:T→R^d在軌跡數據集T上的輸出結果，Lap_i(Δf/ε)(1≤i≤d)為相互獨立的拉普拉斯變量。