基于KL散度的ALS推薦算法

韓遠達

摘要：針對傳統協同過濾推薦算法在稀疏數據上推薦準確度低的問題，提出一種基于KL散度的ALS推薦算法KL-ALS。傳統ALS算法計算物品相似度時只考慮了用戶之間的共同評分項，得到的相似性與真實值會有一定的誤差，而采用KL散度計算物品相似度時，對用戶評論的數量不做任何限制，不依賴于用戶共同評分項。KL-ALS算法首先將ALS算法計算物品相似度和KL散度計算的物品相似度按照一定權重混合，產生總體相似度，進而采用ALS算法訓練模型，能夠更加準確地度量物品間的相似度，改善推薦效果。實驗選取亞馬遜智能產品評論數據集，與傳統的基于ALS的協同過濾推薦算法和基于物品的協同過濾推薦算法（Item-CF）進行對比，實驗結果表明KL-ALS推薦算法能有效提高推薦的準確度和性能。

關鍵詞：KL散度;ALS算法;推薦算法;相似度;協同過濾

中圖分類號：TP399? ? ? 文獻標識碼：A

文章編號：1009-3044（2022）12-0004-03

開放科學（資源服務）標識碼（OSID）：

近幾年來，網絡中的數據呈現爆炸性增長的趨勢，人們漸漸由信息缺乏時期進入了信息超載時期，存儲、分析、處理這些數據往往需要利用大數據技術。對于平臺來說，如何使自己的產品信息在大量的信息中凸顯出來，被用戶所關注，正變成一個日益重要的問題。而推薦系統[1]可以很好地解決這個問題，它可以將平臺海量數據加以處理利用，以便用于預測用戶的興趣。

1 相關研究

推薦系統通過分析數據源中用戶對不同物品的評價和歷史偏好之間的聯系規律[2]，幫助用戶從網絡中的大量信息中搜索現在和將來可能會喜歡的信息資源，從而進一步向用戶提供相應的推薦服務。而推薦算法是推薦系統中的核心部分，目前常用的推薦算法按照數據源不同可以分為基于人口統計學的推薦算法、基于內容的推薦算法和協同過濾推薦算法[3]。基于人口統計學的推薦算法主要根據用戶的身份信息的相似性進行推薦，例如：性別、年齡、職業等信息，這種推薦較為粗糙，精確度一般不高。基于內容的推薦算法是給用戶推薦與其曾經喜愛的物品相似的物品，主要基于物品自身的屬性，廣泛應用于文本領域的推薦。協同過濾推薦算法是目前推薦領域應用較多的算法，它可以通過基于統計的機器學習算法得到不錯的推薦效果，但仍然存在數據稀疏性等問題[4]。針對該問題，本文提出一種基于KL散度的ALS推薦算法KL-ALS，在Spark平臺[5]上進行實驗，達到提高推薦的準確度和推薦性能目的。

2 基于KL散度的ALS推薦算法KL-ALS

2.1KL散度

KL散度基于概率分布，能夠度量幾何距離[6]（如余弦距離、歐氏距離）難以衡量的數據對象是它最顯著的突破之一。假設區間D為連續區間，[ρi]和[ρj]分別為兩個不同的概率密度函數，則離散型隨機變量的KL距離如公式（1）所示。

[D（ρi||ρj）=x∈Dρi（x）log2ρi（x）ρj（x）]? ? ? ? ? ? ? ? ? ? （1）

連續型隨機變量的 KL 距離如公式（2）所示。

[D（ρi||ρj）=Dρi（x）log2ρi（x）ρj（x）]? ? ? ? ? ? ? ? ? （2）

其中，[ρi（x）>0且ρj（x）>0]，且保證[0log20ρ=0]。

基于KL散度進行相似度的計算主要分為平滑處理、對稱性修正、距離到相似度的轉換三個步驟，下面詳細討論實現過程。

（1）平滑處理

為確保KL散度對智能產品數據的適用性，即保證[ρ（x）>0]，需對[ρ（x）]平滑處理，如公式（3）所示。其中[0<δ<1]，在平滑處理后，當[δ]值趨于0，誤差趨于0。

[ρ（x）=ρ（x）+δ]? ? ? ? ? ? ? ? ? ? ? ? ?（3）

（2）對稱性修正

由公式（1）可知，KL散度具有完全非對稱性，即[D（ρi||ρj）≠D（ρj||ρi）]。所以在計算兩個物品之間的距離時需進行對稱性修正，對KL散度修正為KL距離[Ds（i，j）]，并用公式（4）進行兩個物品之間KL距離的計算。

[Ds（i，j）=（D（ρi||ρj）+D（ρj||ρi））/2]? ? ? ? ? ? ? ? ? ?（4）

（3）距離到相似度的轉換

由公式（1）的離散型隨機變量的KL距離，得到的基于KL距離的物品相似度計算方法如公式（5）所示。

[KL（i，j）=simKL（i，j）=11+Ds（i，j）]? ? ? ? ? ? ? （5）

由上式可知，KL距離越小，兩個物品之間相似度越高，KL距離越大，相似度越低。

