协同过滤推荐算法稳定性研究

荆常春 李亚茹 郭强 刘建国

摘要 协同过滤推荐算法应用广泛，容易遭到外来系统攻击。用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.