用戶評分偏好相似性的近鄰?fù)扑]算法研究

艾 均，趙興源，蘇 湛，胡家祺，馬天啟，蘇瑞卿

（上海理工大學(xué)光電信息與計算機(jī)工程學(xué)院，上海 200093）

0 引言

隨著互聯(lián)網(wǎng)的快速發(fā)展，網(wǎng)絡(luò)提供了大量信息和內(nèi)容［1-2］，用戶可通過互聯(lián)網(wǎng)獲取到非常多的書籍［3］、電影［4-6］等資源。在可獲取的資源數(shù)量愈發(fā)龐大的同時，用戶獲取特定、感興趣目標(biāo)內(nèi)容的難度也在不斷增大［1-2，7-8］。以在線購物網(wǎng)站為例，當(dāng)今用戶幾乎可通過網(wǎng)絡(luò)購買到任何商品，但當(dāng)用戶打開購物網(wǎng)站時，琳瑯滿目的商品會使用戶難以作出決定［1，9］。用戶可能會需要進(jìn)行多次搜索、篩選、比較才能找到心儀的商品。

推薦系統(tǒng)的出現(xiàn)有效緩解了用戶難以作出抉擇這一問題［1，10］，其可通過分析用戶行為，“猜”出用戶對物品的偏好，以及用戶是否會對某個物品產(chǎn)生興趣［11］。個性化推薦通過預(yù)測用戶的潛在偏好，向用戶推薦其可能感興趣的物品，一方面可方便用戶選擇、節(jié)省時間，另一方面也節(jié)省了商家的宣傳和推廣成本。

推薦算法能夠解決“預(yù)測”和“推薦”兩方面的問題［12］。“預(yù)測”的過程就是判斷用戶是否會喜歡一個物品，以及喜歡或不喜歡的程度是多少。舉例來說，用戶看過電影后會對其打分，分值即代表了用戶對這部電影的喜愛程度。通過推薦算法，在用戶尚未評分前即計算出用戶可能會給出的分值，該過程就是預(yù)測。而“推薦”則是根據(jù)算法計算出的預(yù)估評分值，由推薦系統(tǒng)向用戶推送其可能會感興趣物品的有序列表。物品的排序越靠前，說明用戶更可能喜歡該物品。

在推薦系統(tǒng)中，用戶對物品的評分可以體現(xiàn)其對該物品的情感信息。情緒中包含了更多情感信息，尤其是在進(jìn)行一些諸如電影等文學(xué)藝術(shù)領(lǐng)域的評分預(yù)測和推薦時，對用戶情感進(jìn)行分析要比簡單的評分計算更加可靠［13］。而用戶對一個物品情緒的表達(dá)，可通過其對該物品的評分來體現(xiàn)［14］。

盡管利用鄰居進(jìn)行相似性計算的協(xié)同過濾算法在行業(yè)中獲得了巨大成功，但由于傳統(tǒng)模型沒有考慮用戶情感對預(yù)測結(jié)果的影響，因此傳統(tǒng)方法存在著準(zhǔn)確性不高、可擴(kuò)展性不強(qiáng)等局限［15-16］。當(dāng)用戶對物品打分時，分值不僅反映了該用戶的評分習(xí)慣，而且也體現(xiàn)了該用戶對此物品的情感偏好。因此，本文通過對用戶情緒極性的度量，為目標(biāo)用戶計算相似性和鄰居選擇，有效避免了用戶評分差異對實驗結(jié)果的影響。相較于其他算法，本文方法具有預(yù)測結(jié)果誤差更小、時間復(fù)雜度更低等優(yōu)點，同時該方法的可擴(kuò)展性強(qiáng)，相比其他算法性能明顯提升。

1 推薦算法研究與分類

推薦系統(tǒng)可被用于進(jìn)行預(yù)測或推薦，傳統(tǒng)的推薦算法主要包括基于內(nèi)容的推薦算法、基于協(xié)同過濾的推薦算法和混合推薦算法3 類［12］。其中，協(xié)同過濾算法是目前推薦系統(tǒng)中一種被廣泛應(yīng)用，也是最成功的推薦算法［8，12，17-21］。

1.1 推薦算法相關(guān)研究

