孫慧中，楊健宇，程祥，蘇森

北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，北京 100876

1 引言

隨著互聯(lián)網(wǎng)和云計(jì)算等信息技術(shù)的發(fā)展，各種智能設(shè)備日益普及，用戶的高維數(shù)值型數(shù)據(jù)被許多服務(wù)提供商（如谷歌等互聯(lián)網(wǎng)公司）收集。通過收集用戶的高維數(shù)值型數(shù)據(jù)，服務(wù)提供商能夠分析和挖掘這些數(shù)據(jù)的價(jià)值，以提供更好的用戶體驗(yàn)，并增加收益。例如，在推薦系統(tǒng)中，用戶的商品評(píng)分?jǐn)?shù)據(jù)就是一種典型的高維數(shù)值型數(shù)據(jù)，通過收集用戶的商品評(píng)分?jǐn)?shù)據(jù)，服務(wù)提供商能夠分析商品流行趨勢(shì)，從而更有效地為用戶推薦商品，并且更合理地投放廣告，以增加營業(yè)額。然而，用戶的高維數(shù)值型數(shù)據(jù)中往往包含大量的敏感信息（如興趣偏好等），如果沒有隱私保護(hù)，直接對(duì)這些數(shù)據(jù)進(jìn)行收集可能導(dǎo)致嚴(yán)重的用戶隱私泄露問題，進(jìn)而阻礙商業(yè)運(yùn)營。因此，用戶高維數(shù)值型數(shù)據(jù)收集中的隱私問題亟待解決。

隱私保護(hù)的數(shù)據(jù)收集技術(shù)為解決數(shù)據(jù)收集帶來的個(gè)人隱私泄露問題提供了一種可行的方案。近年來提出的差分隱私（differential privacy，DP）技術(shù)[1-3]是目前比較先進(jìn)的隱私保護(hù)技術(shù)。與傳統(tǒng)的基于匿名的隱私保護(hù)技術(shù)（例如，k-匿名[4]和L-多樣性[5]）不同，差分隱私技術(shù)提供了一種嚴(yán)格的、可證明的隱私保護(hù)手段，并且其提供的隱私保護(hù)強(qiáng)度并不依賴于攻擊者掌握的背景知識(shí)。本地差分隱私技術(shù)（local differential privacy，LD P）[6-7]是一種專門解決數(shù)據(jù)收集導(dǎo)致個(gè)人隱私泄露問題的技術(shù)，該技術(shù)已被應(yīng)用于眾多現(xiàn)實(shí)應(yīng)用軟件之中，如Google公司的Chrome瀏覽器[8]等。該技術(shù)的主要思想是每個(gè)用戶在將自己的真實(shí)數(shù)據(jù)發(fā)給數(shù)據(jù)收集者之前就對(duì)其進(jìn)行加噪處理。由于用戶的真實(shí)數(shù)據(jù)始終存儲(chǔ)在用戶本地，本地差分隱私技術(shù)可以有效地避免不可信收集者的惡意攻擊，從根本上為用戶提供隱私保護(hù)。

當(dāng)前，本地差分隱私技術(shù)已被應(yīng)用于一維或多維分類型數(shù)據(jù)收集[8-13]以及多維數(shù)值型數(shù)據(jù)收集[14-15]中。其中，一種可以用于處理這些問題的簡單方案是數(shù)據(jù)收集者直接調(diào)用Multi-HM算法[14]。該算法是當(dāng)前先進(jìn)的、滿足本地差分隱私的多維數(shù)據(jù)收集算法，該算法的基本思路是每個(gè)用戶從屬性集合中隨機(jī)選取幾個(gè)屬性，并進(jìn)行加噪處理，然后將加噪后的屬性信息發(fā)送給數(shù)據(jù)收集者。然而，運(yùn)用該算法收集到的數(shù)據(jù)的準(zhǔn)確性受維度高低（即屬性個(gè)數(shù)大?。┯绊懨黠@，在處理具有較高維度的用戶數(shù)據(jù)時(shí)，會(huì)導(dǎo)致收集的數(shù)據(jù)中包含大量的噪聲，因此不適用于用戶高維數(shù)值型數(shù)據(jù)的收集。為此，本文提出了一種基于隨機(jī)投影技術(shù)的本地差分隱私數(shù)據(jù)收集算法——Multi-RPHM算法。在該算法中，首先用戶基于隨機(jī)投影技術(shù)對(duì)自身原始高維數(shù)據(jù)進(jìn)行降維，然后數(shù)據(jù)收集者對(duì)降維后的數(shù)據(jù)進(jìn)行收集并進(jìn)行維度還原。直觀上，由于數(shù)據(jù)收集者只需收集低維數(shù)據(jù)，因此Multi-RPHM算法能有效降低收集到的數(shù)據(jù)中包含的噪聲，獲得較高的數(shù)據(jù)效用。

