彭冬阳　王睿　 胡谷雨

摘  要： 缓存替换策略是内容分发网络（Content Delivery Network， CDN）研究中的重要内容。常用的缓存方案是根据内容本身的特征进行缓存，比如视频的流行度、评分质量等。文章在缓存策略的设计中考虑到了用户特征，即根据用户的喜好，选择需要缓存的内容。使用基于矩阵分解的推荐算法对用户需求进行分析，筛选出用户可能感兴趣的视频，并利用基于加权评分预测值的贪婪缓存算法选择合适的内容进行缓存。仿真实验的结果表明，该算法可以将缓存命中率提高5-10%。

关键词： CDN; 缓存策略; 推荐算法; 矩阵分解

中图分类号：TP393          文献标识码：A    文章编号：1006-8228（2022）02-12-04

Application of collaborative filtering recommendation algorithm in video caching strategy

Peng Dongyang， Wang Rui， Hu Guyu

（Command and Control Engineering College， Army Engineering University of PLA， Nanjing， Jiangsu 210007， China）

Abstract： The cache replacement strategy is an important content in the research of content delivery network （CDN）. The caching scheme commonly used is to cache according to the characteristics of the content itself， such as the popularity of the video， the quality of the rating， and so on. This paper takes into account the characteristics of users in the design of the caching strategy， that is， select the content that needs to be cached according to the user's preferences. A recommendation algorithm based on matrix factorization is used to analyze users' needs， and screen out the videos that users may be interested in， and use a greedy caching algorithm based on weighted score predictions to select appropriate video content for caching. The results of simulation experiments show that the algorithm can increase the cache hit rate by 5-10%.

Key words： CDN; caching strategy; recommendation algorithm; matrix factorization

0 引言

隨着网络技术和自媒体平台的发展，人们可以享受到越来越丰富的视频服务，如优酷、抖音、哔哩哔哩等都允许用户个人上传自己视频作品供他人观看。但是，这也导致了网络中视频内容的爆炸式增长。一方面，用户面对海量视频会遇到“信息过载”的问题，难以筛选出自己需要的内容;另一方面，视频服务商既要应对大量视频数据的缓存和处理压力，又要选择合适的视频内容推送给目标用户以提升服务质量。基于CDN[1]的流媒体系统通过将视频数据缓存在网络的边缘的方式，一定程度上缓解了骨干网中数据拥塞的压力，而视频推荐系统则可以帮助用户解决“信息过载”问题[2]。视频推荐系统可以通过用户的历史行为信息，对用户喜好进行分析、预测，并推送用户可能感兴趣的视频。一个良好的视频推荐算法既可以满足用户的特色需求，提高其观看体验，也可以为CDN系统中视频缓存策略的设计提供支撑。

一个典型的流媒体CDN系统由一个源服务器和若干个缓存服务器组成，源服务器可以提供所有的视频资源，缓存服务器由于缓存能力限制只能为邻近的用户提供部分视频的服务。因此我们需要充分利用缓存服务器的缓存资源，合理地选择视频内容进行缓存。为了提高缓存服务器的效率，需要尽量保证用户请求的视频内容已经被缓存在服务器中。常用的缓存策略是基于视频流行度的，即：把网络中最流行的内容进行缓存[3]，因为他们被用户请求的概率较高。本文在设计缓存策略时将用户的偏好考虑在内，通过协同过滤推荐算法预测目标用户可能会请求的视频内容并进行缓存，从而提高缓存服务器的性能。

Amazon在2003年提出的基于协同过滤的推荐系统[4]取得了令人震惊的效果，从此协同过滤也逐渐成为推荐系统领域应用最广泛的一种推荐模型[5]。协同过滤的主要思想是通过分析用户的行为数据，筛选出目标用户可能感兴趣的物品进行推荐[6]。用户的行为数据通常可以用一个[m×n]维的评分矩阵[R]来表示，其中[m]表示物品的数量，[n]表示用户的数量，矩阵中的值表示用户对物品的评分。用户只对部分物品有评分记录，因此该矩阵是一个稀疏矩阵。协同推荐需要解决的问题是利用评分矩阵中已有的信息，来预测矩阵中的空白信息，并选出评分预测值最高的物品推荐给用户[7]。本文拟采用基于矩阵分解[8]的协同过滤算法进行视频推荐。

