楊 競，向 真，王小驥

(1. 中國電子科技集團公司第三十研究所，四川 成都 610041；2. 93114部隊，北京 100195)

1 引言

隨著越來越多地用戶使用移動設(shè)備，利用在線商店進行商品購買的人數(shù)也越來越多。這種數(shù)據(jù)泛濫通常意味著消費者面臨許多選擇，這使得決策更加困難。推薦系統(tǒng)可幫助消費者找到感興趣或者建議的項目[1～2]。因此，推薦系統(tǒng)在我們的日常生活中變得越來越普遍，從電影到商品的推薦。推薦系統(tǒng)可收集和挖掘用戶數(shù)據(jù)以獲得更好的用戶體驗[3]。然而，用戶數(shù)據(jù)包括個人信息，常常會引起隱私問題。

差分隱私由于其強大的隱私保障能力，是解決隱私問題的常用工具。已經(jīng)有一些工作將差分隱私應(yīng)用于推薦系統(tǒng)。例如，文獻[4]應(yīng)用差分隱私來保護每個用戶的項集，但其采用隨機化算法干擾了位于預(yù)定類別內(nèi)的項，導(dǎo)致用戶的類別偏好可能被暴露。文獻[5]還提出了局部模型，其中用戶的私人數(shù)據(jù)被擾動之前提交給推薦者。文獻[6]提出一種RAPPor算法來收集和分析用戶數(shù)據(jù)而不侵犯隱私。RAPPor建立在隨機反應(yīng)的概念之上，它是由Warner開發(fā)的一種調(diào)查技術(shù)，用于收集敏感話題的統(tǒng)計數(shù)據(jù)。文獻[7]開發(fā)改進的RAPPor實用LDP解決方案。其隨機化機制使得能夠分析分類數(shù)據(jù)和數(shù)值數(shù)據(jù)，以及基于隨機梯度下降的機器學(xué)習(xí)任務(wù)。文獻[8]提出一種用于差分私有矩陣分解的梯度擾動算法，以防止不可信推薦者學(xué)習(xí)任何用戶的評級或配置文件。此類文獻還有很多，不再贅述?，F(xiàn)有的方法均從不同的角度提出了差分隱私的改進方案，取得了很好的效果，但是也存在不足，主要體現(xiàn)在兩個方面：①其被設(shè)計成保護用戶的評價或用戶評價的項目，但不能同時保護兩者。在許多情況下，用戶的項目集與她的評分一樣存在敏感信息，因為推斷用戶對哪些項目進行了評分可以泄露其政治觀點等隱私信息。②其關(guān)注于保護單個項目或用戶的整個項目及其評級中的評級值。然而，在推薦系統(tǒng)中，存在高度相關(guān)的項目集(例如，同一類型的電影)。掩蓋相關(guān)項中單個項的存在或不存在不足以保護用戶的敏感信息。此外，用戶通常一次上傳一組收視率。從這個意義上說，單一評級或項目的保護在實踐中并不適合。人們可能會試圖擴展現(xiàn)有的方案，以便將差別隱私應(yīng)用于每個項目和評價。此外，這些算法中的大多數(shù)假設(shè)可信推薦場景，然而，隨著推薦服務(wù)越來越流行，許多不信任推薦者出現(xiàn)在網(wǎng)上，可能超出服務(wù)濫用用戶隱私，特別是用戶存在非對稱化時，可能存在個人數(shù)據(jù)意外泄漏問題。

本文的目標是通過保證每個用戶的強隱私性，建立一個解決現(xiàn)有文獻局限性的推薦系統(tǒng)。在協(xié)同過濾技術(shù)中使用矩陣分解進行推薦。我們發(fā)展了新的用于矩陣分解的差分隱私梯度下降算法。通過采用Nguyen等人建議的最新LDP梯度擾動解決方案來保護用戶的私有數(shù)據(jù)，包括項目、評級和配置文件。驗證了矩陣因式分解算法的最終項目配置文件在用戶或不在用戶之間沒有顯著差異，從而保證每個用戶的隱私，并通過采用隨機投影降維技術(shù)，減小了大量項目引起的攝動誤差，該解決方案將保護用戶的項和評級放在一起，保證每個用戶隱私，并保持推薦質(zhì)量。

