基于本地化差分隱私的政務(wù)數(shù)據(jù)共享隱私保護(hù)算法研究*

郝玉蓉 樸春慧, 2 顏嘉麒 蔣學(xué)紅

(1. 石家莊鐵道大學(xué) 石家莊 050043；2.河北省電磁環(huán)境效應(yīng)與信息處理重點(diǎn)實(shí)驗(yàn)室 石家莊 050043；3.南京大學(xué) 南京 210023；4.河北省住房和城鄉(xiāng)建設(shè)廳 石家莊 050051)

智慧政府作為電子政務(wù)發(fā)展到一定程度后的高級(jí)階段[1-2]，是智慧城市理念對(duì)電子政務(wù)提出的更高要求。Z.Lv等[3]指出智慧政府作為智慧城市建設(shè)生態(tài)系統(tǒng)中重要組成部分，是政府利用信息通信技術(shù)實(shí)現(xiàn)各部門間數(shù)據(jù)互通、更為公開(kāi)的可持續(xù)發(fā)展的政府服務(wù)[4]。這一點(diǎn)可以從G.Perboli等[5]建立的智慧城市模型中加以驗(yàn)證。電子政務(wù)的發(fā)展使政府部門的政務(wù)系統(tǒng)數(shù)量不斷增加，積累了大量的部門業(yè)務(wù)數(shù)據(jù)[6]。數(shù)據(jù)共享成為推進(jìn)智慧政府建設(shè)必不可少的任務(wù)。但若在沒(méi)有適當(dāng)預(yù)防措施的情況下就共享政務(wù)數(shù)據(jù)，將很容易推斷出敏感信息，這一點(diǎn)可以從過(guò)去二十年中公開(kāi)的數(shù)據(jù)泄露事件中得到證明，這些事件包括馬薩諸塞州公共健康記錄的去匿名化、Netflix用戶的去匿名化以及參與全基因組協(xié)會(huì)研究的個(gè)人去匿名化[7]。

