改進學習率的一種高效SVD++算法

王燕+李鳳蓮+張雪英+田玉楚

摘 要： 推薦系統的核心包括推薦算法及其所依賴的大數據。推薦算法的高效計算，是實現實時人機交互的基本要求。在各種推薦算法中，SVD++算法因其特殊優點而得到廣泛應用。但是，大數據背景下SVD++推薦算法的突出問題是計算效率低，難以滿足實時人機交互要求。為解決這一問題，提出一種新的方法來提高SVD++推薦算法的計算效率，其核心是采用新的學習率函數對目標函數的指標進行優化。該學習率函數結合指數函數和一次函數的升降速率特點，具有初期值大、中期下降迅速以及后期值小且變化緩慢的特點。仿真實驗證明了該方法的有效性。

關鍵詞： 推薦系統； 推薦算法； 大數據； SVD++； 計算效率； 學習率

中圖分類號： TN911.1?34 文獻標識碼： A 文章編號： 1004?373X（2018）03?0146?05

Abstract： The core of the recommendation system includes the recommendation algorithm and big data. The efficient computation of the recommendation algorithm is the essential requirement to realize the real?time human?machine interaction. Among various recommendation algorithms， the SVD++ algorithm is widely used because its special advantages. However， in the environment of big data， the SVD++ recommendation algorithm has the prominent problem of low computing efficiency， and is difficult to satisfy the requirement of real?time human?machine interaction. In order to solve this problem， a new method to improve the computation efficiency of the SVD++ recommendation algorithm is proposed， whose kernel is to optimize the indicator of the target function with new learning rate function. In combination with the changing rate characteristics of the exponential function and linear function， the learning rate function has the characteristics of high initial value， low medium?term descend speed and later value， and slow change toward. The effectiveness of the method was verified with simulation experiment.

Keywords： recommendation system； recommendation algorithm； big data； SVD++； computation efficiency； learning rate

0 引 言

推薦系統是解決當前互聯網“信息過載”的一項關鍵技術[1]，其通過收集和分析用戶的各種信息來學習用戶特征，并根據分析得到的用戶興趣和行為模式來為用戶推薦所需要的服務。目前，推薦系統在很多領域獲得了廣泛應用，例如電子商務、電影、音樂、移動應用等。

推薦算法及其依賴的原始大數據是推薦系統的核心[2]?；ヂ摼W上每天產生TB及PB級的數據，數據復雜、維度高。在此背景下，有效提高推薦算法的計算效率成為實際應用中實現實時人機交互的關鍵。在常用的推薦算法中，基于奇異值分解算法（Singular Value Decomposition，SVD）改進的SVD++推薦算法[3]因具有很多優點而被應用于推薦系統，主要優點包括降低數據維度、考慮含蓄隱式行為信息以及預測準確性高等，是推薦算法中一種重要的用于實現目標用戶對目標項目進行評分預測的算法。

雖然SVD++推薦算法具有很多優點，但在實際應用中，需要處理的數據量往往屬于海量級。對于海量數據，SVD++算法計算效率低的問題格外突出，因而不能滿足實時人機交互的基本要求。

本文提出一種新的方法來提高SVD++推薦算法的計算效率，其核心是采用一種新的學習率函數對SVD++推薦算法中的各項指標進行優化學習。該新學習率函數采用指數函數和一次函數的綜合函數作為優化函數，從而具有自適應學習的能力，具體表現為初始學習率大、中期下降迅速以及后期學習率小且變化緩慢。

1 推薦算法

目前，主流的推薦算法包括四類：基于內容、協同過濾、基于圖結構以及混合的算法。其中，協同過濾算法是當前推薦系統中最廣泛應用的推薦算法[2]，其核心思想是尋找目標用戶的相似用戶群，然后根據相似用戶群對目標項目的評分情況預測目標用戶對該項目的喜好。協同過濾算法又包括基于項目、基于用戶和基于模型三類[2]?；陧椖亢突谟脩舻乃惴ㄔ砗唵?，但效率低。而基于模型的算法原理復雜，但預測準確性高，能夠很好地解決數據稀疏性的問題。本文針對基于模型的協同過濾推薦算法進行研究。endprint

基于模型的協同過濾推薦算法中的一種典型算法為SVD推薦算法，該算法的研究方向包括預測準確性和計算效率。針對準確性進行研究的方法主要包括：

1） 在原有SVD算法的基礎上加入其他信息，如置信度參數[4]、隱式信息及時間信息，綜合提高推薦模型的性能。

2） 在已改進算法的基礎上加入其他信息，如用戶和項目的偏置信息[5]。

3） 利用其他類型矩陣的特征來完成對評分的預測[6]。

這些方法較經典SVD算法的準確性都有所提高，但效率均低于SVD++推薦算法。

對于計算效率的研究，主要包括兩類：

