鄧勁松，羅永龍，俞慶英，陳付龍

(1.安徽師范大學(xué) 數(shù)學(xué)計算機科學(xué)學(xué)院，安徽 蕪湖 241003； 2.安徽師范大學(xué) 網(wǎng)絡(luò)與信息安全工程技術(shù)研究中心，安徽 蕪湖 241003)

(*通信作者電子郵箱18726154578@163.com)

基于非敏感信息分析的軌跡數(shù)據(jù)隱私保護發(fā)布

鄧勁松1*，羅永龍1,2，俞慶英1,2，陳付龍1,2

(1.安徽師范大學(xué) 數(shù)學(xué)計算機科學(xué)學(xué)院，安徽 蕪湖 241003； 2.安徽師范大學(xué) 網(wǎng)絡(luò)與信息安全工程技術(shù)研究中心，安徽 蕪湖 241003)

(*通信作者電子郵箱18726154578@163.com)

針對軌跡數(shù)據(jù)發(fā)布時軌跡和非敏感信息引起的隱私泄露問題，提出一種基于非敏感信息分析的軌跡數(shù)據(jù)隱私保護發(fā)布算法。首先，分析軌跡和非敏感信息的關(guān)聯(lián)性構(gòu)建軌跡隱私泄露判定模型，得到最小違反序列元組(MVS)，然后借鑒公共子序列的思想，在消除MVS帶來的隱私泄露風(fēng)險時，選擇MVS中對軌跡數(shù)據(jù)損失最小的時序序列作為抑制對象，從而生成具有隱私能力和低數(shù)據(jù)損失率的匿名軌跡數(shù)據(jù)集。仿真實驗結(jié)果表明，與LKC-Local算法和Trad-Local算法相比，在序列長度為3的情況下，該算法平均實例損失率分別降低了6%和30%，平均最大頻繁序列(MFS)損失率分別降低了7%和60%,因此所提算法能夠有效用于提高推薦服務(wù)質(zhì)量。

隱私保護；高維軌跡數(shù)據(jù)；非敏感信息；公共子序列；序列抑制

0 引言

隨著定位技術(shù)的發(fā)展和智能設(shè)備的普及，產(chǎn)生了大量移動對象的軌跡數(shù)據(jù)，這些軌跡數(shù)據(jù)包含的非敏感信息，如朋友信息、職業(yè)信息等，促進了社交推薦[1-4]的快速發(fā)展，例如為用戶提供飯店推薦服務(wù)時，考慮用戶與朋友興趣選擇更相似，對用戶軌跡和朋友信息發(fā)布進行數(shù)據(jù)挖掘來提高推薦質(zhì)量；當(dāng)預(yù)測用戶未來軌跡位置時，考慮相同職業(yè)的用戶軌跡可能更相似，對用戶軌跡和職業(yè)信息發(fā)布進行數(shù)據(jù)挖掘來提高預(yù)測精度等。然而，簡單地將移動對象軌跡和非敏感信息發(fā)布進行社交推薦時，若攻擊者掌握用戶的部分軌跡序列和非敏感信息，可能形成隱秘位置推理攻擊[5]，造成用戶隱私信息的泄露，例如攻擊者掌握用戶的部分軌跡序列和朋友關(guān)系，則可以根據(jù)朋友信息高概率推測出用戶的軌跡信息，從而威脅用戶的安全。因此，用戶軌跡數(shù)據(jù)的隱私保護發(fā)布成為研究者和用戶的關(guān)注重點。

目前，軌跡數(shù)據(jù)隱私保護發(fā)布的研究方法主要集中于K-匿名模型[6]，已取得大量研究成果[7-14]。近年來，隨著高維軌跡數(shù)據(jù)集隱私保護發(fā)布[15]的提出，由于傳統(tǒng)的隱私保護算法并不適用于高維軌跡數(shù)據(jù)集的隱私保護[15-16]，相關(guān)領(lǐng)域也取得了很多研究成果[15-21]：Mohammed等[15]基于LKC-隱私模型[20](其中K表示軌跡匿名個數(shù)，C表示敏感信息推斷概率，L表示軌跡序列長度)獲得高維軌跡數(shù)據(jù)集中所有存在隱私泄露的違反序列，提出全局抑制違反序列的隱私保護算法；Chen等[16]在文獻[15]的研究基礎(chǔ)上，考慮全局抑制操作會刪除大量的數(shù)據(jù)實例，提出局部抑制違反序列來消除隱私泄露，保證數(shù)據(jù)集的數(shù)據(jù)后續(xù)實用性；Al-Hussaeni等[17]基于軌跡前綴樹提出動態(tài)更新軌跡序列滑動窗口的隱私模型，能解決軌跡數(shù)據(jù)流發(fā)布造成的用戶隱私泄露問題；Ghasemzadeh等[18]基于LK-隱私模型(其中K表示軌跡匿名個數(shù)，L表示軌跡序列長度)提出抑制軌跡序列操作來消除軌跡數(shù)據(jù)集用于客流分析時造成的用戶位置隱私泄露問題；Komishani等[19]提出基于軌跡數(shù)據(jù)隱私水平和敏感屬性分類樹水平來泛化敏感屬性的隱私保護算法，能解決軌跡序列造成的隱私泄露問題。

