一種面向稀疏數(shù)據(jù)的比率相似度計(jì)算方法

馮軍美,馮曉毅,夏召?gòu)?qiáng),彭進(jìn)業(yè),姚 娟

(1.西北工業(yè)大學(xué) 電子信息學(xué)院, 陜西 西安 710072;2.西北大學(xué) 信息科學(xué)與技術(shù)學(xué)院,陜西 西安 710127)

近年來(lái),推薦系統(tǒng)[1]越來(lái)越多地應(yīng)用在人們的日常生活中,根據(jù)用戶的興趣愛(ài)好、購(gòu)買記錄等信息為用戶提供推薦。在推薦系統(tǒng)中,推薦算法在整個(gè)系統(tǒng)中是必不可少的。一般來(lái)講,推薦算法分為4類:基于人口統(tǒng)計(jì)學(xué)的推薦[2]、基于內(nèi)容的推薦[3]、協(xié)同過(guò)濾推薦[4]和混合推薦[5],其中,最常用的推薦算法是協(xié)同過(guò)濾推薦算法,且基于內(nèi)存的推薦算法[6]和基于模型的推薦算法[7]是協(xié)同過(guò)濾推薦算法中的兩個(gè)子類別?；趦?nèi)存的推薦方法主要包括相似度計(jì)算和評(píng)分預(yù)測(cè)兩個(gè)步驟。由于數(shù)據(jù)稀疏[8]和冷啟動(dòng)問(wèn)題[9-10]在推薦系統(tǒng)中普遍存在,基于內(nèi)存的協(xié)同過(guò)濾推薦方法中的數(shù)據(jù)稀疏問(wèn)題是本文的研究重點(diǎn)。

目前,皮爾遜相關(guān)系數(shù)(Pearson correlation coefficient, PCC)和杰卡德系數(shù)(Jaccard)[6]是傳統(tǒng)的基于內(nèi)存的協(xié)同過(guò)濾推薦方法中比較常用的相似度計(jì)算方法。上述兩種方法的相似度均通過(guò)用戶之間共同評(píng)分項(xiàng)的評(píng)分?jǐn)?shù)據(jù)來(lái)計(jì)算,但在稀疏的數(shù)據(jù)集上,共同評(píng)分項(xiàng)很少或者不存在,因此無(wú)法進(jìn)行精準(zhǔn)的推薦。針對(duì)這個(gè)問(wèn)題,程偉杰等人[11]提出了一種利用用戶的全部評(píng)分?jǐn)?shù)據(jù)來(lái)提高推薦系統(tǒng)精度的方法,該方法借助動(dòng)態(tài)權(quán)重將基于用戶全部評(píng)分的相似度與皮爾遜相關(guān)系數(shù)進(jìn)行混合,并根據(jù)混合后的相似度和最近鄰的評(píng)分?jǐn)?shù)據(jù)來(lái)預(yù)測(cè)用戶對(duì)項(xiàng)目的評(píng)分大小。Guo等人[12]利用多種隱式反饋信息來(lái)解決推薦系統(tǒng)中的數(shù)據(jù)稀疏問(wèn)題。Suryakant等人[13]考慮到傳統(tǒng)的相似度計(jì)算方法存在數(shù)據(jù)稀疏問(wèn)題,將3種相似度方法包括余弦相似度、杰卡德系數(shù)和平均散度進(jìn)行線性組合來(lái)提高預(yù)測(cè)精度。

一種面向稀疏數(shù)據(jù)的基于用戶的比率相似度計(jì)算方法在本文中提出。與現(xiàn)有的解決稀疏問(wèn)題的推薦方法不同的是,該方法直接根據(jù)用戶全部的評(píng)分?jǐn)?shù)據(jù)來(lái)計(jì)算用戶之間的相似度,根據(jù)相似度進(jìn)行評(píng)分預(yù)測(cè)。解決了在稀疏數(shù)據(jù)的情況下傳統(tǒng)的基于內(nèi)存的協(xié)同過(guò)濾推薦算法無(wú)法計(jì)算相似度的問(wèn)題,同時(shí)也提高了推薦算法的推薦精度。

