滿足差分隱私的一種頻繁序列挖掘算法

李玉偉，楊 庚,2

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院、軟件學(xué)院、網(wǎng)絡(luò)空間安全學(xué)院，江蘇 南京 210023；2.江蘇省大數(shù)據(jù)安全與智能處理重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210023)

0 引 言

頻繁模式挖掘在數(shù)據(jù)處理方面具有重要意義，頻繁模式挖掘最早由Agrawal等人[1]提出，在他們的研究中，頻繁模式被定義為頻繁項(xiàng)集，其目的是在事務(wù)數(shù)據(jù)庫中挖掘出消費(fèi)者的購買習(xí)慣，通過分析消費(fèi)者已經(jīng)購買的商品中不同物品之間的聯(lián)系，觀察者可以制定出更優(yōu)的市場策略。頻繁模式挖掘算法目前在網(wǎng)絡(luò)信息安全、金融預(yù)測、地震監(jiān)測和營銷策略等領(lǐng)域均得到了廣泛應(yīng)用。頻繁模式算法的范圍隨著研究的不斷深入也已經(jīng)從最初的頻繁項(xiàng)集挖掘，擴(kuò)展至挖掘更復(fù)雜的模式，比如頻繁子圖挖掘[2]、頻繁序列挖掘[3]等等。

頻繁序列挖掘算法的目的就是在以序列形式儲存的數(shù)據(jù)集中挖掘出頻繁的序列事務(wù)。對于序列而言，某一序列中可以多次出現(xiàn)相同項(xiàng)，這是其與項(xiàng)集的差別。因此序列的長度就能突破字符種類上限的限制，序列的種類也會隨序列的大小增加呈指數(shù)級增長。序列模式和序列數(shù)據(jù)，如軌跡或DNA序列，在許多應(yīng)用中被廣泛使用。例如，從主要道路收集的交通數(shù)據(jù)可用于確定出行最多的地區(qū)和預(yù)測交通擁堵。然而頻繁序列模式的內(nèi)容和支持度的計(jì)數(shù)都會導(dǎo)致用戶信息的安全得不到保障[4]。為了解決該問題，Dwork等人[5]在2006年提出了差分隱私模型。該模型在挖掘過程和發(fā)布數(shù)據(jù)中對支持度添加擾動噪音，為數(shù)據(jù)隱私提供了強(qiáng)有力的、可證明的保障。差分隱私保護(hù)模型的隱私保護(hù)手段是可量化并且嚴(yán)格的，其隱私保護(hù)強(qiáng)度與入侵者持有的信息無關(guān)。由于該模型在挖掘過程中對數(shù)據(jù)進(jìn)行噪音擾動，可以達(dá)到在原數(shù)據(jù)集中改變序列記錄并不會導(dǎo)致挖掘結(jié)果出現(xiàn)較大波動的目的。

目前已經(jīng)有了一些具有差分隱私保護(hù)的序列挖掘算法，但這些挖掘算法大多是缺乏交互性的非漸進(jìn)式的算法。在選擇了數(shù)據(jù)集和確定了最小閾值之后，用戶啟動算法(比如PrefixSpan算法)，在算法停止之前，中間的過程中不會得到任何回應(yīng)。這樣的延遲對于數(shù)據(jù)挖掘的生產(chǎn)力有很大的影響，因此將操作者對于挖掘信息的即時判斷處理加入到整體的挖掘過程中十分有必要。Sacha等人提出的Prosecco算法[6]就是一種漸進(jìn)式的、滿足交互性的頻繁序列挖掘算法。但此算法同樣存在隱私泄露的問題。該文在Prosecco算法的基礎(chǔ)上，采用差分隱私保護(hù)技術(shù)對其進(jìn)行安全性保障，設(shè)計(jì)了一種滿足差分隱私保護(hù)的序列挖掘算法ProSVT。主要貢獻(xiàn)如下：

(1)針對交互式、漸進(jìn)式的序列挖掘算法添加差分隱私保護(hù)機(jī)制。ProSVT周期性地返回給用戶高度近似的頻繁序列結(jié)果。這種漸進(jìn)式的過程體現(xiàn)在根據(jù)用戶定義的對數(shù)據(jù)集分塊(blocks)的基礎(chǔ)下逐漸分析挖掘的過程。