現(xiàn)有的軌跡隱私保護方法大多應(yīng)用于解決軌跡數(shù)據(jù)發(fā)布過程中軌跡序列造成的位置隱私泄露和敏感信息泄露兩方面問題，而針對軌跡數(shù)據(jù)和非敏感信息聯(lián)合發(fā)布過程中存在的隱私泄露問題[15-16]并未見研究工作。簡單使用上述隱私保護算法解決該問題存在如下缺陷：若對非敏感信息進行泛化處理[21-23]，軌跡數(shù)據(jù)集高維性使得處理后的非敏感信息實用性得不到保證；若不對非敏感信息進行泛化處理，當(dāng)軌跡序列在部分非敏感信息下存在隱私泄露、在部分非敏感信息下不存在隱私泄露時，算法總是抑制數(shù)據(jù)集中全部軌跡序列，造成實例被大量抑制，處理后的實例實用性得不到保證。

為此，本文提出基于非敏感信息分析的軌跡數(shù)據(jù)隱私保護發(fā)布算法(TrajectoryPrivacy-preservingbasedonNon-SensitiveinformationAnalysis,TP-NSA)。首先針對高維軌跡數(shù)據(jù)集和非敏感信息聯(lián)合存在的隱私泄露問題，構(gòu)建LQK-隱私模型(其中L表示軌跡序列長度，Q表示非敏感信息集合，K表示軌跡匿名個數(shù))獲取數(shù)據(jù)集在各非敏感信息下可能存在隱私泄露的違反序列元組集合；然后基于各時序序列的抑制方式提出非敏感信息下各時序序列的抑制權(quán)重值計算公式，并依據(jù)權(quán)重值對違反序列元組集合進行抑制處理操作，得到滿足LQK-隱私模型的匿名軌跡數(shù)據(jù)集。本文對包含違反序列的軌跡數(shù)據(jù)進行局部抑制操作時，采用雙重判斷：一是權(quán)重值最高；二是借鑒公共子序列的思想，選擇各軌跡中可以消除最多違反序列元祖的時序序列作為抑制成員，保證軌跡數(shù)據(jù)的后續(xù)實用性。

1 相關(guān)定義及隱私模型

1.1 相關(guān)定義

定義1 軌跡[7]。軌跡是三維空間中時間和位置有序組合得到的連續(xù)線段，可形式化表示為tr=(oi;((x1,y1,t1),(x2,y2,t2),…,(xn,yn,tn)))。其中:oi為用戶標(biāo)識;((x1,y1,t1),(x2,y2,t2),…,(xn,yn,tn))為軌跡序列，且t1

定義4 軌跡數(shù)據(jù)。軌跡數(shù)據(jù)是移動用戶所有個人信息的集合。通常情況下，軌跡數(shù)據(jù)表示為Tr=(oi;((x1,y1,t1),(x2,y2,t2),…,(xn,yn,tn));ns1,ns2,…,nsm)，其中Q為非敏感信息(non-sensitive,ns)集合,nsi∈Q(1≤i≤m)。

定義5 軌跡數(shù)據(jù)集[15]。軌跡數(shù)據(jù)集T是一系列軌跡數(shù)據(jù)的集合，表示為：T=(Tr1,Tr2,…,Trn)。

1.2 LQK-隱私模型

對移除用戶標(biāo)識符后發(fā)布的軌跡數(shù)據(jù)集進行信息挖掘時，攻擊者可以獲取用戶的軌跡序列和非敏感信息作為背景知識來攻擊用戶。本文在軌跡序列與非敏感信息聯(lián)合攻擊造成的隱私泄露問題上提出LQK-隱私模型。

定義6LQK-隱私模型。假設(shè)L為攻擊者掌握用戶的背景知識(即軌跡序列個數(shù))最大長度，Q為非敏感信息集合，K為軌跡匿名個數(shù)，則軌跡數(shù)據(jù)集滿足LQK-隱私模型當(dāng)且僅當(dāng)長度0<|q|≤L的軌跡序列q滿足：對Q中各ns，|T({q,ns})|≥K，其中T({q,ns})表示數(shù)據(jù)集同時包含q和ns的軌跡集合，|T({q,ns})|表示數(shù)據(jù)集同時包含q和ns的軌跡個數(shù)，要求軌跡個數(shù)至少K條。

