融合評分相對差異的協(xié)同過濾推薦算法

王麗萍,傅 攀,邱飛岳,陳 宏

1(浙江工業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310023) 2(浙江工業(yè)大學(xué) 教育科學(xué)與技術(shù)學(xué)院,杭州 310023)

1 引 言

隨著計算機(jī)技術(shù)的發(fā)展,推薦系統(tǒng)被應(yīng)用在越來越多的領(lǐng)域[1],包括物品與資源推薦、學(xué)習(xí)資源推薦[2]以及醫(yī)療健康領(lǐng)域中的患者康復(fù)訓(xùn)練方案推薦[3]及患者表現(xiàn)預(yù)測[4]等.推薦系統(tǒng)正逐步影響著我們的生活,目前推薦算法大致可以分為基于協(xié)同過濾的推薦、基于內(nèi)容的推薦、基于知識的推薦等類型[5-8].基于協(xié)同過濾的推薦算法的核心思想之一是通過尋找目標(biāo)用戶的相似用戶,將他們感興趣的內(nèi)容推薦給目標(biāo)用戶.基于內(nèi)容的推薦算法通過提取物品特征與用戶偏好特征并通過相似度計算為用戶推薦相關(guān)項(xiàng)目.而基于知識的推薦算法則是根據(jù)特定領(lǐng)域的知識為用戶推薦相關(guān)內(nèi)容.

基于協(xié)同過濾的推薦算法是最經(jīng)典的同時也是目前最流行的推薦算法之一[5,8].基于協(xié)同過濾的推薦算法包括基于內(nèi)存的協(xié)同過濾和基于模型的協(xié)同過濾.基于內(nèi)存的協(xié)同過濾又可以分為基于用戶的協(xié)同過濾和基于物品的協(xié)同過濾,兩者的核心都是通過相似度計算完成推薦,區(qū)別在于前者計算用戶相似度,后者計算物品相似度.基于模型的協(xié)同過濾通過對用戶和項(xiàng)目的關(guān)系建立關(guān)聯(lián)模型,通過模型求解項(xiàng)目的評分預(yù)測實(shí)現(xiàn)推薦,常用的方法有矩陣分解和貝葉斯方法等.

雖然基于協(xié)同過濾的推薦算法在諸多方面呈現(xiàn)出巨大優(yōu)勢,如方法易于實(shí)現(xiàn)、不需要太多的領(lǐng)域知識,但是在不同的場景下依然面臨許多問題,如冷啟動、數(shù)據(jù)稀疏問題[5,7]等,這些都會影響推薦質(zhì)量.為了改善推薦質(zhì)量,眾多研究從不同角度出發(fā),充分挖掘潛在信息,使協(xié)同過濾推薦算法可以應(yīng)用于更加廣闊的場景.文獻(xiàn)[9]將用戶社會信任信息整合到非負(fù)矩陣分解(NMF)的框架中,緩解了數(shù)據(jù)稀疏和冷啟動問題.文獻(xiàn)[10]提出一種自適應(yīng)矩陣分解方法,自適應(yīng)地改變最小化函數(shù),獲取了更高的預(yù)測準(zhǔn)確率.文獻(xiàn)[11]考慮時間因素,將用戶評分形成評分序列,計算序列相似度.文獻(xiàn)[12]認(rèn)為用戶對物品的評分受情境影響,考慮用戶評分時的時間、地點(diǎn)等信息.文獻(xiàn)[13]引入了項(xiàng)目的標(biāo)簽并計算用戶-標(biāo)簽相似度,文獻(xiàn)[14]引入了用戶的人口統(tǒng)計屬性(年齡、性別、職業(yè)等)進(jìn)行相似度計算,并證明了引入的額外信息有助于提升推薦質(zhì)量.文獻(xiàn)[15]認(rèn)為可以利用間接鄰居信息來提高推薦質(zhì)量.除此之外,針對相似度計算的問題,文獻(xiàn)[16]基于KL散度提出一種非對稱的相似度計算方法,能有效提高稀疏數(shù)據(jù)集上的推薦精度.文獻(xiàn)[17]提出一種基于α散度的項(xiàng)目相似度計算方法,降低了對共同評分項(xiàng)的依賴.文獻(xiàn)[18]提出局部相似度的概念,認(rèn)為用戶對某些特定主題的物品更加感興趣.文獻(xiàn)[19]提出了一個基于L-P范數(shù)的相似度計算方式,可以有效改善推薦質(zhì)量.文獻(xiàn)[8]提出一種新的相似度計算方法,將相似度計算公式應(yīng)該滿足的條件轉(zhuǎn)化為數(shù)學(xué)方程,通過數(shù)學(xué)方法求解出相似度計算的表達(dá)式,最終證明基于新的相似度計算公式的推薦算法優(yōu)于許多其他具有代表性的方法.文獻(xiàn)[6]指出將帶有結(jié)構(gòu)信息的相似度與評分相似度進(jìn)行混合可以減少算法對鄰居數(shù)的依賴.

