稀疏數(shù)據(jù)下基于用戶偏好的協(xié)同過(guò)濾算法

趙文濤，張 爍

(河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南 焦作 454150)

0 引 言

協(xié)同過(guò)濾推薦技術(shù)[1]在推薦系統(tǒng)中占據(jù)著很重要的地位。協(xié)同過(guò)濾推薦技術(shù)可以通過(guò)用戶對(duì)物品的評(píng)分或者別的行為模式為用戶提供優(yōu)質(zhì)的推薦服務(wù)?；卩徲虻乃惴╗2]是協(xié)同過(guò)濾推薦算法中最基本也是最常用的方法之一。其基于用戶對(duì)項(xiàng)目的評(píng)級(jí)，把具有相似評(píng)級(jí)的用戶稱為最近鄰居[3]，如果找到鄰近的鄰居，則通過(guò)鄰居預(yù)測(cè)用戶的未評(píng)級(jí)項(xiàng)目，然后向用戶推薦具有高預(yù)測(cè)評(píng)級(jí)的項(xiàng)目。

但是，現(xiàn)存的基于協(xié)同過(guò)濾推薦算法的推薦系統(tǒng)仍然存在諸多問(wèn)題，譬如冷啟動(dòng)[4]，數(shù)據(jù)稀疏性以及可擴(kuò)展性[5-8]等。一般而言，傳統(tǒng)相似性算法可以很好地反映2個(gè)用戶或項(xiàng)目之間的相似程度，但卻沒(méi)有重復(fù)考慮用戶偏好。同時(shí)，當(dāng)數(shù)據(jù)稀疏的時(shí)候，用戶或項(xiàng)目之間可能沒(méi)有共同評(píng)級(jí)項(xiàng)目，相似性計(jì)算將無(wú)法進(jìn)行[9]，這也被稱為共同評(píng)定問(wèn)題。

1 相關(guān)工作

當(dāng)前，研究人員為協(xié)同過(guò)濾提供了非常豐富的理論依據(jù)和技術(shù)支持，文獻(xiàn)[10]給出了Jaccard和均方差組合的方法(Jaccard mean squared difference，JMSD)，JMSD中Jaccard用于捕獲共同評(píng)定項(xiàng)目的比例，均方差(mean squared difference，MSD)用于獲取評(píng)級(jí)信息，該方法解決了傳統(tǒng)算法過(guò)于依賴距離和矢量導(dǎo)致相似性度量不準(zhǔn)確的問(wèn)題，文獻(xiàn)[11]提出了另一種相似性方法，結(jié)合6種相似性度量來(lái)獲得全局相似性，每個(gè)測(cè)量的權(quán)重是通過(guò)神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)獲得的。但是，這些措施在稀疏數(shù)據(jù)的情況下不起作用。文獻(xiàn)[12]通過(guò)考慮用戶在不同評(píng)級(jí)等級(jí)上提供的本地和全局評(píng)級(jí)信息，結(jié)合Matusita系數(shù)提出一個(gè)新的Matusita協(xié)同過(guò)濾模型 (Matusita collaborative filtering，MCF)，有效解決了稀疏數(shù)據(jù)集下的共同評(píng)級(jí)問(wèn)題，然而該算法只單純計(jì)算用戶得分偏好而忽視了用戶興趣偏好，在極端情況下推薦會(huì)非常不穩(wěn)定。文獻(xiàn)[13]考慮到傳統(tǒng)的余弦相似度不考慮用戶偏好的問(wèn)題，通過(guò)用戶項(xiàng)目評(píng)級(jí)值減去項(xiàng)目平均值的方法得到修正余弦。文獻(xiàn)[14]提出了一種新的相似性度量，稱為新啟發(fā)式相似性方法，為每個(gè)共同評(píng)定的項(xiàng)目計(jì)算3個(gè)參數(shù)，分別是接近度，重要性和奇異性，之后，將每個(gè)計(jì)算出的參數(shù)乘以修改后的Jaccard相似度。