2.2基于矩陣分解的ALS算法

ALS隱語義模型依據隱含特征獲取用戶的偏好特征，將某類偏好特征對應的物品進行推薦。根據奇異值原理，一個用戶評分矩陣[R（m×n）]可以分解為用戶特征矩陣[U（m×k）]、物品特征矩陣[V（k×n）]，矩陣[R（m×n）]可以用[UTV]的乘積近似表示。時間復雜度由[Ο（mn）]降為[Ο（（m+n）×k）]，節省存儲空間的同時能夠有效緩解矩陣稀疏性問題[7]。ALS處理過程如下。

（1）生成隨機的[U0]。本文選取隨機數方式初始化[U0]矩陣。

（2）固定[U0]，求解[V0]。此時，損失函數如公式（6）所示。

[f（U，V）=minU，V（u，i）∈k（Ru，i-（U（0）u）TVi）2+λ（U（0）u2+Vi2）]（6）

其中，[f（U，V）]函數只有一個變量[Vi]，[U0]是已知常量，對向量[Vi]求偏導[?f（U，V）?Vi=0]得到公式（7）。

[Vi=（UUT+λE）-1URTi]? ? ? ? ? ? ? ? ? ? ? ?（7）

其中，E為單位矩陣，[Ri]為物品[i]的歷史評分向量，[i∈1，n]，按照公式（7）求得[V1，V2，V3...Vn]，得到[V（0）]。

（3）固定[V（0）]，此時[V（0）]是已知常量，求解[U1]，求解過程類似步驟（2），損失函數變為公式（8）。

[f（U，V）=minU，V（u，i）∈k（Ru，i-（Uu）TV0i）2+λ（Uu2+V（0）i2）]? ?（8）

其中，[Uu]為變量，對向量[Uu]求偏導[?f（U，V）?Uu=0]，得到公式（9）。

[Uu=（VVT+λE）-1VRTu]? ? ? ? ? ? ? ? ? ? ? ? ?（9）

其中，[Ru]表示物品[i]的歷史評分向量，[i∈1，m]，按照公式（9）求得[U1，U2，U3...Un]，從而得到[U（0）]。

（4）反復迭代（2）、（3）步，終止條件為：算法誤差值收斂或迭代次數達到預先設定次數。求得最終[U、V]特征矩陣后，通過公式（10）預測評分。

[R=UTuVi]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （10）

最后，可根據余弦相似度計算公式得到任意兩個物品之間的相似性，公式如（11）所示。

[simCi，j=u∈UijRui*Ruju∈UijR2ui×u∈UijR2uj]? ? ? ? ? ? ? ? ? （11）

其中，[simCi，j]為物品[i]和[j]的相似度，[Uij]為參與評分所有用戶的集合;[Rui]為用戶[u]對物品[i]的評分，[Ruj]為用戶[u]對物品[j]的評分。

2.3 KL-ALS算法

由于評分數據中用戶與物品間的交互信息是不完整的，部分用戶未對相關物品給出評價，此時數據矩陣是稀疏的，隨著數據量的增大，這種稀疏性會越來越明顯[8]。ALS算法能將用戶-物品-評分矩陣分解為低階的用戶特征矩陣和物品特征矩陣，通過得到的物品特征矩陣可以計算出每兩個物品之間的余弦相似度，進而實現對物品的推薦，而這種相似度計算通常只考慮用戶之間的共同評分項，用KL散度計算物品相似性能夠充分利用數據集內所有物品的信息。通過融合以上兩種相似度計算方法可以更加準確地計算出物品之間的相似度，進而實現對物品的推薦。因此，本文提出的KL-ALS算法將這兩種物品相似度按一定權重混合得到具有兩者優點的混合相似度，如公式（12）所示。

[simmix（i，j）=λsimC（i，j）+（1-λ）simKL（i，j）]? ? ?（12）

其中[simmix（i，j）]表示相似度加權后的最終相似度，[simC（i，j）]為利用余弦相似度計算得到的物品相似度，[simKL]為利用KL距離計算得到的物品相似度。l表示調節參數，可以動態調節[simmix（i，j）]的權重。特別的是，當系統新生產一個物品信息數據時，可以僅使用[simKL]來表示[simmix（i，j）]。本文提出的KL-ALS推薦算法基于topN推薦，通過分析數據集中用戶評分數據信息，為用戶推薦N個自身喜歡的產品。

3實驗及分析

推薦算法的提升離不開大數據處理技術的運用，于是海量數據處理技術隨著并行計算思想的發展變得越來越能適應推薦系統的需要[9]。Spark是一種基于內存進行計算的分布式批處理引擎，它兼具延遲小和支持迭代計算的優勢，并且開發效率更高，容錯性也更好[10]，因此經常應用于復雜的推薦場景中。

3.1實驗環境配置

針對本文提出的KL-ALS算法，按如表1所示的環境下進行實驗，以驗證該算法的推薦性能。

3.2實驗數據

