滿足差分隱私保護的矩陣分解推薦算法

王 永，冉 珣，尹恩民，王 利

(1.重慶郵電大學電子商務與現代物流重點實驗室 重慶南岸區400065；2.桂林電子科技大學廣西密碼學與信息安全重點實驗室 桂林 541004)

推薦系統是當前互聯網商家為用戶提供個性化信息服務的主要技術手段之一。協同過濾作為一類主流的推薦算法，它利用用戶對項目的歷史評價信息來預測用戶對未知項目的好惡并據此進行推薦。協同過濾技術需要使用大量用戶數據，存在用戶個人隱私泄漏的風險[1]。在基于鄰居的協同過濾技術中，攻擊者可以通過追蹤鄰居用戶的推薦列表變化，推測目標用戶對項目的評分[2]；在基于矩陣分解的協同過濾技術中，由于分解所得的隱因子矩陣攜帶數據信息，可能被攻擊者利用，通過重構攻擊等方式推斷出用戶的評分數據[3-4]。遭泄露的評分可能被進一步用于推測出用戶的性別、年齡等信息，侵犯用戶隱私[5]。如果用戶出于安全考慮拒絕提供部分信息，則可能會導致推薦系統性能下降，甚至無法提供個性化服務。因此，非常有必要在推薦系統中考慮對用戶信息進行隱私保護。

文獻[6]提出了差分隱私的定義，為在推薦系統中實施有效隱私保護提供了良好的理論基礎。文獻[7]將差分隱私保護引入協同過濾技術中，通過擾動項目協方差矩陣實現差分隱私保護。文獻[8]將差分隱私應用到基于鄰居的協同過濾推薦算法中，通過在鄰居選擇和相似性度量過程中加入噪音，實現隱私保護。文獻[9]提出了兩種分別對原始評分和用戶相似性度量過程添加Laplace噪音的隱私保護方案。

針對基于矩陣分解的推薦算法，文獻[10]在考慮推薦系統不可信的情況下，擾動矩陣分解算法的目標函數，將實施了隱私保護的項目隱因子矩陣用于推薦任務。文獻[11]假設用戶有不同程度的隱私保護需求，基于概率矩陣分解提出一種個性化的差分隱私推薦算法。文獻[12]通過對目標函數進行擾動，提出了基于聯合優化的隱私矩陣分解方案。文獻[13-14]將差分隱私保護應用到矩陣分解推薦算法中，設計了3種添加噪音的方式，即分別在輸入信息中、訓練過程中和輸出信息中添加噪音。依據這種思想，文獻[15]在SVD++模型上設計了3種差分隱私保護模型。目前的工作大多通過對矩陣分解過程的各種結果(如梯度、隱因子矩陣、目標函數)加入噪聲項以實現差分隱私保護，這類方案存在如下問題：1)噪聲較大。較高的隱私保護需求或敏感度會使噪聲分布的方差增大，導致加入過大的噪聲；2)不具通用性。加噪方法可能導致最終解在有約束問題上不可行；3)沒有考慮隱因子的重要程度，影響了算法求解效率。

針對上述問題，本文將遺傳算法引入矩陣分解任務，使得差分隱私保護可以通過擾動候選解的選擇過程實現，而不依賴于上述加入噪聲的方法[16]。此外，遺傳算法中解的搜索將在可行域內進行，易于延伸到帶約束的矩陣分解問題。然而，直接應用遺傳算法存在如下困難：首先，矩陣分解屬非凸問題且參數量大，求解難度高；其次，如何減小隱私保護機制引入的擾動也是重要挑戰。為解決上述問題，本文改進了遺傳算法的關鍵步驟，提出一種滿足差分隱私保護的矩陣分解方案。本文的主要貢獻為：1)將矩陣分解轉化為兩個交替進行的用戶隱因子和項目隱因子優化問題，有效克服了求解過程中存在的解空間高維性和優化中的非凸性問題。2)考慮用戶或項目對隱因子的不同偏重，重新設計了遺傳算法的變異過程，提升解的搜索效率；在此基礎上利用增強指數機制減輕了算法受擾動程度，更好地實現了隱私保護水平和算法效用之間的平衡。

1 理論知識

1.1 矩陣分解算法