上述研究并沒(méi)有從全局的角度分析用戶的興趣偏好問(wèn)題，尤其是在數(shù)據(jù)稀疏的情況下，傳統(tǒng)的推薦算法僅使用戶間的共同項(xiàng)目，會(huì)讓推薦的精度更加不準(zhǔn)確。針對(duì)這些問(wèn)題，本文通過(guò)深入挖掘和分析用戶的興趣偏好，從多角度考慮影響用戶偏好的因素；同時(shí)，采用全局項(xiàng)目擴(kuò)大了相似用戶的查找范圍，避免數(shù)據(jù)稀疏性引起的相似度計(jì)算問(wèn)題；最后，結(jié)合加權(quán)的JMSD提高算法的精確度。

2 基于用戶偏好的改進(jìn)協(xié)同過(guò)濾算法

2.1 稀疏數(shù)據(jù)下用戶的偏好問(wèn)題

傳統(tǒng)用戶項(xiàng)目評(píng)分矩陣如表1，用戶評(píng)分是1—5，0表示用戶間沒(méi)有共同項(xiàng)目，如果對(duì)用戶U1進(jìn)行推薦，會(huì)發(fā)現(xiàn)U2,U3與U1并沒(méi)有共同評(píng)分項(xiàng)目，傳統(tǒng)相似度計(jì)算無(wú)法進(jìn)行，相似度默認(rèn)為0，U4與U1的有共同項(xiàng)目評(píng)分分別為(5,4)和(1,1),根據(jù)計(jì)算相似度為負(fù)值，此時(shí)，推薦系統(tǒng)會(huì)把優(yōu)先級(jí)高的U2,U3推薦給U1。反觀U3對(duì)項(xiàng)目的打分非常低，U1卻對(duì)此類物品有高的評(píng)分，從用戶偏好的角度出發(fā)，U3和U1對(duì)物品的喜好有所不同，U2會(huì)更適合向U1推薦。但傳統(tǒng)的相似性度量顯然沒(méi)有考慮到這個(gè)問(wèn)題，并且現(xiàn)實(shí)中的數(shù)據(jù)往往比較稀疏，用戶間的共同項(xiàng)目缺失嚴(yán)重，上述問(wèn)題出現(xiàn)頻率會(huì)更多，這會(huì)對(duì)推薦的精度產(chǎn)生很大影響。

表1 用戶項(xiàng)目評(píng)分矩陣Tab.1 User-Item scoring matrix

2.2 基于用戶偏好的相似度

2.2.1 用戶的興趣偏好貼近度

在模糊數(shù)學(xué)中，貼近度可以用來(lái)表示2個(gè)集合的貼近程度，若2個(gè)模糊集合距離越大，貼近程度越遠(yuǎn)，集合的相關(guān)性越弱。假設(shè)u=(u1,u2,u3…un)，則海明貼近度為

(1)

用戶的興趣偏好度可以通過(guò)項(xiàng)目評(píng)級(jí)表現(xiàn)出來(lái)，評(píng)分越接近的用戶，他們喜歡某一物品的概率也會(huì)越大。所以可以通過(guò)貼近度算法來(lái)計(jì)算用戶間的偏好。定義用戶的評(píng)級(jí)項(xiàng)目L=(l1,l2,l3…lm)，u和v是L上的評(píng)分集合，則基于用戶偏好的貼近度可以定義為

(2)

(2)式僅使用了用戶共有評(píng)定項(xiàng)目，這只能反映很小一部分用戶的真實(shí)狀況，忽視了游離在共同項(xiàng)目之外的用戶評(píng)分，未能全面把握用戶的興趣偏好。本文使用全局評(píng)分項(xiàng)目，擴(kuò)大對(duì)用戶興趣偏好的查找范圍。然后，考慮到稀疏數(shù)據(jù)上由于評(píng)分分布稀疏且不均勻，公式計(jì)算會(huì)偏大造成用戶貼近度失真的問(wèn)題，利用分層的思想把全局項(xiàng)目分成用戶共同項(xiàng)目和用戶本地項(xiàng)目。對(duì)于無(wú)共同評(píng)定部分計(jì)算，使用平均評(píng)分填充。計(jì)算表達(dá)式為

