基于直方圖的隱私鍵-值數(shù)據(jù)收集算法

張嘯劍 徐雅鑫 付 楠 孟小峰

1(河南財經(jīng)政法大學計算機與信息工程學院 鄭州 450002) 2(中國人民大學信息學院 北京 100872)

(xjzhang82@ruc.edu.cn)

移動互聯(lián)網(wǎng)環(huán)境下的新興技術快速發(fā)展與應用，使得鍵-值(key-value)數(shù)據(jù)的獲取與收集變得尤為容易，例如網(wǎng)購、健康醫(yī)療、金融等數(shù)據(jù)的收集與分析.鍵-值數(shù)據(jù)收集與分析能夠提升產(chǎn)品服務與設備服務的質(zhì)量，以及向用戶提供個性化的體驗.然而，鍵-值數(shù)據(jù)通常蘊含著豐富的個人敏感信息，在提供給收集者或者第三方應用的同時，個人的敏感信息有可能被泄露.表1為某不可信購物網(wǎng)站收集用戶購買與評分的記錄.通過表1中鍵的頻率以及鍵所對應值的均值分析，可以學習出用戶的購物行為模式與偏好.例如，商品k2的頻率為2，k2所對應值的均值為0.61.不可信收集者分析出k2的頻率之后，即可對表1中的用戶進行統(tǒng)計攻擊.因此，在此情景下，用戶無法控制自己的隱私數(shù)據(jù).本地差分隱私保護技術的出現(xiàn)有效地解決了此類矛盾.該技術允許每個用戶擾動自身數(shù)據(jù)之后再響應收集者的需求.

目前基于本地差分隱私的鍵-值收集算法包括PrivKV[1],KVUE[2],KVOH[2],PCKV-GRR[3],LDPKV[4].PrivKV,KVUE,KVOH,LDPKV算法基于鍵的整個值域進行編碼，利用簡單隨機抽樣技術減少收集者與用戶之間的通信代價.然而，這4種算法均沒有考慮到鍵的值域稀疏性與偏斜性問題.例如，假設表1中商品的值域為7.以u3為例，對其鍵編碼之后可以獲得長度為7的向量(〈1,0.6〉,〈0,0〉,〈0,0〉,〈0,0〉,〈0,0〉,〈0,0〉,〈0,0〉).基于該向量進行隨機抽樣時，〈0,0〉以67的概率被抽取到，而〈0,0〉對最終統(tǒng)計結(jié)果無效.當鍵的值域非常大且稀疏時，PrivKV,KVUE,KVOH,LDPKV算法估計誤差比較高.

為了解決PrivKV,KVUE,KVOH,LDPKV算法無法應對鍵的值域稀疏性問題，PCKV-GRR利用填充-抽樣[5]技術減少稀疏性帶來的影響.其主要思想是利用給定長度截斷每個用戶所擁有的鍵-值對集合，然后利用啞元填充那些小于的鍵-值對集合.例如，表1中用戶u2利用=3截斷所擁有的鍵-值對集合后，該集合變成{〈k2,0.42〉,〈k4,0.6〉,}，其中為啞元.然而，該算法存在3點不足：

1) 與PrivKV類似，把隱私預算ε分割成ε1與ε2，其中ε1用來本地擾動鍵，而ε2用來擾動每個鍵所對應的值；

2) 在設定本地擾動概率時，沒有考慮真實鍵對最終估計的影響，無論鍵擾動自身還是其他值均設定相同的擾動概率；

若用戶直接發(fā)送所擁有的鍵-值對長度,則會導致隱私泄露.此外，如何選擇合理的至關重要，直接影響最終鍵頻率與均值的估計精度.例如，以真實稀疏數(shù)據(jù)TalkingData為例，該數(shù)據(jù)集中非零鍵-值對所占的比例僅為6.9%.根據(jù)該數(shù)據(jù)中60 032個用戶的鍵-值對長度分布(如圖1所示)可知，98%的用戶的鍵-值對長度小于50.因此，的理想選擇區(qū)間為[0,50].

Fig. 1 Length distribution of TalkingData key-value pair圖1 TalkingData鍵-值對長度分布

