金凱忠,彭慧麗,張嘯劍

(河南財(cái)經(jīng)政法大學(xué) 計(jì)算機(jī)與信息工程學(xué)院, 鄭州 450002) (*通信作者電子郵箱xjzhang82@ruc.edu.cn)

基于差分隱私的軌跡模式挖掘算法

金凱忠,彭慧麗,張嘯劍*

(河南財(cái)經(jīng)政法大學(xué) 計(jì)算機(jī)與信息工程學(xué)院, 鄭州 450002) (*通信作者電子郵箱xjzhang82@ruc.edu.cn)

針對(duì)現(xiàn)有基于差分隱私的頻繁軌跡模式挖掘算法全局敏感度過高、挖掘結(jié)果可用性較低的問題，提出一種基于前綴序列格和軌跡截?cái)嗟牟罘蛛[私下頻繁軌跡模式挖掘算法——LTPM。該算法首先利用自適應(yīng)的方法獲得最優(yōu)截?cái)嚅L(zhǎng)度，然后采用一種動(dòng)態(tài)規(guī)劃的策略對(duì)原始數(shù)據(jù)庫(kù)進(jìn)行截?cái)嗵幚?，在此基礎(chǔ)上，利用等價(jià)關(guān)系構(gòu)建前綴序列格，并挖掘頻繁軌跡模式。理論分析表明LTPM算法滿足ε-差分隱私；實(shí)驗(yàn)結(jié)果表明，LTPM算法的準(zhǔn)確率(TPR)和平均相對(duì)誤差(ARE)明顯優(yōu)于N-gram和Prefix算法，能有效提高挖掘結(jié)果的可用性。

差分隱私;隱私保護(hù);頻繁模式挖掘;軌跡截?cái)?前綴序列格

0 引言

位置獲取技術(shù)的興起和互聯(lián)網(wǎng)技術(shù)的蓬勃發(fā)展產(chǎn)生了大量的軌跡數(shù)據(jù),例如車輛、人的位置信息、用戶行為信息。在軌跡數(shù)據(jù)上挖掘頻繁模式,其目的是找出頻繁出現(xiàn)在數(shù)據(jù)中的模式,是關(guān)聯(lián)規(guī)則、相關(guān)性分析、分類、聚類和其他數(shù)據(jù)挖掘任務(wù)的基礎(chǔ),被廣泛應(yīng)用于用戶行為分析、交通規(guī)劃、推薦系統(tǒng)等領(lǐng)域。然而從敏感數(shù)據(jù)庫(kù)例如位置信息中乘客乘車和下車點(diǎn)信息、互聯(lián)網(wǎng)用戶點(diǎn)擊流信息中挖掘出的頻繁模式本身的內(nèi)容以及支持度計(jì)數(shù)信息都有可能泄露個(gè)人隱私信息或者披露個(gè)人的真實(shí)身份。攻擊者獲得某些模式的支持度計(jì)數(shù)之后,可以利用額外的背景知識(shí)進(jìn)行攻擊。例如表1中b表示某一敏感位置,攻擊者想竊取“Tom是否去過b位置”這種信息。通過分析獲知b為頻繁模式,其真實(shí)支持度計(jì)數(shù)為5。如果攻擊者已經(jīng)知道其他4人去過b位置,則可推理出Tom也去過b位置,進(jìn)而導(dǎo)致Tom的敏感位置泄露。因此,在挖掘頻繁模式的過程中,如何保護(hù)模式的支持度計(jì)數(shù)是主要的技術(shù)挑戰(zhàn)。

近年來，出現(xiàn)了幾種差分隱私保護(hù)下的模式挖掘算法[1-5],文獻(xiàn)[6]為了解決事務(wù)數(shù)據(jù)庫(kù)高維度的難題,將高維度的數(shù)據(jù)庫(kù)轉(zhuǎn)化為低維度,結(jié)合θ-基和映射技術(shù)提出了PrivBasis算法,根據(jù)θ-頻繁對(duì)構(gòu)建出候選集合,最后對(duì)候選集合的所有項(xiàng)的頻度添加噪聲,而后選取top-k頻繁模式。

表1 軌跡數(shù)據(jù)庫(kù)

文獻(xiàn)[8]結(jié)合自頂向下的前綴樹,第一次提出了發(fā)布軌跡數(shù)據(jù)庫(kù)的Prefix算法,支持頻繁模式挖掘。該算法對(duì)序列模式對(duì)應(yīng)的真實(shí)支持度計(jì)數(shù)添加拉普拉斯噪聲,構(gòu)建前綴序列樹,最終發(fā)布滿足差分隱私的軌跡數(shù)據(jù)庫(kù)。文獻(xiàn)[9]提出的N-gram算法為了降低序列維度的影響,限制序列的最大長(zhǎng)度為lmax。上述幾種算法通過降低序列的維度或限制序列的最大長(zhǎng)度來提高挖掘結(jié)果的可用性,然而這些算法存在以下問題:

問題1 PrivBasis算法和N-gram算法雖然考慮到序列維度的影響,但是仍然存在全局敏感度過高的問題；而且PrivBasis和N-gram算法僅適用于短序列居多的數(shù)據(jù)庫(kù)，Prefix和N-gram算法限制序列長(zhǎng)度的算法存在較大的信息損失。

問題2 從大規(guī)模軌跡數(shù)據(jù)庫(kù)中挖掘頻繁模式時(shí),常常會(huì)產(chǎn)生大量滿足最小支持度閾值的序列集合,序列冗余較嚴(yán)重,而且上述算法均沒有設(shè)計(jì)一種比較好的隱私預(yù)算的分配策略,導(dǎo)致添加的噪聲量很大,從而造成挖掘結(jié)果可用性低下。

總而言之,目前還沒有一種很有效的頻繁軌跡模式挖掘算法能夠同時(shí)兼顧上述兩個(gè)問題,提高挖掘結(jié)果的可用性,為此,本文提出一種融合軌跡截?cái)嗪颓熬Y序列格的頻繁軌跡模式挖掘算法——LTPM(Lattice-Trajectory Pattern Mining)。首先,在滿足差分隱私的前提下,利用自適應(yīng)的方法獲取最優(yōu)截?cái)嚅L(zhǎng)度,接下來采用動(dòng)態(tài)規(guī)劃策略對(duì)軌跡數(shù)據(jù)庫(kù)進(jìn)行截?cái)嗵幚?然后基于前綴序列格結(jié)構(gòu)壓縮頻繁軌跡模式,避免隱私預(yù)算重復(fù)分配。

本文的主要工作:

