[發明專利]基于拉格朗日優化的軌跡間相關性隱私保護方法

有效

• 申請號: 201810188835.2
• 申請日: 2018-03-08
• 公開（公告）號: CN108491730B
• 公開（公告）日: 2021-11-19
• 發明（設計）人: 歐露;秦拯;胡娟
• 申請（專利權）人: 湖南大學
• 主分類號: G06F21/62
• 分類號: G06F21/62
• 代理公司: 深圳市興科達知識產權代理有限公司 44260
• 代理人: 王翀;賈慶

1.一種基于拉格朗日優化的軌跡間相關性隱私保護方法，其特征在于，包括如下步驟：

步驟一：將用戶的原始軌跡以天為單位，劃分為多條子軌跡，稱為“每天的軌跡”，“每天的軌跡”具有n個采樣時間點；

步驟二：針對每天的軌跡，運用n體拉普拉斯框架，通過生成服從拉普拉斯分布的噪聲集合，并將集合中噪聲依據時間順序分別添加到原始軌跡上，從而實現軌跡間相關性隱私保護；并且n體拉普拉斯框架滿足以下式子：

其中，

表示在θ_ρ分布的條件下，屬于集合的概率；表示運用S機制查詢所得到的結果，表示加噪聲之后的一個軌跡距離；表示，在θ_ρ分布的條件下，屬于集合的概率；表示運用S機制查詢所得到的結果，表示加噪聲之后的另一個軌跡距離；和有且僅有一個時間點上的位置距離不同；θ_ρ是所有可能的位置相關性的分布；位置相關性表示第i個時間點上經度x的相關系數，表示第i個時間點上緯度y的相關系數；為第m個時間點上經度x的隱私保護預算，為第m個時間點上緯度y的隱私保護預算，為第i個時間點上經度x的隱私保護預算，為第i個時間點上緯度y的隱私保護預算；

步驟三：當應用場景不需要利用用戶位置間相關關系的時候，根據位置有用性，來凈化處理兩個用戶的軌跡，以實現軌跡間相關性；位置有用性是通過絕對距離偏差來衡量數據有用性的方法，通過計算經度x和緯度y上噪聲的期望之和的平均值，表達式為：

其中，和分別為第i個時間點上用戶的經度x和緯度y所添加的噪聲，u_d表示位置有用性，d表示位置有用性的下標；E()表示或絕對值的期望的運算符；

面向位置有用性時，兩個用戶的隱私保護處理步驟如下：

一、輸入原始數據：輸入用戶a和用戶b的原始軌跡集合以及給定的位置有用性其中，u_d的取值由用戶依據需求來設定；

二、計算原始軌跡距離：將用戶a和用戶b軌跡中每個時間點上經度x和緯度y依次相減，得到的集合為原始軌跡距離，標記為其中，和分別為兩用戶的經度x上位置距離和緯度y上位置距離，i為一天中第i個時間點，和分別為用戶a和b在第i個時間點上的經度，和分別為用戶a和b在第i個時間點上的緯度；

三、計算用戶a和用戶b的軌跡相關性分數S：軌跡相關性分數S是一種運用軌跡距離來測量同一天兩條軌跡間相關性的測量方法，該方法為一個關于軌跡距離的指數函數，其表達式為：S＝S(x)S(y)，

其中，R表示決定相關性范圍的參數；

四、計算面向位置有用性情況下的拉格朗日乘數因子λ_d：首先，構建拉格朗日約束條件，其表達式為：從而可得，與歸一化軌跡距離和拉格朗日乘數因子相關的歸一化拉普拉斯分布尺度參數的函數，標記為表示第i個時間點上歸一化的位置距離，然后，通過牛頓拉弗森方法來求解計算得拉格朗日乘數因子λ_d；其中，為歸一化的第i個時間點上拉普拉斯分布尺度參數，表示面向位置有用性情況下第i個時間點上的拉普拉斯分布尺度參數；

五、計算歸一化的拉普拉斯分布尺度參數的集合運用拉格朗日乘數法，求解滿足拉格朗日約束條件：的所有的即得，由組成的集合

六、凈化處理原始軌跡：將服從拉普拉斯分布的噪聲添加到原始軌跡上，以實現軌跡間相關性隱私保護，其操作如下所示：δ是添加在經度和緯度上噪聲的數據集；

表示凈化處理后用戶a的軌跡，表示凈化處理后用戶b的軌跡；

步驟四：當應用場景需要利用用戶位置間相關關系的時候，根據位置相關性有用性來凈化處理兩個用戶的軌跡，以實現軌跡間相關性隱私保護；位置相關性有用性是運用兩用戶間經度和緯度的相關系數來衡量數據有用性的方法，其表達式為：

其中，和分別為在第i個時間點上加入噪聲前后的經度的相關系數，和分別為在第i個時間點上加入噪聲前后的緯度的相關系數，表示位置相關性有用性，c表示位置相關性有用性的下標；

面向位置相關性有用性時，兩個用戶的隱私保護處理步驟如下：

一、輸入原始數據：輸入兩個用戶的原始軌跡集合以及位置相關性有用性c表示位置相關性有用性的下標；0≤u_c≤1；

二、計算相關系數集合：獲取用戶a和用戶b原始軌跡中每個時間點上經度相關系數集合ρ_x和每個時間點上緯度相關系數集合ρ_y；

三、計算原始軌跡距離：將用戶a和用戶b用戶軌跡中每個時間點上經度和緯度依次相減，得到的集合為原始軌跡距離，標記為其中，和分別為兩用戶的經度上位置距離和緯度上位置距離，i為一天中第i個時間點，x為經度，y為緯度，和分別為用戶a和b在第i個時間點上的經度，和分別為用戶a和b在第i個時間點上的緯度；

四、計算用戶a和用戶b的軌跡相關性分數S：軌跡相關性分數S是一種運用軌跡距離來測量同一天兩條軌跡間相關性的測量方法，該方法為一個關于軌跡距離的指數函數，其表達式為：

S＝S(x)S(y)，

其中，R表示決定相關性范圍的參數；

五、計算面向位置相關性有用性情況下拉格朗日乘數因子λ_c：首先，構建拉格朗日約束條件，其表達式為：從而可得，與歸一化位置相關性和拉格朗日乘數因子相關的歸一化拉普拉斯分布尺度參數的函數；然后，通過牛頓拉弗森方法來求解ρⁱ表示第i個時間點上兩用戶間相關系數；計算得拉格朗日乘數因子λ_c；其中，為歸一化的第i個時間點上拉普拉斯分布尺度參數，表示面向位置相關性有用性情況下第i個時間點上的拉普拉斯分布尺度參數；

六、計算歸一化的拉普拉斯分布尺度參數的集合運用拉格朗日乘數法，求解滿足拉格朗日約束條件的所有的即得由組成的集合

七、凈化處理原始軌跡：將服從拉普拉斯分布的噪聲添加到原始軌跡上，以實現軌跡間相關性隱私保護，其操作如下所示：

表示凈化處理后用戶a的軌跡，表示凈化處理后用戶b的軌跡。