1） 利用矩陣的特性提取出一個新的矩陣作為目標函數對SVD推薦算法進行優化[7]，此方法雖然有效提高了算法推薦效率，但準確性卻低于SVD++推薦算法。

2） 針對算法適應性進行研究，如基于SVD增量算法的模型不會隨著數據的變化而產生大的變化，該方法雖然能夠有效地提高算法計算效率[8]，但缺點是沒有考慮含蓄隱式信息。

針對以上方法的準確性低以及沒有考慮含蓄隱式信息的缺點，本文在SVD++推薦算法的基礎上，提出一種新的學習率函數對算法的模型進行訓練，該學習率函數具有自適應的特點，以此來解決大數據背景下推薦算法計算效率低的問題。

2 新的SVD++推薦算法

2.1 基本SVD++推薦算法預測公式

假設給定個用戶，個項目以及用戶對項目的評分矩陣是稀疏矩陣，表示用戶對項目的評分，推薦算法最終目標是對的項目進行預測。

最初該算法把高維的用戶?項目?評分矩陣分解為兩個降維矩陣乘積的形式其中表示的近似矩陣，和分別是降維后的用戶特征向量矩陣和項目特征向量矩陣，是降維后向量的維數，用戶對項目的預測評分公式為：

后來研究人員把用戶和項目自身的差異性，以及用戶的歷史瀏覽記錄和觀看記錄等含蓄隱式信息加入到推薦模型，得到SVD++推薦算法的預測評分公式如下：

式中：用戶的特征向量被模型化為為用戶的顯式評分信息的特征向量，為用戶的隱式反饋信息的特征向量， 表示用戶有過行為的項目數量，該行為包括用戶對項目的瀏覽、觀看以及評分等；表示對項目有過行為的用戶特征向量；表示項目的特征向量；是全局的平均數；是用戶的偏置向量；是項目的偏置向量。

2.2 梯度下降法

對SVD++算法的預測評分函數的各個參數進行優化求解的方法有兩種：一種是梯度下降法；另一種是最小二乘法。因后者的原理相對復雜，研究時一般采用前者[8]。

梯度下降法是一種最常用的優化算法。假設要求一個目標函數的極小值，首先要對待優化的指標進行求導，確定每次迭代的搜索方向，然后需要確定一個學習率作為每次搜索尋優的步長，最終使得待優化的指標迭代至目標值附近。

梯度下降法的一種簡單形式是：其中為學習速率，可以是較小的常數，也可以是一個函數表達式；是的梯度；為迭代次數。

2.3 基于新學習率的SVD++推薦模型

在SVD++推薦模型的訓練階段，對目標函數進行優化，學習率的選擇極其重要。若取值較大，即梯度下降迭代的步長較大，可以快速迭代至最優解附近，但是可能一直在最優解附近徘徊，無法計算出最優解，對于特殊的函數也可能會導致不收斂，始終發散求不出解；若取值較小，即梯度下降迭代的步長較小，下降速度較慢，其迭代出的解精度較高，但會耗費很長時間，這將不利于實際應用。

分析該模型訓練過程可知，梯度下降法中所用的學習率是一個自適應減函數，即學習初期時，采用較大的學習率，此時梯度下降的步長較大；中期時，迅速下降迭代至最優解附近；末期時，學習率很小并且變化緩慢，以一個很小的值來尋找最優解。若采用一個恒定不變的經驗值或是按經驗先取較大值后取較小值，則需要進行多次實驗才能找到合適的值，并且模型的訓練過程較長，精確度也不高。目前應用最多的學習率方法是采用指數函數調整大小，其公式為：

式中：為迭代次數；分別為該指數學習率函數的參數。大多數研究都采用該函數，該函數雖然可以通過調節參數滿足學習率先大后小的條件，但因為可控參數少，不夠靈活，在SVD++模型中應用時效率仍然很低。

綜合考慮以上情況，本文提出一種新的可用于SVD++算法的新學習率函數，該學習率函數表達式為：

式中：為迭代次數；和為學習率函數的三個參數。

基于新學習率函數的SVD++推薦算法包括模型訓練及性能測試兩部分。具體步驟如下：

輸入：訓練數據文件u?train，歷史數據文件u?his，學習率初值，迭代最大次數維度

輸出：迭代停止次數訓練時間和均方根誤差RMSE。

1） 初始化特征矩陣和使向量中的值為0～0.1的任意數，并把偏置項和向量中的值初始化為0。

2） 根據SVD++推薦算法的預測評分式（2）求解訓練數據中用戶對項目的預測評分再根據求得預測評分與實際評分的誤差值。

3） 學習模型中用戶和項目的特征變量和方法是使用梯度下降法最小化損失函數，損失函數如下所示：

