基于合格邻居和异常检测的社区增强协同过滤

Community-Augmented Cosine Collaborative Filtering Based on All Qualified Neighbors and Abnormal Detection

摘要: 为了解决协同过滤推荐算法存在较大预测误差和推荐列表准确度不高的问题，提出一种结合异常检测和网络社区并基于所有合格邻居的协同过滤推荐算法。该算法使用修改的拉依达准则检测标记数据异常，在协同过滤相似度计算阶段降低与异常用户之间的相似性权重；使用得到的用户相似性建立网络模型，利用K核分解进行网络社区检测，在得到用户间的社区信息后对社区中用户进行相似性权重处理。基于MovieLens数据集并与五种同类型算法进行对比实验，结果表明，提出的算法可以有效降低预测误差以及提升推荐列表的排序准确度。

Abstract: In order to address the issue of the significant prediction errors and the low accuracy of recommendation lists in the collaborative filtering recommendation algorithm, a collaborative filtering recommendation algorithm that combines anomaly detection and network community based on all qualified neighbor is proposed. The algorithm uses the modified Pauta criterion for data anomaly detection and mark, and during the collaborative filtering similarity calculation stage reduces the similarity weight with abnormal users; Builds a network model using the obtained user similarity, and uses K-core decomposition for network community detection, and processes the similarity weights for users in the community after obtaining community information between users. Compared with five recommendation algorithms of the same type, and based on the MovieLens dataset, the experimental results showed that the proposed algorithm can effectively reduce prediction error and improve the accuracy of recommendation list rankings.

1. 引言

推荐系统目前已经成为各类在线平台或在线应用的不可或缺的一部分。解决人们在互联网时代如何从大量数据中获取有用信息的问题，推荐系统是最有用的工具之一 [1] 。作为一种信息过滤系统，其主要目标是提供个性化的信息服务，帮助用户在海量的信息中找到他们真正需要和感兴趣的内容 [2] 。

推荐系统对于互联网大数据时代具有非同小可的意义和价值，因此，作为领域中的关键技术——协同过滤(Collaborative Filtering, CF)，得到了大量研究人员的重视 [3] [4] [5] 。但是，该项研究一方面仍存在着数据稀疏性 [6] 、冷启动 [7] 、可拓展性 [8] 等经典挑战，另一方面在邻居使用上的问题引起了研究者的关注 [9] 。

异常检测(anomaly detection, AD)是一种用于识别数据集中与正常模式不符的数据点或行为的技术 [10] ，检测算法可以分为七类，其中包含了52种异常检测算法 [11] 。拉依达准则(Pauta criterion)是最简单有效的异常检测算法之一 [12] 。

相似性网络(Similarity network)是推荐系统中的一种常见技术，是一个将用户或物品视为节点、用户或物品之间的相似度视为节点间链接权重的链式模型。Ai等人 [13] 基于相似性网络设计了一种网络内资源分配的用户物品链接预测算法，缓解了推荐算法中预测准确性与多样性之间矛盾的问题以及存在的可扩展性问题。

本文旨在通过研究异常检测技术对异常数据的处理，以及结合相似性网络中相关技术的应用，解决协同过滤面对冷启动挑战带来的预测误差偏大的问题和面对海量信息带来的推荐列表排序不佳的问题。

2. 提出的算法

为了应对协同过滤算法存在较大的预测误差和推荐列表准确度不高的挑战，本文提出一种基于合格邻居和异常检测的社区增强协同过滤算法。如图1所示，算法包含了三个关键步骤：

1) 采用拉依达准则作为数据异常检测算法用于进行评分数据的检测和标记；

2) 在使用余弦相似度量计算完用户间的相似性后，选用训练集中所有合格邻居来构建网络；

3) 在构建的用户相似性网络中利用K核分解算法进行社区检测及标记。

Figure 1. Algorithm structural diagram

图1. 算法结构图

本文算法的总体流程如下：

1) 从评分集R获得每个物品的评分均值μ和标准差σ，使用改进的拉依达准则筛选异常评分构成物品异常评分集 $S_{ui}$ ；

