協(xié)同過濾推薦算法在視頻緩存策略中的應(yīng)用

彭冬陽　王睿　 胡谷雨

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

關(guān)鍵詞： 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 引言

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

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

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

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

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

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

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

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

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

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

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

輸出：緩存策略[S]

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

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

3.? for[iinlist]do //對[list]進行遍歷

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

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

6.? ? ? [break]

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

8. [returnS]

3 實驗驗證與結(jié)果分析

3.1 實驗數(shù)據(jù)集

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

3.2 對比的算法

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

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

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

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

3.3 評價指標與實驗參數(shù)設(shè)置

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

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

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

3.4 實驗結(jié)果與分析

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

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

4 結(jié)束語

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

參考文獻（References）：

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

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

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

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

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

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