基于KL散度的ALS推薦算法

韓遠達

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

關(guān)鍵詞：KL散度;ALS算法;推薦算法;相似度;協(xié)同過濾

中圖分類號：TP399? ? ? 文獻標(biāo)識碼：A

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

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

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

1 相關(guān)研究

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

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

2.1KL散度

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

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

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

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

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

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

（1）平滑處理

為確保KL散度對智能產(chǎn)品數(shù)據(jù)的適用性，即保證[ρ（x）>0]，需對[ρ（x）]平滑處理，如公式（3）所示。其中[0<δ<1]，在平滑處理后，當(dāng)[δ]值趨于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）距離到相似度的轉(zhuǎn)換

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

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

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

2.2基于矩陣分解的ALS算法

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

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

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

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

其中，[f（U，V）]函數(shù)只有一個變量[Vi]，[U0]是已知常量，對向量[Vi]求偏導(dǎo)[?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），損失函數(shù)變?yōu)楣剑?）。

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

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

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

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

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

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

最后，可根據(jù)余弦相似度計算公式得到任意兩個物品之間的相似性，公式如（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算法

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

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

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

3實驗及分析

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

3.1實驗環(huán)境配置

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

3.2實驗數(shù)據(jù)

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

3.3評價指標(biāo)

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

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

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

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

此外，F(xiàn)1值[12]通過統(tǒng)計[topN]推薦結(jié)果中含有至少[N]個相關(guān)產(chǎn)品的用戶所占比例，評價推薦算法推薦相關(guān)產(chǎn)品的能力，數(shù)值越大、性能越好。計算方法如公式（15）所示。

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

3.4 實驗設(shè)計與結(jié)果分析

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

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

由表2可知，當(dāng)[λ]為0.7時，[simmix（i，j）]的F1值達到最優(yōu)。

實驗2：推薦個數(shù)變化下三種算法各項指標(biāo)對比

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

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

4結(jié)束語

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

參考文獻：

[1] 朱揚勇，孫婧.推薦系統(tǒng)研究進展[J].計算機科學(xué)與探索，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] 許海玲，吳瀟，李曉東，等.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J].軟件學(xué)報，2009，20（2）：350-362.

[5] 李現(xiàn)偉.基于Spark的推薦系統(tǒng)的研究[D].杭州：浙江理工大學(xué)，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] 李改，李磊.基于矩陣分解的協(xié)同過濾算法[J].計算機工程與應(yīng)用，2011，47（30）：4-7.

[8] 張玉葉.基于協(xié)同過濾的電影推薦系統(tǒng)的設(shè)計與實現(xiàn)[J].電腦知識與技術(shù)，2019，15（6）：70-73.

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

[10] 陳恒.一種基于Spark的大規(guī)模語義數(shù)據(jù)分布式推理框架[J].計算機科學(xué)，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.

【通聯(lián)編輯：唐一東】