2) 以用户为行、物品为列构建用户物品评分矩阵 $R_{ui}$ ，其中未评分的数据设置为0，基于对物品有共同评分的用户使用余弦相似度度量用户间的相似性，并依此选取每一位用户所有的合格邻居构成合格邻居集V；

3) 构建以用户为节点、相似度为边的用户相似性网络G，利用K核分解算法对相似性网络进行网络裁剪及社区标记，获得用户的社区信息；

4) 结合异常评分集，对合格邻居进行异常判断并处理，并且结合社区信息，最终用于用户项目的评分预测以及生成推荐列表。

2.1. 基于拉依达准则进行异常检测

拉依达准则又被称为3σ准则，准则要求被检测数据集基于正态分布的特性，认为数据点落在均值加减3倍标准差之外的概率很小，可以将这些数据点视为异常值。相关公式如式(1)：

$P\left(\left|x-\mu \right|>3\sigma \right)\le 0.003$ (1)

式中，x为数据值，μ和σ分别为数据集的平均值和标准差， $P\left(X\right)$ 为符合条件下的概率。

为了研究分析海量数据中可能存在的异常数据对推荐算法的影响，本文对拉依达准则的应用进行了调整，相关公式如式(2)所示：

$S_{ui}=\left(\left|r_{ui}-{\bar{r}}_i\right|>s{\sigma }_i\right)$ (2)

式中， $r_{ui}$ 代表用户u 对物品i的评分， ${\bar{r}}_i$ 和 ${\sigma }_i$ 分别代表物品i的平均分和标准差， $S_{ui}$ 代表了用户u对物品i的异常评分集，即把用户对物品的评分与物品的平均分的差值与s倍物品标准差比较后，由满足条件的用户物品对构成。

算法的具体步骤如下：

1) 计算数据集中每个物品评分的均值μ以及标准差σ；

2) 基于均值和标准差，进行项目异常评分的标记。计算物品评分及其均值的差值，并将差值大于s倍σ的物品及评分标记在物品异常评分集中，如式(2)；

3) 返回物品异常评分集。

2.2. 基于合格邻居的协同过滤和网络建模

本文算法是一种基于使用合格邻居的协同过滤。合格邻居需要满足下列条件：1) 与目标用户有超过一项共同评分的物品；2) 与目标用户可以计算余弦相似度；3) 可以进行异常判断，存在异常评分。

算法的具体流程包括以下三步：

1) 构建评分矩阵，计算用户间相似性 $s_{uv}$ 。本文算法在计算用户间相似度时是通过用户物品交互矩阵来计算用户间的余弦相似度。计算公式如式(3)所示：

$s_{uv}=Cos\left(u,v\right)=\frac{{{\displaystyle \sum }}_{i\in I_u\cap I_v}{r}_{ui}\cdot r_{vi}}{\sqrt{{{\displaystyle \sum }}_{i\in I_u\cap I_v}{r}_{ui}{}^2}\cdot \sqrt{{{\displaystyle \sum }}_{i\in I_u\cap I_v}{r}_{vi}{}^2}}$ (3)

式中， $I_u$ 和 $I_v$ 代表用户u和用户v评过分的物品集， $r_{ui}$ 和 $r_{vi}$ 代表用户u和用户v对物品i的评分。

2) 根据异常评分集，判断处理合格邻居。基于异常数据检测得到的异常检测评分集，其中包含了异常的用户物品对，通过对目标用户的合格邻居进行循环判断，若邻居对目标物品的评分属于异常集，则对这些异常邻居与目标用户的相似度进行p次幂处理。相关公式如式(4)：

$s_{uv}={\left(s_{uv}\right)}^p$ (4)

式中， $s_{uv}$ 代表用户u和用户v的相似度，p代表降幂权重。

3) 使用用户相似度进行网络建模。通过上述两步可以得到合格用户间的相似度，相似度网络建模基于每个用户为网络节点，用户间相似度为网络链接权重，建立无向链接，构成复杂网络。

