王彤　黃樹(shù)斌

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

【 關(guān)鍵詞 】 協(xié)同過(guò)濾（CF）；差分隱私保護(hù)；安全

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

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

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

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

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

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

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

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

2.1 算法思想

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

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

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

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

2.2 算法描述

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

算法1 IPriCF

輸入：用戶ua對(duì)物品ti的真實(shí)評(píng)分rai ；輸出：保證用戶隱私的預(yù)測(cè)評(píng)分ai 。

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

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

3）計(jì)算預(yù)測(cè)評(píng)分ai 。

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

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

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

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

3 實(shí)驗(yàn)與評(píng)價(jià)

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

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

RMSE=

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

3.3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

4 結(jié)束語(yǔ)

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

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

參考文獻(xià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.

作者簡(jiǎn)介：

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

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