定義7 違反序列元組。假設(shè)q為軌跡數(shù)據(jù)集上滿足0<|q|≤L的軌跡序列，給定LQK-隱私模型，若Q中存在ns滿足|T({q,ns})|

定義8 最小違反序列元組。給定{q,ns}，若q的所有可能子序列[15]與ns組合都不是違反序列元組，稱{q,ns}為最小違反序列元組(MinimalViolatingSequencetuple,MVS)，記作mMVS,并將數(shù)據(jù)集中存在的所有mMVS存儲到集合MMVS中。

定義9 權(quán)重值(Weight)。q的權(quán)重值是評價時序序列q在非敏感信息下抑制造成的信息損失指標(biāo)，記為w(q)。計算公式如下：

w(q)=mvsDel(q)/infoLoss(q)

(1)

其中：mvsDel(q)表示MMVS中包含q的違反序列元組個數(shù)；infoLoss(q)表示抑制q造成軌跡和非敏感信息關(guān)聯(lián)性的缺失率，按式(2)計算。

(2)

其中:count(i)表示數(shù)據(jù)集同時包含q與第i個ns的軌跡個數(shù)，loss(i)表示抑制操作造成同時包含q和第i個ns的軌跡減少數(shù)量，n為非敏感信息個數(shù)。

2 隱私保護算法

本文提出的TP-NSA算法主要用于解決軌跡序列和非敏感信息聯(lián)合造成的隱私泄露問題，核心思想是對數(shù)據(jù)集在各非敏感信息下存在隱私泄露的違反序列元組進行抑制操作，保證軌跡K-匿名，同時盡可能保證匿名數(shù)據(jù)集的后續(xù)實用性。因此，基于文獻[16]的LKC-Local(Length K-anonymity Confidence based on Local suppression)算法框架，本文的TP-NSA算法分為兩個步驟：1)獲取軌跡數(shù)據(jù)集最小違反序列元組集合；2)對最小違反序列元組進行時序序列抑制方式判斷和時序序列抑制選擇，從而進行軌跡數(shù)據(jù)集匿名化處理。

2.1 相關(guān)定理及證明

定理1LQK-隱私模型是有效的。

證明 文獻[15]指出高維軌跡數(shù)據(jù)集的高維性和數(shù)據(jù)稀少造成實現(xiàn)傳統(tǒng)K-匿名需要花費極大代價，因此高維軌跡數(shù)據(jù)集隱私保護研究需要限制攻擊者掌握的背景知識長度L；同時從定義6得出：LQK-隱私模型可以保證用戶軌跡在軌跡序列和非敏感信息聯(lián)合下被成功識別的概率≤1/K，故LQK-隱私模型是有效的。

證畢。

定理2 TP-NSA算法采用公共子序列實現(xiàn)數(shù)據(jù)低損失是可行的。

證明 文獻[24]指出：數(shù)據(jù)集中實例個數(shù)和MFS(Maximal Frequent Sequence)[24]個數(shù)對數(shù)據(jù)挖掘質(zhì)量影響較大，而公共子序列可以作為描述多個違反序列元組公共包含的時序序列，對該時序序列進行抑制操作，可以同時消除多個違反序列元組造成的隱私泄露問題，降低實例抑制個數(shù)，實現(xiàn)數(shù)據(jù)集的數(shù)據(jù)低損失。故TP-NSA算法采用公共子序列實現(xiàn)數(shù)據(jù)低損失是可行的。

證畢。

2.2 TP-NSA算法描述

2.2.1 最小違反序列元組獲取

在獲取數(shù)據(jù)集各非敏感信息下存在隱私泄露的違反序列元組時，由于LKC-Local算法[16]提出的MVS生成子算法并沒有將非敏感信息當(dāng)成違反序列一部分，而且若對每個非敏感信息進行一次數(shù)據(jù)集掃描，花費時間代價較大。因此，本文基于文獻[16]的MVS生成子算法框架提出改進的MVS生成算法(具體見算法1)：首先將非敏感信息相同的軌跡放在同一個等價類Tns中(見算法1第2)～9)行)，用于算法的后續(xù)操作，從而保證對所有非敏感信息進行掃描操作次數(shù)總和為數(shù)據(jù)集記錄個數(shù)，減少掃描花費時間。然后根據(jù)定義6對各等價類Tns進行掃描判斷：若在違反序列候選集合Di中存在軌跡序列q滿足|T({q,ns})|

算法1MVSGenerating。

輸入T，L，K，Q；

輸出MMVS，Tec。

1)

MMVS←?;Tec←?;i←1;

2)

foreachns∈Qdo

//非敏感信息軌跡劃分

3)

foreachtrajectorytr∈Tdo

4)

iftrhasthesamens

5)

Tns←Tns∪{tr};

6)

endif;

7)

endfor;

8)