2 預(yù)備知識(shí)與問題定義

2.1 高維數(shù)值型數(shù)據(jù)

用戶的高維數(shù)值型數(shù)據(jù)是一種典型的個(gè)人數(shù)據(jù)，由多個(gè)數(shù)值型屬性構(gòu)成，每個(gè)屬性反映用戶不同方面的信息。特別地，給定一個(gè)屬性集合A={A1,A2,…,Ad}，其中，d表示屬性數(shù)量，Aj代表第j個(gè)屬性，并且每個(gè)屬性的取值均為實(shí)數(shù)。據(jù)此，本文將一個(gè)用戶的高維數(shù)值型數(shù)據(jù)表示為一個(gè)元組t=[t[A1],t[A2],…,t[Ad]]，其中t[Aj]代表元組t中第j個(gè)屬性的取值。本文假定所有屬性的取值范圍均為[-1,1]，即t[Aj]∈[-1,1]（1≤j≤d）。

2.2 本地差分隱私

本地差分隱私[6-7]的定義如下。

ε-本地差分隱私：給定一個(gè)隱私參數(shù)ε，對(duì)于一個(gè)隨機(jī)算法M，當(dāng)且僅當(dāng)任意兩個(gè)輸入值v、v′和任意一個(gè)可能的輸出值O∈Range(M)滿足計(jì)算式（1），則稱算法M滿足ε-本地差分隱私。

特別地，對(duì)于一系列本地差分隱私算法，整體隱私保護(hù)強(qiáng)度滿足如下串行 機(jī)制[16]。

串行機(jī)制：給定r個(gè)本地差分隱私算法Mi(1≤i≤r)，其中第i個(gè)算法Mi滿足εi-本地差分隱私，則算法序列M i(v)滿足本地差分隱私。

2.3 問題定義

給定n個(gè)用戶ui(1≤i≤n)，其中ui代表第i個(gè)用戶。每個(gè)用戶ui擁有的高維數(shù)值型數(shù)據(jù)用元組ti來表示。本文的目標(biāo)是設(shè)計(jì)一個(gè)滿足本地差分隱私的算法，使一個(gè)不可信的數(shù)據(jù)收集者收集到的用戶高維數(shù)值型數(shù)據(jù)集{ti*|1≤i≤n}與用戶的原始數(shù)據(jù)集{ti|1≤i≤n}具有相同的統(tǒng)計(jì)特征。為了便于分析，本文假定所有用戶均采用相同的隱私參數(shù)ε。

文中常用的符號(hào)及說明見表1。

3 Multi-HM算法

目前，可以處理該問題的方法共有3種：Laplace加噪算法[2]、MeanEST算法[15]和Multi-HM算法。在Laplace加噪算法中，每個(gè)用戶向其原始數(shù)據(jù)的各個(gè)屬性維度注入滿足Laplace分布的隨機(jī)噪聲，然后將加噪后的數(shù)據(jù)發(fā)送給數(shù)據(jù)收集者。在MeanEST算法中，首先，用戶根據(jù)其原始數(shù)據(jù)產(chǎn)生2個(gè)集合，每個(gè)集合中包含多個(gè)數(shù)據(jù)元組；然后，用戶依照特定概率選擇一個(gè)集合；最后，用戶在該集合中隨機(jī)選取一個(gè)數(shù)據(jù)元組，并將其作為擾動(dòng)結(jié)果發(fā)送給數(shù)據(jù)收集者。但是，這2種方法均存在一定的缺陷：Laplace加噪算法引入的隨機(jī)噪聲是無界的，即噪聲的取值可能無窮大或無窮小，會(huì)導(dǎo)致收集的數(shù)據(jù)噪聲較大、效用較差；而對(duì)于MeanE S T算法，用戶返回的擾動(dòng)元組始終落在原始數(shù)據(jù)域之外，也會(huì)導(dǎo)致收集的數(shù)據(jù)的效用較差。為了解決上述2種方法存在的缺陷，參考文獻(xiàn)[14]中提出了一種新的滿足本地差分隱私的多維數(shù)值型數(shù)據(jù)收集算法，即Multi-HM算法。