現(xiàn)有研究使用隱私保護(hù)技術(shù)對(duì)政務(wù)數(shù)據(jù)中可能存在的敏感信息[8]泄露進(jìn)行了研究。當(dāng)前的數(shù)據(jù)隱私保護(hù)技術(shù)大致可分為三類：基于匿名的隱私保護(hù)技術(shù)、基于加密的隱私保護(hù)技術(shù)和基于差分隱私的隱私保護(hù)技術(shù)?；谀涿碾[私保護(hù)技術(shù)根據(jù)隱私數(shù)據(jù)類型與應(yīng)用場(chǎng)景的差別，又可以進(jìn)一步劃分為關(guān)系型數(shù)據(jù)隱私保護(hù)、社交圖譜數(shù)據(jù)隱私保護(hù)以及位置與軌跡數(shù)據(jù)隱私保護(hù)。但基于匿名的方法通常缺乏嚴(yán)格的隱私安全保證，因此其更適用于小規(guī)模數(shù)據(jù)的隱私保護(hù)?；诩用艿姆椒m然具有更好的安全性保證，但其加密操作會(huì)帶來(lái)大量的計(jì)算開(kāi)銷，這使其難以應(yīng)用于資源受限的場(chǎng)景中。在過(guò)去的十幾年中，差分隱私(DP)[9]蓬勃發(fā)展。由于其嚴(yán)格的數(shù)學(xué)定義和組合的靈活性，成為了隱私保護(hù)的標(biāo)準(zhǔn)，被廣泛應(yīng)用于大數(shù)據(jù)收集的各個(gè)方面。例如，美國(guó)人口普查局對(duì)人口統(tǒng)計(jì)數(shù)據(jù)就采用了DP模型。傳統(tǒng)的DP模型被部署在了中央服務(wù)器上，但在實(shí)踐中，很難找到一個(gè)真正的可信第三方，這在一定程度上限制了傳統(tǒng)差分隱私的應(yīng)用。本地化差分隱私(LDP)[10-11]在DP的基礎(chǔ)上應(yīng)運(yùn)而生，其不僅可以抵御任意背景知識(shí)攻擊，還能夠抵御不可信第三方攻擊。目前，Google[12]、Apple[13]等公司已使用LDP模型用于收集用戶默認(rèn)瀏覽器主頁(yè)和搜索引擎設(shè)置的信息。但將LDP模型應(yīng)用于隱私保護(hù)政務(wù)數(shù)據(jù)共享中的研究工作還較少，這是由于這些前沿方法需要結(jié)合應(yīng)用場(chǎng)景和變化的需求進(jìn)行創(chuàng)新應(yīng)用。在政務(wù)數(shù)據(jù)共享場(chǎng)景中，LDP模型存在準(zhǔn)確性低、統(tǒng)計(jì)誤差大等缺點(diǎn)，在數(shù)據(jù)域大且數(shù)據(jù)量較少的情形中尤為顯著。

為了解決這些問(wèn)題，本文在LDP模型中采用數(shù)據(jù)分箱來(lái)降低統(tǒng)計(jì)誤差，并在不同分布下獲得較高的數(shù)據(jù)效用。本文的主要貢獻(xiàn)如下：

a.針對(duì)政府部門間共享統(tǒng)計(jì)數(shù)據(jù)的場(chǎng)景，提出了基于LDP的政務(wù)數(shù)據(jù)共享方法，其可在推行數(shù)據(jù)共享的基礎(chǔ)上為敏感信息提供可控制的隱私保護(hù)。

b.該方法解決了當(dāng)前隱私保護(hù)算法在數(shù)據(jù)域較大時(shí)對(duì)數(shù)據(jù)量大小要求嚴(yán)格的問(wèn)題，有效降低了數(shù)據(jù)的統(tǒng)計(jì)誤差，能在保護(hù)政務(wù)數(shù)據(jù)隱私的同時(shí)，提供可用的統(tǒng)計(jì)信息。

c.所提方法在不同的數(shù)據(jù)分布中均保持了較優(yōu)的數(shù)據(jù)效用性，能適應(yīng)于多種不同分布的隱私保護(hù)任務(wù)。

1 相關(guān)工作

在本地化差分隱私中，一個(gè)統(tǒng)計(jì)數(shù)據(jù)庫(kù)的查詢結(jié)果不會(huì)受到任何單一隱私數(shù)據(jù)的影響，它能在確保處理后統(tǒng)計(jì)信息可用的需求下保護(hù)個(gè)人信息不被泄露。因此可將LDP應(yīng)用于政府部門間共享統(tǒng)計(jì)數(shù)據(jù)的場(chǎng)景中，確保數(shù)據(jù)共享過(guò)程中敏感信息的安全。

下面通過(guò)一個(gè)簡(jiǎn)單示例說(shuō)明本地化差分隱私技術(shù)在統(tǒng)計(jì)數(shù)據(jù)共享應(yīng)用中的隱私保護(hù)作用。數(shù)據(jù)提供部門(如稅務(wù)部門)將高收入者(如年收入100萬(wàn)美元以上)按年齡分組，共享人數(shù)統(tǒng)計(jì)數(shù)據(jù)，如圖1所示。通常，個(gè)人收入狀況屬于敏感隱私數(shù)據(jù)。攻擊者的目的可能是確定某個(gè)特定的人(攻擊目標(biāo))——如u6是否為高收入者。攻擊者通過(guò)各種方式掌握了大量背景知識(shí)——如圖1所示統(tǒng)計(jì)數(shù)據(jù)以及表1中5位年齡為30歲的高收入者身份。若攻擊者還知道u6的年齡為30歲，則可以判定u6是一位年收入100萬(wàn)美元以上的高收入者，導(dǎo)致u6的收入狀況信息遭到泄露。而采用LDP技術(shù)，對(duì)圖1中各個(gè)年齡高收入者的統(tǒng)計(jì)數(shù)據(jù)(頻數(shù))做擾動(dòng)處理，30歲對(duì)應(yīng)的頻數(shù)值可能會(huì)從6變?yōu)?.5或變?yōu)?.2，攻擊者根據(jù)掌握的背景知識(shí)——擾動(dòng)后的統(tǒng)計(jì)數(shù)據(jù)、5位年齡為30歲的高收入者身份、u6的年齡為30歲，無(wú)法判定攻擊目標(biāo)u6是否為高收入者，從而避免了u6收入狀況隱私信息的泄露。