Tec←Tec∪{Tns};

9)

endfor;

10)

D1=alldistinctdoubletsinT;

11)

foreachTns∈Tec

12)

ifi<=LandDi!=?then

13)

foreachsequenceq∈Dido

14)

scanTnstocompute|T({q,ns})|;

15)

if|T({q,ns})|

16)

MVSns←MVSns∪{q,ns};

17)

else

18)

NMVSi←NMVSi∪{q};

19)

endif;

20)

endfor;

21)

i++;

22)

23)

foreachsequenceq∈Dido

24)

if{q,ns}isasupersequenceofm∈MVSnsthen

25)

removeqfromDi;

26)

endif;

27)

endfor;

28)

else

29)

MMVS←MMVS∪MVSns;

30)

i←1;

31)

endif;

32)

endfor;

33)

returnMMVS,Tec;

2.2.2 匿名化處理

對于給定的軌跡數(shù)據(jù)tr和包含q的違反序列元組m，有效選擇違反序列元組中抑制時序序列，可以降低數(shù)據(jù)集實例抑制個數(shù)。算法2基于公共子序列思想詳細描述違反序列元組中抑制時序序列的選擇，首先將MMVS包含于tr的違反序列元組存到集合A中；然后將A中與m相交的違反序列元組m′存到集合B(見定義3)；最后對m分割得到長度為1的時序序列集合C，掃描集合B計算C中各時序序列的父序列[15]個數(shù)作為在tr中得分，并返回得分最高的時序序列。這樣，抑制最高分時序序列可以保證軌跡在損失最少實例情況下，得到更多的隱私保護，數(shù)據(jù)實用性更高。

算法2Suppression-doubletChecking。

輸入tr,anMVSmthatcontainsq；

輸出thesuppressiondoubletinm。

1)

A←{m′|m′∈tr,m′∈MMVS};

2)

B←{m′|m′∈A,m∩m′≠?};

3)

C=alldistinctdoubletsinm;

4)

foreachdoubletq′∈Cdo

5)

ScanBtocompute|q′|;

6)

D=D∪|q′|;

7)

endfor;

8)

selectthedoubletq′withhighestscorefromD;

9)

ifq′equalsqthen

10)

returnq;

11)

else

12)

returnq′;

13)

endif;

算法在判斷違反序列元組中各時序序列的抑制方式時，考慮LKC-Local算法[16]為時序序列抑制方式的判斷設(shè)計了高效的判定方法，并證明了方法的有效性，因此，本文直接調(diào)用該方法來獲取各時序序列在非敏感信息下的抑制方式。

確定MVS中時序序列抑制方式集合suppression_way之后，根據(jù)定義9提出的權(quán)重值計算公式，得到MVS中時序序列在非敏感信息下的抑制權(quán)重表Weight_Table，并按照降序排列?？紤]權(quán)重值大小反映出用戶隱私獲取與信息損失之間的比值，權(quán)重值越大，表明比值越大，數(shù)據(jù)損失越小，因此算法3總是選擇權(quán)重值最高的時序序列q作為抑制成員，并根據(jù)q抑制方式的不同對各等價類Tns采取不同的操作(見算法3第5)～15)行)：如果q可以局部抑制，選擇包含最小違反序列元組m(m包含q)的軌跡tr進行q抑制操作時，算法并不是直接對tr中q抑制，而是調(diào)用算法2得到m中最高分抑制時序序列q′，并執(zhí)行q′抑制操作(見算法3第9)～10)行)，因為基于算法2得到的抑制時序序列包含于違反序列元組最多，這樣每次抑制操作可以實現(xiàn)tr中違反序列元組消除最多，從而保證數(shù)據(jù)損失最??；如果q被全局抑制，則抑制Tns中所有q(見算法3第14)行)。此外，當(dāng)q引起的隱私泄露消除后，算法需要更新MVS，檢查時序序列的抑制方式是否發(fā)生改變，更新和降序排列Weight_Table，為下一次抑制作準(zhǔn)備(見算法3第16)～17)行)。

重復(fù)上述操作直到Weight_Table為空時結(jié)束，將抑制處理得到的數(shù)據(jù)集作為可以發(fā)布的匿名數(shù)據(jù)集T′。

算法3AnonymityProcessing。

輸入Tec，MMVS，suppression_way，Weight_Table；

輸出 滿足LQK-隱私模型的軌跡數(shù)據(jù)集T′。

1)

T′←?;

2)

whileWeight_Table≠ ?do

/*迭代抑制各時序序列*/

3)

q←thefirstdoubletinWeight_Table;

4)

foreachTns∈Tecdo

5)

ifsuppression_way(q)=localsuppressionthen

6)

foreachm∈MVSns(q)do

7)

A←{tr|tr∈Tns,m?tr};

8)

foreachtrajectorytr∈Ado