本文基于余弦相似度,提出一種融合評分相對差異的用戶間相似度計算方法,考慮評分之間的相對差異并引入放大系數(shù),更加有效地區(qū)分了用戶間差異,在非偏好評分場景中可以降低算法的預(yù)測誤差,與其他同類方法相比有一定競爭力.

2 相關(guān)工作

2.1 基于用戶的協(xié)同過濾算法

傳統(tǒng)的基于用戶的協(xié)同過濾算法主要涉及的對象有:用戶U,項(xiàng)目I,以及用戶對項(xiàng)目的歷史評分Rui.其主要步驟包括[5,17,20]:1)利用用戶對項(xiàng)目的歷史評分構(gòu)造用戶-項(xiàng)目評分矩陣,對于未知評分通常標(biāo)記為0;2)利用用戶-項(xiàng)目評分矩陣計算用戶間相似度;3)根據(jù)用戶間相似度選出與目標(biāo)用戶最相似的K個用戶作為鄰居集合;4)根據(jù)鄰居用戶的評分信息預(yù)測目標(biāo)用戶對未知項(xiàng)目的評分;5)將預(yù)測得分最高的N個項(xiàng)目推薦給目標(biāo)用戶.

表1 用戶-項(xiàng)目評分矩陣Table 1 User-item scoring matrix

如表 1所示,用戶-評分矩陣的行索引代表用戶集合用U表示,U={U1,U2,…,Um},列索引代表項(xiàng)目集合用I表示,I={I1,I2,…,In},Rmn代表用戶Um對項(xiàng)目In的評分.值得注意的是,用戶-項(xiàng)目評分未知時評分記為0,當(dāng)項(xiàng)目數(shù)量較多時,該矩陣將會是一個較為稀疏的矩陣.

用戶間相似度的計算主要依賴用戶評分向量,兩個用戶的評分向量之間的相似度將作為用戶相似度.如何準(zhǔn)確計算用戶間相似度是基于用戶的協(xié)同過濾推薦算法的關(guān)鍵步驟.

2.2 用戶相似度計算方法

常見的相似度計算方法主要有余弦相似度(COS,Cosine)[6-8]、皮爾遜相關(guān)系數(shù)(PCC,Pearson correlation coefficient)[6-8]、修正余弦相似度(ACOS,Adjusted cosine)[6-8,21],計算公式為:

(1)

(2)

(3)

PCC和ACOS考慮了用戶個人的評分習(xí)慣[7],有的用戶可能偏向給高分,而有的用戶偏向給低分.如式(2)、式(3)所示,PCC和ACOS會在原始評分的基礎(chǔ)上減去用戶評分均值后計算用戶間相似度.當(dāng)用戶的評分由用戶主觀偏好給出時,這樣的處理方式可以起到改善推薦質(zhì)量的作用.但是在一些非用戶偏好評分場景中,用戶-項(xiàng)目評分由特定的標(biāo)準(zhǔn)衡量得出時,例如學(xué)習(xí)項(xiàng)目表現(xiàn)評分、訓(xùn)練項(xiàng)目表現(xiàn)評分等,PCC和ACOS難以準(zhǔn)確衡量用戶間差異.

文獻(xiàn)[22]中指出余弦相似度不能準(zhǔn)確反映兩個用戶向量之間的相似度.如圖 1(a)所示,考慮向量間余弦相似度,向量A與向量B之間的相似度等于向量A與向量C之間的相似度.向量B與向量C的余弦相似度為1,無法體現(xiàn)出差異.