矩陣分解是隱語義推薦模型的典型算法，它將用戶和項目均映射到相同的d維隱因子空間中[17]。將用戶u對應的隱因子向量表示為P u∈Rd，將由所有用戶的隱因子向量構成的矩陣表示為P；將項目i的隱因子向量表示為Q i∈Rd，將所有項目的隱因子向量構成的矩陣表示為Q；則矩陣分解算法就是求解滿足式(1)的最佳P和Q：

式中，rui為用戶評分矩陣r中用戶u對項目i的評分；K為觀測到的評分數據對應的用戶?項目對(u,i)集 合。假設r中包含的用戶數為m，項目數為n，則有r∈Rm×n,Q∈Rn×d,P∈Rm×d，其中d?m,n。

1.2 差分隱私

差分隱私(differential privacy,DP)是一種新型隱私保護框架，通過添加可控的噪聲到數據的統計結果中，保證隱私不被泄露且數據具有可用性。

定義1差分隱私(DP)[6]：對于任意的鄰近數據集D和D′至多相差一條數據，且隨機算法A所有可能的輸出O?Range(A)，當且僅當滿足不等式(2)時，A滿足ε-差分隱私：

式中，ε為隱私預算，當ε值越小時，隱私保護的需求水平越高。

1.3 指數機制

指數機制[18]是一種實現差分隱私保護的技術手段，其定義如下。

定義2指數機制：設隨機算法M的輸入為數據集D，輸出為ω ∈Ω。 函數Q(D,ω)→R為 ω的可用性函數。若算法M以正比于e xp(εQ(D,ω)/Δ)的概率從Ω 中選擇并輸出ω，則算法M提供ε-差分隱私保護，稱算法M為指數機制。其中，Δ為可用性函數Q(D,ω)的阻尼因子，也稱Q(D,ω)的敏感度，表示單個數據的差異對Q(D,ω)造成的最大影響。假設D′與D為鄰近數據集，Δ滿足不等式：

1.4 增強指數機制

文獻[16]針對模型擬合問題設計了增強指數機制，與指數機制相比，增強指數機制的應用限于可用性函數，具有特定形式：

式中，D是包含了n個元組的數據集；T 是任意元組t的取值范圍；q(t,ω)為元組擬合函數，表示模型對D中單個元組t的擬合程度；h(ω)是獨立于數據集D的函數?；诖丝捎眯院瘮?，增強指數機制的定義如下。

定義3增強指數機制(enhanced exponential mechanism,EEM)：設隨機算法M的輸入為數據集D，輸出為 ω∈Ω。 算法M以正比于exp(εf(D,ω)/Δ)的概率從 Ω中選擇并輸出ω，其中f(D,ω)滿足式(4)且Δ 滿足不等式：

那么算法M提供ε-差分隱私保護，稱算法M為增強指數機制。

2 隱私遺傳矩陣分解算法

2.1 算法總體流程

本文算法圍繞推薦系統的評分矩陣分解展開，將隱因子矩陣P和Q的求解過程轉化為兩個交替進行的優化過程。在優化過程中使用遺傳算法求解，并在求解過程中引入增強指數機制，進而使矩陣分解過程滿足差分隱私保護。本文算法的總體流程如下：

1)為提高評分預測準確性，對用戶評分矩陣r進行預處理，即設邊界參數為B，將評分轉化到[?B,B]的范圍，得到新的用戶評分矩陣R。然后，對矩陣R進行隱因子分解，即：

式中，Rui為R中用戶u對項目i的真實評分。隱因子分解的目標是找到使預測評分與真實評分誤差平方和最小的P和Q矩陣。

2)將式(6)的目標問題轉換成兩類特征求解任務：1)求解用戶的隱因子向量；2)求解項目的隱因子向量。即在求解P u時，將矩陣Q看作常數，構建目標函數：

同理，在求解Q i時，保持P矩陣不變，構建目標函數：3)首先保持矩陣Q不變，使用2.2節設計的隱私遺傳算法(APrivGene)為每個用戶求解式(7)所示的優化問題，得到對應的用戶隱因子，更新矩陣P。然后，保持矩陣P不變，同樣使用2.2節設計的隱私遺傳算法為每個項目求解式(8)所示的優化問題，得到對應的項目隱因子，更新矩陣Q。交替重復上述過程，持續優化P和Q矩陣，直至達到最大迭代次數T。

上述隱私遺傳矩陣分解算法的偽代碼如算法1所示，其中改進的隱私遺傳算法APriveGene將在2.2節中進行詳細說明。

