基于KL散度的ALS推薦算法

韓遠(yuǎn)達(dá)

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

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

中圖分類號(hào)：TP399? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2022）12-0004-03

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

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

1 相關(guān)研究

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

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

2.1KL散度

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

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

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

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

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

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

（1）平滑處理

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

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

（2）對(duì)稱性修正

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

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

（3）距離到相似度的轉(zhuǎn)換

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

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

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

2.2基于矩陣分解的ALS算法

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

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

（2）固定[U0]，求解[V0]。此時(shí)，損失函數(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ù)只有一個(gè)變量[Vi]，[U0]是已知常量，對(duì)向量[Vi]求偏導(dǎo)[?f（U，V）?Vi=0]得到公式（7）。

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

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

（3）固定[V（0）]，此時(shí)[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]為變量，對(duì)向量[Uu]求偏導(dǎo)[?f（U，V）?Uu=0]，得到公式（9）。

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

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

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

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

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

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

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

2.3 KL-ALS算法

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

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

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

3實(shí)驗(yàn)及分析

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

3.1實(shí)驗(yàn)環(huán)境配置

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

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

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

3.3評(píng)價(jià)指標(biāo)

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

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

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

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

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

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

3.4 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

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

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

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

實(shí)驗(yàn)2：推薦個(gè)數(shù)變化下三種算法各項(xiàng)指標(biāo)對(duì)比

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

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

4結(jié)束語

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

參考文獻(xiàn)：

[1] 朱揚(yáng)勇，孫婧.推薦系統(tǒng)研究進(jìn)展[J].計(jì)算機(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é)報(bào)，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].計(jì)算機(jī)工程與應(yīng)用，2011，47（30）：4-7.

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

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

[10] 陳恒.一種基于Spark的大規(guī)模語義數(shù)據(jù)分布式推理框架[J].計(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)編輯：唐一東】