圖1 相似度示例Fig.1 Example of similarity

相似度計算方式還有杰卡德相似系數(shù)(Jaccard)[6-8]、均方差(MSD,Mean squared difference)[6-8],杰卡德相似系數(shù)只考慮用戶間共同評分項(xiàng)的數(shù)目,并沒有考慮用戶的具體評分.均方差考慮的是用戶共同評分項(xiàng)分值上的差異,非常依賴共同評分項(xiàng).具體計算公式為:

(4)

(5)

其中Iu和Iv分別表示用戶u和用戶v各自評過分的項(xiàng)目集合.

當(dāng)以上兩種相似度結(jié)合后可以得到新的相似度計算方法杰卡德均方差(JMSD)[6,23],計算公式為:

(6)

3 融合評分相對差異的協(xié)同過濾推薦算法

3.1 融合評分相對差異的相似度計算

皮爾遜相關(guān)系數(shù)和修正余弦相似度在非偏好評分的場景下不能準(zhǔn)確衡量用戶間相似度,余弦相似度不能衡量評分規(guī)模上的差異,基于評分差值的相似度又僅考慮共同評分項(xiàng)之間的差異,存在無法準(zhǔn)確衡量多個用戶間差異的情況.為了更加準(zhǔn)確地計算非用戶偏好評分場景下用戶間相似度的計算,降低評分預(yù)測誤差,以提高基于用戶的協(xié)同過濾算法的推薦質(zhì)量,使其能更好地應(yīng)用在更多場景中.本文基于余弦相似度并利用用戶評分分值相對差異提出一種改進(jìn)的用戶間相似度計算方式.

由于余弦相似度沒有考慮具體評分規(guī)模上的差異,所以改進(jìn)的相似度需要計算用戶評分間數(shù)值上的差異.又因?yàn)橛脩舸嬖谖丛u分項(xiàng)目,所以無法通過用戶對所有項(xiàng)目的評分計算用戶間評分差異,只能利用用戶共同評分項(xiàng)目.

利用用戶共同評分可以計算出評分之間的平均絕對差異,但是平均絕對差異容易受某個較大差異影響導(dǎo)致不能準(zhǔn)確衡量用戶評分間的整體差異,例如現(xiàn)有評分向量A=(1,1,4),B=(1,1,1),C=(2,3,1),A、B之間的平均絕對差異,B、C之間的平均絕對差異都為1.但是整體上看A和B有兩項(xiàng)相同評分,A和B之間的總體差異可能更小.所以平均絕對差異并不適合直接用于修正余弦相似度,本文利用共同評分之間的評分相對差異進(jìn)行余弦相似度修正.現(xiàn)給出相關(guān)定義與計算公式如下:

(7)

評分相對差異用于衡量用戶共同評分項(xiàng)之間的評分相對差異,表示為:

(8)

為了使用戶間差異滿足對稱性[18],對式(8)進(jìn)行調(diào)整,將評分絕對差異除以兩個目標(biāo)用戶共同評分項(xiàng)的對應(yīng)評分之和.

(9)

以用戶評分和作為除數(shù),會使差異變得不明顯.在式(9)的基礎(chǔ)上進(jìn)一步處理,以用戶評分均值作為除數(shù).一方面滿足對稱性,另一方面克服以用戶評分和作為除數(shù)導(dǎo)致差異不明顯的問題.最終評分相對差異計算公式為:

(10)

定義3.歸一化累計差異Duv

歸一化累計差異用于衡量用戶間差異.為了使用戶間差異可以進(jìn)行橫向?qū)Ρ?將評分相對差異向量的各位進(jìn)行累加得到累計差異,并作歸一化處理:

(11)

(12)

評分相對相似度,將用戶間差異轉(zhuǎn)換為相似度,計算公式為:

(13)

評分相對相似度,依賴共同評分項(xiàng),并不適合單獨(dú)作為用戶間相似度計算方式.而且當(dāng)用戶間沒有共同評分項(xiàng)時,通過該方式計算會得到用戶間差異為0,相似度為1,并不正確.