2.2 改進的隱私遺傳算法

本算法對文獻[16]中的隱私遺傳算法進行了改良，提出調整的隱私遺傳算法(adjusted private genetic algorithm, APrivGene)。使用APrivGene算法對式(7)和式(8)所示的優化問題進行求解，在選擇階段引入增強指數機制，實施對矩陣分解過程的隱私保護。按照執行順序、從初始化、選擇和變異3個方面介紹APrivGene算法。

初始化階段：設置包括ε在內的各個控制參數。然后，隨機生成l個d維的向量作為初始候選解集 Ω ，計算 Ω 中每個解的目標函數值f(D,ω)作為遺傳算法的適應度值。

選擇階段：以f(D,ω)為可用性函數，使用ε/2TG作為選擇操作的隱私預算，應用增強指數機制EEM以正比于 exp(εf(D,ω)/2TGΔ)的概率從 Ω中挑選出 ω。為了有效減輕選擇階段引入的擾動，只選出單個個體進行后續操作，之后將 Ω置空，準備接納新解。

變異階段：為避免交叉操作造成敏感度過大，只使用了變異操作。為了改善尋優效率，采用全局搜索效率較高的柯西變異算子生成變異擾動，即從標準柯西分布C(0,1)中生成隨機擾動。然后，以尋找重要程度最高的隱因子為目的，讓變異操作對各個隱因子進行變化，且每次只在一個維度k上搜索。由于用戶或項目對某隱因子的偏好可分為正負兩類，對單個隱因子的擾動對應地被設計為正負兩個方向。對每個維度進行上述變異，每次變異生成兩個新解，加入Ω ，最后形成新的候選解集。

生成新集合之后，為逐步減小搜索范圍提高尋優效率，使用衰減因子β 縮減變異步長η。然后，返回選擇環節，進入下一輪循環。當達到最大迭代次數G時，使用EEM方式選出最終解ω?。

上述改進的隱私遺傳算法的偽代碼如算法2所示。

初始化算法中的控制參數：設置隱因子個數d，隱私預算ε，變異步長η，衰減因子 β<1，最大迭代次數G，候選解集Ω 的大小l；

在算法2中，為了發揮增強指數機制的作用，在每次迭代中需要根據當前候選解，求解增強指數機制中的阻尼因子。求解過程如2.3節所示。

2.3 阻尼因子求解

在求解隱因子向量時，根據候選集合中個體的適應值f(D,ω)和隱私預算ε，EEM將按照如下的概率輸出用戶隱因子向量和項目隱因子向量：

數據集Du或Di中的元組t有d+1個屬性，其中預處理后的評分數據Rui在 [?B,B]之 間，|Puk|≤1和|Qik|≤1，k∈{1,2,···,d}，所以元組t的取值范圍T=[?B,B]×[?1,1]d。設 ΔPu為求解用戶隱因子向量時的阻尼因子， ΔQi為求解項目隱因子向量時的阻尼因子，則根據增強指數機制的定義可得：

同理可得求解項目隱因子向量時阻尼因子ΔQi應滿足的條件為：

觀察 ΔPu和 ΔQi應 滿足的條件，可以發現 Δ2衡量的是候選解集中各隱因子向量之間的差異。在多數情況下 Δ1>Δ2，這是因為隨著APrivGene的迭代，q(t,P u)?q(t,Pu′)或q(t,Q i)?q(t,Qi′)的 值 會 逐 漸 減小，但 Δ1的值并不會受到APrivGene迭代的影響。所以，隨著APrivGene迭代次數增加，阻尼因子會減小，增強指數機制可以選擇出更精確的解，從而有效保證算法的效用。

3 算法的分析

3.1 安全性分析

定理1算法1滿足ε-差分隱私。

證明：令D為數據集Du或Di，D′與D為其鄰近數據集，t和t′分別表示D與D′中相異的元組；令ω為隱因子向量P u或Q i，在應用APrivGene求解ω時，設EEM的隱私預算 ε′=ε/2TG，T表示算法1(PGMF)中外循環的次數，G表示算法2(APrivGene)中的最大迭代次數。令Δ 為EEM的阻尼因子ΔPu或ΔQi，根據2.3節中式(9)和式(10)，考慮以下兩種情況：