(3)

2.2.2 用戶的評(píng)分偏好

每個(gè)用戶都有屬于自己的評(píng)分風(fēng)格，有的用戶可能不喜歡給高分，有的用戶可能會(huì)給相同的評(píng)分，對(duì)同一喜好物品，不同用戶基于自己的評(píng)分偏好，可能會(huì)給出不同的數(shù)值，這就會(huì)降低推薦的精確度?？紤]到用戶在全局的評(píng)分項(xiàng)，通過(guò)計(jì)算不同用戶可能出現(xiàn)的評(píng)分概率分布用以處理用戶評(píng)分偏好問(wèn)題。用戶的評(píng)級(jí)偏好定義為

(4)

(4)式中：P(u,v)的取值為[0,1]；φ表示用戶對(duì)物品的評(píng)分取值范圍；l(u)與l(v)表示用戶對(duì)所評(píng)分物品的數(shù)目；Φn與φm表示評(píng)分φ在u，v用戶的物品評(píng)分列表中出現(xiàn)的次數(shù)之和。(4)式反映了在離散區(qū)間內(nèi)，不同用戶全局評(píng)分的概率分布的密度。對(duì)(4)式進(jìn)行舉例演示，假設(shè)u=(0,0,1,0,0,2,0,0,3,0,0,4,0,0,5)，v=(1,2,0,2,3,0,3,3,0,4,5,0,5,3,0)是項(xiàng)目的評(píng)級(jí)數(shù)據(jù)，其中評(píng)級(jí)值是1—5，根據(jù)(4)式，可以得出

(5)

2.2.3Jeffries-Matusita距離的組合相似度

Jeffries-Matusita距離[15]廣泛用于各種領(lǐng)域，如圖像處理，信號(hào)和模式識(shí)別等。對(duì)于度量距離較小的2個(gè)分量，會(huì)反映出較差的可分性，從而得出精度不高的結(jié)果。在協(xié)同過(guò)濾中，該距離可以用來(lái)計(jì)算用戶的相似度，所以可以利用Jeffries-Matusita算法把用戶在全局實(shí)際評(píng)分中的偏好度轉(zhuǎn)化成用戶間的相似度，表示為

(6)

2.3 基于共同評(píng)分項(xiàng)的相似度計(jì)算

2.3.1 基于logistic函數(shù)的懲罰因子

在推薦系統(tǒng)中，不同用戶之間的共同評(píng)定項(xiàng)目的數(shù)量變化很大。評(píng)級(jí)越多的項(xiàng)目，從中提取的信息越多，相似度計(jì)算結(jié)果就越準(zhǔn)確。因此，共同評(píng)定項(xiàng)目數(shù)量的比例是一個(gè)非常重要的影響因素。本文引入logistic函數(shù)對(duì)用戶的共同評(píng)分項(xiàng)進(jìn)行線性映射，得到一種關(guān)于共同評(píng)定的限制性懲罰因子，如果用戶共同項(xiàng)目越少，得分就會(huì)越小。模型表示為

(7)

2.3.2 加權(quán)JMSD算法

JMSD算法考慮了用戶的共同評(píng)級(jí)和項(xiàng)目信息，但是如前文所提問(wèn)題一樣，該算法過(guò)度依靠用戶的共同項(xiàng)目，未能考慮到全局信息，在稀疏的數(shù)據(jù)下，用戶共同項(xiàng)目較少，用戶對(duì)項(xiàng)目評(píng)級(jí)缺失，共同評(píng)級(jí)計(jì)算難度大，這會(huì)造成相似度計(jì)算不準(zhǔn)確。結(jié)合(7)式，對(duì)JMSD算法進(jìn)行加權(quán)得