結(jié)合文獻[1-4]可知，收集與分析鍵-值數(shù)據(jù)過程中存在的挑戰(zhàn)包括：1)用戶在設計本地擾動算法時，如何設置真實鍵的擾動概率以及維持鍵與值之間的關聯(lián)性；2)由于鍵-值數(shù)據(jù)的值域通常很大且稀疏，如何設計有效的最優(yōu)截斷長度；3)收集者如何以較小的通信代價收集所有用戶的鍵-值數(shù)據(jù).總而言之，目前還沒有一個行之有效且滿足本地差分隱私的鍵-值收集與分析算法能夠克服上述算法存在的問題.為此，本文基于本地差分隱私技術提出了一種鍵-值數(shù)據(jù)收集算法能夠兼顧3方面挑戰(zhàn)需求.

本文主要貢獻有3個方面：

1) 為了解決挑戰(zhàn)1，提出一種基于直方圖技術的鍵-值頻率與均值估計算法HISKV.不同于PrivKV,KVOH,LDPKV,PCKV-GRR算法，HISKV算法在不分割隱私預算的情況下，利用直方圖技術對鍵-值對進行整體擾動，進而維持了鍵-值之間的關聯(lián)性.同時，對于真實的鍵分配較大的本地擾動概率.

2) 為了有效解決挑戰(zhàn)2與挑戰(zhàn)3，提出了一種最優(yōu)截斷算法來尋找截斷長度.不同于PCKV-GRR算法中的經(jīng)驗設置，HISKV利用用戶分組策略與部分隱私預算估計.結(jié)合利用填充-抽樣技術處理鍵值域的稀疏性問題.

3) 理論分析了HISKV算法滿足ε-本地差分隱私，以及頻率與均值估計的無偏性、誤差邊界以及最大偏差.通過合成數(shù)據(jù)與真實數(shù)據(jù)實驗分析，HISKV算法具有較高的可用性.

1 相關工作

本地化差分隱私技術在假設收集者完全不可信的情況下，允許每個用戶利用隨機響應機制[6]本地擾動自己的數(shù)據(jù)，并把噪音結(jié)果發(fā)送給收集者.目前本地化差分隱私研究主要集中于頻率估計[7-11]與均值估計[12-15].GRR[7]算法通過直接編碼將整個類別屬性的值域進行轉(zhuǎn)換，然后對原始值進行本地擾動，而該算法的通信代價與誤差均較高.類似于GRR算法，RAPPOR[8]算法結(jié)合一元編碼與布隆過濾技術把類別屬性的整個值域散列到較小的值域中，結(jié)合散列值域統(tǒng)計每個類別屬性的頻率.該算法能夠永久性或者及時性地保護每個用戶的數(shù)據(jù)，相應的通信代價較低.基于RAPPOR算法，O-RR[9]算法借助散列編碼與分組操作估計整個類別屬性的概率分布情況.無論是GRR，RAPPOR及其變種算法，它們的誤差均隨著值域的增加而增加.OLH[7]算法克服了對值域大小的依賴，該算法利用優(yōu)化本地散列技術將整個值域Hash到較小地址空間.為了進一步減少通信代價，在較高計算代價的基礎上，SHist[10]算法采用隨機矩陣投影技術對類別屬性值域進行編碼，隨機擾動1個比特位發(fā)送給收集者.此外，LDPMiner[11]算法基于SHist算法研究了集-值數(shù)據(jù)下的Heavy Hitter問題.不同于上述基于類別屬性的頻率估計算法，文獻[12-15]集中研究[-1,1]中數(shù)值均值的估計.Duchi[12-13]算法基于離散化操作，對數(shù)值型屬性的均值進行估計，并取得較小的通信代價與較低的估計誤差.基于Duchi算法，Harmony[14]算法在多維數(shù)值元組中隨機抽取單個數(shù)值并擾動成離散值，然而該算法的估計結(jié)果遠離了區(qū)間[-1,1]中的真實值.PM[15]算法能夠?qū)-1,1]中的真實值擾動到一個連續(xù)的區(qū)間，并在該連續(xù)區(qū)間中計算出該擾動值的左右邊界.在隱私預算較大時，PM算法的估計精度明顯高于Duchi與Harmony算法.

