李艷輝，劉 浩，袁 野，王國仁

(東北大學 計算機科學與工程學院，沈陽110819)

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

基于差分隱私的頻繁序列模式挖掘算法

李艷輝*，劉 浩，袁 野，王國仁

(東北大學 計算機科學與工程學院，沈陽110819)

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

針對當數(shù)據(jù)集含有敏感信息時，直接發(fā)布頻繁序列模式本身及其支持度計數(shù)都有可能泄露用戶隱私信息的問題，提出一種滿足差分隱私(DP)的頻繁序列模式挖掘(DP-FSM)算法。該算法利用向下封閉性質(zhì)生成候選序列模式集，基于智能截斷方法從候選模式中挑選出頻繁的序列模式，最后采用幾何機制對所選出模式的真實支持度添加噪聲進行擾動。另外，為了提高挖掘結(jié)果的可用性,設計了一個閾值修正的策略來減小挖掘過程中的截斷誤差和傳播誤差。理論分析證明了該算法滿足ε-差分隱私。實驗結(jié)果表明了該算法在拒真率(FNR)和相對支持度誤差(RSE)兩個指標上明顯低于對比算法PFS2,有效地提高了挖掘結(jié)果的準確度。

頻繁序列挖掘；差分隱私；隱私保護；幾何機制；數(shù)據(jù)挖掘

0 引言

頻繁序列挖掘(Frequent Sequence Mining，F(xiàn)SM)是數(shù)據(jù)挖掘研究領(lǐng)域的一個重要課題，其目的是找出相對時間或其他順序頻繁出現(xiàn)在數(shù)據(jù)集中的模式，是關(guān)聯(lián)規(guī)則、相關(guān)性分析、分類、聚類等多種數(shù)據(jù)挖掘任務的基礎。隨著大量序列數(shù)據(jù)的收集和存儲，頻繁序列模式可以為諸如市場分析、需求預測等數(shù)據(jù)分析任務提供大量有價值的信息。然而，頻繁序列模式本身和其相應支持度計數(shù)都有可能泄露隱私信息。

傳統(tǒng)隱私保護方法大多基于k-匿名[1]和劃分，這類方法均需要對攻擊模型和攻擊者的背景知識預先作出假設，無法提供一種有效且嚴格的方法來證明其隱私保護水平。此外，隨著諸如組合攻擊和前景知識攻擊等新型攻擊模型的出現(xiàn)，對這些方法的有效性提出了嚴峻挑戰(zhàn)。差分隱私(Differential Privacy，DP)[2]是Dwork在2006年提出的一種基于數(shù)據(jù)失真，獨立于攻擊者背景知識和計算能力的強隱私保護模型，近年來已成為隱私保護領(lǐng)域的一個研究熱點。

當前已有很多文獻對差分隱私下的頻繁序列模式挖掘進行了深入研究。文獻[3-4]提出了兩種非交互框架下的頻繁序列模式挖掘方法，其關(guān)注于序列數(shù)據(jù)庫的發(fā)布，挖掘結(jié)果效用性較差。不同于文獻[3-4]，文獻[5-6]提出交互式框架下的頻繁序列模式挖掘方法，分別關(guān)注于挖掘連續(xù)序列模式和一般化的頻繁序列挖掘。

盡管文獻[6]提出的差分隱私下的頻繁序列模式挖掘算法PFS2(differentially Private Frequent Sequence mining via Sampling-based Candidate Pruning)可以解決頻繁序列模式挖掘過程中存在的隱私泄露問題。但是，該算法在重構(gòu)序列數(shù)據(jù)庫時未考慮不同候選序列重要程度的差異性，導致算法準確度低，挖掘結(jié)果效用性差。

針對上述問題，本文基于差分隱私，提出一種具有高效用性的頻繁序列挖掘策略——DP-FSM(Differential Private Frequent Sequence Mining)算法。該算法主要從兩個方面提高挖掘結(jié)果的準確度。首先，基于候選集中不同候選序列重要程度的差異性，提出了一種啟發(fā)式的方法設計打分函數(shù)來區(qū)分不同候選序列的重要程度，從而能在序列截斷時使具有高優(yōu)先級的候選序列優(yōu)先保留；其次，針對挖掘頻繁序列模式的誤差問題，提出一種閾值修正策略，通過判斷某序列是否頻繁和判斷某序列是否用于產(chǎn)生候選序列而設置不同的閾值以減小誤差。

1 相關(guān)工作

根據(jù)挖掘的對象不同，目前差分隱私保護下的頻繁模式挖掘研究主要分為頻繁項集挖掘和頻繁序列挖掘，其中頻繁序列挖掘與本文討論的問題最為相關(guān)。

