基于用户坐标距离与误差修正的推荐算法

Recommendation Algorithm Based on User Coordinate Distance and Error Correction

摘要: 推荐系统是一种根据用户历史行为、社交关系等信息去判断用户感兴趣的物品的智能系统，它可以有效的解决互联网信息过载的问题，因此具有重要的研究意义和广泛应用价值。为了解决推荐算法存在准确性有待提升和可扩展性不足的问题，本文提出了一种带有相似性选择和误差修正的用户坐标与评分距离推荐算法。该算法首先基于用户间相似性筛选出正相关的邻居，针对筛选后的邻居集合计算评分距离。然后建立用户间评分距离的合成坐标模型，与得到的用户坐标间距离进行评分预测。最后基于训练题设计误差修正算法，进一步提升预测准确度。通过本文算法与其他推荐算法在MovieLens数据集上进行对比，试验结果表明，该算法可以有效提高推荐算法的预测准确性和可扩展性。研究揭示了利用用户坐标距离进行预测的可行性，为进一步研究推荐系统的性能提升和运行机理提供了有效的依据。

Abstract: The recommendation system is an intelligent system that determines the items that the user is interested in based on the user’s historical behavior, social relationships and other information. It can effectively solve the problem of Internet information overload, so it has important research significance and wide application value. In order to solve the problems of recommendation algorithm that needs to be improved in accuracy and insufficient scalability, this paper proposes a user coordinate and rating distance recommendation algorithm with similarity selection and error correction. The algorithm first selects positively correlated neighbors based on the similarity between users, and calculates the scoring distance for the filtered neighbor set. Then a synthetic coordinate model of the rating distance between users is established, and the rating prediction is performed with the obtained distance between user coordinates. Finally, an error correction algorithm is designed based on the training questions to further improve the prediction accuracy. By comparing the algorithm in this article with other recommendation algorithms on the MovieLens data set, the experimental results show that the algorithm can effectively improve the prediction accuracy and scalability of the recommendation algorithm. The research reveals the feasibility of using user coordinate distance for prediction, and provides an effective basis for further research on the performance improvement and operating mechanism of the recommendation system.

1. 引言

推荐系统目前已经成为各类在线平台或在线应用的不可或缺的一部分。随着互联网接入在全球范围内的普及，消费者的选择呈指数级增长。尽管这允许多种选择和更广泛的选择，但将消费者的偏好与最合适的产品相匹配变得越来越困难 [1] 。系统试图通过分析消费者偏好并尝试预测用户对新商品的偏好来改变这种情况。推荐系统有着广泛的应用，如：在拥有大量产品的消费者网站中，为消费者提供可能感兴趣的产品的有针对性的信息；或者设计营销策略，用于预测产品的受欢迎程度 [2] 。

目前推荐系统包括基于内容的推荐、基于协同过滤的推荐、基于知识的推荐和混合推荐 [3] 。

基于内容的推荐算法 [4] 主要根据物品的相关信息、用户的相关信息和用户对物品的行为来构建推荐算法。基于内容的推荐算法一般只依赖于用户自身的行为为用户提供推荐，不涉及到其他用户的行为。

基于协同过滤的推荐算法是一种广泛应用的推荐算法，它主要依赖用户的历史行为数据来进行推荐。这种算法可以进一步分为基于记忆的协同过滤算法(Memory-based Collaborative Filtering)和基于模型的协同过滤算法(Model-based Collaborative Filtering) [5] 。基于记忆的协同过滤算法无论是基于物品 [6] 还是基于用户 [7] ，核心都是计算相似性，基于相似用户更容易做出相似的评分行为，相似的物品更容易获得相似的评分 [8] 。基于模型的协同过滤算法包括聚类模型 [9] 、矩阵分解模型 [10] 、神经网络 [11] 等，核心是建立物品和用户的模型表示，并利用训练好的模型来进行预测和推荐。

基于知识的推荐算法是将已知的数据进行专家知识进行建模和抽象，结果作为知识系统存储，并在用户提出需求时通过约束条件加以筛选，进行推荐 [12] 。

混合推荐算法是综合上述各种类型的推荐算法，用以提高推荐性能，或是满足不同推荐需求，其混合方案包括：加权型、交叉型、切换型、瀑布型、特征组合型、特征增强型等 [13] 。