盡管文獻[7-15]對類別屬性與數(shù)值屬性上的頻率與均值進行了較為系統(tǒng)的研究，然而這些算法很難直接應用于鍵-值數(shù)據(jù)，其主要原因在于這些算法沒有考慮鍵-值對之間的關聯(lián)性.文獻[1-4]對鍵-值數(shù)據(jù)上的頻率與均值估計進行了研究.基于RAPPOR與Harmony算法，PrivKV[1]算法對鍵-值數(shù)據(jù)的頻率與均值進行了估計，PrivKV與Harmony的主要區(qū)別在于PrivKV把擾動后的數(shù)值修正操作放到了收集者端.然而，PrivKV算法由于分割隱私預算導致估計精度較低.KVOH[2]與LDPKV[4]算法結(jié)合鍵-值數(shù)據(jù)值域與擾動輸出值域之間的整體映射關系，利用GRR算法對離散化后的鍵-值對進行擾動.然而，這2種算法的誤差易受到值域大小的影響.不同于PrivKV,KVOH,LDPKV 3種算法，PCKV-GRR[3]算法利用填充-抽樣操作對原始鍵-值序列進行截斷與抽樣，然后再利用GRR算法進行本地擾動.盡管PCKV-GRR在值域較大且稀疏的情況下優(yōu)于KVOH與PrivKV，但是該算法的誤差同樣受到值域大小的影響，并且沒有顧及到如何設置有效鍵的擾動概率以及截斷長度的計算方法.基于上述分析，本文提出一種基于本地差分隱私的鍵-值收集與分析算法HISKV，該算法利用直方圖技術統(tǒng)一估計鍵的頻率及其均值，利用最優(yōu)截斷長度與填充-抽樣技術處理值域稀疏問題.

2 定義與問題

2.1 本地差分隱私

不同于中心化差分隱私保護技術，本地差分隱私技術通常要求用戶在本地保護自己的數(shù)據(jù)，把擾動之后的數(shù)據(jù)報告給不可信的收集者，從而實現(xiàn)隱私不被泄露.本地差分隱私的形式化定義為：

定義1.ε-本地差分隱私.給定一個隨機算法A及其定義域Dom(A)和值域Range(A)，若算法A在任意2條不同元組t與t′(t,t′∈Dom(A))上得到相同輸出結(jié)果o(o∈Range(A))滿足不等式：

Pr[A(t)=o]≤eε×Pr[A(t′)=o]，

(1)

則A滿足ε-本地差分隱私.其中ε為隱私預算，其值越小則算法A的隱私保護程度越高.

2.2 隨機應答機制

隨機應答機制[6]是實現(xiàn)本地差分隱私的常用技術.在用戶發(fā)送數(shù)據(jù)ti之前，對其進行隨機擾動.該機制的原始思想是用戶在響應敏感的布爾問題時，以概率p真實應答，以q的概率給出相反的應答.為了使隨機應答機制滿足ε-本地差分隱私，通常設置p=eε(1+eε),q=1(1+eε).目前，基于隨機應答機制出現(xiàn)了以GRR為代表的本地擾動算法.給定ki,kj∈{1,2,…,d}，GRR算法：

(2)

2.3 問題描述

類似文獻[4]，給定n個用戶U={u1,u2,…,un}和一個收集者，每個用戶擁有鍵-值對集合.K={k1,k2,…,kd}為鍵的值域，d為該值域大小，V=[-1,1]為鍵所對應值的值域.Si={〈kj,vj〉|1≤j≤li,kj∈K,vj∈V}為用戶ui所擁有的鍵-值對集合，其中l(wèi)i表示Si的長度.收集者收集所有用戶的鍵-值數(shù)據(jù)后，通常估計鍵所對應的頻率以及值所對應的均值，具體計算為

(3)

(4)

采用均方誤差與相對誤差度量fk與μk的估計精度.本文要解決的問題是在設計滿足本地差分隱私的頻率與均值估計算法的同時，要盡可能獲得誤差較小的估計結(jié)果.

3 基于直方圖技術的鍵-值數(shù)據(jù)收集算法

3.1 HISKV算法

不同于文獻[1-4]中的收集算法，HISKV算法不需要對每個用戶的鍵按照值域進行編碼，而是僅對鍵所對應值進行離散化處理.給定某個鍵-值對〈k,v〉，只對值v進行離散化操作，結(jié)果為