1)為了解決問題1,本文基于動(dòng)態(tài)規(guī)劃策略提出一種滿足差分隱私的軌跡序列截?cái)嗨惴―P_Trunc,在有效降低全局敏感度的同時(shí),減少截?cái)嗨惴◣淼恼`差。

2)為了解決問題2,提出基于前綴序列格的頻繁軌跡模式挖掘算法LTPM,借鑒Clospan算法[13]思想,利用軌跡模式間的等價(jià)關(guān)系有效壓縮頻繁軌跡模式規(guī)模,減少序列冗余,避免隱私預(yù)算的重復(fù)分配。

3)理論分析了LTPM算法滿足ε-差分隱私,通過真實(shí)數(shù)據(jù)庫(kù)上的實(shí)驗(yàn)結(jié)果表明,LTPM在數(shù)據(jù)可用性方面優(yōu)于N-gram算法和Prefix算法。

1 相關(guān)工作

滿足差分隱私的頻繁模式挖掘的研究已取得很多成果。文獻(xiàn)[5]利用拉普拉斯機(jī)制[3]和指數(shù)機(jī)制[4]提出兩種差分隱私下頻繁模式挖掘算法,從固定長(zhǎng)度的模式中選取支持度最大的k個(gè)模式,并對(duì)其添加噪聲作為top-k頻繁模式,但是該算法受k值的影響比較大。文獻(xiàn)[6]為了解決事務(wù)數(shù)據(jù)庫(kù)高維度的難題,將高維度的數(shù)據(jù)庫(kù)轉(zhuǎn)化為低維度,結(jié)合θ-基和映射技術(shù)提出了PrivBasis算法,根據(jù)θ-頻繁對(duì)構(gòu)建出候選集合,最后對(duì)候選集合的所有項(xiàng)的頻度添加噪聲,而后選取top-k頻繁模式。該算法適用于k值比較小的情況,當(dāng)k比較大時(shí),該算法的可用性會(huì)很低。文獻(xiàn)[7]分析了事務(wù)長(zhǎng)度對(duì)全局敏感度的影響,發(fā)現(xiàn)數(shù)據(jù)庫(kù)中記錄的最大長(zhǎng)度與全局敏感度成正比,為此提出一種基于事務(wù)截?cái)嗟乃惴⊿mart Trunc來限制事務(wù)數(shù)據(jù)庫(kù)的長(zhǎng)度,并通過雙重標(biāo)準(zhǔn)降低截?cái)嗨惴◣淼恼`差,進(jìn)而提高挖掘算法的可用性。該算法應(yīng)用在短事務(wù)居多的事務(wù)數(shù)據(jù)庫(kù)性能較高,而在其他數(shù)據(jù)庫(kù)中性能較差；并且該算法不支持頻繁序列挖掘。文獻(xiàn)[8]結(jié)合自頂向下的前綴樹,第一次提出了發(fā)布軌跡數(shù)據(jù)庫(kù)的Prefix算法,支持頻繁序列挖掘。該算法對(duì)序列模式對(duì)應(yīng)的真實(shí)支持度計(jì)數(shù)添加拉普拉斯噪聲,構(gòu)建前綴序列樹,最終發(fā)布滿足差分隱私的軌跡數(shù)據(jù)庫(kù)；但隨著前綴序列樹的增長(zhǎng),每一子分割的序列數(shù)量會(huì)急劇減小,嚴(yán)重影響發(fā)布序列的可用性。文獻(xiàn)[9]提出的N-gram算法為了降低序列維度的影響,限制序列的最大長(zhǎng)度為lmax。該算法應(yīng)用在短事務(wù)居多的數(shù)據(jù)庫(kù)時(shí)精度較高，但對(duì)于長(zhǎng)序列居多的數(shù)據(jù)庫(kù)，其可用性比較差,而且存在較多的信息丟失。文獻(xiàn)[10]在設(shè)計(jì)DP-FIM(Differential Privacy Frequent Itemset Mining)時(shí),考慮到長(zhǎng)事務(wù)數(shù)據(jù)處理導(dǎo)致信息損失和效率低下的問題,提出了包含智能權(quán)重截取和支持度評(píng)估的DP Apriori算法。文獻(xiàn)[11]提出了一個(gè)頻繁序列挖掘算法PFS2,其核心是利用一個(gè)基于采樣的候選剪枝技術(shù)來減小候選序列的數(shù)目,并使用候選序列在樣本數(shù)據(jù)庫(kù)中的局部噪聲支持度來估計(jì)該序列是否頻繁。該算法未考慮不同候選序列重要程度的差異性,導(dǎo)致挖掘結(jié)果可用性低下。文獻(xiàn)[12]提出的DiffPart算法基于上下文無(wú)關(guān)分類樹,自頂向下從根節(jié)點(diǎn)開始迭代地進(jìn)行子分割并生成葉子節(jié)點(diǎn),再根據(jù)葉子節(jié)點(diǎn)的噪聲計(jì)數(shù)重構(gòu)并發(fā)布擾動(dòng)后的集值型數(shù)據(jù)庫(kù),支持頻繁模式挖掘。DiffPart算法發(fā)布精度高,但僅支持計(jì)數(shù)查詢,未考慮不同項(xiàng)之間的語(yǔ)義關(guān)系。

綜上所述,上述算法均存在各自的不足,為此本文提出一種融合軌跡截?cái)嗪颓熬Y序列格的頻繁軌跡模式挖掘算法LTPM,以有效降低全局敏感度,提高挖掘結(jié)果的可用性。

2 定義和概念

2.1 差分隱私

相對(duì)于傳統(tǒng)保護(hù)模型,差分隱私保護(hù)模型具有兩個(gè)顯著的特點(diǎn):1)定義了一個(gè)相當(dāng)嚴(yán)格的攻擊模型,不關(guān)心攻擊者擁有多少背景知識(shí)。假設(shè)攻擊者已掌握除某一條記錄之外的所有記錄信息,該攻擊者也無(wú)法從統(tǒng)計(jì)結(jié)果中推測(cè)出這條記錄是否存在于數(shù)據(jù)集中。2)對(duì)隱私保護(hù)水平給出了嚴(yán)格的定義和定量分析評(píng)估方法。

定義1 近鄰關(guān)系。設(shè)T={t1,t2, …,tn}為原始軌跡數(shù)據(jù)庫(kù),T′={t1,t2,…,tr-1,tr+1, …,tn},T與T′相差一條記錄,則二者互為近鄰關(guān)系。

結(jié)合T與T′給出ε-差分隱私的形式化定義,如定義2所示:

定義2ε-差分隱私。給定一個(gè)軌跡模式挖掘算法A,Range(A)為A的輸出范圍,若算法A在T與T′上任意輸出結(jié)果O(O∈Range(A))滿足式(1),則A滿足ε-差分隱私。

Pr[A(T)=O]≤exp(ε)×Pr[A(T′)=O]

(1)

其中:ε表示隱私預(yù)算,用于衡量差分隱私保護(hù)的強(qiáng)度,其值越小則算法A的隱私保護(hù)程度越高。實(shí)現(xiàn)差分隱私保護(hù)需要噪聲機(jī)制的介入,拉普拉斯與指數(shù)機(jī)制是實(shí)現(xiàn)差分隱私的主要技術(shù)。而所需要的噪聲大小與其響應(yīng)查詢函數(shù)f的全局敏感性密切相關(guān)。

定義3 全局敏感性。設(shè)f為某一個(gè)查詢,且f:T→Rd,f的全局敏感性為:

(2)

其中:R為映射的實(shí)數(shù)空間；d為f的查詢維度。

文獻(xiàn)[3]提出的拉普拉斯機(jī)制可以取得差分隱私保護(hù)效果,該機(jī)制利用拉普拉斯分布產(chǎn)生噪聲,進(jìn)而使得頻繁軌跡模式挖掘算法滿足ε-差分隱私,如定理1所示。