2 問題描述

2.1 算法框架

圖1 所提差分隱私推薦系統(tǒng)概述

由于各個用戶的梯度包括關(guān)于評級rij和用戶配置文件ui的信息，所以需要在每次迭代中保護用戶的梯度。因此，所提隨機擾動算法被設(shè)計為在每次迭代中滿足ε/k-LDP，以保護由項、評級和用戶簡檔組成的整個數(shù)據(jù)。在局部隱私模型中，評價模型中的M不能先驗地知道，除非用戶公開他們評級的項目的數(shù)量。因此，本文采用n代替M來改進所提梯度下降算法。所有參數(shù)，即n、γt、λu、λv、d和k由推薦者給出。隱私預(yù)算ε也由推薦者給出。

2.2 矩陣分解

假設(shè)n個用戶對m項的子集(例如，電影)進行評級。利用M?{1，…，n}×{1，…，m}表示已生成評級的用戶/項對，m是項目的數(shù)量。令M=|M|是總評級數(shù)。利用rij表示由用戶i生成的項目j的評級。在實際設(shè)置中，提供的評級是稀疏的，因此M比nm小得多，而n和m都大。對于給定評級{rij：(i，j)∈M}，推薦系統(tǒng)可預(yù)測未被用戶評定的項目的評級。矩陣分解用于計算用戶配置文件ui∈Rd，1≤j≤n，以及項目的配置文件vj∈Rd，1≤j≤m，d是潛在因素數(shù)?？赏ㄟ^最小化已知評級集上正則均方誤差獲得

(1)

(2)

式中，γt>0是迭代t的學(xué)習(xí)率，U是用戶配置文件矩陣，其第i行是ui，V是項目輪廓矩陣，其第j行是vj。?uiφ(U，V)和?vjφ(U，V)分別是ui和vj的梯度，可計算為

(3)

式中，?uiφ(U，V)和?vjφ(U，V)特征是用戶配置文件ui應(yīng)該改變以減少均方誤差。學(xué)習(xí)率γt是一個常數(shù)，通常被設(shè)置為O(1/t)。

3 基于服務(wù)器隨機擾動的差分隱私矩陣分解

3.1 項目保護和評價

早期的研究中就將拉普拉斯機制應(yīng)用于梯度，以保護用戶的收視率。在他們的算法中，推薦者要求評分項目j的用戶以私有的方式提交他們的梯度。因此，聚合器可以了解用戶是否具有評級項目j。在本節(jié)中，我們提出了一個簡單的解決方案來克服現(xiàn)有工作中的問題。

如果用戶i對項目j進行評價，則令yij為1，否則設(shè)定yij為0。對于(i，j)?M，令rij=0。

(4)

因此公式(3)中?vjφ(U，V)梯度形式可改寫為

(5)

(6)

(7)

(8)

服務(wù)器利用噪聲梯度的平均值更新項目配置文件vj，即

(9)

3.2 用戶隱私的服務(wù)器梯度擾動

為了減少V估計中的誤差，采用隨機化方法。特別地，該方法考慮這樣的場景，其中每個用戶都有一個要由服務(wù)器收集的多維元組，并且要求用戶在提交元組時隨機選擇一個維度，并在所選維度上提交其元組值的擾動版本，同時忽略所有其他維度。由服務(wù)器收集的擾動值可以用于估計每個維度上的所有用戶值的平均值，并且估計誤差顯著小于每個用戶在所有維度上提交其值的情況。算法1給出基于服務(wù)器隨機擾動的矩陣分解算法。

算法1：差分隱私梯度下降

輸入：預(yù)定義迭代數(shù)k與隱私參數(shù)ε；

輸出：項目配置矩陣V∈km×d；

1) 初始化U、V以及迭代計數(shù)器iter=0；