故應用APrivGene算法求解隱因子向量時，其每一輪迭代均滿足ε /2TG-差分隱私。由差分隱私保護的序列組合性質可得，更新每個用戶或項目的隱因子向量時算法滿足 ε/2T-差分隱私，算法1滿足ε-差分隱私。

3.2 效用分析

3.2.1對問題轉化的分析

本文算法將矩陣分解的求解轉換為對兩個優化問題的求解，這樣處理有兩點優勢：

1)更好地體現個性化的思想。因為直接求解式(6)可能忽視單個個體的推薦質量。轉化為式(7)和式(8)所示的問題后，可以為每個用戶或每個項目分別設計其專屬的考慮隱私保護的隱因子值，更好地體現個性化的推薦思想，利于提升推薦精度。

2)提升算法效率和效用。直接對原問題應用遺傳算法求解，解的維度將是d×(m+n)，而推薦系統中的用戶數m和項目數n通常都很龐大。采用遺傳算法在高維空間中尋優，將會導致效率非常低。同時，原問題關于P，Q是非凸的，也會導致算法收斂速度慢。過慢的收斂速度，會導致迭代輪次增加。由于需要在每輪迭代中添加隱私保護的噪音，會導致噪聲增大，從而使解的質量下降甚至不可用。本算法將原問題分解為兩個優化問題，使得各個子問題都是凸問題，且解的維度是隱因子個數d，它遠小于m和n，極大地提高了求解的效率，也利于提高解的效用。

3.2.2改進隱私遺傳算法的分析

APrivGene算法是PrivGene算法的改進算法。PrivGene算法并沒有對變異操作進行專門的設計，它所采用的隨機變異方式，將導致解的搜索效率不高，影響最終解的質量。APrivGene算法在變異操作中，對選擇的個體沿著解的各個維度，從正反兩個方向使用標準柯西分布生成隨機擾動進行變異，具有如下優勢：

1)有助于EEM選出更好的解。EEM的特點是，當候選解之間的變動程度不大時，其敏感度將取得較小值從而減輕選擇過程的擾動。單維度變異所生成的新解之間只存在一個隱因子上的差異，此時式(9)和式(10)中對于ΔPu和ΔQi通常有Δ1>Δ2。隨著算法逐漸收斂， Δ2的取值將更小，增強指數機制的阻尼因子減小，使得選中優質解的概率提高。

2)有助于提高解的搜素效率并減少擾動。矩陣分解中用戶和項目共享相同的隱因子，但不同的用戶或項目對不同的隱因子會有不同程度的關注，單維度變異將有利于快速找到相對重要的隱因子。用戶或項目對隱因子只有正向或負向兩類偏好，變異算子在隱因子的正負方向上同時進行搜索，而非隨機搜索，符合實際情況。該做法有效提升了解的搜索效率，同時控制了候選解之間的變動程度，減輕選擇過程受到的擾動。

3)標準柯西分布 C(0,1)由于有較高的兩翼概率特性，具有較好的全局搜索能力，能幫助算法在迭代的初期保持一定程度的多樣性。設置了衰減因子β在每次迭代時對步長η 進行縮減，利于在迭代后期增強指數機制實現更優的選擇。因為隨著迭代進行，式(9)和式(10)中ΔPu和ΔQi的值Δ2會逐漸減小，但 Δ1的值并不會受到影響，這樣增強指數機制的阻尼因子會減小，使選擇過程受到更少的擾動，做出更優的選擇。

4 實驗結果與分析

4.1 實驗數據

采用兩個常用數據集Movielens100K和YahooMusic進行實驗，按8∶2的比例隨機劃分為訓練集和測試集。兩個數據集的統計屬性如表1所示。

表1 實驗數據集統計屬性

4.2 實驗算法與評估指標

除本文算法外，還對其他一些類似算法進行了對比實驗。實驗中涉及到的算法及其描述如表2所示。

本文取10次實驗的平均值作為最終結果。采用均方根誤差(RMSE)度量算法的性能：

式中，T為有效預測項目的個數；rui為用戶u對項目i的真實評分；r?ui為用戶u對項目i的預測評分。RMSE越小則推薦精度越高。

4.3 實驗結果

采用文獻[14]中的預處理方式，將評分區間轉換為[?1,1]，設置隱因子變量域為[?1,1]。在APrivGene中，最大迭代輪次為23，候選集大小為85，柯西變異算子的步長為0.2，步長的衰減率為0.95。對比算法的參數設置均遵循相應文獻中的最優參數設置。

