朱美琪，楊 庚，白云璐

(1.南京郵電大學(xué) 計算機學(xué)院、網(wǎng)絡(luò)空間安全學(xué)院，江蘇 南京 210023；2.江蘇省大數(shù)據(jù)安全和智能處理重點實驗室，江蘇 南京 210023；3.南京市醫(yī)藥大學(xué) 信息技術(shù)學(xué)院，江蘇 南京 210023)

0 引 言

頻繁項目挖掘(frequent items mining)是當(dāng)前數(shù)據(jù)挖掘研究的熱點問題之一，其算法的核心是找出數(shù)據(jù)集中頻繁出現(xiàn)的項。top-k頻繁項目挖掘[1]是挖掘出前k個頻繁出現(xiàn)的項。該思想已廣泛運用到現(xiàn)實生活中。例如，視頻網(wǎng)站可以通過對所有用戶觀看的影片進行記錄、分析，然后向用戶推薦本周最受歡迎的前十個電影。在記錄用戶信息的過程中，如果不做任何隱私保護措施，最后的推薦結(jié)果可能會有很高的準(zhǔn)確性，但會嚴(yán)重侵犯用戶的隱私。因此，在保證用戶隱私性的同時要保證挖掘結(jié)果的準(zhǔn)確性已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域亟待解決的問題之一。

差分隱私[2]作為一個有效的隱私保護機制，現(xiàn)已廣泛運用到瀏覽器、系統(tǒng)等應(yīng)用中。例如Apple的IOS系統(tǒng)和Google的Chrome都運用了差分隱私的思想來保護用戶的隱私。差分隱私又分為中心化差分隱私與本地化差分隱私，其中中心化差分隱私技術(shù)中，算法的隱私性通過臨近數(shù)據(jù)集來定義，因此其要求一個可信的第三方數(shù)據(jù)收集者對數(shù)據(jù)分析結(jié)果進行隱私化處理，而對于本地化差分隱私技術(shù)而言，每個用戶能夠獨立地對個體數(shù)據(jù)進行處理。目前已經(jīng)有了許多關(guān)于本地化差分隱私的頻繁項目挖掘算法，例如Zhan Qin提出的LDPMiner[3-4]算法，該算法在保護用戶隱私的同時，比較了當(dāng)前已有的滿足本地化差分隱私的保護算法，并對其進行優(yōu)化，在一些真實數(shù)據(jù)集上有較好的表現(xiàn)。但該算法在面對大量用戶的真實數(shù)據(jù)挖掘的問題時，面臨了一些新的挑戰(zhàn)：(1)因為用戶量的增大，挖掘的時間復(fù)雜度也隨之增大；(2)可以對用戶進行分組挖掘來降低時間復(fù)雜度，但同時需要保持挖掘結(jié)果的可用性。所以，如何在保證時間復(fù)雜度降低的同時也能提高挖掘頻繁項目的可用性就成了研究的關(guān)鍵所在。因此，該文通過基于本地化差分隱私保護，對用戶進行分組挖掘的思想，設(shè)計了一種頻繁項目挖掘的算法GFIM(group-based frequent items mining)。

主要貢獻如下：

(1)為了提高挖掘頻繁項目的可用性，設(shè)計了一種基于分組思想的滿足本地化差分隱私挖掘算法，并在理論上證明了該算法滿足ε-本地化差分隱私，多個真實數(shù)據(jù)集上的實驗表明該算法的性能要優(yōu)于LDPMiner算法。

(2)在GFIM算法中，采用將整個運行過程分成兩個階段、用戶數(shù)據(jù)分為兩組的策略，在保證高可用性的同時，減少了挖掘時計算的次數(shù)，從而加快了挖掘數(shù)據(jù)的時間，達到了優(yōu)化算法時間復(fù)雜度的效果。

1 相關(guān)工作

