一种利用半监督Fisher判别分析检测推荐攻击的方法

武锦霞，周全强，段亮亮

(青岛理工大学 信息与控制工程学院，山东 青岛 266525)

1 引 言

随着大数据时代的到来，信息过载问题越来越严重.协同推荐系统(Collaborative Recommender System)能够依据用户概貌(User Profile)主动地为用户推送感兴趣的信息，成为解决信息过载问题的有效途径之一，在电子商务、社交网络、多媒体服务等领域有着广泛的应用[1].

然而，大量研究表明，协同推荐系统易遭受推荐攻击(Recommendation Attack)[2,3].在这种攻击中，恶意用户出于商业竞争等目的，通过向协同推荐系统注入大量虚假概貌来改变推荐结果.为了与真实概貌(Genuine Profile)相区分，通常将这种虚假概貌称为攻击概貌(Attack Profile)[4].根据不同的攻击目的，一般将推荐攻击分为推攻击(Push Attack)和核攻击(Nuke Attack)，分别用于提升和降低目标项目的推荐等级[4].为了达到攻击的目的，恶意用户通常使用攻击模型(Attack Model)[4]生成攻击概貌.除了目标项目，其他一些项目也将被评分使攻击概貌看起来更接近真实概貌.常见的攻击模型包括随机攻击、均值攻击和流行攻击[5].推荐攻击的强度通常用攻击规模和填充规模来度量[5].

为了检测推荐攻击，研究者提出了很多检测方法，从机器学习的角度可以将已有方法分类3类：无监督[6-12]、有监督[13-21]及半监督检测方法[22,23].无监督检测方法一般不需要训练样本，但通常需要一定的先验知识.有监督检测方法通常利用有标签的用户概貌训练分类器对推荐攻击进行检测.半监督检测方法在利用有标签用户概貌训练分类器的同时，能够利用无标签用户概貌进一步提升分类器的性能，由于协同推荐系统往往存在大量无标签用户概貌，因此，能利用无标签用户概貌提升分类器性能成为半监督类检测方法的重要优势.然而，目前针对半监督检测方法的研究较少，且已有半监督检测方法的准确率不高.

为了提升半监督检测方法的检测性能，本文基于半监督Fisher判别分析技术提出一种推荐攻击检测方法RAD-SFDA.本文方法同时利用了从有标签用户概貌捕获的判别结构，以及从由有标签和无标签用户概貌构成的全部用户概貌捕获的全局结构，以获得最优投影向量，在新的投影空间中增加了真实概貌和攻击概貌的区分度以提升检测性能.本文的主要贡献如下：

1)利用FDA(Fisher Discriminant Analysis)技术捕获了有标签用户概貌的判别结构；利用PCA(Principal Components Analysis)技术捕获了全部用户概貌的全局结构；

2)综合上述判别结构和全局结构获得了最佳投影向量，在新的投影空间中增加了真实概貌和攻击概貌的区分度；

3)提出了一种基于半监督Fisher判别分析SFDA(Semi-supervised Fisher Discriminant Analysis)的检测算法，通过训练贝叶斯分类器对推荐攻击进行了有效检测；

4)在标准的MovieLens数据集上与相关工作进行了对比实验，验证了本文方法的有效性.

2 相关工作和背景知识

2.1 相关工作