9)

q′←Suppression-doubletChecking(tr,m);

10)

Deleteq′fromtr;

11)

endfor;

12)

endfor;

13)

else

14)

DeleteallqfromTns;

15)

endif;

16)

MMVS=MMVS-MVSns(q);

17)

Updatethew(q′)ifq′inMVSns(q);

18)

T′←T′∪{Tns};

19)

endfor;

20)

RemoveqfromWeight_Table;

21)

endwhile;

22)

returnT′;

2.3 算法分析

TP-NSA算法時間復(fù)雜度由兩部分組成。第一部分是獲取數(shù)據(jù)集中違反序列元組集合，這部分花費時間的操作是掃描數(shù)據(jù)集判斷軌跡序列在各非敏感信息下的隱私泄露風(fēng)險，由于軌跡數(shù)據(jù)集中軌跡序列候選集合大小為O(|d|2)[15]，算法1對各軌跡序列在各非敏感信息下進行掃描操作的時間復(fù)雜度為O(|d|2|T|)，其中|d|為軌跡數(shù)據(jù)集的維數(shù)，|T|為軌跡數(shù)據(jù)集的記錄數(shù)。第二部分是對算法1產(chǎn)生的MVS集合進行抑制處理，假設(shè)算法1產(chǎn)生的MVS集合大小為O(N)，算法3執(zhí)行次數(shù)為O(M)，每個MVS包含于軌跡集合的平均個數(shù)為O(L)，則算法3每次抑制操作消除MVS個數(shù)為O(N/M)，花費時間為O(L/MN2)?？紤]判斷時序序列在非敏感信息下的局部抑制有效性的時間復(fù)雜度為O(N|T|)[16]，因此，TP-NSA算法的總時間復(fù)雜度為O(|d|2|T|)+O(M)·O(L/MN2)+O(N|T|)=O(|d|2|T|)+O(LN2)+O(N|T|)，其中：|d|為軌跡數(shù)據(jù)集的維數(shù)，|T|為軌跡數(shù)據(jù)集的記錄數(shù)。

TP-NSA算法與LKC-Local算法[16]相比，在軌跡序列隱私泄露判定時，將非敏感信息軌跡進行等價類劃分，能縮短算法掃描花費時間；在序列抑制操作時，采用公共子序列的思想，能降低數(shù)據(jù)實例的抑制數(shù)量。

2.4 衡量標(biāo)準(zhǔn)

損失率是衡量軌跡數(shù)據(jù)集數(shù)據(jù)實用性的重要參數(shù)?；诟呔S軌跡數(shù)據(jù)集挖掘處理時實例個數(shù)和MFS[24]個數(shù)對挖掘價值的影響[15-16]，本文將從實例和MFS兩方面衡量TP-NSA算法實用性損失：

1)在實例損失[16]方面，采用式(3)來衡量：

InstanceLoss=[N(T)-N(T′)]/N(T)

(3)

其中，N(T)和N(T′)分別表示原始軌跡數(shù)據(jù)集中實例總數(shù)和匿名軌跡數(shù)據(jù)集中實例總數(shù)。實例損失越小，表明匿名軌跡數(shù)據(jù)集與原始軌跡數(shù)據(jù)集的相似度越大，數(shù)據(jù)挖掘操作得到的挖掘結(jié)果越精確。

2)在MFS損失[16]方面，使用文獻[24]提出的MAFIA算法分別得到原始軌跡數(shù)據(jù)集MFS集合和匿名軌跡數(shù)據(jù)集MFS集合，并采用式(4)來衡量：

MFSLoss=[U(T)-U(T′)]/U(T)

(4)

其中，U(T)和U(T′)分別表示原始軌跡數(shù)據(jù)集MFS總數(shù)和匿名軌跡數(shù)據(jù)集MFS總數(shù)。MFS損失越小，表明基于MFS進行數(shù)據(jù)挖掘為用戶提供推薦服務(wù)的質(zhì)量越高，用戶滿意度越高。

3 實驗與分析

3.1 實驗數(shù)據(jù)集

實驗采用合成數(shù)據(jù)集City80K[15-16,19]來測試TP-NSA隱私保護算法數(shù)據(jù)實用性損失。City80K是一個模擬擁有26個板塊的大都市中80 000個行人在每天24小時移動軌跡的合成數(shù)據(jù)集，其中數(shù)據(jù)集提供的非敏感信息為用戶職業(yè)信息，包括醫(yī)生、學(xué)生和律師三種。實驗的硬件環(huán)境為：IntelCore2QuadCPUQ9500 @2.83GHz,2GB內(nèi)存，操作系統(tǒng)為MicrosoftWindows7，算法使用Java語言實現(xiàn)。

3.2 實驗結(jié)果與分析