表1 部分背景知識(shí)

現(xiàn)有LDP的應(yīng)用研究主要基于隨機(jī)響應(yīng)機(jī)制，最早于1965年由Warner等人[14]提出。其主要思想是利用對(duì)敏感問(wèn)題響應(yīng)的不確定性實(shí)現(xiàn)對(duì)原始數(shù)據(jù)的隱私保護(hù)[15]，進(jìn)而研究對(duì)敏感屬性值的隱私化處理及其頻數(shù)、均值的統(tǒng)計(jì)校正處理和發(fā)布[16-17]。

1.1本地化差分隱私LDP提供了比中心化差分隱私更強(qiáng)的隱私保障，其正式定義如下：

定義1：本地化差分隱私(ε-LDP)[16]。假設(shè)x是一個(gè)私有信息，該私有信息從含k個(gè)元素的集合X中取值(令X= [k]:= {0,1,2,3,…,k-1},x∈X)。私有化機(jī)制Q是從[k]到輸出集Z的隨機(jī)映射，它以概率Q(z|x)將x∈X映射到z∈Z，映射后輸出的z被稱為私有化樣本。如果對(duì)于所有的x,x'∈X，當(dāng)ε>0時(shí)，有：

(1)

則認(rèn)為Q滿足ε-本地化差分隱私。由公式(1)可知，較小的隱私預(yù)算ε可以保證較高的隱私水平。且任意一對(duì)x,x'的映射輸出都是相似的，因此不能通過(guò)輸出結(jié)果推斷出特定的輸入。

(2)

2 問(wèn)題陳述

現(xiàn)有的本地化差分隱私算法(如代表性算法CMS、RAPPOR等)均是基于隨機(jī)響應(yīng)，其不確定性使得估計(jì)結(jié)果的準(zhǔn)確性不穩(wěn)定。在數(shù)據(jù)域較大且數(shù)據(jù)量較少的情況下，這種現(xiàn)象尤為顯著。為了更清楚的說(shuō)明這一問(wèn)題，本文生成了兩個(gè)含10萬(wàn)條記錄的仿真數(shù)據(jù)集進(jìn)行觀察，它們分別滿足Zipf分布和正態(tài)分布。在ε=2下，仿真數(shù)據(jù)集的頻數(shù)統(tǒng)計(jì)結(jié)果與經(jīng)過(guò)GRR處理后數(shù)據(jù)的頻數(shù)統(tǒng)計(jì)結(jié)果如圖2所示。

(a) Zipf分布

從圖2可得，在數(shù)據(jù)域較大且數(shù)據(jù)量較少的情況下(如已在圖3中放大的Zipf分布的右端以及正態(tài)分布的兩端)，處理后的頻數(shù)統(tǒng)計(jì)結(jié)果與原始頻數(shù)統(tǒng)計(jì)結(jié)果相差較大，易出現(xiàn)遠(yuǎn)離正常分布的異常數(shù)據(jù)值。它甚至可能將一個(gè)低頻屬性值所對(duì)應(yīng)的頻數(shù)值估計(jì)為負(fù)，這在一定程度上降低了數(shù)據(jù)的參考價(jià)值。故本文研究的目的是對(duì)隨機(jī)響應(yīng)機(jī)制的效用性進(jìn)行優(yōu)化，實(shí)現(xiàn)具有高數(shù)據(jù)效用性的LDP算法。