2)whileiter≤kdo

4)fori=1tondo

6) 在{1，2，…，m}中對j進行采樣；

7) 在{1，2，…，d}中對l進行采樣；

9)if(xi)j，l?[-1，1]，將(xi)j，l映射到[-1，1]區(qū)間；

13)endif

15)endfor

18)fori=1tondo

19)ui=ui-γt·{?ui+2λuui}；

20)endfor

21)endwhlie

22)returnV

3.3 通過降維實現(xiàn)精度提升

(10)

(11)

對于任意的a，b∈Rm，存在

(12)

(13)

對于給定的{ui∈d，1≤i≤n}，可得更新公式

Bt=Bt-1-γt·{?Bψ(Ut-1，Bt-1)+2λvBt-1}

(14)

(15)

(16)

算法1：基于降維的差分隱私梯度下降

輸入：正整數(shù)q，預(yù)定義迭代數(shù)k與隱私參數(shù)ε；

輸出：項目配置矩陣V∈Rm×d；

1) 初始化U、V以及迭代計數(shù)器iter=0；

2)whileiter≤kdo

4)fori=1tondo

8) 在{1，2，…，m}中對j進行采樣；

9) 在{1，2，…，d}中對l進行采樣；

10)if(xi)j，l?[-1，1]，將(xi)j，l映射到[-1，1]區(qū)間；

14)endif

16)endfor

18)fori=1tondo

20)endfor

21)endwhlie

22)returnV

4 實驗分析

4.1 實驗設(shè)置

本節(jié)實驗選取的硬件配置為：英特爾i5-6400K 3.2GHz，內(nèi)存為8GHx，系統(tǒng)是win8旗艦版。為驗證本文算法的有效性，這里選取文獻[14]的LAP和文獻[15]的NOE兩種算法作為對比算法，其中LAP算法采用的是拉普拉斯噪聲攝動算法。本文算去的實驗對象是表1數(shù)據(jù)。

表1 選取的數(shù)據(jù)集

表1中的有關(guān)參數(shù)，參數(shù)U是實驗對象中設(shè)定的用戶數(shù)量，參數(shù)E1是實驗對象中用戶之間的關(guān)系數(shù)量，參數(shù)E2是實驗對象中用戶和項目之間的關(guān)系數(shù)量，參數(shù)Item是實驗對象中的項目的數(shù)量。

為了驗證三種對比算法的差分隱私推薦結(jié)果可用性，選取的實驗評價指標是NDCG指標，定義形式如下

(17)

式中，參數(shù)項NDCG(k，u)是實驗對象中用戶u對差分隱私項目k進行可用性推薦的評估指標，定義形式為

(18)

式中，參數(shù)項index(Ii)是差分隱私項目Ii在(k)數(shù)據(jù)集中的位置索引。同時，為了評估Flixster數(shù)據(jù)集和Last.fm兩個數(shù)據(jù)集的差分隱私推薦相似性，這里選取近鄰關(guān)系指標

(19)

(20)

式中，參數(shù)項Γ(u)是同數(shù)據(jù)集中用戶u的關(guān)系近鄰集。

4.2 可用性度量評價

采用表1中所示的兩種實驗數(shù)據(jù)集，實驗過程中通過設(shè)定不同的項目推薦數(shù)k以及隱私預(yù)算ε，來獲得不同大小的可用性推薦的評估指標NDCG(k，u)，其中參數(shù)ε={0.1，0.4，0.7，1.0}，k={10，40，70，100}。參數(shù)實驗如下：

1)隱私預(yù)算ε影響實驗：本實驗中設(shè)定數(shù)據(jù)集中差分隱私的推薦數(shù)量是k=40，實驗過程中選擇改變隱私預(yù)算ε，分別采用Jaccard度量指標對算法的有效性進行驗證。則對比算法在選取實驗集上的NDCG評估指標見圖2～3所示。

圖2 實驗集(Last.fm)上的NDCG指標變化情況

