融合核密度估計和奇異值分解的多樣化推薦算法

李衛(wèi)疆,羅潘虎

(昆明理工大學 信息工程與自動化學院,昆明 650500)

1 引 言

隨著互聯(lián)網(wǎng)的發(fā)展,互聯(lián)網(wǎng)信息的爆炸式增長給人們帶來了嚴重的信息過載,比如電影、書籍、音樂等方面,如何從大量的資源池中準確的找出用戶感興趣的信息是各大互聯(lián)網(wǎng)企業(yè)的研究焦點.以電影推薦為例,電影市場每年都會推出數(shù)以千計的電影,然而如此多的電影中符合某個用戶需求的并沒有多少,這使得用戶很難快速找出他喜歡的影片,而隨著時間的推移,積累的影片數(shù)量越來越多,用戶就更難尋找到他所感興趣的影片,在這種背景下,推薦系統(tǒng)應運而生,目前,推薦系統(tǒng)的主要工作內(nèi)容是通過信息過濾技術(shù)向用戶準確的推送用戶感興趣的信息,避免用戶在信息海中浪費時間[1,2].

現(xiàn)今的推薦算法大多關(guān)注推薦的準確性上,但在實際中,單純的提高準確率有時并不能提高用戶對物品推薦的滿意度[3],一方面,這使得展示給用戶的信息過于單一,展現(xiàn)在用戶面前的很多是當前時期的熱門物品,雖然這提高的準確率,但用戶很可能從其它渠道知道了這個物品,比如他的朋友告訴他或者是滿大街的海報等等,這樣的推薦顯然是無效的.另一方面,會使得推薦系統(tǒng)的數(shù)據(jù)集中于熱門物品,這將導致嚴重的馬太效應,致使資源整體曝光率變得極低,熱門的物品愈發(fā)熱門,冷門的更加冷門,從而很多用戶感興趣的信息埋沒在龐大的資源池中,因為用戶感興趣的信息不僅僅只有當前熱門信息[4,5].提高物品的多樣化推薦不僅對提升用戶滿意度有幫助,它對網(wǎng)上商店的影響也非常大,根據(jù)帕累托原理可以知道,少數(shù)的商品占據(jù)了大量的市場空間,如果推薦系統(tǒng)能把更多的長尾商品展示出來,商品制造商會更有動力去豐富商品的種類數(shù)量[6,7].如何能讓更多的信息展示在用戶面前,如何發(fā)現(xiàn)用戶感興趣的長尾信息,提高推薦的多樣性,在今后將是研究推薦算法性能的焦點之一.

推薦結(jié)果多樣性研究面臨很多問題,準確率與覆蓋率是一對相互矛盾的指標,當準確率較高時覆蓋率會相對低,反之亦然,因此目前面臨最大的難題便是如何即保證準確性不降低而又能提高推薦多樣性.

針對此問題,本文通過興趣核密度估計的方式挖掘用戶潛在興趣,尋找與用戶興趣相近的鄰居,由于在同一興趣集合下的物品較多,其鄰居在該興趣集合中選擇的物品在很大可能上也不一樣,由此產(chǎn)生的推薦結(jié)果會跳出熱門物品影響,當用戶足夠多的時候,在該興趣集合下的所有項目都可能被推薦出來,從而提高推薦結(jié)果總體多樣性,得到推薦預評分后填充到SVD矩陣中解決數(shù)據(jù)稀疏問題.SVD算法具有推薦準確率高的優(yōu)點,可以用其來保證推薦的準確率.

2 相關(guān)工作

一個好的推薦系統(tǒng)應當在保證推薦準確率的前提下充分提高資源池中物品的曝光率,如果推薦系統(tǒng)只以提高準確率為目標,隨著推薦數(shù)據(jù)的積累,長期以后推薦系統(tǒng)將只會推薦當前熱點,使得推薦結(jié)果過于單一.