在无监督检测方法中，Chirita等人[6]首先提出了几个基于统计的指标来检测高密度的攻击概貌.Mehta等人[7,8]利用PCA技术过滤攻击概貌，可有效检测多种类型的推荐攻击，但是，该方法假设在检测前已经知道测试集中攻击概貌的数目，这种先验知识在实际中不易获得.李聪等人[9]通过定量度量攻击概貌的群体效应构建出遗传优化的目标函数，并在遗传优化的过程中融入贝叶斯推断思想来完成对攻击概貌的检测，有效降低了无监督方法对先验知识的依赖程度.Yang等人[10]采用图挖掘算法区分真实概貌和攻击概貌，通过构造无向图和估计相似度提出一种检测方法，可检测多种类型攻击，然而，为该方法选取合适的共同评分阈值是一项有挑战性的工作.Yang等人[11]通过分析用户、项目和特殊评分的分布，联合目标项目分析和非线性聚类技术提出一种检测方法.非线性聚类技术有效提升了该方法对推荐攻击的检测性能，然而，从大量项目中确认目标项目并非易事.Zhang等人[12]假设测试集中同时包含真实概貌和攻击概貌，采用聚类技术划分真实概貌和攻击概貌到不同的簇中以识别推荐攻击，有效降低了无监督方法对先验知识的要求.无监督检测方法存在的主要问题是过度依赖先验知识，因此，如何有效降低检测方法对先验知识的依赖是该类方法面临的重要挑战之一.

在有监督检测方法中，Burke等人[13,14]通过训练kNN、C4.5和SVM3个分类器检测推荐攻击，这些分类器有较高的召回率，但准确率不高.伍之昂等人[15]提出一种特征选择算法，在已有特征的基础上选取部分作为特性属性，检测特定类型的攻击模型，与没进行特征选择之前相比，一定程度上提升了检测性能.Zhang等人[16]利用Hilber-Huang变换提取了推荐攻击的评分分布特征，在此基础上训练SVM检测推荐攻击，对高密度攻击概貌具有一定检测效果.李文涛等人[17]提出了一种基于流行度的检测算法，该算法从评分项目的流行度角度提取分类特征，进而通过训练决策树生成分类器对推荐攻击进行检测，对包括混合攻击在内的多类攻击模型具有一定的检测效果.Yang等人[18]基于重新缩放的Boosting和AdaBoost检测推荐攻击，提升了针对不平衡测试数据的检测性能.Zhou等人[19]结合Borderline-SMOTE技术和目标项目分析训练了基于SVM的分类器检测推荐攻击.该方法一般来说具有较好的检测性能，然而，由于协同推荐系统通常有大量项目，有时很难准确查找目标项目，在这种情况下，该方法的检测性能变得不稳定.Tong等人[20]提出了一种基于卷积神经网络的推荐攻击检测方法，在满足其对大量有标签训练样本需求的条件下，该方法具有一定的检测效果.Xu等人[21]提取了基于信任的用户概貌特征，在此基础上训练SVM检测推荐攻击.该方法提升了单分类器的检测性能，然而，该方法建立在正确识别目标项目的基础之上，从大量项目中确定目标项目有时难以实现.有监督检测方法虽然不需要先验知识，但只能从有标签的训练样本中学习检测模型，无法有效利用协同推荐系统中存在的大量无标签用户概貌.

半监督检测方法主要是Wu等人[22,23]的工作，他们提出了基于贝叶斯的半监督检测方法.首先利用有标签用户概貌初始化一个贝叶斯分类器，然后，利用无标签用户概貌提升分类器的性能.该方法对某些类型的推荐攻击具有较高的召回率，然而，该方法的准确率较低.如何有效提升准确率成为当前半监督检测方法面临的重要研究课题之一.

2.2 背景知识

2.2.1 Fisher判别分析FDA

FDA[24]是一种有监督的线性降维技术，利用有标签样本，通过寻找一个最佳投影向量，使得在投影空间中最大化不同类样本间离散度，同时最小化同类样本之间的离散度.

(1)

(2)

可通过优化下面的目标函数来确定FDA判别向量：

(3)

将上述优化问题转化为求解下面的广义特征值问题：

Sbt=λSwt

(4)

其中，λ表示广义特征值，t表示λ对应的广义特征向量，与FDA判别向量等价.

为便于问题描述，将Sb和Sw的定义改写为对等表达形式：

(5)

(6)

其中，

(7)

(8)

由上式可以看出，同类中的数据对越接近，类内的离散度矩阵就越小，不同类中的数据对彼此之间越分散，类间离散度矩阵就越大.