圖3 實驗集(Flixster)上的NDCG指標變化情況

根據(jù)圖2～圖3實驗結(jié)果可知，當實驗參數(shù)隱私預(yù)算ε在區(qū)間[0.1，1.0]變化時，指標NDCG的取值從大到小的趨勢進行變化，主要原因是算法中因為隱私預(yù)算ε取值越大，其在算法實現(xiàn)過程中所需要的拉普拉斯噪音的取值越小，但是本文算法因為采用了用戶隱私的服務(wù)器梯度擾動，因此其所得到的NDCG指標取值大約是文獻[14]算法的3倍，是文獻[15]的2倍。

2)參數(shù)m變化影響實驗。本部分實驗環(huán)節(jié)中，設(shè)定隱私預(yù)算為固定值，即ε=0.4，對于不同取值的差分隱私推薦數(shù)量m，選取Jaccard度量指標對算法的有效性進行驗證。則對比算法在選取實驗集上的NDCG評估指標見圖4～5所示。

圖4 實驗集(Last.fm)上的NDCG指標變化情況

圖5 實驗集(Flixster)上的NDCG指標變化情況

根據(jù)圖4～5實驗結(jié)果可知，當差分隱私推薦項目個數(shù)由10個逐漸增加到100個時，集中對比算法的NDCG指標均呈現(xiàn)出單調(diào)遞增的趨勢，當時相對來講，本文算法在選取的實驗數(shù)據(jù)集上的NDCG指標均保持在90%以上，對比算法中文獻[14]算法可保持在80%以上，而文獻[15]算法僅維持在不到60%的水平，主要原因在于本文算法在針對實驗數(shù)據(jù)集的項目用戶之間具有較低的噪音。

4.3 算法對比測試

這里仍然選取文獻[14～15]作為對比計算方法，對比指標對象見表1。選取算法計算時間和隱私數(shù)據(jù)恢復(fù)精度作為對比指標，驗證算法的數(shù)據(jù)推薦質(zhì)量，實驗結(jié)果見表2所示。

表2 算法對比測試

為了更加穩(wěn)定的評估算法的性能，這里選取實驗運行10次的平均計算指標作為對比結(jié)果。根據(jù)表2所示實驗結(jié)果可知，在計算時間實驗對比指標上，本文算法在Last.fm測試集上的差分隱私推薦時間是2.35s左右，而對比算法文獻[14]算法為5.69s，文獻[15]算法為52.6s，本文算法相對于文獻[14～15]兩種算法計算時間分別提升58.70%和69.91%。而在推薦精度指標上，本文算法的推薦精度為98.76，比文獻[14～15]兩種算法高6.18%和10.25%，這表明本文算法在Last.fm測試集上的差分隱私推薦效率和推薦質(zhì)量均要優(yōu)于選取的文獻[14～15]兩種對比算法。同時，在Flixster測試集上本文算法也要優(yōu)于文獻[14～15]兩種對比算法，呈現(xiàn)出相似性能表現(xiàn)。

5 結(jié)束語

與現(xiàn)有的差分隱私矩陣因式分解相比，本文的工作創(chuàng)新如下：①可獲得更大程度的隱私權(quán)保證，所提矩陣分解算法可保證每個用戶的隱私，這是比現(xiàn)有算法更強的隱私保證。②極大地提高了推薦精度。LDP在用戶數(shù)據(jù)上的直接應(yīng)用引起一個大的攝動誤差，該誤差隨著項目的數(shù)量呈現(xiàn)線性增長。這里采用隨機投影進行降維，并采用最新的隨機化算法來減少加入到梯度中的噪聲量。此外，我們還通過穩(wěn)定噪聲梯度來減少迭代造成的精度損失。③大大降低了通信成本。每個用戶在每次迭代中只向服務(wù)器發(fā)送一個比特，而現(xiàn)有的工作要求每個用戶發(fā)送其長度與由其評定的項目數(shù)量成比例的數(shù)據(jù)。同時，通過降維減少了從服務(wù)器到用戶的通信開銷。