多樣化推薦研究分為個體多樣性和總體多樣性兩個方面,個體多樣性通過對用戶給出的推薦列表計算,通過考量推薦列表中物品的相似程度來確定列表多樣性程度[8,9],其主要目的是避免給用戶推薦的物品相似度過高,給單個用戶推薦相似度過高的物品會導致無效推薦,比如一個用戶喜歡看戰(zhàn)爭片,如果一個推薦系統(tǒng)采用傳統(tǒng)協(xié)同過濾的方法來進行推薦,那么它會盡可能多的推薦當前的熱門戰(zhàn)爭片,而一段相對短的時間內(nèi)熱門戰(zhàn)爭片是有限的,用戶可能全部都看過,這時候給出的推薦列表就是無效推薦.總體多樣性是指在資源池中物品的曝光數(shù)量,總體多樣性高可以為用戶提供更多的選擇,很多優(yōu)秀的電影作品用戶自己并不能挖掘出來,這些物品可能是很多年以前的,但是它恰巧是用戶所需要的,總體多樣性一般用覆蓋率來衡量,即已推薦出的物品占物品總數(shù)的百分比,本文的工作主要在提高推薦總體多樣性.

現(xiàn)有的多樣化推薦算法主要有兩個研究方向,第一種是使用現(xiàn)有的協(xié)同過濾算法來計算預測評分,然后對得出的推薦候選集進行重新排序,按比例取出一些長尾項目推薦給用戶,第二種方法是改進計算預測評分的方法,通過一些特殊方法提高低流行度項目的優(yōu)先級.

Adomavicius G[10]等在2012年根據(jù)物品的流行度對推薦列表進行重排,首先根據(jù)物品的預測評分進行排序,然后設定流行度閾值,刪除流行度高于此閾值的項目得出推薦列表,此算法對提高推薦結(jié)果總體多樣性有一定幫助,但是僅僅使用用戶的行為數(shù)據(jù)作為推薦候選集,推薦結(jié)果往往還是會偏向熱門物品;Zhang M[9]等人提出了一種基于聚類的的多樣化算法,首先,實驗表明該算法在準確率和多樣性方面取得比較好的平衡,但該算法只考慮了用戶興趣范圍內(nèi)的物品,對于用戶興趣之外的物品不會被推薦;Mcnee S M[11]提出了一種貪心選擇算法,追求最大化推薦列表的多樣化程度,該方法以常用預測評分方法為基礎,在組織推薦列表時加以考慮物品與推薦列表中其它物品的相異程度,雖然該方法在多樣化方面的性能優(yōu)秀,但由于不考慮用戶興趣分布導致準確率太低;Adomavicius G[12]等人在2011提出了一種基于圖論的算法,首先用常用的系統(tǒng)過濾算法得出候選集,并計算他們的預測得分,然后把用戶集合和其對應的候選物品集合分為兩組建立二分圖,對應的預測評分為用戶頂點到對應推薦物品頂點的權(quán)值,最后通過二分圖最大匹配的方式得出每個用戶的推薦結(jié)果集合,該方法的精確度和多樣化程度取決于訓練集中每個用戶的物品數(shù),用戶的物品數(shù)越多,推薦結(jié)果多樣化程度就越高,但它的精度就會相應降低.

針對以上問題,本文提出了的KDE-SVD算法,該算法是通過預評分公式(6)計算得到的預評分來提高低流行度物品的優(yōu)先級來實現(xiàn)多樣化推薦的,與其它算法相比,該算法只需要用到用戶對物品的評分和物品的基本特征屬性,對于在不容易采集用戶或物品更多信息的情況下比較方便和實用,該算法的第一個部分是從與用戶興趣相近的鄰居那里獲得鄰居的物品集合,然后對當前用戶不曾擁有的物品進行預評分,在預評分的過程中就已經(jīng)對低流行度的物品提高了它的優(yōu)先級,所以它是獨立的一部分,因此,用戶興趣估計這部分可以和其它推薦精度高而多樣化程度差的算法結(jié)合使用.

3 KDE-SVD模型

3.1 核密度估計基本概念

核密度估計是統(tǒng)計學上一種常用于估算樣本概率密度的方法,是對直方圖的自然拓展,通過擬合函數(shù)曲線的方式消除直方圖圖像不連續(xù)和bins對圖像觀察的影響,如圖1、圖2所示,圖1bins過大掩蓋了數(shù)據(jù)細節(jié),而圖2通過減小bins顯示出了數(shù)據(jù)細節(jié),然而,bins不可能無限減小,這時由數(shù)據(jù)擬合出的函數(shù)曲線便可很好的描述數(shù)據(jù)分布.

圖1 學生成績統(tǒng)計圖1Fig.1 Student achievement statistics 1

3.2 基于核密度估計的評分預測