損失函數包括誤差部分和正則化部分，誤差部分是式（5）中的第一部分，正則化部分為第二部分，該部分的作用是防止訓練過程中出現過擬合現象。

最小化損失函數的方法是對每個特征變量求偏導，得到相應特征的梯度向量，特征變量將沿著梯度方向進行更新，直到梯度向量接近零時特征更新結束。式（5）為特征和的學習更新公式，每個特征學習采用的學習率均同式（4）。

4） 根據更新得到以上特征參數，執行步驟2），判斷得到的誤差是否小于閾值若小于則停止訓練，否則繼續步驟2）。

5） 根據最終訓練出來的用戶和項目的特征參數，對測試數據里的用戶項目進行預測評分，并得到迭代次數訓練時間和預測準確性指標RMSE。其中RMSE的求解見4.1評價指標部分。endprint

上述步驟中，從步驟1）～步驟4）為采用訓練數據對特征和的值進行訓練的過程；步驟5）為對測試數據進行預測評分的過程，根據訓練出來的特征和的值對測試數據進行預測。

與現在常用的學習率函數相比，新學習率函數的主要優點是通過三個參數靈活有效地控制學習率的變化，具有自適應的特點。根據本實驗及數學理論分析可知，新舊學習率函數均為減函數，式（3）利用指數函數下降的特性，需要滿足條件。式（4）在指數函數的基礎上加入一次函數，增大了學習率的變化速率，并在此基礎上取倒數，最終也得到了一個減函數，式（4）需滿足條件和。與式（3）相比，首先，式（4）在兩個參數的基礎上又增加了一個參數，通過控制能更靈活地控制初值的大小，具有較大的初值；其次，式（4）的下降速率在指數函數基礎上加入了一次函數，下降速度較單純的指數函數更快；最后，隨著逐漸增大，會越來越小，相同的值條件下，比小很多，可以以一個更小的步長尋找到更精確的最優解。

3 實驗設計

3.1 數據集

本文采用MovieLens網站上的10萬、100萬和1 000萬條評分信息的數據集進行相應的實驗[9]，分別代表三類不同規模的推薦數據集，其數據量分別相差約一個數量級，如表1所示。這些數據集是對推薦算法性能進行測試的最常用的數據集合[8]，包含用戶對電影的評分和電影屬性等內容。數據集中每個用戶至少對20部電影進行過評分，評分值均為1～5的整數值，評分越高代表用戶對相應電影的評價越高，即越喜歡。該數據集能滿足本文實驗的要求。實驗時，對每個數據集按82的比例隨機分割為訓練集和測試集。

3.2 實驗平臺

本實驗的實驗平臺采用Windows 7操作系統，Intel CoreTM i5?2410M的CPU，6 GB的RAM以及eclipse環境。

3.3 推薦算法參數設定

實驗分別采用本文提出的新學習率和已有的舊學習率對算法進行調試，最終得到兩個學習率函數的合理參數。其中兩種方法的正則化參數和維度相同，分別為0.007和30。采用本文提出的新學習率對SVD++推薦模型進行訓練時，參數分別取為采用舊學習率函數對模型訓練時的參數取為0.007，0.9。兩種學習率隨迭代次數變化曲線的對比情況如圖1所示。

迭代次數（m≥4）變化對比

因迭代次數小于4時，新學習率的初值比舊學習率大1個數量級（新為0.047，舊為0.007），不能直觀比較差別，圖中不作顯示。

當迭代次數大于等于4時，由圖1可以看出，新學習率函數從0.005開始下降，迭代至20次時，學習率基本趨于零；而舊學習率函數從0.004 4開始下降，迭代至60次時，學習率才基本趨于零。在相同的迭代次數下，新學習率值小于舊學習率。該結果表明，與舊學習率函數相比，本文提出的新學習率函數，在學習初期以較大的學習率開始學習，然后以相對較快的速度下降，在后期以很小的學習率以及很少的迭代次數尋找到最優解。

4 評價指標及結果分析

4.1 評價指標

本實驗從三個方面來確定評價指標[10]：第一，為了提高推薦算法的效率，采用推薦模型訓練所用迭代次數作為評價指標之一，越小，則表示推薦性能越好；第二，隨著數據集的增大，為了使算法適應數據集的可擴展性，采用訓練時間作為第二個評價指標；第三，在提高效率的同時，需要保證算法的預測準確性，采用均方根誤差RMSE作為第三個指標，RMSE越小則準確性越高，其表達式如下所示：

式中：表示推薦算法預測的用戶對項目的評分；表示用戶對項目的實際評分；表示測試的樣本集；表示中測試樣本的個數。

4.2 結果分析

實驗分別采用基于新學習率和傳統舊學習率的SVD++推薦算法對各實驗數據集進行測試，得到的訓練迭代次數訓練時間RMSE的結果對比如圖2～圖4所示。實驗結果是相同實驗環境下重復執行20次，對實驗結果取均值所得。