(5)

例如，設〈漢堡,0.4〉為某一個鍵-值對，則0.4以0.7的概率離散化+1；以0.3的概率離散化為-1.

根據(jù)式(5)可知，每個用戶所擁有鍵的對應值均被離散化成2個類別，分別為+1或者-1，而所有的鍵還保持原來的值.因此，可以在{d,+1}與{d,-1}這2個二維值域內(nèi)構建相應的直方圖來估計鍵的頻率以及所對應值的均值，其中每個鍵即是直方圖的桶.結(jié)合桶的頻率可以估計每個鍵的頻率及所對應值的均值.如表1所示，用戶u1，u2，u3的鍵-值對經(jīng)過離散化之后的值為{〈k1,+1〉,〈k2,+1〉,〈k3,-1〉,〈k4,-1〉,〈k5,+1〉},{〈k2,-1〉,〈k4,+1〉},{〈k5,+1〉}.根據(jù)d={k1,k2,k3,k4,k5,k6,k7}以及d所對應的值{+1,-1}可獲得相應直方圖(如圖2所示).根據(jù)圖2可以估計出d中每個鍵的頻率及均值.例如，鍵k2的頻率為23，k2所對應值的均值為1.

Fig. 2 Two-dimensional range histogram圖2 二維值域直方圖

結(jié)合直方圖技術的HISKV算法如算法1所示：

算法1.HISKV算法.

輸入：n個用戶、每個用戶所擁有的鍵-值對集合S={S1,S2,…,Sn}、隱私預算ε、鍵的值域d；

輸出：頻率向量f*、均值向量μ*.

①f*←?,μ*←?；

② 收集者將n個用戶分成2組βn,(1-β)n；

④ for 在[(1-β)n]內(nèi)的每個用戶ui執(zhí)行步驟⑤～⑥;*每個用戶擾動*

LRR_KV(Si,ε,)；

⑦ end for

⑨ ifkj∈[1,2(d+)] then

HISKV算法是基于本地差分隱私解決鍵的頻率以及所對應值的估計問題.首先收集者從n個用戶中抽取βn個用戶(β為抽取概率)(步驟②).基于βn個用戶利用OETL算法估計最優(yōu)截斷長度(步驟③).每個用戶結(jié)合截斷長度對自身所擁有的鍵值對集合進行截斷或者填充.然后再均勻隨機抽樣一個鍵-值對本地擾動，并把擾動結(jié)果報告給收集者(步驟④～⑦).收集者聚集所有用戶的報告值后，估計每個鍵的頻率以及值所對應的均值(步驟⑧～).由LRR_KV算法中的抽樣可知，每個用戶僅擾動一組鍵-值對報告給收集者，進而使得收集者與用戶之間的通信代價為O(1).接下來闡述LRR_KV與OETL算法，其中LRR_KV算法具體細節(jié)如算法2所示：

算法2.LRR_KV算法.

輸入：(1-β)n用戶中任意ui的鍵-值集合Si、隱私預算ε、截斷長度；

① 〈kj,vj〉←Padding-Sampling(Si,)；

②〈kj,±1〉←Discretizing(〈kj,vj〉)；

③ if thej-th pair 〈kj,vj〉 is 〈kj,1〉 then

⑤ else if thej-th pair 〈kj,vj〉 is 〈kj,-1〉 then

⑦ end if

結(jié)合LRR_KV算法，用戶ui首先利用算法3步驟①對集合Si進行填充-抽樣操作，進而獲得〈kj,vj〉.結(jié)合〈kj,vj〉，用戶ui利用式(5)對值vj進行離散化操作(步驟②).然后結(jié)合離散化結(jié)果〈kj,±1〉進行本地擾動(步驟②～⑦).結(jié)合用戶ui的鍵-值對集合Si，LRR_KV算法的具體實現(xiàn)思路如圖3所示：

Fig. 3 LRR KV local disturbance圖3 LRR_KV本地擾動示意圖