在Warner首次對隨機響應(yīng)的方法進行研究[5]之后，研究者們開始探索其他擾動機制。Hsu等[6]集中在基于隨機投影和測度集中的技術(shù)來估計頻繁項目。繼這項工作，Bassily等[7]提出了一種有效的協(xié)議，用于SH(succinct histogram)估計與信息理論上的誤差。為了處理隱私預(yù)算的問題，提出了RAPPOR[8-9]，SH和RAPPOR的相關(guān)信息將在第二節(jié)進行介紹。此外，關(guān)于頻繁項集挖掘的文獻也很豐富。其中，有幾篇與文中的研究方向有關(guān)。 Bhaskar等[10]提出了一種基于兩階段的方法，該方法使用截短的頻率閾值來縮小頻繁項集的候選列表。算法可以概括為如下兩步：(1)計算出一個m值，從所有長度不大于m的候選項組成的集合C中挑選出top-k頻繁項集；(2)對挑選出的k個項集的真實支持度添加拉普拉斯噪聲后發(fā)布。該算法的問題在于第一步，因為其候選項集合C呈指數(shù)規(guī)模增大，即|C|=|I|m(|I|表示項集域的大小)，若遍歷C中所有項集，則每個項集能分到的隱私預(yù)算將會很少，計算結(jié)果將會很不準(zhǔn)確。TF應(yīng)用截斷頻率技術(shù)對C中項集進行篩選，只需遍歷C中支持度大于fk-γ的項集(其中fk表示第k頻繁項集的支持度真實計數(shù)，γ是調(diào)節(jié)參數(shù))。在一般情況下，使用該技術(shù)可以對候選項集合C進行有效篩選，但是隨著k值的增加，該篩選條件會被弱化，甚至失效。丁哲[11]為了從不確定的數(shù)據(jù)集中挖掘出基于期望支持度的前k個最頻繁的頻繁項集,并且保證挖掘結(jié)果滿足差分隱私,提出了FIMUDDP算法。該算法利用差分隱私的指數(shù)機制和拉普拉斯機制確保從不確定數(shù)據(jù)中挖掘出的基于期望支持度的前k個最頻繁的頻繁項集和這些頻繁項集的期望支持度滿足差分隱私小的項,從而降低發(fā)布的頻繁項集的支持度誤差。

然而，所有上述機制都需要對數(shù)據(jù)集有全局了解，這使得它們不適用于本地化差分隱私。盡管上述已有工作并非所有針對中心化差分隱私的技術(shù)都適合于本地化差分隱私，但這些技術(shù)背后的思想仍有助于筆者設(shè)計符合LDP的算法。

2 理論基礎(chǔ)

2.1 本地化差分隱私

近年來，本地化差異隱私作為一種區(qū)別于中心化差分隱私的隱私保護模式，引起了人們的廣泛關(guān)注。它的隱私化處理發(fā)生在用戶的本地設(shè)備中，用戶對自己的個人數(shù)據(jù)進行加噪再發(fā)給數(shù)據(jù)收集者。數(shù)據(jù)收集者得到的是不準(zhǔn)確的用戶數(shù)據(jù)，這樣能夠避免不可信的第三方造成隱私的泄露。下面給出正式的定義：

定義1(ε-本地化差分隱私)：假設(shè)有一個隨機算法A，A的所有輸出構(gòu)成集合O，A的所有取值構(gòu)成集合I，如果對于任意兩條記錄R∈I和R'∈I以及任意一個輸出S∈O，存在：

Pr(A(R)∈S)

(1)

則稱算法A滿足ε-本地化差分隱私，其中ε稱為隱私參數(shù)或隱私預(yù)算。

定義3(并行組合性)：假設(shè)有隨機算法A1,A2,…,An，其隱私參數(shù)分別為ε1,ε2,…,εn，當(dāng)這些算法作用于不相交的數(shù)據(jù)集D1,D2,…,Dn時，這些算法構(gòu)成的組合算法A(A1(I),A2(I),…,An(I))對這些數(shù)據(jù)集提供max(εi)-差分隱私保護。

此性質(zhì)表明，當(dāng)多個隨機算法作用的數(shù)據(jù)集兩兩之間互不相交時，它們對所有數(shù)據(jù)集提供的隱私保護水平取決于max(εi)。特殊地，當(dāng)A1=A2=…=An時，ε=εi,即當(dāng)同一個算法多次作用于不相交的數(shù)據(jù)集時，隱私保護水平不變。

2.2 頻繁項目挖掘