具體地，對(duì)于每個(gè)用戶ui，Multi-HM算法（算法1）如下。其輸入是用戶數(shù)據(jù)隱私參數(shù)ε，輸出是擾動(dòng)結(jié)果在該算法中，用戶ui首先初始化擾動(dòng)結(jié)果，計(jì)算參數(shù)k、ε*、C和α。然后，在A中隨機(jī)選取k個(gè)屬性構(gòu)成集合S；接著，對(duì)每個(gè)屬性A j∈S，用戶ui計(jì)算

算法1 Multi-HM算法

在A中隨機(jī)選取k個(gè)屬性構(gòu)成屬性集合S；

在[0,1]內(nèi)選取隨機(jī)數(shù)f；

在[0,1]內(nèi)選取隨機(jī)數(shù)x；

返回

參考文獻(xiàn)[4]證明了Multi-HM算法滿足ε-本地差分隱私，并且對(duì)數(shù)據(jù)收集者運(yùn)用該算法收集到的數(shù)據(jù)集進(jìn)行了效用分析。然而，根據(jù)其分析結(jié)果，本文發(fā)現(xiàn)運(yùn)用Multi-HM算法收集到的數(shù)據(jù)的效用受屬性個(gè)數(shù)d的影響明顯。隨著d的增大，數(shù)據(jù)效用逐漸變差。對(duì)于較大的d（如d>200），Multi-HM算法會(huì)產(chǎn)生較大的誤差，難以滿足實(shí)際應(yīng)用需求。

4 Multi-RPHM算法

4.1 算法設(shè)計(jì)

為解決Multi-HM算法在處理較大屬性個(gè)數(shù)d時(shí)誤差較大的問題，本文提出了Multi-RPHM算法。用戶首先通過隨機(jī)投影對(duì)自身原始高維數(shù)據(jù)進(jìn)行降維，然后數(shù)據(jù)收集者收集用戶降維后的數(shù)據(jù)并進(jìn)行維度還原。隨機(jī)投影（random projection，RP）[17]是一種有效的降維技術(shù)，在投影維度選擇合理時(shí)，降維后的低維數(shù)據(jù)能夠保留原始數(shù)據(jù)的特征信息。

Multi-RPHM算法的整體框架如圖1所示，共包括4個(gè)步驟。

● 數(shù)據(jù)收集者生成一個(gè)隨機(jī)投影矩陣，并將其廣播給所有用戶。

● 每個(gè)用戶利用該投影矩陣對(duì)其原始高維數(shù)據(jù)進(jìn)行降維處理，分別得到對(duì)應(yīng)的低維數(shù)據(jù)元組。

● 數(shù)據(jù)收集者利用Multi-HM算法對(duì)所有用戶降維后的數(shù)據(jù)進(jìn)行收集。

● 數(shù)據(jù)收集者利用投影矩陣的廣義逆矩陣對(duì)收集到的低維擾動(dòng)數(shù)據(jù)進(jìn)行維度恢復(fù)，得到與原始維度相同的高維數(shù)據(jù)。

Multi-RPHM算法（算法2）如下。其輸入為所有用戶原始高維數(shù)據(jù){ti∈[-1,1]d| 1≤j≤n}、隱私參數(shù)ε、投影維度q，輸出為高維數(shù)據(jù)矩陣T*。在該算法中，數(shù)據(jù)收集者首先生成一個(gè)d q× 維的隨機(jī)投影矩陣Rd×q，并將其廣播給所有用戶。具體地，Rd×q采用經(jīng)典的正交矩陣方法構(gòu)造，即首先生成一個(gè)d q× 維的隨機(jī)矩陣，該

