基于奇異值分解模型的在線實時推薦的隱私保護

□路應金 杜素娟

[電子科技大學 成都 611731]

基于奇異值分解模型的在線實時推薦的隱私保護

□路應金 杜素娟

[電子科技大學 成都 611731]

利用縮減的奇異值分解更新算法和隨機技術提出了一個基于奇異值分解模型的在線推薦的隱私保護方法，將新數據混合到原始數據中保護消費者在線購物的隱私數據。實驗結果表明，我們提供的模型可以保證數據高效性和更低概率的隱私泄露，并且預測的精度仍然很高，對于實現消費者網上隱私保護有重要的指導意義。

奇異值分解；隱私保護；實時推薦；協同過濾

引言

伴隨著電子商務的快速發展，個性化推薦系統成為電子商務企業在線推銷商品的有力工具。亞馬遜、京東通過向消費者推薦感興趣的產品提升在線商品銷售的選擇。推薦系統是通過構建消費者的購物模式利用相關算法來預測消費者的購物偏好的系統。從上世紀90年代中期就有很多關于推薦系統的論文發表[1]，學者們將其算法和模型應用于現實生活中，大多數的推薦系統源于協同過濾算法[2～3]。協調過濾算法是推薦算法中應用得最為廣泛和成功的一種算法[4～5]。協同過濾技術也是個性化推薦中應用最成功的技術[6～7]。協同過濾技術可以分為兩大分支：鄰近算法和潛在因子模型[8]。奇異值分解算法是基于潛在因子模型的一種算法[9]。

隱私保護的協同過濾推薦研究致力于在確保高質、高效地產生推薦的同時有效地保護參與方的隱私[10]。奇異值分解模型是協同過濾算法中重要的一種典型算法[11]，是一種基于數據擾動的方法[12]。在推薦系統中，用戶并不參與原始數據的處理，他們將自己的數據發送給服務器，然后服務器進行數據的協同過濾。Polat和Du將隨機擾動加入到基于協同過濾技術的奇異值分解算法中，以此來構建隱私保護系統[13～14]，把統一的或者高斯分布的擾動加入到用戶的真實偏好中，然后服務器預測這些擾動數據的未知偏好。在這種結構下，數據擁有者也要注意數據的快速更新，以及隨著數據更新，對隱私的保護水平還可以保持在一個相對合理的位置。Stewart研究了奇異值分解算法中的擾動理論以及其在信號處理中的應用[15]。Brand論證了一個奇異值分解算法的快速降低矩陣的秩的修正算法[16]，Tougas和Spiteri證明了局部奇異值分解更新算法時需要進行正交三角分解以及完全奇異值分解時計算并不復雜[17]。Wang等提出了一種改進的奇異值分解模型，本文改進了模型的奇異值分解更新算法，加入了隨機擾動和后期的加工。

一、模型的構建

（一）基于潛在因子模型的原始奇異值分解算法

潛在因子模型[18]主要致力于用戶評分矩陣的降低維度上，以此來發掘一些潛在因子，這些因子使用最少的擾動數據可以最好地詮釋用戶的偏好，我們可以充分利用這些因子來近似估計原始評分值。在Paterek的基于潛在因子模型的奇異值分解算法中，將用戶評分矩陣因式分解成更低的評分矩陣，用戶元素矩陣UF和商品元素矩陣IF。每一個用戶i和商品j可以分別表示成一個f維度矢量UFi（矩陣UF的第i行）和IFi（矩陣IF的第j列）。我們通過計算向量UFi和IFi的內積來預測第i行第j列元素的評分。

首先，應用奇異值分解算法計算稀疏矩陣R，填補所有的缺失值，將缺失數值設置為零，然后得到用戶向量和商品向量。

這里的U和V是標準正交矩陣，S是對角線上的元素為奇異值的對角陣，且矩陣S的秩為r。

利用Berry的大范圍的稀疏奇異值算法[19]，當分解評分矩陣時，維度f（f不大于r）比較容易定義，因此用戶元素矩陣和商品元素矩陣也可以表示為：

（二）問題描述

假設數據擁有者有一個用戶評分矩陣，R∈Rm×n，其中有m個用戶和n個商品，rij表示用戶i對商品j的評分。有效的評分值取值范圍在不同網絡的情況是不同的，一些網絡評分值從1～5，1是最低評分表示不喜歡，5是最高評分代表最受歡迎，而一些網站用-10～10來評分，其中-10表示最低分，0表示中立評分，10為最高評分。