(2)運(yùn)用并改善了添加噪音的機(jī)制，即雙層拉普拉斯噪音稀疏向量算法。稀疏向量法[7]是滿足差分隱私保護(hù)的一種添加拉普拉斯噪音的方法，該文將其運(yùn)用于挖掘頻繁序列的算法中，并且在添加閾值噪音的位置做了改變，使添加噪音后算法挖掘結(jié)果更精確和穩(wěn)定。

1 相關(guān)工作

在目前的隱私保護(hù)模型方法中，k-匿名模型[8]已經(jīng)得到了廣泛的研究并應(yīng)用于各領(lǐng)域，而后續(xù)研究表明，信息入侵者持有的信息量在很大程度上會影響模型的安全性，而且k-匿名模型的隱私保護(hù)水平并未得到有效且嚴(yán)格的證明。針對這些問題，Dwork提出的差分隱私保護(hù)模型(2006)可以抵擋各類對數(shù)據(jù)信息的攻擊，并且同時可以設(shè)定隱私參數(shù)來決定其隱私保護(hù)水平。Dwork證明了在背景知識存在的情況下，絕對隱私保護(hù)是不可能的，由此產(chǎn)生了基于不可區(qū)分性的差分隱私概念。差分隱私要求任何計(jì)算對單個記錄的更改不敏感，也就是說，針對任意一條記錄，數(shù)據(jù)庫包含或者不包含該條記錄不影響最后計(jì)算的結(jié)果。因此，這意味著掌握某條記錄的攻擊者不能根據(jù)對數(shù)據(jù)庫的操作得到關(guān)于該條記錄的任何有價值信息。實(shí)現(xiàn)該模型的噪音機(jī)制一般分為兩種情況，如果數(shù)據(jù)為非數(shù)值型采用指數(shù)機(jī)制，反之則采用拉普拉斯機(jī)制。

該領(lǐng)域的研究現(xiàn)狀在文獻(xiàn)[9]中已經(jīng)得到了非常詳盡的介紹。滿足差分隱私保護(hù)的頻繁模式挖掘的研究，最早從頻繁項(xiàng)集挖掘相關(guān)算法開始。文獻(xiàn)[4]定義了一個新的效用概念top-k用來量化頻繁項(xiàng)集挖掘算法的輸出精度，即返回數(shù)據(jù)集中前k個最頻繁的項(xiàng)集作為輸出結(jié)果，該算法將模式長度大于lmax的事務(wù)截斷，然后添加Laplace噪音對支持度進(jìn)行擾動以達(dá)到安全性，但當(dāng)參數(shù)k和lmax較大時，算法不能保證其挖掘性能。文獻(xiàn)[10]提出的PrivBasis算法利用了一種稱為θ-基的新概念，θ-基集具有頻率大于θ的項(xiàng)集是某個基集的子集的性質(zhì)，該算法采用的top-k頻繁項(xiàng)集挖掘可以看作是通過降維的方式來處理高維數(shù)據(jù)。文獻(xiàn)[11]中提出的DP-topkP算法通過后置處理噪音支持度的方式使結(jié)果滿足一致性約束，同時也增強(qiáng)了其可用性。由于較長的數(shù)據(jù)事務(wù)會使數(shù)據(jù)集的敏感度提高，文獻(xiàn)[12]提出了一種截斷長事務(wù)的方法，并且將截斷引發(fā)的錯誤與噪音引發(fā)的錯誤進(jìn)行權(quán)衡，該top-k算法在k不是很小的情況下能獲得較好可用性的挖掘結(jié)果。和頻繁項(xiàng)集挖掘相比，頻繁序列挖掘存在高維和序列性的特點(diǎn)，因此這些算法尚不能應(yīng)用于挖掘頻繁序列。