1 傳統(tǒng)的協(xié)同過(guò)濾推薦算法

基于用戶的協(xié)同過(guò)濾推薦算法和基于項(xiàng)目的協(xié)同過(guò)濾推薦算法是基于內(nèi)存的協(xié)同過(guò)濾推薦算法根據(jù)相似度計(jì)算對(duì)象的不同而劃分的兩種方法。本文把基于用戶的協(xié)同過(guò)濾推薦算法作為主要的研究對(duì)象。

常用的相似度計(jì)算方法包括:PCC和Jaccard,上述兩種方法均根據(jù)用戶(項(xiàng)目)之間的共同評(píng)分項(xiàng)的評(píng)分?jǐn)?shù)據(jù)進(jìn)行相似度計(jì)算。兩用戶u和v之間的PCC的計(jì)算公式為

sim(u,v)PCC=

(1)

2 面向稀疏數(shù)據(jù)的協(xié)同過(guò)濾推薦算法

在實(shí)際的推薦系統(tǒng)中,用戶之間的共同評(píng)分項(xiàng)通常很少或者不存在,評(píng)分?jǐn)?shù)據(jù)集比較稀疏,采用傳統(tǒng)的協(xié)同過(guò)濾推薦算法無(wú)法實(shí)現(xiàn)高精度的推薦。表1是用戶User對(duì)電影Item的評(píng)分?jǐn)?shù)據(jù),從表可以看出,用戶User 2和User 3之間只有一個(gè)共同評(píng)分項(xiàng)Item 5,User 1和User 2,User 1和User 3之間沒(méi)有共同評(píng)分項(xiàng)的存在,在這種情況下,傳統(tǒng)的相似度方法可以利用的數(shù)據(jù)很少或者沒(méi)有,很難得到準(zhǔn)確的相似度計(jì)算結(jié)果。因此,一種面向稀疏數(shù)據(jù)的比率相似度計(jì)算方法在本文中提出,該方法直接使用全部的評(píng)分?jǐn)?shù)據(jù)進(jìn)行相似度計(jì)算。

表1 用戶對(duì)電影的評(píng)分Tab.1 Users′ ratings for the movies

2.1 面向稀疏數(shù)據(jù)的比率相似度計(jì)算方法

本文提出了一種面向稀疏數(shù)據(jù)的基于全部評(píng)分的比率相似度計(jì)算方法來(lái)解決傳統(tǒng)的協(xié)同過(guò)濾推薦算法中相似度計(jì)算不足的問(wèn)題。該方法定義用戶u和用戶v在所有項(xiàng)目上評(píng)分的集合Iu和Iv,用戶u和v之間的相似度計(jì)算公式定義為

(2)

其中，|Iu|和|Iv|分別被用來(lái)表示用戶u和用戶v總的評(píng)分個(gè)數(shù),用戶u在所有評(píng)過(guò)分的項(xiàng)目上的第k個(gè)評(píng)分值用ru,k表示,用戶v在所有評(píng)過(guò)分的項(xiàng)目上的第w個(gè)評(píng)分值用rv,w表示,min(ru,k,rv,w)函數(shù)返回ru,k和ru,w兩者中的最小值,最大值通過(guò)max函數(shù)返回。從式(2)可以看出,本文提出的算法不依賴于共同評(píng)分項(xiàng)。

考慮到數(shù)據(jù)集中共同評(píng)分項(xiàng)的影響,對(duì)面向稀疏數(shù)據(jù)的比率相似度計(jì)算公式進(jìn)行了修正,修正后的公式為

(3)

從式(3)可以看出,本文提出的相似度計(jì)算方法充分利用了用戶評(píng)分?jǐn)?shù)據(jù)集中的全部評(píng)分信息,相似度計(jì)算不會(huì)受到數(shù)據(jù)稀疏度的影響。

2.2 評(píng)分預(yù)測(cè)方法