用戶的原始評分矩陣包含用戶對商品的真實評分，我們可以由此確定用戶的購物模式。這些模型可能泄露了某些用戶的隱私，所以在毫無隱私保護措施的情況下放出用戶的原始評分數據將會導致隱私的泄露。在放出用戶原始評分數據之前插補矩陣然后擾亂它是一種可行的保護用戶隱私的方法。因為所有的商品都隨著評分做了標記，所以存在缺失數值就無法分辨哪些商品已經評分。在這個過程中，插補估算缺失的評分數據，隱藏用戶對特定商品的喜好，同時這個擾動使得用戶對特定商品的喜好變得模糊不清。

當有新的用戶交易數據出現時，新的行向量，定義為T∈Rp×n，添加到原始矩陣R中，

類似的，當有新的商品交易數據出現時，新的列向量，定義為G∈Rm×q，添加到原始矩陣R中，

為了保護用戶隱私，新的評分矩陣在放出之前必須經過加工。Tr∈Rp×n表示處理過的新的行向量，Gr∈Rm×q表示處理過的新的列向量。

（三）數據更新模型

本部分主要介紹在數據更新過程保護隱私的協同過濾算法中的數據更新模型。通過在以下三個方面用戶的隱私：缺失數值的插補，隨機擾動數據和縮減的SVD算法。插補值的步驟可以保護用戶已評分的隱私信息。但是由于單一的傳統的插補值會產生相同的值并以此填入空白項，這樣的矩陣容易被攻擊。因此我們增加了另外一種隱私信息，即用戶對特定商品的實際評分值。在這種情況下，隨機性和縮減的SVD技術可以作為解決問題的第二種擾動項。一方面，隨機擾動可以一定程度上改變評分值，剩余的分布不改變。另一方面，所用的SVD技術是一種理想的數據擾動的方式，這種技術可以捕獲矩陣的潛在性質并且消除無用的擾動。對于給定的已選好的縮減排列，SVD可以在數據隱私和效用之間保持很好的平衡。

正如前面部分的陳述一樣，新的數據可以作為矩陣新的行向量或者列向量。把這些新數據添加到原始矩陣R，然后進一步擾亂數據來保護用戶隱私。相應的，我們提出的模型也可以在行向量或者列向量單獨更新的時候使用。

1.行更新

在等式（1）中，將向量T加入R中，得到的新矩陣R’是一個（m+p）×n的矩陣，假設縮減矩陣R的k階SVD先前已經計算過，

其中，Uk∈Rm×k，Vk∈Rn×k是正交矩陣；是最大有K個奇異值的對角線矩陣。

我們上一部分提到的，用戶評分矩陣在因式分解之前是一個不完全的矩陣，需要提前插入缺失值，例如，插入每個商品的平均評分值，這些平均值用來幫助更新SVD。

對于新的行向量T，在加入現存矩陣之前，先插入缺失值，用插入數值填補空白項，插入數值來自于現存矩陣和新評分數據的平均值。列的均值由下式計算：

新的列的平均值不影響原來的矩陣，因此，擁有擾動數據的第三方平臺和數據擁有者只需要釋放擾動的新數據，不需要改變列均值。

這個k階奇異值分解矩陣在下面的矩陣中計算得到

由于(k+p)是一個很小的值，奇異值分解的計算過程很快，所以我們用矩陣縮減的奇異值分解來代替完整的分解

在協同過濾算法中，所有項的值的取值范圍應該是有效的。例如，在MovielLens數據中的r的取值范圍應該是0＜r≤5。所以，在得到新的新矩陣之后，接下來的一步就是應用有效取值范圍，使得合理值取代所有的非有效值

以下總結了行更新時的奇異值分解算法步驟

2.列更新

列更新類似于行更新，但是兩者有一些不同。在新的用戶評分矩陣中，用商品平均值來填補缺失值。在行更新中，當新用戶增加時均值改變；但是列更新中，均值僅僅取決于新商品。由于這種特性，列更新時不必保持一個商品的均值矢量。

以下總結了行更新時的奇異值分解算法步驟

數據擁有者應該持有更新元素矩陣，無論是列更新還是行更新，并且插入新的數據矩陣。當用戶發生更新時，這個更新商品均值也應該由數據擁有者持有。

正像在兩種算法中表述的，在保護用戶隱私方面，結合使用了三種插入數值技術。初始插入數值替補了所有的缺失值。在插入數據中加入隨機擾動使得插入數值之間彼此不同。縮減的奇異值分解算法消除了數據的繁瑣性，這個過程保護了數據的有效性同時保護了數據的隱私。三種技術結合起來在不同方面保護隱私。

圖1 奇異值分解算法流程示意圖

二、模型評估

（一）預測模型和誤差檢測