定義1.設數(shù)據(jù)集{X|x1,x2,x3,…,xn}為X的獨立同分布隨機變量,且它服從的密度分布函數(shù)為f(x),其中x∈X,定義函數(shù):

(1)

公式(1)稱為函數(shù)f(x)的核密度估計,其中,參數(shù)h為帶寬,用于,通常是一個預先給定的正數(shù),φ(°) 為該核密度估計的核函數(shù).

定義2.一件物品在分類上可以同時屬于多種類屬,比如一部電影可以同時屬于戰(zhàn)爭片與愛情片,假設C={c1,c2,c3,…,cn}為物品空間的所有類別集合,物品i的所屬類別C={c1,c2,c4,c5},物品j的所屬類別C={c2,c3,c5,c6},此時物品i與物品j之間有兩個相同的類別屬性,即它們之間有一定的共同點,這種共同點稱為類別相似度,它的計算公式定義為:

(2)

定義兩個物品類別間距離公式為:

di,j=1-simc(i,j)

di,j越大表示兩個物品的共同點越少.

進行用戶興趣分布計算時,核函數(shù)的對密度估計影響較小[13],為方便計算,本文選用高斯核函數(shù)作為本文核密度估計的核函數(shù).

(3)

用戶u在高斯核函數(shù)下的興趣分布公式為:

(4)

其中Iu表示用戶u評價過的物品,I表示整個物品空間,ru,i表示用戶u對物品i的評分,h為核密度估計的帶寬.

圖2 學生成績統(tǒng)計圖2Fig.2 Student achievement statistics 2

在興趣分布屬于概率分布,無法用計算距離的方式計算用戶之間的相似度.在信息論中,往往使用KL散度計算兩個概率間的差異,由于KL散度不具備對稱性,用于計算用戶相似度時需先對稱化,兩個用戶間的相似度計算公式定義為:

(5)

D(Pu‖Pv)為用戶u和用戶v之間的KL散度.

根根據(jù)由KL散度計算的用戶相似度,便可用近鄰算法即可獲得離目標用戶最近的鄰居集,然后用相似度作為權(quán)重加權(quán)計算鄰居用戶對目標物品的評分,該值即可作為目標用戶對目標物品的預測評分,預測評分公式定義為:

(6)

其中,μ為用戶的評分平均值.

3.3 帶寬及其計算

核核密度估計中的帶寬指的是核函數(shù)的方差,帶寬大小對核密度估計的影響要遠大于核函數(shù)種類的影響[14],當帶寬過小時得到的概率密度曲線極其陡峭,雖然能最大限度地描述樣本分布,但卻不利于觀察樣本的分布特點,當帶寬過大時得到的概率密度函數(shù)曲線過于平滑,會掩蓋樣本分布細節(jié).

在數(shù)據(jù)樣本確定的情況下,可以先計算樣本的概率密度,然后使用最小化L2風險函數(shù)(MISE)的方式求得最佳帶寬h,設:

(7)

在Weak-Assumptions的情況下有:

(8)

其中AMISE為漸進均平方積分誤差[15],從而有:

(9)

用求AMISE(h)一階導數(shù)0點的方式獲取AMISE(h)的最小值,其最小值即為MISE(h)的最小值,根據(jù)公式(9)有:

(10)

得:

(11)

3.4 融合核密度估計的SVD的推薦算法

在3.2節(jié)中,我們使用核密度估計的方式估計用戶興趣分布,通過匹配用戶之間興趣相似度的差異程度獲取與用戶興趣相似的鄰居,但這樣產(chǎn)生的鄰居用戶是興趣相似的鄰居而不是行為相似的鄰居,比如用戶i和用戶j都喜歡看戰(zhàn)爭電影,他們此時是興趣相似的鄰居,但能把用戶i看過的戰(zhàn)爭電影全部推薦給用戶j嗎,這顯然是不行的,雖然都是戰(zhàn)爭電影,但電影的劇情、演員等因素仍然會極大影響一個用戶的行為,由此產(chǎn)生的推薦列表多樣性較高但精度相對低,因此需要結(jié)合奇異值分解算法提高推薦結(jié)果的精確度.

