协同过滤推荐系统为解决“信息过载”问题提供了一条有效途径，在电子商务站点得到越来越多的应用。然而由于推荐系统自身的开放性，一些恶意用户通过向推荐系统中注入大量的虚假评分，使其推荐结果产生偏差，进而影响用户对推荐系统的信任^[1]。这种虚假评分的行为被称为“托攻击(shilling attacks)^[2]”或“概貌注入攻击(profile injection attacks)”。为了降低攻击者对推荐系统的影响，需要寻找一些特征来区分正常用户和攻击用户。传统的攻击检测方法大多都是根据真实概貌和攻击概貌的评分值存在差异来提取特征，但是这种基于用户评分值差异提取的特征存在两个问题：1)攻击用户通过选择流行项目并且评最高分(例如，流行攻击)来减小与正常用户的评分值差异，那么利用此类特征容易造成正常用户的误判；2)此类特征对于低填充规模攻击有较低的检测准确率和召回率。

为了解决以上问题，本文在提取特征时，一方面，考虑将用户对项目的评分值用一种统计指标值代替；另一方面，不考虑用户对项目的评分值大小，只考虑用户对某个项目是否有评分。另外，对于低填充规模的攻击，通过改进相似度计算方法，增加相似度权重，进而改进DegSim这一特征指标。

本文提出一种基于项目流行度和新颖度分类特征的托攻击检测算法。本文的主要贡献如下：

1)基于项目流行度和项目新颖度，提出了7个不依赖于项目具体评分值大小的托攻击检测特征。

2)根据提出的检测特征，提出了一种基于Boosting技术的托攻击集成检测框架。

3)在MovieLens数据集上进行了对比实验，验证了本文所提方法的有效性。

1 相关工作

托攻击检测算法大致可以分为两种：有监督检测算法和无监督检测算法。现有的有监督检测方法中，Chirita等^[3]提出了几个简单的统计指标, 在此基础上提出两种简单的攻击检测算法来达到检测攻击概貌的目的。Williams等^[4]提出一些通用特征和专用特征，并利用经典的机器学习算法对攻击概貌进行检测。基于文献[4]中提出的特征，He等^[5]提出了一种基于粗糙集的检测方法。基于Williams等^[4]提出的特征，伍之昂等^[6]针对不同的攻击模型提出了一种特征选择算法。李文涛等^[7]提出了一种基于流行度分类特征的托攻击检测算法，一定程度上提高了检测精度。Zhou^[8]通过利用文本分类技术提取特征，提出了一种有监督检测方法。Zhang等^[9]提出了一种基于元学习的集成检测算法，利用集成学习技术有效提升了检测精度。Zhang等^[10]通过构建有序项目序列，提出了一种基于决策树的集成检测算法，一定程度上提高了检测性能。

无监督检测方法中，Zhang等^[11]利用奇异值分解技术得到一个低维线性模型，依据信任分歧计算概貌之间的信任程度来检测攻击概貌。Mehta等^[12]基于主成分分析提出了一种无监督检测算法，在检测标准攻击时具有较好的效果。Bryan等^[13]基于攻击概貌之间的高相似性利用聚类技术提出了一种无监督检测算法。李聪等^[14]提出了一种缺失评分潜在因素分析模型。Chung等^[15]提出了一种基于β分布的检测方法。文献[16]利用信息熵提出了一种基于多维风险因子的推荐攻击检测方法。周全强等^[17]依据项目流行度划分窗口，提出了一种基于仿生模式识别的未知托攻击检测方法。

2 基于流行度和新颖度分类的托攻击集成检测框架

为了提高攻击检测的性能，本文提出一种基于流行度和新颖度分类的特征提取算法和一个集成检测框架来检测攻击用户。其中，集成检测框架如图 1所示。在特征提取阶段，通过引入流行度和新颖度，运用特征提取算法将训练集和测试集分别映射到特征空间。在基分类器生成阶段，采用Boosting^[18]技术，将训练集中每个样本分别赋以不同权重，从而保证每轮迭代过程中基训练集的差异，运用C4.5算法，生成k个不同的基分类器。在攻击检测阶段，通过融合多个带有权重的基分类器的预测结果，得到最终的检测结果。

2.1 特征提取

为了得到托攻击检测特征，首先给出项目流行度和项目新颖度的定义。

定义1 项目流行度(item popularity, IPop)：是指评分数据库中所有真实用户对项目i的评分次数，即

$IPo{p_i} = \sum\limits_{u \in {D_g}} \psi \left( {{r_{u,i}}} \right)$

(1)