推荐系统在面对多任务时，仍出现一些挑战。比如：预测准确性、算法可扩展性、冷启动等 [14] 。预测准确性用于评估推荐系统预测用户对物品的评分能力，准确性越高，说明推荐系统对用户的喜好理解得越准确。可扩展性是指推荐系统能够有效地处理大规模的用户和物品数据。随着用户数量和物品数量的增加，推荐系统需要能够在有限的计算资源和时间内，依然能够提供高质量的推荐结果。冷启动指的是加入系统的新用户和新物品在没有评价数据等关键信息条件下的推荐问题。

本文针对推荐系统准确性有待提升、可扩展性不足的问题，研究了推荐系统中用户相似性、合成坐标和误差修正的相关技术，提出了基于误差修正与用户坐标距离的推荐算法(Recommendation Algorithm Based on User Coordinate Distance and Error Correction)。

2. 相关工作

基于用户共同评分物品集合计算的用户相似性，在推荐系统研究中一般被称为用户间的相似性(User Similarity)。以基于记忆的协同过滤推荐算法为例，其核心思想就是通过利用与目标用户兴趣偏好相似的用户群体的喜好程度来预测和推荐。具体来说就是计算目标用户与其他所有用户两两之间的相似性，再通过相似性从高到低来选择必要的k个邻居，最后根据邻居的评分来对目标用户进行预测 [15] 。推荐系统领域提出了许多方法来计算用户间相似性，例如皮尔逊相似系数 [16] 、余弦相似系数 [17] 、Jaccard相似系数 [18] 等。这些相似性算法考虑不同的因素和计算方式来度量用户间的相似性。

合成坐标算法(Vivaldi) [19] 是一种轻量级、自适应地合成网络坐标算法，它使用欧几里得坐标系及其关联的距离系数，每个节点与其他节点的一部分进行交互，将自身定位在空间中，以便节点距离和测量的延迟相匹配。当系统收敛时，意味着每个节点都已获得所需的位置，任何一对节点之间的距离都可以准确预测其延迟。

Harris等提出了SCoR [20] 算法，将坐标分配给物品和用户，以便用户和物品之间的距离可以准确预测用户对物品的偏好。由于SCoR是无参数的，所以不需要微调就可以获得高性能。同时，与其他算法相比更能抵抗冷启动问题。但是，由于需要对所有的用户和物品数据进行建模，SCoR的执行时间非常缓慢，且算法的可扩展性较低。

误差修正是推荐系统中的一种常见方法，主要目标是最小化预测误差，通过调整模型的参数，使得预测评分和实际评分的误差尽可能小。

梯度下降 [21] 是一种迭代的误差修正算法，它的工作原理是在每一步中，根据当前的误差，对模型的参数进行微调。如果预测评分高于实际评分，那么降低预测评分；反之，则提高预测评分。从一个随机的初始点开始，沿着函数的梯度的负方向，逐步更新参数，直到找到一个局部最小值。

Harris等提出了DTEC [22] 算法，使用误差修正用于提高推荐系统的预测性能。DTEC在推荐系统初始执行之后引入第二阶段，该阶段考虑用户和物品之间训练集中的误差及相似性来改进其预测。这种方法适用于任何具有正训练误差的基于模型的推荐算法，实验结果有效提高了推荐的准确性。

结合用户相似性、合成坐标和误差修正技术，本文将针对推荐系统准确性与可扩展性问题展开研究。

3. 方法

为了解决推荐系统准确性有待提升、可扩展性不足的问题，本文提出一种基于用户坐标距离与误差修正的推荐算法。如图1所示，算法包含了四个个关键的步骤：第一、采用皮尔逊相似系数筛选用户的相似性，将相似性大于阈值的用户作为邻居，再计算用户之间的评分距离；第二、将用户和评分距离带入合成坐标算法建立模型，计算出用户间的坐标距离；第三、选择待测用户在合成坐标中所对应的邻居，预测用户对物品的评分；第四、使用误差修正算法对预测准确性进行更好地提升。

Figure 1. Algorithm structure diagram

图1. 算法结构图

3.1. 相似性，评分距离计算及选择

基于距离模型的推荐算法在计算上相对简单且运行时间较短，但是因为没有考虑用户间的相似性，所以精度不高。本文使用皮尔逊相似系数计算用户之间的相似性。一般来说，两个用户相似性越大，评分相似性就越强，该邻居在预测的重要性就越高。

$PCC\left(u,v\right)=S_{uv}=\frac{{{\displaystyle \sum }}_{i\in I_{uv}}\left(r_{ui}-{\bar{r}}_u\right)\cdot \left(r_{vi}-{\bar{r}}_v\right)}{\sqrt{{{\displaystyle \sum }}_{i\in I_{uv}}\left(r_{ui}-{\bar{r}}_u\right)}\cdot \sqrt{{{\displaystyle \sum }}_{i\in I_{uv}}\left(r_{vi}-{\bar{r}}_v\right)}}$ (1)