基于2.4節(jié)的實例損失和MFS損失衡量標(biāo)準(zhǔn)，本文將TP-NSA算法與基于傳統(tǒng)K-匿名[6]的Trad-Local算法和文獻[16]提出基于局部抑制的LKC-Local算法進行比較，圖1～3展示了三個算法的實例損失率和MFS損失率對比結(jié)果。

圖1 實例損失(L=3)

圖1是L值相同、K值不同情況下實例損失率的對比結(jié)果。實驗中TP-NSA和LKC-Local設(shè)定L=3，Trad-Local設(shè)定L=|d|(|d|表示軌跡數(shù)據(jù)集維數(shù))，K從20遞增到40。從圖1中可看出，實例損失率隨著K的遞增而遞增，且TP-NSA算法的實例損失率低于LKC-Local算法，這是由于K的遞增使得違反序列元組遞增，被抑制序列個數(shù)遞增，實例損失率遞增。但TP-NSA算法不僅考慮軌跡序列在各非敏感信息下的隱私泄露風(fēng)險，而且違反序列元組抑制時也考慮局部抑制最優(yōu)的時序序列，能降低實例被錯誤抑制的概率，保證數(shù)據(jù)集實例可用性；Trad-Local算法則受限于背景知識的最大長度為數(shù)據(jù)集維數(shù)，各非敏感信息下的違反序列元組比較多，實例損失率最高。

圖2是L值相同、K值和S值不同的情況下MFS損失率的對比結(jié)果。實驗中TP-NSA和LKC-Local設(shè)定L=3，Trad-Local設(shè)定L=|d|(|d|表示軌跡數(shù)據(jù)集維數(shù))，K從20遞增至35，S從200遞增至1 000。

從圖2中可以看出，在相同S值的情況下，MFS損失率隨著K的遞增而遞增，這時由于K的遞增導(dǎo)致違反序列元組的個數(shù)遞增，被抑制的序列遞增，數(shù)據(jù)集中MFS損失率越來越大；在相同K值的情況下，MFS損失率隨著S的遞增先遞增后遞減，這是由于S的遞增使得MFS個數(shù)降低，且MFS與MVS之間的覆蓋率逐漸遞減，造成損失率先遞增再遞減。由對比實驗可以看出，TP-NSA算法在不同參數(shù)K上和S上MFS損失率都要低于LKC-Local算法，因為LKC-Local算法在處理軌跡序列和非敏感信息聯(lián)合攻擊造成的隱私泄露問題時，認(rèn)為軌跡序列在非敏感信息下存在隱私泄露風(fēng)險時，則數(shù)據(jù)集全部抑制該違反序列，造成很多時序序列被錯誤抑制；TP-NSA算法則將非敏感信息當(dāng)作違反序列元組一部分，只對數(shù)據(jù)集中包含相同非敏感信息的軌跡進行抑制處理，保證時序序列的低損失率；相比Trad-Local算法，軌跡數(shù)據(jù)集的高維性使得違反序列集合的相當(dāng)龐大，時序序列被抑制的個數(shù)增多，MFS損失率最高。

圖2 MFS損失vs.K (L=3)

圖3表示參數(shù)L對實例損失和MFS損失的影響。實驗中固定K=30，S=800，參數(shù)L的取值從1增加到5。

圖3 實用性損失vs.L (K=30,S=800)

從圖3可以看出：實例損失率和MFS損失率隨著參數(shù)L的遞增而遞增。L的遞增導(dǎo)致存在隱私泄露的違反序列元組越來越多，被抑制的序列越來越多，導(dǎo)致實例損失率和MFS損失率遞增。由對比實驗可以看出，TP-NSA算法的實例損失率和MFS損失率低于LKC-Local算法。當(dāng)L比較小時違反序列很少，由于MVS集合相同造成兩種算法在實例損失率和MFS損失率相等；而隨著L的遞增，違反序列個數(shù)逐漸遞增，非敏感信息的限制有效減少了數(shù)據(jù)集實例的抑制個數(shù)，使得TP-NSA算法在實例損失率和MFS損失率上低于LKC-Local算法。

4 結(jié)語

本文基于攻擊者背景知識的實際假設(shè)，針對使用用戶移動軌跡和非敏感信息進行數(shù)據(jù)挖掘以提供社交推薦服務(wù)會對高維軌跡數(shù)據(jù)集發(fā)布造成用戶隱私泄露的問題，提出了一種基于非敏感信息分析的軌跡數(shù)據(jù)隱私保護發(fā)布算法——TP-NSA算法。該算法引入LQK-隱私模型來獲取軌跡數(shù)據(jù)集在非敏感信息限制下可能存在隱私泄露的軌跡序列，并采用局部抑制和全局抑制相結(jié)合的操作消除違反序列元組，實現(xiàn)軌跡數(shù)據(jù)集K-匿名。實驗結(jié)果表明，TP-NSA算法在實例損失率和MFS損失率上優(yōu)于LKC-Local算法和Trad-Local算法。下一階段的研究工作是對隱私保護的發(fā)布數(shù)據(jù)集進行數(shù)據(jù)挖掘，幫助服務(wù)提供商更好地為用戶提供個性化推薦服務(wù)，同時盡可能實現(xiàn)推薦服務(wù)過程中的隱私保護。