文獻(xiàn)[13]提出的基于混合粒度前綴樹結(jié)果算法首次實(shí)現(xiàn)了發(fā)布軌跡數(shù)據(jù)(頻繁序列挖掘)中的差分隱私保護(hù)。該算法在構(gòu)建前綴樹的過程中使用Laplace噪音對數(shù)據(jù)進(jìn)行擾動，使其發(fā)布的數(shù)據(jù)結(jié)果滿足差分隱私保護(hù)，但是算法存在前綴樹高度增長導(dǎo)致發(fā)布數(shù)據(jù)的效用大大降低的問題。文獻(xiàn)[14]采用變長n-gram來提取序列數(shù)據(jù)庫的基本信息，利用了前綴搜索樹結(jié)果和一組基于馬爾可夫假設(shè)的新技術(shù)來降低噪音量，使算法在挖掘的過程中滿足差分隱私保護(hù)。該算法在短序列為主的數(shù)據(jù)集下有較好的表現(xiàn)，當(dāng)存在較多高維數(shù)據(jù)時挖掘結(jié)果的可用性得不到保證。PT-Sample算法[15]利用數(shù)據(jù)的統(tǒng)計(jì)特性來構(gòu)造一個基于模型的前綴樹，用于挖掘前綴和子串模式的候選集，但是該算法并不適用于挖掘非字符類型的數(shù)據(jù)。文獻(xiàn)[16]提出的DPFSM算法，設(shè)計(jì)了一種打分函數(shù)來區(qū)分不同候選序列的優(yōu)先權(quán)，然后通過閾值修正策略來減少截斷誤差與傳播錯誤，但尚未考慮到隱私預(yù)算的分配問題。以上算法都各自有其適用的方向并且都還存在一些問題，因此如何通過設(shè)計(jì)一種算法使頻繁序列挖掘的結(jié)果可用性與差分隱私保護(hù)的安全性達(dá)到較好的平衡是現(xiàn)在研究的重點(diǎn)和難點(diǎn)。

2 理論基礎(chǔ)

2.1 差分隱私

差分隱私是通過在挖掘過程中或者輸出結(jié)果中添加噪音對數(shù)據(jù)進(jìn)行擾動來保證數(shù)據(jù)的安全性，使得在數(shù)據(jù)集中改變一條記錄(移除或者添加一條記錄)之后，任何查詢的輸出結(jié)果都不會改變。差分隱私的定義如下：

定義1：對于相鄰數(shù)據(jù)庫D1和D2(D1和D2之間只相差一條記錄)，給定算法A，算法A可能輸出的結(jié)果集合為S，若算法A在數(shù)據(jù)庫D1中輸出S的概率與算法A在數(shù)據(jù)庫D2中輸出S的概率的比值小于常數(shù)值eε，稱算法A滿足ε-差分隱私保護(hù), 即：

Pr[A(D1)∈S]≤eε×Pr[A(D2)∈S]

(1)

隱私預(yù)算參數(shù)ε可以衡量算法的隱私保護(hù)強(qiáng)度，ε值越小表示安全性(隱私強(qiáng)度)越高，但是同時也會使數(shù)據(jù)的可用性降低。

實(shí)現(xiàn)差分隱私保護(hù)主要依靠對數(shù)據(jù)的支持度添加噪音的機(jī)制，主要包括Laplace機(jī)制和指數(shù)機(jī)制，前者針對實(shí)數(shù)型數(shù)據(jù)，后者針對字符型數(shù)據(jù)。噪音量的大小取決于隱私參數(shù)和全局敏感度，隱私參數(shù)是用戶自己設(shè)定的，敏感度是數(shù)據(jù)集在算法下的屬性，函數(shù)的敏感度為數(shù)據(jù)庫中改變一條事務(wù)之后函數(shù)輸出結(jié)果的最大改變量，其數(shù)學(xué)的定義如下：

定義2：對于任意一個函數(shù)f，D→Rd，函數(shù)f的敏感度Δf定義為：

(2)

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

該文的數(shù)據(jù)集為實(shí)數(shù)型數(shù)據(jù)，因此采用Laplace機(jī)制。為了使算法滿足差分隱私保護(hù)，Laplace機(jī)制在算法輸出結(jié)果中加入服從Laplace分布的隨機(jī)噪音。Laplace機(jī)制的定義如下：

