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

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

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

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

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

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

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

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

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

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

0 引言

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

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

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

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

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

1.1 相關(guān)定義

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

定義4 軌跡數(shù)據(jù)。軌跡數(shù)據(jù)是移動(dòng)用戶所有個(gè)人信息的集合。通常情況下，軌跡數(shù)據(jù)表示為T(mén)r=(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-隱私模型

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

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

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

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

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

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

(1)

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

(2)

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

2 隱私保護(hù)算法

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

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

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

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

證畢。

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

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

證畢。

2.2 TP-NSA算法描述

2.2.1 最小違反序列元組獲取

在獲取數(shù)據(jù)集各非敏感信息下存在隱私泄露的違反序列元組時(shí)，由于LKC-Local算法[16]提出的MVS生成子算法并沒(méi)有將非敏感信息當(dāng)成違反序列一部分，而且若對(duì)每個(gè)非敏感信息進(jìn)行一次數(shù)據(jù)集掃描，花費(fèi)時(shí)間代價(jià)較大。因此，本文基于文獻(xiàn)[16]的MVS生成子算法框架提出改進(jìn)的MVS生成算法(具體見(jiàn)算法1)：首先將非敏感信息相同的軌跡放在同一個(gè)等價(jià)類(lèi)Tns中(見(jiàn)算法1第2)～9)行)，用于算法的后續(xù)操作，從而保證對(duì)所有非敏感信息進(jìn)行掃描操作次數(shù)總和為數(shù)據(jù)集記錄個(gè)數(shù)，減少掃描花費(fèi)時(shí)間。然后根據(jù)定義6對(duì)各等價(jià)類(lèi)Tns進(jìn)行掃描判斷：若在違反序列候選集合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 匿名化處理

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

算法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;

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

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

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

算法3AnonymityProcessing。

輸入Tec，MMVS，suppression_way，Weight_Table；

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

1)

T′←?;

2)

whileWeight_Table≠ ?do

/*迭代抑制各時(shí)序序列*/

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算法時(shí)間復(fù)雜度由兩部分組成。第一部分是獲取數(shù)據(jù)集中違反序列元組集合，這部分花費(fèi)時(shí)間的操作是掃描數(shù)據(jù)集判斷軌跡序列在各非敏感信息下的隱私泄露風(fēng)險(xiǎn)，由于軌跡數(shù)據(jù)集中軌跡序列候選集合大小為O(|d|2)[15]，算法1對(duì)各軌跡序列在各非敏感信息下進(jìn)行掃描操作的時(shí)間復(fù)雜度為O(|d|2|T|)，其中|d|為軌跡數(shù)據(jù)集的維數(shù)，|T|為軌跡數(shù)據(jù)集的記錄數(shù)。第二部分是對(duì)算法1產(chǎn)生的MVS集合進(jìn)行抑制處理，假設(shè)算法1產(chǎn)生的MVS集合大小為O(N)，算法3執(zhí)行次數(shù)為O(M)，每個(gè)MVS包含于軌跡集合的平均個(gè)數(shù)為O(L)，則算法3每次抑制操作消除MVS個(gè)數(shù)為O(N/M)，花費(fèi)時(shí)間為O(L/MN2)。考慮判斷時(shí)序序列在非敏感信息下的局部抑制有效性的時(shí)間復(fù)雜度為O(N|T|)[16]，因此，TP-NSA算法的總時(shí)間復(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ìn)行等價(jià)類(lèi)劃分，能縮短算法掃描花費(fèi)時(shí)間；在序列抑制操作時(shí)，采用公共子序列的思想，能降低數(shù)據(jù)實(shí)例的抑制數(shù)量。

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

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

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

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

(3)

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

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

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

(4)

其中，U(T)和U(T′)分別表示原始軌跡數(shù)據(jù)集MFS總數(shù)和匿名軌跡數(shù)據(jù)集MFS總數(shù)。MFS損失越小，表明基于MFS進(jìn)行數(shù)據(jù)挖掘?yàn)橛脩籼峁┩扑]服務(wù)的質(zhì)量越高，用戶滿意度越高。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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

3.2 實(shí)驗(yàn)結(jié)果與分析

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

圖1 實(shí)例損失(L=3)

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

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: 一種移動(dòng)社交網(wǎng)絡(luò)中的軌跡隱私保護(hù)方法[J].計(jì)算機(jī)學(xué)報(bào),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] 霍崢,孟小峰.軌跡隱私保護(hù)技術(shù)研究[J].計(jì)算機(jī)學(xué)報(bào),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)相似度的軌跡聚類(lèi)算法[J].通信學(xué)報(bào),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。

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

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

1001- 9081(2017)02- 0488- 06

10.11772/j.issn.1001- 9081.2017.02.0488

TP

A