頻繁項目挖掘是數(shù)據(jù)挖掘的研究熱點問題之一，旨在找出頻繁出現(xiàn)在事務(wù)數(shù)據(jù)集中的top-k項目。具體描述如下：如果一個數(shù)據(jù)流σ={a1,a2,…,am}，其中m為數(shù)據(jù)流的大小，ai∈{1,2,…,n}。可以定義每個元素出現(xiàn)的次數(shù)為F=(f1,f2,…,fn)，其中fi為第i個項目出現(xiàn)的次數(shù)。如果給定參數(shù)k，求top-k頻繁項目，那么可以對F進行分析和統(tǒng)計，然后輸出的前k個項目就是top-k頻繁項目挖掘的過程。

2.3 LDP解決方案

2.3.1 隨機響應(yīng)解決方案

2.3.2 RAPPOR算法

2.3.3 Succinct Histogram算法

3 GFIM算法

本節(jié)包括GHHE算法的概述及具體實現(xiàn)細(xì)節(jié)。GFIM分為兩個階段，并將隱私預(yù)算也分為兩個部分用來完成這兩個階段，整個過程滿足ε-LDP。第一階段中，每個用戶擁有l(wèi)項，并在ε-DP下向數(shù)據(jù)收集者報告數(shù)據(jù)，數(shù)據(jù)收集者根據(jù)用戶提交的信息挖掘出一個大小為kmax=O(k)的候選集C。第二個階段，首先是對用戶進行分組，第一組根據(jù)挖掘出的候選項集C，把自身擁有的卻不在C中的項目設(shè)置為冗余項，然后把挖掘出的項集E報告給數(shù)據(jù)收集者；第二組是根據(jù)第一組挖掘出的項集E進行二次挖掘，最終得到top-k頻繁項目。

3.1 GFIM算法概述

算法1總結(jié)了GFIM算法完整的框架。其中1～2行屬于預(yù)處理部分，3屬于GFIM算法的第一階段，4～6是GFIM算法的第二階段。

算法1：GFIM算法。

Input：事務(wù)數(shù)據(jù)集D，k，隱私預(yù)算ε;

Output：top-k頻繁項目。

1.將隱私預(yù)算ε分為ε1和ε2;

2.計算真實的top-k頻繁項集;

3.使用ε1的隱私預(yù)算來獲取候選項集C;

4.將總用戶數(shù)隨機分成兩組；

5.第一組數(shù)據(jù)使用ε2的隱私，以C為候選項集預(yù)算來獲取項集E；

6.第二組數(shù)據(jù)同樣使用ε2的隱私預(yù)算，以E為候選項集來獲取top-k頻繁項目。

3.2 GFIM算法中階段一分析設(shè)計

階段一是找出頻繁項的候選集的過程。上文提到的RAPPOR和SH是兩個經(jīng)典的頻繁項目挖掘算法，但它們不能直接運用于階段一的場景，因為傳統(tǒng)的RAPPOR和SH算法均要求每個用戶的輸入為一個項目，而在文中的場景中用戶輸入的是一個經(jīng)過處理后的大小為l的項集。一個直觀的解決方案是調(diào)用l次RAPPOR或SH，再把每次調(diào)用得到的估計頻率累加得到最終的估計頻率。這個想法是可行的，但也是低效的。對這種想法的一種改進方案是從每個用戶的項集Si中隨機選取一個項作為輸入，然后采用RAPPOR或SH算法。已有的工作[2]證明了該想法的合理性，證明了其優(yōu)于前面所說的調(diào)用l次RAPPOR或SH。但是，因為每個用戶只向數(shù)據(jù)收集者發(fā)送一個隨機的項而不是所有l(wèi)個項，這樣直接的隨機抽取會導(dǎo)致有偏頻率估計。為了達到無偏估計，需要將估計的頻率乘以l。根據(jù)上文描述的RAPPOR和SH算法的對比分析，出于節(jié)約通信帶寬和提高計算效率的考慮，這里將以SH算法為基礎(chǔ)對其進行改造分析，改造后的算法稱為抽樣SH算法，抽樣SH算法將作為階段一和階段二的基本算法。抽樣SH算法與傳統(tǒng)SH算法大體一致。同時，文中采用了一種正交矩陣生成的方法，假設(shè)d?n，參考文獻[9]證明了在d?n的情況下采用正交矩陣取代完全隨機矩陣能夠提高SH的準(zhǔn)確性。

