協同過濾推薦算法穩定性研究

荊常春 李亞茹 郭強 劉建國

摘要 協同過濾推薦算法應用廣泛，容易遭到外來系統攻擊。用9種相似度指標計算用戶相似度，研究協同過濾推薦算法在遭受攻擊時的穩定性。實證結果表明：在惡意打分時，相似度指標中改進的熱傳導相似度指標比其它相似度指標的推薦結果穩定，而皮爾森（Pearson）系數和公共鄰居（Common Neighbor）的表現非常不穩定；在隨機連邊中，相似度指標LeichtHolmeNewman （LHN）的推薦結果非常穩定，而其它相似度指標則表現非常不穩定。研究結果表明用戶的相似度度量對于協同過濾推薦算法至關重要。

關鍵詞 協同過濾；相似度指標；惡意打分；隨機連邊

DOI DOI： 10.11907/rjdk.162367

中圖分類號： TP311

文獻標識碼： A 文章編號 文章編號： 16727800（2017）002003903

0 引言

協同過濾推薦算法在商業網站中得到了廣泛應用[13]。該方法基于用戶的歷史數據計算用戶或產品的相似度進行個性化推薦。在電影推薦網站中，一個用戶如果觀看了某部電影，則該用戶就可以對該電影進行打分，然而這些打分可能會影響其它用戶的抉擇[4]。在線網絡系統每天都會面臨來自各種攻擊，導致產品的打分信息不一定真實。例如，某些用戶可能因為對該產品不熟悉而給予不合理打分，有些甚至可能是 “黑客”，惡意打分[5，6]。對在線用戶而言，穩定的推薦結果是推薦算法的重要目標。

目前，在推薦算法穩定性方面有諸多研究。Bhaskar Mehta[7]提出了一種基于矩陣分解的算法（Matrix Factorization algorithm）來解決推薦算法中的隨機均值打分攻擊問題，此種算法計算復雜度高，對于用戶過多的系統具有局限性。此外，周濤等[8，9]基于關聯聲譽和組織聲譽提出了在線系統面對攻擊時穩定的兩種排序算法。侯磊等[10]研究了多種相似度指標的穩定性問題，同時為用戶相似度的計算提供了多種方法。然而，大多數學者專注于算法的優化和改進，并沒有從用戶相似度的角度衡量推薦算法的穩定性。

本文主要研究九種相似度指標在兩種攻擊下的穩定性問題。實證結果表明，在惡意打分攻擊中，推薦算法在LHN指標和改進的熱傳導（Improved Heat Conduction）指標表現較其它指標更為穩定。特別，當惡意打分概率，推薦列表長度時，LHN指標的推薦準確性比皮爾森（Pearson）指標準確53%，比公共鄰居（Common Neighbor）指標準確55%。

1 推薦算法以及相似度指標

1.1 協同過濾算法

協同過濾算法是根據與目標用戶選擇和打分行為相似的用戶集合來預測目標用戶喜好的產品。首先計算目標用戶與其他用戶的相似度，選取與該目標用戶最相似的用戶作為 “好友”，去除目標用戶已經選擇過的產品，將 “好友”選擇過的剩余產品生成推薦列表推薦給目標用戶。

“好友”選擇的產品決定了目標用戶推薦列表的內容，所以確定“好友”是算法的重要步驟。衡量用戶之間的相似度是決定推薦算法優劣的關鍵。本文分別用了九種相似度指標來計算用戶的相似度。

計算用戶相似度后對“好友”選擇過的產品（去除目標用戶選擇過的產品）進行預測打分，定義用戶對產品的預測打分Pred（o）為：

其中，sαβ代表相似度指標，rβo表示用戶對產品的打分，rβ 表示用戶對所有產品評分的平均分。對所有被預測打分的產品將按降序排列，選取排名前L個產品作為目標用戶的推薦列表。

1.2 9種相似度指標

相似度指標是用來衡量兩個用戶之間的相似程度，9種指標如下：

基于用戶歷史打分的指標有兩種：Pearson Coefficient （PC）指標[10，11]和 Cosine Index （CI）指標[10，12]，其公式定義為：

其中，Oαβ是用戶α和用戶β共同選擇產品的集合，rα 和rβ 是用戶α和用戶β對各自所選產品打分的均值，向量rα和rβ分別表示用戶α和用戶β所選共同產品的打分向量。

此外，當用戶的歷史打分信息不可獲取時，用戶相似度還可以依據用戶和產品的度信息來衡量，例如公共鄰居Common Neighbor （CN）指標，其定義為：

2 兩種攻擊模式介紹

首先，構建包含 n 個用戶、 m 個產品和 l 條連邊的用戶——產品二部分網絡：包含用戶構成的集合U={u1，u2，…un}和產品構成的集合O={o1，o2，…om}，建立用戶和產品之間的連邊E={e1，e2，…el}。

本文用兩種攻擊模式測試推薦算法的穩定性，惡意打分來自于惡意用戶或者測試工程師隨機抽取數據，從{1，2，3，4，5}中打分；另一種攻擊是隨機連邊，測試者隨機連邊來擾亂數據結構，即：隨機選擇一條記錄μ-o-r，然后從剩余的產品中隨機選擇產品o'，生成一條新的記錄μ-o'-r，但打分不變。定義惡意打分或者隨機連邊在數據集中的比例為p=l'/l，其中l'為遭受攻擊的記錄數量， p 的取值范圍為[0，1]。

3 實驗結果

3.1 數據介紹