其中，集合 $I_{uv}$ 代表用户 $u,v$ 共同评分的物品集合， $r_{ui}$ 和 $r_{vi}$ 代表用户 $u,v$ 对物品i的评分， ${\bar{r}}_u$ 和 ${\bar{r}}_v$ 代表用户 $u,v$ 对所有物品的平均评分。

用户之间的评分距离计算公式定义如式(2)所示：

$d_{uv}=\underset{i\in I_{uv}}{{\displaystyle \sum }}\frac{r_{vi}-r_{ui}}{\left|I_{uv}\right|}$ (2)

其中， $d_{uv}$ 是用户u和用户v的评分之间的评分距离， $r_{ui}$ 和 $r_{vi}$ 代表用户 $u,v$ 对物品i的评分，集合 $I_{uv}$ 代表用户 $u,v$ 共同评分的物品集合， $\left|I_{uv}\right|$ 代表集合的大小。

UCD-EC根据公式(1)计算用户之间的相似性，通过公式(3)对用户进行过滤，选择符合条件的用户作为预测目标的邻居用户。

$\{\begin{array}{c}v\in N_u\text{if}{s}_{uv}\ge T_h\\ v\notin N_u\text{if}{s}_{uv}<T_h\end{array}$ (3)

其中， $N_u$ 代表用户u选择的邻居集， $s_{uv}$ 代表用户 $u,v$ 的相似性， $T_h$ 是UCD-EC算法设定的阈值。

3.2. 合成坐标计算

为了能更好地提高精度，将每个用户以及3.1中求出的评分距离进行合成坐标布局。本文使用修改后的合成坐标算法，将用户节点及3.2中计算、筛选后的评分距离作为网络节点，而所有用户的评分距离作为延迟，形成一个二分图，由用户节和评分距离作为节点组成。该算法的输入是 $\left(u,v,d_{uv}\right)$ 的三元组，其中 $u,v$ 代表不同的用户节点， $d_{uv}$ 是用户u和用户v的评分之间的评分距离。

对于训练集中的每个 $\left(u,v,d_{uv}\right)$ 三元组，在节点u和v之间添加一条边。基于评分距离 $d_{uv}$ ，为每条边分配一个权重 ${d^{\prime }}_{uv}$ ，该权重反映了边 $\left(u,v\right)$ 的距离。如果用户u和用户v的评分距离更相近，那么它们 $d_{uv}$ 值会更高，反映出它们的 $\left(u,v\right)$ 对对应于距离更小的边，反之亦然。最小评分 $\min R$ 的距离指定为100，而最高评分的距离指定为0。给定这些值，距离 ${d^{\prime }}_{uv}$ 计算如式(4)所示：

${d^{\prime }}_{uv}=100\cdot \left(\frac{\max R-d_{uv}}{\max R-\min R}\right)$ (4)

其中，节点u和节点v之间的用户坐标距离即为 ${d^{\prime }}_{uv}$ ， $\min R$ ， $\max R$ 表示最小偏好和最大偏好评级。因此，把Vivaldi中网络节点之间的延迟替换为上述等式后，可以根据用户和用户之间的评分距离算出用户间坐标距离。

3.3. 评分预测

通过合成坐标计算出所有用户的坐标距离后，针对目标用户，UCD-EC会对他的邻居进行选择。对于用户u，如果用户v与他有足够的共同评分且存在空间中的坐标，则会计算u和v的评分差值，将结果放入用户u的邻居集合中。计算公式如式(5)所示：

$r_{uv}=\max R-\frac{{d^{\prime }}_{uv}\cdot \left(\max R-\min R\right)}{100}$ (5)

其中， $r_{uv}$ 是用户u和用户v的评分差值， ${d^{\prime }}_{uv}$ 是u和用户v的坐标距离， $\min R$ ， $\max R$ 表示最小偏好和最大偏好评级。

然后通过邻居集合中的评分差来预测目标用户的评分。如果有邻居，该用户的预测评分即为它对所有物品评分的平均值。基于邻居评分预测用户评分，预测公式如式(6)所示：

$r_{ui}=\{\begin{array}{l}\frac{1}{\left|N_u\right|}\underset{v\in N_u}{{\displaystyle \sum }}\left(r_{uv}+r_{vi}\right),\left|N_u\right|>0\hfill \\ {\bar{r}}_u,\left|N_u\right|\le 0\hfill \end{array}$ (6)

其中， $r_{ui}$ 是用户u对物品i评分的预测值， $\left|N_u\right|$ 是用户u的邻居数量， $r_{uv}$ 是用户u和用户v的评分差值， $r_{vi}$ 是用户v对物品i的评分， ${\bar{r}}_u$ 是用户u对所有其他物品的评分均值。

3.4. 误差修正

为了更好地提高UCD-EC的预测准确性，本文使用了一种误差修正(Error Correction, EC)方法。该方法作用于训练集，对于每个用户，计算其预测值和实际值的平均绝对误差(MAE)，找出令MAE最小的最佳误差修正值E。算法1展示了单个用户误差修正的计算方法。

在此基础上，对3.3中求出的预测评分进行误差修正，公式如式(7)所示：

${r^{\prime }}_{ui}=r_{ui}+E_u$ (7)

其中， ${r^{\prime }}_{ui}$ 是进行误差修正后用户u对物品i评分的预测值， $r_{ui}$ 是公式(6)得出的评分预测值， $E_u$ 为该用户通过算法1出的误差修正值。

4. 实验

4.1. 实验设计

本实验使用MovieLens 25M [23] 数据集，此数据集从电影推荐网站中收集的，包含了由162,000名用户对62,000部电影的25,000,000条评分信息。本实验中采用了100 KB的数据集，包括了610个用户对9742部物品的100,836条评分数据。

实验在处理器为12th Gen Intel(R) Core(TM) i7-12700H 2.30 GHz，32 GB内存，操作系统为64位的Windows 11的环境下运行，采用了相同的编程语言进行算法实现和结果的可视化。

为了更好评估实验的性能，本文采用十折交叉验证，每次使用1份作为测试集，剩余9份作为训练集，每次选取训练集的数据进行训练，测试集的数据进行验证，最后的结果为10次实验的平均值。

4.2. 基准对比算法

为了验证算法准确性，本文将UCD-EC算法与基于合成坐标算法(Synthetic Coordinate, SCoR, 2017)、双重误差校正算法(Dual Training Error based Correction approach, DTEC, 2021)、用户观点传播算法(User Opinion Spreading, UOS, 2015)、基于信息熵的协同过滤算法(Entropy, 2020)、基于相似性网络资源分配算法(SRA, 2022)、基于向量相似性的算法(VS, 2020)等几种算法进行比较，所有算法用到的参数都采用其论文中最优的指标。

1) 基于合成坐标的算法(SCoR) [20] 把物品和用户当成节点，将合成坐标分配给节点以便用户和物品间的距离可以准确预测用户对某个物品的偏好；

2) 双重误差校正算法(DTEC) [22] 是一种基于双重(物品和用户训练误差的校正方法)，可以对一些基于模型的推荐算法进行误差校正，提高其准确率；