2.3. K核分解网络及社区划分

社区是相似性网络中的重要结构，通过将相似性网络中的一组相似度更高的节点归为一类，从而将网络划分成不同的社区。Ai等人 [14] 基于用户之间和项目之间的相似性分别建立了用户–用户和项目–项目的网络，通过揭示网络中意义非凡的结构信息，改善了系统的预测和推荐结果。

然而，在复杂的相似性网络中通过社区检测来进行用户或项目的聚类会面临着大量的计算。因此，Ai等人 [15] 通过结合模糊链接重要性，利用K核分解算法为社区检测降低了计算复杂度。K核分解算法是依据节点度值从低到高依次去除节点的，一旦分解达到最高的核，即节点度值大于K，每个节点及其关联节点都将会被标记在一个社区。具体流程如图2所示。

Figure 2. K-core decomposition flowchart (K = 3)

图2. K-core分解流程图(K = 3)

为了改善异常检测算法对协同过滤的影响以及增强算法模型在面对冷启动的挑战时的推荐性能，本文进行了相似性网络建模，并且采用K核分解算法进行了优化。结合图2，社区划分步骤如下：

第一步，将网络中的每一节点都视为独立社区，并且从度值为1的节点开始进行第一轮递归检测，最大度值为t时，则需要进行t轮递归。

第二步，在第k次(k ≤ t)递归中，删除度值等于或小于k的节点，直到网络中合格节点的最小度值大于k，并且记录当前网络结构中度值最小节点的邻居。

第三步，如果邻居集为空，那么被删除节点的社区保持不变。如果邻居集为非空，那么从中找出权重最高的节点，并将其社区分配给该节点，再将依赖者的社区也合并到该节点的社区中。

第四步，如果网络中仍存在未被记录的节点，则从第二步开始进行下一轮的递归；否则，结束递归。

2.4. 基于异常数据和社区信息进行评分预测

在传统的基于用户的余弦协同过滤模型中，通常依据用户相似度矩阵来选择相似邻居计算目标用户对物品的评分，算法的评分预测公式如式(5)所示：

${\tilde{r}}_{ui}={\bar{r}}_u+\frac{{{\displaystyle \sum }}_{v=1}^k\left(r_{vi}-{\bar{r}}_i\right)\cdot s_{uv}}{{{\displaystyle \sum }}_{v=1}^k\left|s_{uv}\right|}$ (5)

式中， ${\tilde{r}}_{ui}$ 代表用户u对物品i的预测评分， ${\bar{r}}_u$ 代表用户u的平均评分， $r_{vi}$ 代表邻居用户v对物品i的评分， ${\bar{r}}_i$ 代表物品i的平均评分， $\left|s_{uv}\right|$ 代表用户u和用户v之间相似度的绝对值。

在基于用户相似性建立网络模型后，通过K核算法对网络进行分解，得到标记好的社区，可以对目标用户与不同社区下用户邻居的权重进行调整，定义如式(6)：