用戶u對(duì)未評(píng)分項(xiàng)目i的預(yù)測(cè)評(píng)分pu,i采用式(4)[14]進(jìn)行評(píng)分預(yù)測(cè)，

(4)

3 實(shí)驗(yàn)結(jié)果和分析

為了驗(yàn)證本文所提出的面向稀疏數(shù)據(jù)的比率相似度計(jì)算方法的有效性,實(shí)驗(yàn)在兩個(gè)電影數(shù)據(jù)集MOVIELENS 100K和MOVIELENS 1M上進(jìn)行,將文中所提方法與傳統(tǒng)的基于用戶的協(xié)同過(guò)濾方法進(jìn)行了比較。

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

MOVIELENS 100K數(shù)據(jù)集包含100 000次評(píng)分, 這些評(píng)分是在1 682部電影上來(lái)自943個(gè)用戶的匿名評(píng)價(jià)。 MOVIELENS 1M數(shù)據(jù)集包含1 000 209次評(píng)分,這些評(píng)分是在3 706部電影上來(lái)自6 040個(gè)用戶的匿名評(píng)分,分值均為1～5。用戶對(duì)電影的喜歡程度用分值的大小來(lái)表示,分值1表示用戶非常不喜歡該電影,5表示非常喜歡。數(shù)據(jù)集的稀疏度不僅影響相似度計(jì)算的準(zhǔn)確性,同時(shí)影響推薦系統(tǒng)的性能。本文所采用的兩個(gè)數(shù)據(jù)集的稀疏度分別為93.7%和95.53%。

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

由于本文所提方法以及用于對(duì)比實(shí)驗(yàn)的方法都是針對(duì)個(gè)性化推薦中的評(píng)分預(yù)測(cè)問(wèn)題,因此，采用兩個(gè)典型的預(yù)測(cè)精準(zhǔn)度的度量指標(biāo):平均絕對(duì)誤差(mean absolute error, MAE)[15]和均方根誤差(rooted mean squared error, RMSE)[16],來(lái)度量算法的預(yù)測(cè)精度。MAE和RMSE越小,表示算法的預(yù)測(cè)誤差越小,預(yù)測(cè)精度就會(huì)越高。MAE被用來(lái)估計(jì)預(yù)測(cè)值與實(shí)際值之間的平均偏差,計(jì)算公式為

(5)

其中,測(cè)試集中評(píng)分的集合用IT表示,pu,i被用來(lái)表示用戶u在項(xiàng)目i上的預(yù)測(cè)評(píng)分值,ru,i被用來(lái)表示用戶u對(duì)項(xiàng)目i的實(shí)際評(píng)分值。

RMSE反映了實(shí)際值與預(yù)測(cè)值之間的偏離程度,當(dāng)預(yù)測(cè)值的誤差較大時(shí),RMSE比MAE更加敏感。RMSE用式(6)進(jìn)行評(píng)估，

(6)

3.3 實(shí)驗(yàn)設(shè)置

為了驗(yàn)證本文提出的協(xié)同過(guò)濾算法在數(shù)據(jù)稀疏情況下的有效性,我們隨機(jī)地移除了兩個(gè)數(shù)據(jù)集中的一部分?jǐn)?shù)據(jù)來(lái)構(gòu)成稀疏數(shù)據(jù)集。在實(shí)驗(yàn)中,每個(gè)數(shù)據(jù)集上分別重構(gòu)了7個(gè)稀疏度在97%～99.9%范圍內(nèi),且步長(zhǎng)為0.5%的稀疏數(shù)據(jù)集(稀疏度為99.9%的數(shù)據(jù)集除外),來(lái)驗(yàn)證稀疏度對(duì)本文所提出推薦算法的影響。對(duì)所有重構(gòu)的稀疏數(shù)據(jù)集進(jìn)行隨機(jī)劃分,取出其中的80%作為訓(xùn)練集,測(cè)試集采用剩余的20%。在接下來(lái)的實(shí)驗(yàn)中,本文提出的算法與PCC, Jaccard, CjacMD[13]和TMJ[17]這4種算法在性能上進(jìn)行了比較。由于上述幾種方法的性能同時(shí)受到稀疏度和最近鄰的影響,所以,為了保證實(shí)驗(yàn)的準(zhǔn)確性,本文需要確定上述4種方法的最佳最近鄰數(shù)目,以排除最近鄰的影響。