根據(jù)圖3可知，用戶ui所抽取的鍵-值對〈kj,vj〉經(jīng)過離散化后變成〈kj,1〉或者〈kj,-1〉.以概率p1,q1,q2分別將〈kj,1〉與〈kj,-1〉擾動成4種不同的情況.其中一種情況是〈kj,1〉與〈kj,-1〉以概率p1擾動成自身.由式(2)可知，p1=eε(eε+d′-1)，其中，d′=2(d+).如何設置剩余3種的擾動概率是一個大的挑戰(zhàn).文獻[3]中PCKV-GRR算法在相應參數(shù)取得最優(yōu)時，剩余3種概率均取值為1(eε+d′-1).然而，該算法卻忽略一種事實，即不論〈kj,1〉以概率q1擾動成〈kj,-1〉或者〈kj,-1〉以概率q1擾動成〈kj,1〉，鍵kj并沒有被擾動成值域d′中的其他值.此種情況對鍵kj的頻率及其所對應值的均值估計均有效.因此，概率q1的值不應該取平均值，應該傾向性地取較大的值.由定義1可知下式成立：

影響LRR_KV算法本地擾動效果包括2個因素：Padding-Sampling算法的設計以及如何獲得最優(yōu)截斷長度.接下來結(jié)合文獻[5]設計填充-抽樣算法.

算法3.Padding-Sampling算法.

輸入：Si、截斷長度；

輸出：所抽取的鍵-值對(kj,vj).

① ifli>then*li表示Si的長度*

②ui不放回地從Si,隨機采樣個鍵值對，得到抽取個鍵-值對*

③ else ifli

④ui用-li個從{〈1,0〉,〈2,0〉,…,〈l,0〉}集合采樣的啞元填充Si,得到

⑥ end if

⑦ return 〈kj,vj〉.

用戶ui利用Si的長度li與截斷長度比較.如果li>，則從Si中無放回地抽取個鍵-值對形成(步驟①②);否則，從啞元鍵-值對集合{〈1,0〉,〈2,0〉,…,〈l,0〉}中隨機抽取-li個鍵-值對填充Si，并獲得(步驟③④).結(jié)合用戶以概率1抽取一個鍵-值對〈kj,vj〉.

算法4.OETL算法.

輸入：n、β、ε、鍵的值域d；

① for 在[βn]的每個用戶ui執(zhí)行步驟②～③;*每個用戶擾動*

④ end for

⑧ end for

βn中的每個用戶利用GRR算法本地擾動自己鍵-值對長度li，步驟①～④發(fā)送給收集者；步驟⑤～⑧收集者計算并修正每個長度的計數(shù);步驟⑨利用第90個百分位數(shù)求解后;步驟⑩收集者將發(fā)送給(1-β)n中的每個用戶.

3.2 HISKV隱私性與可用性分析

本節(jié)主要從本地差分隱私闡述HISKV算法的隱私性以及無偏性估計、方差及其最大偏差來闡述其可用性.從算法1可知，HISKV算法采用用戶分組的形式分別估計頻率與均值(LRR_KV算法)以及最優(yōu)截斷長度(OETL算法).

定理1.OETL算法滿足ε-本地差分隱私.

證明. 結(jié)合[βn]集合中用戶所給定任意的li與lj，算法OETL的輸出為l′，則不等式成立：

則OETL算法滿足ε-本地差分隱私.

證畢.

定理2.LRR_KV算法滿足ε-本地差分隱私.

1) 當〈k*,v*〉=〈kj,1〉時，根據(jù)定義1可知：

2) 當〈k*,v*〉=〈kj,-1〉時，類似于第1種情況：

通過4種情況可知LRR_KV算法滿足ε-本地差分隱私.

證畢.

由定理1與定理2以及差分隱私的序列組合性質(zhì)可知，HISKV收集鍵-值數(shù)據(jù)的過程滿足本地差分隱私.HISKV的可用性主要從LRR_KV算法與OETL算法的誤差來度量.OETL算法的誤差主要來自于GRR算法的本地擾動操作，根據(jù)文獻[7]可知，OETL算法產(chǎn)生的方差為βn(eε+d-2)(eε-1)2.LRR_KV算法的可用性主要從無偏性、方差、最大偏差來度量.盡管收集者可以估計出鍵k的頻率以及所對應值的均值但由于LRR_KV算法的本地擾動使得與會偏離真實值.而我們期望與均要滿足無偏性，即與成立.

根據(jù)二項分布構造極大似然函數(shù)：

(6)

(7)

將式(7)帶入式(6)可推理出：

