面向軌跡數據發布的優化抑制差分隱私保護研究

白雨靚，李曉會，陳潮陽，王亞君

(遼寧工業大學 電子與信息工程學院，遼寧 錦州 121001)

1 概 述

定位技術的逐步發展和智能設備的全球普及使大量移動對象的軌跡信息被持有和分享，形成了龐大的軌跡數據集，這其中所包含的信息，推動了軌跡數據分析和挖掘技術的進步，使其成為大數據安全領域的一個熱點課題[1-4].研究人員通過對軌跡數據的分析和探索，從中獲取大量有價值的信息用于移動對象的隱私保護研究.在數據發布過程中，不恰當的數據處理很可能會造成用戶的隱私泄露，攻擊者可以根據已掌握的背景知識對移動對象的個人信息進行推斷，從而獲得被攻擊者的經濟狀況、家庭住址等隱私信息[5-7].但如果對軌跡數據集處理過甚，也會導致對象信息的大量損失，降低發布數據的可用性和完整性，造成信息資源的浪費[8，9].所以降低移動對象隱私泄露風險的同時提高待處理軌跡數據的可用性是一個值得深入研究的課題.

現階段，國內外在軌跡數據隱私保護領域已取得了一些研究成果.例如，Mohammed[10]等利用一種匿名算法來實現了LKC隱私模型使其適用于RFID數據，首先識別出軌跡數據集中的最小違反序列集，然后通過貪心法對違反序列進行全局抑制，達到盡可能減少最大頻繁序列損失的目的，但全局抑制的方法需要將大量數據刪除，沒有有效提高數據可用性.Chen[11]等人通過(K，C)L隱私模型及算法提出了局部抑制的概念.該算法首先確定軌跡數據集中不滿足(K，C)L隱私模型要求的所有序列；然后在保證數據高效可用性的前提下，通過局部抑制將軌跡數據集簡化.Ghasemzadeh[12]等人通過對LKC-隱私模型中C=1的情況進行研究，通過全局抑制來實現對軌跡數據的隱私保護；Komishani[13]等人提出一種泛化敏感信息的隱私保護算法，該算法通過對敏感信息屬性建立分類樹來實現對高維軌跡數據集的抑制，但由于不確定攻擊者所掌握背景知識的長度，所以需要抑制大量數據，降低了數據挖掘價值.由此，為了提高軌跡數據發布過程中用戶信息的安全性，降低由于全局抑制帶來的數據損失率，本文提出了一種面向軌跡數據發布的優化抑制差分隱私保護算法.通過對大量軌跡數據集的分析結果表明，相比于其他算法，該算法在保證用戶隱私信息不被泄露的同時有效降低了數據損失率，提高了數據可用性.

2 相關定義

本節主要闡述一些基本定義及相關概念，包括軌跡、違反序列、頻繁序列、分類樹等.

2.1 軌跡

定義 1.(軌跡)[14]軌跡是空間中移動對象所產生的時間和位置的有序組合，可表示為tr=(oi；((x1，y1，t1)，(x2，y2，t2)，…，(xn，yn，tn))).其中：oi為用戶標識符；((x1，y1，t1)，(x2，y2，t2)，…，(xn，yn，tn))為軌跡序列，t1

定義 2.(軌跡數據集)軌跡數據集T是一系列軌跡數據的集合，表示為：T=(tr1，tr2，…，trn)，其中n表示T中包含的軌跡條數，也可用|T|表示，即|T|=n.

若軌跡數據集中的某個敏感屬性和某些位置點共同頻繁出現在同一序列中，攻擊者不用確認移動對象的具體軌跡，也可以通過對其他擁有部分相同序列對象的分析，推斷出被攻擊者的敏感屬性，例如表1是一個包含移動對象敏感屬性的簡單軌跡數據集T.

表1 軌跡數據集T

從表1可知，軌跡數據集T中，包含e2、e3兩個位置點的序列有tr3、tr5、tr7這3條，其中tr3、tr5兩條軌跡所對應的敏感屬性均為SARS.因此，假設被攻擊對象為A，當攻擊者掌握A曾經到過e2、e3兩個位置點這一背景知識時，其可推斷出用戶A患有SARS的概率為2/3=66.7%.

定義 3.(LKC-privacy)[15]L是攻擊者掌握的最大軌跡長度值，T是所有用戶的軌跡數據集，S是數據集T中的敏感屬性值，若T滿足LKC-隱私當且僅當T中任意子序列P在|P|