算法2：抽樣SH正交矩陣的生成。

Input：項的取值集合大小d；

Output:正交矩陣φ。

1.計算m=2「log2d?

2.S={[1，-1],[1，1]}

3.while |S|

4.S'=φ

5. forv∈Sdo

6.S'=S'∪{v‖v,v‖(-v)}

7. end for

8.S←S'

9. end while

10.N=S[1:m]

11.φ=NT

12. returnφ

算法3：抽樣SH LR(local randomizer)(用戶端部分)。

Output：干擾后的向量zi。

1.從項集Si中隨機選取一個項i；

3.ifii=⊥ then

5. else

6. 生成一個標(biāo)準(zhǔn)的基向量eii∈{0,1}；

8.end if

9.returnzi

3.3 GFIM算法中階段二分析設(shè)計

階段二的場景與階段一有所不同，不同之處有二：一是對總用戶數(shù)進行了隨機分組；二是每一組進行挖掘時的候選項集是不同的。針對這兩點不同，需要設(shè)計出相應(yīng)的解決方案。階段二中依舊采用抽樣SH作為算法的基礎(chǔ)。顯然，當(dāng)候選項集合縮小時，SH中的隨機矩陣也會相應(yīng)縮小。這一方面減少了噪音，另一方面也降低了運算開銷，最終會提高估計頻率的準(zhǔn)確性。針對第二個不同點，在用戶端上的LR(local randomizer)做了以下調(diào)整：(1)第一組LR收到候選集C后，先求出用戶原本的項集Si與候選集C的交集Ti；(2)如果交集N的大小小于kmax，補充若干個冗余項使其大小變?yōu)閗max，得到新項集Ni；(3)從Ni中隨機選取一個項ii應(yīng)用隨機響應(yīng)技術(shù)。第二組數(shù)據(jù)也要經(jīng)歷這樣的過程，區(qū)別是第二組用戶收到的不是候選項集C，而是第一組用戶響應(yīng)后的數(shù)據(jù)。這樣處理的好處是能有效增大候選集中的項被抽中的概率，進而提高候選集中的項的估計頻率準(zhǔn)確性。一個例子能很好解釋其中的原因：假設(shè)用戶ui的原項集Si包含候選集C，Si的大小為l=60，C的大小為kmax=30；在未經(jīng)過以上處理前，從Si隨機抽取一個項，該項屬于候選集的概率為1/2，但經(jīng)過(1)～(3)步處理后，被抽中的項屬于候選集的概率為1?？梢姡@樣的處理是很有效的。并且，如果不對長度小于的交集Ti填充冗余項，Ti的大小直接暴露給用戶，會給攻擊者提供額外的信息，存在著隱私泄露的風(fēng)險。階段二中的抽樣SH只能計算候選集中各項的估計頻率。然而，真實的top-k項并不一定恰好都落到候選集中，為了解決這個問題，需要把兩個階段的結(jié)果綜合利用起來。這里按以下公式得到最終各項的估計頻率：

(2)

需要說明的是，階段二中處理的兩組用戶數(shù)據(jù)并不相交，為了保證兩組數(shù)據(jù)與總數(shù)據(jù)滿足同分布，必須保證劃分?jǐn)?shù)據(jù)時是隨機劃分的。

算法4：GFIM LR(用戶端)。

Output：干擾后的向量zi。

1.求交集Ti=Si∩C；

2.if |Ti|

3. 往Ti中加入若干個冗余項得到新的用戶項集|Ni|=kmax；

4.end if

5.從項集Ni中隨機選取一個項ii；

7.ifii=⊥ then

9. else

10.生成一個標(biāo)準(zhǔn)的基向量eii∈{0,1}；

12.end if

13.returnzi

4 GFIM算法隱私保護性能分析

本地化差分隱私蘊含著兩個極其重要的性質(zhì)：序列組合性和并行組合性[15]。利用這兩個性質(zhì)，可以很容易地證明某種算法是否滿足本地化差分隱私。

GFIM算法將隱私預(yù)算ε分為兩部分，分配給算法的兩個主要步驟：階段一生成候選集ε1、階段二分組計算頻繁項目ε2。其中，選擇ε1=0.6×ε，ε2=0.4×ε。

定理:GFIM算法滿足ε-本地化差分隱私。

