金凱忠,彭慧麗,張嘯劍

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

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

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

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

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

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

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ù)庫例如位置信息中乘客乘車和下車點(diǎn)信息、互聯(lián)網(wǎng)用戶點(diǎn)擊流信息中挖掘出的頻繁模式本身的內(nèi)容以及支持度計數(shù)信息都有可能泄露個人隱私信息或者披露個人的真實(shí)身份。攻擊者獲得某些模式的支持度計數(shù)之后,可以利用額外的背景知識進(jìn)行攻擊。例如表1中b表示某一敏感位置,攻擊者想竊取“Tom是否去過b位置”這種信息。通過分析獲知b為頻繁模式,其真實(shí)支持度計數(shù)為5。如果攻擊者已經(jīng)知道其他4人去過b位置,則可推理出Tom也去過b位置,進(jìn)而導(dǎo)致Tom的敏感位置泄露。因此,在挖掘頻繁模式的過程中,如何保護(hù)模式的支持度計數(shù)是主要的技術(shù)挑戰(zhàn)。

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

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

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

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

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

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

本文的主要工作:

1)為了解決問題1,本文基于動態(tài)規(guī)劃策略提出一種滿足差分隱私的軌跡序列截斷算法DP_Trunc,在有效降低全局敏感度的同時,減少截斷算法帶來的誤差。

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

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

1 相關(guān)工作

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

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

2 定義和概念

2.1 差分隱私

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

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

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

定義2ε-差分隱私。給定一個軌跡模式挖掘算法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為某一個查詢,且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為某個查詢函數(shù),且f:T→Rd,若算法A符合下列等式,則A滿足ε-差分隱私。

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

(3)

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

2.2 頻繁軌跡模式挖掘

軌跡數(shù)據(jù)是具有時間戳的按照時間先后排序的序列數(shù)據(jù),例如空間軌跡數(shù)據(jù),每個位置可表示成一個三元組〈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分別對應(yīng)于地理空間經(jīng)度與緯度數(shù)據(jù);wi為xi和yi位置的時間戳信息,且1lt;ilt;n,wilt;wi+1。根據(jù)北京公交車軌跡Geolife數(shù)據(jù),畫出15條軌跡序列,其可視化結(jié)果如圖1所示。

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

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

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

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

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

圖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就是針對表1代表的軌跡數(shù)據(jù)庫T,采用前綴序列樹結(jié)構(gòu)挖掘的結(jié)果,其中最小支持度閾值為1。掘頻繁軌跡模式的過程中,采用Clospan算法[13]思想,通過等價關(guān)系判斷,對前綴序列樹進(jìn)行子樹合并,得到前綴序列格。3.4節(jié)對前綴序列格的構(gòu)建作了詳細(xì)的說明。

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

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

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

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

針對原則1和原則2,本文提出一種基于軌跡截斷和前綴序列格的軌跡模式挖掘算法LTPM。

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

算法1 LTPM算法。

輸入 軌跡數(shù)據(jù)庫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

該算法主要包含三個過程:估計最優(yōu)截斷長度過程(行2))、截斷軌跡數(shù)據(jù)庫過程(行4)),構(gòu)建前綴序列格過程(行3)～5))。接下來分別詳細(xì)介紹上述三個過程。

3.2 最優(yōu)截斷長度選取

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

算法2 estimate_opt_length算法。

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

輸出 最優(yōu)截斷長度lopt。

1)

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

2)

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

3)

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

例1 給定軌跡數(shù)據(jù)庫T如表1所示,則T長度分布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)截斷長度為2。

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

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

基于上述最優(yōu)截斷長度lopt對軌跡數(shù)據(jù)庫進(jìn)行截斷處理,截斷軌跡數(shù)據(jù)庫過程核心步驟為DP_Trunc算法。

3.3 軌跡截斷策略

3.3.1 全局敏感度分析

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

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

ΔfQ=ΔI×lmax

ΔI=(qmax-qmin)+1

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

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

3.3.2 動態(tài)規(guī)劃軌跡截斷