1)|T(p)|≥K，T(p)是軌跡中包含p的用戶.

2)Conf(s|T(P)≤C，Conf(s|T(p))=|T(P∪s)|/|T(P)|，其中0≤C≤1，s∈S，C是匿名集的置信度閾值，可以根據需求靈活地調整匿名的程度.

2.2 序列

定義 4.(違反序列)假定軌跡序列集上的序列p長度|p|滿足0<|p|≤L，若序列p不滿足LKC-privacy定義中的任一條件，則稱p為違反序列.

定義 5.(最小違反序列)給定違反序列p，若序列p為最小違反序列(記為MVS(Minimal Violating Sequence))，當且僅當序列p的任一子序列均不為違反序列.

定義 6.(頻繁序列)給定閾值E>0和軌跡數據集T中的任一子序列p，若|T(p)|≥E，則稱p為頻繁序列，其中|T(p)|為序列p在T中出現的次數.

定義 7.(最大頻繁序列)給定頻繁序列p，當且僅當p的父序列都不是頻繁序列，則稱序列p為最大頻繁序列，記為MFS(Maximal Frequent Sequence).

2.3 分類樹

定義 8.(分類樹)[16]根據軌跡數據集T建立分類樹，將數據集中敏感信息逐一添加到分類樹的葉子節點中，葉子節點自底向上泛化成為分類樹的節點，所有葉子節點的集合即為分類樹的根節點，對于所有分支，劃分后選擇相同分支的所有實例都屬于同一類.圖1為根據表1數據建立的簡單分類樹.

圖1 表1中敏感屬性的簡單數據分類樹

2.4 差分隱私

差分隱私保護技術通過向數據中添加噪聲技術來實現數據失真，降低數據敏感度的同時保持數據屬性不變，在數據集中更改任一條數據信息，算法輸出結果保持不變，所以即使攻擊者掌握了除一條記錄外的所有敏感數據，這一條記錄中的敏感信息仍然不會被泄露.

定義 9.(差分隱私)[17]給定一個隨機算法Q，Rang(Q)代表其值域，若算法Q對于任意兩個鄰近數據集T1和T2的輸出結果O(O∈Rang(Q))均滿足不等式(1)，則Q滿足ε-差分隱私.

Pr[Q(T1)=O]≤exp(ε)·Pr[Q(T2)=O]

(1)

其中，ε表示隱私預算，Pr[Q(Ti)=O]表示算法的概率，其由算法Q決定.(本文采用的差分隱私保護噪音機制為拉普拉斯噪音機制)

定義 10.(全局敏感度)輸入一個軌跡數據集T，對于任一函數f：T→Rd其全局敏感度可表示為：

(2)

其中，R代表映射的實數閾，d代表f：T→Rd的查詢維度，‖f(T1)-f(T2)‖1表示f(T1)和f(T2)之間的1-階范數距離.

定理 1.(拉普拉斯機制)對于任一函數f：T→Rd，給定隨機算法A，則使A滿足ε-差分隱私，當且僅當算法A滿足等式(3).

A(T)=f(T)+〈Lap1(Δf/ε)，Lap2(Δf/ε)，…，Lapi(Δf/ε)〉

(3)

其中，Lapi(Δf/ε)(1≤i≤d)是相互獨立的拉普拉斯變量，噪音通常由拉普拉斯分布產生，噪音量大小與Δf成正比，與ε成反比.

3 算法的基本思想

3.1 設計思路

本文提出一種面向軌跡數據發布的優化抑制差分隱私保護算法，主要包括兩個部分：

1)將需要進行全局抑制的序列進行局部抑制的操作，根據位置點的抑制優先級得分決定抑制順序，計算其可能產生的最小違反序列，并將其從軌跡數據集中舍棄；

2)建立分類樹，引進差分隱私保護方法實現對軌跡數據保護操作.

3.2 算法描述

面向軌跡數據發布的優化抑制差分隱私保護算法框架圖如圖2所示.

圖2 算法框架圖

第1部分(TOS)：計算新產生的最小違反序列(NewMVS)，具體過程如下：首先找出軌跡數據集中的MVS集合，根據給定的頻繁閾值E，找出最大頻繁序列集，然后構建MFS樹，根據點p的抑制優先級[18]得分Score(p)來決定抑制的順序：

(4)

其中Eliminate(p)代表抑制點p可以消除的MVS數目，Loss(p)代表抑制點p帶來的有用性損失.算法偽代碼如下：