References)

[1] KONSTAS I, STATHOPOULOS V, JOSE J M.On social networks and collaborative recommendation [C]// SIGIR ’09: Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval.New York: ACM, 2009: 195-202.

[2] MA H, ZHOU D, LIU C, et al.Recommender systems with social regularization [C]// WSDM ’11: Proceedings of the 4th ACM International Conference on Web Search and Data Mining.New York: ACM, 2011: 287-296.

[3] YE M, YIN P, LEE W-C, et al.Exploiting geographical influence for collaborative point-of-interest recommendation [C]// Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval.New York: ACM, 2011: 325-334.

[4] LIU B, HENGARTNER U.Privacy-preserving social recommendations in geosocial networks [C]// PST 2013: Proceedings of the 11th International Conference on Privacy, Security and Trust.Washington, DC: IEEE Computer Society, 2013: 1-21.

[5] 霍崢,孟小峰,黃毅.PrivateCheckIn: 一種移動社交網(wǎng)絡(luò)中的軌跡隱私保護方法[J].計算機學(xué)報,2013,36(4):716-726.(HUO Z, MENG X F, HUANG Y.PrivateCheckIn: trajectory privacy preserving for check-in services in MSNS[J].Chinese Journal of Computers, 2013, 36(4): 716-726.)

[6] SWEENEY L.k-anonymity: a model for protecting privacy [J].International Journal of Uncertainty Fuzziness and Knowledge Based Systems, 2002, 10(5): 557-570.

[7] 霍崢,孟小峰.軌跡隱私保護技術(shù)研究[J].計算機學(xué)報,2011,34(10):1820-1830.(HUO Z, MENG X F.A survey of trajectory privacy preserving techniques [J].Chinese Journal of Computers, 2011, 34(10): 1820-1830.)

[8] ABUL O, BONCHI F, NANNI M.Never walk alone: uncertainty for anonymity in moving objects databases [C]// ICDE ’08: Proceedings of the 2008 IEEE 24th International Conference on Data Engineering.Washington, DC: IEEE Computer Society, 2008: 376-385.

[9] YAROVOY R, BONCHI F, LAKSHMANAN L V S, et al.Anonymizing moving objects: how to hide a MOB in a crowd? [C]// EDBT ’09: Proceedings of the 12th International Conference on Extending Database Technology:Advances in Database Technology.New York: ACM, 2009: 72-83.

[10] NERGIZ M E, ATZORI M, SAYGIN Y, et al.Towards trajectory anonymization: a generalization-based approach [C]// SPRINGL ’08: Proceedings of the SIGSPATIAL ACM GIS 2008 International Workshop on Security and Privacy in GIS and LBS.New York: ACM, 2008: 52-61.

[11] TERROVITIS M, MAMOULIS N.Privacy preservation in the publication of trajectories [C]// MDM ’08: Proceedings of the 9th International Conference on Mobile Data Management.Piscataway, NJ: IEEE, 2008: 65-72.

[12] 袁冠,夏士雄,張磊,等.基于結(jié)構(gòu)相似度的軌跡聚類算法[J].通信學(xué)報,2011, 32(9):103-110.(YUAN G,XIA S X,ZHANG L, et al.Trajectory clustering algorithm based on structural similarity [J].Journal on Communications, 2011, 32(9): 103-110.)

[13] MANO K, MINAMI K, MARUYAMA H.Pseudonym exchange for privacy-preserving publishing of trajectory data set [C]// GCCE 2014: Proceedings of the 3rd IEEE Global Conference on Consumer Electronics.Piscataway, NJ: IEEE, 2014: 691-695.

[14] HUO Z, MENG X, HU H, et al.You can walk alone: trajectory privacy-preserving through significant stays protection [C]// Proceedings of the 17th International Conference on Database Systems for Advanced Applications, LNCS 7238.Berlin: Springer-Verlag, 2012: 351-366.

[15] MOHAMMED N, FUNG B C M, DEBBABI M.Preserving privacy and utility in RFID data publishing, Technical Report 6850 [R].Montreal, Canada: Concordia University, 2010.

[16] CHEN R, FUNG B C M, MOHAMMED N, et al.Privacy-preserving trajectory data publishing by local suppression [J].Information Sciences, 2013, 231(1): 83-97.

