彭冬陽　王?！?胡谷雨

摘? 要： 緩存替換策略是內(nèi)容分發(fā)網(wǎng)絡(luò)（Content Delivery Network， CDN）研究中的重要內(nèi)容。常用的緩存方案是根據(jù)內(nèi)容本身的特征進(jìn)行緩存，比如視頻的流行度、評(píng)分質(zhì)量等。文章在緩存策略的設(shè)計(jì)中考慮到了用戶特征，即根據(jù)用戶的喜好，選擇需要緩存的內(nèi)容。使用基于矩陣分解的推薦算法對(duì)用戶需求進(jìn)行分析，篩選出用戶可能感興趣的視頻，并利用基于加權(quán)評(píng)分預(yù)測(cè)值的貪婪緩存算法選擇合適的內(nèi)容進(jìn)行緩存。仿真實(shí)驗(yàn)的結(jié)果表明，該算法可以將緩存命中率提高5-10%。

關(guān)鍵詞： CDN; 緩存策略; 推薦算法; 矩陣分解

中圖分類號(hào)：TP393? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? 文章編號(hào)：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 引言

隨著網(wǎng)絡(luò)技術(shù)和自媒體平臺(tái)的發(fā)展，人們可以享受到越來越豐富的視頻服務(wù)，如優(yōu)酷、抖音、嗶哩嗶哩等都允許用戶個(gè)人上傳自己視頻作品供他人觀看。但是，這也導(dǎo)致了網(wǎng)絡(luò)中視頻內(nèi)容的爆炸式增長(zhǎng)。一方面，用戶面對(duì)海量視頻會(huì)遇到“信息過載”的問題，難以篩選出自己需要的內(nèi)容;另一方面，視頻服務(wù)商既要應(yīng)對(duì)大量視頻數(shù)據(jù)的緩存和處理壓力，又要選擇合適的視頻內(nèi)容推送給目標(biāo)用戶以提升服務(wù)質(zhì)量?；贑DN[1]的流媒體系統(tǒng)通過將視頻數(shù)據(jù)緩存在網(wǎng)絡(luò)的邊緣的方式，一定程度上緩解了骨干網(wǎng)中數(shù)據(jù)擁塞的壓力，而視頻推薦系統(tǒng)則可以幫助用戶解決“信息過載”問題[2]。視頻推薦系統(tǒng)可以通過用戶的歷史行為信息，對(duì)用戶喜好進(jìn)行分析、預(yù)測(cè)，并推送用戶可能感興趣的視頻。一個(gè)良好的視頻推薦算法既可以滿足用戶的特色需求，提高其觀看體驗(yàn)，也可以為CDN系統(tǒng)中視頻緩存策略的設(shè)計(jì)提供支撐。

一個(gè)典型的流媒體CDN系統(tǒng)由一個(gè)源服務(wù)器和若干個(gè)緩存服務(wù)器組成，源服務(wù)器可以提供所有的視頻資源，緩存服務(wù)器由于緩存能力限制只能為鄰近的用戶提供部分視頻的服務(wù)。因此我們需要充分利用緩存服務(wù)器的緩存資源，合理地選擇視頻內(nèi)容進(jìn)行緩存。為了提高緩存服務(wù)器的效率，需要盡量保證用戶請(qǐng)求的視頻內(nèi)容已經(jīng)被緩存在服務(wù)器中。常用的緩存策略是基于視頻流行度的，即：把網(wǎng)絡(luò)中最流行的內(nèi)容進(jìn)行緩存[3]，因?yàn)樗麄儽挥脩粽?qǐng)求的概率較高。本文在設(shè)計(jì)緩存策略時(shí)將用戶的偏好考慮在內(nèi)，通過協(xié)同過濾推薦算法預(yù)測(cè)目標(biāo)用戶可能會(huì)請(qǐng)求的視頻內(nèi)容并進(jìn)行緩存，從而提高緩存服務(wù)器的性能。

