王彤　黃樹斌

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

【 關(guān)鍵詞 】 協(xié)同過濾（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等人首次提出在推薦系統(tǒng)中的隱私問題，Narayanan等人通過聯(lián)合Netflix與IMDB的發(fā)布數(shù)據(jù)集成功的標(biāo)識出部分戶。Calandrino等人通過觀察推薦系統(tǒng)一段時間內(nèi)推薦結(jié)果的變化，結(jié)合背景知識推斷出某用戶的歷史評分與行為。

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

很多學(xué)者就差分隱私在推薦系統(tǒng)中的應(yīng)用提出不同的方法，在隱私保護與推薦的準(zhǔn)確性方面均取得了不錯的效果，但仍有許多局限性，它們主要表現(xiàn)在兩個方面。

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

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

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

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

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

2.1 算法思想

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

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

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

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

2.2 算法描述

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

算法1 IPriCF

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

1）數(shù)據(jù)裁剪：（1）用戶評分的數(shù)量位于區(qū)間[α，β]；（2）1.2 物品被評分的次數(shù)應(yīng)不小于γ。

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

3）計算預(yù)測評分ai 。

本算法中，步驟3為標(biāo)準(zhǔn)的CF操作，我們將重點討論數(shù)據(jù)裁剪與隱私鄰居選擇部分。

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

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

鄰居選擇部分與標(biāo)準(zhǔn)的KNN協(xié)同過濾算法類似，我們設(shè)置參數(shù)k表示參與用戶推薦的相似用戶個數(shù)。

3 實驗與評價

3.1 實驗數(shù)據(jù)集

實驗數(shù)據(jù)集采用的是推薦領(lǐng)域中公認(rèn)的MovieLen數(shù)據(jù)集，包含943個用戶對1682部電影共10萬條評分，每個用戶的評分?jǐn)?shù)不小于20，評分為1-5。

圖1為用戶評分統(tǒng)計圖與物品被評分統(tǒng)計圖，從圖中可以看出，用戶評分次數(shù)集中在 [20， 400]這一區(qū)間，而大于400次評分的用戶僅占1.60%，物品被評分?jǐn)?shù)集中在[1， 300]這一區(qū)間，僅被評分過一次的物品占8.38%。

3.2 評價標(biāo)準(zhǔn)

本文采用推薦領(lǐng)域中公認(rèn)的均方根誤差（RMSE）作為評價標(biāo)準(zhǔn)：

RMSE=

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

3.3 實驗結(jié)果與分析

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

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

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

4 結(jié)束語

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

在后續(xù)研究中，將研究數(shù)據(jù)剪裁程度通隱私保護預(yù)算與算法推薦準(zhǔn)確度之間的關(guān)系，以進一步的提升算法的準(zhǔn)確度。

參考文獻

[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-），男，四川南充人，畢業(yè)于重慶大學(xué)，重慶大學(xué)讀研，碩士；主要研究方向和關(guān)注領(lǐng)域：推薦系統(tǒng)、隱私保護。

黃樹斌（1991-），男，江西宜春人，畢業(yè)于重慶大學(xué)，重慶大學(xué)讀研，碩士；主要研究方向和關(guān)注領(lǐng)域：社交網(wǎng)絡(luò)、隱私保護。