定理1[3]設(shè)f為某個(gè)查詢函數(shù),且f:T→Rd,若算法A符合下列等式,則A滿足ε-差分隱私。

A(T)=f(T)+〈lap(Δf/ε)〉n

(3)

其中:lap(Δf/ε)為相互獨(dú)立的拉普拉斯噪聲變量,噪聲量大小與Δf成正比,與ε成反比。因此,查詢f的全局敏感性越大,所需的噪聲越多。

2.2 頻繁軌跡模式挖掘

軌跡數(shù)據(jù)是具有時(shí)間戳的按照時(shí)間先后排序的序列數(shù)據(jù),例如空間軌跡數(shù)據(jù),每個(gè)位置可表示成一個(gè)三元組〈xi,yi,wi〉,則一條軌跡序列t可表示為t={(x1,y1,w1),(x2,y2,w2),…,(xn,yn,wn)},其中:w1lt;wilt;wn;xi和yi表示二維地理空間中的位置點(diǎn)信息,在全球定位系統(tǒng)(Global Positioning System, GPS)系統(tǒng)中xi和yi分別對(duì)應(yīng)于地理空間經(jīng)度與緯度數(shù)據(jù);wi為xi和yi位置的時(shí)間戳信息,且1lt;ilt;n,wilt;wi+1。根據(jù)北京公交車軌跡Geolife數(shù)據(jù),畫出15條軌跡序列,其可視化結(jié)果如圖1所示。

圖1 軌跡序列可視化結(jié)果

給定軌跡數(shù)據(jù)庫(kù)T,|T|表示數(shù)據(jù)庫(kù)大小,字符表τ={i1,i2,…,in}是所有項(xiàng)的集合。例如,表1包含5條軌跡序列,其中每一條軌跡序列記錄按照時(shí)間先后排序。軌跡模式是否頻繁,取決于模式的支持度與最小支持度閾值的關(guān)系,頻繁軌跡模式挖掘的任務(wù)就是在軌跡數(shù)據(jù)庫(kù)中找出所有大于最小支持度閾值的軌跡序列。

定義4[13]閉頻繁軌跡模式(CS)。如果不存在真超模式Y(jié),使得Y與X在軌跡數(shù)據(jù)庫(kù)T中有相同的支持度計(jì)數(shù),則稱X在軌跡數(shù)據(jù)庫(kù)T中是閉的,如果X是頻繁模式,則X就為閉頻繁軌跡模式。

定義5[13]等價(jià)關(guān)系。給定2個(gè)軌跡序列s和s′,若等價(jià)當(dāng)且僅當(dāng)s′?s或s?s′且|Ds|=|Ds′|。其中Ds表示以s為前綴的子序列中出現(xiàn)的所有項(xiàng)的集合。

從大規(guī)模數(shù)據(jù)庫(kù)中挖掘頻繁軌跡模式常常產(chǎn)生大量滿足最小支持度計(jì)數(shù)閾值的模式集,序列冗余較嚴(yán)重。為了克服這一缺陷,添加等價(jià)關(guān)系,引入閉頻繁軌跡模式，使得在具有更少軌跡模式的同時(shí)包含完整的信息。

圖2 前綴序列樹

本文利用前綴序列格結(jié)構(gòu)挖掘頻繁軌跡模式,格結(jié)構(gòu)是一種層次數(shù)據(jù)結(jié)構(gòu),格中第i層節(jié)點(diǎn)代表的序列是第i-1層所有節(jié)點(diǎn)代表的序列排列組合的所有情況。前綴序列格和格結(jié)構(gòu)類似,不同的地方在于格中第i層節(jié)點(diǎn)代表的序列是第i-1層節(jié)點(diǎn)所代表序列通過序列擴(kuò)展得到,即第i-1序列是其第i層的孩子節(jié)點(diǎn)的前綴。前綴序列格基于前綴序列樹構(gòu)建。圖2就是針對(duì)表1代表的軌跡數(shù)據(jù)庫(kù)T,采用前綴序列樹結(jié)構(gòu)挖掘的結(jié)果,其中最小支持度閾值為1。掘頻繁軌跡模式的過程中,采用Clospan算法[13]思想,通過等價(jià)關(guān)系判斷,對(duì)前綴序列樹進(jìn)行子樹合并,得到前綴序列格。3.4節(jié)對(duì)前綴序列格的構(gòu)建作了詳細(xì)的說明。

3 基于差分隱私的頻繁軌跡模式挖掘算法

給定軌跡數(shù)據(jù)庫(kù)T,隱私預(yù)算ε,最小支持度閾值min_up,在設(shè)計(jì)滿足差分隱私的頻繁軌跡模式挖掘算法時(shí),需要考慮如下原則:

1)針對(duì)軌跡數(shù)據(jù)庫(kù)中長(zhǎng)序列會(huì)帶來很大的全局敏感度的問題,所設(shè)計(jì)的挖掘算法在滿足差分隱私的前提下,應(yīng)該能夠有效降低全局敏感度,同時(shí)保證較少的信息損失和高的數(shù)據(jù)可用性。

2)針對(duì)大規(guī)模軌跡數(shù)據(jù)庫(kù)頻繁模式挖掘會(huì)產(chǎn)生大量冗余序列的問題,所設(shè)計(jì)的算法在能夠包含完整的頻繁軌跡模式信息的前提下,盡量壓縮挖掘出的頻繁軌跡模式的規(guī)模。

針對(duì)原則1和原則2,本文提出一種基于軌跡截?cái)嗪颓熬Y序列格的軌跡模式挖掘算法LTPM。

3.1 LTPM算法實(shí)現(xiàn)

算法1 LTPM算法。

輸入 軌跡數(shù)據(jù)庫(kù)T,隱私預(yù)算ε,最小支持度閾值min_up。

輸出 頻繁軌跡序列模式FS。

1)

ε=ε1+ε2

2)

lopt← estimate_opt_length(T,ε1)

3)

for eachk(1≤k≤lopt) do

4)

T′← DP_Trunc(T,Sk-1,lopt)

//Sk為頻繁k-軌跡模式集合,初始化S0為空

5)

Sk← Gen_ Lattice(SL,T′,ε2,Sk-1,min_up,lopt)

//SL為前綴序列格,初始化SL為空

6)

FS← DFS(SL)

7)

ReturnFS

該算法主要包含三個(gè)過程:估計(jì)最優(yōu)截?cái)嚅L(zhǎng)度過程(行2))、截?cái)嘬壽E數(shù)據(jù)庫(kù)過程(行4)),構(gòu)建前綴序列格過程(行3)～5))。接下來分別詳細(xì)介紹上述三個(gè)過程。

3.2 最優(yōu)截?cái)嚅L(zhǎng)度選取

首先需要確定針對(duì)軌跡數(shù)據(jù)庫(kù)的最優(yōu)截?cái)嚅L(zhǎng)度lopt,為了滿足差分隱私,本文采用一種自適應(yīng)的方法確定lopt的大小,算法2描述了估計(jì)最優(yōu)截?cái)嚅L(zhǎng)度estimate_opt_length的實(shí)現(xiàn)過程。

算法2 estimate_opt_length算法。

輸入 軌跡數(shù)據(jù)庫(kù)T,隱私預(yù)算ε1。

輸出 最優(yōu)截?cái)嚅L(zhǎng)度lopt。