1.1 頻繁項集挖掘

近年來，差分隱私下的頻繁項集挖掘已取得一些重大的研究進展。Bhaskar等[7]提出了兩種滿足差分隱私的top-k頻繁項集挖掘策略。這兩種方法借鑒截斷頻率的思想，分別運用拉普拉斯機制與指數(shù)機制。Li等[8]提出一種可用于高維數(shù)據(jù)的PrivBasis算法，該算法結(jié)合θ-基與映射技術(shù)在保證計算性能的前提下實現(xiàn)差分隱私保護。張嘯劍等[9]提出一種采用后置處理技術(shù)對噪聲計數(shù)進行求精處理，使輸出結(jié)果滿足一致性要求的方法，該方法能獲得較好的可用性。Zeng等[10]針對長事務會導致高查詢敏感性的缺陷，提出了一種基于事務截斷技術(shù)提高結(jié)果可用性的貪婪方法SmartTrunc。上述算法是交互式框架下的頻繁項集挖掘方法，但它們只適用于特定的情境，而項集與序列的差異使得這些算法并不適用于挖掘頻繁序列模式。

Chen等[11]提出了一種基于上下文無關(guān)分類樹,結(jié)合自頂向下的樹劃分方法來發(fā)布數(shù)據(jù)集；Lee等[12]提出了一種使用前綴樹來隱私地發(fā)布頻繁項集的方法。這兩種算法是非交互式框架下的頻繁項集挖掘方法，這類方法通過隱私地發(fā)布數(shù)據(jù)集來支持頻繁項集挖掘。

1.2 頻繁序列挖掘

Chen等[3]提出一種基于前綴樹的方法隱私地發(fā)布軌跡數(shù)據(jù)集，用于支持頻繁序列挖掘。此外，他們在文獻[4]中還提出了一種基于變長n-gram模型來發(fā)布序列數(shù)據(jù)集的方法。這種方法主要利用變長n-gram模型提取序列數(shù)據(jù)庫的必要信息，利用探索樹減少添加噪聲的數(shù)量。這兩種方法與本文方法的不同之處在于前者關(guān)注于序列數(shù)據(jù)庫的發(fā)布，而本文方法則關(guān)注于頻繁序列的發(fā)布。

Bonomi等[5]提出了一個滿足差分隱私保護的兩階段的頻繁連續(xù)序列挖掘策略。該方法首先利用一個前綴樹來找到所有的候選序列，然后利用數(shù)據(jù)庫局部轉(zhuǎn)換技術(shù)細化候選序列的支持度。和這種方法只針對連續(xù)序列挖掘相比，Xu等[6]提出了一個關(guān)注于一般化的頻繁序列挖掘，忽略序列中的項是否連續(xù)的算法PFS2。這個算法的核心是利用一個基于采樣的候選剪枝技術(shù)來減小候選序列的數(shù)目。該技術(shù)的主要思想是使用候選序列在樣本數(shù)據(jù)庫中的局部噪聲支持度來估計該序列是否頻繁。

本文的工作更類似于PFS2算法，但PFS2算法在序列重構(gòu)時將所有候選序列等同看待，而本文則提出了區(qū)分不同候選序列重要程度的算法，并提出一種閾值修正策略來提高挖掘結(jié)果的準確度。

2 問題定義

2.1 差分隱私

差分隱私保護可以保證對數(shù)據(jù)集的查詢處理結(jié)果對于具體某個記錄的變化是不敏感的，即在數(shù)據(jù)集中添加或刪除一條數(shù)據(jù)記錄不會對查詢的輸出結(jié)果產(chǎn)生顯著影響。因此，即使在最壞情況下，攻擊者獲得除目標記錄外的所有記錄信息，仍可以保證這一記錄的敏感信息不會被泄露。

如果兩個數(shù)據(jù)集D和D′相差最多為一個記錄，則稱D和D′為鄰居數(shù)據(jù)集(NeighboringDatasets)。本文使用符號D～D′表示兩個數(shù)據(jù)集是鄰居關(guān)系。

定義1ε-差分隱私[2]。給定兩個鄰居數(shù)據(jù)集D和D′以及一個隨機算法A，Range(A)表示A的取值范圍。若對于在數(shù)據(jù)集D和D′上的所有輸出結(jié)果O(O∈Range(A))，算法A滿足下列不等式，則稱算法A滿足ε-差分隱私。

Pr(A(D)∈O)≤exp(ε)Pr(A(D′)∈O)

(1)