本文基于兩個真實網絡的數據集Movielens和Netflix來研究推薦算法的穩定性（見表1），兩個數據集均采用5分制來打分。 n ， m ， l 分別為用戶個數、產品個數、連邊數，其中表示數據集的稀疏度，即s=l/（m×n）。

3.2 評價指標

為了比較攻擊前后推薦列表的變化，本文提出了前L項交叉距離（topL intersection distance）評價指標[22]，公式為：

其中，Δ表示兩個集合的對稱差分算子，即并集個數與交集個數之差，xL和yL表示前L個產品的排序列表。如果兩個列向量完全相同，那么τL（x，y）=0；如果完全不同，則τL（x，y）=1。兩個列向量的相似程度越大時，τL反而越小。為了計算整體的差異性，作一個簡單平均，即平均交叉距離τ =∑τ/n。因此，可以用平均交叉距離τ 衡量原始列表與測試列表之間的差異。

3.3 結果分析

本文通過兩種攻擊模式和9種相似度指標探究了推薦算法在遭受攻擊時的穩定性，推薦列表長度定義為L=3，L=10，L=20，“好友”個數Nu=20。

首先分析惡意打分對推薦算法穩定性的影響。以概率 p 從數據集中隨機選取記錄給予打分，重新計算推薦列表。實驗結果如圖1所示，橫軸為惡意打分比例，縱軸為平均交叉距離τ ，平均交叉距離τ 與惡意打分比例 p 呈明顯正相關關系。此外，在每個子圖中相似度指標τ LHN和τ IHC均小于其它指標，當取推薦列表長度L=20、惡意打分比例p=0.1時，在Netflix數據集上τ LHN=0.227 3，τ IHC=0.328 4；在Movielens數據集上，τ LHN=0.251 8，τ IHC=0.228 7。指標IHC用于推薦時穩定性比PC高53.7%，比CN高55.4%；而指數PC和CN進行推薦時效果最差，當p=0.4時，τ PC和τ CN接近0.9，說明此時推薦列表幾乎全部紊亂；推薦列表為L=3和L=10時都有相似的表現特征。此外，從圖1中還可以看出，指標HDI、SAL、SOR和JAC在每個子圖中具有幾乎相同趨勢，該現象可能由于它們的公式定義相似。

另外一種攻擊模式是隨機連邊，選取一定比例的記錄重新連接。如圖2所示，在Movielens數據集上，當推薦列表長度L=3，L=10，L=20時τ LHN分別為0.580 5，0.555 8，0.532 4，要比其它指標小得多。當p=0.3時，各個子圖中其它指標值接近0.9，說明即使遭到更多攻擊，LHN指標用于推薦時要比其它指標穩定得多。就隨機連邊而言，LHN指標可以使推薦算法更為穩定。

4 結語

協同過濾算法作為個性化推薦算法中非常高效的方法之一，研究其遭遇攻擊時的穩定性至關重要。本文在兩個數據集上測試了協同過濾推薦算法在遭受惡意打分和隨機連邊攻擊時的表現，對比攻擊前后推薦列表的變化。實證結果表明，在推薦長度和攻擊比例改變的情況下指標LHN仍能進行穩定推薦，特別當攻擊比例，推薦列表長度時，其推薦準確性比皮爾森系數穩定53%，比公共鄰居指標穩定55%。

本文基于兩種常見的隨機攻擊模式研究了協同過濾推薦算法的穩定性問題。但攻擊模型的發展甚至要比防御系統發展快，不同攻擊模型下的穩定性問題還需要不斷深入探究。推薦系統隨時面臨著未知的攻擊風險，如何使推薦算法在遭受攻擊時也能穩定地推薦需深入研究。

參考文獻：

[1] LU L， MEDO M， YEUNG C H， et al. Recommender systems[J]. Physics Reports， 2012， 519（1）： 149.

[2] GUO Q， SONG W J， LIU J G. Ultraaccurate collaborative information filtering via directed user similarity[J]. EPL （Europhysics Letters）， 2014， 107（1）： 18001.

[3] 王孟頔， 邰泳， 薛安榮. 基于 Hadoop 平臺的人才發現與推薦系統研究[J]. 軟件導刊， 2014， 13（1）： 46.

[4] 宋文君， 郭強， 劉建國. 一種改進的混合推薦算法[J]. 上海理工大學學報， 2015， 37（4）： 327331.

[5] 劉建國， 周濤， 郭強， 汪秉宏. 個性化推薦系統評價方法綜述[J]. 復雜系統與復雜性科學， 2009， 6（3）： 110.

[6] 石珂瑞， 劉建國. 二階有向相似性對協同過濾算法的影響[J]. 上海理工大學學報， 2014， 36（1）： 3133.

[7] MEHTA B， HOFMANN T， NEJDL W. Robust collaborative filtering[C].Proceedings of the 2007 ACM conference on Recommender systems. ACM， 2007： 4956.

[8] ZHOU Y B， LEI T， ZHOU T. A robust ranking algorithm to spamming[J]. EPL （Europhysics Letters）， 2011， 94（4）： 48002.

[9] GAO J， DONG Y W， SHANG M S， et al. Groupbased ranking method for online rating systems with spamming attacks[J]. EPL （Europhysics Letters）， 2015， 110（2）： 28003.

[10] LIU J G， HOU L， PAN X， et al. Stability of similarity measurements for bipartite networks[J]. Scientific reports，2016.

[11] HERLOCKER J， KONSTAN J A， RIEDL J. An empirical analysis of design choices in neighborhoodbased collaborative filtering algorithms[J]. Information retrieval， 2002， 5（4）： 287310.