因為奇異值分解模型不能解決缺失數值問題，如果沒有預處理值的話那些缺失數值就會為零。經典的填補缺失數值的方法就是使用商品的均值。

假設p’ij是通過基于協同過濾算法的奇異值分解模型得到的預測值，為了確保預測的評分值在有效范圍內，我們需要做一些邊界范圍的檢測：

當我們檢測預測的準確度時，用戶元素矩陣UF和商品元素矩陣IF首先來自于樣本集，然后對于在每個樣本集里的評分集，我們對所有的評分值計算出相應的預測值，并且檢測誤差值，以及絕對平均誤差，誤差值越小越好。計算公式如下：

（二）隱私估計

隱私水平是一個度量，表示我們可以通過給出的隨機變量X來估計隨機變量Y的取值范圍

隱私估計是由阿格瓦拉和阿加沃爾提出的，并且波拉提爾應用于協同過濾算法中。阿格瓦拉和阿加沃爾還提出了已知X條件下的Y的缺失值的條件隱私的估計[20]。

（三）評估策略

為了檢測何時重新進行奇異值分解，我們把評分矩陣的數據集用一個專門的比率ρ1分解成兩個子欄目。 假設第一個的ρ1已經處理過了，剩下的數據然后更新進去。然后計算矩陣中的k階奇異值分解和商品平均值矢量。我們命名K階矩陣的近似值為開始矩陣。我們利用這些數據結構作為公式（10）的輸入。我們期望得到的結果隨著分流比率不同而變化。如果結果與我們預先確定的臨界值偏離太遠，或者結果演變的更慢或者開始在某些點上下降，我們將會進行重新的計算。

然而，我們在樣本集中保留的60%行向量不僅僅只有一次更新，因為現實當中程序通常是逐步增加的。本次實驗當中，分幾次向60%的行向量添加到開始矩陣，取決于另一個分流比ρ2。比如說，如果ρ2=1/10，增加十次新數據到開始矩陣。最后由開始矩陣與十次增加矩陣之和得到的矩陣就是擾動和更新矩陣。

三、數據分析

本次實驗的數據取自MovieLens數據庫和Jester數據庫。我們選取MovieLens數據庫的10萬條評分集，其中有943位用戶和1682件商品。這十萬條評分，評分值從1～5，可分為有8萬評分的樣本集和2萬評分的測試集，兩個集合都比較稀疏。

Jester數據庫來自一個笑話推薦系統的網站，我們選取其中的數據集，包括24983位用戶和100條笑話以及1810455個評分，評分值從-10～+10。我們隨機抽取其中的80%作為樣本集，其余的作為測試集。與MovieLens數據庫相比，Jester數據沒有那么稀疏。

（一）奇異值分解算法中的縮減的秩（k）的選取

在實驗中我們從{2,5,…,25,50,100}中選取k值，然后計算相應的絕對平均誤差。MovieLens的結果如圖2，這個曲線顯示MAE隨著k值的變化而變化，并且在k=13的時候有最小值。類似的Jester的實驗結果顯示k=11的時候有最小的MAE值。因此，我們在MovieLens數據集里面選擇k=13，Jester數據集里面的k=11是合理的。

（二）分流比ρ2

在本次實驗當中，ρ1是固定的40%，也就是樣本集里的40%的數據作為起始矩陣，余下的60%的會加到矩陣里面。分別設置ρ2為1/10,1/9,1/8,…,1/2,1。

圖3描述了不同的分流比ρ2對應的時間成本。行更新用Row代表，列更新用Column代表。為了消除其中的隨機影響，設置μ和σ為零。

圖2 不同秩k值下的MAE變化圖

圖3 隨著分流比ρ2變化的時間成本圖

MovieLens數據的曲線通常是隨著分流比的增大而上升的趨勢，行更新的時間比列的更新的更長一些。在Jester數據中，當ρ2=1/3時，列更新的時間最短，行更新的時間比列的更新較短，而且在每次循環中更新的數據越少，需要的時間越短。分流比不能僅僅通過時間因素來確定，實驗中的預測精確度和隱私保護水平也是關鍵。

圖3表明更新的時間取決于行和列的維度。比如說，MovieLens數據集有列比行多，Jester數據的列比行少。每一步的行和列的算法顯示，當列數比行數多的時候，因為有更高的維度和，算法中的第一步和第三步需要更多時間。與插入數據的時間成本相比，進行原始樣本集的奇異值分解，該方案在行和列更新上運行更快。

圖4顯示，不同分流比ρ2對應的絕對平均誤差保持不變，說明更新數據的預測精確度受ρ2的影響不大，類似的隱私水平結果也是如此，如下圖4所示。