其中，參數(shù)ε叫作隱私預算，控制著隱私保護的水平。ε越小，表示隱私保護水平越高。差分隱私的含義在于，對于算法的任一可能的輸出結(jié)果而言，無論函數(shù)的輸入是數(shù)據(jù)集D還是D′，得到這一輸出的概率相差很小。

設計差分隱私算法的常用技術(shù)是向查詢或者分析結(jié)果中添加噪聲使數(shù)據(jù)失真。添加干擾噪聲的大小與查詢函數(shù)的敏感度密切相關(guān)。查詢函數(shù)的敏感度是指改變數(shù)據(jù)集中任一記錄對查詢結(jié)果造成的最大改變量。

定義2 全局敏感度。設有函數(shù)f:D→Rd，輸入為一數(shù)據(jù)集D，輸出為一個d維實數(shù)向量。對于任意的鄰居數(shù)據(jù)集D和D′，函數(shù)f的全局敏感度為：

(2)

其中‖·‖1表示L1距離。注意:函數(shù)的全局敏感度獨立于數(shù)據(jù)集，僅由函數(shù)本身決定。不同的函數(shù)會有不同的敏感度。常用的計數(shù)查詢的敏感度為1。

拉普拉斯機制是2006年由Dwork等[13]提出的一種實現(xiàn)差分隱私保護的方法。該機制的形式化描述如下：給定一個函數(shù)f:D→Rd，若一個隨機算法A的輸出結(jié)果滿足等式(3)，則A滿足ε-差分隱私。

A(D)=f(D)+Lap(Δf/ε)d

(3)

Laplace機制適用于響應函數(shù)的返回值為實數(shù)型的情況，其主要思想是在真實的輸出值上添加符合拉普拉斯分布的噪聲以達到保護效果。添加的噪聲量大小與Δf成正比，與ε成反比。對于函數(shù)返回值為整數(shù)的情況，Ghosh等[14]提出了拉普拉斯機制的特例——幾何機制。該機制添加的噪聲大小服從概率密度函數(shù)為式(4)的雙邊幾何分布。本文方法也使用幾何機制對頻繁序列的支持度添加噪聲。

Pr(δ=x)～exp(-ε|x|)

(4)

定理1 幾何機制。設f:D→Rd是一個輸出為整數(shù)、敏感度為Δf的函數(shù)。若一個隨機算法A的輸出結(jié)果滿足等式(5)，則A滿足ε-差分隱私。

A(D)=f(D)+G(ε/Δf)d

(5)

通常，一個復雜的隱私保護問題通常需要多次運用差分隱私保護算法才能得以解決。在這種情形下，為了保證整個過程滿足ε-差分隱私，需要合理地將全部預算分配到各個子過程中。這時經(jīng)常利用差分隱私保護算法的一個很重要的性質(zhì)——序列組合性。

2.2 頻繁序列模式挖掘

設字母表I={i1,i2,…,i|I|}，一個序列S是字母表中一些項的有序排列。使用S=s1s2…s|S|表示一個長度為|S|的序列，也稱為|S|-序列。一個序列數(shù)據(jù)庫D是輸入序列的集合，每個輸入序列代表一個人的記錄。

通常而言，模式是否頻繁取決于模式的支持度與指定閾值的關(guān)系?；谶@個事實，我們需要知道序列模式支持度的計算方法。在給出支持度的定義之前，先介紹序列的包含關(guān)系。

定義3 包含關(guān)系。給定兩個序列S=s1s2…s|S|和T=t1t2…t|T|。如果存在整數(shù)w1

定義4 支持度。給定一個序列模式S和一個序列數(shù)據(jù)庫D，在D中T的支持度定義為D中包含S的軌跡的數(shù)量。也就是說，Sup(T)=|{o|o∈D∧S?o}|。

頻繁序列模式挖掘的任務就是在給定的序列數(shù)據(jù)庫中找出所有支持度大于給定閾值σk的序列模式。然而，在挖掘頻繁序列模式過程中存在隱私泄露的風險?；谶@一事實，本文提出一種在保護個人敏感信息的前提下隱私地挖掘頻繁序列模式的算法。下面先給出本文的問題定義。

問題定義：給定一個語義軌跡數(shù)據(jù)庫D、隱私參數(shù)ε和一個閾值σk，本文的目標是設計DP-FSM算法來挖掘所有支持度大于σk的頻繁序列模式，并計算每個頻繁序列的支持度。該算法需滿足如下要求：1)DP-FSM算法滿足ε-差分隱私;2)DP-FSM算法具有較高的數(shù)據(jù)可用性。

3 DP-FSM算法