simJM(u,v)=Qu,v×JMSD

(8)

2.4 改進(jìn)協(xié)同過(guò)濾算法ED-JM

加權(quán)JMSD算法使用用戶的絕對(duì)評(píng)級(jí)信息和共同評(píng)級(jí)的比例，這是偏好度算法沒(méi)有考慮到的地方。使基于用戶的偏好度算法與加權(quán)JMSD算法相結(jié)合，可以充分利用他們的優(yōu)點(diǎn)。最終得出本文算法模型為

simED-JM(u,v)=D(u,v)+simJM(u,v)

(9)

(9)式通過(guò)考慮用戶興趣偏好貼近度和用戶的評(píng)分偏好，有效地使用共同評(píng)級(jí)項(xiàng)目和所有評(píng)級(jí)信息，這解決了在稀疏數(shù)據(jù)中，常規(guī)度量中找到相似性的參數(shù)僅考慮共同評(píng)定項(xiàng)目的實(shí)際評(píng)級(jí)信息而造成的共同評(píng)定問(wèn)題；最后，結(jié)合加權(quán)JMSD算法對(duì)用戶的絕對(duì)評(píng)級(jí)信息和共同評(píng)級(jí)的比例，提高了協(xié)同過(guò)濾算法的準(zhǔn)確度。具體算法流程如圖1。

圖1 算法公式流程圖Fig.1 Algorithm formula flow chart

2.5 評(píng)級(jí)預(yù)測(cè)

相似度計(jì)算完成后，預(yù)測(cè)表達(dá)式可以表示為

(10)

(10)式中，Nu表示用戶u的最近鄰居集合。該方法可以計(jì)算目標(biāo)用戶的所有未評(píng)級(jí)項(xiàng)目[16]。然后，推薦算法將前N個(gè)項(xiàng)目推薦給目標(biāo)用戶作為推薦結(jié)果。

3 實(shí)驗(yàn)對(duì)比分析

3.1 評(píng)價(jià)標(biāo)準(zhǔn)

推薦系統(tǒng)中推薦精度的評(píng)價(jià)標(biāo)準(zhǔn)有多種，現(xiàn)階段使用最廣的是平均絕對(duì)偏差MAE和均方根誤差RMSE等[17]方法進(jìn)行精度評(píng)估。MAE和RMSE的值越小表明推薦越精確越高，MAE用于估計(jì)實(shí)際評(píng)級(jí)與預(yù)測(cè)評(píng)級(jí)之間的平均絕對(duì)偏差，用pui和rui分別表示用戶u在項(xiàng)目i上的預(yù)測(cè)評(píng)級(jí)和實(shí)際評(píng)級(jí)。MAE可以定義為

(11)

RMSE用來(lái)表示實(shí)際評(píng)級(jí)與預(yù)測(cè)評(píng)級(jí)之間的均方根誤差，定義為

(12)

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

本次實(shí)驗(yàn)采用的數(shù)據(jù)集是Movielens 100 K。Movielens 100 K含有943名用戶對(duì)1 682部電影的100 000次評(píng)分，其中評(píng)分為5分制，稀疏程度為93.7%。其中，MAE，RMSE覆蓋的性能值是基于鄰居數(shù)K的數(shù)值計(jì)算的，K的值定義為10到100，間隔為10。

圖2和圖3分別展示出了在Movielens 100K的數(shù)據(jù)集上不同的相似性度量在不同K值下MAE和RMSE的對(duì)比。從圖2和圖3中可知，JMSD算法和修正的余弦算法明顯不如其他算法，除了以上2個(gè)算法外，其他算法的函數(shù)曲線相對(duì)穩(wěn)定，隨著K值增加，算法準(zhǔn)確率不斷上升，之后略有下降。相比于性能較好的MCF算法[8]與COS算法，本文模型算法ED-JM在MAE指標(biāo)上分別提高了2.1%和1.86%，在RMSE指標(biāo)上分別提高了4%和3.68%。