2.2.2 主元分析PCA

PCA[25]是一种无监督的线性降维技术，目的是找到所有样本方差变化最大的方向，能够将原始样本空间中的最大信息保留下来.

(9)

全局离散度矩阵St的对等形式可以表示为：

(10)

PCA的优化目标函数为：

(11)

目标函数优化问题等价于下述广义特征值求解问题：

StL=δIdL

(12)

其中，δ为广义特征值，L为δ对应的特征向量，Id为d维单位矩阵.

2.2.3 半监督Fisher判别分析SFDA

SFDA[26]将FDA和PCA有效的结合在一起，可同时利用从标签样本学习的判别结构和从全部样本学习的全局结构，找到最佳投影向量.

Srb=(1-β)Sb+βSt

(13)

Srw=(1-β)Sw+βId

(14)

其中，β∈[0,1]表示调整参数，当β=0时，SFDA完全转化为FDA，当β=1时，SFDA完全转化为PCA，SFDA的优化目标函数为：

(15)

上述优化问题等价于下面求广义特征值问题：

Srbq=λSrwq

(16)

其中，λ表示广义特征值，q表示对应的广义特征向量.若广义特征值的大小排序为λ1≥λ2…≥λd，对应的广义特征向量为q1，q2，…，qd.前r个广义特征向量可以构成最佳投影向量q1,q2,…,qr，即SFDA判别向量，其中，r(1≤r≤d)代表降维维数，此时降维后的空间变成了r维投影空间，一旦找到了最佳投影向量，便可以将样本投影到r维空间中，在投影空间中增加不同类样本之间的离散度.

3 提出的检测方法RAD-SFDA

3.1 检测框架

图1描述了本文方法RAD-SFDA的基本框架.

图1 RAD-SFDA的推荐攻击检测框架Fig.1 Recommendation attack detection framework of RAD-SFDA

如图1所示，RAD-SFDA方法首先利用特征提取方法对训练集和测试集中的用户概貌进行特征提取，本文选用主流的推荐攻击特征提取方法，将在实验部分进行介绍；在进行归一化处理操作之后，利用FDA从有标签用户概貌获得判别结构，利用PCA从全部用户概貌获得全局结构，然后，结合PCA和FDA建立SFDA模型获得最佳投影向量；在新的投影空间中训练贝叶斯分类器对测试集进行检测.

3.2 检测算法

用L=[x1，x2，…，xl]T表示训练集中的有标签用户概貌，U=[xl+1,xl+2，…，xl+u]T表示训练集中的无标签用户概貌，则训练集可以表示为Ttrain=[L,U]T=[xi,x2,…,xl,xl+1,xl+2，…，xl+u]T.

用Ck表示有标签用户概貌的第k个类别，其中，k为1或2，C1表示真实概貌，C2表示攻击概貌.

根据FDA[24]，利用公式(17)计算真实概貌和攻击概貌间的离散度矩阵Sb：

(17)

利用公式(18)，计算类内离散度矩阵Sw：

(18)

根据PCA[25]，利用公式(19)计算全局离散度矩阵St：

(19)

根据SFDA[26]，利用公式(20)计算正则化类间离散度矩阵Srb：

Srb=(1-β)Sb+βSt

(20)

利用公式(21)计算正则化类内离散度矩阵Srw：

Srw=(1-β)Sw+βId

(21)

其中，β∈[0,1]表示调整参数.

计算得到Srb和Srw之后，利用公式(16)计算得到广义特征值及其对应的广义特征向量q.设广义特征值由大到小排列为λ1≥λ2≥…≥λd，对应的广义特征向量为q1,q2，…，qd，利用前r个广义特征向量建立投影矩阵Qr=[q1,q2,…，qr]，其中，r表示降维维数，降维后的空间即是r(1≤r≤d)维投影空间，r将作为超参数在实验中设置具体值.通过设置r确定最佳投影空间，在该空间中，减少了真实概貌之间及攻击概貌之间的离散度，同时增大了真实概貌和攻击概貌之间的离散度，有效增加了不同类用户概貌的区分度，提升了检测性能.