為了使FSM滿足差分隱私，最直接的方法是利用向下封閉屬性[15]生成所有候選序列(即所有可能的頻繁序列)，并對每個候選序列的支持度添加擾動噪聲，最后根據(jù)噪聲支持度選出頻繁序列。然而，這種方法結(jié)果效用性差。這是由于大量的候選序列會導致大量的擾動噪聲，進而導致序列模式的噪聲支持度主要取決于噪聲，結(jié)果會造成嚴重失真。

3.1 算法描述

算法1 DP-FSM算法。

輸入 序列數(shù)據(jù)庫D，百分比η，閾值σk，隱私預算ε，字母表I；

輸出 頻繁序列及其噪聲計數(shù)。

1)

〈l1,l2,…,ln〉=Estimate_Distribution(D,ε1)

3)

lf=Estimate_Frequent_Maxlength(D，ε2，σk)

//估計頻繁序列的最大長度

4)

FS=Mining_FrequentSequence(D,lmax,σk,ε3)

//利用向下封閉屬性[15]性質(zhì)按序列長度遞增的

//順序挖掘所有長度小于lf的頻繁序列；

5)

輸出頻繁序列模式及其噪聲計數(shù)Perturb(FS,ε4)。

DP-FSM主要由預處理、挖掘和擾動三個階段組成。

預處理階段(算法1)～3)行)：主要估計最大長度約束lmax和頻繁序列的最大長度lf。

lf的計算方法如下：從1到lmax，計算i-序列的最大支持度，然后向其添加噪聲G(ε2/log(lmax))，選出支持度大于閾值σk最大的整數(shù)i。

挖掘階段(算法第4)行)：算法按照序列長度遞增的方式隱私地發(fā)現(xiàn)頻繁序列

擾動階段(算法第5)行)：實現(xiàn)比較簡單，向直接挑選出的頻繁序列的支持度添加幾何機制的噪聲即可。

以下將著重介紹DP-FSM算法的核心——挖掘頻繁序列階段。

3.2 挖掘頻繁序列模式

算法2DP-MiningFrequentSequence。

輸入 頻繁序列最大長度lf，截斷序列長度約束lmax，隱私預算ε3，閾值σk；

輸出 頻繁序列集合FS。

1)

For(k=1；k≤lf；k++)

2)

Ifk==1 thenD′←D；Ck←I

Else

3)

Ck←Generate_CandidatSet(Sk-1)；

4)

D′=Truncate_Database(D，Ck，lmax)

//截斷數(shù)據(jù)庫；

5)

Sk←Choose_Candidate_Seed(D′，Ck，ε′，σk)；

6)

FSk=Discover_Frequent_Sequence(D′，Ck，ε′，σk)；

7)

FS=FS+FSk；

8)

ReturnFS；

算法2描述了隱私地挖掘頻繁序列模式的過程，其核心思想是利用候選序列在截斷序列數(shù)據(jù)庫D′中的噪聲支持度判斷該候選序列是否頻繁。同時，為了提高挖掘結(jié)果的準確度，該算法從兩個方面對閾值進行修正:1)截斷序列數(shù)據(jù)庫后會造成某些候選序列頻率信息的損失，考慮到這種截斷情況產(chǎn)生的誤差(稱之為截斷誤差)，該算法修正判斷閾值σk為σk-avg(θ′)+θ′，其中avg(θ′)為根據(jù)序列的噪聲支持度θ′估計該序列在原數(shù)據(jù)庫中的平均支持度。2)如果一個頻繁序列模式被錯誤地標注為不頻繁的模式，則它的任何超序列在不計算其支持度的情況下即被判定為不頻繁的序列模式。考慮到這種情況產(chǎn)生的傳播誤差， 修正判斷某一序列是否用于產(chǎn)生候選序列的閾值為σk-max(θ′)+θ′，其中max(θ′)為根據(jù)序列的噪聲支持度θ′估計該序列在原數(shù)據(jù)庫中的最大支持度。

1)截斷序列數(shù)據(jù)庫。這一步的目的是轉(zhuǎn)換序列數(shù)據(jù)庫使其滿足長度約束。理想情況下，當收縮序列時，希望新得到的序列既滿足長度約束又保存盡可能多的潛在頻繁序列模式的頻率信息?；诖?，提出一種序列收縮的方法，通過無關(guān)項刪除、連續(xù)模式壓縮和智能序列重構(gòu)三種策略收縮序列的長度。

a)無關(guān)項刪除。

給定一個序列，當一個項不包含在任何候選序列中時，顯然這個項對于候選集中任何序列模式的支持度無貢獻。這樣的項稱為無關(guān)項，從序列中刪除無關(guān)項不會導致任何頻率損失。

基于向下封閉性質(zhì)，如果一個項對于候選k-序列是無關(guān)項，那么對于長度大于k的候選序列也是無關(guān)項。