圖3 圖2部分位置對(duì)應(yīng)放大2倍的分布圖

針對(duì)上述不足，本文在GRR算法的基礎(chǔ)上引入數(shù)據(jù)分箱思想以解決當(dāng)前隱私保護(hù)算法在數(shù)據(jù)域較大時(shí)對(duì)數(shù)據(jù)量要求嚴(yán)格的問(wèn)題。這樣做的好處是，利用分箱思想可以將數(shù)據(jù)記錄分入更小的數(shù)據(jù)域范圍內(nèi)。當(dāng)聚合數(shù)據(jù)時(shí)，不同子域中的數(shù)據(jù)在各自域內(nèi)進(jìn)行聚合處理，可以防止本數(shù)據(jù)域中的數(shù)據(jù)被劃分到其他子域內(nèi)，一定程度上提高了數(shù)據(jù)聚合的可靠性。

3 基于本地化差分隱私的數(shù)據(jù)共享算法設(shè)計(jì)

常見(jiàn)的數(shù)據(jù)分箱有等寬分箱和等頻分箱。等寬分箱以敏感屬性值的域大小為前提，按相同區(qū)間寬度分箱，這時(shí)每個(gè)分箱內(nèi)數(shù)據(jù)量不定。等頻分箱則是把敏感屬性值按照從小到大的順序排列，根據(jù)記錄的個(gè)數(shù)將其等分為x部分，這時(shí)每個(gè)分箱內(nèi)數(shù)據(jù)量相同。但等頻分箱的效果容易受數(shù)據(jù)分布的影響，特別是當(dāng)大量數(shù)據(jù)記錄集中在少數(shù)幾個(gè)屬性值上，如Zipf分布、幾何分布以及正態(tài)分布等。因此，本文采用等寬分箱對(duì)數(shù)據(jù)記錄進(jìn)行劃分。為簡(jiǎn)化描述，將改進(jìn)后的算法記為BRR(Binning Randomized Response)。該算法是對(duì)GRR工作的改進(jìn)，且GRR可作為BRR在特定情況下特定參數(shù)選擇的方法。

完整的BRR算法在算法1中給出。第1行按照等寬分箱思想劃分了敏感屬性值的域區(qū)間，Zi為劃分后更小的域區(qū)間。算法在第2行中初始化了一個(gè)集合V，用來(lái)存放之后得到的擾動(dòng)數(shù)據(jù)。其中，Vi用來(lái)存放屬于域區(qū)間Zi的數(shù)據(jù)的擾動(dòng)報(bào)告。第3～7行由數(shù)據(jù)提供方執(zhí)行，依次對(duì)共享數(shù)據(jù)記錄中敏感屬性值d(i)進(jìn)行擾動(dòng)處理。第8～11行由數(shù)據(jù)需求方根據(jù)接收到的擾動(dòng)報(bào)告和相關(guān)參數(shù)校正并計(jì)算每個(gè)屬性值的頻數(shù)統(tǒng)計(jì)信息。當(dāng)參數(shù)fxs=1時(shí)，為GRR算法。

Algorithm 1Binning Randomized Response (BRR)

Input:d(1),d(2),d(3), …,d(n); privacy budgetε, number of binsfxs.

Output:Estimated FrequencyF(d)

1.bins←{Z1,Z2,Z3,Z4, …,Zfxs}

2.Initialize a setV←{V1,V2,V3,V4, …,Vfxs}

3.fori∈[n] do

4. forf∈[fxs] do

5. ifd(i)inZfdo

6.d'(i)←GRR_client(d(i);ε)