3.4 最近鄰對(duì)精度的影響

本文選取在Movielens 100K數(shù)據(jù)集上重構(gòu)的稀疏度為99.5%的稀疏數(shù)據(jù)集來(lái)驗(yàn)證最近鄰對(duì)幾種不同方法性能的影響。最近鄰K設(shè)置為K∈[10,100]，步長(zhǎng)為10。圖1和圖2分別展示了4種方法中MAE和RMSE隨最近鄰變化的實(shí)驗(yàn)結(jié)果。

圖1 最近鄰對(duì)幾種方法中MAE的影響Fig.1 Effect of nearest neighbors on MAE by several methods

圖2 最近鄰對(duì)幾種方法中RMSE的影響Fig.2 Effect of nearest neighbors on RMSE by several methods

從圖1和圖2中可以看出,最近鄰對(duì)MAE和RMSE影響的變化趨勢(shì)是一樣的,本文提出的方法在整個(gè)最近鄰范圍內(nèi)性能均最好,MAE和RMSE都比較低,當(dāng)最近鄰為20時(shí),MAE和RMSE同時(shí)達(dá)到最低點(diǎn)。最近鄰對(duì)本文提出的方法影響不是很大,在最近鄰大于30以后，MAE和RMSE保持不變。PCC方法和Jaccard方法的性能相對(duì)較差,并且最近鄰對(duì)Jaccard的影響比較大,隨著最近鄰的增加,性能逐漸變差。TMJ方法在最近鄰為20時(shí),兩個(gè)指標(biāo)均取到最小值,在最近鄰大于40之后性能趨于穩(wěn)定。CjacMD方法在最近鄰大于60之后趨于穩(wěn)定。實(shí)驗(yàn)結(jié)果說(shuō)明,在整個(gè)最近鄰范圍內(nèi),本文提出的方法,PCC,Jaccard, CjacMD和TMJ方法在最近鄰分別為20, 20, 10, 50和20時(shí)性能最好,兩個(gè)指標(biāo)均到達(dá)最低點(diǎn)。因此,在接下來(lái)的稀疏度實(shí)驗(yàn)中,本文提出的方法,PCC,Jaccard,CjacMD和TMJ上述5種方法的最近鄰取值分別為20, 20, 10, 50, 20。

3.5 實(shí)驗(yàn)結(jié)果與討論

在兩個(gè)重構(gòu)的不同稀疏度的稀疏數(shù)據(jù)集上來(lái)驗(yàn)證本文提出的面向稀疏數(shù)據(jù)的比率相似度計(jì)算方法的有效性。

圖3和圖4是在Movielens 100K上重構(gòu)的7個(gè)不同稀疏度的數(shù)據(jù)集上得到的實(shí)驗(yàn)結(jié)果。圖3和圖4顯示了本文提出的方法與PCC, Jaccard,CjacMD, TMJ方法在不同稀疏度條件下MAE和RMSE隨著稀疏度變化的實(shí)驗(yàn)結(jié)果?？梢钥闯?幾種推薦方法的MAE和RMSE隨著稀疏度的增加在不斷變大。本文提出的方法在整個(gè)稀疏度實(shí)驗(yàn)范圍內(nèi)均取得了最小的MAE和RMSE,特別是在數(shù)據(jù)集稀疏度較高的情況下優(yōu)勢(shì)更大。PCC和Jaccard方法在整個(gè)稀疏度范圍內(nèi)MAE和RMSE值均比較高,性能較差。CjacMD和TMJ方法在稀疏度較低時(shí)和本文提出的方法性能比較接近,隨著稀疏度的升高,性能逐漸變差。