例1 設有序列A=abababebcdfg及候選2-序列集合{ab,bc,cd,ac}，則efg為無關(guān)項，刪除后為A1=abababbcd。

b)連續(xù)模式壓縮。

一個序列可能包含一個連續(xù)出現(xiàn)的序列模式。對于k-序列的估計，可在不引起任何頻率信息損失的情況下壓縮連續(xù)的j個序列模式為連續(xù)的k個序列模式。這是由于在候選k-序列中的k個項最多來自k個模式。繼續(xù)上面的例1，序列ab在A1中出現(xiàn)3次，則可用2個連續(xù)模式去代替它，即A2=ababbcd。

c)智能序列重構(gòu)。

無關(guān)項刪除和連續(xù)模式壓縮在不導致頻率(支持度)損失的情況下有效地收縮了序列。然而，在經(jīng)過這兩種方法處理軌跡序列后，某些序列仍然違背序列長度約束。直觀地，收縮一個序列時僅需保留頻繁序列的子序列，這是由于不頻繁的子序列對頻繁序列的支持度無貢獻。然而，我們的目標是隱私地找到這些頻繁的序列模式，為此提出一個啟發(fā)式的方法預測某一個候選序列是否是頻繁的。在實際生活中，如果一個候選序列的所有子序列是充分頻繁的，那么該候選序列很可能是頻繁的序列模式。基于這個觀察，對每個候選i-序列(i≥2)分配一個頻率分。

定義5 頻率分。給定一個頻繁(i-1)-序列的集合GS={S1,S2,…,Sd}，一個i-序列X的頻率分數(shù)為:

(6)

其中，Si.sup′代表序列Si的噪聲支持度。

但找到最優(yōu)的lmax-序列這個問題是NP-hard的，為此提出一個貪心算法來收縮序列。貪心算法的思想如下：對于每條序列，迭代地添加包含在輸入序列中高頻率分數(shù)的候選序列，直到重構(gòu)的序列達到最大集勢。同時，我們注意到一個候選序列的頻率分不應該是靜態(tài)的:當一個候選序列的一些子序列已經(jīng)添加到重構(gòu)序列中后，為了使重構(gòu)序列包含候選序列，該候選序列需要添加的子序列中項的數(shù)目少于其他候選序列。因此，在一個候選序列的一些子序列已經(jīng)添加到重構(gòu)序列后，應更新受影響的候選序列的頻率分。

更新策略如下：假設一個候選序列Xi被添加到重構(gòu)軌跡序列中，需更新集合X的頻率分。對于每個剩余候選序列Xj?{X1,…,Xi-1,Xi+1,…,Xd}，計算單個項的得分αj=fs(Xj)/i。假設已在重構(gòu)序列中的最大子序列包含的項的數(shù)目為βj，則更新候選序列的頻率分為fs(Xj)=fs(Xj)+αj*βj。

例2 繼續(xù)上面的例1，同時假設候選序列的權(quán)重情況如下集合所示：{ab:8;bc:6;cd:4;ac:2}；以及假設序列限制長度為4。經(jīng)過無關(guān)項刪除機制和連續(xù)模式壓縮機制處理后，序列A由序列A2=ababbcd表示，但它的長度依然大于限制長度4，因此需要根據(jù)智能序列重構(gòu)機制處理。依據(jù)該規(guī)則，首先選取ab加入到結(jié)果序列t′中去，然后更新候選序列bc的權(quán)重為6+1×8/2=10。cd的權(quán)重保持不變，ac的權(quán)重更新為2+1×2/2=3。則將bc添加到事務t′中，此時t′=abc，長度仍小于約束長度4。再按同樣的方法進行下一次迭代，得到t′=abcd。此時t′的長度已達到了序列限制長度，因此，用序列abcd表示原序列A=abababebcdfg。

2)閾值修正。為了彌補截斷誤差和傳播誤差導致的頻率信息的損失，受“雙重標準”機制[10]的啟發(fā)，提出一種新的支持度預估方法。該方法根據(jù)序列在轉(zhuǎn)換后事務數(shù)據(jù)庫中的噪聲支持度估算序列在原始數(shù)據(jù)集中真實支持度信息，進而使用平均支持度來判斷該序列是否頻繁，使用最大支持度決定該序列是否會被用來生成候選序列。具體地來說，新的支持度預估方法主要由以下兩步組成。

第一步：給定序列X的噪聲支持度θ′，估算序列X在轉(zhuǎn)換后數(shù)據(jù)集中的真實支持度θreal。根據(jù)“雙重標準”中給定的定理可以得出：