在推薦系統(tǒng)中，有很多種相似性計算方法可基于兩個用戶的共同評分來衡量其之間的相似程度［12］，如Pearson相似性［22-23］、Bhattacharyya 相似性［24］等。除采用基于評分的協(xié)同過濾算法外，許多學(xué)者設(shè)計了基于模型的推薦算法。如Lemire 等［25］提出了基于距離模型的推薦算法，Javari 等［26］提出了基于資源分配模型的推薦算法，Su 等［27］提出了一種基于向量相似性的計算方法。

通過研究發(fā)現(xiàn)，這些算法在計算相似性時沒有考慮用戶的情感偏好，因此預(yù)測結(jié)果的準(zhǔn)確性不高。而通常用戶在對物品打分時體現(xiàn)了其對該物品的情感信息，因此在本文的研究中通過計算用戶對物品的情感偏好，改進(jìn)了相似性計算方法，使預(yù)測準(zhǔn)確性得以提升。

1.2 推薦算法分類

1.2.1 基于內(nèi)容的推薦算法

基于內(nèi)容的推薦算法向用戶推薦的物品，通常都具有相似的特征或?qū)傩裕?2］。這類推薦算法通過分析用戶和物品的固有屬性進(jìn)行推薦［28］，如用戶的年齡、性別、所在地區(qū)，以及物品的類型、發(fā)行年份等，利用推薦項的特征相似性作出預(yù)測和推薦。例如，在進(jìn)行音樂推薦時，通過基于內(nèi)容的推薦算法所作出的推薦，更多地與用戶喜歡的音樂是同一類型的。如果用戶的歷史評分顯示出其更喜歡動作電影后，推薦系統(tǒng)就會推薦更多動作電影給該用戶。

1.2.2 協(xié)同過濾推薦算法

協(xié)同過濾，從字面上理解，包括協(xié)同和過濾兩個操作。這種方法根據(jù)用戶與用戶之間，或是物品與物品之間的相似性進(jìn)行推薦［12］。被“過濾”出的具有相似行為或喜好的目標(biāo)用戶被稱為鄰居用戶，在隨后的預(yù)測階段，目標(biāo)用戶對物品未知的評分，基于篩選出的鄰居們已知的評分進(jìn)行預(yù)測。

所謂協(xié)同就是利用群體行為進(jìn)行推薦，對于推薦系統(tǒng)而言，通過用戶的持續(xù)協(xié)同作用，最終給用戶的推薦會越來越準(zhǔn)確。而過濾就是從可行的推薦方案中將用戶喜歡的物品找出來。協(xié)同過濾算法分為基于用戶的協(xié)同過濾算法和基于物品的協(xié)同過濾算法，這與“物以類聚，人以群分”的思想類似。

在協(xié)同過濾推薦算法中，相似性計算是關(guān)鍵的一步，相似性計算的是否準(zhǔn)確將會影響最終生成的推薦列表是否準(zhǔn)確。在近年來的研究中，相似性通常是基于用戶對其共同評價過的物品評分來計算的［1-2，28-30］。

1.2.3 混合推薦算法

將不同的基于內(nèi)容的推薦算法與不同的協(xié)同過濾算法進(jìn)行組合，便得到了混合推薦算法。常見的組合方式有以下4種［12］：

（1）分別應(yīng)用基于內(nèi)容的推薦算法和協(xié)同過濾算法，將兩者的結(jié)果進(jìn)行混合［31-32］。

（2）將一些基于內(nèi)容的推薦算法的特性應(yīng)用到協(xié)同過濾算法中，以得到更好的結(jié)果［33］。

（3）將一些協(xié)同過濾算法的特性應(yīng)用到基于內(nèi)容的推薦算法中，以得到更好的結(jié)果［34］。

（4）取兩種方法的優(yōu)點，融合成一個新算法［35-36］。

2 基于用戶物品偏好的相似性算法

本文算法的一般流程為：①對比用戶對物品的評分和其歷史平均分，判斷用戶對該物品所表達(dá)的情感偏好，計算該用戶對該物品的喜歡指數(shù)和不喜歡指數(shù)；②對每兩兩用戶篩選其共同評分過的物品，分別計算其喜歡指數(shù)序列和不喜歡指數(shù)序列的相似性，取平均值作為這兩個用戶的相似性；③對每位預(yù)測目標(biāo)用戶，根據(jù)其與其他用戶的相似性，為其由大到小選擇最多200 位鄰居；④根據(jù)鄰居用戶對目標(biāo)物品的評分和鄰居用戶與目標(biāo)用戶的相似性，計算目標(biāo)用戶對目標(biāo)物品的預(yù)測評分。