$\phi =\{\begin{array}{c}{\phi }_1\in \left[1,2\right],c_u=c_v\\ {\phi }_2\in \left(0,1\right],c_u\ne c_v\end{array}$ (6)

式中， $\phi$ 代表用户u和用户v的社区权重， $c_u$ 和 $c_v$ 代表用户u和用户v所在的社区。

综上，结合式(4)~(6)，本文算法最终的预测评分公式如式(7)所示：

${\tilde{r}}_{ui}=\{\begin{array}{c}{\bar{r}}_u+\frac{{{\displaystyle \sum }}_{v=1}^k\left(r_{vi}-{\bar{r}}_i\right)\cdot s_{uv}{}^p\cdot \phi }{{{\displaystyle \sum }}_{v=1}^k\left|s_{uv}{}^p\right|},v\in S_{ui}\\ {\bar{r}}_u+\frac{{{\displaystyle \sum }}_{v=1}^k\left(r_{vi}-{\bar{r}}_i\right)\cdot s_{uv}\cdot \phi }{{{\displaystyle \sum }}_{v=1}^k\left|s_{uv}{}^p\right|},v\notin S_{ui}\end{array}$ (7)

3. 实验

3.1. 实验设计

本文采用了MovieLens最新的小型数据集进行实验。该数据集包含100,836个评分和3683个标签应用程序，涉及9742部电影，由610名用户在1996年3月29日至2018年9月24日期间创建。

本文实验在处理器为Intel(R) Core(TM) i5-7300HQ CPU @ 2.50 GHz，8.0 GB内存，操作系统为64位Windows 10的环境下进行，采用了相同的编程语言进行算法实现和实验结果可视化。

实验采用的验证方法是折五验证，即把数据集随机分成五份，选取一份作为测试集，其余四份作为训练集，依次选取每一份测试集并循环实验五次，将五次的实验结果求和取平均作为最终的实验结果。

3.2. 对比算法与评价指标

3.2.1. 对比算法

本文所提出的算法是对协同过滤推荐算法的改进。首先，通过使用异常检测技术来减少异常邻居评分，避免异常值对预测准确度的影响；然后，通过使用社区检测技术来分解相似度网络，削弱不相似的用户间的影响；最后，同时使用所有合格邻居进行预测和推荐，提升算法效率。为了验证算法性能的优劣，本文选用如下五种算法进行对比实验：

1) 用户观点传播算法(UOS) [16] ：一种通过将用户观点传播过程与协同过滤相结合的评分预测方法。

2) 向量相似性算法(VS) [17] ：一种根据项目特征在多维度上使用向量测量用户相似性的链式预测模型。

3) 相似性网络资源分配算法(SRA) [13] ：通过将二分图模型和相似性网络相结合，实现资源分配并利用中心性和社区的网络特征预测用户物品链接。

4) 信息熵协同过滤算法(Entropy) [18] ：通过利用用户评分的信息熵来改进相似性度量，从而反映用户对物品的全局评分行为。

5) 巴氏算法(Bhattacharyya) [19] ：通过使用每个目标用户的最相似的邻居来预测物品，一般用于处理数据集稀疏的情况。

3.2.2. 评价指标

为了评估算法模型的综合性能，本文分别从评分预测准确性、分类预测准确性和推荐排序准确性三方面进行测评。平均绝对误差(Mean Absolute Error, MAE)和均方根误差(Root Mean Squared Error, RMSE)用于评估评分预测误差；准确性(Accuracy)和精确性(Precision)用于评估分类预测准确性；归一化折损累计增益(Normalized Discounted Cumulative Gain, NDCG)、排序准确性(Sorting Accuracy, SA)用于评估推荐列表排序准确性。

MAE计算了算法预测值与真实值的差值之和的均值，而RMSE计算了算法预测值与真实值的差值平方和求平均后的开平方结果。相比于MAE，RMSE在对于异常值的敏感程度更高，受偏差值的影响更大。MAE和RMSE的实验结果越小，预测精度越高，算法性能越好。两者计算公式如式(8)、式(9)所示：

$\text{MAE}=\frac{1}{n}\underset{i=1}{\overset{n}{{\displaystyle \sum }}}\left|r_{ui}-{\tilde{r}}_{ui}\right|$ (8)

$\text{RMSE}=\sqrt{\frac{1}{n}\underset{i=1}{\overset{n}{{\displaystyle \sum }}}{\left(r_{ui}-{\tilde{r}}_{ui}\right)}^2}$ (9)

其中，n是测试集中的样本数量； $r_{ui}$ 和 ${\tilde{r}}_{ui}$ 分别代表用户u对物品i的预测评分和实际评分。

Precision和Accuracy两个指标都是用于评估推荐算法的准确度度量。Precision侧重考虑推荐结果的精确度，即推荐给用户喜欢的物品占所有推荐物品的比重；而Accuracy侧重考虑算法结果分类的准确度，即能正确地将喜欢的推荐给用户而不将不喜欢的推荐给用户占所有物品的比重。两者公式如式(10)、(11)：

