基于本地化差分隱私保護(hù)的頻繁項(xiàng)目挖掘算法

朱美琪，楊 庚，白云璐

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

0 引 言

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

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

主要貢獻(xiàn)如下：

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

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

1 相關(guān)工作

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

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

2 理論基礎(chǔ)

2.1 本地化差分隱私

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

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

Pr(A(R)∈S)

(1)

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

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

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

2.2 頻繁項(xiàng)目挖掘

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

2.3 LDP解決方案

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

2.3.2 RAPPOR算法

2.3.3 Succinct Histogram算法

3 GFIM算法

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

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頻繁項(xiàng)目。

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

2.計(jì)算真實(shí)的top-k頻繁項(xiàng)集;

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

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

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

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

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

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

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

Input：項(xiàng)的取值集合大小d；

Output:正交矩陣φ。

1.計(jì)算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.從項(xiàng)集Si中隨機(jī)選取一個(gè)項(xiàng)i；

3.ifii=⊥ then

5. else

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

8.end if

9.returnzi

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

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

(2)

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

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

Output：干擾后的向量zi。

1.求交集Ti=Si∩C；

2.if |Ti|

3. 往Ti中加入若干個(gè)冗余項(xiàng)得到新的用戶項(xiàng)集|Ni|=kmax；

4.end if

5.從項(xiàng)集Ni中隨機(jī)選取一個(gè)項(xiàng)ii；

7.ifii=⊥ then

9. else

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

12.end if

13.returnzi

4 GFIM算法隱私保護(hù)性能分析

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

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

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

證明：

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

(3)

(4)

進(jìn)而有：

(5)

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

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

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

(6)

因?yàn)樾藜暨^程是確定的，所以有：

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

(7)

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

(8)

由上述可知第一組用戶對(duì)數(shù)據(jù)的處理算法滿足ε2-本地化差分隱私。因?yàn)榈诙M用戶對(duì)數(shù)據(jù)的處理與第一組原理相同，所以第二組對(duì)數(shù)據(jù)的處理也滿足ε2-本地化差分隱私。又因?yàn)椋@兩組數(shù)據(jù)不相交，根據(jù)差分隱私的并行組合原理可知，整個(gè)階段二滿足ε2-本地化差分隱私。

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

5 實(shí) 驗(yàn)

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

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

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

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

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

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

(9)

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

relvi=

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

(10)

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

(11)

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

(12)

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

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

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

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

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

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

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

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

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

(2)設(shè)定隱私預(yù)算ε為固定值，觀察GFIM算法在不同k值下的RE和NDCG與LDPMiner算法的對(duì)比。USCensus，Mushroom，Connect實(shí)驗(yàn)結(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ù)曲線圖可以看出，改進(jìn)后的GFIM算法在相對(duì)誤差上的性能優(yōu)于LDPMiner算法。

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

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

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

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

6 結(jié)束語

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