通常相似度的結(jié)合或修正手段有加權(quán)、相乘、特殊函數(shù)映射等[6,8,14].加權(quán)的方式通常難以得到準(zhǔn)確的權(quán)重系數(shù),需要進(jìn)行大量的實(shí)驗(yàn),特別是當(dāng)數(shù)據(jù)規(guī)模存在較大差異時,如何確定準(zhǔn)確的權(quán)重系數(shù)將會是一件困難的事.通過特殊的函數(shù)映射來對數(shù)據(jù)修正,通常需要特定的領(lǐng)域知識或基礎(chǔ)理論,否則難以找到適合的映射函數(shù).

本文提出的評分相對相似度適合采用相乘的方式與余弦相似度結(jié)合,以達(dá)到修正的目的.首先,余弦相似度在數(shù)據(jù)維度較高時具體值會比較小,而評分相對相似度相對偏大,如果采用加權(quán)的方式進(jìn)行修正,確定合適的權(quán)重系數(shù)以保證修正效果將非常困難.其次,當(dāng)用戶間沒有共同評分項(xiàng)時,余弦相似度為0,評分相對相似度為1,如果采用加權(quán)的方式進(jìn)行修正會導(dǎo)致明顯錯誤.而采用相乘的方式可以保證該極限情況下的兼容性,即兩個相似度相乘后結(jié)果仍為0.所以本文提出的評分相對相似度以相乘的形式對余弦相似度進(jìn)行修正是最佳選擇.

(14)

通過結(jié)合評分相對相似度,可以克服余弦相似度無法準(zhǔn)確衡量評分規(guī)模上的差異的缺點(diǎn).

表2給出的用戶評分示例為4個用戶在兩個項(xiàng)目上的評分,其中用戶U4無項(xiàng)目I2評分.表 3、表 4、表 5分別為針對表 2的余弦相似度、評分相對相似度以及改進(jìn)的用戶相似度.

表2 用戶-項(xiàng)目評分示例Table 2 Example of user-item scoring

通過U1,U2間的相似度和U1,U3間的相似度可以看出,改進(jìn)的相似度可以克服余弦相似度無法衡量規(guī)模上的差異的問

表3 用戶余弦相似度Table 3 COS similarity of users

題.如果僅考慮共同評分項(xiàng),U1,U4間的相似度和U2,U4間的相似度將會相同,但是假設(shè)U4對I2的評分已知為1,那么

表4 用戶評分相對相似度Table 4 ER similarity of users

U4和U1,U2間的相似度不同.從示例的相似度計算結(jié)果中可用看出,改進(jìn)后的相似度計算方法能更加有效地區(qū)分相似度.

表5 改進(jìn)的用戶相似度Table 5 COS-ER similarity of users

3.2 放大系數(shù)α

本文中的放大系數(shù)指在使用評分相對相似度對余弦相似度進(jìn)行修正時加入冪運(yùn)算,對應(yīng)冪運(yùn)算的指數(shù)即為放大系數(shù).文獻(xiàn)[6]中指出冪運(yùn)算可以擴(kuò)大數(shù)據(jù)差異,調(diào)整數(shù)據(jù)規(guī)模.為使最終的相似度計算更加有效,本文使用放大系數(shù)對評分相對相似度進(jìn)行調(diào)整.

所以,本文提出的改進(jìn)的用戶間相似度計算方法最終計算公式為:

(15)

其中α為放大系數(shù).

相對余弦相似度而言,由于評分相對相似度只基于共同評分項(xiàng)計算,偏差較小.通過放大系數(shù)α,可以擴(kuò)大相似度之間的差異.另外放大系數(shù)可以降低數(shù)據(jù)中的噪聲,使得小值被忽略[24].放大系數(shù)α的缺點(diǎn)是其最佳取值需要通過具體實(shí)驗(yàn)進(jìn)行對比分析后得出,而且冪運(yùn)算增加了計算量.

4 實(shí)驗(yàn)結(jié)果與分析

4.1 數(shù)據(jù)集

本文在兩組數(shù)據(jù)集上對算法有效性進(jìn)行實(shí)驗(yàn)驗(yàn)證,分別是MovieLens100K數(shù)據(jù)集和開放大學(xué)學(xué)習(xí)分析數(shù)據(jù)集(OULAD,Open University Learning Analytics dataset)[25].

