一種基于隨機投影的本地差分隱私高維數(shù)值型數(shù)據(jù)收集算法

孫慧中,?楊健宇,?程祥,?蘇森

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

摘要：對滿足本地差分隱私的高維數(shù)值型數(shù)據(jù)收集問題進行了研究。設(shè)計了一種基于隨機投影技術(shù)的滿足本地差分隱私的高維數(shù)值型數(shù)據(jù)收集算法Multi-RPHM，在滿足本地差分隱私的條件下，該算法處理維度較高的數(shù)據(jù)時能夠保證所收集的數(shù)據(jù)的高效用。從理論上證明了該算法滿足ε-本地差分隱私的要求。在合成數(shù)據(jù)集上進行的實驗結(jié)果驗證了該算法的有效性。

關(guān)鍵詞：高維數(shù)值型數(shù)據(jù)?;?隱私保護?;?本地差分隱私?;?隨機投影

論文引用格式：

孫慧中,?楊健宇,?程祥,?蘇森.一種基于隨機投影的本地差分隱私高維數(shù)值型數(shù)據(jù)收集算法. ?大數(shù)據(jù)[J], 2020, 6(1）：3-11

SUN H Z, YANG J Y,CHENG X, SU S.A high-dimensional numeric data collection algorithm for local difference privacy based on random projection.?Big Data Research[J], 2020, 6(1):3-11

1 引言

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

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

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

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

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

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

2.2 本地差分隱私

本地差分隱私的定義如下。

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

特別地，對于一系列本地差分隱私算法，整體隱私保護強度滿足如下串行機制。

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

2.3 問題定義

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

文中常用的符號及說明見表1。

3 Multi-HM算法

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

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

算法1 Multi-HM算法

輸入:用戶數(shù)據(jù)ti∈[?1,1]d、隱私參數(shù)ε。

輸出:擾動結(jié)果。

初始化

令

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

for

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

if f >α then

else

令，

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

if

隨機選取

else

隨機選取；返回

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

4 Multi-RPHM算法

4.1 算法設(shè)計

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

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

圖1????Multi-RPHM算法的整體框架

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

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

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

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

Multi-RPHM算法（算法2）如下。其輸入為所有用戶原始高維數(shù)據(jù){ti∈[-1,1]d|1≤j≤n}、隱私參數(shù)ε、投影維度q，輸出為高維數(shù)據(jù)矩陣。在該算法中，數(shù)據(jù)收集者首先生成一個 d ×q 維的隨機投影矩陣，并將其廣播給所有用戶。具體地，采用經(jīng)典的正交矩陣方法構(gòu)造，即首先生成一個d ×q 維的隨機矩陣，該矩陣中每個元素均由均值為0、標準差為的高斯分布采樣生成，然后將該矩陣進行Gran-Schmidt正交化，使得矩陣的每一列都是標準正交的，最后對矩陣的每一列進行歸一化處理。對于每個用戶首先計算q維的向量，然后將xi中的所有值映射到[-1,1]。具體地，對于，如果 xi[s]<?1，則令xi[s]=?1；如果xi[s]>1，則令xi[s]=1。接著，用戶ui執(zhí)行Multi-HM算法對xi進行隱私處理，得到擾動后的低維數(shù)據(jù)元組，并將其發(fā)送給數(shù)據(jù)收集者。在收集到所有用戶的擾動結(jié)果集合后，數(shù)據(jù)收集者構(gòu)建n×q維的矩陣X*，該矩陣的第i行為。最后，數(shù)據(jù)收集者通過廣義逆矩陣對X*進行維度恢復(fù)，得到原始屬性維度的數(shù)據(jù)集，其中，的第i行對應(yīng)用戶ui的具有隱私保護的高維數(shù)據(jù)。

算法2 Multi-RPHM

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

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

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

for每個用戶ui?do

計算；

fordo

如果xi[s]?[?1,1]，將xi[s]映射到[-1,1]；

end for

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

end for

數(shù)據(jù)收集者根據(jù)集合構(gòu)建矩陣X*；

數(shù)據(jù)收集者計算矩陣T*=X*?R；

返回T*；

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

4.2 隱私分析

對于任意用戶及隱私預(yù)算ε，Multi-RPHM算法滿足ε-本地差分隱私，具體證明過程如下。

對于任意兩個不同的高維數(shù)據(jù)元組t1,2t ∈[?1,1]d，用戶端的隱私化處理流程如圖2所示，即用戶首先利用投影矩陣R將其降維為，然后通過Multi-HM算法對其進行擾動，最后將擾動后的低維數(shù)據(jù)元組傳送給數(shù)據(jù)收集者。

圖2???t1、t2的算法處理流程

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

由于Multi-HM算法滿足ε-本地差分隱私，即對于任意的以及任意的輸出x*，始終有：

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

綜上所述，成立。

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

5 實驗分析

5.1 實驗設(shè)置

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

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

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

在實驗中，本文設(shè)置隱私參數(shù)ε∈{0.6,0.8,1.0,1.2,1.4}。對于Multi-RPHM算法，本文設(shè)置參數(shù)q=0.3d。本文所有實驗均在內(nèi)存為8 GB、處理器為Intel Core i5 2.9 GHz的計算機上進行。實驗結(jié)果均為各種算法運行10次的平均結(jié)果。

5.2 結(jié)果分析

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

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

圖3???屬性維度改變時Multi-RPHM算法與Multi-HM算法對比

圖4???不同隱私保護強度下Multi-RPHM算法與Multi-HM算法對比

6 結(jié)束語

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

作者簡介

孫慧中（1998-），女，北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點實驗室碩士生，主要研究方向為隱私保護和機器學(xué)習(xí) 。

楊健宇（1994-），男，北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點實驗室博士生，主要研究方向為隱私保護 。

程祥（1984-），男，北京郵電大學(xué)副教授、博士生導(dǎo)師，主要研究方向為數(shù)據(jù)挖掘、知識工程、隱私保護等。其研究成果已發(fā)表在包括IEEEICDE、IEEEICDM、AAAI、IJCAI、EMNLP、IEEETKDE、IEEETDSC、IEEETSC等在內(nèi)的國際會議和期刊上。主持與大數(shù)據(jù)隱私保護相關(guān)的國家自然科學(xué)基金青年科學(xué)基金項目1項、國家自然科學(xué)基金項目面上項目1項，并作為科研骨干參與多項國家級和部級科研項目 。

蘇森（1971-），男，北京郵電大學(xué)教授，計算機學(xué)院執(zhí)行院長，中國計算機學(xué)會理事，服務(wù)計算專業(yè)委員會秘書長，“數(shù)字中國產(chǎn)業(yè)發(fā)展聯(lián)盟”副理事長。2005年入選教育部“新世紀優(yōu)秀人才支持計劃”，2017年入選國家“萬人計劃”科技創(chuàng)新領(lǐng)軍人才。目前主要研究方向為智能數(shù)據(jù)服務(wù)、數(shù)據(jù)隱私保護、社交網(wǎng)絡(luò)分析。獲國家科技進步獎二等獎1次，中國通信學(xué)會科技進步獎一等獎1次，教育部科技進步獎二等獎1次 。

《大數(shù)據(jù)》期刊

《大數(shù)據(jù)（Big Data Research，BDR）》雙月刊是由中華人民共和國工業(yè)和信息化部主管，人民郵電出版社主辦，中國計算機學(xué)會大數(shù)據(jù)專家委員會學(xué)術(shù)指導(dǎo)，北京信通傳媒有限責(zé)任公司出版的中文科技核心期刊。

關(guān)注《大數(shù)據(jù)》期刊微信公眾號，獲取更多內(nèi)容

往期文章回顧

基于數(shù)據(jù)空間的電子病歷數(shù)據(jù)融合與應(yīng)用平臺

基于APMSSGA-LSTM的容器云資源預(yù)測

Hadoop下水環(huán)境模擬集群運算模式

WEB：一種基于網(wǎng)絡(luò)嵌入的互聯(lián)網(wǎng)借貸欺詐預(yù)測方法

基于SARIMA-LSTM的門診量預(yù)測研究

---

總結(jié)

以上是生活随笔為你收集整理的一种基于随机投影的本地差分隐私高维数值型数据收集算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。