Amazon在2003年提出的基于協(xié)同過濾的推薦系統(tǒng)[4]取得了令人震驚的效果，從此協(xié)同過濾也逐漸成為推薦系統(tǒng)領(lǐng)域應(yīng)用最廣泛的一種推薦模型[5]。協(xié)同過濾的主要思想是通過分析用戶的行為數(shù)據(jù)，篩選出目標(biāo)用戶可能感興趣的物品進(jìn)行推薦[6]。用戶的行為數(shù)據(jù)通?？梢杂靡粋€(gè)[m×n]維的評(píng)分矩陣[R]來表示，其中[m]表示物品的數(shù)量，[n]表示用戶的數(shù)量，矩陣中的值表示用戶對(duì)物品的評(píng)分。用戶只對(duì)部分物品有評(píng)分記錄，因此該矩陣是一個(gè)稀疏矩陣。協(xié)同推薦需要解決的問題是利用評(píng)分矩陣中已有的信息，來預(yù)測(cè)矩陣中的空白信息，并選出評(píng)分預(yù)測(cè)值最高的物品推薦給用戶[7]。本文擬采用基于矩陣分解[8]的協(xié)同過濾算法進(jìn)行視頻推薦。

1 基于矩陣分解的協(xié)同過濾推薦算法

最后通過迭代對(duì)模型進(jìn)行訓(xùn)練，實(shí)現(xiàn)矩陣[R]的分解，得到用戶矩陣[U]和物品矩陣[V]。通過[U]和[V]，可以得到用戶對(duì)物品的評(píng)分預(yù)測(cè)值，再依據(jù)預(yù)測(cè)值的大小篩選出合適的物品推薦給用戶。

2 推薦算法在緩存策略中的應(yīng)用

如前文中緩存策略模型所介紹的，為了給用戶提供更好的服務(wù)，每個(gè)緩存服務(wù)器都會(huì)優(yōu)先緩存那些將要被推薦給目標(biāo)用戶的視頻。然而，一個(gè)緩存服務(wù)器需要同時(shí)服務(wù)多個(gè)用戶，系統(tǒng)為每個(gè)用戶推薦的視頻也是不同的，因此具體選擇哪些視頻進(jìn)行緩存依然是一個(gè)問題。

本文提出一種基于加權(quán)評(píng)分預(yù)測(cè)值的貪婪緩存算法（weighted rating prediction based greedy algorithm， WBGA），它的基本思想是為視頻推薦列表中的視頻賦以權(quán)重值，并以貪婪的方式緩存權(quán)重值最高的視頻。假設(shè)每個(gè)緩存服務(wù)器服務(wù)了[H]名用戶，每名用戶的視頻推薦列表用[Lu]表示，其中[Lu]中的視頻是按照評(píng)分預(yù)測(cè)值降序排列的。首先，用戶的優(yōu)先級(jí)應(yīng)當(dāng)加以區(qū)分。不同用戶每天觀看視頻的時(shí)長(zhǎng)是不同的，因此在一段單位時(shí)間內(nèi)，用戶提出視頻請(qǐng)求的可能性也是不同的。為了提高緩存服務(wù)器的效率，在替換緩存內(nèi)容時(shí)應(yīng)當(dāng)優(yōu)先為那些更有可能提出視頻請(qǐng)求的用戶考慮。其次，同一個(gè)視頻可能會(huì)出現(xiàn)在多名用戶的推薦列表中，這樣的視頻也應(yīng)該被優(yōu)先緩存。最后，評(píng)分預(yù)測(cè)值較高的視頻的優(yōu)先級(jí)也應(yīng)當(dāng)被提高，因?yàn)樗麄兛梢詾橛脩籼峁└哔|(zhì)量的觀看體驗(yàn)。

WBGA的偽代碼如算法1所示。

算法1 基于加權(quán)評(píng)分值的貪婪緩存算法

輸入：視頻推薦列表[L1，L2，…，Lu]，每個(gè)用戶的優(yōu)先級(jí)[φu]

輸出：緩存策略[S]

1. 計(jì)算視頻推薦列表中每個(gè)視頻的權(quán)重值[ρv]

2. 對(duì)視頻推薦列表中所有視頻依據(jù)[ρv]降序排序，得到有序視頻序列[list]

3.? for[iinlist]do //對(duì)[list]進(jìn)行遍歷

4.? ? [W=W+wi]//[W]表示已緩存的視頻的大小