7Vf.append(d'(i))

8. forf∈[fxs] do

9. ford∈Zfdo

10. F(d)←GRR_server(d;ε,Vf)

回顧公式(2)可以發(fā)現(xiàn)，p接近0或1的值并不可取。這是因?yàn)闃O端情況下當(dāng)p= 1時(shí)，K= 1，此時(shí)敏感屬性僅有一種取值，即數(shù)據(jù)不翻轉(zhuǎn)的概率為1，共享數(shù)據(jù)將使敏感信息處于危險(xiǎn)之中；而當(dāng)p= 0時(shí)，數(shù)據(jù)翻轉(zhuǎn)概率最大，得到的擾動(dòng)數(shù)據(jù)越背離原始數(shù)據(jù)，雖然增大了保護(hù)強(qiáng)度，但卻違背了共享數(shù)據(jù)的初衷。算法1中Zi的作用類似公式(2)中提及的K，即敏感屬性在子域中可取值的種類數(shù)。BRR算法中，敏感屬性在子域中可取值的個(gè)數(shù)由敏感屬性列的數(shù)據(jù)域和分箱數(shù)fxs共同決定，要使敏感屬性在子域中的取值超過(guò)1種，應(yīng)保證分箱數(shù)取值不超過(guò)數(shù)據(jù)域的大小，從而保護(hù)共享數(shù)據(jù)的隱私。

為驗(yàn)證BRR算法的可行性，本文仍選用上文生成的滿足幾何分布和均勻分布的仿真數(shù)據(jù)集。圖4為原始數(shù)據(jù)的頻數(shù)統(tǒng)計(jì)結(jié)果與經(jīng)過(guò)BRR(fxs=8)算法處理后數(shù)據(jù)的頻數(shù)統(tǒng)計(jì)結(jié)果。不難發(fā)現(xiàn)，在相同隱私預(yù)算下，經(jīng)過(guò)BRR算法處理后的數(shù)據(jù)統(tǒng)計(jì)值與原始數(shù)據(jù)統(tǒng)計(jì)值相差較小，具有統(tǒng)計(jì)學(xué)意義，能在控制隱私泄露的條件下為政府部門制定決策提供輔助參考。

(a)Zipf分布

4 實(shí)驗(yàn)部分

4.1實(shí)驗(yàn)數(shù)據(jù)集本實(shí)驗(yàn)共采用三個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析：兩個(gè)仿真數(shù)據(jù)集和一個(gè)真實(shí)數(shù)據(jù)集。仿真數(shù)據(jù)集分別滿足Zipf分布和均勻分布，且每個(gè)數(shù)據(jù)集中包含100 000條數(shù)據(jù)，主要用于驗(yàn)證數(shù)據(jù)域大小對(duì)統(tǒng)計(jì)數(shù)據(jù)誤差的影響。真實(shí)數(shù)據(jù)集則選取了Kaggle提供的菲利賓家庭收入支出數(shù)據(jù)集(Family Income and Expenditure)。設(shè)年收入大于20萬(wàn)比索的家庭屬于高收入家庭，以此為條件，共篩選出16685條數(shù)據(jù)用于后續(xù)分析。由于該數(shù)據(jù)集中含有多個(gè)屬性字段，因此數(shù)據(jù)提供部門可以以地區(qū)、年齡、婚姻狀態(tài)等各種維度對(duì)高收入家庭的統(tǒng)計(jì)分析數(shù)據(jù)進(jìn)行共享。本文以年齡維度為例，通過(guò)對(duì)各個(gè)年齡的高收入家庭頻數(shù)數(shù)據(jù)進(jìn)行隱私保護(hù)處理，證明本文提出的BCS算法的特性和優(yōu)勢(shì)。

4.2實(shí)驗(yàn)指標(biāo)隱私保護(hù)后數(shù)據(jù)的效用性通常由原始數(shù)據(jù)集與隱私處理后數(shù)據(jù)集的差異程度來(lái)評(píng)估。常用的誤差度量標(biāo)準(zhǔn)有：相對(duì)誤差、絕對(duì)誤差、平均絕對(duì)百分比誤差以及歐式距離等。本文采用平均絕對(duì)百分比誤差(MAPE)作為評(píng)價(jià)BRR算法數(shù)據(jù)效用性的指標(biāo)。MAPE[19-20]的定義如下：