1 基于矩阵分解的协同过滤推荐算法

最后通过迭代对模型进行训练，实现矩阵[R]的分解，得到用户矩阵[U]和物品矩阵[V]。通过[U]和[V]，可以得到用户对物品的评分预测值，再依据预测值的大小筛选出合适的物品推荐给用户。

2 推荐算法在缓存策略中的应用

如前文中缓存策略模型所介绍的，为了给用户提供更好的服务，每个缓存服务器都会优先缓存那些将要被推荐给目标用户的视频。然而，一个缓存服务器需要同时服务多个用户，系统为每个用户推荐的视频也是不同的，因此具体选择哪些视频进行缓存依然是一个问题。

本文提出一种基于加权评分预测值的贪婪缓存算法（weighted rating prediction based greedy algorithm， WBGA），它的基本思想是为视频推荐列表中的视频赋以权重值，并以贪婪的方式缓存权重值最高的视频。假设每个缓存服务器服务了[H]名用户，每名用户的视频推荐列表用[Lu]表示，其中[Lu]中的视频是按照评分预测值降序排列的。首先，用户的优先级应当加以区分。不同用户每天观看视频的时长是不同的，因此在一段单位时间内，用户提出视频请求的可能性也是不同的。为了提高缓存服务器的效率，在替换缓存内容时应当优先为那些更有可能提出视频请求的用户考虑。其次，同一个视频可能会出现在多名用户的推荐列表中，这样的视频也应该被优先缓存。最后，评分预测值较高的视频的优先级也应当被提高，因为他们可以为用户提供更高质量的观看体验。

WBGA的伪代码如算法1所示。

算法1 基于加权评分值的贪婪缓存算法

输入：视频推荐列表[L1，L2，…，Lu]，每个用户的优先级[φu]

输出：缓存策略[S]

1. 计算视频推荐列表中每个视频的权重值[ρv]

2. 对视频推荐列表中所有视频依据[ρv]降序排序，得到有序视频序列[list]

3.  for[iinlist]do //对[list]进行遍历

4.    [W=W+wi]//[W]表示已缓存的视频的大小

5.    if [W<Cc]   //[Cc]表示缓存服务器的缓存空间大小

6.      [break]

7.    将视频[i]加入缓存策略[S]中

8. [returnS]

3 实验验证与结果分析

3.1 实验数据集

本文仿真实验的数据集是电影推荐研究中常用的公开数据集MovieLens-latest-small，该数据集包含了6040名用户对3952部电影的评价，总计1000209条评价信息。数据集被随机分成三份，分别作为训练集、测试集和验证集，占比分别是80%、10%和10%。训练集和测试集作为用户的历史请求信息对模型进行训练，验证集作为新的用户请求对算法的性能进行评估。

3.2 对比的算法

3.2.1 基于视频流行度的缓存策略（video popularity based cache strategy，PBCS）

这是目前最常用的缓存策略，它的基本思想是依据视频内容的流行度进行缓存，越流行的内容被缓存的优先级越高。由于实验数据集中缺少时间维度的信息，因此我们将每个视频被评论的次数看作它的流行度。缓存服务器会优先缓存最流行的视频内容。

3.2.2 基于视频评分的缓存策略（video rating basedcache strategy，RBCS）

高评分的视频内容往往会带给用户更高质量的观看体验，基于视频评分的缓存策略的主要思想就是优先缓存用户综合评分较高的视频。每名用户的评分偏好不同，在评分标准为1-5分的情形下，有些用户认为3分是较差的评分，也有用户倾向于直接给他们不喜欢的视频打1分。因此对视频的质量进行综合评分时应当考虑到用户的评分偏差带来的影响。消除用户评分偏差后的视频综合评分可以表示为：

3.3 评价指标与实验参数设置