式中：D_g表示用户评分数据库中所有真实概貌的集合；r_{u, i}表示用户u对项目i的评分值；若r_{u, i}=∅，则ψ(r_{u, i})=0；若r_{u, i}≠∅，则ψ(r_{u, i})=1。

定义2 项目新颖度^[19](item novelty, INov)：是指用户u购买项目i与购买记录中其他项目的不相似程度，即

$IPo{v_i} = \frac{{\sum\limits_{u \in {D_g},{r_{u,i}} \ne \emptyset } {No{v_{u,i}}} }}{{\left| {{D_g}} \right|}}$

(2)

式中:D_g表示D_g集合中的数目；Nov_{u, i}表示用户u对某一项目i的新颖度，其计算方法如下：

$No{v_{u,i}} = \frac{{\sum\limits_{{r_{u,i}} \ne \emptyset } {\left( {1 - w\left( {i,j} \right)} \right)} }}{{{N_u}}}$

(3)

式中：N_u表示用户u的评分项目数；w(i, j)表示项目i和项目j的相似度, 这里为余弦相似度。

根据定义1，将所有项目按照流行度降序排序，采用10折交叉验证将项目分为流行项目集合I_pop和非流行项目集合I_unpop。同理，根据定义2，将所有项目按照项目新颖度分为新颖项目集合I_nov和非新颖项目集合I_unnov。

1)流行项目流行度分布(popular item popularity distribution，PIPD)：是指某用户概貌中，已评分流行项目的流行度占用户流行度的比例，其计算公式为：

$PIP{D_u} = \frac{{\sum\limits_{i \in {I_{{\rm{pop}}}}} {\delta ({r_{u,i}})} }}{{\sum\limits_{i \in I} {\delta ({r_{u,i}})} }}$

(4)

式中, δ(r_{u, i})的计算公式如下：

$\delta ({r_{u,i}}) = \left\{ {\begin{array}{*{20}{l}} {IPo{p_i},{r_{u,i}} \ne 0;}\\ {0,{r_{u,i}} = 0} \end{array}} \right.$

(5)

2)非流行项目流行度分布(unpopular item popularity distribution, UNPIPD)：是指某用户概貌中，已评分非流行项目的流行度占用户流行度的比例，其计算公式为：

$UNPIP{D_u} = \frac{{\sum\limits_{i \in {I_{{\rm{unpop}}}}} {\delta ({r_{u,i}})} }}{{\sum\limits_{i \in I} {\delta ({r_{u,i}})} }}$

(6)

式中, δ(r_{u, i})的计算同式(5)。

3)新颖项目新颖度分布(novel item novelty distribution, NIND)：是指某用户概貌中，已评分新颖项目的新颖度占用户新颖度的比例，其计算公式为：

$NIN{D_u} = \frac{{\sum\limits_{i \in {I_{{\rm{nov}}}}} {\mathit{\Gamma }({r_{u,i}})} }}{{\sum\limits_{i \in I} {\mathit{\Gamma }({r_{u,i}})} }}$

(7)

式中, Γ(r_{u, i})的计算方式如下：

$\mathit{\Gamma }\left( {{r_{u,i}}} \right) = \left\{ {\begin{array}{*{20}{l}} {INo{v_i},{\rm{ }}{r_{u,i}} \ne 0;}\\ {0,{\rm{ }}{r_{u,i}} = 0} \end{array}} \right.$

(8)

4)非新颖项目新颖度分布(unnovel item novelty distribution, UNIND)：是指某用户概貌中，已评分非新颖项目的新颖度占用户新颖度的比例，其计算公式为：

$UNIN{D_u} = \frac{{\sum\limits_{i \in {I_{{\rm{unnov}}}}} {\mathit{\Gamma }({r_{u,i}})} }}{{\sum\limits_{i \in I} {\mathit{\Gamma }({r_{u,i}})} }}$

(9)

式中, Γ(r_{u, i})的计算同式(8)。

由于用户在流行项目集合里评分次数较多，在新颖项目集合里评分次数较少，因此可结合文本分类中卡方检验知识，提取检测特征。

χ²统计(Chi-square)^[20]表征2个统计量之间相互关联的程度。关联程度越大，χ²值越大；反之，关联程度越小，χ²越小。在文本分类领域，χ²统计用来表示特征t和类别c之间的依赖关系，其近似值为：

${\chi ^2} \approx \frac{{N \times {{\left( {A \times D - C \times B} \right)}^2}}}{{\left( {A + C} \right) \times \left( {B + D} \right) \times \left( {A + B} \right) \times \left( {C + D} \right)}}$