為了保證有效的隱私保護，實驗中將隱私預算ε設置為較小范圍，即 ε∈[0.1,1]。圖1和圖2分別給出了本算法與其他對比算法在Movielens100K和YahooMusic兩個數據集上的RMSE測試結果。其中，將不考慮隱私保護的ALSBase算法的實驗結果作為對比基線。從整體上看，隨著ε的增大，各個算法的RMSE均逐漸減小，表明隨著隱私保護水平的下降，推薦準確性增加。各算法在Movielens 100K數據集上的推薦準確性均高于YahooMusic數據集，主要原因是YahooMusic數據集具有更高的稀疏性。

圖1 Movielens100K數據集上的RMSE測試結果

在圖1中，隨著ε的變化，PGMF在Movielens 100K數據集上的RMSE為： 0.995≤RMSE≤1.308，低于其他的隱私保護算法。同樣的趨勢也存在于YahooMusic數據集的測試中。在圖2中，PGMF的RMSE總是低于其他對比算法，其RMSE值的范圍為1 .290≤RMSE≤1.670，比其他隱私保護算法平均低0.2左右，顯示出了更好的準確性。在兩個數據集上，PGMF與不考慮任何隱私保護的ALSBase算法的RMSE差距是最小的，同樣證明了PGMF具有更好的推薦準確性。

圖2 YahooMusic數據集上的RMSE測試結果

在本實驗中，DPALS算法的推薦準確性比DPSGD算法要高。因為在不考慮隱私保護的情況下，ALS的性能比SGD要好，這種優越性在考慮差分隱私的情形下同樣存在。但是，這兩種方法都是基于傳統優化方式的算法，當隱私預算ε越小，DPSGD和DPALS所引入的噪聲就越大，導致求解出的隱因子向量與最優解之間差距過大，推薦準確度降低。在圖1中，ε =0.1時，DPALS與DPSGD的RMSE都超過了2.1，而PGMF的RMSE只有1.3；在圖2中，ε=0.1時，DPALS與DPSGD的RMSE都超過了2.3，而PGMF的RMSE只有1.67。比較結果說明在隱私保護要求較高時，PGMF的優勢更為明顯。

DPSGDInput算法是文獻[13]中表現最優的算法，直接對評分數據添加噪音。它不需要在矩陣分解過程中分配隱私預算，在較低隱私保護需求下具有良好的推薦準確性。當ε=1時，其RMSE值在Movielens100K與YahooMusic數據集上分別為1.06和1.44，是除PGMF算法以外最低的。但是，這種直接對數據集加噪音的方式在高隱私保護需求下會引入過大的噪聲。從圖1和圖2中可以看出，在ε<0.5時，該算法的推薦RMSE值顯著增加，其推薦準確性比DPALSObj算法和PGMF更差。

DPALSObj算法通過對目標函數進行擾動而實現隱私保護。它的推薦精度在高隱私保護條件下，即ε∈[0.1,0.5]時，優于除PGMF之外的其他隱私保護算法。這種方法對隱私預算的大小比較敏感，在高隱私保護需求下相對于PGMF仍然引入了過大的噪聲，即便在其表現更為突出的YahooMusic數據集上，其RMSE仍然明顯比PGMF高。

PGMF的性能優于其他算法的主要原因是采用了獨特的進化方式限制了候選解集的方差，又借助增強指數機制改善了解的選擇過程。所以，即使在很小的隱私預算條件下，求解出的隱因子向量都不會偏離最優解太遠，實現了更高的推薦準確度。

5 結束語

本文針對推薦系統中的隱私問題提出了一種滿足差分隱私保護的矩陣分解算法。該算法將矩陣分解問題轉化為兩個交替進行的優化問題。在遺傳算法的選擇操作中采用了增強指數機制使得整個矩陣因子分解的過程滿足差分隱私保護?；谒阉髦匾[因子的思想，設計了遺傳算法的變異操作，從正反兩個方向變異隱因子，不僅提高了算法的效率而且有效增強了解的性能。在兩個標準數據集上的實驗結果表明本文算法能更好地平衡隱私性和推薦的準確性，尤其在隱私保護需求較高的條件下，仍然可以取得良好的推薦效果，具有很好的應用潛力。