(3)

其中|D|為敏感屬性列的類別域大小，yi為第i個(gè)屬性值的真實(shí)頻數(shù)，xi為第i個(gè)屬性值的估計(jì)頻數(shù)。MAPE的值越小，估計(jì)分布越接近真實(shí)分布，說(shuō)明數(shù)據(jù)的效用越好。

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

a.頻數(shù)估計(jì)。為了清楚顯示頻數(shù)分布趨勢(shì)并便于觀察，本文計(jì)算了每個(gè)年齡屬性值下對(duì)應(yīng)高收入家庭的估計(jì)頻數(shù)。根據(jù)所選數(shù)據(jù)分別繪制了三種類型的分布直方圖，如圖5所示。其中圖(a)為原始數(shù)據(jù)的頻數(shù)直方圖、圖(b)為隱私預(yù)算參數(shù)ε=2時(shí)由GRR算法處理后得到的頻數(shù)直方圖、圖(c)為ε=2，fxs=16時(shí)由BRR處理后得到的頻數(shù)直方圖。

圖5 高收入家庭年齡分布直方圖

觀察圖5直方圖可以發(fā)現(xiàn)，隱私保護(hù)后的數(shù)據(jù)雖然改變了記錄的具體值，但是從數(shù)據(jù)總體分布趨勢(shì)而言，較好的保留了原始數(shù)據(jù)的分布性質(zhì)，仍存在著較強(qiáng)的參考價(jià)值。同GRR算法相比，BRR算法處理后的數(shù)據(jù)的估計(jì)頻數(shù)更接近真實(shí)值，在數(shù)據(jù)量稀疏的兩端尤為顯著。

b.誤差估計(jì)。以GRR為對(duì)照組，本文分別在ε=2和fxs=16的參數(shù)設(shè)置下計(jì)算了隱私保護(hù)處理后每個(gè)年齡對(duì)應(yīng)的高收入家庭戶數(shù)統(tǒng)計(jì)量的MAPE值，以觀察誤差分布趨勢(shì)，如圖6所示。當(dāng)戶主年齡分別為15、17、89、96、98時(shí)，由GRR算法隱私保護(hù)后的數(shù)據(jù)對(duì)應(yīng)的統(tǒng)計(jì)值誤差最大。而這些戶主年齡對(duì)應(yīng)的戶數(shù)分別為2、4、5、3、4，均屬于數(shù)據(jù)量過(guò)少的情況。相較于GRR算法，BRR算法在數(shù)據(jù)量較少時(shí)對(duì)應(yīng)的統(tǒng)計(jì)誤差則小很多，其總體趨勢(shì)也更平穩(wěn)。

圖6 隱私處理后各年齡統(tǒng)計(jì)量的MAPE

c.分箱數(shù)對(duì)統(tǒng)計(jì)數(shù)據(jù)誤差的影響。圖7提供了不同分箱數(shù)下每個(gè)戶主年齡對(duì)應(yīng)的高收入家庭戶數(shù)統(tǒng)計(jì)量的MAPE值，用于驗(yàn)證分箱數(shù)對(duì)統(tǒng)計(jì)數(shù)據(jù)誤差的影響。其中隱私預(yù)算參數(shù)ε=2，可得分箱數(shù)越大，MAPE值越低。這是由于分箱可以在一定程度上限制隨機(jī)響應(yīng)機(jī)制帶來(lái)的偏差，保證某一低頻數(shù)的年齡值被隱私保護(hù)處理后仍處于距離該原始年齡值較近的位置。上文在第3節(jié)提到，分箱數(shù)取值不應(yīng)超過(guò)數(shù)據(jù)域大小，否則會(huì)使敏感屬性在子類別域Zi中可取值的個(gè)數(shù)接近于1，即數(shù)據(jù)不翻轉(zhuǎn)概率接近1。例如圖7中，當(dāng)1≤Zi≤1.5時(shí)，分箱數(shù)的取值為56≤fxs≤84，此時(shí)對(duì)應(yīng)的誤差值逐漸接近于0。若直接共享這樣的數(shù)據(jù)，將使敏感信息處于危險(xiǎn)之中，這是不可取的。