图2 不同β值对应投影向量的二维示意图Fig.2 Two-dimensional diagram of projection vectors corresponding to different β values

在公式(20)中，Sb由有标签用户概貌计算得来，若有标签用户概貌过少则容易导致过拟合，若大量增加有标签用户概貌通常会增加标记代价.而St是由包含大量无标签用户概貌的信息计算得到，在不增加标记代价的条件下，会提高Srb检测推荐攻击的检测性能.在公式(21)中，Srw中的βId可以看作为正则化项，SFDA通过添加正则化项会表现出更强的泛化能力.

公式(20)和公式(21)中的调整参数β能够灵活调整SFDA的平滑性，当β趋于0时，SFDA倾向于FDA，当β趋于1时，SFDA倾向于PCA，将FDA和PCA巧妙的结合起来.图2演示了二维空间中不同β值对投影向量的影响.

如图2所示，实心圆圈表示有标签真实概貌，空心圆圈表示无标签真实概貌，实心方框表示有标签攻击概貌，空心方框表示无标签攻击概貌，虚线表示不同β值对应的投影向量.当β=0时，SFDA转化为FDA，投影向量对有标签用户概貌进行了很好的区分，但是部分无标签用户概貌有一定重叠，区分度不高.当β接近于1时，SFDA的开始向PCA过度，能够捕获全部用户概貌的全局结构.当β=0.5时，投影向量综合考虑了判别结构和全局结构，有标签和无标签用户概貌的区分度得到有效增强.

(22)

(23)

根据贝叶斯分类规则，按照后验概率的大小作分类依据，利用下式给出推荐攻击的检测结果：

(24)

基于上述分析，本文提出的基于SFDA的检测算法如算法1所示.

算法1.基于SFDA的推荐攻击检测算法

输入：训练集Ttrain，测试集Ttest，有标记用户概貌的比例ratio，降维维数r，调整参数β

输出：检测结果集

4.利用β、Sb、Sw和St，结合公式(20)和公式(21)计算正则化类间离散度矩阵Srb和类内离散度矩阵Srw；

5.利用r、Srb和Srw，结合公式(16)计算投影矩阵Qr；

4 实验结果与分析

4.1 实验数据和设置

采用协同推荐领域中的标准MovieLens 10M(1)https://grouplens.org/datasets/movielens/(数据集作为实验数据，该数据集包含71567个用户对10681部电影的10000054个评分，评分值位于1-5之间，每个用户至少拥有20条评分记录.MovieLens 10M数据集中的用户概貌全部标记为真实概貌，选取3种常见的攻击模型随机攻击、均值攻击和流行攻击[5]生成攻击概貌.

为了建立训练集，从数据集中随机选取1000个用户概貌作为真实概貌，设置随机攻击、均值攻击、流行攻击的攻击规模分别为1%、2%、5%和10%，对应填充规模分别为1%，3%，5%，10%.

为了建立验证集，从剩余数据集中随机选取1000个用户概貌作为真实概貌，设置随机攻击、均值攻击、流行攻击的攻击规模分别为1%，对应填充规模分别为1%.

为了建立每一个测试集，从剩余数据集中随机选取1000个用户概貌作为真实概貌，设置随机攻击、均值攻击、流行攻击的攻击规模分别为1%、2%、5%和10%，对应填充规模分别为1%，3%，5%，10%，分别注入到每一个测试集中.本文实验只检测推攻击，随机选取一个项目作为目标项目，然而，本文方法可直接用于检测核攻击，重复10次建立不同的测试集，记录检测结果的平均值进行对比和分析.