(10)

式中，A为特征t与c类文档同时出现的次数，B为特征t出现而c类文档不出现的次数，C为c类文档出现而特征t不出现的次数，D为特征t与c类文档均不出现的次数, N为文档总数。若特征t与c类文档相互独立，那么特征t的χ²值为0。

根据式(10)，提出以下2个检测特征：

5)流行项目的卡方估计值(Chi-square of popular item, CHIP)：表示用户u的评分项目与流行项目之间的关联程度，计算公式为：

$\begin{array}{l} CHI{P_u} = \left| I \right| \times {({A_{u,{I_{{\rm{pop}}}}}} \times {D_{u,{I_{{\rm{pop}}}}}} - {C_{u,{I_{{\rm{pop}}}}}} \times {B_{u,{I_{{\rm{pop}}}}}})^2} \times \\ \frac{1}{{({A_{u,{I_{{\rm{pop}}}}}} + {C_{u,{I_{{\rm{pop}}}}}}) \times ({B_{u,{I_{{\rm{pop}}}}}} + {D_{u,{I_{{\rm{pop}}}}}}) \times ({A_{u,{I_{{\rm{pop}}}}}} + {B_{u,{I_{{\rm{pop}}}}}}) \times ({C_{u,{I_{{\rm{pop}}}}}} + {D_{u,{I_{{\rm{pop}}}}}})}} \end{array}$

(11)

式中，A_{u, Ipop}表示被用户u评过分且属于流行项目I_pop集合的项目数，B_{u, Ipop}表示被用户u评过分且不属于流行项目I_pop集合的项目数，C_{u, Ipop}表示没有被用户u评过分但属于流行项目I_pop集合的项目数，D_{u, Ipop}表示没有被用户u评过分且不属于流行项目I_pop集合的项目数。

6)新颖项目的卡方估计值(Chi-square of novel item, CHIN)：表示用户u的评分项目与流行项目之间的关联程度，计算公式为：

$\begin{array}{l} CHI{N_u} = \left| I \right| \times {({A_{u,{I_{{\rm{nov}}}}}} \times {D_{u,{I_{{\rm{nov}}}}}} - {C_{u,{I_{{\rm{nov}}}}}} \times {B_{u,{I_{{\rm{nov}}}}}})^2} \times \\ \frac{1}{{({A_{u,{I_{{\rm{nov}}}}}} + {C_{u,{I_{{\rm{nov}}}}}}) \times ({B_{u,{I_{{\rm{nov}}}}}} + {D_{u,{I_{{\rm{nov}}}}}}) \times ({A_{u,{I_{{\rm{nov}}}}}} + {B_{u,{I_{{\rm{nov}}}}}}) \times ({C_{u,{I_{{\rm{nov}}}}}} + {D_{u,{I_{{\rm{nov}}}}}})}} \end{array}$

(12)

式中，A_{u, Inov}表示被用户u评过分且属于流行项目I_nov集合的项目数，B_{u, Inov}表示被用户u评过分且不属于流行项目I_nov集合的项目数，C_{u, Inov}表示没有被用户u评过分但属于流行项目I_nov集合的项目数，D_{u, Inov}表示没有被用户u评过分且不属于流行项目I_nov集合的项目数。

从用户评分角度发现：①DegSim相似度计算中，用户u与v之间的相似度不能等同于用户v与u之间的相似度；②计算中没有考虑评分为空的值。因此，通过改进DegSim这一特征，提出针对低填充规模攻击的检测特征。

7)相似度权重均值(weighted degree of average similarity, WDSA)：指用户与k近邻用户之间的平均相似度, 其计算公式为：

$WDS{A_u} = \frac{1}{k}\sum\limits_{u = 1}^k {sim\left( {u,v} \right)} \times \frac{{co\_rateitem\left( {u,v} \right)}}{{{N_u}}}$

(13)

式中:sim(u, v)为皮尔逊相似度，这里需要将评分为空的值当成0参与到计算中；co_rateitem(u, v)表示用户u和用户v共同评分的项目个数；N_u的含义同定义2；k为用户的最近邻数，本文选取k=25。

基于以上分析，给出特征提取算法的描述如下:

算法1 特征提取算法

输入:D_g, U, I;

输出:特征矩阵V。

BEGIN

(1) for i∈I do

(2) for u∈D_g do

(3)  IPop_i←计算每个项目的流行度

(4)  INov_i←计算每个项目的新颖度

(5) end for

(6) end for

(7) I←{I_pop, I_unpop}/*按流行度划分项目集合*/