矩陣中每個(gè)元素均由均值為0、標(biāo)準(zhǔn)差為1/k的高斯分布采樣生成，然后將該矩陣進(jìn)行Gran-Schmidt正交化，使得矩陣的每一列都是標(biāo)準(zhǔn)正交的，最后對(duì)矩陣的每一列進(jìn)行歸一化處理。對(duì)于每個(gè)用戶ui，首先計(jì)算q維的向量，然后將xi中的所有值映射到[-1,1]。具體地，對(duì)于如果xi[s] ＜?1 ，則令如果，則令接著，用戶ui執(zhí)行Multi-HM算法對(duì)xi進(jìn)行隱私處理，得到擾動(dòng)后的低維數(shù)據(jù)元組并將其發(fā)送給數(shù)據(jù)收集者。在收集到所有用戶的擾動(dòng)結(jié)果集合后，數(shù)據(jù)收集者構(gòu)建n×q維的矩陣X*，該矩陣的第i行為。最后，數(shù)據(jù)收集者通過廣義逆矩陣RT對(duì)X*進(jìn)行維度恢復(fù)，得到原始屬性維度的數(shù)據(jù)集T=X*R+，其中，T*的第i行(T*)i=ti*對(duì)應(yīng)用戶ui的具有隱私保護(hù)的高維數(shù)據(jù)。

算法2 Multi-RPHM

輸入: 用戶原始高維數(shù)據(jù){ti∈[-1,1]d|1≤j≤n}、隱私參數(shù)ε、投影維度q。

輸出: 估計(jì)高維數(shù)據(jù)矩陣T*。

數(shù)據(jù)收集者生成d q× 維的隨機(jī)投影矩陣d qR×，并廣播給所有用戶；

for 每個(gè)用戶uido

將xi和ε作為參數(shù)執(zhí)行Multi-HM算法，生成擾動(dòng)結(jié)果，并發(fā)送給數(shù)據(jù)收集者；

數(shù)據(jù)收集者根據(jù)集合{xi*|1≤i≤n}構(gòu)建矩陣X*；

返回T*；

為了說明Mu l ti-R PHM算法的有效性，本文對(duì)其誤差進(jìn)行了討論分析。Multi-R PHM算法的誤差來源主要包括兩個(gè)方面：一是數(shù)據(jù)降維與維度恢復(fù)；二是低維數(shù)據(jù)的隱私化處理。當(dāng)原始數(shù)據(jù)維度較大時(shí)（例如 200d＞ ），Multi-RPHM算法通過降維能夠有效地減少隱私化處理引入的誤差，并且保證維度恢復(fù)產(chǎn)生的誤差相對(duì)較小，從而降低總體誤差。因此，Multi-RPHM算法能夠在保證數(shù)據(jù)隱私的同時(shí)，降低誤差，提高數(shù)據(jù)效用，具有一定的有效性。

4.2 隱私分析

由本地差分隱私的定義可知，對(duì)于上述高維數(shù)據(jù)元組12, [ 1,1]d t t∈? 以及數(shù)據(jù)收集者收集的任意低維擾動(dòng)數(shù)據(jù)x*，要證Multi-RPHM算法滿足ε-本地差分隱私，即證：

屋子里很快想起鼾聲。響屁連天。我們破天荒地睡了個(gè)懶覺，被李大頭喊起來時(shí)，天已完全亮了。我們提著褲子，急匆匆尋露天廁所。室內(nèi)的廁所不夠這么多人排泄。

由于Multi-HM算法滿足ε-本地差分

另外，由于隨機(jī)投影矩陣Rd×q的生成不依賴于用戶的數(shù)據(jù)，因而Rd×q不泄露隱私（R+同理）。因此，由給定的Rd×q以及式（2）可得到：

因此，Multi-RPHM算法滿足ε-本地差分隱私。

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

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

本文在多個(gè)合成數(shù)據(jù)集上對(duì)Multi-RPHM算法進(jìn)行了測(cè)試。每個(gè)合成數(shù)據(jù)集包含10 000個(gè)用戶的高維數(shù)據(jù)記錄，維度（即屬性個(gè)數(shù)）分別為200、300、400、500、600。特別地，根據(jù)參考文獻(xiàn)[14]，本文設(shè)置這些數(shù)據(jù)集均由均值 1/3μ= 、標(biāo)準(zhǔn)差σ1/4 = 的高斯分布采樣生成，并且數(shù)據(jù)取值在[ 1,1]? 內(nèi)。