(8)

證畢.

(9)

(10)

證畢.

其中n′=(1-β)n.

(11)

(12)

證畢.

證畢.

至少以概率1-η成立，其中n為用戶個數(shù)，為最優(yōu)截斷長度，β為用戶分組抽樣率.

則可知：

(13)

證畢.

證畢.

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

文獻[4]結(jié)論部分所給出的未來研究點正是本文的研究工作。因此，從實驗平臺、實驗數(shù)據(jù)集以及隱私參數(shù)ε的設置均與文獻[4]保持一致。實驗平臺是4核Intel i7-4790 CPU(4 GHz)，8 GB內(nèi)存，Win7系統(tǒng)，Python實現(xiàn)所有算法.采用TalkingData，JData，GAUSS，LNR四個數(shù)據(jù)集驗證文中相關算法.4個數(shù)據(jù)集具體細節(jié)如表2所示：

Table 2 Characteristics of Datasets

其中GAUSS和LNR這2個數(shù)據(jù)集為合成數(shù)據(jù)集，鍵和值分別遵循高斯和線性分布.TalkingData是從與移動應用的SDK中收集而得，包含60 822個設備和306類應用程序.JData來自于JD.com，包含2016年的5 060萬條銷售記錄，該數(shù)據(jù)集記錄了2016年間105 180個用戶對442個品牌的5 060萬條購買記錄.

隱私參數(shù)ε分別取值為0.1，0.2，0.4，0.8，1.6，3.2.此外，實驗分別對4個數(shù)據(jù)集中頻率最高的top10， top20，top30，top40，top50的鍵值進行統(tǒng)計，在每種情況下進行500次實驗并求取平均值作為最終的計算結(jié)果.

在文獻[4]中，我們分別實現(xiàn)了LDPKV,PrivKV,KVOH,RAPPOR以及Harmony算法，并結(jié)合MSE與RE進行了綜合對比分析.因此，本文主要對比HISKV算法與上述6種算法的性能.

1) 基于TalkingData數(shù)據(jù)集的多種算法的MSE和RE值比較.

圖4(a)～(f)描述了HISKV，PCKV-GRR，PrivKV，KVOH，LDPKV，RAPPOR，Harmony算法的MSE值和RE值的比較結(jié)果.由圖4(a)的實驗結(jié)果可以發(fā)現(xiàn)，當ε從0.1變化到3.2時，6種算法的MSE值均減少，而HISKV算法的精度優(yōu)于其他5種算法.當ε=1.6時，HISKV算法的精度是PCKV-GRR算法的近4倍，是PrivKV和KVOH算法的將近3倍，是LDPKV算法的將近1倍.盡管文獻[4]中提到LDPKV算法優(yōu)于PrivKV和KVOH算法，然而由于該算法沒有考慮到鍵-值的稀疏性(如圖1所示)，過多的〈0, 0〉對使得該算法的MSE大于HISKV算法.

Fig. 4 The key-value frequency and mean estimation of TalkingData圖4 基于TalkingData的鍵-值頻率與均值估計結(jié)果

由圖4(c)～(f)可知，當ε固定，鍵的數(shù)目從top10增加到top50時，相應算法的RE值均增大，但HISKV算法的精度卻優(yōu)于其他4種算法，其原因在于HISKV算法利用最優(yōu)截斷長度削弱了鍵-值值域稀疏帶來的影響.由圖4(b)中6種算法的均值MSE比較結(jié)果可知，當ε從0.1變化到3.2時，6種算法的均值MSE均呈現(xiàn)下降趨勢，而HISKV算法估計出的均值精度明顯優(yōu)于其他5種算法.當ε=1.6時，HISKV算法的均值精度是LDPKV算法的將近1倍.其主要原因在于HISKV算法利用直方圖將鍵-值對進行統(tǒng)一編碼擾動，避免了隱私預算的分割，合理增大了擾動成真實鍵的本地擾動概率.此外，HISKV算法利用截斷-抽樣技術避免了鍵-值稀疏性帶來的影響，實現(xiàn)了隱私增強.

2) 基于JData數(shù)據(jù)集的多種算法的MSE和RE值比較.