MovieLens100K數(shù)據(jù)集包含943名用戶對1682部電影的評分記錄,共計100000條.該數(shù)據(jù)集中的用戶評分基于偏好,評分區(qū)間為1-5分,每個用戶至少為20部電影評過分,數(shù)據(jù)密度約為6.3%.

OULAD中包含了開放大學(xué)學(xué)生的學(xué)習(xí)表現(xiàn)數(shù)據(jù),其中包含學(xué)生各次學(xué)習(xí)任務(wù)表現(xiàn)評分,得分區(qū)間為1-100.該數(shù)據(jù)集中的評分是一種非偏好評分.本文實(shí)驗(yàn)取其中3000名學(xué)生學(xué)習(xí)數(shù)據(jù),包括105次學(xué)習(xí)任務(wù),保證每名學(xué)生至少有5次評分結(jié)果,共計23058條評分記錄,數(shù)據(jù)密度約7.3%.

本文采用Python作為編程語言,基于LensKit[26]工具包進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)數(shù)據(jù)按80%訓(xùn)練集,20%測試集進(jìn)行交叉驗(yàn)證.

4.2 評價指標(biāo)

推薦算法的主要目的是預(yù)測用戶在某些項(xiàng)目上的喜好或表現(xiàn).存在大量評價指標(biāo),兩個常用的指標(biāo)包括平均絕對誤差(MAE,Mean Absolute Error)[7,17]和均方根誤差(RMSE,Root Mean Squared Error)[7,17],公式定義如下:

(16)

(17)

其中T代表測試集中的用戶評分集合,Rui代表用戶真實(shí)評分,pui代表預(yù)測評分.

4.3 參數(shù)設(shè)定

本文提出的改進(jìn)的相似度計算公式存在可變參數(shù)α,α的具體值會影響相似度計算.取鄰居個數(shù)K=10,20,30,40,50,60,70分別在兩個數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),所提方法在不同α取值下MAE和RMSE結(jié)果如圖 2所示.

由圖2(a)、圖2(b)可以看出,在MovieLens100K數(shù)據(jù)集上,MAE、RMSE值隨著α從1遞增到7時整體呈下降趨勢,當(dāng)α遞增到5之后,MAE與RMSE都出現(xiàn)了個別上升的情況.為保證整體效果,在MovieLens100K數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)中α設(shè)置為6.

由圖 2(c)、圖 2(d)可以看出,在OULAD數(shù)據(jù)集上,MAE隨著α從1遞增到7時整體呈下降趨勢,在遞增到6后趨于穩(wěn)定.RMSE在α遞增到4之后下降緩慢,而且在6遞增到7出現(xiàn)上升的情況.所以本次在OULAD數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)中α同樣也設(shè)置為6.

圖2 MAE和RMSE隨值的變化Fig.2 MAE and RMSE changes with α value

4.4 結(jié)果與分析

本文提出的相似度計算方法記為COS-ER,將其與COS、MSD、Jaccard、JMSD、OS[8]、ACOS、PCC等相似度計算方法進(jìn)行對比實(shí)驗(yàn),鄰居數(shù)K取10,20,30,40,50,60,70.其中OS被證明是一種較好的相似度計算方法[8].

另外本次實(shí)驗(yàn)還對比了另一種合并的相似度計算方法記為COS-MSD,由余弦相似度和均方差合并而來,主要用于驗(yàn)證基于絕對誤差的MSD方法無法直接用于修正余弦相似度,COS-MSD方法計算公式如下:

(18)

各方法在MovieLens100K數(shù)據(jù)集上預(yù)測誤差指標(biāo)如圖 3、圖 4所示,在OULAD數(shù)據(jù)集上的誤差指標(biāo)如圖 5、圖 6所示,分別包含了各方法在不同鄰居個數(shù)K下的MAE和RMSE結(jié)果.

圖3 MovieLens100K數(shù)據(jù)集上不同算法MAE值對比Fig.3 Comparison of MAE values of different algorithms corresponding to MovieLens100K