1)

z=〈z1,z2,…,zn〉,zi表示軌跡數(shù)據(jù)庫(kù)中長(zhǎng)度為i的個(gè)數(shù)

2)

z′=z+〈g1,g2,…,gn〉,其中g(shù)i從幾何分布G(ε1)隨機(jī)獲得

3)

行3)中η為常量,大多數(shù)真實(shí)軌跡數(shù)據(jù)庫(kù)序列長(zhǎng)度分布比較偏頗,因此本文選取η值為0.90。下面通過一個(gè)例子說明算法2的執(zhí)行過程。

例1 給定軌跡數(shù)據(jù)庫(kù)T如表1所示,則T長(zhǎng)度分布z=〈0,2,1,4〉,利用幾何機(jī)制加噪聲后z′=〈1,4,2,3〉,因?yàn)?1+4)/7lt;0.90,(1+4+2)/7gt;0.90,則選擇最優(yōu)截?cái)嚅L(zhǎng)度為2。

定理2 算法2滿足ε1-差分隱私。

證明 對(duì)于軌跡數(shù)據(jù)庫(kù)T,由于添加(刪除)一個(gè)輸入序列只影響T變化1,則這個(gè)計(jì)算的敏感度為1。因此,在計(jì)算時(shí)添加幾何噪聲G(ε1)滿足ε1-差分隱私。

基于上述最優(yōu)截?cái)嚅L(zhǎng)度lopt對(duì)軌跡數(shù)據(jù)庫(kù)進(jìn)行截?cái)嗵幚?截?cái)嘬壽E數(shù)據(jù)庫(kù)過程核心步驟為DP_Trunc算法。

3.3 軌跡截?cái)嗖呗?/h3>

3.3.1 全局敏感度分析

在軌跡數(shù)據(jù)上挖掘頻繁序列模式具有較高的全局敏感度。在滿足差分隱私的前提下,全局敏感度越大,添加的噪聲越大,數(shù)據(jù)的可用性越低。

定理3[7]計(jì)數(shù)全局敏感度。給定軌跡數(shù)據(jù)庫(kù)T,T中序列的最大長(zhǎng)度為lmax,查詢Q=[q1,q2,…,qn],用以查詢qi在數(shù)據(jù)庫(kù)T中的支持度,qi的序列長(zhǎng)度滿足qi∈I=[qmin,qmax],1≤qmin≤qmax,查詢Q的全局敏感度滿足:

ΔfQ=ΔI×lmax

ΔI=(qmax-qmin)+1

定理3表明,全局敏感度與軌跡數(shù)據(jù)的最大長(zhǎng)度lmax成正比,即使只有一個(gè)非常長(zhǎng)的序列存在于軌跡數(shù)據(jù)庫(kù),所有的頻繁軌跡模式的支持度都要添加非常大的噪聲。通過上述分析可知,降低軌跡數(shù)據(jù)的最大長(zhǎng)度,將降低全局敏感度,提高數(shù)據(jù)的可用性。

采用截?cái)嗟姆椒▽④壽E數(shù)據(jù)庫(kù)T轉(zhuǎn)換為T′后,希望頻繁軌跡模式的支持度不會(huì)發(fā)生變化或者變化很小。隨機(jī)截?cái)嘬壽E序列是最直接的方法,但顯然這種方法不可避免會(huì)造成很大的信息損失。在截?cái)噙^程中,如果一個(gè)頻繁軌跡模式被錯(cuò)誤地當(dāng)成非頻繁軌跡模式,它的所有超集都會(huì)被誤認(rèn)為非頻繁軌跡模式。例如軌跡序列t={a→b→c→d→e},序列{a→b}支持度計(jì)數(shù)為2,最小支持度閾值為2,隨機(jī)截?cái)嗪髏′={c→d→e},{a→b}支持度計(jì)數(shù)變?yōu)?,則{a→b}被誤認(rèn)為非頻繁的,根據(jù)向下閉包性質(zhì),{a→b}所有的超集都會(huì)被誤認(rèn)為非頻繁,這樣會(huì)造成很大的誤差,所以在截?cái)嘬壽E序列s時(shí),為了減少上述誤差,提高挖掘結(jié)果的可用性,需要找到一個(gè)最優(yōu)的截?cái)嗪蟮能壽E序列,以保證能夠保留那些足夠頻繁的軌跡序列。

3.3.2 動(dòng)態(tài)規(guī)劃軌跡截?cái)?/p>

為了表述更加確切,以下稱軌跡模式為軌跡序列。經(jīng)分析發(fā)現(xiàn),如果一個(gè)候選k-軌跡序列的所有子序列足夠頻繁的話,那么該k-軌跡序列很有可能是頻繁的。為了衡量哪些軌跡序列是足夠頻繁的,本文為每個(gè)軌跡序列定義一個(gè)權(quán)重,每個(gè)候選k-軌跡序列的權(quán)重等于它的所有子序列的噪聲支持度的和。

定義6 軌跡序列權(quán)重。給定頻繁(k-1)-軌跡序列集合Sk-1={s(k-1)1,s(k-1)2,…,s(k-1)n},則候選k-軌跡序列集合Ck的權(quán)重為:

(4)

其中:s(k-1)j.sup′表示頻繁軌跡序列s(k-1)j的噪聲支持度。

例2 軌跡序列t={a→b→c},頻繁2-軌跡序列{a→b}、{b→c}、{a→c}的噪聲支持度分別為2、3、4,t的子序列為{a→b}、{b→c},則軌跡序列t的權(quán)重為5。

根據(jù)上面的定義,軌跡序列t的最優(yōu)截?cái)鄦栴}可以表示為:

optimal(t′)=max(FW(t′))

(5)

在最優(yōu)截?cái)嚅L(zhǎng)度lopt給定的情況下,即找到一個(gè)長(zhǎng)度為lopt截?cái)嗪筌壽E序列t′,使得t′的權(quán)重最大。

基于上面的分析可知,當(dāng)軌跡序列規(guī)模很大的情況下,最優(yōu)截?cái)鄦栴}的搜索空間會(huì)非常大,而且在計(jì)算候選k-軌跡序列的權(quán)重時(shí),也許并不知道其(k-1)-子序列的噪聲支持度,只能依賴于現(xiàn)有的頻繁軌跡序列集合來指導(dǎo)截?cái)?。因?本文提出一種滿足差分隱私的軌跡截?cái)嗨惴―P_Trunc,該算法采用動(dòng)態(tài)規(guī)劃的思想,把多階段過程轉(zhuǎn)化為一系列單階段問題,利用各階段之間的關(guān)系進(jìn)行遞推,逐個(gè)求解。具體細(xì)節(jié)如算法3所示。

算法3 DP_Trunc算法。

輸入 軌跡數(shù)據(jù)庫(kù)T,頻繁(k-1)-序列集合Sk-1,最優(yōu)序列截?cái)嚅L(zhǎng)度lopt。

輸出 截?cái)嗪蟮能壽E數(shù)據(jù)庫(kù)T′。

1)

for eacht(t∈T) do

2)

Ck←Apriori(Sk-1)

3)

//獲得Ck中軌跡t包含的候選k-軌跡序列的集合

4)

for eachai(ai∈tand 1≤i≤t.length) do