3) 用户观点传播算法(UOS) [24] 核心思想是将用户的观点分为正面和负面，从而判断用户之间评价的相似程度；

4) 基于信息熵的协同过滤算法(Entropy) [25] 将信息熵引入相似性计算，通过计算用户之间的信息熵，改进用户的相似性；

5) 基于相似性网络资源分配(SRA) [26] 设计了一种基于用户相似性网络内资源分配的用户–物品推荐算法，以提高预测精度，同时保持推荐算法的多样性；

6) 基于向量相似性的算法(VS) [27] 定义了全局相似性、局部相似性和元相似性作为用户间相似性指标，使得针对不同物品可以用不同方式测量用户相似性。

4.3. 评价指标

本文主要考查了UCD-EC算法与基准算法间在评分预测误差、推荐分类质量、算法可扩展性三个方面的性能差异。其中，使用平均绝对误差(MAE)、来评估算法预测的误差水平，使用Accuracy、Precision来评估算法的推荐分类质量。

4.3.1. 预测准确性指标

平均绝对误差(MAE) [28] 是模型评价中使用的标准度量。在推荐系统中，MAE表示预测值与实际值的平均误差，MAE越小，说明预测越准确。

$MAE=\frac{1}{n}{\displaystyle {\sum }_{i=1}^n\left|{r^{\prime }}_{u,i}-r_{u,i}\right|}$ (8)

其中，n表示实验中预测集的预测目标数量， ${r^{\prime }}_{u,i}$ 表示用户的预测得分， $r_{u,i}$ 表示用户的实际评分。

4.3.2. 分类准确性指标

准确率(Accuracy) [29] 是指推荐系统正确推荐的电影数占全部电影数量的比例，它反映了推荐系统的整体效果。准确率的计算公式是：

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