定理1：對于敏感度為Δf的函數(shù)f，算法

A(D)=f(D)+Lap(λ)

(3)

滿足ε-差分隱私保護(hù)，其中Lap(λ)是服從λ=Δf/ε的Laplace分布，Laplace分布的概率密度函數(shù)為：

Pr[x|λ]=(1/2λ)e-|x|/λ

(4)

參數(shù)λ是根據(jù)隱私參數(shù)ε和函數(shù)敏感度Δf共同決定的。

由于處理的問題有時比較復(fù)雜，單個差分隱私保護(hù)算法不能解決問題，通常需要將用戶在算法中指定的隱私參數(shù)進(jìn)行合理分配并采用多個滿足差分隱私保護(hù)的安全性算法。

定理3(并行性質(zhì))：假設(shè)A1,A2,…,Ak為k個滿足差分隱私保護(hù)的算法，其中，每個算法Ai依次滿足εi-差分隱私保護(hù)(1≤i≤k)。那么，當(dāng)算法A1,A2,…,Ak分別作用于數(shù)據(jù)庫D1,D2,…,Dk(所有數(shù)據(jù)庫均不相交)時，這些算法構(gòu)成的組合算法A滿足max{εi}-差分隱私保護(hù)。

由差分隱私保護(hù)算法的串行性質(zhì)和并行性質(zhì)可以推出如下結(jié)論：當(dāng)存在多個滿足差分隱私保護(hù)的算法A1,A2,…,Ak，對于其構(gòu)成的組合算法A的隱私預(yù)算總和，根據(jù)需要處理的數(shù)據(jù)庫彼此是否相交有不同的結(jié)果，前者為所有算法的隱私預(yù)算之和，后者為所有算法中隱私預(yù)算的最大值。

2.2 頻繁序列挖掘

多條序列記錄構(gòu)成了頻繁序列挖掘的數(shù)據(jù)集，每一條用戶序列記錄都可能包含該用戶的涉及隱私安全的信息。在頻繁序列挖掘中，對于某一條序列，其在數(shù)據(jù)集中出現(xiàn)的次數(shù)被定義為該序列的支持度，支持度與數(shù)據(jù)集中所有序列記錄的數(shù)量的比值被定義為該序列的頻率。類似地，閾值也分別被定義為絕對閾值和相對閾值，對應(yīng)于支持度和頻率。如果某一序列的支持度大于絕對閾值或者其頻率大于相對閾值，就可以將該序列加入所要輸出的頻繁序列集合之中。如果未經(jīng)特殊說明，文章中的閾值一般指絕對閾值。

已知I={i1,i2,…,in}為序列數(shù)據(jù)集中項(xiàng)的集合(即字母表)。在頻繁序列挖掘中，字母表中任意項(xiàng)的一個非空集組合就構(gòu)成了一條用戶序列，例如S=a1a2…a|s|表示長度為|S|的序列(a1,a2,…,a|s|∈I)。對于一條序列S，如果|S|=k，稱S為一個長度為k的序列(即一個k-序列)。頻繁序列挖掘的目的是要發(fā)現(xiàn)序列數(shù)據(jù)庫中的所有頻繁子序列，并且計(jì)算每個頻繁序列的支持度。

3 ProSVT算法

本節(jié)詳細(xì)描述所提出的用于挖掘頻繁序列的ProSVT(Prosecco-SVT)算法。

3.1 概 述

基于Prosecco算法，設(shè)計(jì)了一種具有隱私保護(hù)功能的序列挖掘算法，Prosecco算法首先將數(shù)據(jù)集分成數(shù)量為b的子集塊，b為用戶指定的參數(shù)。在挖掘過程中，當(dāng)分析完第i個子集塊后，算法輸出一個滿足αi-近似的中間結(jié)果。中間結(jié)果在不斷更新，用戶可以根據(jù)當(dāng)前結(jié)果的價值來決定是否繼續(xù)挖掘，因此整個挖掘過程中得到的數(shù)據(jù)具有交互性質(zhì)。