5)

遞推方程:

FW[i]=max{FW[i],Suffix[ai]-Suffix[ai-lopt]}

6)

site← max(FW)

7)

t′←{asite-lopt+1,asite-lopt+2,…,asite}

/*從t的第site-lopt+1個(gè)位置開始截取長(zhǎng)度為lopt的連續(xù)序列t′ 并添加到T′*/

8)

ReturnT′

首先行2)利用Apriori算法[14]對(duì)Sk-1通過連接和剪枝操作獲得候選k-軌跡序列Ck,Ck中序列權(quán)重等于其對(duì)應(yīng)Sk-1中的子序列噪聲支持度累加和。該算法核心步驟是利用行5)的遞推方程從軌跡序列t中找到權(quán)重最大的子序列。

假設(shè)軌跡序列t={a1→a2,…,ai,…,a|t|},給定候選k-序列集合Ck,最優(yōu)截?cái)嚅L(zhǎng)度lopt,則根據(jù)式(4)～(5),要找的截?cái)嗪筌壽E序列t′滿足下面等式:

1≤j≤n-|t| (6)

從式(6)可以看出,問題的求解過程如果利用窮舉法,則時(shí)間復(fù)雜度為O(|T|n3),|T|為軌跡數(shù)據(jù)庫(kù)記錄條數(shù),利用動(dòng)態(tài)規(guī)劃的思想,通過一遍掃描軌跡序列t,遞歸地找到權(quán)重最大的子序列,可以將時(shí)間復(fù)雜度降為O(|T|n)。遞推公式如下:

FW[i]=max{FW[i],Suffix[ai]-Suffix[ai-lopt]}

(7)

其中：FW[i]表示以軌跡t中ai結(jié)尾且長(zhǎng)度為lopt的子序列權(quán)重和；Suffix[ai]表示以軌跡t中a1開頭且以ai結(jié)尾的子序列權(quán)重和。

例3 給定軌跡序列t={a→b→c→d→e},候選2-序列及其權(quán)重:{a→b}:8,{b→c}:12, {c→d}:15,{d→e}:18, 最優(yōu)截?cái)嚅L(zhǎng)度lopt=3。按照l(shuí)opt=3在t中選擇出連續(xù)的子序列有三種情況,分別為{a→b→c}、{b→c→d}、{c→d→e},從中選擇權(quán)重最大的子序列作為t的截?cái)嘈蛄小?/p>

首先計(jì)算Suffix[ai],遍歷軌跡t的每一項(xiàng)ai,得到向量v=(0,8,20,35,53),v中第i個(gè)元素即為Suffix[ai],則有Suffix[ai]-Suffix[ai-lopt]等于以ai開頭且長(zhǎng)度為lopt的子序列權(quán)重和。接下來可以將問題轉(zhuǎn)化為求v中長(zhǎng)度不超過3的最大連續(xù)子序列和問題。利用式(7),遞歸地更新向量v,最終得到結(jié)果v=(0,0,0,35,45),找出v中的最大值,對(duì)應(yīng)的下標(biāo)site=5即為截?cái)嗟哪┪参恢?然后從該位置向前截取長(zhǎng)度為lopt=3的連續(xù)序列,即得到最優(yōu)截?cái)嘈蛄衪′={c→d→e}。

3.4 構(gòu)建前綴序列格

構(gòu)建前綴序列格的具體實(shí)現(xiàn)細(xì)節(jié)見算法4。

算法4 Gen_Lattice算法。

輸入 截?cái)嘬壽E數(shù)據(jù)庫(kù)T′,隱私預(yù)算ε2,最優(yōu)截?cái)嚅L(zhǎng)度lopt,前綴序列格SL,最小支持度閾值min_up,頻繁(k-1)-序列Sk-1。

輸出 頻繁k-序列Sk。

1)

Ck←prefix_expend(Sk-1,T′)

//C1為軌跡數(shù)據(jù)庫(kù)所有不同的項(xiàng)

2)

3)

4)

ifk==1 then

5)

6)

ifc1i.sup′gt;min_upthen

7)

S1=S1∪c1i

8)

SL=SL+S1

//將S1添加到前綴序列格SL中

9)

else

10)

ifcki(cki?Ck) 與?s(k-1)i,?cki,s(k-1)i?Sk-1,cki?Ck存在等價(jià)關(guān)系 then

11)

修改前綴序列格指針指向,s(k-1)i父節(jié)點(diǎn)指向cki

12)

Ck=Ck-cki

13)

for eachcki(cki?Ck) do

14)

15)

ifbigt;min_upthen

16)

Sk=Sk∪bi

17)

SL=SL+Sk

//將Sk添加到SL中,并根據(jù)包含關(guān)系添加指針指向

18)

ReturnSk

該算法通過層序遍歷方式構(gòu)建前綴序列格。構(gòu)建過程如下:首先獲取頻繁1-軌跡序列,并創(chuàng)建節(jié)點(diǎn),然后通過上層節(jié)點(diǎn)得出后繼節(jié)點(diǎn),迭代構(gòu)建SL的每一層,構(gòu)建過程中某一節(jié)點(diǎn)是否要往下劃分,即是否產(chǎn)生后繼節(jié)點(diǎn)的條件為:1)是否滿足等價(jià)關(guān)系；2)層次是否超過lopt。

首先行1)根據(jù)頻繁(k-1)-軌跡序列Sk-1,掃描軌跡數(shù)據(jù)庫(kù)T′,獲得以Sk-1中軌跡序列為前綴的所有序列,即為Ck,例如,如圖2所示,已知頻繁軌跡序列S1={a,b,c},則候選軌跡序列集合為C2={a→b,a→c,b→a,b→c,c→a,c→b},接下來通過行5)～行8)以及行12)～行16)判斷cki(cki?Ck)是否頻繁,如果頻繁,則將cki及其噪聲支持度添加到頻繁軌跡序列Sk中。行10)～行12)通過等價(jià)關(guān)系判斷對(duì)前綴序列格進(jìn)行子樹合并操作,很大程度上減少了候選軌跡序列的規(guī)模。

隱私預(yù)算的分配采用均分的策略,通過層序方式構(gòu)建前綴序列格的過程中,每層分得的隱私預(yù)算為ε2/lopt,為了減少加入的噪聲量,同時(shí)避免隱私預(yù)算的重復(fù)分配,本文借鑒Clospan算法的思想,通過等價(jià)關(guān)系的判定來減少冗余序列,進(jìn)而提高Gen_Lattice算法的可用性,具體過程如例4所述。

例4 給定軌跡數(shù)據(jù)庫(kù)如表1所示,其前綴序列樹表示如圖2所示,為了更直觀地描述和表示,圖3(b)中每個(gè)節(jié)點(diǎn)用其所代表的頻繁軌跡序列表示。根據(jù)定義5可看出軌跡序列a→b與c→b存在等價(jià)關(guān)系以及b→a與c→a存在等價(jià)關(guān)系,圖3(a)表示的即是合并等價(jià)關(guān)系的過程,圖3(b)是在圖2的基礎(chǔ)上,通過合并等價(jià)關(guān)系得到的結(jié)果。合并前,a→b與c→b都需要添加噪聲,合并后,只需為a→b添加噪聲,同時(shí)以c→b為前綴的序列都不需要添加噪聲,同理只需為b→a與c→a添加一次噪聲即可,因此,通過等價(jià)關(guān)系合并軌跡序列,很大程度上壓縮了挖掘出的頻繁軌跡序列的規(guī)模,同時(shí)隱私預(yù)算得到了合理的分配。獲得前綴序列格后,通過深度優(yōu)先遍歷和回溯法,可得到所有的頻繁軌跡序列及其噪聲支持度,最終輸出滿足差分隱私的頻繁軌跡序列集合FS。