證明：

(1)階段一安全性證明。

(3)

(4)

進而有：

(5)

所以抽樣SH算法滿足ε1-本地化差分隱私，即階段一滿足ε1-本地化差分隱私。階段一生成一個大小為kmax的候選集。候選項目集大小的選取至關(guān)重要。候選項目集太小的話，真實的頻繁項可能會沒有落在候選集內(nèi)，導(dǎo)致估計的誤差會增大；候選集過大，kmax有可能會大于l，同樣會降低估計頻率的準(zhǔn)確性。

(2)階段二安全性證明。

假設(shè)B為階段二中第一組用戶對數(shù)據(jù)的處理算法。B的輸入是隱私參數(shù)ε2、用戶ui的項集Si和候選集C。B首先對Si進行修剪得到Ni。之后B對Ni采用抽樣SH算法，該處理過程用C表示。由階段一的證明可知，C滿足本地化差分隱私。假設(shè)S1，S2為任意兩個未修剪前的用戶項集，o表示B的任意輸出。要證第一組用戶對數(shù)據(jù)的處理算法滿足ε2-本地化差分隱私，即證：

(6)

因為修剪過程是確定的，所以有：

Pr[B(S1,ε2,C)=o]=Pr[C(N1,ε2)=o]

(7)

又C滿足本地化差分隱私，有：

(8)

由上述可知第一組用戶對數(shù)據(jù)的處理算法滿足ε2-本地化差分隱私。因為第二組用戶對數(shù)據(jù)的處理與第一組原理相同，所以第二組對數(shù)據(jù)的處理也滿足ε2-本地化差分隱私。又因為，這兩組數(shù)據(jù)不相交，根據(jù)差分隱私的并行組合原理可知，整個階段二滿足ε2-本地化差分隱私。

由于階段一，階段二分別滿足ε1和ε2-本地化差分隱私，由差分隱私的序列組合性知，ε=ε1+ε2。即，GFIM滿足ε-本地化差分隱私，證畢。

5 實 驗

5.1 實驗設(shè)置

實驗環(huán)境為Inter(R) Core(TM) i5-3230M CPU2.60 GHz，4 GB內(nèi)存，Windows10操作系統(tǒng)。算法均使用Python來實現(xiàn)。在三個真實數(shù)據(jù)集上進行了測試，這些數(shù)據(jù)集可從Spmf上下載。分別是USCensus(US Census 1990 dataset)，Mushroom(UCI mushrooms dataset)和Connect(UCIconnect-4 dataset)。表1給出了每個數(shù)據(jù)集中的幾種特征，包括事務(wù)數(shù)量、項集域大小以及平均事務(wù)長度。通過實驗將LDPMiner算法與文中提出的GFIM算法進行比較，驗證該算法的性能。

表1 三種數(shù)據(jù)集信息描述

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

為了評估兩種算法的性能，采用了兩個廣泛使用的評價標(biāo)準(zhǔn)，即相對誤差(RE)[16]和折扣累計增益(DCG)，定義如下：

(1)相對誤差(RE)：用來測量相對于頻繁項目實際頻率的估計頻率的誤差。具體來說，令V={v1,v2,…,vk}是前k個頻繁項目的集合。

(9)

(2)折扣累計增益(DCG)：DCG測量數(shù)據(jù)收集者計算的頻繁項目的質(zhì)量[17]。頻繁項目的頻率排名列表中的項目vi的相關(guān)性或增益是通過相關(guān)性計算公式得出的：

relvi=

log2[|d-|rankactual(vi)-rankestimated(vi)||]

(10)

可以直觀地發(fā)現(xiàn)，vi的估計頻率排名與真實頻率排名越接近，相關(guān)性就越大。給定一個真實的前k個頻繁項目V={v1,v2,…,vk}，估計頻率的排名的DCG計算為：

(11)

折扣因子log2(i)可以賦予較高排名的項目更高的權(quán)重。通過將估計的排名列表與理想的DCG(IDCG，與實際的頻繁項目排名完全一致)進行比較來進行歸一化。

(12)

很容易從公式得出，NDCG的結(jié)果是在0到1之間，能夠比較不同k值上計算的頻繁項目的質(zhì)量。

