馬 浩,黃 俊,孔 麟,鄭小楠,郭小煥
(重慶郵電大學(xué) 通信與信息工程學(xué)院,重慶 400065)
隨著互聯(lián)網(wǎng)和信息技術(shù)的快速發(fā)展,信息過(guò)載[1]問(wèn)題也愈來(lái)愈突出。如何在信息海洋中快速發(fā)掘用戶的興趣,并向其推薦感興趣的信息,已成為當(dāng)前的研究熱點(diǎn)。
Daniel Lemire提出了Slope One算法(SO)。該算法簡(jiǎn)單、高效,在協(xié)同過(guò)濾算法中得到廣泛的應(yīng)用和發(fā)展。但隨著數(shù)據(jù)量的增加,其數(shù)據(jù)稀疏性、準(zhǔn)確性等問(wèn)題[2]也凸現(xiàn)出來(lái)。Slope One算法在進(jìn)行平均評(píng)分偏差計(jì)算時(shí),考慮所有共同評(píng)分用戶的歷史評(píng)分?jǐn)?shù)據(jù),其中包含大量與目標(biāo)用戶相似度極低的用戶群體,難免會(huì)引入干擾數(shù)據(jù),導(dǎo)致評(píng)分預(yù)測(cè)結(jié)果不夠精確[3]。因此,部分學(xué)者[4]采用k近鄰的方法給目標(biāo)用戶選擇近鄰用戶集合。但k值不具有特殊性,無(wú)法適應(yīng)不同的預(yù)測(cè)場(chǎng)景、人群及物品,使得推薦誤差很大。所以,有學(xué)者[5,6]提出使用不確定鄰居來(lái)優(yōu)化Slope One算法。在傳統(tǒng)的Slope One算法當(dāng)中運(yùn)用最為廣泛的是Daniel Lenmire提出的Weighted Slope One算法(WSO)[7],考慮到共同評(píng)分用戶數(shù)量的影響,將其作為權(quán)重,使得推薦的準(zhǔn)確性在一定程度上得到改善。在此基礎(chǔ)上,部分學(xué)者[8,9]將用戶相似度和項(xiàng)目相似度添加為原始公式的權(quán)重因子進(jìn)行改進(jìn),一定程度上提高了推薦精度。倪建成等[10]通過(guò)引入時(shí)間權(quán)重,來(lái)改善傳統(tǒng)Slope One算法數(shù)據(jù)的稀疏性和實(shí)時(shí)性差等問(wèn)題。以上改進(jìn)大多是針對(duì)單一方面進(jìn)行考慮,往往取得的效果不是很理想。針對(duì)以上問(wèn)題,本文綜合多方面考慮,提出一種動(dòng)態(tài)k近鄰輔助多權(quán)值Slope One算法(dynamick-nearest neighbor-assisted multi-weight Slope One,KTWSO)。
傳統(tǒng)Slope One算法是一種基于項(xiàng)目的協(xié)同過(guò)濾算法,其核心思想是利用一元線性模型f(x)=x+b對(duì)評(píng)分進(jìn)行線性回歸預(yù)測(cè)。詳細(xì)定義請(qǐng)參見文獻(xiàn)[11]。
Slope One算法基本原理如圖1所示。要對(duì)用戶B的項(xiàng)目J進(jìn)行評(píng)分預(yù)測(cè),首先找出用戶B的其它評(píng)分項(xiàng)目,如項(xiàng)目I。然后找出對(duì)項(xiàng)目I和項(xiàng)目J都做出評(píng)分的用戶集合,如用戶A,并計(jì)算項(xiàng)目I與項(xiàng)目J之間的平均評(píng)分偏差。最后,將用戶B對(duì)項(xiàng)目I的評(píng)分與項(xiàng)目I和項(xiàng)目J之間的平均評(píng)分偏差進(jìn)行計(jì)算,得出預(yù)測(cè)評(píng)分。
圖1 Slope One算法基本原理
綜上,Slope One算法評(píng)分預(yù)測(cè)推薦分為3步:
(1)利用式(1)計(jì)算項(xiàng)目之間的評(píng)分差的均值,記為平均評(píng)分偏差devij
(1)
其中,rui為用戶u對(duì)項(xiàng)目i的評(píng)分,ruj為用戶u對(duì)項(xiàng)目j的評(píng)分,Uij為對(duì)項(xiàng)目i與j都產(chǎn)生了評(píng)分的用戶集合,|Uij| 為集合Uij中用戶個(gè)數(shù)。
(2)利用式(2),根據(jù)目標(biāo)用戶的歷史評(píng)分和項(xiàng)目間的平均評(píng)分偏差,產(chǎn)生目標(biāo)用戶未評(píng)分項(xiàng)目的預(yù)測(cè)評(píng)分
(2)
其中,用preui為用戶u對(duì)項(xiàng)目i的預(yù)測(cè)評(píng)分,I(u)為用戶u產(chǎn)生過(guò)項(xiàng)目評(píng)分,且滿足 (i≠j,|Uij|>0) 的項(xiàng)目集合,|I(u)| 為集合I(u) 中的項(xiàng)目個(gè)數(shù)。
(3)將預(yù)測(cè)評(píng)分進(jìn)行Top-N排序,對(duì)目標(biāo)用戶產(chǎn)生推薦。
傳統(tǒng)Slope One算法簡(jiǎn)單、高效且可擴(kuò)展。但是在計(jì)算項(xiàng)目i與項(xiàng)目j間的平均評(píng)分偏差時(shí),沒(méi)有將不同用戶和項(xiàng)目區(qū)別對(duì)待,導(dǎo)致推薦結(jié)果不夠理想。如果對(duì)項(xiàng)目i和項(xiàng)目j都產(chǎn)生評(píng)分的用戶數(shù)為200,對(duì)項(xiàng)目i和項(xiàng)目k都產(chǎn)生評(píng)分的用戶數(shù)為20,顯然,產(chǎn)生共同評(píng)分的用戶數(shù)差異會(huì)影響平均評(píng)分偏差的可靠性。本例中得到的平均評(píng)分偏差devij要比devik更精確,所以在進(jìn)行評(píng)分預(yù)測(cè)時(shí)應(yīng)該賦予devij更高的權(quán)重。因此,文獻(xiàn)[2]提出了將用戶數(shù)量作為項(xiàng)目間平均評(píng)分偏差的權(quán)重的Weighted Slope One算法,如式(3)所示
(3)
相似度計(jì)算作為協(xié)同過(guò)濾算法中關(guān)鍵步驟,在近鄰用戶的選擇中顯得尤為重要。常用的幾種(用戶)相似度計(jì)算方法如下所示:
(1)余弦相似度
(4)
其中,rui和rvi分別表示用戶u和v對(duì)項(xiàng)目i的評(píng)分,Iuv為u和用戶v共同評(píng)分的項(xiàng)目集。
(2)修正余弦相似度
(5)
(3)Pearson相關(guān)系數(shù)
(6)
針對(duì)傳統(tǒng)Slope One算法和Weighted Slope One算法在計(jì)算項(xiàng)目平均評(píng)分偏差時(shí),忽略了用戶之間的內(nèi)在關(guān)系,無(wú)差別地使用所有用戶的數(shù)據(jù)可能會(huì)引入大量不相關(guān)的評(píng)分?jǐn)?shù)據(jù),從而導(dǎo)致得到的平均評(píng)分偏差誤差大并影響推薦質(zhì)量,以及采用單一加權(quán)方式來(lái)提高推薦精度上存在的不足等問(wèn)題,本文先采用一種改進(jìn)的k近鄰方法,去除部分不相關(guān)的干擾用戶,以過(guò)濾掉干擾的評(píng)分?jǐn)?shù)據(jù)。然后在評(píng)分預(yù)測(cè)時(shí),從用戶相似度、用戶綜合信任度和項(xiàng)目相似度三方面綜合考慮,提出一種動(dòng)態(tài)k近鄰輔助多權(quán)值Slope One算法,以提高推薦的準(zhǔn)確率。
2.1.1 改進(jìn)的相似度計(jì)算
k近鄰的選擇取決于相似度計(jì)算,本文選擇Pearson相關(guān)系數(shù),如式(6)所示,其定義請(qǐng)參見文獻(xiàn)[9]。
假設(shè)用戶共同評(píng)分項(xiàng)目集合很小,且它們的評(píng)分也很接近,就會(huì)得到較高的相似度。但這是不可靠的,因?yàn)榧匣鶖?shù)太小,不具普遍性。因此,可以考慮將用戶間共同評(píng)分的項(xiàng)目數(shù)作為一個(gè)平衡因子Nuv,來(lái)改善用戶評(píng)分?jǐn)?shù)據(jù)稀疏的問(wèn)題,如式(7)所示
(7)
其中,|Iuv| 為用戶u和v共同評(píng)價(jià)的項(xiàng)目數(shù),|Iu| 為用戶u評(píng)分項(xiàng)目數(shù),|Iv| 為用戶v評(píng)分的項(xiàng)目數(shù)。
傳統(tǒng)的Pearson相關(guān)系數(shù)無(wú)差別對(duì)待所有項(xiàng)目,忽略了熱門項(xiàng)目對(duì)相似度帶來(lái)的影響。熱門項(xiàng)目往往反映的是大眾的喜好,并不能完全代表個(gè)人的偏好,反之,若兩個(gè)用戶都對(duì)某個(gè)冷門項(xiàng)目產(chǎn)生評(píng)分,則更能反映用戶間的相似性。因此本文引入熱門項(xiàng)目懲罰因子wi,如式(8)所示
(8)
其中,Ni為所有用戶中喜歡用戶u和用戶v共同評(píng)價(jià)的項(xiàng)目i的用戶數(shù)。
而在實(shí)際生活中,用戶的興趣不會(huì)保持一成不變,用戶近期的評(píng)分記錄相對(duì)于比較久遠(yuǎn)的評(píng)分記錄對(duì)預(yù)測(cè)應(yīng)該有著更重的權(quán)值。因此,本文采用非線性指數(shù)遺忘函數(shù)來(lái)刻畫用戶興趣隨時(shí)間的變化,其值保持在(0,1]之間。并定義興趣穩(wěn)定期概念為用戶興趣保持不變的時(shí)間周期,用于解決用戶興趣在較小的時(shí)間窗內(nèi)保持不變的問(wèn)題,使得用戶興趣的衰減呈現(xiàn)梯度指數(shù)衰減,更加符合實(shí)際情況,如式(9)所示
(9)
其中,t=tnow-tui,tnow為當(dāng)前時(shí)間,tui為用戶u對(duì)項(xiàng)目i的產(chǎn)生評(píng)分時(shí)間,Ts為興趣穩(wěn)定期。
綜上,結(jié)合平衡因子、熱門項(xiàng)目懲罰因子和時(shí)間權(quán)重,改進(jìn)的Pearson相關(guān)系數(shù)如式(10)所示
(10)
2.1.2 閾值過(guò)濾
傳統(tǒng)的k近鄰算法固定k值不具有特殊性,無(wú)法適應(yīng)不同的預(yù)測(cè)場(chǎng)景、人群等。為了提高預(yù)測(cè)精度,本文在采用改進(jìn)的Pearson相關(guān)系數(shù)度量用戶相似度的情況下,設(shè)置一個(gè)評(píng)分相似度閾值λ,針對(duì)不同的目標(biāo)用戶篩選出動(dòng)態(tài)k近鄰用戶集。即在與目標(biāo)用戶產(chǎn)生共同評(píng)分項(xiàng)目的用戶集中,只有大于相似度閾值λ的用戶,才會(huì)被選入目標(biāo)用戶的動(dòng)態(tài)k近鄰用戶集合參與評(píng)分預(yù)測(cè),并將該集合定義為rknn(u),如式(11)所示
rknn(u)={v|simr(u,v)≥λ}
(11)
2.2.1 改進(jìn)的用戶相似度
采用上章節(jié)改進(jìn)的Pearson相關(guān)系數(shù),如式(10)所示,將它作為權(quán)重加權(quán)到Slope One算法中,以考慮用戶間相似性的影響。
2.2.2 用戶綜合信任度
用戶信任度可以作為評(píng)分預(yù)測(cè)的一個(gè)重要依據(jù)。在生活中,一個(gè)值得信任的人提供的信息就具有更高的可靠性,同理,在Slope One算法中,也可以運(yùn)用這種思維。具有高信任度的用戶對(duì)某些項(xiàng)目產(chǎn)生的歷史評(píng)分將具有更高的可信性和參考價(jià)值,反之亦然。因此,本文提出一種用戶綜合信任度,包含用戶活躍度和評(píng)分公正度兩方面。事實(shí)上,并非所有的用戶都積極參與項(xiàng)目的評(píng)分,這就會(huì)出現(xiàn)部分用戶的評(píng)分?jǐn)?shù)量較多,而另外一部分用戶評(píng)分?jǐn)?shù)量較少的情況,顯然我們更愿意去信任那些評(píng)分比較積極的用戶。因此,我們可以采用用戶的項(xiàng)目評(píng)分?jǐn)?shù)去衡量用戶活躍度。當(dāng)用戶的項(xiàng)目評(píng)價(jià)數(shù)越多,其活躍度越高,反之越低。但是僅通過(guò)用戶活躍度去衡量某個(gè)用戶的信任度是不夠的,因?yàn)槟承┯脩艨赡艽嬖陔S意或者惡意評(píng)分的情況。因此,需要考慮用戶對(duì)項(xiàng)目的評(píng)分客觀公正程度。本文采用用戶對(duì)項(xiàng)目的評(píng)分與其平均評(píng)分差值作為衡量用戶評(píng)分公正度的標(biāo)準(zhǔn),當(dāng)這差值越大,其評(píng)分公正度越小,反之越大。
用戶的活躍度Au如式(12)所示,其值保持在(0,1]之間
(12)
用戶的公正度Fu如式(13)所示,其值保持在(0,1]之間
(13)
結(jié)合上述兩個(gè)因子,用戶綜合信任度T(u) 如式(14)所示
T(u)=Au*Fu
(14)
對(duì)于某個(gè)用戶來(lái)說(shuō),他的評(píng)分?jǐn)?shù)量越多而且評(píng)分具有越高可靠性,就越具有參考價(jià)值,賦予越高的權(quán)重。
2.2.3 改進(jìn)項(xiàng)目相似度
Weighted Slope One算法在衡量項(xiàng)目間內(nèi)在聯(lián)系的時(shí)候,考慮了兩個(gè)項(xiàng)目共同產(chǎn)生評(píng)分的用戶數(shù)量的影響。因此,在評(píng)分?jǐn)?shù)據(jù)稀疏情況下,針對(duì)Pearson相關(guān)系數(shù)準(zhǔn)確度不高的問(wèn)題,可以結(jié)合Weighted Slope One算法的思想,加權(quán)項(xiàng)目間共同評(píng)分的用戶數(shù)來(lái)進(jìn)行改進(jìn),如式(15)所示
(15)
其中,Uij表示對(duì)項(xiàng)目i和項(xiàng)目j共同評(píng)分的用戶集合,|Uij| 表示該集合中用戶的個(gè)數(shù),|Ui| 表示對(duì)項(xiàng)目i評(píng)分的用戶數(shù),|Uj| 表示對(duì)項(xiàng)目j評(píng)分的用戶數(shù)。
綜合多個(gè)方面進(jìn)行考慮,可以有效解決單因素加權(quán)改進(jìn)的不足。
(16)
(17)
最后,將生成的預(yù)測(cè)評(píng)分,進(jìn)行Top-N推薦。具體過(guò)程如下:
輸入:用戶-項(xiàng)目評(píng)分矩陣Rm×n,目標(biāo)用戶u,目標(biāo)項(xiàng)目j,用戶相似度閾值λ,興趣穩(wěn)定期Ts,推薦長(zhǎng)度N。
輸出:N個(gè)推薦項(xiàng)目。
步驟1 根據(jù)評(píng)分矩陣Rm×n,使用改進(jìn)的相似度計(jì)算式(10)計(jì)算用戶間相似度矩陣Sm×m。
步驟2 將其他用戶與目標(biāo)用戶u進(jìn)行相似度比較,篩選出相似度值大于λ的用戶作為u的動(dòng)態(tài)k近鄰用戶集合rknn(u)。
步驟3 在集合rknn(u) 中,采用式(16)計(jì)算目標(biāo)項(xiàng)目j與其它項(xiàng)目間的平均評(píng)分偏差。
步驟4 通過(guò)式(17)為目標(biāo)項(xiàng)目j生成預(yù)測(cè)評(píng)分。若用戶u的rknn(u) 集合為空,則以u(píng)對(duì)其它項(xiàng)目的評(píng)分均值作為預(yù)測(cè)評(píng)分,若u未產(chǎn)生過(guò)任何評(píng)分,則以項(xiàng)目j的評(píng)分均值作為預(yù)測(cè)評(píng)分。
步驟5 將產(chǎn)生的預(yù)測(cè)評(píng)分進(jìn)行排序,并取評(píng)分較高的N個(gè)項(xiàng)目生成推薦列表。
本文實(shí)驗(yàn)采用Grouplens提供的MovieLens數(shù)據(jù)集[12]。MovieLens數(shù)據(jù)集包含大量用戶的電影的評(píng)分?jǐn)?shù)據(jù),以及電影元數(shù)據(jù)信息和用戶屬性信息等。其中,數(shù)據(jù)集MovieLens 100k記錄了943個(gè)用戶在1682部電影上產(chǎn)生的 100 000 條評(píng)分記錄,評(píng)分范圍由1到5,評(píng)分的高低反映了對(duì)電影的喜愛(ài)程度。本實(shí)驗(yàn)隨機(jī)選取100 k總數(shù)據(jù)集的80%作為訓(xùn)練集,余下的20%用作測(cè)試集。
本文采用實(shí)際評(píng)分和預(yù)測(cè)評(píng)分的平均絕對(duì)誤差(mean absolute error,MAE)來(lái)衡量算法預(yù)測(cè)評(píng)分的準(zhǔn)確性。MAE的值越高,預(yù)測(cè)評(píng)分的準(zhǔn)確性越低,反之亦然。MAE如式(18)所示
(18)
其中,pi和qi分別表示項(xiàng)目i的預(yù)測(cè)評(píng)分和實(shí)際評(píng)分,N為測(cè)試集中預(yù)測(cè)項(xiàng)目的數(shù)量。
本文實(shí)驗(yàn)分為兩個(gè)部分:一是參數(shù)的選擇,包括用戶相似度閾值λ,興趣穩(wěn)定期Ts;二是進(jìn)行算法對(duì)比性實(shí)驗(yàn),驗(yàn)證改進(jìn)的有效性。
3.3.1 參數(shù)分析實(shí)驗(yàn)結(jié)果
(1)首先進(jìn)行興趣穩(wěn)定期Ts的選擇實(shí)驗(yàn)。由于改進(jìn)的k近鄰方法中涉及到用戶相似度閾值λ和興趣穩(wěn)定期Ts那個(gè)參數(shù)的選擇,我們先去掉相似度閾值這一參數(shù),然后采用傳統(tǒng)的k近鄰算法中選擇式(10)來(lái)進(jìn)行用戶相似度的計(jì)算,最后將產(chǎn)生的k近鄰用戶集拿去進(jìn)行平均評(píng)分偏差的計(jì)算,定義為改進(jìn)k近鄰Slope One算法(improved k-nearest neighbor Slope One,KSO)。
分別取近鄰k值為10、20、30與不同取值的興趣穩(wěn)定期來(lái)進(jìn)行實(shí)驗(yàn)。由圖2可知,在用戶興趣穩(wěn)定期Ts為30的情況下,MAE總能取到最優(yōu)值,因此我們選擇Ts=30作為最佳的興趣穩(wěn)定期。
圖2 興趣穩(wěn)定期對(duì)MAE的影響
(2)進(jìn)行用戶相似度閾值的選擇實(shí)驗(yàn)。如果將相似度閾值設(shè)置得太低,就會(huì)引入過(guò)多的干擾數(shù)據(jù)參與到評(píng)分預(yù)測(cè)當(dāng)中,勢(shì)必會(huì)影響推薦的準(zhǔn)確性,同理,如果將相似度閾值設(shè)置的太高,得到的用戶近鄰集合就會(huì)太小,推薦的精度也不會(huì)太理想。因此,從這兩方面考慮,選取0.1到0.8作為用戶相似度閾值分別進(jìn)行實(shí)驗(yàn)。由圖3可知,在相似度閾值為0.3時(shí),可以取得最優(yōu)的MAE值。
圖3 λ對(duì)MAE的影響
綜上,分別取λ=0.3和Ts=30作為本實(shí)驗(yàn)的用戶相似度閾值和興趣穩(wěn)定期。
3.3.2 算法對(duì)比實(shí)驗(yàn)結(jié)果
(1)首先,比較本文第二章中的兩個(gè)改進(jìn)部分,以驗(yàn)證改進(jìn)的有效性。
將數(shù)據(jù)集MovieLens 100k通過(guò)5折線交叉法,隨機(jī)分成5等份,輪流取其中4份作為訓(xùn)練集,取剩下的1份作為測(cè)試集。然后將2.1節(jié)改進(jìn)的動(dòng)態(tài)k近鄰方法與Slope One算法結(jié)合,定義為動(dòng)態(tài)k近鄰Slope One算法(dynamic k-nearest neighbor Slope One,KTSO),并與結(jié)合2.1節(jié)和2.2節(jié)提出的動(dòng)態(tài)k近鄰輔助多權(quán)值Slope One算法進(jìn)行對(duì)比,采用上面分好的數(shù)據(jù)集,分別執(zhí)行5次。
實(shí)驗(yàn)結(jié)果如圖4所示,在采用動(dòng)態(tài)k近鄰的情況下,結(jié)合多權(quán)值改進(jìn)的KTWSO算法的MAE值明顯低于僅采用動(dòng)態(tài)k近鄰改進(jìn)的KTSO算法,從而驗(yàn)證了2.2節(jié)算法改進(jìn)的合理性。
圖4 KTSO和KTWSO的MAE比較
(2)然后將本文提出的KTWSO算法與SO算法、WSO算法以及文獻(xiàn)[5]提出的The K-nearest neighbor Slope One algorithm based on weighted user similarity and user tag算法(KHSO)進(jìn)行比較,分別進(jìn)行5組實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果見表1。
表1 不同算法下的MAE
分別取表中各算法MAE均值作比較,由圖5中可知,本文提出的KTWSO算法的MAE值相對(duì)于前3種算法分別降低了3%、2%和1%。相對(duì)于KHSO算法來(lái)說(shuō),本文提出的KTWSO算法采用動(dòng)態(tài)k近鄰,過(guò)濾掉了部分干擾數(shù)據(jù),并一定程度上改進(jìn)了傳統(tǒng)K近鄰算法無(wú)法適應(yīng)不同的預(yù)測(cè)場(chǎng)景、人群的問(wèn)題,同時(shí)從用戶相似度、用戶綜合信任度以及項(xiàng)目相似度多方面考慮,進(jìn)一步提高了評(píng)分預(yù)測(cè)的準(zhǔn)確性,達(dá)到了更好的推薦效果。
圖5 SO、WSO、KHSO和KTWSO的MAE比較
針對(duì)傳統(tǒng)Slope One算法無(wú)差別地使用所有用戶評(píng)分?jǐn)?shù)據(jù)導(dǎo)致評(píng)分預(yù)測(cè)不準(zhǔn)確的問(wèn)題,本文引入動(dòng)態(tài)k近鄰的思想來(lái)篩選用戶的近鄰用戶集,并從用戶興趣偏移和熱門項(xiàng)目方面對(duì)相似度計(jì)算方法進(jìn)行改進(jìn),一定程度上提高了近鄰用戶的質(zhì)量。然后將近鄰用戶集運(yùn)用到計(jì)算項(xiàng)目平均評(píng)分偏差中,從而剔除了干擾用戶數(shù)據(jù)并提高了推薦精度。同時(shí),本文優(yōu)化的算法將用戶相似度、用戶綜合信任度和項(xiàng)目相似度作為權(quán)重因子加權(quán)到Slope One算法的評(píng)分預(yù)測(cè)當(dāng)中,使得推薦的精度進(jìn)一步提高。未來(lái),我們可以從用戶和項(xiàng)目的標(biāo)簽信息考慮,將更多信息納入算法,以獲得更多的改進(jìn)。