通過以上的分流比ρ2的實驗結果，我們設定在MovieLens數據中，行更新和列更新時ρ2=1/10，在Jester數據中行更新是設定ρ2=1/10，列更新時設定ρ2=1/3 。

圖4 隨著分流比ρ2變化的MAE圖

（三）分流比ρ1

由于SVD算法固有的特性，每次運算中少不了誤差。數據的擁有者應該意識到合適的時間對整個數據重新進行奇異值分解以便保證數據的質量，這個問題就是通過分流比ρ1來解決。

不同ρ1下更新數據的時間成本如圖5所示，我們預期更新的行或列數據越少花費的時間越少。但是，隨著分流比的不同，相應的行更新和列更新的時間成本保持不變。

圖5 隨著分流比ρ2變化的隱私水平圖

圖6表示了絕對平均誤差，MovieLens數據的曲線在航更新中有一個下降的趨勢，但是在列更新中保持穩定。

圖6 隨著分流比ρ1變化的時間成本圖

在Jester數據中有所不同，隨著分流比ρ1的增加絕對平均誤差在列更新中有下降趨勢，在行更新中保持穩定。這說明起始矩陣的評分值越少，預測模型刻畫用戶偏好的精確度越低，因此導致了更低的預測精準度。關于行和列對絕對平均誤差的影響，取決于行和列的維度。因為在一個評分矩陣中的信息總量是確定的，假設每個矩陣之間的輸入量是相同的，用戶的數目越少，每個用戶貢獻的信息就越多。比如，在MovieLens數據中，行維度比列維度少，因此用戶比商品扮演更重要的角色，因為用戶比商品少，所以每個用戶貢獻的信息量比每個商品多。因此隨著用戶書面的增加，絕對平均誤差減少了。在Jester數據中正好相反，行維度比列的多，因此列向量對于誤差更為關鍵。如圖7，與未更新的樣本集的絕對平均誤差MovieLens數據的0.7769和Jester數據的3.2871相比，當更新模型的ρ1為40%時，MovieLens數據的行更新為0.7951，列更新為0.7768和Jester數據的行更新為3.2870，列更新為3.3221，絕對平均誤差保持在很好的水平，預測模型可用。

圖8展示了隨著分流比變化的隱私水平，起始矩陣中的數據越多隱私水平越低，數據越多，尤其是用戶越多，對建構模型的貢獻越多，泄露的隱私也就越多。在本次實驗中，行更新的隱私水平都比列更新高，變化速度都比列的更新快。隱私在更新過程中至關重要。在已知擾亂的更新數據（X）時，得到的樣本集數據的隱私的缺失值（Y）的結果如圖9所示。

圖7 隨著分流比ρ1變化的絕對平均誤差圖

圖8 隨著分流比ρ1變化的隱私水平圖

隨著分流比的增大，隱私的缺失數值增大，隱私水平減小。兩個曲線看起來是相反的。

從圖6和圖7可以確定整個數據重新進行奇異值分解的時間，由于當ρ1大于等于50%之后絕對平均誤差下降的很慢，并且隱私保護水平曲線的斜率沒有顯著的變化，所以重新計算時的ρ1設定為50%。

（四）數據更新中的隨機性

隨機技術還未應用到我們提出的數據更新模型當中，但是隨機性還是對于數據的質量和隱私的保護很重要的。一下的實驗當中，ρ1是不變的值40%，ρ2是固定值1/9，我們試著設置μ在{0，1}中取值，σ在{0.1，1}當中取值。實驗結果如表1所示。

圖9 隨著分流比ρ1變化的隱私缺失值圖

表1 數據更新過程中的隨機性因素

在這個表格中，隨機的行更新和列更新與沒有隨機因素的進行比較。在數據更新前加入了隨機擾動的新數據，隱私量和都有一定程度的提高。但是，數據的有效性略有下降，MAE也有所增加。因此，應該在數據的效用和數據的隱私之間權衡，選擇參數。而且，結果顯示期望μ比標準差σ更能影響實驗結果，所以我們優先考慮μ。

在基于數據更新模型的奇異值分解算法中，我們采用隨機技術作為一個輔助的步驟，以便更好地保護隱私。在奇異值算法更新前插入數據是隨機的。因此，算上奇異值分解，有兩次數據的擾動，可以提高隱私保護水平。同時，通過奇異值分解獲取的潛在因子，我們可以保留關鍵的信息，確保推薦數據的質量。

四、結論