本實驗使用修正后的亞馬遜智能產品評論數據集（Consumer Reviews of Amazon Products），包含235位用戶對1521個產品的34655條評分記錄。每一條評分記錄包括用戶id、產品id、產品名字、評分數據、評分時間戳、標簽等。用戶id為1-235的連續整數，產品id為1-1521的連續整數，評分數字為1～5的連續整數，數值越大表示評分越高。本實驗按照8：2劃分訓練集與測試集。

3.3評價指標

準確率[（precision）]和召回率[（Recall）]是[topN]推薦的兩種主要評價指標[11]，數值越大、性能越好。計算如公式（13）、（14）所示。

[Precision（N）=1Uu∈ULN（u）N]? ? ? ? ? ? ?（13）

[RecallN=1Uu∈ULN（u）L（u）]? ? ? ? ? ? ? ? ?（14）

其中，[U]是測試集中所有用戶的集合;[LN（u）]是針對用戶[u]的[topN]推薦結果中，用戶[u]喜歡的產品;[L（u）]是測試集中用戶[u]評分過的所有產品。公式（13）和公式（14）都與[TopN]推薦個數[N]相關。

此外，F1值[12]通過統計[topN]推薦結果中含有至少[N]個相關產品的用戶所占比例，評價推薦算法推薦相關產品的能力，數值越大、性能越好。計算方法如公式（15）所示。

[F1=2×Precision×RecallPrecision+Recall]? ? ? ? ? ? ? ? ? ? ? ?（15）

3.4 實驗設計與結果分析

實驗1：確定參數[λ]的最佳取值

調節參數[λ]變化下，最終相似度[simmix（i，j）]的F1值變化情況，實驗結果如表2所示。

由表2可知，當[λ]為0.7時，[simmix（i，j）]的F1值達到最優。

實驗2：推薦個數變化下三種算法各項指標對比

驗證本文推薦算法（KL-ALS）的有效性，將其與傳統ALS協同過濾推薦算法和基于物品的協同過濾推薦（Item-CF）進行比較。根據實驗1中取得的最佳參數的值，得出實驗結果。

由圖1的三組圖可以看出，隨著推薦個數N的增加，基于物品的協同過濾推薦算法（ItemCF）、基于ALS的協同過濾推薦算法（ALS）以及基于KL散度的ALS推薦算法（KL-ALS），準確率均呈降低趨勢，召回率和F1值有明顯提高。然而，KL-ALS推薦算法相比于傳統ALS推薦算法和ItemCF推薦算法，在Precision、Recall和F1值三個指標上的提升較為明顯，進一步驗證了本文提出的混合推薦算法具有更好的推薦效果。

4結束語

文中提出了一種基于KL散度的ALS推薦算法（KL-ALS），在分布式大數據處理平臺Spark進行實驗。該算法將ALS算法計算的物品相似度和KL散度計算的物品相似度按照一定權重混合產生總體相似度，進而通過ALS算法訓練模型，在亞馬遜智能產品評價數據集驗證其有效性。實驗表明，本文提出的基于KL散度的ALS推薦算法（KL-ALS）優于其他類似方法，有效提高了整體的推薦質量。

參考文獻：

[1] 朱揚勇，孫婧.推薦系統研究進展[J].計算機科學與探索，2015，9（5）：513-525.

[2] Kimball A，Michels-Slettvet S，Bisciglia C.Cluster computing for web-scale data processing[J].ACM SIGCSE Bulletin，2008，40（1）：116-120.

[3] Ghemawat S，Gobioff H，Leung S T.The Google file system[C]//Proceedings of the nineteenth ACM symposium on Operating systems principles - SOSP '03.October 19-22，2003.Bolton Landing， N Y， USA. New York： ACM Press，2003：29-43.

[4] 許海玲，吳瀟，李曉東，等.互聯網推薦系統比較研究[J].軟件學報，2009，20（2）：350-362.

[5] 李現偉.基于Spark的推薦系統的研究[D].杭州：浙江理工大學，2017.

[6] Lee Y，Lee Y.Toward scalable Internet traffic measurement and analysis with Hadoop[J].ACM SIGCOMM Computer Communication Review，2013，43（1）：5-13.

[7] 李改，李磊.基于矩陣分解的協同過濾算法[J].計算機工程與應用，2011，47（30）：4-7.

[8] 張玉葉.基于協同過濾的電影推薦系統的設計與實現[J].電腦知識與技術，2019，15（6）：70-73.

[9] 胡俊，胡賢德，程家興.基于Spark的大數據混合計算模型[J].計算機系統應用，2015，24（4）：214-218.

[10] 陳恒.一種基于Spark的大規模語義數據分布式推理框架[J].計算機科學，2016，43（S2）：93-96.

[11] Bobadilla J，Ortega F，Hernando A，et al.A collaborative filtering approach to mitigate the new user cold start problem[J].Knowledge-Based Systems，2012，26：225-238.

[12] Patra B K，Launonen R， Ollikainen V， et al. Exploiting bhattacharyya similarity measure to diminish user cold-start problem in sparse data[C]//Discovery Science，2014：252-263.

【通聯編輯：唐一東】