缓存策略的质量主要体现在其缓存命中率上，如果缓存服务器中的内容长期得不到访问，那么就是对缓存资源的浪费。因此，缓存命中率越高表示缓存策略的效果越好。假设一段单位时间内，缓存服务器收到了部分用户的视频请求，那么缓存命中率的计算公式为：

缓存命中率=已缓存的视频被请求的次数/视频请求的总数 ⑺

为便于计算，假设缓存每个视频所需的空间大小是相同的，那么缓存服务器的缓存能力可以用它所能容纳的视频数目占视频总数的百分比来表示。比如缓存能力的默认值为20%，这表示它可以缓存[3952×0.2≈790]个视频。CDN系统中默认的缓存服务器数量为五个，6040名用户均匀地分布在每个缓存服务器上。在一段单位时间内，缓存服务器可以收到视频请求数目等于其服务的用户数目。

3.4 实验结果与分析

图2展示了缓存命中率随缓存服务器缓存能力的变化情况。从图中可以看出，基于加权评分预测值的贪婪缓存算法（WBGA）的命中率是最高的，而基于视頻流行度的缓存策略（PBCS）的表现也优于基于视频评分的缓存策略（RBCS）。随着缓存能力的不断提高，三种算法的命中率都会得到提升，但是提升的幅度都呈现下降的趋势。造成这一现象的原因可能是，随着服务器缓存能力的增加，可以被缓存的视频数目增多，命中率自然会得到提升。然而，协同过滤的算法的准确率是有限的，尤其是当推荐的视频数目较多时，排名越靠后的内容的准确性越差。因此，当考虑到缓存服务器的性价比时，缓存服务器的缓存能力并不是越高越好。这也为后续关于缓存策略的研究提供了参考。

圖3展示了缓存命中率随缓存服务器数目的变化情况。用户均匀地分布在每个缓存服务器上的，缓存服务器越多表明用户分布得越分散。从图中可以看出，随着缓存服务器数目的增加，WBGA的命中率不断提高。这是因为WBGA是基于用户评分的预测值做决策的，那么每个缓存服务器选择缓存的内容时都会考虑其所服务的用户的偏好。这也就意味着，每个缓存服务器上的用户越少，每个用户可以“占用”的缓存空间就越大，从而缓存命中率也会增加。然而，PBCS和RBCS都是基于视频本身的特征进行决策，并没有考虑到用户的喜好。当缓存服务器数目增加时，他们命中率反而会出现小幅度的下降。

4 结束语

缓存替换策略是CDN的关键技术之一，推荐系统的应用为缓存策略的设计提供了新的思路：不仅要考虑到视频本身的特征，还要考虑到用户的特征。本文提出的基于矩阵分解的协同过滤推荐算法只能对用户特征进行比较浅层次地分析，而基于深度学习的推荐系统能够分析用户和物品之间的上下文关系，充分挖掘数据中的隐藏信息。但是，如何将复杂的推荐系统和缓存策略的制定有效地结合仍然是一个难点，也是我们今后需要的研究主要内容。

参考文献（References）：

[1] 王薇薇，李子木.基于CDN的流媒体分发技术研究综述[J].计算机工程与应用，2004（8）：121-125

[2] 许海玲，吴潇，李晓东，等.互联网推荐系统比较研究[J].软件学报，2009，20（2）：350-362

[3] 聂华，张敏，郭敬荣，等.基于内容流行度差异性的CDN-P2P融合分发网络缓存替换机制研究[J].通信学报，2015，36（S1）：9-15

[4] G. Linden， B. Smith and J. York. Amazon.comrecommendations： item-to-item collaborative filtering[J].IEEE Internet Computing，2003，7（1）：76-80

[5] 翁小兰，王志坚.协同过滤推荐算法研究进展[J].计算机工程与应用，2018，54（1）：25-31

[6] 赵亮，胡乃静，张守志.个性化推荐算法设计[J].计算机研究与发展，2002（8）：986-991

[7] 李姗姗.基于协同过滤的视频推荐系统设计[D].南京邮电大学，2017

[8] Y. Koren， R. Bell and C. Volinsky. Matrix FactorizationTechniques for Recommender Systems[J].Computer， 2009，42（8）：30-37