[17] AL-HUSSAENI K, FUNG B C M, CHEUNG W K.Privacy-preserving trajectory stream publishing [J].Data & Knowledge Engineering, 2014, 94(Part A): 89-109.

[18] GHASEMZADEH M, FUNG B C M, CHEN R, et al.Anonymizing trajectory data for passenger flow analysis [J].Transportation Research Part C: Emerging Technologies, 2014, 39(2): 63-79.

[19] KOMISHANI E G, ABADI M.A generalization-based approach for personalized privacy preservation in trajectory data publishing [C]// IST ’12: Proceedings of the 2012 IEEE Sixth International Symposium on Telecommunications.Piscataway, NJ: IEEE, 2012: 1129-1135.

[20] MOHAMMED N, FUNG B, HUNG P C K, et al.Anonymizing healthcare data: a case study on the blood transfusion service [C]// KDD ’09: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York: ACM, 2009: 1285-1294.

[21] FUNG B C M, WANG K, YU P S, Anonymizing classification data for privacy preservation [J].IEEE Transactions on Knowledge and Data Engineering, 2007, 19(5): 711-725

[22] DeWITT D J, LeFEVRE K, RAMAKRISHNAN R.Mondrian multidimensionalk-anonymity [C]// SIGMOD ’06: Proceedings of the 22nd IEEE International Conference on Data Engineering.Washington, DC: IEEE Computer Society, 2006: 25.

[23] XIAO X, TAO Y.Personalized privacy preservation [C] // Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data.New York: ACM, 2006: 229-240.

[24] BURDICK D, CALIMLIM M, GEHRKE J.MAFIA: a maximal frequent itemset algorithm for transactional databases [C]// Proceedings of the 17th IEEE International Conference on Data Engineering.Piscataway, NJ: IEEE, 2001: 443-452.

This work is partially supported by the National Natural Science Foundation of China (61370050,61672039), the Natural Science Foundation of Anhui Province (1508085QF134).

DENG Jingsong, born in 1991, M.S.candidate.His research interests include information security, privacy preseving.

LUO Yonglong, born in 1972, Ph.D., professor.His research interests include spatial data processing, information security, privacy preseving.

YU Qingying, born in 1980, Ph.D.candidate, lecturer.Her research interests include spatial data processing, information security.

CHEN Fulong, born in 1978, Ph.D., professor.His research interests include embedded computing and pervasive computing, cyber-physical system, high-performance computer architecture.

Privacy-preserving trajectory data publishing based on non-sensitive information analysis

DENG Jingsong1*, LUO Yonglong1,2,YU Qingying1,2,CHEN Fulong1,2

(1.SchoolofMathematicsandComputerScience,AnhuiNormalUniversity,WuhuAnhui241003,China;2.EngineeringTechnologyResearchCenterofNetworkandInformationSecurity,AnhuiNormalUniversity,WuhuAnhui241003,China)

Focusing on the issue of privacy disclosure between trajectory and non-sensitive information, a trajectory privacy preserving algorithm based on non-sensitive information analysis was proposed.Firstly, the correlation between trajectory and non-sensitive information was analyzed to build trajectory privacy disclosure decision model, and the Minimal Violating Sequence tuple (MVS) was gotten.Secondly, using common subsequences, the doublets with the minimal loss of trajectory data in MVS were selected as the suppression objects when removing the privacy risks caused by MVS, then the anonymized trajectory dataset with privacy and low data loss was obtained.In the comparison experiments with LKC-Local algorithm and Trad-Local algorithm, when the sequence length is 3, the average instance loss of the proposed algorithm is decreased by about 6% and 30% respectively, and the average MFS (Maximal Frequent Sequence) loss is decreased by about 7% and 60% respectively.The experimental results verify that the proposed algorithm can effectively improve the quality of recommend service.

privacy-preserving; high-dimensional trajectory data; non-sensitive information; common subsequence; sequence-suppression

2016- 07- 22;

2016- 09- 05。

國家自然科學(xué)基金資助項目(61370050, 61672039)；安徽省自然科學(xué)基金資助項目(1508085QF134)。

鄧勁松(1991—),男,安徽合肥人,碩士研究生,主要研究方向:信息安全、隱私保護; 羅永龍(1972—),男,安徽太湖人,教授,博士生導(dǎo)師,博士,CCF會員,主要研究方向:空間數(shù)據(jù)處理、信息安全、隱私保護; 俞慶英(1980—),女,安徽黃山人,講師,博士研究生,CCF會員,主要研究方向:空間數(shù)據(jù)處理、信息安全; 陳付龍(1978—),男,安徽霍邱人,教授,博士,CCF會員,主要研究方向:嵌入式和普適計算、信息物理融合系統(tǒng)、高性能計算機體系結(jié)構(gòu)。

1001- 9081(2017)02- 0488- 06

10.11772/j.issn.1001- 9081.2017.02.0488

TP

A