圖3 構(gòu)建前綴序列格過程

3.5 LTPM算法性能分析

3.5.1 算法隱私性分析

定理4 構(gòu)建前綴序列格過程滿足ε2-差分隱私。

定理5 LTPM算法滿足ε-差分隱私。

根據(jù)算法1描述,LTPM算法包含三個(gè)過程:估計(jì)最優(yōu)截?cái)嚅L(zhǎng)度過程(行2))、截?cái)嘬壽E數(shù)據(jù)庫(kù)過程(行4)),構(gòu)建前綴序列格過程(行3)～5)),截?cái)嘬壽E數(shù)據(jù)庫(kù)過程依賴于頻繁(k-1)-軌跡序列的噪聲支持度,所以不消耗隱私預(yù)算。根據(jù)定理2與定理4,以及結(jié)合差分隱私的順序性質(zhì)[15]可知,LTPM算法滿足(ε1+ε2)-差分隱私,即滿足ε-差分隱私。

3.5.2 算法復(fù)雜度分析

LTPM算法首先需要估計(jì)在軌跡數(shù)據(jù)庫(kù)T上的最優(yōu)截?cái)嚅L(zhǎng)度lopt,該過程只需遍歷一次軌跡數(shù)據(jù)庫(kù)T,因此時(shí)間復(fù)雜度為O(|T|)。截?cái)嘬壽E數(shù)據(jù)庫(kù)過程采用動(dòng)態(tài)規(guī)劃的策略,遞歸的找到每條軌跡數(shù)據(jù)庫(kù)記錄中權(quán)重最大的子序列,可以將時(shí)間復(fù)雜度降為O(|T|n),n為當(dāng)前候選軌跡序列集合的大小。構(gòu)建前綴序列格過程采用層序的方式,在構(gòu)建當(dāng)前層序列格過程中,需判斷候選軌跡序列集合中的頻繁軌跡序列,因此時(shí)間復(fù)雜度為O(n)。截?cái)嘬壽E數(shù)據(jù)庫(kù)和構(gòu)建前綴序列格過程需重復(fù)lopt次,所以最壞情況下,整個(gè)算法的時(shí)間復(fù)雜度為O(lopt|T|n)?；谇熬Y樹劃分的Prefix算法的時(shí)間復(fù)雜度為O(h|T|n),基于變長(zhǎng)模型的N-gram算法的時(shí)間復(fù)雜度為O(lmax|T|n)。由于lopt≤lmaxlt;h,則LPTM算法的性能較好。

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

實(shí)驗(yàn)平臺(tái)是4核Intel i7- 4790 CPU(4 GHz),8 GB內(nèi)存,Windows 7系統(tǒng)。所有算法均采用Python實(shí)現(xiàn)。實(shí)驗(yàn)采用4個(gè)真實(shí)軌跡數(shù)據(jù)庫(kù)BMS1[18]、MSNBC[19]、Kosarak[20]、Geolife(https://www.microsoft.com/en-us/download)。Geolife為空間軌跡數(shù)據(jù)庫(kù),MSNBC、Kosarak、BMS1為用戶行為軌跡數(shù)據(jù)庫(kù)。其中Geolife數(shù)據(jù)庫(kù)是微軟亞洲研究院從2007年4月—2012年8月收集的包含182個(gè)用戶、17 621條軌跡信息的數(shù)據(jù)庫(kù),每條軌跡記錄的是用戶的戶外運(yùn)動(dòng),包括日常生活,娛樂和體育活動(dòng)。在Geolife數(shù)據(jù)庫(kù)基礎(chǔ)上,選取北京市五環(huán)以內(nèi)的數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)庫(kù)。MSNBC數(shù)據(jù)庫(kù)是msnbc.com網(wǎng)站的點(diǎn)擊流數(shù)據(jù),每條記錄描述的是某個(gè)用戶一天之內(nèi)訪問的新聞頁(yè)面的軌跡,包含989 818條記錄,數(shù)據(jù)來源于UCI repository。Kosarak數(shù)據(jù)庫(kù)是匈牙利新聞門戶網(wǎng)站kosarak.org的點(diǎn)擊流數(shù)據(jù),包含990 002條記錄。BMS1數(shù)據(jù)庫(kù)是電子商務(wù)網(wǎng)站Gazelle.com幾個(gè)月的點(diǎn)擊流數(shù)據(jù),每條記錄描述的是用戶按照時(shí)間順序訪問的所有商品的軌跡,包含59 602條記錄。四種軌跡數(shù)據(jù)庫(kù)的具體特征與長(zhǎng)度分布分別如表2和圖4所示。

表2 實(shí)驗(yàn)數(shù)據(jù)庫(kù)的特征

圖4 數(shù)據(jù)庫(kù)長(zhǎng)度分布

圖5 截?cái)嗪髷?shù)據(jù)庫(kù)長(zhǎng)度分布

本文將LTPM和兩種滿足差分隱私的序列數(shù)據(jù)庫(kù)發(fā)布算法N-gram、Prefix進(jìn)行可用性比較。為了得到滿足差分隱私的頻繁軌跡模式,首先針對(duì)原始數(shù)據(jù)庫(kù)T,分別執(zhí)行N-gram和Prefix算法,獲得隱私數(shù)據(jù)庫(kù)T′,然后在T′上執(zhí)行頻繁序列挖掘算法PrefixScan[16],從而獲得頻繁軌跡模式。

結(jié)合上述四種數(shù)據(jù)庫(kù),本文采用準(zhǔn)確率(True Postive Rate, TPR)和平均相對(duì)誤差(Average Relative Error, ARE)衡量LTPM、N-gram、Prefix算法的可用性。

1)準(zhǔn)確率。該標(biāo)準(zhǔn)主要用來度量頻繁軌跡模式本身的可用性,計(jì)算公式如下:

(8)

根據(jù)公式可知TPR值越大,算法的可用性越高。

2)平均相對(duì)誤差。該標(biāo)準(zhǔn)主要用來度量頻繁軌跡模式支持度計(jì)數(shù)的可用性,公式如下:

(9)

本文實(shí)驗(yàn)隱私預(yù)算參數(shù)ε的取值為0.2、0.4、0.6、0.8、1.0,隱私預(yù)算的分配策略如下:ε1=0.1ε,ε2=0.9ε。最小支持度閾值min_up為相對(duì)閾值,即最小支持度閾值的取值隨著數(shù)據(jù)庫(kù)大小的不同而變化。每個(gè)算法分別執(zhí)行100次,并記錄輸出結(jié)果的平均值。分別通過固定隱私預(yù)算,改變最小支持度閾值大小和固定最小支持度閾值,改變隱私預(yù)算大小來比較LTPM、N-gram以及Prefix算法的準(zhǔn)確率和平均相對(duì)誤差,進(jìn)而比較四種算法的可用性。