2.1 用戶偏好相似性與評分預(yù)測

在大多數(shù)基于用戶的協(xié)同過濾算法中，用戶之間的相似性是通過用戶對物品的評分來計算的。用戶只能同時對同一物品表達(dá)出一種情感，即用戶喜歡該物品，或是不喜歡該物品。本文認(rèn)為，用戶對物品的評分大小體現(xiàn)出其對該物品的喜歡或不喜歡程度。若用戶對某一物品的評分高于其平均評分，則說明用戶喜歡該物品，反之則說明用戶不喜歡該物品。因此，本文提出一種基于用戶偏好相似性的協(xié)同過濾算法，分別計算兩兩用戶對共同評分過物品喜歡程度和不喜歡程度的相似性，并將結(jié)果取平均值作為這兩個用戶之間的相似性。

在本文算法中，根據(jù)用戶對物品的評分分別計算出用戶對該物品的兩個指數(shù)。若用戶對某個物品表現(xiàn)出積極情感，即評分高于平均評分，則通過式（1）計算其喜歡指數(shù)，并將其對該物品的不喜歡指數(shù)設(shè)置為0。同理，若用戶對某一物品表現(xiàn)出消極情感，即評分低于平均評分，則通過式（2）計算其不喜歡指數(shù)，并將其對該物品的喜歡指數(shù)設(shè)置為0。如果用戶評分與其歷史評分的最大值或最小值相同，則將其對該物品的喜歡指數(shù)和不喜歡指數(shù)均設(shè)置為0。至此便得到了所有m位用戶對其所評分過物品的偏好程度序列。

Pearson 相似性是協(xié)同過濾推薦系統(tǒng)中被廣泛使用的相似性準(zhǔn)確程度衡量方法，常用于度量兩個變量X與Y之間的相關(guān)程度，結(jié)果介于[ -1，1]。根據(jù)本文算法分別計算了具有共同評分的兩兩用戶之間喜歡指數(shù)和不喜歡指數(shù)的相似性，計算方法如式（3）、式（4）所示，并按照式（5）計算出平均值作為這兩個用戶之間的相似性。

其中，μ1(rui)表示通過計算用戶u對物品i的模糊偏好程度得到的喜歡指數(shù)，同理，μ2(rui)表示不喜歡指數(shù)。表示用戶u對所有共同評分物品的平均喜歡程度，而表示用戶u對所有共同評分物品的平均不喜歡程度。Iuv是用戶u與用戶v共同評分過的物品集合。

評分預(yù)測過程就是在目標(biāo)用戶u未對目標(biāo)物品i評分之前，使用推薦系統(tǒng)算法計算出該用戶可能會對該物品給出的評分值。所有與目標(biāo)用戶有共同評分物品的用戶稱為目標(biāo)用戶的鄰居用戶，通過將用戶u與其他用戶的相似性由大到小排序，選取最相似的前k位用戶組成鄰居用戶集合，按照式（6）得到用戶u的預(yù)測評分。

2.2 實驗結(jié)果

為驗證本文提出的基于用戶評分相似性的算法，使用MovieLens-25M 電影評分?jǐn)?shù)據(jù)集進(jìn)行實驗，并選取了時下流行的算法進(jìn)行對比。MovieLens 是由GroupLens Research負(fù)責(zé)收集和維護(hù)的公開數(shù)據(jù)集，其包含了162 000 位用戶對62 000部電影的約250萬條評分?jǐn)?shù)據(jù)。

同時，本文還采用折十驗證方法增強(qiáng)實驗結(jié)果的準(zhǔn)確性。通過折十驗證，數(shù)據(jù)集被隨機(jī)分成了10 份進(jìn)行實驗，其中任意1 份都可作為其余9 份的測試集，將10 次實驗的平均值作為該實驗的最終結(jié)果。對于所有算法，本文采用的變量均相同，并分別在鄰居數(shù)量為1～200 的情況下進(jìn)行實驗。

He 等［1］提出用戶觀點傳播算法（UOS），其認(rèn)為用戶之間存在著觀點傳播路徑，一個用戶的觀點可沿著該通路傳遞或影響其他用戶。多級協(xié)同過濾算法（MLCF）是由Polatidis 等［2］提出的，在該算法中，共同評分?jǐn)?shù)量更大的用戶之間的相似性被增強(qiáng)。Ai 等［38］在研究中使用了快速無折疊算法進(jìn)行社團(tuán)發(fā)現(xiàn)，構(gòu)建了物品—物品的復(fù)雜網(wǎng)絡(luò)模型，并提出了MIOS 算法。用戶評分的信息熵可體現(xiàn)用戶對物品的整體評分行為，Lee 等［39］在其研究中改進(jìn)了Pearson 相似性算法，將用戶評分的信息熵與推薦算法相結(jié)合，提出了Entropy 算法。