圖2 在Movielens100 K下不同相似性度量的MAE對(duì)比Fig.2 MAE comparison of different similarity measuresunder movielens 100 K

圖3 在Movielens100 K下不同相似性度量在RMSE對(duì)比Fig.3 Comparison of different similarity measures in RMSE under Movielens 100 K

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

數(shù)據(jù)的稀疏性可能會(huì)使協(xié)同過(guò)濾算法的精度降低，為進(jìn)一步驗(yàn)證所提算法，采用更為稀疏的數(shù)據(jù)集FilmTrust進(jìn)行實(shí)驗(yàn)。FilmTrust數(shù)據(jù)集是一個(gè)小型的公開(kāi)數(shù)據(jù)集。該數(shù)據(jù)集在2 071部電影中有1 508位用戶擁有35 497個(gè)評(píng)分，其值為0.5的倍數(shù)，范圍從0.5到4。FilmTrust的稀疏度為98.86%。在實(shí)驗(yàn)方面，使用COS算法、JMSD算法和MCF算法進(jìn)行對(duì)比。

表2為不同算法在鄰居數(shù)為[10，20，40，80，100]上不同的MAE值。

表2 不同相似度對(duì)應(yīng)的MAETab.2 MAE values for different similarities

表3展示了3種相似度與本文算法在MAE上平均和最小的誤差對(duì)比。

表3 算法誤差對(duì)比Tab.3 Algorithm error comparison

由于FilmTrust數(shù)據(jù)集展現(xiàn)更為稀疏的特性，從表2、表3可知，隨著K值增加，算法誤差逐漸變大。JMSD算法準(zhǔn)確度的高低和用戶項(xiàng)目數(shù)有關(guān)，所以該算法相比其他算法依舊有著較差的MAE；傳統(tǒng)協(xié)同過(guò)濾算法COS只考慮用戶共同項(xiàng)目，所以在稀疏數(shù)據(jù)下整體性能較差，如表3，余弦算法最低誤差率達(dá)到14.89%，該點(diǎn)在全圖中有著最大誤差。MCF的平均誤差率為4.39%，相比Movielens 100 K實(shí)驗(yàn)可以發(fā)現(xiàn)，MCF算法對(duì)比所提算法性能有所下降。從圖4可知，所提算法明顯優(yōu)于其他算法，在K=10的時(shí)候，本文算法精度要略低于MCF算法，但隨著鄰居數(shù)增加，算法要優(yōu)于MCF算法并在K=40取得最優(yōu)點(diǎn)。由此可見(jiàn)，本文算法在稀疏數(shù)據(jù)下也會(huì)有著高的準(zhǔn)確率。

圖4 FilmTrust數(shù)據(jù)集下不同的MAEFig.4 Different MAEs in the FilmTrust dataset

4 結(jié)束語(yǔ)

傳統(tǒng)相似性度量算法不能向稀疏數(shù)據(jù)集中的用戶提供有效推薦，本文算法有效地利用全局所有評(píng)級(jí)信息，而非單純考慮用戶提供的共同評(píng)定項(xiàng)目值。該算法將用戶的興趣貼近度評(píng)分偏好考慮到相似度計(jì)算中，然后結(jié)合加權(quán)JMSD算法，得出一個(gè)基于用戶偏好的改進(jìn)協(xié)同過(guò)濾算法。通過(guò)實(shí)驗(yàn)表明，本文算法不僅緩解了稀疏性問(wèn)題，算法的精度也要高于傳統(tǒng)算法和文獻(xiàn)算法。在未來(lái)研究中，要進(jìn)一步優(yōu)化推薦算法，提高算法的精確度，為用戶提供更好的推薦體驗(yàn)。