Pr(θreal|θ′)≈e-ε(θreal-θ′)

(7)

第二步：根據(jù)序列在轉(zhuǎn)換后數(shù)據(jù)集中真實支持度θreal，進一步估計序列在原始數(shù)據(jù)集中的真實支持度θ。這里通過分析隨機截取方法產(chǎn)生的信息損失來衡量截斷序列數(shù)據(jù)庫方法產(chǎn)生的信息損失量。直觀地，給定一個長度為l的序列記錄t，若將t截取為t′序列記錄，如果t中不包含序列S，則t′事務中也必然不包含序列S。因此只需要利用包含序列S的截斷序列記錄來計算其支持度。給定長度為l的序列記錄，將長度為|t|包含i-序列S的事務t截取為t′序列記錄，截取為t′序列記錄包含i-序列S的概率為：

(8)

將序列S在轉(zhuǎn)換后數(shù)據(jù)集中的支持度看為隨機變量，則該變量的期望是：

(9)

與“雙重標準”中計算最大支持度和平均支持度的方法相似，給定序列在轉(zhuǎn)換后數(shù)據(jù)集中的支持度θreal，則序列在原始數(shù)據(jù)庫的平均支持度：

(10)

序列在原始數(shù)據(jù)庫的最大支持度：

max(θ″)=

(11)

結(jié)合第一步和第二步的結(jié)論，給定序列在轉(zhuǎn)換后數(shù)據(jù)集中的噪聲支持度θ′，我們估算該序列在原始數(shù)據(jù)集中平均支持度為：

(12)

最大支持度為：

(13)

綜上，在挖掘頻繁序列模式過程中利用i-序列S的平均支持度來判斷該序列是否頻繁，利用最大支持度來決定該序列是否會被用來生成候選(i+1)-序列。換句話說，我們在判斷是否頻繁時將閾值σk修正為σk-avg(θ′)+θ′；在判斷某序列是否用于生成候選序列時閾值σk修正為σk-max(θ′)+θ′。

4 隱私性能分析

以下首先對DP-FSM算法各階段的隱私性能進行分析，然后利用差分隱私的序列組合性(性質(zhì)1)給出整個算法的隱私性能結(jié)果。

預處理階段： 對于序列數(shù)據(jù)庫的集勢|D|的計算，由于添加(刪除)一個輸入序列只影響|D|變化1，則這個計算的敏感度為1。因此，在計算時添加幾何噪聲G(ε11)滿足ε11-差分隱私。相似地，計算aj的敏感度為1，添加G(ε12)也滿足ε12-差分隱私。因此，根據(jù)差分隱私的序列組合性，計算lmax滿足ε1差分隱私。對于lf的計算，當估計每個i-序列的最大噪聲支持度時向其加入符合G(ε2/log(lmax))的噪聲，文獻[2]已給出證明，表明該過程符合ε2-差分隱私。

擾動階段：擾動階段的主要目標是向挑選出的頻繁序列集合FS的真實支持度中添加噪聲達到隱私保護的目的。此時，增加或者刪除一條序列最多影響|FS|個頻繁序列的支持度變化1，則計算頻繁序列集合FS的支持度計數(shù)的敏感度為ΔFS=|FS|。因此，向FS的支持度計數(shù)添加G(ε4/ΔFS)滿足ε4-差分隱私。

定理2 DP-FSM算法滿足ε-差分隱私，其中ε=ε1+ε2+ε3+ε4。

證明 可以根據(jù)差分隱私的序列組合性(性質(zhì)1)直接得出結(jié)論。

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

以下通過實驗來評估DP-FSM算法的性能，實驗環(huán)境為CPUInterCorei7-2600，頻率3.40GHz，8GB內(nèi)存，500GB硬盤，Windows7操作系統(tǒng),所有的代碼用C++編程語言實現(xiàn)。實驗中將DP-FSM與目前最先進的隱私地挖掘頻繁序列的算法PFS2進行比較。由于算法涉及到隨機化，算法各運行15次后取平均值作為結(jié)果發(fā)布。

5.1 實驗設置