圖7 分箱數(shù)對(duì)誤差的影響

d.數(shù)據(jù)規(guī)模對(duì)統(tǒng)計(jì)數(shù)據(jù)誤差的影響。為了解BRR在不同規(guī)模數(shù)據(jù)上的效用性，本文對(duì)上面篩選的菲律賓高收入家庭原始數(shù)據(jù)集(16 685條數(shù)據(jù))進(jìn)行了翻倍處理，分別生成4倍(66 740條數(shù)據(jù))、8倍、12倍、16倍、20倍(333 700條數(shù)據(jù))的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。觀察在ε=2和fxs=16參數(shù)設(shè)置下，BRR算法統(tǒng)計(jì)量誤差值隨數(shù)據(jù)規(guī)模的變化情況。

圖8 數(shù)據(jù)規(guī)模對(duì)統(tǒng)計(jì)數(shù)據(jù)誤差的影響

由圖8可得，隨著數(shù)據(jù)規(guī)模的增加，經(jīng)過(guò)GRR和BRR隱私保護(hù)處理后的數(shù)據(jù)統(tǒng)計(jì)量整體誤差逐漸降低。相較于GRR，BRR在不同數(shù)據(jù)規(guī)模下均保持了更好的數(shù)據(jù)效用性，且數(shù)據(jù)規(guī)模較小時(shí)，BRR的優(yōu)勢(shì)更為明顯。當(dāng)數(shù)據(jù)量達(dá)到一定規(guī)模時(shí)，BRR統(tǒng)計(jì)量的整體誤差在小范圍內(nèi)浮動(dòng)。此實(shí)驗(yàn)結(jié)果也驗(yàn)證了Ye Q.Q.等在文獻(xiàn)[15]中指出的“用于統(tǒng)計(jì)的數(shù)據(jù)量大小決定了數(shù)據(jù)效用性高低”這一說(shuō)法?！?/p>

e.隱私預(yù)算對(duì)統(tǒng)計(jì)數(shù)據(jù)誤差的影響。圖9為隱私預(yù)算在不同取值下(0～5)對(duì)BRR數(shù)據(jù)效用性的影響。同上，以GRR為對(duì)照組，選擇參數(shù)fxs=8。從圖9不難發(fā)現(xiàn)，隨著隱私預(yù)算的增加，這兩種算法的誤差值均越小。即當(dāng)隱私預(yù)算增加時(shí)數(shù)據(jù)不翻轉(zhuǎn)的概率增大，得到的擾動(dòng)數(shù)據(jù)越接近原始數(shù)據(jù)，但相應(yīng)地其保護(hù)強(qiáng)度也將減小，這與預(yù)期是一致的。其次，在相同隱私預(yù)算下，BRR算法的誤差值更小，尤其當(dāng)ε<3.5時(shí)，BRR算法的數(shù)據(jù)效用性顯著優(yōu)于GRR。如圖10所示，本文還在相同參數(shù)設(shè)置下分別對(duì)比了fxs=4，fxs=8，fxs=16時(shí)相應(yīng)的MAPE值。容易發(fā)現(xiàn)，在相同隱私預(yù)算下，分箱數(shù)fxs越大，統(tǒng)計(jì)數(shù)據(jù)誤差MAPE的值越小。

圖9 隱私預(yù)算對(duì)統(tǒng)計(jì)數(shù)據(jù)誤差的影響