為了表述更加確切,以下稱軌跡模式為軌跡序列。經(jīng)分析發(fā)現(xiàn),如果一個候選k-軌跡序列的所有子序列足夠頻繁的話,那么該k-軌跡序列很有可能是頻繁的。為了衡量哪些軌跡序列是足夠頻繁的,本文為每個軌跡序列定義一個權(quán)重,每個候選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)截斷問題可以表示為:

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

(5)

在最優(yōu)截斷長度lopt給定的情況下,即找到一個長度為lopt截斷后軌跡序列t′,使得t′的權(quán)重最大。

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

算法3 DP_Trunc算法。

輸入 軌跡數(shù)據(jù)庫T,頻繁(k-1)-序列集合Sk-1,最優(yōu)序列截斷長度lopt。

輸出 截斷后的軌跡數(shù)據(jù)庫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個位置開始截取長度為lopt的連續(xù)序列t′ 并添加到T′*/

8)

ReturnT′

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

假設(shè)軌跡序列t={a1→a2,…,ai,…,a|t|},給定候選k-序列集合Ck,最優(yōu)截斷長度lopt,則根據(jù)式(4)～(5),要找的截斷后軌跡序列t′滿足下面等式:

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

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

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

(7)

其中：FW[i]表示以軌跡t中ai結(jié)尾且長度為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)截斷長度lopt=3。按照lopt=3在t中選擇出連續(xù)的子序列有三種情況,分別為{a→b→c}、{b→c→d}、{c→d→e},從中選擇權(quán)重最大的子序列作為t的截斷序列。

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

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

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

算法4 Gen_Lattice算法。

輸入 截斷軌跡數(shù)據(jù)庫T′,隱私預(yù)算ε2,最優(yōu)截斷長度lopt,前綴序列格SL,最小支持度閾值min_up,頻繁(k-1)-序列Sk-1。

輸出 頻繁k-序列Sk。

1)

Ck←prefix_expend(Sk-1,T′)

//C1為軌跡數(shù)據(jù)庫所有不同的項(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存在等價關(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)是否滿足等價關(guān)系；2)層次是否超過lopt。

首先行1)根據(jù)頻繁(k-1)-軌跡序列Sk-1,掃描軌跡數(shù)據(jù)庫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)通過等價關(guān)系判斷對前綴序列格進(jìn)行子樹合并操作,很大程度上減少了候選軌跡序列的規(guī)模。

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

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

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

3.5 LTPM算法性能分析

3.5.1 算法隱私性分析

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

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

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

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

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

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

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

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

圖4 數(shù)據(jù)庫長度分布

圖5 截斷后數(shù)據(jù)庫長度分布

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

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

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

(8)

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

2)平均相對誤差。該標(biāo)準(zhǔn)主要用來度量頻繁軌跡模式支持度計數(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為相對閾值,即最小支持度閾值的取值隨著數(shù)據(jù)庫大小的不同而變化。每個算法分別執(zhí)行100次,并記錄輸出結(jié)果的平均值。分別通過固定隱私預(yù)算,改變最小支持度閾值大小和固定最小支持度閾值,改變隱私預(yù)算大小來比較LTPM、N-gram以及Prefix算法的準(zhǔn)確率和平均相對誤差,進(jìn)而比較四種算法的可用性。

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

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

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

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

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

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

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

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

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

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

5 結(jié)語

針對目前的差分隱私下頻繁軌跡模式挖掘算法全局敏感度過高,會產(chǎn)生大量候選序列,僅適用于短序列居多的數(shù)據(jù)庫的問題,結(jié)合軌跡截斷和前綴序列格,本文提出了一種滿足差分隱私的頻繁軌跡模式挖掘算法LTPM。從理論角度分析的結(jié)果顯示,LTPM滿足差分隱私。最后,通過真實(shí)數(shù)據(jù)庫的實(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ī)學(xué)報, 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] 丁麗萍, 盧國慶. 面向頻繁模式挖掘的差分隱私保護(hù)研究綜述[J]. 通信學(xué)報, 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ī)應(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ī)研究與發(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。

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

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

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.