奇異值分解算法(SVD)是推薦系統(tǒng)中常用的一種方法,具有速度快、精度高等優(yōu)點,是目前最流行的推薦算法之一.對于任意一個Rm×n(m>n)矩陣,均可分解成Rm×n=U×Σ×V,其中U為m×m的矩陣,Σ為m×n的矩陣,其為一個對角矩陣,除了對角線外,其余地方值均為0,對角線上的值稱為奇異值,V為n×n的矩陣,U和V均為正交矩陣.

4 實驗結(jié)果及分析

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

本文實驗使用的數(shù)據(jù)集是GroupLens提供的ML-1M數(shù)據(jù)集進行對算法的評估.該數(shù)據(jù)集一共有1000209個評分,由6040名用戶對3962部電影評分而產(chǎn)生,每名用戶至少有20個評分,評分值為1-5的整數(shù),電影共分為19大類,整個用戶-評分矩陣填充率為4.1%.實驗時隨機抽取80%的用戶作為訓練數(shù)據(jù),其余作為測試數(shù)據(jù).

4.2 評價指標

本文采用準確率(Precision)和覆蓋率(Coverage)兩個指標來評價本文模型.令P(u)為模型給用戶的推薦列表,Q(u)為用戶的實際看過的電影列表.

準確率用于評價該模型推薦的準確度,計算公式為:

(12)

覆蓋率是衡量推薦系統(tǒng)對長尾物品發(fā)掘能力的指標,覆蓋率越大表示物品庫中被推薦的物品個數(shù)越多,其計算公式為:

(13)

其中|∪u∈UP(u)|表示推薦系統(tǒng)推薦出的電影集合,集合中元素互斥,|I|為電影總數(shù).

4.3 P-C值

在推薦系統(tǒng)中,對于準確率和覆蓋率到目前還沒有統(tǒng)一的綜合評價方法,為了在準確度和覆蓋率找到比較好的平衡點,受F值的啟發(fā),本文提出了P-C值的概念,P-C值計算公式為:

(14)

其中,α為調(diào)節(jié)P和C重要程度的參數(shù),P為準確率,C為覆蓋率.

4.4 相似度計算

在協(xié)同過濾中,相似度算法用于計算用戶之間的相似度,常用的有余弦相似度、歐氏距離等,本實驗采用余弦相似度作為相似度計算方式,其公式為:

(15)

其中vi、vj分別表示用戶i和用戶j在用戶-評分矩陣SVD分解后而得的Vm×m向量中的位置向量,vi,k、vj,k分別為用戶i和用戶j在m維空間中第k維的值.

余弦相似度在計算用戶相似度時并沒有考慮用戶的評分習慣.因此本文對余弦相似度算法進行改進,對用戶的每個評分都減去他的評分平均值,改進后的余弦相似度公式為:

(16)

4.5 實驗分析

實驗1.圖3為使用核密度估計對三位用戶估計其興趣分布的興趣分布函數(shù)圖,從圖中可以看出,用戶3和用戶100的興趣分布比較相近,和用戶5差別較大.在數(shù)據(jù)集中,用戶3和用戶100喜愛的電影類型較為相似,與用戶5差別較大,與函數(shù)圖像所展示的情況一致,因此本文提出的用戶興趣分布估計方法可以比較好的估計用戶興趣分布.

圖3 三個用戶的興趣分布函數(shù)圖Fig.3 Three users′ interest distribution function graph

實驗2.本組實驗意在考量在不同的帶寬下,核函數(shù)的差異和對實驗結(jié)果的影響,由于推薦列表的長度和Σk×k維度也會影響推薦的準確度,因此本實驗的結(jié)果為針對不同核函數(shù)和不同帶寬調(diào)節(jié)推薦列表參數(shù)和Σk×k維度參數(shù)達到最優(yōu)的結(jié)果,Gaussian Kernel與Cosin Kernel做對比得到的結(jié)果如下:

圖4 兩種核函數(shù)隨帶寬的變化情況Fig.4 Variation of two kernel functions with bandwidth