圖10 相同隱私預(yù)算下分箱數(shù)量對(duì)統(tǒng)計(jì)數(shù)據(jù)誤差的影響

f.數(shù)據(jù)域大小對(duì)統(tǒng)計(jì)數(shù)據(jù)誤差的影響。如圖11所示，我們?cè)诓煌臄?shù)據(jù)域大小下生成了滿足Zipf分布和均勻分布的數(shù)據(jù)集，其中參數(shù)設(shè)置為ε=2和fxs=8。當(dāng)數(shù)據(jù)量一定時(shí)，BRR和GRR算法在Zipf分布和均勻分布下的誤差均隨數(shù)據(jù)域大小的增大而增大。且相同條件下，BRR算法的效用性顯著優(yōu)于GRR算法。此誤差曲線也較好反映了本文所說(shuō)的“當(dāng)數(shù)據(jù)量較少而數(shù)據(jù)域|D|較大時(shí)，統(tǒng)計(jì)誤差較大”這一問(wèn)題。

4.4算法特性分析我們從以下兩個(gè)方面分析BRR算法特性：

a.較好的數(shù)據(jù)效用性。從頻數(shù)直方圖的誤差角度看，GRR算法的誤差值主要源于敏感屬性取值稀疏的部分。本文提出基于數(shù)據(jù)分箱的隱私保護(hù)算法BRR，通過(guò)將數(shù)據(jù)分入更小的數(shù)據(jù)域，得到更小的誤差量。從數(shù)據(jù)規(guī)模、隱私預(yù)算、數(shù)據(jù)域大小等方面進(jìn)行討論分析，表明BRR具有更好的數(shù)據(jù)效用性。

b.略高的時(shí)間復(fù)雜度。使用BRR算法所需的時(shí)間復(fù)雜度與GRR算法O(n+k)相比較，僅多出了數(shù)據(jù)分箱的時(shí)間。但由于政府共享的個(gè)人統(tǒng)計(jì)數(shù)據(jù)通常不會(huì)涉及很大的數(shù)量級(jí)，略高的時(shí)間復(fù)雜度不會(huì)成為本算法在政府領(lǐng)域?qū)嶋H應(yīng)用的制約因素。

(a)Zipf分布

5 結(jié) 語(yǔ)

為幫助智慧政府利用數(shù)據(jù)做出更準(zhǔn)確更客觀的決策，數(shù)據(jù)共享是其建設(shè)進(jìn)程中必不可少的任務(wù)。由于政務(wù)數(shù)據(jù)中含有大量個(gè)人敏感信息，直接共享這些數(shù)據(jù)或是對(duì)已共享的數(shù)據(jù)進(jìn)行分析都有可能造成隱私信息的泄露。因此，本文就政府在推行政務(wù)數(shù)據(jù)共享的同時(shí)如何保護(hù)個(gè)人隱私信息不泄露進(jìn)行了研究。首先，本文針對(duì)政府部門間共享統(tǒng)計(jì)數(shù)據(jù)場(chǎng)景，討論了現(xiàn)有隱私保護(hù)技術(shù)存在的不足，并在GRR算法的基礎(chǔ)上提出了基于本地化差分隱私的政務(wù)數(shù)據(jù)共享算法BRR。通過(guò)與算法GRR進(jìn)行比較，驗(yàn)證了所提算法具有較高的效用性，可在不同分布和數(shù)據(jù)域大小下保持其效用性。本算法可用于民意調(diào)查、電子投票等傾向于政務(wù)統(tǒng)計(jì)數(shù)據(jù)共享的情景，目的是為政府部門管理或服務(wù)決策提供輔助參考依據(jù)。但本文提出的算法目前僅適用于單值敏感屬性的情況，下一步工作將考慮如何在多值敏感屬性的情況下保證數(shù)據(jù)的敏感性與效用性問(wèn)題，完成智慧政務(wù)中共享數(shù)據(jù)的隱私保護(hù)。