1)固定ε=0.5,最小支持度閾值min_sup=0.01,分別在四種數(shù)據(jù)庫(kù)上執(zhí)行軌跡截?cái)嗨惴―P_Trunc,實(shí)驗(yàn)結(jié)果如圖5所示。由圖4可以看出,MSNBC、Kosarak、BMS1數(shù)據(jù)庫(kù)中短序列占絕大部分,Geolife數(shù)據(jù)庫(kù)含有大量長(zhǎng)序列,對(duì)比圖4和圖5,能夠直觀地看出DP_Trunc算法僅僅將極少數(shù)長(zhǎng)序列截?cái)?卻大幅降低了軌跡的最大長(zhǎng)度。

2)基于Geolife數(shù)據(jù)庫(kù)的LTPM、N-gram以及Prefix算法比較。

圖6 頻繁軌跡模式挖掘結(jié)果

圖6(a)和圖6(b)顯示,固定ε=0.5,最小支持度閾值min_up取值分別為數(shù)據(jù)庫(kù)大小的0.020、0.025、0.030、0.035、0.040倍,當(dāng)min_up從0.020變化到0.040時(shí),LTPM算法的TPR明顯比N-gram和Prefix算法表現(xiàn)好,其原因是N-gram和Prefix算法也限制序列長(zhǎng)度,但是直接刪除超過限定長(zhǎng)度的項(xiàng),因此會(huì)丟失大量信息,而LTPM算法使用DP_Trunc算法,在限制序列長(zhǎng)度的同時(shí),很大程度上保留了序列的頻繁信息。LTPM算法的ARE是Prefix算法的將近1/4,是N-gram算法的將近1/13,其原因是LTPM算法采用軌跡截?cái)嗟姆椒?明顯降低了全局敏感度,同時(shí)利用等價(jià)關(guān)系,在減少序列冗余的同時(shí),進(jìn)一步降低了全局敏感度。而N-gram和Prefix算法受序列長(zhǎng)度影響較大,僅適用于短序列居多的數(shù)據(jù)庫(kù)。由圖6(c)和圖6(d)可看出,當(dāng)固定min_up=0.02,ε從0.2變化到1.0時(shí),LTPM算法的TPR比N-gram和Prefix表現(xiàn)要好,維持在0.8左右,而N-gram和Prefix算法在0.6左右,LTPM算法的ARE隨著ε的增大降低明顯,尤其在ε=1.0時(shí),是N-gram算法的將近1/15,是Prefix算法的將近1/5。圖6(a)～圖6(d)可看出,LTPM算法明顯要優(yōu)于N-gram和Prefix算法。

3)基于MSNBC數(shù)據(jù)庫(kù)的LTPM、N-gram以及Prefix算法比較圖6(e)和圖6(f)顯示,固定ε=0.5,最小支持度閾值min_up取值分別為數(shù)據(jù)庫(kù)大小的0.020、0.025、0.030、0.035、0.040,當(dāng)min_up逐漸變大時(shí),LTPM算法的TPR比Prefix和N-gram算法好很多,LTPM算法的ARE是N-gram算法的將近1/7,是Prefix算法的將近1/3,MSNBC數(shù)據(jù)庫(kù)包含大量短序列記錄,所以N-gram和Prefix表現(xiàn)較好,ARE較低,但是仍然高于LTPM算法。圖6(g)和圖6(h)可看出,當(dāng)固定min_up=0.02,ε從0.2變化到1.0時(shí),LTPM算法的TPR同樣好于N-gram和Prefix算法,LTPM算法的ARE隨著ε的增大降低明顯,尤其是當(dāng)ε=1.0時(shí),是N-gram算法的近1/9,是Prefix算法的近1/6。

雖然N-gram和Prefix在短序列居多的數(shù)據(jù)庫(kù)MSNBC中表現(xiàn)較好,但LTPM算法仍然優(yōu)于兩者。

4)基于Kosarak數(shù)據(jù)庫(kù)的LTPM、N-gram以及Prefix算法比較。

圖6(i)和圖6(j)顯示,固定ε=0.5,最小支持度閾值min_up取值分別為數(shù)據(jù)庫(kù)大小的0.001、0.001 5、0.002 0、0.002 5、0.003 0倍,當(dāng)min_up逐漸變大時(shí),LTPM算法的TPR優(yōu)于N-gram和Prefix算法,ARE是N-gram算法的將近1/8,是Prefix算法的將近1/6。由圖6(k)和圖6(l)可看出,當(dāng)固定min_up=0.001,ε從0.2變化到1.0時(shí),LTPM算法的TPR同樣好于N-gram和Prefix算法,在最壞情況下,LTPM算法的ARE不到N-gram的1/3,不到Prefix的1/2。由表2和圖4(b)、(c)可看出,Kosarak數(shù)據(jù)庫(kù)和MSNBC數(shù)據(jù)庫(kù)特征類似,都是短序列居多,所以表現(xiàn)類似。

5)基于BMS1數(shù)據(jù)庫(kù)的LTPM、N-gram以及Prefix算法比較。