為了評(píng)估Multi-RPHM算法的性能，參照參考文獻(xiàn)[4]的評(píng)估方法，本文選取均方誤差（mean square error，MSE）作為評(píng)測(cè)指標(biāo)，對(duì)收集到的高維數(shù)據(jù)集的效用進(jìn)行評(píng)估。具體地，假設(shè)原屬性均值為估計(jì)均值為，其中d代表屬性個(gè)數(shù)，則的計(jì)算式如下：

由于Multi-HM算法是目前比較先進(jìn)的滿足本地差分隱私的多維數(shù)據(jù)收集算法，因此，為了驗(yàn)證Multi-RPHM算法的有效性，本文選取Multi-HM算法作為實(shí)驗(yàn)中的對(duì)比算法。

5.2 結(jié)果分析

首先，本文固定隱私參數(shù)ε=1.0，投影維度q=0.3d，用戶數(shù)n=10 000，在屬性維度不同的合成數(shù)據(jù)集上對(duì)Multi-HM算法和Multi-RPHM算法進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果如圖3所示。可以看出，隨著屬性維度d增加，Multi-HM算法的效果明顯變差，而Multi-RPHM算法受維度影響不大，算法性能穩(wěn)定。這是因?yàn)镸ulti-HM算法受維度d影響較大，而Multi-RPHM算法通過隨機(jī)投影技術(shù)將高維數(shù)據(jù)降至低維，且僅收集低維數(shù)據(jù)，降低了隱私化處理引入的擾動(dòng)誤差。當(dāng)維度d較大時(shí)（如400、500、600），Multi-RPHM算法的優(yōu)勢(shì)變得更加明顯，這說明其具有良好的可擴(kuò)展性，更適用于高維數(shù)據(jù)的收集。

其次，為了測(cè)試隱私保護(hù)強(qiáng)度對(duì)算法準(zhǔn)確性的影響，本文固定屬性維度d=400，投影維度q=0.3d，以評(píng)估Multi-HM算法和Multi-RPHM算法在不同隱私參數(shù)下的性能，實(shí)驗(yàn)結(jié)果如圖4所示。值得注意的是，圖4中的RP代表只進(jìn)行數(shù)據(jù)降維及維度恢復(fù)操作，不添加隱私保護(hù)時(shí)的均值誤差。可以看出，隨著ε變大，兩種算法的MSE均逐漸減小，Multi-RPHM算法的誤差逐漸趨近RP，且始終低于Multi-HM算法。特別地，當(dāng)隱私參數(shù)ε較小時(shí)（如0.6、0.8、1.0），Multi-RPHM算法明顯優(yōu)于對(duì)比算法Multi-HM。正如第4.1節(jié)中分析的，這是因?yàn)镸ulti-RPHM算法的總體誤差由兩個(gè)因素引起，一個(gè)是數(shù)據(jù)的降維與維度恢復(fù)，另一個(gè)是低維數(shù)據(jù)的隱私化處理。當(dāng)ε較小時(shí)，用戶采用Multi-HM算法直接對(duì)原始的高維數(shù)據(jù)隱私化處理會(huì)引入大量噪聲，而Multi-RPHM算法通過降維有效地降低了這部分誤差的引入，從而總體誤差較小，優(yōu)勢(shì)更加明顯。

6 結(jié)束語

針對(duì)滿足本地差分隱私的高維數(shù)值型數(shù)據(jù)收集問題，本文提出了一種基于隨機(jī)投影的隱私數(shù)據(jù)收集算法，即Multi-RPHM算法。本文在理論上證明了Multi-RPHM算法滿足ε-本地差分隱私。同時(shí)，實(shí)驗(yàn)結(jié)果驗(yàn)證了Multi-RPHM算法的有效性。本文提出的Multi-RPHM算法適用于多種真實(shí)場(chǎng)景，具有較強(qiáng)的實(shí)際應(yīng)用價(jià)值。此外，需要指出的是，高維數(shù)據(jù)一般包括數(shù)值型、分類型、混合型3種類型，本文主要聚焦在高維數(shù)值型數(shù)據(jù)收集的問題上，而高維分類型和混合型數(shù)據(jù)的收集具有新的問題場(chǎng)景和挑戰(zhàn)，解決這兩個(gè)問題具有很高的研究價(jià)值與現(xiàn)實(shí)意義，能夠豐富高維數(shù)據(jù)收集問題的理論體系。本文提出的基于數(shù)據(jù)降維的解決思路，能夠?yàn)榻鉀Q上述問題提供一定的借鑒意義。