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

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

(東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽110819)

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

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

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

(東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽110819)

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

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

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

0 引言

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

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

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

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

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

1 相關(guān)工作

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

1.1 頻繁項(xiàng)集挖掘

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

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

1.2 頻繁序列挖掘

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

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

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

2 問題定義

2.1 差分隱私

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

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

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

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

(1)

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

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

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

(2)

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

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

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

(3)

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

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

(4)

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

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

(5)

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

2.2 頻繁序列模式挖掘

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

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

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

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

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

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

3 DP-FSM算法

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

3.1 算法描述

算法1 DP-FSM算法。

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

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

1)

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

3)

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

//估計(jì)頻繁序列的最大長(zhǎng)度

4)

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

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

//順序挖掘所有長(zhǎng)度小于lf的頻繁序列；

5)

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

DP-FSM主要由預(yù)處理、挖掘和擾動(dòng)三個(gè)階段組成。

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

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

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

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

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

3.2 挖掘頻繁序列模式

算法2DP-MiningFrequentSequence。

輸入 頻繁序列最大長(zhǎng)度lf，截?cái)嘈蛄虚L(zhǎng)度約束lmax，隱私預(yù)算ε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)

//截?cái)鄶?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描述了隱私地挖掘頻繁序列模式的過程，其核心思想是利用候選序列在截?cái)嘈蛄袛?shù)據(jù)庫D′中的噪聲支持度判斷該候選序列是否頻繁。同時(shí)，為了提高挖掘結(jié)果的準(zhǔn)確度，該算法從兩個(gè)方面對(duì)閾值進(jìn)行修正:1)截?cái)嘈蛄袛?shù)據(jù)庫后會(huì)造成某些候選序列頻率信息的損失，考慮到這種截?cái)嗲闆r產(chǎn)生的誤差(稱之為截?cái)嗾`差)，該算法修正判斷閾值σk為σk-avg(θ′)+θ′，其中avg(θ′)為根據(jù)序列的噪聲支持度θ′估計(jì)該序列在原數(shù)據(jù)庫中的平均支持度。2)如果一個(gè)頻繁序列模式被錯(cuò)誤地標(biāo)注為不頻繁的模式，則它的任何超序列在不計(jì)算其支持度的情況下即被判定為不頻繁的序列模式?？紤]到這種情況產(chǎn)生的傳播誤差， 修正判斷某一序列是否用于產(chǎn)生候選序列的閾值為σk-max(θ′)+θ′，其中max(θ′)為根據(jù)序列的噪聲支持度θ′估計(jì)該序列在原數(shù)據(jù)庫中的最大支持度。

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

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

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

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

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

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

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

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

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

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

(6)

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

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

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

例2 繼續(xù)上面的例1，同時(shí)假設(shè)候選序列的權(quán)重情況如下集合所示：{ab:8;bc:6;cd:4;ac:2}；以及假設(shè)序列限制長(zhǎng)度為4。經(jīng)過無關(guān)項(xiàng)刪除機(jī)制和連續(xù)模式壓縮機(jī)制處理后，序列A由序列A2=ababbcd表示，但它的長(zhǎng)度依然大于限制長(zhǎng)度4，因此需要根據(jù)智能序列重構(gòu)機(jī)制處理。依據(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添加到事務(wù)t′中，此時(shí)t′=abc，長(zhǎng)度仍小于約束長(zhǎng)度4。再按同樣的方法進(jìn)行下一次迭代，得到t′=abcd。此時(shí)t′的長(zhǎng)度已達(dá)到了序列限制長(zhǎng)度，因此，用序列abcd表示原序列A=abababebcdfg。

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

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

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

(7)

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

(8)

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

(9)

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

(10)

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

max(θ″)=

(11)

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

(12)

最大支持度為：

(13)

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

4 隱私性能分析

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

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

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

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

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

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

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

5.1 實(shí)驗(yàn)設(shè)置

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

表1 實(shí)驗(yàn)數(shù)據(jù)集參數(shù)

(14)

(15)

5.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

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

6 結(jié)語

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

)

[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] 張嘯劍,王淼,孟小峰.差分隱私保護(hù)下一種精確挖掘top-k頻繁模式方法[J].計(jì)算機(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。 基金項(xiàng)目:北京市自然科學(xué)基金資助項(xiàng)目(4131001, 4142023)。

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

1001- 9081(2017)02- 0311- 05

10.11772/j.issn.1001- 9081.2017.02.0311

TP311.13;TP

A