一種挖掘頻繁序列的流算法采用了一種用戶相關(guān)的降低閾值(ξ<θ)的方法，并且在所有的子集塊中都使用相同的降低后的閾值，這種策略不足以保證中間結(jié)果的有效性，因?yàn)樵谀承K中有的序列支持度低于ξ，于是就會被忽略，導(dǎo)致結(jié)果不準(zhǔn)確，從而誤導(dǎo)用戶。Prosecco為了避免這種隱患，使用了塊相關(guān)的降低閾值的方法。這個過程是根據(jù)統(tǒng)計(jì)學(xué)中的相關(guān)定理確定了每個子集塊的特定參數(shù)，結(jié)合用戶先前設(shè)定的錯誤概率，共同決定誤差參數(shù)，即閾值下降的幅度。隨著挖掘過程的繼續(xù)，該幅度越來越小，最終收斂于0，閾值也收斂于標(biāo)準(zhǔn)閾值，算法輸出精確挖掘結(jié)果。

在挖掘頻繁序列的部分使用雙噪音(改善過的SVT)來為候選序列添加拉普拉斯噪音，即在序列支持度和閾值上同時添加噪音并控制噪音大小。此前的SVT法是在每個查詢序列上添加不同的隨機(jī)噪音，而在閾值上添加統(tǒng)一的一個噪音，這種做法存在弊端，如果閾值噪音過大就會導(dǎo)致整體比較結(jié)果，因此將統(tǒng)一的閾值噪音改為在每一次對查詢序列操作時在閾值上添加的不同隨機(jī)噪音，在比較噪音支持度和噪音閾值時，剔除未能達(dá)到噪音閾值的候選序列，反之就將其加入頻繁序列集合中。

3.2 算法描述

首先來詳細(xì)描述提出的ProSVT算法(如Algorithm1所示)，其輸入?yún)?shù)有數(shù)據(jù)集D，子集塊數(shù)量b，閾值θ，錯誤概率δ，敏感度Δ，隱私預(yù)算ε，算法的輸出為最終的頻繁序列集合。

ProSVT算法將數(shù)據(jù)集D分割成β個子集塊B1,B2,…,Bβ，其中β=|D|/b，在同一時間只處理一個子集塊。根據(jù)統(tǒng)計(jì)學(xué)的Vapnik-Chervonenkis(VC) dimension及相關(guān)公式計(jì)算出的誤差參數(shù)α，然后由該誤差參數(shù)α得到降低后的閾值ξ，將參數(shù)ξ作為新的閾值進(jìn)行頻繁序列挖掘，獲得第一個子集塊的輸出結(jié)果。接著依次對后面的子集塊進(jìn)行操作，不斷更新輸出序列集，得到最終結(jié)果F并輸出。

Algorithm 1：ProSVT

Input：datasetD，block sizeb，minimum frequency thresholdθ，failure probabilityδ，sensitivity Δ，privacy budgetε

Output：a setF

1β←|D|/b

3ξ←θ-α/2

4Q←pretreatment(B1)

5F←doubleNoise-getFS(B1,Q,Δ,ξ,ε)

6 returnIntermeiateResult (F,α)

7 for eachi←2，…，β-1 do

9ξ←θ-α/2

10Q←pretreatment(Bi)

11F←upadteRunningSet (F,doubleNoise-getFS(Bi,Q,Δ,ξ,ε))

12 returnIntermediateResult(F,α)

13F←upadteRunningSet(F,Bβ,ξ)

14 returnF

Algorithm2是改善過后的SVT法，即doubleNoise-getFS算法。該算法的輸入為子集塊B，查詢隊(duì)列Q，敏感度Δ，下調(diào)閾值ξ，隱私參數(shù)ε，輸出為查詢結(jié)果。

doubleNoise-getFS算法中，先將給定的隱私參數(shù)ε分為ε1(分配給支持度的隱私預(yù)算)和ε2(分配給支持度的隱私預(yù)算)，然后分別計(jì)算出支持度噪音和閾值噪音，接著對于查詢隊(duì)列Q中每個查詢序列的支持度和閾值添加噪音，保留噪音支持度大于噪音閾值的序列，并將其加入挖掘算法的中間結(jié)果。

Algorithm 2：doubleNoise-getFS