實驗分為兩個部分:(1)設(shè)定k=10，查看GFIM算法在不同的隱私預(yù)算下與LDPMiner算法的RE和NDCG性能對比。USCensus，Mushroom，Connect實驗結(jié)果按順序如圖1(a)、(b)、(c)和圖2的(a)、(b)、(c)所示。

(a)USCensus數(shù)據(jù)集

(c)Connect數(shù)據(jù)集

從圖1可以看出，隨著隱私預(yù)算ε的增大，相對誤差RE在三個數(shù)據(jù)集上都是呈總體下降趨勢，這符合差分隱私思想中隱私預(yù)算越大相對誤差越小的性質(zhì)。同時可以看出，隱私預(yù)算參數(shù)ε從0變化到10的過程中，改進后的GFIM算法在相對誤差上的性能優(yōu)于LDPMiner算法。

(a)USCensus數(shù)據(jù)集

(b)Mushroom數(shù)據(jù)集

(c)Connect數(shù)據(jù)集

從圖中可以看出，隨著隱私預(yù)算ε的增大，計算頻繁項目的質(zhì)量在三個數(shù)據(jù)集上都是呈總體上升的趨勢，這與NDCG標(biāo)準(zhǔn)定義的理論結(jié)果相符。同時，隱私預(yù)算參數(shù)ε從0變化到10的過程中，改進后的GFIM算法在頻繁結(jié)果質(zhì)量上優(yōu)于LDPMiner算法。

(2)設(shè)定隱私預(yù)算ε為固定值，觀察GFIM算法在不同k值下的RE和NDCG與LDPMiner算法的對比。USCensus，Mushroom，Connect實驗結(jié)果如圖3(a)、(b)、(c)和圖4(a)、(b)、(c)所示。

(a)USCensus數(shù)據(jù)集

(b)Mushroom數(shù)據(jù)集

(c)Connect數(shù)據(jù)集

圖3中，根據(jù)不同的數(shù)據(jù)集大小設(shè)置了不同的隱私預(yù)算值。其中Mushroom的隱私預(yù)算ε設(shè)置為3，Connect和USCensus數(shù)據(jù)集隱私預(yù)算ε設(shè)置為1。根據(jù)曲線圖可以看出，改進后的GFIM算法在相對誤差上的性能優(yōu)于LDPMiner算法。

從圖4中可以明顯看出，改進后的GFIM算法計算出的頻繁項目的質(zhì)量要高于LDPMiner算法計算出的頻繁項目的質(zhì)量。

(a)USCensus數(shù)據(jù)集

(b)Mushroom數(shù)據(jù)集

(c)Connect數(shù)據(jù)集

6 結(jié)束語

該文研究出一個既滿足本地化差分隱私又有較高可用性的GFIM算法。整個加噪和挖掘頻繁項目的過程劃分為兩個階段。在第一個階段，GFIM實現(xiàn)對整體用戶的隱私保護和頻繁項候選集的篩選；在第二個階段，GFIM把用戶劃分為隨機等大小的兩組用戶，把候選集發(fā)送給第一組用戶，讓用戶對自身的項集重新進行打包和加噪，挖掘候選集內(nèi)各項的頻率，再把結(jié)果當(dāng)成候選項集發(fā)送給第二組用戶。最后，GFIM綜合兩個階段得到最后頻繁項目和對應(yīng)頻率。為了驗證算法GFIM的可行性和對已有方案的改善，選取了LDPMiner算法進行對比，并在三個真實數(shù)據(jù)集進行多次實驗。結(jié)果表明，GFIM能夠較為準(zhǔn)確地挖掘出頻繁項目，并且在RE和NDCG這兩個指標(biāo)上的性能表現(xiàn)均優(yōu)于LDPMiner算法。同時，在實驗中發(fā)現(xiàn)，針對不同的數(shù)據(jù)集和不同的k值，kmax有對應(yīng)的最適合的大小。kmax的大小會對實驗結(jié)果有重要的影響，一個合適的kmax將極大地提高實驗結(jié)果的準(zhǔn)確性。另外，用戶的分組問題也是個可以討論的研究方向，文中方法是將用戶隨機等分成兩組，可以嘗試在用戶分組上面再進行研究，觀察是否能對頻繁項目挖掘的性能有進一步的提高。