5.? ? if [W<Cc]? ?//[Cc]表示緩存服務(wù)器的緩存空間大小

6.? ? ? [break]

7.? ? 將視頻[i]加入緩存策略[S]中

8. [returnS]

3 實(shí)驗(yàn)驗(yàn)證與結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

本文仿真實(shí)驗(yàn)的數(shù)據(jù)集是電影推薦研究中常用的公開數(shù)據(jù)集MovieLens-latest-small，該數(shù)據(jù)集包含了6040名用戶對(duì)3952部電影的評(píng)價(jià)，總計(jì)1000209條評(píng)價(jià)信息。數(shù)據(jù)集被隨機(jī)分成三份，分別作為訓(xùn)練集、測(cè)試集和驗(yàn)證集，占比分別是80%、10%和10%。訓(xùn)練集和測(cè)試集作為用戶的歷史請(qǐng)求信息對(duì)模型進(jìn)行訓(xùn)練，驗(yàn)證集作為新的用戶請(qǐng)求對(duì)算法的性能進(jìn)行評(píng)估。

3.2 對(duì)比的算法

3.2.1 基于視頻流行度的緩存策略（video popularity based cache strategy，PBCS）

這是目前最常用的緩存策略，它的基本思想是依據(jù)視頻內(nèi)容的流行度進(jìn)行緩存，越流行的內(nèi)容被緩存的優(yōu)先級(jí)越高。由于實(shí)驗(yàn)數(shù)據(jù)集中缺少時(shí)間維度的信息，因此我們將每個(gè)視頻被評(píng)論的次數(shù)看作它的流行度。緩存服務(wù)器會(huì)優(yōu)先緩存最流行的視頻內(nèi)容。

3.2.2 基于視頻評(píng)分的緩存策略（video rating basedcache strategy，RBCS）

高評(píng)分的視頻內(nèi)容往往會(huì)帶給用戶更高質(zhì)量的觀看體驗(yàn)，基于視頻評(píng)分的緩存策略的主要思想就是優(yōu)先緩存用戶綜合評(píng)分較高的視頻。每名用戶的評(píng)分偏好不同，在評(píng)分標(biāo)準(zhǔn)為1-5分的情形下，有些用戶認(rèn)為3分是較差的評(píng)分，也有用戶傾向于直接給他們不喜歡的視頻打1分。因此對(duì)視頻的質(zhì)量進(jìn)行綜合評(píng)分時(shí)應(yīng)當(dāng)考慮到用戶的評(píng)分偏差帶來的影響。消除用戶評(píng)分偏差后的視頻綜合評(píng)分可以表示為：

3.3 評(píng)價(jià)指標(biāo)與實(shí)驗(yàn)參數(shù)設(shè)置

緩存策略的質(zhì)量主要體現(xiàn)在其緩存命中率上，如果緩存服務(wù)器中的內(nèi)容長(zhǎng)期得不到訪問，那么就是對(duì)緩存資源的浪費(fèi)。因此，緩存命中率越高表示緩存策略的效果越好。假設(shè)一段單位時(shí)間內(nèi)，緩存服務(wù)器收到了部分用戶的視頻請(qǐng)求，那么緩存命中率的計(jì)算公式為：

緩存命中率=已緩存的視頻被請(qǐng)求的次數(shù)/視頻請(qǐng)求的總數(shù)?⑺

為便于計(jì)算，假設(shè)緩存每個(gè)視頻所需的空間大小是相同的，那么緩存服務(wù)器的緩存能力可以用它所能容納的視頻數(shù)目占視頻總數(shù)的百分比來表示。比如緩存能力的默認(rèn)值為20%，這表示它可以緩存[3952×0.2≈790]個(gè)視頻。CDN系統(tǒng)中默認(rèn)的緩存服務(wù)器數(shù)量為五個(gè)，6040名用戶均勻地分布在每個(gè)緩存服務(wù)器上。在一段單位時(shí)間內(nèi)，緩存服務(wù)器可以收到視頻請(qǐng)求數(shù)目等于其服務(wù)的用戶數(shù)目。

3.4 實(shí)驗(yàn)結(jié)果與分析