圖6(m)和圖6(n)顯示,固定ε=0.5,最小支持度閾值min_up取值分別為數(shù)據(jù)庫(kù)大小0.005、0.010、0.015、0.020、0.025倍,當(dāng)變化min_up時(shí),LTPM算法的TPR比N-gram和Prefix稍好,ARE不足N-gram算法的1/2,比Prefix算法低。由圖6(o)和圖6(p)可看出,當(dāng)固定最小支持度閾值min_up=0.005,變化ε時(shí),LTPM算法的TPR同樣比N-gram和Prefix稍好,在最好情況ε=1.0時(shí),ARE不足N-gram算法的1/3,是Prefix算法的近1/2。由表2和圖4(d)可知,BMS1數(shù)據(jù)庫(kù)絕大多數(shù)記錄都是短序列,所以N-gram和Prefix表現(xiàn)非常好,但LTPM算法仍然優(yōu)于兩者,其原因是DP_Trunc算法能有效降低截?cái)鄮淼恼`差,同時(shí)LTPM算法很大程度降低了全局敏感度。

5 結(jié)語(yǔ)

針對(duì)目前的差分隱私下頻繁軌跡模式挖掘算法全局敏感度過高,會(huì)產(chǎn)生大量候選序列,僅適用于短序列居多的數(shù)據(jù)庫(kù)的問題,結(jié)合軌跡截?cái)嗪颓熬Y序列格,本文提出了一種滿足差分隱私的頻繁軌跡模式挖掘算法LTPM。從理論角度分析的結(jié)果顯示,LTPM滿足差分隱私。最后,通過真實(shí)數(shù)據(jù)庫(kù)的實(shí)驗(yàn)結(jié)果表明該算法在滿足差分隱私的前提下可獲得較高的數(shù)據(jù)可用性。在未來的工作中,將研究如何更加合理地分配隱私保護(hù)預(yù)算,以進(jìn)一步提高挖掘結(jié)果的可用性。

References)

[1] DWORK C. Differential privacy [C]// ICALP 2006: Proceedings of the 33rd International Conference on Automata, Languages and Programming. Berlin: Springer, 2006: 1-12.

[2] DWORK C. LEI J. Differential privacy and robust statistics [C]// STOC 2009: Proceedings of the 41th Annual ACM Symp on Theory of Computing. New York: ACM, 2009: 371-380.

[3] DWORK C, McSHERRY F, NISSIM K, SMITH A. Calibrating noise to sensitivity in private data analysis [C]// TCC 2006: Proceedings of the 3th Theory of Cryptography Conference. Berlin: Springer, 2006: 363-385.

[4] McSHERRY F, TALWAR K. Mechanism design via differential privacy[C]// FOCS 2007: Proceedings of the 54th IEEE Symposium on Foundations of Computer Science. Washington, DC: IEEE Computer Society, 2007: 94-103.

[5] BHASKAR R, LAXMAN S, SMITH A, et al. Discovering frequent patterns in sensitive data[C]// KDD 2010: Proceedings of the 16th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York: ACM, 2010: 503-512.

[6] LI N, QARDOJI W, SU D, et al. PrivBasis: frequent itemset mining with differential privacy[J]. Proceedings of the VLDB Endowment, 2012, 5(11): 1340-1351.

[7] ZENG C, NAUGHTON J F, CAI J-Y. On differentially private frequent itemset mining [J]. Proceedings of the VLDB Endowment, 2012, 6(1) : 25-36.

[8] CHEN R, FUNG B, DESAI B C, et al. Differentially private transit data publication: a case study on the montreal transportation system [C]// KDD 2012: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2012: 213-221.

[9] CHEN R, GERGELY A, CLAUDE C. Differentially private sequential data publication via variable-length n-grams[C]// CCS 2012: Proceedings of the 19th ACM Conference on Computer and Communications Security. New York: ACM, 2012: 638-649.

[10] CHENG X, SU S, XU S, et al. DP-Apriori: a differentially private frequent itemset mining algorithm based on transaction splitting[J]. Computers amp; Security, 2015, 50 (C): 74-90.

[11] XU S, SU S, CHENG X, et al. Differentially private frequent sequence mining via sampling-based candidate pruning[C]// ICDE 2015: Proceedings of the 31st IEEE International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2015: 1035-1046.

[12] CHEN R, MOHAMMED N, FUNG B C M, et al. Publishing set-valued data via differential privacy [EB/OL]. [2017- 01- 10]. http://www.vldb.org/pvldb/vol4/p1087-chen.pdf.

[13] YAN X, HAN J, AFSHAR R. CloSpan: mining closed sequential patterns in large datasets[C]// SDM 2003: Proceedings of the 2003 SIAM International Conference on Data Mining. Philadelphia, Pennsylvania, USA: SIAM, 2003: 166-177.

[14] AGRAWAL R, SRIKANT R. Fast algorithms for mining association rules in large databases [C]// VLDB 1994: Proceedings of the 20th International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc. San Francisco, CA, USA, 1994: 487-499.

[15] McSHERRY F. Privacy integrated queries: an extensible platform for privacy-preserving data analysis [C]// SIGMOD 2009: Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2009: 19-30.

[16] PEI J, HAN J, MORTAZAVI-ASL B, et al. PrefixSpan: mining sequential patterns by prefix-projected growth [C]// ICDE 2001: Proceedings of the 17th International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2001: 215-224.

[17] 張嘯劍, 孟小峰. 面向數(shù)據(jù)發(fā)布和分析的差分隱私保護(hù)研究綜述[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(4): 927-949. (ZHANG X J, MENG X F. Differential privacy in data publication and analysis[J]. Chinese Journal of Computers, 2014, 37(4): 927-949.)

[18] 丁麗萍, 盧國(guó)慶. 面向頻繁模式挖掘的差分隱私保護(hù)研究綜述[J]. 通信學(xué)報(bào), 2014, 35(10): 200-209. (DING L P, LU G Q. Survey of differential privacy in frequent pattern mining [J]. Journal on Communications, 2014, 35(10): 200-209.)[19] 李艷輝, 劉浩, 袁野, 等. 基于差分隱私的頻繁序列模式挖掘算法[J]. 計(jì)算機(jī)應(yīng)用, 2017, 37(2): 316-321. (LI Y H, LIU H, YUAN Y, et al. Frequent sequence pattern mining with differential privacy[J]. Journal of Computer Applications, 2017, 37(2): 316-321.)

[20] 張嘯劍, 王淼, 孟小峰. 差分隱私保護(hù)下一種精確挖掘top-k頻繁模式方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(1): 104-114. (ZHANG X J, WANG M, MENG X F. An accurate method for mining top-kfrequent pattern under differential privacy[J]. Journal of Computer Research and Development, 2014, 51(1): 104-114.)

Trajectorypatternminingwithdifferentialprivacy

JIN Kaizhong, PENG Huili, ZHANG Xiaojian*

(SchoolofComputeramp;InformationEngineering,HenanUniversityofEconomicsandLaw,ZhengzhouHenan450002,China)

To address the problems of high global query sensitivity and low utility of mining results in the existing works, a Lattice-Trajectory Pattern Mining (LTPM) algorithm based on prefix sequence lattice and trajectory truncation was proposed for mining sequential patterns with differential privacy. An adaptive method was employed to obtain the optimal truncation length, and a dynamic programming strategy was used to truncate the original database. Based on the truncated database, the equivalent relation was used to construct the prefix sequence lattice for mining trajectory patterns. Theoretical analysis shows that LTPM satisfies ε-differential privacy. The experimental results show that the True Postive Rate (TPR) and Average Relative Error (ARE) of LTPM are better than those ofN-gram and Prefix algorithms, which verifies that LTPM can effectively improve the utility of the mining results.

differential privacy; privacy protection; frequent pattern mining; trajectory truncation; prefix sequential lattice

2017- 05- 05;

2017- 07- 28。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61502146,91646203);河南省自然科學(xué)基金資助項(xiàng)目(162300410006);河南省科技攻關(guān)項(xiàng)目(162102310411);河南省教育廳高等學(xué)校重點(diǎn)科研項(xiàng)目(16A520002);河南財(cái)經(jīng)政法大學(xué)青年拔尖人才項(xiàng)目。

金凱忠(1991—),男,河南開封人,碩士研究生,主要研究方向:差分隱私、數(shù)據(jù)庫(kù); 彭慧麗(1981—),女,河南周口人,講師,碩士，主要研究方向:數(shù)據(jù)庫(kù)、隱私保護(hù); 張嘯劍(1980—),男,河南周口人,副教授,博士,CCF會(huì)員,主要研究方向:差分隱私、數(shù)據(jù)庫(kù)。

1001- 9081(2017)10- 2938- 08

10.11772/j.issn.1001- 9081.2017.10.2938

TP309.2

A

This work is partially supported by the National Natural Science Foundation of China (61502146, 91646203), the Natural Science of Henan Province (162300410006), the Science and Technology Project of Henan Province (162102310411), the Key Scientific Research Projects of Education Department of Henan Province (16A520002), the Youth Top-notch Talent Project of Henan University of Economics and Law.

JINKaizhong, born in 1991, M. S. candidate. His research interests include differential privacy, database.

PENGHuili, born in 1981, M. S., lecturer. Her research interests include database, privacy protect.

ZHANGXiaojian, born in 1980, Ph. D., associate professor. His research interests include differential privacy, database.