圖3 Movielens 100K重構(gòu)的數(shù)據(jù)集上稀疏度對(duì)幾種MAE的影響Fig.3 Effects of sparsity on MAE of several methods on Movielens 100K reconstructed dataset

圖4 Movielens 100K重構(gòu)的數(shù)據(jù)集上稀疏度對(duì)幾種方法RMSE的影響Fig.4 Effects of sparsity on RMSE of several methods on Movielens 100K reconstructed dataset

圖5和圖6是在Movielens 1M上重構(gòu)的7個(gè)不同稀疏度的數(shù)據(jù)集上得到的實(shí)驗(yàn)結(jié)果。圖5和圖6顯示了本文提出的方法與PCC, Jaccard,CjacMD,TMJ方法在不同稀疏度條件下的MAE和RMSE隨著稀疏度變化的實(shí)驗(yàn)結(jié)果?？梢钥闯?幾種推薦方法的MAE和RMSE隨著稀疏度的升高在不斷地增加,性能也隨之變差。本文提出的方法在整個(gè)稀疏度實(shí)驗(yàn)范圍內(nèi)的MAE和RMSE均較小,特別是在數(shù)據(jù)集稀疏度大于99%時(shí)優(yōu)勢(shì)更明顯。PCC方法在整個(gè)稀疏度范圍內(nèi)MAE和RMSE值均比較高,性能也較差。Jaccard方法在稀疏度較低時(shí)MAE和RMSE值比較低,在稀疏度較高時(shí)性能一般。CjacMD方法的MAE和RMSE在整個(gè)稀疏度范圍內(nèi)均較低,性能僅次于本文所提出的方法。TMJ方法在整個(gè)稀疏度范圍內(nèi)優(yōu)于傳統(tǒng)的協(xié)同過(guò)濾算法。

圖5 Movielens 1M重構(gòu)的數(shù)據(jù)集上稀疏度對(duì)幾種方法MAE的影響Fig.5 Effects of sparsity on MAE of several methods on Movielens 1M reconstructed dataset

圖6 Movielens 1M重構(gòu)的數(shù)據(jù)集上稀疏度對(duì)幾種方法RMSE的影響Fig.6 Effects of sparsity on RMSE of several methods on Movielens 1M reconstructed dataset

實(shí)驗(yàn)結(jié)果表明,PCC方法不適合對(duì)稀疏數(shù)據(jù)進(jìn)行推薦,Jaccard, CjacMD和TMJ方法可應(yīng)用在稀疏度較低的推薦系統(tǒng),而本文提出的面向稀疏數(shù)據(jù)的比率相似度計(jì)算方法充分利用了全部的評(píng)分信息,且不依賴于共同評(píng)分項(xiàng),在數(shù)據(jù)稀疏度較高的情況下也能保證系統(tǒng)的精度和性能。

4 結(jié) 論

本文提出了一種面向稀疏數(shù)據(jù)的比率相似度計(jì)算方法來(lái)提高推薦算法的預(yù)測(cè)精度和推薦系統(tǒng)的性能，主要貢獻(xiàn)為:

1)本文提出的比率相似度計(jì)算方法是基于全部評(píng)分?jǐn)?shù)據(jù)的,不同于傳統(tǒng)的推薦方法的是,本文提出的算法不依賴于共同評(píng)分項(xiàng)。

2)充分利用全部評(píng)分?jǐn)?shù)據(jù),挖掘其中的有價(jià)值的信息,提高了推薦系統(tǒng)的推薦精度。

3)解決了傳統(tǒng)的推薦算法對(duì)稀疏數(shù)據(jù)推薦精度不高甚至無(wú)法推薦的問(wèn)題。

4)本文提出的相似度計(jì)算方法主要面向稀疏數(shù)據(jù),尤其是稀疏度較高的數(shù)據(jù),為進(jìn)一步徹底解決稀疏問(wèn)題和提高推薦精度提供了思路。

在接下來(lái)的工作中,我們將繼續(xù)研究稀疏問(wèn)題,并從隱式反饋信息入手,將其轉(zhuǎn)化為顯示信息來(lái)提高推薦精度。