(8) I←{I_nov, I_unnov}/*按新颖度划分项目集合*/

(9) for u∈U do

  V_u←{PIPD_u, UNPIPD_u, NIND_u,

  UNIND_u, CHIP_u, CHIN_u, WDSA_u}/*

  根据式(4)~(13)计算特征*/

(10) V←V∪V_u

(11) end for

(12) return V

END

算法1中第1~6行是计算每个项目的流行度和新颖度，然后按照项目流行度降序排序，把所有项目分为流行项目集合和非流行项目集合(第7行)，同理，按照项目新颖度降序，把所有项目分为新颖项目集合和非新颖项目集合(第8行)。第9~11行利用式(4)~(13)对每个用户u计算PIPD、UNPIPD、NIND、UNIND、CHIP、CHIN、WDSA，最后返回所有用户特征向量组成的特征矩阵V(第12行)。

2.2 基于流行度和新颖度的集成检测算法 2.2.1 基分类器的生成

采用Boosting^[18]技术，首先将映射到特征空间的训练集中每个样本赋一个初始权重，然后将带有权重的训练集数据用C4.5进行训练，得到一个基分类器。通过检测结果得到每个样本的分类错误率ε_i，进而得到基分类器的分类权重α_i。根据基分类器的分类权重得到下一次迭代中每个样本的权值，然后再进行训练得到另一个基分类器。基分类器生成算法描述如下：

算法2 基分类器生成算法

输入:训练集train, 迭代次数T, 基分类器C4.5, 类标签集y_i∈{0, 1};

输出:基分类器集C4.5set，基分类器权重集α。

BEGIN

(1)利用算法1的特征提取算法计算训练集的特征矩阵V_train；

(2)将基分类器集C4.5set初始化为空集；

(3)将每个样本的初始权重w_j¹设为1/m, j=1, 2, …, m;

(4) for i=1 to T do

(5)  对带有权值w_jⁱ的训练集特征矩阵V_train用C4.5算法进行分类，得到第i个基分类器C4.5setⁱ；

(6)计算第i个分类器的分类错误率：

${\varepsilon _i} = \frac{1}{m}[\sum\limits_j {w_j^i} \zeta ({C_i}({\mathit{\boldsymbol{V}}_{{\rm{train}}}}_j) \ne {y_j})];$

(7)依据分类器的分类错误率，计算第i个分类器的分类权重α_i；

(8)依据第i个分类器的分类权重更新下一轮样本的权重w_jⁱ⁺¹；

(9)将训练好的基分类器放到基分类集中，即

C4.5set←C4.5set∪{C4.5setⁱ};

(10)将每个基分类器的权重放到权重集合中，即

α←α∪{α_i};

(11) end for

(12) return C4.5set，α

END

2.2.2 托攻击检测算法描述

融合多个基分类器的预测结果，得到最终的检测结果。检测算法如下：

算法3 基于流行度和新颖度分类的集成检测算法

输入：测试集test, C4.5set, α, T;

输出：用户类标签集T_result。

BEGIN

(1)利用算法1的特征提取算法计算测试集的特征矩阵V_test;

(2) for each u∈Vtest do

(3) for each C4.5setⁱ∈C4.5set do

(4)  将特征矩阵V_test用已训练好的基分类器C4.5setⁱ检测，得到预测结果pre_i←pre_C4.5setⁱ(u)；

(5)  将用户u的预测结果和分类器权重融合，即p(u)←α_ipre_i；

(6) end for

(7)组合基分类器对每个样本的预测结果，即result(u)←sum(p(u));

(8)与阈值1/2sum(α)进行比较，确定用户u的类别T(u);

(9) end for

(10) T_result←T_result∪{T(u)};

(11) return T_result

END

3 实验数据与评价 3.1 实验数据与设置

实验选用MovieLens 100K数据集，该数据集由943个用户对1 682部电影的100 000条评分数据构成，且每个用户至少对20部电影进行了评分。

实验中，将数据集中的用户平均分成2组，分别作为训练集和测试集中的真实用户概貌。训练集和测试集中的攻击概貌分别由3种攻击模型(随机攻击、均值攻击和流行攻击)按照一定的填充规模和攻击规模生成，所产生的攻击概貌均为推攻击。填充规模分别为1%、3%和5%；攻击规模分别为3%、5%、10%和12%。

3.2 评价标准

本文采用托攻击检测中常用的准确率(precision)、召回率(recall)作为检测方法的评价指标。其定义为：

$precision = \frac{{TP}}{{TP + FP}}$

(15)

$recall = \frac{{TP}}{{TP + FN}}$