$\text{Precision}=\frac{TP}{TP+FP}$ (10)

$\text{Accuracy}=\frac{TP+TN}{TP+TN+FP+FN}$ (11)

其中，TP、TN、FP、FN分别代表真阳性(推荐了用户喜欢的物品)，真阴性(没有将用户不喜欢的物品推荐给用户)，假阳性(推荐了用户不喜欢的物品)，假阴性(没有将用户喜欢的物品推荐给用户)。

NDCG用于衡量推荐算法排序质量优劣，能够反映出推荐结果的排序准确性和相关性，越高相关性的物品出现在推荐列表越靠前的位置时，NDCG指标越优。其计算公式如式(12)、(13)所示：

$\text{DCG}=\underset{i=1}{\overset{b}{{\displaystyle \sum }}}{R}_i+\underset{i=b+1}{\overset{N}{{\displaystyle \sum }}}\frac{R_i}{{\log }_b{r}_i}$ (12)

$\text{NDCG}=\frac{\text{DCG}}{{\text{DCG}}_{\max }}$ (13)

其中，R_i代表推荐列表中第i个物品的相关度，若用户对该物品评分超过其平均评分，则 $R_i=1$ ，否则 $R_i=0$ ；b代表折损程度，本文实验设置为2；N代表列表中所有物品集合； $r_i$ 代表物品i在列表中的排列名次。

SA是一种评估算法结果排序准确度的指标 [20] 。其计算公式如式(14)所示：

$SA=\frac{{{\displaystyle \sum }}_{i=1}^{\left|L\right|}{{\displaystyle \prod }}_{j=i+1}^{\left|L\right|}I\left(S_i\ge S_{j+1}\right)}{\left|L\right|}$ (14)

其中， $S_i$ 和 $S_{j+1}$ 是用户在推荐列表对i和j位置的物品评分；I是指标函数，满足条件返1，否则为0；L为推荐列表。

3.3. 参数选择和结果分析

3.3.1. 参数选择

参数s用于异常评分数据的筛选。由式(1)、式(2)可知，s的取值处在3左右，因此，本文选取不同的s值对评分总数进行了过滤统计，如图3所示。

Figure 3. The sum of ratings under different s values

图3. 不同s值下的评分总数

由图可知，当s值小于2时，评分数量才有明显减少；而当s值小于1时，评分数量快速减少。因此，本文对参数s在[1, 2]取值进行对比实验，实验结果的MAE指标如图4所示。当s取值为1.5时，MAE值最低，这代表此时的s值能使算法误差降到最低。

Figure4. MAE for algorithms under different s values

图4. 不同s值下算法的MAE

参数p用于对异常邻居与目标用户的相似度进行次幂处理。由式(4)可知，当参数p数值越大时，对相似度降权的程度越大。图5、图6展示了算法在选择不同p值时的MAE指标和NDCG指标。由图可知p值越大，MAE值越小，算法误差越小，但与此同时NDCG指标下降，算法分类性能降低。

综上所述，为了综合提高算法的性能，本文设置参数s = 1.5，p = 10。

Figure 5. MAE for algorithms under different p values

图5. 不同p值下算法的MAE

Figure 6. NDCG for algorithms under different p values

图6. 不同p值下算法的NDCG

3.3.2. 结果分析

图7展示了六种算法随邻居数量变化而变化的MAE实验结果。随着邻居数量的增多，五种对比算法都逐步达到误差的最低值，而本文算法的MAE误差因使用所有邻居的缘故误差值一直保持在0.6802，并且保持最低位。较新的SRA算法误差值在0.6809附近位居第二，其次是UOS (0.6843)、Entropy (0.6870)、VS (0.6924)，最后是巴氏算法(0.6949)。结果表明，本文算法能将MAE误差降低0.59%~2.11%，能够较快速的实现更精准的预测结果。

Figure 7. MAE for different algorithms

图7. 不同算法的MAE