选取13个广泛使用特征提取方法[14]将上述数据集映射到特征空间，这些特征包括：WDMA，RDMA，WDA，Length Variance，DegSim，DegSim′，FMD(random attack)，FAC(random attack)，FMV(average attack)，FMD(average attack)，PV(average attack)，FMD(bandwagon attack，push)，和 FAC(bandwagon attack).

利用标准的召回率Recall和准确率Precision[28]评价方法在测试集上的检测性能.F-measure[28]是对召回率和准确率的调和均值，利用F-measure评价检测方法在验证集上的检测性能.

4.2 参数设置

在算法1中有3个关键的参数需要设置，分别是有标签用户概貌比例ratio、降维数目r和调整参数β.为了设定这3个参数，我们固定其中两个参数，让第3个参数在合理的范围内进行变化，观察本文方法在验证集上的检测性能.

图3 验证集上的检测性能随ratio的变化Fig.3 Changes of detection performance on validation set with ratio

设置β=0.5，r=11，本文方法在验证集上的检测性能随ratio的变化情况如图3所示.

如图3所示，曲线反映了有标签用户概貌所占比例ratio对本文方法检测性能的影响.随着ratio的不断增加，对应的F-measure值不断增大，这是因为随着有标签用户概貌的增加，从有标签用户概貌学习到的分类方向会更加准确，因而从全部用户概貌学习到的最大方差方向调整利用从有标签用户概貌学习到的分类方向后，便能找到最佳的投影向量，达到最好的检测性能.当ratio的值增加到15%时，F-measure达到最大值，之后便趋于稳定，说明该方法在此点找到最佳投影向量.该曲线图表明，有标签用户概貌的加入能够增加该方法的检测性能，并且即使在有标签用户概貌比例很小的情况下，该方法也能取得很好的检测性能.综上，在算法1中，设置ratio=15%.

设置β=0.5，ratio=15%，本文方法在验证集上的检测性能随r的变化情况如图4所示.

图4 验证集上的检测性能随r的变化Fig.4 Changes of detection performance on validation set with r

如图4所示，曲线反映了不同维度的投影向量对本文方法检测性能的影响.随着r值不断增加，本文方法检测性能不断上升，这是因为最佳投影向量是由r个广义特征向量构成的，广义特征向量的个数越多，包含的信息也就越多，通常越有利于提升检测性能.当r=11时，F-measure增加到最大，之后便不再增加，表明在此点便找到了最佳投影向量，用户概貌经过最佳投影向量的投影后，在r维空间中能够增加不同类用户概貌之间的离散度，使得检测性能达到最大.综上，在算法1中，设置r=11.

设置ratio=15%，r=11，本文方法在验证集上的检测性能随β的变化情况如图5所示.

图5 验证集上的检测性能随β的变化Fig.5 Changes of detection performance on validation set with β

如图5所示，曲线反映了调整参数β对本文方法检测性能的影响，β能够调整本文方法的灵活性，将FDA和PCA巧妙的结合起来，当β趋于0.1时，本文方法接近于FDA方法，当β趋于0.9时，本文方法接近于PCA方法.从曲线的变化幅度可以看出β值的变化对检测性能影响波动不大，这主要是因为不论β的取值情况如何，文本方法都有效利用了训练集中全部用户概貌信息.如图5所示，当β取0.5时，F-measure值最大，说明本文方法在此点处能最大限度的发挥出FDA和PCA结合后的优势，充分利用判别结构和全局结构找到最佳投影向量，因而检测性能最佳.因此在算法1中，设置β=0.5.

4.3 对比方法

为了验证本文方法的有效性，我们将其与下面有代表性的工作进行实验对比：

-PCA-VarSelect[6]：一种基于PCA的无监督检测方法，通过计算协方差检测攻击概貌，该方法假设攻击规模已知.

-SVM-TIA[19]：一种基于SVM的有监督检测方法，用Borderline-SMOTE方法平衡用户概貌样本，利用目标分析方法降低误判率.