實驗中使用兩個真實序列數(shù)據(jù)集：BIBLE[16]和MSNBC(http://kdd.ics.uci.edu/databases/msnbc/msnbc.html)，數(shù)據(jù)集的參數(shù)設置如表1所示。

表1 實驗數(shù)據(jù)集參數(shù)

(14)

(15)

5.2 實驗結(jié)果

5.2.1DP-FSM和PFS2算法的性能比較

圖1(a)分析了在數(shù)據(jù)集MSNBC上閾值參數(shù)σk對FNR的影響。需要注意的是，實驗中的閾值是指相對于整個數(shù)據(jù)集大小的比例。從實驗結(jié)果可以看出，隨著閾值參數(shù)σk的增大，PFS2算法的FNR呈現(xiàn)增大的趨勢，這意味著隨著σk的增大，PFS2算法挖掘結(jié)果的準確度降低，算法性能變差；而DP-FSM算法的FNR總體上呈現(xiàn)相對穩(wěn)定的趨勢。除此之外，從實驗結(jié)果上看，就FNR而言，DP-FSM算法的性能總體上優(yōu)于PFS2算法的性能。

上述實驗結(jié)果是合理的。原因如下：閾值σk的增大意味著用于判斷序列是否頻繁的支持度變大，這樣使得更多的序列變?yōu)榉穷l繁的序列。PFS2算法在重構(gòu)序列時未考慮候選序列頻繁程度的差異性，很有可能導致頻繁序列在截斷序列數(shù)據(jù)庫時未被保留，進一步導致根據(jù)噪聲支持度錯誤地判斷該候選序列為非頻繁的序列模式。而DP-FSM算法由于在截斷序列數(shù)據(jù)庫時考慮了候選序列的差異性，有效地減小了誤差。

圖1(b)分析了在數(shù)據(jù)集MSNBC上閾值參數(shù)σk對兩個算法的RSE的影響。從實驗結(jié)果可以看出，隨著σk的增大，DP-FSM算法的RSE變化不大，而PFS2算法的RSE也呈現(xiàn)增大的趨勢。這種現(xiàn)象是由于隨著σk的增大，對頻繁序列設置的閾值要求更高。PFS2由于在重構(gòu)序列時未考慮候選序列的差異性，導致結(jié)果集中含有大量的非頻繁序列；又由于非頻繁序列的支持度較低，故根據(jù)式(15)，可得出隨著σk的增大，PFS2算法的RSE增大。

圖1 數(shù)據(jù)集MSNBC上算法的可用性

圖2是算法DP-FSM和PFS2在數(shù)據(jù)集BIBLE上的性能結(jié)果。從中可以看出，這兩個算法在該數(shù)據(jù)集的性能總體趨勢與在數(shù)據(jù)集MSNBC上大體相似。

圖2 數(shù)據(jù)集BIBLE上算法的可用性

5.2.2 閾值修正策略對DP-FSM算法性能的影響

為研究閾值修正策略對DP-FSM算法準確度的影響，將不帶閾值修正策略的挖掘頻繁序列模式的算法稱為DP-RS。圖3分析了閾值修正策略隨著σk的變化對算法性能的影響。從中可以看出，帶閾值修正的DP-FSM算法的性能優(yōu)于不帶閾值修正策略的DP-RS算法，并且隨著閾值參數(shù)σk的增大，兩個算法的性能差異性越大。因為閾值修正策略減少了挖掘頻繁序列過程中的截斷誤差與傳播誤差，故相對于DP-RS算法，DP-FSM算法的準確度較高。又由于隨著σk的增大，對頻繁序列的要求更為嚴格，DP-RS算法由于誤差的存在導致結(jié)果集中存在許多非頻繁模式，從而導致FNR增大；并且大多非頻繁模式的支持度較低，故DP-RS算法的RSE也較大。

圖3 閾值修正策略對算法可用性的影響

6 結(jié)語

本文首次針對頻繁序列模式挖掘過程中的隱私泄露問題,提出了一種滿足ε-差分隱私的算法DP-FSM。該算法首先從候選集中挖掘所有頻繁序列模式，然后采用幾何機制對挑選出來的模式的支持度添加幾何噪聲擾動。除此之外，為了提高挖掘結(jié)果的可用性，本文提出了一個閾值修正策略來減小挖掘過程中的截斷誤差和傳播誤差。最后，通過實驗驗證了該算法在滿足差分隱私的前提下可獲得較高的數(shù)據(jù)可用性。在未來的工作中，我們將研究如何合理地分配隱私預算使得挖掘結(jié)果的準確度達到最高值。

)

[1]SWEENEYL.k-Anonymity： a model for protecting privacy [J].International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2002, 10(5): 557-570.

[2] DWORK C.Differential privacy: a survey of results [C]// TAMC 2008: Proceedings of the 5th International Conference on Theory and Applications of Models of Computation, LNCS 4978.Berlin: Springer-Verlag, 2006: 1-19.

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

[4] CHEN R, ACS G, CASTELLUCCIA C.Differentially private sequential data publication via variable-lengthn-grams [C]// CCS ’12: Proceedings of the 7th ACM CCS Conference on Computer and Communications Security.New York: ACM, 2012: 638-649.