從圖4中可以看到,帶寬在0.5到1.4之間變化時,兩個核函數(shù)在最高點處的差距非常小,Cosin Kernel核函數(shù)在帶寬為0.7處取得最大準確率0.292,Gaussian Kernel核函數(shù)在帶寬為1.0處取得最大準確率0.311.兩條曲線走勢基本相同,Cosin Kernel對應的折線從0.5到0.7時持續(xù)上漲,0.7以后下降非常迅速,Gaussian Kernel對應的折線在0.5到1.0之間持續(xù)上漲,當帶寬大于1.0時,開始下降,但下降幅度沒有Cosin Kernel對應的折線陡峭,兩條折線的最高點處所對應的帶寬與3.3節(jié)所述方法計算而得的帶寬差值很小,驗證了3.3節(jié)所述帶寬計算方法真實有效.隨著帶寬的增長,兩個核函數(shù)對應的準確率有越來越低的趨勢,這是因為帶寬過大時會掩蓋掉大量的數(shù)據(jù)分布細節(jié),導致對用戶某個項目的興趣進行估計時產(chǎn)生很大的泛化.

實驗3.本組實驗意在對比本文算法與其它算法之間的準確率和覆蓋率,評估本文算法性能.為此,本文算法將與SVD(Singular Value Decomposition)、PS[7](Probabilistic Selection)、PSVM[16]三種算法進行比較,表1為本組實驗結(jié)果.

SVD:SVD是矩陣分解類算法中最有代表的算法之一.該算法的提出是為了解決推薦準確率差問題,在覆蓋率上考慮較少,本文算法便是在SVD的基礎上進行改進,提高其覆蓋率.

PS:PS是采用概率選擇的方式對初始排序列表進行抽選生成推薦列表,對于一個項目,先按一定概率確定它是不是需要推薦的類型,再按一定的概率確定它是不是要推薦的項目,該算法在準確率和覆蓋率上有比較好的平衡.

PSVM:該模型是LAD模型與結(jié)構(gòu)化支持向量機SSVM相融合的一個模型,它在組織推薦列表時充分考慮了時間推移對用戶興趣的變化,在準確率和覆蓋率上也有比較好的平衡.表1中的四組實驗結(jié)果均為通過參數(shù)對準確率與覆蓋率進行平衡得比較好的結(jié)果.在三組實驗中,均取推薦列表長度為70,以此消除召回率不同而帶來的實驗誤差.

表1 三種算法實驗結(jié)果對比
Table 1 Comparison of experimental results of three algorithms

KDE-SVDSVDPSPSVMPrecision0.3110.3350.2890.316Diversity0.8750.6210.8160.856P-C0.4590.4350.4270.466

從表1中可以看到,KDE-SVD算法由于在推薦時充分考慮了用戶的興趣分布,相比于只考慮用戶評分的SVD算法雖然Precision有小幅度降低,但Coverage卻有大幅度提升,說明在推薦過程中考慮用戶興趣分布可以得到更好的推薦效果.和PS對比,KDE-SVD比PS有更好的準確率和覆蓋率,從P-C值可以看出KDE-SVD在準確率與覆蓋率的平衡上也明顯比PS好,.和PSVM相比,雖然在準確率方面略低,但在覆蓋率上略有優(yōu)勢.綜上三點說明本文提出的融合核密度估計與奇異值分解推薦算法可以提高推薦系統(tǒng)在準確率與覆蓋率方面的平衡能力,可以在精度不明顯下降的情況下大幅提高覆蓋率.

5 總 結(jié)

隨著互聯(lián)網(wǎng)的發(fā)展,推薦系統(tǒng)作為互聯(lián)網(wǎng)個性化服務的主要實現(xiàn)方式受到越來越多的研究者的關(guān)注.針對如何提高總體覆蓋率,本文用核密度估計的方式估計用戶的興趣分布,然后用與戶興趣分布相似的鄰居的評分對當前用戶未評分的物品進行預測評分,以此提高物品曝光率,在同一興趣下有很多物品,不同的用戶在一個興趣下選擇的物品往往是不一樣的,在用戶量大的情況下,任何一個物品都可能被推薦出來.針對如何保證準確率不明顯下降問題,本文將上階段得到的預測評分填入用戶-評分矩陣,然后用推薦算法中準確率高的SVD算法對其進行分解,在SVD分解而得的m維空間中用相似度算法找出對當前用戶行為相似的鄰居,此時得出鄰居即是興趣相似和行為相似調(diào)和的鄰居.在真實數(shù)據(jù)集上實驗表明,本文算法可以保證精確率較高的情況下提高總體覆蓋率.在本文,僅考慮了總體多樣性的提升,而在個體多樣性考慮較少,因此,下一步將研究如何提升個體多樣性,提高推薦質(zhì)量.