[發明專利]一種面向隱私保護的用戶軌跡生成方法及系統

有效

• 申請號: 201911345902.8
• 申請日: 2019-12-23
• 公開（公告）號: CN111125764B
• 公開（公告）日: 2022-02-15
• 發明（設計）人: 丁曉鋒;金海;周文翔
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F21/62
• 分類號: G06F21/62
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 李智

1.一種面向隱私保護的用戶軌跡生成方法，其特征在于，該方法包括以下步驟：

S1.將時間段t對應的位置元組數據流S所在區域范圍劃分為層次網格，采用Geohash算法對各個網格進行編碼，得到每個位置數據元組的編碼字符串；

S2.根據劃分后的網格和所有位置數據元組的編碼字符串，生成該元組數據流S對應的前綴層次樹；

S3.將該元組數據流S劃分為k段，根據第一隱私預算值ε_a對每段數據流進行采樣，得到采樣后的位置元組數據集{D′_i}，1≤i≤k；

S4.根據差分隱私的指數機制，將各個采樣后的位置元組泛化到對應的劃分區域內，得到泛化后的位置元組數據集

S5.通過第二隱私預算ε_b，對處于相同劃分網格內的元組數據進行合并得到符合隱私保護要求的用戶軌跡；

步驟S3包括以下步驟：

S31.以時間窗口長度T為單位，將用戶位置數據流S劃分為k個連續的分段D₁,…,D_i,…,D_k；

S32.根據第一隱私預算ε_a，計算每個分段D_i的元組采樣隱私預算ε_a,i，將其分配給對應分段，元組采樣隱私預算ε_a,i計算公式如下：

S33.根據每段數據流D_i分配到的隱私預算ε_a,i值，計算其對應的采樣概率

S34.根據采樣概率P_i，分別對每個分段數據流D_i中的位置數據進行采樣，整理采樣后得到的流數據元組，并生成采樣后的元組數據集D′₁,…,D′_i,…,D′_k；

其中，s為界限常數，滿足k為分段總數，i為分段編號；

步驟S4包括以下步驟：

S41.收集元組數據流S所在路網中的每個位置，組成位置域Γ；

S42.對于每個分段D′_i，計算其每一個元組數據x′_iz對于在位置域Γ的每個網格r_j的權重分數q(x′_iz,r_j)，計算公式如下：

其中，Pt[r_j]表示網格節點r_j所包含的訪問者人數信息，Δdis_ijz表示網格節點r_j與D′_i中的元組x′_iz所在的網格節點之間的距離，a是小于1的常數，由位置域的面積確定；

S43.使用差分隱私的指數機制，結合元組x′_iz與周圍網格的權重分數q(x′_iz,r_j)，生成相應的泛化概率

S44.根據泛化概率P_ijz將x′_iz泛化到對應的網格r_j中，得到元組數據集

其中，1≤z≤|D′_i|，1≤j≤|Γ|，r_j表示位置域Γ第j個網格；

步驟S5包括以下步驟：

S51.根據第二隱私預算ε_b的值，確定對應的元組合并級別level，該合并級別level代表元組要被合并到的網格的父節點的深度；

S52.定義k個空集合LR_i，對于在每段位置數據集中，每個元組數據所在的網格節點的祖先節點anc進行集合的添加操作，即LR_i＝LR_i∪{anc}，最后構成對應的祖先節點集合LR_i；

S53.對于祖先節點集合LR_i中的每個元素p_ij，計算鍵值對字典

S54.根據隱私預算ε_b和鍵值對字典計算每個p_ijn作為合并候選網格的概率

S55.使用差分隱私指數機制，根據概率P_ijn進行合并網格的選擇；

S56.將每段位置數據集中，每個元組數據的經緯度位置信息替換為合并網格的位置信息，直至所有k段位置數據集完成元組合并操作，生成一條符合隱私保護要求的用戶軌跡；

其中，p_ijn表示p_ij的第n個子節點，1≤n≤|child(p_ij)|，child(p_ij)為p_ij的子節點集合，表示中所有的元素個數計數，并且要滿足的元素所在的網格與p_ijn存在交集關系，表示所在節點的所有兄弟節點的集合。