[5] BONOMI L, XIONG L.A two-phase algorithm for mining sequential patterns with differential privacy [C]// CIKM ’13: Proceedings of the 22nd ACM International Conference on Conference on Information & Knowledge Management.New York: ACM, 2013: 269-278.

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

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

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

[9] 張嘯劍,王淼,孟小峰.差分隱私保護下一種精確挖掘top-k頻繁模式方法[J].計算機研究與發(fā)展,2014,51(1):104-114.(ZHANGXJ,WANGM,MENGXF.Anaccuratemethodforminingtop-kfrequent pattern under differential privacy [J].Journal of Computer Research and Development, 2014, 51(1): 104-114).

[10] 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.

[11] CHEN R, MOHAMMED N, FUNG B C M, et al.Publishing set-valued data via differential privacy [C]// Proceedings of the VLDB Endowment, 2011, 4(11): 1087-1098.

[12] LEE J, CLIFTONC W.Top-kfrequent itemsets via differentially private FP-trees [C]// KDD ’14: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York: ACM, 2014: 930-940.

[13] DWORK C, McSHERRY F, NISSIM K.Calibrating noise to sensitivity in private data analysis [C]// TCC 2006: Proceeding of the Third Theory of Cryptography Conferenc, LNCS 3876.Berlin: Springer-Verlag, 2006: 265-284.

[14] GHOSH A, ROUGHGARDEN T, SUNDARARAJAN M.Universally utility-maximizing privacy mechanisms [C]// STOC ’09: Proceedings of the 41th ACM STOC Annual Symposium on Theory of Computing.New York: ACM, 2009: 351-360.

[15] AGRAWAL R, SRIKANT R.Fast algorithms for mining association rules [C]// VLDB ’94: Proceedings of the 20th Conference of Very Large Data Bases.San Francisco, CA: Morgan Kaufmann Publishers, 1994: 487-499.

[16] ZHANG C, HAN J, SHOU L, et al.Splitter: mining fine-grained sequential patterns in semantic trajectories [J].Proceedings of the VLDB Endowment, 2014, 7(9): 769-780.

This work is partially supported by the National Natural Science Foundation of China (61033007, 61622202, 61572119), the National Program on Key Basic Research Project (973 Program) (2012CB316201), the Fundamental Research Funds for the Central Universities (N150402005).

LI Yanhui, born in 1989, Ph.D.candidate.Her research interests include data privacy, data query processing.

LIU Hao, born in 1991, M.S.candidate.His research interests include privacy preserving, data mining.

YUAN Ye, born in 1981, Ph.D., professor.His research interests include cloud computing, big data management.

WANG Guoren, born in 1966, Ph.D., professor.His research interests include uncertain data management, graph data management, crowdsourcing data management.

Frequent sequence pattern mining with differential privacy

LI Yanhui*, LIU Hao, YUAN Ye, WANG Guoren

(SchoolofComputerScienceandEngineering,NortheasternUniversity,ShenyangLiaoning110819,China)

Focusing on the issue that releasing frequent sequence patterns and the corresponding true supports may reveal the individuals’ privacy when the data set contains sensitive information, a Differential Private Frequent Sequence Mining (DP-FSM) algorithm was proposed.Downward closure property was used to generate a candidate set of sequence patterns, smart truncating based technique was used to sample frequent patterns in the candidate set, and geometric mechanism was utilized to perturb the true supports of each sampled pattern.In addition, to improve the usability of the results, a threshold modification method was proposed to reduce truncation error and propagation error in mining process.The theoretical analysis show that the proposed method isε-differentially private.The experimental results demonstrate that the proposed method has lower False Negative Rate (FNR) and Relative Support Error (RSE) than that of the comparison algorithm named PFS2, thus effectively improving the accuracy of mining results.

frequent sequence mining; Differential Privacy (DP); privacy protection; geometric mechanism; data mining

2016- 08- 12;

2016- 09- 06。 基金項目:北京市自然科學基金資助項目(4131001, 4142023)。

房俊(1976—),男,江蘇南京人,副研究員,博士,主要研究方向:云數(shù)據(jù)管理、海量時空數(shù)據(jù)管理; 李冬(1989—),男,湖南永州人,碩士研究生,主要研究方向:云數(shù)據(jù)管理; 郭會云(1992—),女,河南漯河人,碩士研究生,主要研究方向:分布式系統(tǒng)調(diào)度; 王嘉怡(1993—),女,北京人,碩士研究生,主要研究方向:海量時空數(shù)據(jù)管理。

1001- 9081(2017)02- 0311- 05

10.11772/j.issn.1001- 9081.2017.02.0311

TP311.13;TP

A