图8展示的是六种算法随邻居数量变化而变化的RMSE误差结果。RMSE对于误差的判断更加灵敏及严格。由图可见，随着邻居数量的增加，当五种对比算法的误差都达到最低值时，本文算法的得分仍然处于比较中的最低值，并且相比于MAE，与其他算法得分拉开了更大的距离。本文算法将RMSE降低了0.16%~3.08%，由此可见，本文算法无论在小误差还是大误差下，都能保持很好的预测准确性。

Figure 8. RMSE for different algorithms

图8. 不同算法的RMSE

Figure 9. Precision for different algorithms

图9. 不同算法的Precision

如图9所示，本文算法的Precision得分(0.6447)在六种算法中排名第一，领先于Entropy算法(0.6441)第三位的SRA算法(0.6436)，排在后面的分别是UOS (0.6421)、Bhattacharyya (0.6389)和VS (0.6266)。与五种对比算法相比本文算法将Precision得分提高了0.09%~2.89%，这代表本文算法在推荐用户喜欢的物品时占所有推荐的物品比例更高，能给用户带来更好的体验。

如图10所示，本文算法的Accuracy得分(0.6306)在六种算法中是第三。一方面，第一位的Bhattacharyya算法和第二位的UOS算法的Accuracy得分分别为0.6360和0.6358，两者不相上下但领先于本文算法得分约0.82%。另一方面，本文算法Accuracy得分比排在第四位的Entropy (0.6301)、第五位的SRA (0.6296)和第六位VS (0.6257)高出0.08%~0.78%。

Figure 10. Accuracy for different algorithms

图10. 不同算法的Accuracy

根据式(10)、(11)以及对应的概念，结合两种指标得分可知，本文算法在推荐结果准确性上性能表现优异，而在分类准确性上性能表现一般。但在实际应用过程中，推荐结果的准确与否直接影响了用户对系统的体验感受，因此，本文认为Precision指标结果更具有参考价值。

如图11所示，本文算法的NDCG得分(0.7104)一直处于领先的位置。最新的SRA其NDCG得分略低与本文算法，随着用户数量的增加，其稳定在0.7090。UOS在用户数为15时达到最高得分0.7059，但随着用户数增加，其得分持续降低，最终平衡在0.7002。随后的Entropy和巴氏算法，其NDCG得分随用户数的增长呈上升趋势，最后得分稳定在0.7084和0.7048。VS的得分整体趋势先增后降，受邻居数量影响较大，最终得分为0.6495。本文算法相比其他算法，NDCG指标的提升范围在0.20%~9.38%。

图12展示的是不同算法在SA排序指标上的得分结果。由图可知，相比于五种对比算法，本文算法得分(0.4802)整体上居于第一位。在用户数为56时，巴氏算法达到最高得分(0.4803)超过本文算法，但用户数的增加让其得分下降至最后的0.4788。Entropy算法和SRA算法的得分随用户数的增加稳步上升，最终排名稳定在0.4795和0.4784。UOS算法和VS算法的SA得分受用户数影响较大，用户数少时得分较高，但后续降低至0.4732和0.4408。本文算法在SA指标上的提升达到了0.15%~9.35%。

Figure 11. NDCG for different algorithms

图11. 不同算法的NDCG

Figure 12. SA for different algorithms

图12. 不同算法的SA

4. 结论

针对协同过滤存在较大的预测误差和推荐列表准确度不高的问题，本文提出了一种基于合格邻居和异常检测的社区增强协同过滤算法。算法引入异常数据检测技术进行数据处理，同时结合相似性网络中的社区检测技术进行用户相似增强，最后基于所有的合格邻居进行协同过滤。

算法在MovieLens数据集中与其他算法进行对比，实验证明，本文提出的算法模在预测准确性上提升了3%，在排序准确性上提高了9%。然而，本文算法在分类准确性方面还有待提升。在未来的工作中，研究人员可以继续研究结合不同的异常检测算法进一步提高协同过滤算法的综合性能。

基金项目

国家自然科学基金项目(61803264)。