Input：subsetB,query queueQ,sensitivity Δ，lower frequencyξ，privacy budgetε

Output：query answera1,a2,…，a setF

1ε1=ε2=ε/2

3 for each queryqi∈Qdo

4 ifqi(B)+ρ1≥ξ+ρ2then

5 Outputai=qi(B) andF.add(ai), count+1

6 else

7 Outputai=⊥

3.3 隱私性證明

定理4：ProSVT算法滿足ε1+ε2-差分隱私。

證明：由于在ProSVT整體算法中，doubleNoise-getFS算法中加入了支持度噪音和閾值噪音，因此需要證明加噪過程滿足差分隱私保護(hù)。對于任意的輸出a={丅,丄}l，只要證得：

(5)

首先考慮第一種情況：

fi(B,z)=Pr[qi(B)+ρ2<ξ+z]≤

Pr[qi(B')+ρ2<ξ+z]=

fi(B',z)

(6)

gi(B,z)=Pr[qi(B)+ρ2≥ξ+z]≤

Pr[qi(B')+ρ2+Δ≥ξ+z]≤

eε2Pr[qi(B')+ρ2≥ξ+z]=

eε2gi(B',z)

(7)

又因?yàn)閨I┬|≤c，所以,

eε2Pr[A(B')=a]<

eε1+ε2Pr[A(B')=a]

(8)

然后考慮第二種情況：

?iqi(B)≤qi(B')，記qi(B)≥qi(B')-Δ，所以有：

fi(B,z-Δ)=Pr[qi(B)+ρ2<ξ+z-Δ]≤

Pr[qi(B')-Δ+ρ2<ξ+z-Δ]=

fi(B',z)

(9)

考慮到約束條件qi(B)≤qi(B')，所以有：

gi(B,z-Δ)=Pr[qi(B)+ρ2≥ξ+z-Δ]≤

Pr[qi(B')+ρ2≥ξ+z-Δ]≤

eε2Pr[qi(B')+ρ2≥ξ+z]=

eε2gi(B',z)

(10)

再將積分變量z轉(zhuǎn)換為z-Δ，可得：

eε1+ε2Pr[A(B')=a]

(11)

因此，該算法滿足ε1+ε2-差分隱私。

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

本節(jié)對提出的ProSVT算法進(jìn)行實(shí)驗(yàn)仿真，并從精確率、召回率和F-score等方面對ProSVT算法進(jìn)行性能分析。

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

實(shí)驗(yàn)環(huán)境為Intel? CoreTMi7-9750H CPU@2.60 GHz，16 GB內(nèi)存，Windows10 64位操作系統(tǒng)，實(shí)驗(yàn)用Java語言實(shí)現(xiàn)具體的ProSVT算法。

4.1.1 數(shù)據(jù)集

實(shí)驗(yàn)基于兩個公開可獲得的真實(shí)序列數(shù)據(jù)集(見表1)。

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

MSNBC數(shù)據(jù)集為1999年9月28日msnbc.com網(wǎng)站按照時間順序記錄下的用戶訪問，數(shù)據(jù)集中的每個序列對應(yīng)于該用戶在24小時內(nèi)的頁面瀏覽點(diǎn)擊，該數(shù)據(jù)集共有989 818條序列記錄，點(diǎn)擊項(xiàng)為17項(xiàng)，對應(yīng)了17個頁面類別，序列平均長度為5.7。BMSWebView1數(shù)據(jù)集用于KDD CUP 2000，它包含來自電子商務(wù)的clickstream數(shù)據(jù)，序列量為59 601，共包含497個不同的項(xiàng)，序列平均長度為2.5。

4.1.2 測試對象

測試主要集中在三個算法：(a)ProSVT：此算法是該文提出的差分隱私保護(hù)下的頻繁序列挖掘算法；(b)Prefix：這是文獻(xiàn)[13]中提出的一種構(gòu)造前綴樹挖掘頻繁序列的差分隱私保護(hù)算法；(c)N-gram：此算法是利用可變長度的n-gram模型來挖掘頻繁序列的差分隱私保護(hù)算法[14]。

4.1.3 指 標(biāo)

在實(shí)驗(yàn)中測試的衡量標(biāo)準(zhǔn)為Precision、Recall和F-score。其中Precision為挖掘的精確率，Recall為挖掘的召回率，F(xiàn)-score為兩者的綜合評價指標(biāo)。設(shè)Up是由具有隱私保護(hù)的算法挖掘得到的頻繁項(xiàng)集，Uc是真實(shí)的頻繁項(xiàng)集，具體定義如下：

(12)

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

本節(jié)首先針對最低閾值θ和隱私預(yù)算ε對ProSVT算法進(jìn)行測試，然后將ProSVT與Prefix、N-gram進(jìn)行對比，并分析實(shí)驗(yàn)得出的結(jié)果。由于敏感度和序列長度成正比，因此在本實(shí)驗(yàn)中用平均序列長度來表征敏感度。

4.2.1 不同閾值

這里測試了ProSVT算法在隱私預(yù)算固定時，改變閾值對其挖掘性能造成的影響。圖1和圖2分別是在MSNBC和BMSWebView1數(shù)據(jù)集下的測試結(jié)果。實(shí)驗(yàn)結(jié)果表明，隨著閾值的提升，挖掘結(jié)果的精確率、召回率都有明顯的增加，從而使F-score也得到提升。因?yàn)殚撝堤岣吆?，算法挖掘的候選頻繁序列數(shù)目減少，出現(xiàn)誤差的可能減少，由此提高了挖掘性能。用戶在挖掘頻繁序列時，不宜將閾值設(shè)置得過低，否則會大大降低挖掘結(jié)果的可用性。

圖1 MSNBC：不同θ下的挖掘性能

圖2 BMSWebView1：不同θ下的挖掘性能

4.2.2 不同隱私預(yù)算

這里測試了ProSVT算法在最低閾值固定時，改變隱私預(yù)算對其挖掘性能造成的影響。圖3和圖4分別是在MSNBC和BMSWebView1數(shù)據(jù)集下的測試結(jié)果?？梢钥闯鲭S著隱私預(yù)算的提升，挖掘結(jié)果的精確率、召回率都有明顯的增加，從而使F-score也得到提升。當(dāng)隱私預(yù)算增加時，所添加的拉普拉斯噪音隨之降低，因此理論上會使挖掘結(jié)果更加精確。

圖3 MSNBC：不同ε下的挖掘性能

4.2.3 ProSVT與其他算法

這里測試當(dāng)固定閾值，改變隱私預(yù)算時在兩個數(shù)據(jù)集中ProSVT、Prefix以及N-gram算法的F-socre指標(biāo)變化，如圖5和圖6所示。對于MSNBC數(shù)據(jù)集，ProSVT在低隱私預(yù)算時表現(xiàn)較差，當(dāng)隱私預(yù)算大于0.4后，其挖掘性能較Prefix和N-gram更優(yōu)秀；對于BMSWebView1數(shù)據(jù)集，ProSVT在各種大小的隱私預(yù)算情況下的挖掘性能表現(xiàn)都要優(yōu)于Prefix和N-gram。

圖5 MSNBC：三種算法的挖掘性能對比

圖6 BMSWebView1：三種算法的挖掘性能對比

5 結(jié)束語

提出了一種滿足差分隱私保護(hù)的頻繁序列挖掘算法ProSVT。此算法是在Prosecco算法的基礎(chǔ)上加入了改善過后的雙拉普拉斯噪音方法以保證挖掘期間的差分隱私機(jī)制，以其漸進(jìn)式、交互性的特點(diǎn)給挖掘者更便捷、有效的挖掘頻繁序列的體驗(yàn)。在真實(shí)數(shù)據(jù)集下的相關(guān)實(shí)驗(yàn)表明了最低閾值和隱私預(yù)算的分配對于挖掘性能的影響，在和其他算法對比的過程中，ProSVT也有比較出色的表現(xiàn)。在隱私預(yù)算的分配中，對于支持度噪音和閾值噪音的隱私預(yù)算分配采用均分的方法，進(jìn)一步的研究中可以針對隱私預(yù)算分配方法作深入的探討。