差分隱私保護下一種改進的協同過濾推薦算法

王彤　黃樹斌

【 摘 要 】 協同過濾（CF）是推薦系統中最常用的算法，然而傳統的構建在協同過濾上的推薦系統很難提供一個嚴格并有數學證明的隱私保證。近期研究表明，攻擊者可以通過觀察用戶的推薦結果，推測出用戶的評分記錄，這將對用戶的隱私造成極大的威脅。論文在應用差分隱私保護技術的隱私保持協同過濾算法的基礎上，對用戶與物品進行裁剪，從而大量減少了噪聲的引入，在保證隱私的前提下提升了算法準確度。同時，論文提出的算法改進方法具有較廣的適用性，能夠與已有的研究能夠很好的結合。

【 關鍵詞 】 協同過濾（CF）；差分隱私保護；安全

【 Abstract 】 Collaborative Filtering （CF） is the most common algorithm in recommender system. However， the traditional approaches can hardly provide a rigid and provable privacy guarantee for recommender system. Recent research revealed that by observing the public output of the CF， the adversary could infer the historical ratings of the particular user， which will cause a great threat to user privacy. This paper address the privacy issue in CF by cutting the data， which is constructed on the basis of the notion of differential privacy. As a result， this method would reduce the large number of noise introduced by differential privacy algorithm， and increase the accuracy of the algorithm with privacy preserving. Furthermore， our method can easily apply in the existing research.

【 Keywords 】 collaborative filtering； differential privacy； security

1 引言

Ramakrishnan等人首次提出在推薦系統中的隱私問題，Narayanan等人通過聯合Netflix與IMDB的發布數據集成功的標識出部分戶。Calandrino等人通過觀察推薦系統一段時間內推薦結果的變化，結合背景知識推斷出某用戶的歷史評分與行為。

差分隱私保護是一種在滿足差分隱私的條件下保證發布數據或查詢結果的精確性的，有著嚴格數學證明的理論，能夠有效的保護個人隱私。在通常情況下，由于推薦系統中的查詢往往具有較高的敏感度，所以應用差分隱私技術會引入大量的噪聲，這會導致在保證隱私的同時會有較大的精度損失。

很多學者就差分隱私在推薦系統中的應用提出不同的方法，在隱私保護與推薦的準確性方面均取得了不錯的效果，但仍有許多局限性，它們主要表現在兩個方面。

（1）差分隱私技術會引入噪聲，由于推薦系統中的查詢往往具有較高的敏感度，所以應用差分隱私技術會引入大量的噪聲，導致數據可用性較差。為了減少大量噪聲的引入，現有研究往往采用各自定義的局部敏感度進行計算，但這使得推薦算法僅在特定應用場景有較好的效果。

（2）現有研究的各種隱私保護推薦算法對原有算法進行了大量的改進，但算法的大量修改使得其很難利用傳統推薦領域已有研究成果。

本文在應用差分隱私保護技術的隱私保持協同過濾算法的基礎上，根據隱私保護程度對用戶與物品進行裁剪，從而大量減少了噪聲的引入。同時，本文提出的算法改進方法具有較廣的適用性，能夠與已有的研究能夠很好的結合。

2 改進的隱私保持協同過濾推薦算法

在本部分，我們將提出改進的隱私保持協同過濾推薦算法（IPriCF）來解決基于近鄰的協同過濾推薦算法中的隱私問題，在后面的部分，我們將首先介紹算法的總體思想，然后對我們的算法進行詳細的描述。

2.1 算法思想

差分隱私的基本思想是對原始數據的轉換或對統計結果添加噪音來達到隱私保護的效果，即保證給出總體或模糊的信息，但是不泄露個體的信息。推薦系統中的查詢往往具有較高的敏感度，所以應用差分隱私技術會引入大量的噪聲，導致數據可用性較差。假如我們以余弦相似度（COS）作為協同過濾算法中的相似度度量，一個典型的情況是兩個用戶僅僅有一個同時評分的物品，最壞的情況下，刪除這條記錄后他們的余弦相似度從1降低到0。對原數據加入滿足Lap（1/ε）分布的噪聲后，原數據的可用性將急劇降低。

定義1 （全局敏感度）對于任意一個函數f：D→Rd，函數f的全局敏感度為：

Δf = || f（D） -f（D'） ||

由定義1可知，對于函數f每條記錄的敏感度是不同的，而直接影響噪聲引入數量的全局敏感度Δf 取其中最大的值，所以，我們會對原始數據進行剪裁，裁剪掉那些“特殊”并且敏感度很大的值，降低查詢的全局敏感度，從而減少噪聲的引入。

2.2 算法描述

根據以上思想，改進的隱私保持協同過濾推薦算法描述如下：

算法1 IPriCF

輸入：用戶ua對物品ti的真實評分rai ；輸出：保證用戶隱私的預測評分ai 。

1）數據裁剪：（1）用戶評分的數量位于區間[α，β]；（2）1.2 物品被評分的次數應不小于γ。

2）隱私鄰居選擇：（1）添加Laplace噪聲，計算相似度度矩陣；（2）選擇鄰居：根據生成相似度矩陣選擇k個鄰居。

3）計算預測評分ai 。

本算法中，步驟3為標準的CF操作，我們將重點討論數據裁剪與隱私鄰居選擇部分。

數據剪裁分為兩個階段：第一階段生成用戶評分數的直方圖統計，在本階段中我們篩選出評分數量不屬于區間[α，β] 的用戶，然后在原始數據集中刪除與該用戶有關的所有評分信息；第二階段生成物品被評分數的直方圖統計，在本階段中我們篩選出被評分數量小于γ的用戶，然后在原始數據集中刪除與該物品有關的所有評分信息。

