Figure 1
基于协同谱聚类的推荐系统托攻击防御算法
引用本文
杨欐, 钮心忻, 黄玮. 基于协同谱聚类的推荐系统托攻击防御算法[J]. 北京邮电大学学报, 2015, 38(6): 81-86. 
YANG Li, NIU Xin-xin, HUANG Wei. Shilling Attack Defense Algorithm for Recommender System Based on Spectral Co-Clustering[J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOMMUNICATIONS, 2015, 38(6): 81-86.
Permissions
Copyright©2015, 《北京邮电大学学报》编辑部
《北京邮电大学学报》编辑部 所有
基于协同谱聚类的推荐系统托攻击防御算法
1. 北京邮电大学 计算机科学与技术学院, 北京 100876;
2. 中国传媒大学 计算机学院, 北京 100024
2. 中国传媒大学 计算机学院, 北京 100024
摘要
提出了一种基于协同谱聚类的推荐系统托攻击防御算法. 该算法首先使用谱聚类方法对协同聚类算法进行改进,以在用户和项目2个维度上同时进行聚类;接着在聚类基础上结合分级偏离平均度对用户进行项目推荐. 实验测试结果表明,在同等托攻击规模的情况下,该算法可以降低实施托攻击的用户和攻击数据对系统推荐结果的影响.
关键词:
协同谱聚类 分级偏离平均度 托攻击 推荐系统
中图分类号: TP301 文献标志码:A 文章编号:1007-5321-38-6-81 DOI:10.13190/j.jbupt.2015.06.017
Shilling Attack Defense Algorithm for Recommender System Based on Spectral Co-Clustering
1. School of Computer Science and Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China;
2. School of Computer Science, Communication University of China, Beijing 100024, China
2. School of Computer Science, Communication University of China, Beijing 100024, China
Abstract
An algorithm for recommender system based on spectral co-clustering was proposed to defend shilling attacks. The proposed algorithm maintains spectral clustering and co-clustering priors and allows a mixed membership in user and item clusters. The rating deviations were used for mean agreement based on the co-clustering results to recommend for users. Experimental results demonstrated that under the same shilling attack dimensions, our algorithm could decrease the shilling attack affects to recommender systems apparently.
Key words:
spectral co-clustering rating deviation from mean agreement shilling attack recommender system
0 引言
其中D为度数矩阵，此时将原聚类问题转化为求以下目标函数的最小值：
其中：Ai(i=1,2,…,k)为第i个分组，${\bar A_i}$为其补集．
其中：左奇异向量U表征对行维度的聚类结果，右奇异向量Q表征对列维度的聚类结果.
其中：Ru为用户u总共评价过的项目个数，Rui为用户u对项目i的评分，${\bar R_i}$为系统中所有用户对项目i的评分均值，Ri为项目i在系统中被评价过的总次数. 既然攻击者的目的是影响目标项目的评分，不论是抬高还是打压评分值，攻击用户都会较其他正常用户有更大的偏差值.
协同过滤方法是当前推荐系统中使用最为广泛的推荐方法之一，但该方法是根据用户概貌信息进行推荐的，已有研究表明，推荐系统尤其是销售领域的推荐系统，用户评价会影响消费者的购买行为，有计划地干扰系统收录的用户评分也会对推荐系统使用者和公司产生明显的影响[1]. 而且即使不知道大量关于该推荐系统的实现细节或算法、仅使用小规模的攻击数据，也能够对系统造成明显的干扰[2]. 攻击者向推荐系统注入具有某种特征的虚假用户信息，使用这些虚假用户数据影响和改变推荐系统的正常推荐结果的行为，称为托攻击[2]. 不同的攻击方式，生成攻击数据的方法不同，对推荐系统的攻击效果也不同[3]. 常见的攻击类型包括随机攻击、均值攻击和造势攻击等.
将聚类算法与托攻击检测模型相结合以提高托攻击检测的效率和准确率也是近年来热门的研究方向之一[4]. 但这些方法均只是针对简单的攻击方式进行了攻击检测的测试，对于实际中较多使用的多种基础托攻击手段结合的高级托攻击行为的检测则有一定的局限性. 而托攻击的多样性与隐蔽性[5]使得现有的托攻击防御算法具有以下局限性：① 仅对单一或某些托攻击行为有效，对复合的或较复杂的托攻击方式，其检测效果较差；② 智能程度有限，即需要预先输入较多的关键参数或需要知道较多的先验知识.
为减小托攻击对推荐系统推荐结果的影响，提高协同推荐系统对托攻击行为的防御效果，笔者提出了一种结合用户评分偏离度的协同谱聚类(CO-SC,spectral co-clustering)托攻击防御方法. 该算法首先结合时间因素，利用项目评分的变化规律和用户评分偏离度对异常的评分波动进行检测；然后基于谱聚类(SC,spectral clustering)算法对CO-SC算法进行改进，通过CO-SC方法同时对用户和项目进行聚类，在聚类基础上对同类的用户和项目进行推荐，以进一步提高系统推荐的准确性. 由于单一的随机攻击和均值攻击较容易被区分且产生的攻击效果有限，因此将随机攻击、均值攻击与造势攻击相结合，使用随机造势攻击和均值造势攻击生成攻击数据，并讨论改进模型在随机造势攻击和均值造势攻击两种攻击方式下的防御和推荐效果.
1 基于CO-SC的推荐系统托攻击防御算法 1.1 理论基础 1.1.1 SC算法SC算法具有能在任意形状的样本空间上聚类且收敛于全局最优解和较好的健壮性与较低的算法复杂度的优点. 该算法的本质是将聚类问题转化为图的最优划分问题[6]：将每个对象看作是图的顶点V，将对象的相似度作为两点连接边的权值E，最优划分准则为使分成的不同子图内部具有最大相似度，子图之间的具有最小相似度. SC算法的主要步骤如下.
1) 构建样本集的相似度矩阵W=[Wi,j]n×m，其中为用户i和用户j的相似度，也可以看作是图G(V,E)中节点i与节点j连接边的权值.
2) 计算归一化的拉普拉斯矩阵：
| $L = D - W$ | (1) |
| ${\text{cut}}\left( {{A_1},{A_2} \cdots {A_k}} \right) = \frac{1}{2}\sum\limits_{i = 1}^k {W\left( {{A_i},\overline {{A_i}} } \right)} $ | (2) |
3) 计算L的最小的k个特征值和对应的特征向量.
4) 根据每个数据点的k维空间坐标，使用K-means或其他聚类算法在k维空间对数据进行聚类.
该算法中步骤3)所需时间最长，使用ARPACK计算时，时间复杂度为
(O(m3)+(O(nm)+O(nt))× O(m－k))(#restartArnoldi)[7]
1.1.2 协同聚类算法协同聚类也叫二部聚类，该算法实质上是运用图的双向划分原则对二部图的行、列2个维度同时进行迭代聚类直至收敛的过程. 假设推荐系统中共有n个用户和m个项目，则用户-项目特征矩阵为A={ai,j}nm，其中ai,j为用户i对项目j的评分值. 基于特征矩阵A构造如下对角矩阵：
| ${D_1}\left( {i,j} \right) = \sum\limits_j^m {{A_{ij}}} $ | (3) |
| ${D_2}\left( {i,j} \right) = \sum\limits_j^n {{A_{ij}}} $ | (4) |
拉普拉斯矩阵定义为
| $L = \left( \begin{gathered} {D_1} - A \hfill \\ - {A^T}{D_2} \hfill \\ \end{gathered} \right)$ | (5) |
进行协同聚类的步骤如下：
1) 对于给定的特征矩阵A，计算
| ${A_n} = {D_1}^{ - \frac{1}{2}}A{D_2}^{ - \frac{1}{2}}$ | (6) |
2) 计算An的前$l = \left\lceil {1{\text{b}}k} \right\rceil $个最大的不为1的奇异值对应的左右奇异向量U=(u2,u3,…,ul+1)和Q=(q2,q3,…,ql+1)生成如下降维后的特征向量空间：
| $Z = \left( \begin{gathered} {D_1}^{ - \frac{1}{2}}U \hfill \\ {D_2}^{\frac{1}{2}}Q \hfill \\ \end{gathered} \right)$ | (7) |
3) 使用K-means方法对经过步骤2)后降维的特征向量空间Z进行聚类，计算最后的聚类结果.
1.2 CO-SC托攻击防御算法 1.2.1 算法描述笔者提出了一种结合分级偏离平均度(RDMA,rating deviation from mean agreement)的CO-SC托攻击防御算法. 使用RDMA将用户的打分频率、项目被评价频率与用户概貌相适度相结合，该值表示用户u对项目i的评价与其他用户对该项目评价的偏离程度：
| ${R_{{\text{user}}}} = \frac{{\sum\limits_{i = 0}^{{R_u}} {\frac{{\left| {{R_{ui}} - {{\bar R}_i}} \right|}}{{{R_i}}}} }}{{{R_u}}}$ | (8) |
所提出的CO-SC方法是一种结合SC方法对协同聚类算法的优化实现. 由于在实际应用中，所使用的推荐系统大都可统计为一个用户-项目评分评分矩阵，该矩阵是一个典型的二部图. 对于用户-项目评分矩阵，仅对行或列单一维度进行相关性聚类都会丢失另一维度的信息. 而协同聚类算法可以将基于用户的推荐方法与基于项目的推荐方法结合，这样不仅能够提高推荐的准确度，同时对攻击者生成攻击数据的要求更高，使推荐系统具有更好的鲁棒性.
对于一个有m个评分项目n个用户的推荐系统，使用向量空间模型将其抽象为一个m×n的用户-项目矩阵，记为A，构造关于A的二部图：
| $G = \left( \begin{gathered} A0 \hfill \\ 0{A^T} \hfill \\ \end{gathered} \right)$ | (9) |
G为(m+n)×(m+n)的对称矩阵，将其作为CO-SC的特征矩阵，在此基础上计算系统样本集的相似度矩阵W. 由于在二部图G中只有项目-用户的连接边，在用户-用户和项目-项目之间没有连接边，使用CO-SC算法在聚类时会保持切割边的权值最小，同时使形成的子图内部的关联性最强. 通过SC算法提高普通协同聚类计算降维特征向量空间的效率和准确性，在协同聚类的基础上对同一类别的用户和项目进行推荐，将托攻击的攻击效果分散，以达到抵御托攻击的目的.
1.2.2 算法步骤为了减少托攻击用户被纳入相似用户 (以下简记为SimUser)集合的概率，同时降低托攻击行为对系统推荐结果的影响，采用RDMA值结合CO-SC的方法，其算法步骤如下.
第1阶段：使用CO-SC算法进行聚类.
输入： 托攻击用户数据的系统评分矩阵、聚类数k.
输出： k个类别分别对应的用户和项目集合.
1) 根据式(9)生成二部图矩阵G(m+n)×(m+n)；
2) 计算G的相似度矩阵W(m+n)×(m+n)；
3) 根据式(1)计算归一化的拉普拉斯矩阵L，计算前$\left\lceil {1{\text{b}}k} \right\rceil $个最大的不为1的奇异值对应的左右奇异向量U、V；
4) 根据式(7)生成降维特征向量空间Z；
5) 使用K-means算法对Z进行聚类，得出用户和项目所对应的类别.
第2阶段： SimUser集合计算、项目推荐.
输入： 评分矩阵和k个聚类分别对应的用户和项目集合.
输出： 用户对应的SimUser集合和推荐项目列表.
1) 根据式(8)计算每个用户的RDMA值；
2) 在聚类的基础上，根据Pearson相关系数计算在同一聚类集合中每个用户最为相似的M个用户，相关公式为
| $\begin{gathered} {\rho _{X,Y}} = \frac{{\operatorname{cov} \left( {X,Y} \right)}}{{{\sigma _X}{\sigma _Y}}} = \frac{{E\left( {X - {\mu _X}} \right)\left( {Y - {\mu _Y}} \right)}}{{{\sigma _X}{\sigma _Y}}} = \hfill \\ \frac{{E\left( {XY} \right) - E\left( X \right)E\left( Y \right)}}{{\sqrt {E\left( {{X^2}} \right) - {E^2}\left( X \right)} \sqrt {E\left( {{Y^2}} \right) - {E^2}\left( Y \right)} }} \hfill \\ \end{gathered} $ |
3) 取前m个RDMA值较小的用户组成不同用户的SimUser集合；
4) 使用基于用户的基本协同推荐算法得出所有用户的N个推荐项目集合.
2 实验测试 2.1 实验步骤以一个m个用户(包括攻击用户)和n个项目的系统为例，算法效果的测试方法如下.
1) 构建m×n的原始评分数据矩阵A；
2) 使用1.2节中描述的CO-SC方法对A的行(用户)和列(项目)两个维度同时进行聚类，使用自适应的方法计算选取聚类的类别数；
3) 对不同聚类集合内的用户，根据Pearson相关系数计算每个用户最为相似的20个用户；
4) 取前15个RDMA值较小的用户组成对应的SimUser集合；
5) 使用协同推荐算法得出对每个用户的推荐项目列表；
6) 统计攻击用户被纳入SimUser集合的次数；
7) 统计攻击目标项目被推荐的次数.
2.2 测试数据 2.2.1 测试数据集使用明尼苏达大学GroupLens小组收集整理的MovieLens 100k(http://movielens.umn.ed)数据集作为测试数据集，该数据集包含了电影网站MovieLens的943位用户对1682部电影的1万条评分数据. 每条评分为1~5的整数，且每个用户都至少对20部电影进行了评分.
2.2.2 托攻击数据首先做如下定义.
攻击规模：Fa=fu/M，其中fu为系统中恶意用户的数量，M为原推荐系统中所有用户的数量.
数据注入规模：Pf=nf/N，其中nf为系统中注入的攻击用户评价数据条数，N为原推荐系统中所有用户评价数据条数.
假设MovieLens数据集中均为正常用户数据，通过实验验证在Fa为10%，Pf分别为3%、5%、10%和15%的情况下，系统对随机造势攻击和均值造势攻击的防御效果. 实验使用的托攻击数据由攻击目标电影评分、填充的热门电影评分和填充的伪装电影评分3部分组成. 其中填充的热门电影评分为数据集中被评分次数最多的前200部热门电影中随机选出的电影，每个攻击用户的虚假评分数据中热门电影的填充率分为50%、60%、70%、80%和90%这5种情况.
3 实验结果如图 1所示，在Fa为10%，Pf分别为3%、5%、10%和15%这4种情况下，采用50%、60%、70%、80%和90%这5种不同的热门电影填充率生成攻击数据对系统进行托攻击，并对攻击用户被纳入SimUser集合的次数进行了统计. 图 1中CF(collaborative filtering)曲线表示使用基本的协同过滤算法；SC曲线表示先使用SC算法再对同一聚类集合中的用户使用协同过滤算法后进行推荐；CO-SC曲线表示基于CO-SC算法在系统中注入托攻击数据后，对系统中原有用户进行推荐时攻击用户被纳入SimUser集合的次数.
|
图1 托攻击用户被纳入SimUser集合的次数 |
从图 1可以看出，在Fa和Pf相同的情况下，随着热门电影填充率的增加，当系统使用CF和SC算法时，SimUser集合中攻击用户出现的总次数整体呈现增加的趋势. 可见热门电影的填充率越高，攻击的效果越好. 另一方面，由于恶意的托攻击用户被纳入SimUser集合的次数越少，系统对托攻击的防御效果越好. 而在Fa和Pf相同的情况下，使用CO-SC算法时，将攻击用户错误地纳入SimUser的总次数要明显少于使用CF和SC算法的情况. 在Pf=3%和Pf=5%的情况下，随着热门电影填充率的增加，使用CO-SC算法时攻击用户在SimUser集合中出现的总次数反而减少了；在Pf=10%和Pf=15%的情况下，出现次数随热门电影填充率的增加的变化并不明显，可见所提出的CO-SC算法可以明显改善推荐系统对托攻击的抵御效果.
对于目的为抬高目标项目的评分或大幅增加目标项目被推荐给用户的次数的托攻击，抵御该攻击的其中一个效果即为保证推荐结果的正确性和稳定性，即系统不会出现在注入攻击数据后，给系统中原有用户进行推荐的结果有明显的变化，以至于托攻击的目标项目TargetItem被推荐的次数突然增加. 图 2从托攻击有目的地提高评分的电影TargetItem被推荐的次数的角度对3种方法进行了比较. 以Fa=10%为基础，向系统中注入Pf分别为5%、10%和15%的托攻击数据，统计在这3种攻击模式下使用CF、SC和CO-SC这3种算法对用户进行推荐后，TargetItem被推荐给系统中原有用户的次数.
|
图2 托攻击的TargetItem被推荐给用户的次数 |
图 2的对比结果更明确的展示出该算法能同时有效地降低被攻击用户有意提升(或降低)的项目在推荐时的被推荐次数和权重.
图 3对攻击前后TargetItem(ID为300)的项目被推荐给用户的次数进行了比较. 图 3中无攻击曲线表示向系统中注入托攻击数据时ID为300的项目被推荐给用户的次数，可视为基线. CF和CO-SC曲线分别表示对应的两种算法在Pf=10%且Fa=10%时，将不同热门电影填充率的托攻击数据注入推荐系统后ID为300的电影被推荐给用户的次数. 从图 3中可以看出，使用简单的协同推荐算法在系统被注入托攻击数据后TargetItem被推荐给用户的次数会明显增多，相对地，所提出的CO-SC算法则会略微减少该项目被推荐的次数. 出现这种结果可能是因为CO-SC算法先将用户进行了聚类，在降低攻击用户对正常用户推荐结果的影响的同时也在一定程度上降低了原有用户对未被聚为同一类的用户的影响. 但减少的次数并不多，尚在正常波动范围之内.
|
图3 注入攻击数据前后TargetItem被推荐次数的比较 |
结合图 1~图 3的结果，实验证明结合用户RDMA值的CO-SC算法在一定程度上能更好地抵御有效的托攻击对系统的攻击，保证系统推荐的正确性和合理性.
4 结束语提出了一种结合RDMA值的基于CO-SC的推荐系统托攻击防御算法，该算法使用SC算法对用户和项目两个维度进行协同聚类后，再对同一类别内的用户计算SimUser进而进行项目的推荐. 该防御算法将托攻击用户的攻击效果进行了分散，并结合RDMA值一定程度上将可疑的用户排除到SimUser集合之外. 因此能显著地减少托攻击用户数据在系统进行推荐时出现的次数，同时也明显降低了被托攻击提升的项目的推荐次数.
然而传统的SC方法也有其不足，即算法的时间复杂度较高，因其需要涉及计算矩阵的特征值分解问题时间复杂度为O(n3)[8]，其中n为所作聚类的数据集的大小. 所提出的CO-SC算法是在协同聚类的基础上再进行SC，因此n的值小于整体实验数据N值，但在算法复杂度上还有进一步的改进空间. 接着考虑到对用户的推荐效果，对用户和项目同时进行协同聚类后由于一个用户和一个项目只能归属于一个类别，将会一定程度地带来原始数据信息的损失和聚类准确性的降低. 所提出的CO-SC算法虽然很好地对托攻击行为进行了抵御，但对于推荐的效果也要更好地保证，因此采用更为灵活的协同聚类方法，并引入用户评分权值进一步改善推荐和托攻击检测效果，同时提高算法的效率将是下一步研究的方向.
参考文献
| [1] | Chevalier J A, Mayzlin D. The effect of word of mouth on sales: online book reviews[J]. Journal of Marketing Research, 2006, 43(3): 345-354.[引用本文:1] |
| [2] | O'Mahony M, Hurley N, Kushmerick N, et al. Collaborative recommendation: a robustness analysis[J]. ACM Transactions on Internet Technology (TOIT), 2004, 4(4): 344-377.[引用本文:2] |
| [3] | Lam S K, Riedl J. Shilling recommender systems for fun and profit[C]//Proceedings of the 13th international conference on World Wide Web. (2004) ACM Press: New York, 2004: 393-402.[引用本文:1] |
| [4] | Abas A R. On determining efficient finite mixture models with compact and essential components for clustering data[J]. Egyptian Informatics Journal, 2013, 14(1): 79-88.[引用本文:1] |
| [5] | Li Cong, Lu Zhigang. Detecting shilling attacks in recommender systems based on non-random-missing mechanism[J]. Acta Automatica Sinica, 2013, 39(10): 1681-1690.[引用本文:1] |
| [6] | Von Luxburg U. A tutorial on spectral clustering [J]. Statistics and Computing, 2007, 17(4): 395- 416.[引用本文:1] |
| [7] | Chen Wenyen. Parallel spectral clustering in distributed systems[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2011, 33(3): 568-586.[引用本文:1] |
| [8] | Xu Sen, Lu Zhimao, Gu Guochang. Spectral clustering algorithms for document cluster ensemble problem[J]. Journal on Communications, 2010 (6): 58-66.[引用本文:1] |