平均絕對誤差（MAE）是協(xié)同過濾推薦算法中普遍使用的結(jié)果檢驗方法，用于計算目標(biāo)對象預(yù)測結(jié)果與真實結(jié)果的誤差。MAE 的計算方法如式（7）所示，結(jié)果越小，說明預(yù)測準(zhǔn)確度越高，算法越優(yōu)異。

其中，Rtest表示測試集分別表示用戶u對物品i的預(yù)測評分和真實評分。

圖1 顯示了不同算法使用MovieLens-25M 數(shù)據(jù)集的MAE 結(jié)果（彩圖掃OSID 碼可見，下同），可看出表現(xiàn)最好的是MIOS 算法，而本文算法的最小值為0.704 2，相比Entropy 算法提升了0.206%，相比UOS 算法提升了1.268%，相比MLCF 算法提升了2.826%。

Fig.1 MAE of different algorithms圖1 不同算法MAE對比

本文還對比了不同算法的歸一化累計折損收益（NDCG），如圖2所示。

Fig.2 NDCG of different algorithms圖2 不同算法NDCG對比

本文算法在所有對比算法中表現(xiàn)最佳，且NDCG 相對于其他算法有著0.060%～1.619%的提升。NDCG 計算方法如式（8）、式（9）所示。

其中，ri代表物品在推薦列表中的排名，排在最頂層的物品記為ri=1。b在算法中控制著折損程度，該值越大，對應(yīng)DCG得分越小，本文在實驗中設(shè)置b=2。Ri表明了推薦列表中物品的相關(guān)性，如果用戶對該物品的評分超過了其平均分，則Ri=1，否則Ri=0。

同時本文算法在基于分類的評價指標(biāo)中也取得了最佳結(jié)果，如圖3所示。

準(zhǔn)確率是在信息檢索領(lǐng)域最常用的評價方法，其表示系統(tǒng)向用戶推薦的物品中用戶喜歡的物品所占比例，其計算方法如式（10）所示。

Fig.3 Precision of different algorithms圖3 不同算法準(zhǔn)確率對比

其中，TP表示用戶喜歡系統(tǒng)推薦的物品，F(xiàn)P表示用戶不喜歡系統(tǒng)推薦的物品。

可以看出，本文算法的準(zhǔn)確率在所有對比算法中是最高的，最大值為0.694 4，而表現(xiàn)最差的為UOS 算法，其準(zhǔn)確率的最大值僅為0.678 5，本文算法相比UOS 算法提升了2.343%。

3 結(jié)語

本文提出一種新的相似性計算方法，提出了喜歡指數(shù)和不喜歡指數(shù)的概念。通過對比用戶對物品的評分及其平均評分，分析用戶通過評分值所表達(dá)的對該物品的情感偏好。同時，本文方法分別計算了兩兩用戶之間共同評分過物品的喜歡偏好與不喜歡偏好的相似性，并將二者結(jié)合作為兩個用戶的相似性。通過在MovieLens 數(shù)據(jù)集進(jìn)行實驗并與其他算法進(jìn)行對比后發(fā)現(xiàn)，本文方法可有效提升預(yù)測結(jié)果的準(zhǔn)確性。此外，該方法可有效避免由于用戶自身評分習(xí)慣而對使用結(jié)果造成的誤差，時間復(fù)雜度更低，具有更強(qiáng)的可擴(kuò)展性及更優(yōu)的性能。因此，本文方法可被應(yīng)用于向用戶推薦其可能會感興趣的商品、電影、書籍、餐廳等。

然而，在本文實驗中，用戶對物品的偏好僅被分成了喜歡和不喜歡，在后續(xù)研究中可將喜歡或不喜歡程度作進(jìn)一步細(xì)分，參考文獻(xiàn)［2］進(jìn)行分級操作，增加或減小相似性，以進(jìn)一步提升預(yù)測結(jié)果的準(zhǔn)確性。此外，本文還將在后續(xù)研究中引入復(fù)雜網(wǎng)絡(luò)模型以尋求更好的實驗結(jié)果。