為了使被裁剪的用戶依然能得到推薦，同時又要保證其隱私，我們在計算相似度時僅與未被剪裁的用戶計算相似度，并加入Laplace噪聲；對于被裁剪用戶之間，他們的相似度為0。需要注意的是，區別于被裁剪的用戶，在計算相似度的過程中，我們將不考慮關于被裁剪物品的評分記錄。

鄰居選擇部分與標準的KNN協同過濾算法類似，我們設置參數k表示參與用戶推薦的相似用戶個數。

3 實驗與評價

3.1 實驗數據集

實驗數據集采用的是推薦領域中公認的MovieLen數據集，包含943個用戶對1682部電影共10萬條評分，每個用戶的評分數不小于20，評分為1-5。

圖1為用戶評分統計圖與物品被評分統計圖，從圖中可以看出，用戶評分次數集中在 [20， 400]這一區間，而大于400次評分的用戶僅占1.60%，物品被評分數集中在[1， 300]這一區間，僅被評分過一次的物品占8.38%。

3.2 評價標準

本文采用推薦領域中公認的均方根誤差（RMSE）作為評價標準：

RMSE=

其中r是用戶ua對物品ti的真實評分，ai是預測評分，T表示訓練數據集，|T|表示訓練數據集的大小。顯然，較低的RMSE值意味著較高的預測準度。

3.3 實驗結果與分析

將原始數據集按 80% / 20% 比例隨機分為訓練數據集與測試數據集，按相同方法分為5組互不相關訓練數據與測試數據，我們分別在數據集上應用基于近鄰的協同過濾算法，典型的使用差分隱私保護的協同過濾推薦算法與本文提出的算法，實驗的結果是在這五組數據集上的結果取均值。

在差分隱私保護中，隱私保護預算是決定隱私保護水平的一個重要指標。越小的代表著越高的隱私保護水平，同時會引入更多的噪聲。在實驗中，我們將隱私保護預算的范圍設置為[0.1，1]，將k設置為20，參考上圖統計信息，我們設置α=20，β=400，γ=2，在以上參數設置下我們將并計算在不同隱私保護水平下算法的表現。

圖 2 為相似度度量分別為余弦相似度（COS）與皮爾森相似度（PCC），基礎算法為基于物品的協同過濾算法的表現。從上圖2可以看出，隨著隱私保護預算的增加，數據的可用性增大。此外，在<0.5時，隨著的增加，RMSE值急劇下降，這表明算法要保證一個較高的隱私保護水平將帶損失較大的數據可用性，在≥0.5時，算法結果變化趨于平緩，這表明算法在一般的隱私保護需求下能在數據可用性與隱私保護水平中取得一個良好的折衷。

4 結束語

隱私保護是推薦系統中一個非常具有挑戰的問題：一方面，為了提供更好的用戶體驗，需要不斷提升推薦的準確度；另一方面，精準的推薦會暴露用戶的隱私信息，這會導致用戶失去對推薦系統的信任。所以，提升推薦系統的準確度與為用戶提供隱私保證同等重要。差分隱私保護技術有著嚴格的數學證明，能夠保證其處理結果的可信度等優點。本文在應用差分隱私保護技術的隱私保持協同過濾算法的基礎上，根據隱私保護程度對用戶與物品進行裁剪，從而大量減少了噪聲的引入。同典型的差分隱私保護下的協同過濾算法相比，該算法在保證用戶隱私的前提下提升了推薦的準確度。同類似的改進型研究相比，該算法與已有的研究成果能較好的結合，同時能夠很好的利用傳統推薦領域的研究成果。

在后續研究中，將研究數據剪裁程度通隱私保護預算與算法推薦準確度之間的關系，以進一步的提升算法的準確度。

參考文獻

[1] N.Ramakrishnan， B.J. Keller， B.J. Mirza， A.Y. Grama， G. Karypis，Privacy risks in recommender systems， IEEE Internet Computing 5 （6） （2001） 54-62.

[2] A.Narayanan， V. Shmatikov， How to break anonymity of the netflix prize dataset， CoRR abs/ cs/0610105.

[3] Narayanan， V. Shmatikov， Robust de-anonymization of large sparse datasets， in： Proceedings of the 2008 IEEE Symposium on Security and Privacy， SP08， IEEE Computer Society， Washington， DC， USA， 2008， pp. 111-125.

[4] J.A. Calandrino， A. Kilzer， A. Narayanan， E.W. Felten， V. Shmatikov， ‘‘You might also like： privacy risks of collaborative filtering， in： Proceedings of the 2011 IEEE Symposium on Security and Privacy， SP11， IEEE Computer Society， Washington， DC， USA， 2011， pp. 231-246.

[5] Dwork， Differential privacy， in： ICALP06： Proceedings of the 33rd Inter- national Conference on Automata， Languages and Programming， Springer- Verlag， Berlin， Heidelberg， 2006， pp. 1-12.

[6] G.Adomavicius， A.Tuzhilin， Toward the next generation of recommender systems： a survey of the state-of-the-art and possible extensions， IEEE Transactions on Knowledge and Data Engineering 17 （6） （2005） 734-749.

作者簡介：

王彤（1990-），男，四川南充人，畢業于重慶大學，重慶大學讀研，碩士；主要研究方向和關注領域：推薦系統、隱私保護。

黃樹斌（1991-），男，江西宜春人，畢業于重慶大學，重慶大學讀研，碩士；主要研究方向和關注領域：社交網絡、隱私保護。