輸入：原始軌跡數據集T、敵手掌握的軌跡長度上限L、匿名數K、置信度閾值C、敏感值合集S、最小違反序列合集MVS

輸出：更新最小違反序列集(NewMVS)

1.X<-Find all MFSs from T；

2.Y<-Based an MFS tree based on the data in X；

3.For each m in MVS；

4.P<-Suppress the point p in m；

5.V<-Single violation sequence point and the violation sequence point of P；

6.Remove the points belong to V from P except p；

7.Generate a new sequence by P；

8.Loop the above operation from 3 to 7；

9.Build the score sheet by Score(p)=Eliminate(p)/Loss(p)；

10.Choose the highest point；

11.If Partial inhibition；

12.Delete the highest p；

13.Update MFS；

14.Else

15.Restrain all instance；

16.Delete the MFS including p；

17.Update score sheet；

18.Return NewMVS；

第2部分(TDP)：利用軌跡數據集經LKC隱私模型處理過的數據迭代構建分類樹，并利用Laplace噪聲機制對敏感信息進行保護[17].首先初始化數據集T，在軌跡數據集選出兩組頻繁序列構造一棵分類樹.其思想為：挑選出每條軌跡記錄中任意兩個位置點出現次數最多所對應的軌跡序列作為第一組，然后在包含這個位置點的所有序列中挑出次數最小的序列，將這個序列所在的軌跡中最頻繁的位置點當做第二組，以此類推，將所有軌跡都迭代挑選進分類樹中，就構造好了一棵分類樹T-tree(0).鑒于軌跡數據集的不斷更新，所以要不斷向分類樹中添加新的記錄，我們需要一個給定的隱私預算ε，每增加新數據集ΔTi時，ΔTi中所有記錄都會被添加到T-tree(i-1)的根節點繼而遞歸到不相交的子集中，若某些記錄被添加到T-tree(i-1)的葉子節點，則需要重新分配該節點的隱私預算后才能繼續分割該節點；若某些記錄被添加到T-tree(i-1)的非葉子節點中，就根據T-tree(i-1)的分類方法處理這些記錄；如果某些記錄為空，則對下一條記錄做上述步驟，直到所有節點都分配完成，形成新的分類樹T-tree(i)，并向分類樹的葉子節點中添加拉普拉斯噪聲.算法偽代碼如下：

輸入：軌跡數據集T，增新數據集ΔTi，隱私預算ε

輸出：噪聲數據集H

19.Initializes the trajectory data set T；

20.Construct matrices A based on data sets；

21.Find the sequence with the most number of occurrences of any two items in A，regard asMmax[i，j]；

22.B1=Mmax[i，j]；

23.Mmin[a，b]←the smallest set of sequences in the rows of i and j；

24.Mmax[c，d]←the largest set of sequences in the rows of a and b；

25.B2=Mmax[c，d]；

26.Repeat the above steps forB1andB2；

27.For each Δ Ti；

28.Z←all trajectory from Δ Ti；

29.Ifz→cut=the root node ofT-tree(0)；

31.Put Z to the root node ofT-tree(i-1)；

32.For eachzi∈ Z；

33.Ifziis leaf node；

34.Separate the node，changeε；

37.Ifziis not a leaf node；

38.Assignziaccording to the classification ofT-tree(i-1)；

39.Else Ifzi=null；

40.Repeat steps 33-36；

41.ReturnT-tree(i)；

42.Add Laplace to A；

43.Return H；

3.3 算法分析

3.3.1 算法的第1部分(TOS)

給定原始軌跡數據集T，首先識別其中的最小違反序列集MVS，然后根據最大頻繁序列集，構建MFS樹，再由點p的抑制優先級得分Score(p)來決定抑制的順序，更新最小違反序列集，時間復雜度為O(|x|L|T|)，|x|為軌跡數據的維數，|T|為軌跡數據集中的軌跡條數；本算法通過更新最小違反序列對局部抑制進行優化，有效解決了全局抑制導致數據可用性降低的問題，同時通過局部抑制提高了軌跡數據安全性.

3.3.2 算法的第2部分(TDP)

4 實驗分析

4.1 實驗環境與數據集

本實驗在Python環境下運行，由Myeclipse集成開發軟件進行算法實現，實驗硬件環境：處理器為Intel(R)Core(TM)i7-5500U CPU 2.40GH、RAM為8.0G、Lnuix操作系統，本文采用包含18670條真實用戶軌跡的開源數據集進行實驗驗證[19]，該數據集由微軟亞洲研究院的Geolife項目提供，在軌跡數據隱私保護相關研究中廣泛應用.