圖5(a)～(f)描述了JData數(shù)據(jù)集上7種算法的MSE值和RE值的比較結(jié)果.根據(jù)圖5(a)的實驗結(jié)果可知，當ε從0.1變化到3.2時，6種算法的MSE值均減少.當ε=1.6時，HISKV算法的精度是PCKV-GRR算法的近6倍，是PrivKV和KVOH算法的將近3倍，是LDPKV的將近2倍.其主要原因是PCKV-GRR算法沒有顧及真實鍵本地擾動概率的傾向性設置問題，PrivKV和KVOH算法隱私預算進行分割，LDPKV算法沒有考慮值域稀疏性帶來的影響.圖5(b)描述了HISKV算法與其他5種算法有關均值MSE值的比較.當ε從0.1變化到3.2時，HISKV算法的均值精度優(yōu)于其他5種算法.當ε=0.8時，HISKV算法的均值精度是PrivKV算法的近4倍，是PCKV-GRR算法的近3倍，是Harmony與KVOH的近2倍，是LDPKV算法的近1倍.在固定ε且變換top10到top50的情況下，HISKV算法同樣優(yōu)于其他4種算法.其主要原因是HISKV算法利用抽樣-截斷技術、本地擾動概率的傾向性設置以及隱私預算不分割策略提升了鍵-值的頻率與均值估計精度.

Fig. 5 The key-value frequency and mean estimation of JData圖5 基于JData的鍵-值頻率與均值估計結(jié)果

Fig. 6 The key-value frequency and mean estimation of LNR圖6 基于LNR的鍵-值頻率與均值估計結(jié)果

Fig. 7 The key-value frequency and mean estimation of GAUSS圖7 基于GAUSS的鍵-值頻率與均值估計結(jié)果

3) 基于LNR，GAUSS數(shù)據(jù)集的多種算法的MSE和RE值比較.

圖6和圖7描述了7種算法基于LNR與GAUSS合成數(shù)據(jù)集上的MSE與RE的對比結(jié)果.在百萬級別的數(shù)據(jù)上，當ε從0.1變化到3.2時，HISKV算法的精度優(yōu)于其他6種算法，如圖6(a)、圖6(b)、圖7(a)、圖7(b)所示.文獻[4]給出了LDPKV算法在LNR與GAUSS數(shù)據(jù)集上優(yōu)于PrivKV,KVOH,RAPPOR以及Harmony算法.而本文的HISKV算法卻明顯有LDPKV算法，其主要原因在于LNR與GAUSS數(shù)據(jù)集中同樣存在鍵-值的稀疏性問題，而HISKV算法的最優(yōu)截斷長度技術卻可以有效減弱鍵-值稀疏性帶來的影響.此外，當固定鍵值的個數(shù)且ε從0.1變化到0.8時，所有算法在LNR與GAUSS數(shù)據(jù)集上的RE值均下降，如圖6(c)～(f)、圖7(c)～(f)所示.當ε=0.2時，鍵值為top40時，HISKV算法的精度相對于PCKV-GRR算法，在LNR數(shù)據(jù)集上達到了近5倍，在GAUSS數(shù)據(jù)集上達到了近6倍，其主要原因是HISKV算法利用直方圖將鍵-值對看成一個整體進行擾動，不但減少了隱私預算分割和擾動次數(shù)，同時其增大了擾動成真實數(shù)據(jù)的概率.

5 結(jié)束語

針對本地差分隱私保護下收集鍵-值數(shù)據(jù)存在的問題，本文結(jié)合現(xiàn)有的該類數(shù)據(jù)收集算法存在的不足，提出了基于直方圖技術的收集算法HISKV，引入基于用戶分組策略的最優(yōu)截斷長度估計算法，結(jié)合真實鍵的實際擾動情況設置合理的擾動概率，并利用填充-抽樣技術減少用戶與收集者之間的通信代價.從本地差分隱私定義角度分析了HISKV滿足ε-本地差分隱私.理論分析了HISKV的無偏性、所產(chǎn)生的方差以及最大偏差，最后通過4種數(shù)據(jù)集驗證了HISKV算法的可用性.實驗結(jié)果表明，HISKV明顯優(yōu)于現(xiàn)有的同類算法.未來工作考慮動態(tài)環(huán)境下的隱私鍵-值數(shù)據(jù)的收集與分析問題.