從圖2可以看出，在三個不同規模的數據集和上進行實驗時，采用新學習率對模型進行訓練迭代的次數大約為30次，相比舊學習率大約減少120次。該結果表明，采用本文提出的學習率函數可以明顯地降低對SVD++推薦算法訓練所用的迭代次數。

從圖3可以看出，在數據量依次增大且分別相差一個量級的三個數據集和上進行實驗時，采用新學習率對算法進行訓練時所用訓練時間增長速度非常小，而采用舊學習率的時間增長速度較大。該結果表明，隨著數據集的增大，與舊學習率相比，采用新學習率對模型進行訓練可以明顯地縮短訓練所用的時間，同時也說明本文提出的新學習率函數可以明顯地改善SVD++算法在針對大數據集時計算效率低的缺點。

從圖4可以看出：在和數據集上進行實驗時，與舊學習率相比，采用新學習率對模型訓練后所得的RMSE略微減??；無論采用新或舊學習率，隨著數據集的增大，RMSE均逐漸減小。以上兩點可以說明，采用新學習率對模型進行訓練后可以略微增大算法的準確性。同時，隨著用戶和電影數量的增多，采用新舊學習率實驗后的準確性均逐步提高。

綜上可知，與舊學習率方法相比，采用本文方法對SVD++模型進行訓練后，迭代次數和訓練時間大幅減少，而且所得結果的準確度也有所提高。該結果說明本文方法在保證推薦模型預測準確性的前提下，可有效地提高SVD++推薦算法的計算效率。

另外，采用該方法在SVD系列其他推薦算法上也進行了測試，結果表明，本文提出的學習率函數既能明顯提高算法計算效率，又能保證推薦準確性，具有廣泛的適應性。

5 結 論

本文針對SVD++推薦算法在推薦系統應用過程中計算效率低的問題，提出一種新的自適應學習率函數來優化推薦模型，通過在MovieLens三個不同規模的數據集上的實驗表明，本文提出的方法可使算法的計算效率明顯提高，且不影響預測結果的準確性。下一步要進行的研究是利用三維張量用戶?項目?標簽信息，采用高階奇異值分解算法對用戶的喜好進行概率分析。endprint

參考文獻

[1] MISHRA R， KUMAR P， BHASKER B. A Web recommendation system considering sequential information [J]. Decision support systems， 2015， 75（C）： 1?10.

[2] 王國霞，劉賀平.個性化推薦系統綜述[J].計算機工程與應用，2012，48（7）：66?76.

WANG G X， LIU H P. Survey of personalized recommendation system [J]. Computer engineering & applications， 2012， 48（7）： 66?76.

[3] KOREN Y， BELL R， VOLINSKY C. Matrix factorization techniques for recommender systems [J]. IEEE computer， 2009， 42（8）： 30?37.

[4] 張超，秦永彬，黃瑞章.結合置信度和SVD的協同過濾算法[J].計算機與數字工程，2015，43（5）：758?761.

ZHANG Chao， QIN Yongbin， HUANG Ruizhang. Collaborative filtering algorithms based on confidence level and SVD [J]. Computer & digital engineering， 2015， 43（5）： 758?761.

[5] 季蕓，胡雪蕾.基于Baseline SVD主動學習算法的推薦系統[J].現代電子技術，2015，38（12）：8?11.

JI Yun， HU Xuelei. Recommender system based on Baseline SVD active learning algorithm [J]. Modern electronics technique， 2015， 38（12）： 8?11.

[6] 吳揚，林世平.基于正負反饋矩陣的SVD推薦模型[J].計算機系統應用，2015，24（6）：14?18.

WU Yang， LIN Shiping. SVD recommendation model based on positive and negative feedback matrix [J]. Computer system & application， 2015， 24（6）： 14?18.

[7] 方耀寧，郭云飛，丁雪濤，等.一種基于局部結構的改進奇異值分解推薦算法[J].電子與信息學報，2013，35（6）：1284?1289.

FANG Yaoning， GUO Yunfei， DING Xuetao， et al. An improved singular value decomposition recommender algorithm based on local structures [J]. Journal of electronics & information techno?logy， 2013， 35（6）： 1284?1289.

[8] ZHOU X， HE J， HUANG G， et al. SVD?based incremental approaches for recommender systems [J]. Journal of computer & system sciences， 2015， 81（4）： 717?733.

[9] GroupLens. MovieLens [EB/OL]. [2017?01?21]. http：//grouplens.org/datasets/movielens/.

[10] 陳清浩.基于SVD的協同過濾推薦算法研究[D].成都：西南交通大學，2015.

CHEN Qinghao. The research of collaborative filtering recommendation algorithm based on SVD [D]. Chengdu： Southwest Jiao Tong University， 2015.endprint