其中，TP (True Positive)表示用户实际感兴趣且被推荐的电影数，TN (True Negative)表示用户实际不感兴趣且未被推荐的电影数，FP (False Positive)表示用户实际不感兴趣但被推荐的电影数，FN (False Negative)表示用户实际感兴趣但未被推荐的电影数。

精确率(Precision) [30] 是指推荐系统推荐给用户的电影中用户实际感兴趣的电影的比例，它反映了推荐系统的用户满意度。精确率的计算公式是：

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

4.3.3. 可扩展性指标

在评估推荐系统的可扩展性时，本文主要关注两个关键指标：算法的执行时间和所需邻居的数量(Neighbor-Used)。算法执行时间越短，意味着推荐系统能够在实际应用中更迅速地为目标用户提供推荐。Neighbor-Used则反映了为进行预测而需要保存到数据库中的邻居数量。所需的邻居数量越少，占用的系统资源也就越少，从而表明推荐算法具有更好的可扩展性。

4.4. 实验结果

4.4.1. 预测准确性指标对比

Figure 2. MAE comparison result of UCD-EC and other algorithms

图2. UCD-EC与其他算法的MAE对比结果

图2表示为各个算法的MAE值。MovieLens 25M数据集内UCD-EC取得MAE最优值为0.683。SRA是表现最好的算法，但SRA牺牲了空间换取预测准确性，而UCD-EC算法提供较好准确性的同时，还有着良好的可扩展性。

4.4.2. 分类准确性指标对比

图3、图4分别展示了不同算法的分类准确性评价结果，其中图2表示的是Accuracy指标，图3表示的是Precision指标。UCD-EC的Accuracy值为0.65，在所有算法中表现最优，Precision值为0.67，仅次于SCoR算法。基于UCD-EC在Accuracy、Precision的表现，UCD-EC对比除了SCoR以外的其他算法能够更好分辨用户喜爱的电影，但是SCoR在准确度、空间和时间的性能指标表现均落后于UCD-EC。

Figure 3. Accuracy comparison result of UCD-EC and other algorithms

图3. UCD-EC与其他算法的Accuracy对比结果

Figure 4. Precision comparison result of UCD-EC and other algorithms

图4. UCD-EC与其他算法的Precision对比结果

4.4.3. 可扩展性指标对比

图5表示每个算法在预测过程中对测试集中所有目标使用的平均邻居数。其中SCoR、DTEC和UCD-EC算法使用固定的用户数量进行预测，所以不会随着数据集中邻居用户数量的增加而变化。其余算法的曲线接近重合，这些算法选择的邻居数量相似，不同的是相似性的度量值。相比于其他算法，UCD-EC平均只需要15个用户，可以选取更少的用户对目标用户的喜好物品进行预测与推荐，这加快了距离部分的计算速度，有效降低了算法的空间复杂度，进而提升了算法的可扩展性。

Figure 5. The actual number of neighbors for prediction and the number of neighbors the algorithm plans to choose

图5. 用于预测的实际邻居数与算法计划选择的邻居数

图6表示每个算法在数据集中运行所需要的时间。由图中可知，UCD-EC算法比SCoR、DTEC算法所需要的时间少，而比UOS、Entropy、VS、SRA算法所需的时间稍长。整体而言，UCD-EC在运行时间指标的表现位于中等，可以相对快速地把物品推荐给目标用户，使得用户反馈变快。

Figure 6. Time Spent comparison result of UCD-EC and other algorithms

图6. UCD-EC与其他算法的执行时间对比结果

5. 总结

针对推荐系统准确性不足和可扩展性低的问题，本文提出了空间排布的方法，针对用户和评分距离建立空间模型进行了探索，将空间模型和推荐系统进行有效结合，同时研究了推荐算法在邻居选择时的特殊情况，结合相似性网络建模来改善推荐性能，最后还设计了误差修正方法用以提高推荐算法的准确性。通过实验，发现本文所提出的UCD-EC算法在预测准确性、分类准确性、可扩展性方面都位于前列。这说明利用用户相似性、坐标距离和误差修正的手段，进一步挖掘推荐系统的潜在信息，在仅增加少量时间的情况下，提高预测的准确度，更精确的找到用户喜欢的类别。

在未来研究中，本文将专注于优化UCD-EC的运行时间。尽管UCD-EC优于同类型的SCoR和DTEC算法，但仍有可以提高的空间。在未来的工作中，研究人员会选择其他方式筛选邻居，或是对空间分布模型进行改进以提高UCD-EC的运行效率。