-HySAD[23]：一种基于贝叶斯分类器的半监督检测方法，首次将半监督技术应用于推荐攻击检测.

为了验证在本文方法中，无标签用户概貌有效提升了检测性能，我们增加了一种对比方法如下：

-SFDA-Labeled：只使用训练集中有标签的用户概貌进行训练，不使用无标签用户概貌提升性能，其余设置与本文方法RAD-SFDA中的设置相同.

4.4 实验结果与分析

4种检测方法PCA-VarSelect、SVM-TIA、HySAD和RAD-SFDA对测试集中随机攻击、均值攻击和流行攻击的检测结果如表1、表2和表3所示.

PCA-VarSelect方法对随机攻击和均值攻击的检测效果较高，准确率和召回率保持在较高水平，该方法在检测流行攻击时性能有所下降，特别是检测小规模的流行攻击时，准确率不高.

表1 随机攻击的检测结果对比Table 1 Comparison of detection results for random attack

表2 均值攻击的检测结果对比Table 2 Comparison of detection results for average attack

表3 流行攻击的检测结果对比Table 3 Comparison of detection results for bandwagon attack

SVM-TIA方法在大多数情况下表现出了很好的检测性能，然而，在个别点处检测性能不稳定，这主要是因为SVM-TIA方法建立在准确识别目标项目的基础之上，当该方法准确定位到目标项目时，检测性能很高，否则，检测性能下降.

HySAD方法在检测3类推荐攻击时，具备一定的召回率，然而，从表中可以看出，该方法的检测准确率需要进一步提升.RAD-SFDA方法在大多数情况下表现出了较好的检测性能，召回率和准确率保持在了较高的水平，实验结果充分验证了本文方法的有效性.

两种检测方法SFDA-Labeled和RAD-SFDA对测试集中随机攻击、均值攻击和流行攻击检测结果的平均性能指标如表4所示.

表4 检测结果对比Table 4 Comparison of test results

如表4所示，在检测各类攻击时，RAD-SFDA方法比SFDA-Labeled方法在性能上均有所提升，平均召回率累计提升0.48，平均准确率累计提升0.08.实验结果表明，本文提出的检测方法充分发挥了半监督检测方法的优势，能够利用无标签用户概貌有效提升推荐攻击的检测性能.

4.5 讨 论

本文提出的RAD-SFDA方法同时利用了从有标签用户概貌捕获的判别结构，以及从由有标签和无标签用户概貌构成的全部用户概貌捕获的全局结构，以获得最佳投影向量，有效提升了半监督检测方法的准确率，这是本文方法与多数已有方法主要不同之处，也是本文方法能够有效提升检测性能的重要原因，实验结果充分验证了本文方法的有效性.

需要指出的是，虽然在多数实验结果中，本文方法都取得了较好的检测结果，但是，在检测高填充规模、高攻击规模的随机攻击和流行攻击时，本文方法的检测性能不高.导致这种现象的原因可能与本文选择的特征提取方法有关，本文所用的特征提取方法整体上是有效的，但对个别的攻击情况如高填充规模、高攻击规模的攻击，特征提取能力较弱.未来的工作中，选择更多、更有效的推荐攻击特征提取方法有望进一步提升半监督检测方法的检测性能.

5 总 结

本文提出了一种基于半监督Fisher判别分析的推荐攻击检测方法，有效提升了半监督检测方法的检测性能.利用Fisher判别分析技术捕获了有标签用户概貌的判别结构，利用主元分析技术捕获了所有有标签和无标签用户概貌的全局结构.利用SFDA技术实现判别结构和全局结构的有机结合，得到了最佳投影向量，增加了不同类用户概貌之间的离散度.在新的投影空间中，利用贝叶斯分类器完成了对推荐攻击的有效检测.在标准的MovieLens数据集上进行了对比实验，验证了本文方法的有效性.未来工作中，将考虑引入更多的推荐攻击特征提取方法，以期进一步提升检测方法的稳定性.