(16)

式中，TP表示被正确检测的攻击概貌的数目，FP表示被误判的真实概貌的数目，FN表示未被检测出来的攻击概貌的数目。

3.3 实验结果与分析 3.3.1 对比算法

为了评价算法的性能，将本文提出的检测算法(简称EMDegreeJ48)与2个集成检测算法进行实验对比。

1) EMJ48-6：选取RDMA、WDMA、WDA、DegSim、MeanVar^[4]和Hv^[13]作为检测特征，利用决策树C4.5算法作为基分类器的Adaboost算法。

2) EMSVM-6：选取RDMA、WDMA、WDA、DegSim、MeanVar^[4]和Hv^[13]作为检测特征，利用支持向量机(SVM)作为基分类器的Adaboost算法。

3.3.2 信息增益

信息增益(IG)^[21]通常用来评价特征对分类系统的重要程度，信息增益越大，说明该特征对分类系统的贡献越大，也就是该特征越重要。本文所提特征在测试集上的平均信息增益如表 1所示。

从表 1中可以看出:在检测3种攻击类型时，CHIP的信息增益位居首位，说明在标准攻击下，该指标对分类系统的贡献最大，比其他特征重要。NIND和UNIND 2个指标均排在前3位，说明它对于分类系统的重要性也是不可小觑的。对于WDSA这一特征指标，虽然它在低填充规模下，起到了相当大的作用，但是随着填充规模的增加，对于分类系统的贡献在减小，因此在测试集上的平均信息增益相比于其他特征表现的值较小，所以排名靠后。

3.3.3 准确率对比

图 2给出了EMDegreeJ48、EMJ48-6和EMSVM-6算法在不同攻击类型、不同填充规模和攻击规模下的检测准确率对比。从图 2可以看出，EMDegreeJ48算法在3种攻击下的准确率均明显高于EMJ48-6和EMSVM-6算法。以图 2(b)为例，对于填充规模为3%的均值攻击，EMDegreeJ48算法的准确率在0.824到0.95之间，EMJ48-6算法的准确率在0.086到0.306之间，EMSVM-6算法的准确率在0.167到0.548之间。这些结果表明本文所提出的检测特征时有效的。从图 2(a)可以看出，对于填充规模为1%的随机攻击，EMDegreeJ48算法的准确率在0.824到0.948之间，而EMJ48-6的准确率在0.069到0.225之间，EMSVM-6算法的准确率在0.149到0.416之间，说明EMDegreeJ48算法在低填充规模下仍能有效检测攻击概貌，进一步说明了本文所提出特征的有效性。

从图 2不难看出，不管是哪一种攻击，在同一填充规模下，随着攻击规模的增大，3种算法的检测准确率都在上升。以图 2(c)为例，对于填充规模为5%的流行攻击，EMDegreeJ48算法的准确率从0.824逐步上升到0.95，EMJ48-6算法的准确率从0.075上升到0.331，EMSVM-6算法的准确率从0.157上升到0.585 2。因此可以得出结论：随着攻击规模的增大，攻击概貌更容易被检测算法识别。

3.3.4 召回率对比

图 3给出了EMDegreeJ48、EMJ48-6和EMSVM-6算法在不同攻击类型、不同填充规模和攻击规模下的召回率对比。从图 3可以看出，EMDegreeJ48算法在填充规模为3%和5%时，召回率都达到了1。虽然在1%的填充规模下，召回率不全为1，但是随机攻击和均值攻击的召回率最低也达到了0.939，流行攻击的召回率最低也达到了0.917，这说明EMDegreeJ48算法能够检测出大部分攻击概貌。而EMJ48-6算法在检测填充规模为1%的均值攻击时，召回率分别为0.929、0.625、0.83和0.719，召回率最低时为0.625，说明有一部分攻击概貌没被检测出来。对于EMSVM-6算法，召回率几乎都是1，说明该算法和EMDegreeJ48算法一样能有效识别攻击概貌。

4 结论及进一步工作

从用户评分分布的角度，提出了一种基于项目流行度和项目新颖度分类特征的托攻击检测算法。该算法通过引入项目流行度和新颖度，提出了不依赖于评分值差异的特征，基于这些特征，提出了一种有监督检测算法EMDegreeJ48。在MovieLens 100K数据集上的实验结果表明，本文提出的检测算法能够有效减少对真实概貌的误判，提高了对攻击概貌的检测精度。

下一步工作将针对伪装能力更强的模糊攻击，从信号处理的角度提取能够有效区分真实概貌和攻击概貌的特征指标，实现对模糊攻击的检测。