4.2 衡量標準

4.2.1 算法的第1部分(TOS)

本文中數據損失是衡量軌跡數據可用性的重要參考，本文從頻繁序列(MFS)和軌跡序列兩方面進行衡量[20]：

1)MFS數據損失MFSLoss，取決于原始軌跡數據集中的MFS數和經過局部抑制處理后數據集中剩余的MFS數：

(5)

其中M(T)為原始軌跡數據集中的MFS數，M(T°)為經過局部抑制處理后的數據集中的MFS數.

2)軌跡序列損失TLoss，取決于原始軌跡數據集中的序列數以及經過數據處理后的序列數：

(6)

其中L(T)為原始軌跡數據集中的軌跡條數，L(T°)為經過局部抑制處理后的數據集中的軌跡條數.

4.2.2 算法的第2部分(TDP)

本算法利用計數查詢[17]計算數據的平均相對誤差作為衡量數據損失的標準，利用計數查詢R：

(7)

4.3 實驗結果

4.3.1 算法的第1部分(TOS)結果

為了驗證本文算法的有效性，將本文中的TOS算法與文獻[21]以及文獻[22]中的LSUP、MPSTD算法進行實驗結果比對.算法中的匿名個數K、置信度閾值C均會對實驗結果產生不同程度的影響，所以本實驗在不同的K值(3種算法C值、L值相同)、C值(3種算法K值、L值相同)下對3種算法實驗結果進行了比較：

1)不同K值對數據損失的影響

由圖3、圖4中的實驗結果可知，當匿名數K值遞增，MFS損失率和序列損失率也在隨之增加，其原理在于最小違反序列集(MVS)的數目與K值成正比例關系，K值的增加導致需要被抑制的序列數增加，加大了數據損失率.相比于其他兩種算法，本文中的TOS算法在數據處理過程中根據抑制優先得分優化了更新最小違反序列集的過程，合理的利用了局部抑制的優勢，具有更低的MFS損失率和序列損失率.

圖3 不同K值對MFS損失率的影響

圖4 不同K值對序列損失率的影響

2)C值不同對數據損失的影響

由圖5、圖6的實驗結果可知，當置信度閾值C的值遞增，MFS損失率和序列損失率逐漸減小.C值的增加會減少需要抑制的最小違反序列(MVS)數，從而導致MFS損失率和序列損失率都在逐步下降.綜合圖3-圖6數據結果，在數據處理過程中，不論是C值還是K值的遞增，本文提出的TOS 算法的數據處理結果均在一定程度上優于其他兩種算法，因為TOS算法是根據抑制點得分優先級來決定抑制順序，可以更合理的更新最小違反序列集，有效降低由于抑制數據導致的數據損失.

圖5 不同C值對MFS損失率的影響

圖6 不同C值對序列損失率的影響

4.3.2 算法的第2部分(TDP)結果

為了驗證本文算法的安全性，將文獻[23]以及文獻[24]中的CTS-DP、DDPA算法與本文TDP算法進行實驗結果對比.實驗結果表明隨著軌跡數據集長度的增加，數據的平均相對誤差也逐漸增加，但在隱私預算值越大的條件下，兩種實驗中數據的平均相對誤差均在降低.從實驗結果可知，相比于其他兩種算法，本文中TDP算法的軌跡數據分類樹是在通過局部抑制處理后的數據基礎上建立的，避免了由于添加過多拉普拉斯噪聲而導致的數據失真，更有效降低了平均相對誤差，提高了軌跡隱私數據的可用性與安全性.

圖7 ε=0.5時，數據集長度對平均相對誤差的影響

圖8 ε=1時，數據集長度對平均相對誤差的影響

5 結束語

本文提出了一種面向軌跡數據發布的優化抑制差分隱私保護算法，在軌跡數據的發布過程中，通過更新最小違反序列對數據進行合理局部抑制，代替全局抑制的處理，降低了全局抑制造成的多數據損失，提高了軌跡數據的可用性，同時根據處理過后的軌跡數據集中的敏感信息建立分類樹，有效減少拉普拉斯噪聲添加，降低數據失真，相比于其他算法，本文提出的算法有效降低了MFS損失率和序列損失率，減小了平均相對誤差，降低隱私泄露風險的同時提高了待發布數據的可用性.未來將繼續對如何進一步提高待發布數據的可用性進行研究.