圖2展示了緩存命中率隨緩存服務(wù)器緩存能力的變化情況。從圖中可以看出，基于加權(quán)評(píng)分預(yù)測(cè)值的貪婪緩存算法（WBGA）的命中率是最高的，而基于視頻流行度的緩存策略（PBCS）的表現(xiàn)也優(yōu)于基于視頻評(píng)分的緩存策略（RBCS）。隨著緩存能力的不斷提高，三種算法的命中率都會(huì)得到提升，但是提升的幅度都呈現(xiàn)下降的趨勢(shì)。造成這一現(xiàn)象的原因可能是，隨著服務(wù)器緩存能力的增加，可以被緩存的視頻數(shù)目增多，命中率自然會(huì)得到提升。然而，協(xié)同過濾的算法的準(zhǔn)確率是有限的，尤其是當(dāng)推薦的視頻數(shù)目較多時(shí)，排名越靠后的內(nèi)容的準(zhǔn)確性越差。因此，當(dāng)考慮到緩存服務(wù)器的性價(jià)比時(shí)，緩存服務(wù)器的緩存能力并不是越高越好。這也為后續(xù)關(guān)于緩存策略的研究提供了參考。

圖3展示了緩存命中率隨緩存服務(wù)器數(shù)目的變化情況。用戶均勻地分布在每個(gè)緩存服務(wù)器上的，緩存服務(wù)器越多表明用戶分布得越分散。從圖中可以看出，隨著緩存服務(wù)器數(shù)目的增加，WBGA的命中率不斷提高。這是因?yàn)閃BGA是基于用戶評(píng)分的預(yù)測(cè)值做決策的，那么每個(gè)緩存服務(wù)器選擇緩存的內(nèi)容時(shí)都會(huì)考慮其所服務(wù)的用戶的偏好。這也就意味著，每個(gè)緩存服務(wù)器上的用戶越少，每個(gè)用戶可以“占用”的緩存空間就越大，從而緩存命中率也會(huì)增加。然而，PBCS和RBCS都是基于視頻本身的特征進(jìn)行決策，并沒有考慮到用戶的喜好。當(dāng)緩存服務(wù)器數(shù)目增加時(shí)，他們命中率反而會(huì)出現(xiàn)小幅度的下降。

4 結(jié)束語

緩存替換策略是CDN的關(guān)鍵技術(shù)之一，推薦系統(tǒng)的應(yīng)用為緩存策略的設(shè)計(jì)提供了新的思路：不僅要考慮到視頻本身的特征，還要考慮到用戶的特征。本文提出的基于矩陣分解的協(xié)同過濾推薦算法只能對(duì)用戶特征進(jìn)行比較淺層次地分析，而基于深度學(xué)習(xí)的推薦系統(tǒng)能夠分析用戶和物品之間的上下文關(guān)系，充分挖掘數(shù)據(jù)中的隱藏信息。但是，如何將復(fù)雜的推薦系統(tǒng)和緩存策略的制定有效地結(jié)合仍然是一個(gè)難點(diǎn)，也是我們今后需要的研究主要內(nèi)容。

參考文獻(xiàn)（References）：

[1] 王薇薇，李子木.基于CDN的流媒體分發(fā)技術(shù)研究綜述[J].計(jì)算機(jī)工程與應(yīng)用，2004（8）：121-125

[2] 許海玲，吳瀟，李曉東，等.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J].軟件學(xué)報(bào)，2009，20（2）：350-362

[3] 聶華，張敏，郭敬榮，等.基于內(nèi)容流行度差異性的CDN-P2P融合分發(fā)網(wǎng)絡(luò)緩存替換機(jī)制研究[J].通信學(xué)報(bào)，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] 翁小蘭，王志堅(jiān).協(xié)同過濾推薦算法研究進(jìn)展[J].計(jì)算機(jī)工程與應(yīng)用，2018，54（1）：25-31

[6] 趙亮，胡乃靜，張守志.個(gè)性化推薦算法設(shè)計(jì)[J].計(jì)算機(jī)研究與發(fā)展，2002（8）：986-991

[7] 李?yuàn)檴?基于協(xié)同過濾的視頻推薦系統(tǒng)設(shè)計(jì)[D].南京郵電大學(xué)，2017

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