如圖 3所示,在MovieLens100K數(shù)據(jù)集上,針對平均絕對誤差MAE,本文提出的相似度計算方法COS-ER較COS方法有一定改善,MAE下降比例約為5%,較Jaccard方法MAE下降比例約為5.5%,較MSD方法MAE下降比例約為2.5%,較OS方法MAE下降比例約為1.6%,較JMSD方法表現(xiàn)相似.直接由COS方法和MSD方法合并而來的COS-MSD方法表現(xiàn)較差,可見MSD方法無法用于修正余弦相似度.

如圖 4所示,在MovieLens100K數(shù)據(jù)集上,針對RMSE指標(biāo),本文提出的COS-ER方法明顯優(yōu)于JMSD,RMSE下降比例約為2.5%,說明COS-ER方法較JMSD方法更穩(wěn)定.同樣的,COS-ER方法也略優(yōu)于OS方法,RMSE下降比例約為1.4%.

圖4 MovieLens100K數(shù)據(jù)集上不同算法RMSE值對比Fig.4 Comparison of RMSE values of different algorithms corresponding to MovieLens100K

綜上所述,COS-ER方法在余弦相似度的基礎(chǔ)上額外考慮了評分規(guī)模上的差異,降低了預(yù)測誤差,但是由于沒有考慮用戶的評分偏好,所以在基于用戶偏好評分的MovieLens100K數(shù)據(jù)集上表現(xiàn)不及PCC和ACOS.

如圖 5所示,在OULAD數(shù)據(jù)集上,針對平均絕對誤差MAE,本文提出的相似度計算方法COS-ER較COS有較大改善,MAE下降比例約為24%,較MSD方法MAE下降比例約為28%,較Jaccard及JMSD方法MAE下降比例約為18%,較ACOS方法MAE下降比例約為7%,較PCC方法MAE下降比例約為4.7%,較OS方法表現(xiàn)相似.

圖5 OULAD數(shù)據(jù)集上不同算法MAE值對比Fig.5 Comparison of MAE values of different algorithms corresponding to OULAD

如圖 6所示,在OULAD數(shù)據(jù)集上,RMSE指標(biāo)所反映的結(jié)果和MAE指標(biāo)基本相同.但本文提出的方法COS-ER在RMSE指標(biāo)上略優(yōu)于OS方法,RMSE下降比例約1.2%.

圖6 OULAD數(shù)據(jù)集上不同算法RMSE值對比Fig.6 Comparison of RMSE values of different algorithms corresponding to OULAD

Jaccard、MSD、JMSD這3種方法極度依賴共同評分項(xiàng),當(dāng)用戶間共同評分?jǐn)?shù)量較少時難以準(zhǔn)確計算用戶間相似度,導(dǎo)致無法發(fā)現(xiàn)鄰居用戶,預(yù)測質(zhì)量較差.與ACOS和PCC相比,在OULAD數(shù)據(jù)集上COS-ER方法表現(xiàn)較好.由于OULAD數(shù)據(jù)集中用戶-項(xiàng)目評分為非偏好評分,ACOS和PCC并不能準(zhǔn)確計算用戶間相似度.COS-MSD方法的結(jié)果再次表明,直接將考慮絕對誤差的MSD方法和COS方法結(jié)合,并不能修正COS方法.

由上述實(shí)驗(yàn)結(jié)果對比分析可知本文提出的COS-ER方法通過評分相對相似度對余弦相似度進(jìn)行修正是有效可行的.由于基于余弦相似度并且考慮了評分規(guī)模上的差異,COS-ER方法可以更加準(zhǔn)確地區(qū)分用戶間相似度.在偏好評分的場景下較部分傳統(tǒng)方法效果更好,并且在非偏好評分的場景下,可以在一定程度上降低預(yù)測誤差,提高推薦質(zhì)量.

5 總 結(jié)

本文基于余弦相似度提出一種融合評分相對差異的協(xié)同過濾推薦算法,更加適用于非偏好評分場景,利用評分間相對差異以及放大系數(shù)對余弦相似度進(jìn)行修正,可以更好地計算用戶間相似度.通過在兩組不同類型的數(shù)據(jù)集上進(jìn)行對比實(shí)驗(yàn),結(jié)果表明本文提出的方法在偏好評分的場景下,效果優(yōu)于多數(shù)方法,在非偏好評分場景下,效果優(yōu)于所有對比方法,可以降低預(yù)測誤差,提高推薦質(zhì)量.