本文提出了一個基于協同過濾技術的隱私保護數據更新模型，這個模型是一個基于隨機技術的增量的奇異值分解算法，可以用來更新增量的用戶商品矩陣同時保護隱私。這個模型試著從三個方面保護消費者的隱私，分別是缺失數值的插入，隨機地擾動和縮減的奇異值分解技術。實驗結果表明，我們提出的模型可以快速地將更新的數據加入到現存的數據中，而且在保護隱私的同時推薦的精確度依然很高。

[1]ADOMAVICIUS G,TUZHILIN A.Toward the Next Generation of Recommender Systems: A Survey of the State-ofthe-Art and Possible Extensions[J].IEEE Transactions on Knowledge and Data Engineering,2005,17(6):734-749.

[2]GOLDBERG D,NICHOLS D,OKI B,TERRY D.Using Collaborative Filtering to Weave an Information Tapestry[J].Communications of the ACM,1992,35:61-70.

[3]KONSTAN J,MILLER B,MALTZ D,HERLOCKER J,et al.GroupLens: Applying Collaborative Filtering to Usenet News[J].Communications of the ACM,1997,40:77-87.

[4]黃宇.基于協同過濾的推薦系統設計與實現[D].北京: 北京交通大學,2015.

[5]劉青文.基于協同過濾的推薦算法研究[D].北京: 中國科學技術大學,2013.

[6]姚婷.基于協同過濾算法的個性化推薦研究[D].北京: 北京理工大學,2015.

[7]沈鍵.電子商務的個性化協同過濾推薦算法研究[D].上海: 上海交通大學,2013.

[8]KOREN Y.Factorization Meets the Neighborhood: a Multifaceted Collaborative Filtering Model[C]// The 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Las Vegas: Nevada,2008: 436-434.

[9]SARWAR B,KARYPIS G,KONSTAN J,RIEDL J.Application of Dimensionality Reduction in Recommender Systems[J].In Acm Webkdd Workshop,2000.

[10]張鋒,孫雪冬,常會友,趙淦森.兩方參與的隱私保護協同過濾推薦研究[J].電子學報,2009(01): 84-89.

[11]PATEREK A.Improving Regularized Singular Value Decomposition for Collaborative Filtering[J].Proceedings of KDD Cup and Workshop,2007(8):39-42.

[12]李光,王亞東.一種改進的基于奇異值分解的隱私保持分類挖掘方法[J].電子學報,2012(04): 739-744.

[13]POLAT H,DU W.Privacy-Preserving Collaborative Filtering [J].International Journal of Electronic Commerce,2005,9(4):9-35.

[14]POLAT H,DU W.SVD-based Collaborative Filtering with Privacy[J].ACM Symposium on Applied Computing,2005,1:791-795.

[15]STEWART G.Perturbation Theory for the Singular Value Decomposition [J].SVD &Signal Processing II Algorithms Analysis &Applications,1996,13(9):99-109.

[16]BRAND M.Fast Low-Rank Modifications of the Thin Singular Value Decomposition [J].Linear Algebra and its Applications,2006,415(1):20-30.

[17]TOUGAS J,SPITERI R.Updating the Partial Singular Value Decomposition in Latent Semantic Indexing [J].Computational Statistics &Data Analysis,2007,52: 174-183.

[18]KOREN Y.Factorization Meets the Neighborhood: a Multifaceted Collaborative Filtering Model[C]// the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Las Vegas: Nevada,2008:436-434.

[19]BERRY M.Large-scale Sparse Singular Value Computations [J].International Journal of High Performance computing Application,1992,6(1):13-49.

[20]ADOMAVICIUS G,TUZHILIN A.Toward the Next Generation of Recommender Systems: A Survey of the State-ofthe-Art and Possible Extensions[J].IEEE Transactions on Knowledge and Data Engineering,2005,17(6):734-749.

Privacy Preservation of Online Real-Time Recommendation Based on the SVD Scheme

LU Ying-jin DU Su-juan
( University of Electronic Science and Technology of China Chengdu 611731 China)

The most personalized recommendation method research of online shopping faces challenges about how to ensure the validity of data during the data sharing process and protect users' personal privacy.In this paper,we propose a privacy preserving scheme of online recommendation based on the SVD algorithm by the truncated SVD update algorithms and randomization techniques.It turns out that the proposed scheme can conduct data efficiently and protect data privacy effectively.It is of important guiding significance for privacy preserving of online consumers.

SVD;privacy preservation;real-time recommendation;collaborative filtering

G206.2

A

10.14071/j.1008-8105(2017)02-0074-08

編 輯 何婧

2015-11-25

國家自然科學基金（71372140）.

路應金（1964-）男，博士，電子科技大學經濟與管理學院副教授；杜素娟（1993-）女，電子科技大學經濟與管理學院碩士研究生.