蔡依芳，艾 均，蘇 湛

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

worldchinacai@126.com;aijun@outlook.com;suzhan@foxmail.com

1 引言(Introduction)

近年來(lái)，信息技術(shù)與移動(dòng)網(wǎng)絡(luò)的飛速發(fā)展使得互聯(lián)網(wǎng)每天都產(chǎn)生海量信息，在網(wǎng)絡(luò)上暢游的用戶在尋求滿足自身需求時(shí)必然面臨過(guò)多的選擇。大量相似的選擇和質(zhì)量未知的信息增加了用戶的困惑，讓選擇更加困難，這就導(dǎo)致用戶不僅沒能從海量數(shù)據(jù)中獲取便利，還要花費(fèi)大量的時(shí)間進(jìn)行目標(biāo)篩選，這種現(xiàn)象被稱為信息過(guò)載。

推薦系統(tǒng)是解決信息過(guò)載問(wèn)題的一個(gè)有效方案，它通過(guò)學(xué)習(xí)用戶歷史行為偏好主動(dòng)預(yù)測(cè)用戶對(duì)未評(píng)分或反饋的物品潛在的反應(yīng)，并將那些預(yù)測(cè)評(píng)分較高或偏好正面的物品，通過(guò)推薦列表等形式自動(dòng)化、個(gè)性化地推薦給不同用戶，從而幫助他們更快速地找到需要或喜歡的物品。這種技術(shù)的成功應(yīng)用有效提升了用戶對(duì)系統(tǒng)的好感，也可以幫助商家尋找對(duì)某物品感興趣的潛在用戶群體，既解決了用戶的困擾，又為商家創(chuàng)造了價(jià)值。因此，推薦系統(tǒng)目前已被廣泛應(yīng)用于多個(gè)領(lǐng)域，例如電子商務(wù)平臺(tái)、在線流媒體網(wǎng)站、電影推薦網(wǎng)站、在線音樂網(wǎng)站或應(yīng)用、社交網(wǎng)絡(luò)平臺(tái)，等等。

本文通過(guò)分析推薦算法過(guò)程中用戶共同評(píng)分物品的數(shù)量和質(zhì)量問(wèn)題，設(shè)計(jì)用戶間的相似性度量方法和對(duì)應(yīng)的協(xié)同過(guò)濾個(gè)性化推薦算法，并通過(guò)在真實(shí)的電影評(píng)分?jǐn)?shù)據(jù)集上實(shí)驗(yàn)以驗(yàn)證算法的有效性。

2 推薦算法分類(The classification of recommendation algorithms)

2.1 算法分類

個(gè)性化推薦算法通常分為三類：基于內(nèi)容的推薦算法、基于內(nèi)存和模型的協(xié)同過(guò)濾算法以及混合推薦算法。

三種算法存在不同的使用限制。(1)基于內(nèi)容的推薦算法通過(guò)分析物品的內(nèi)容信息(新聞、圖書等)預(yù)測(cè)或形成推薦，但其非常依賴內(nèi)容信息的數(shù)據(jù)質(zhì)量，也非常容易給出那些顯而易見的推薦，但推薦的準(zhǔn)確性和多樣性受限。(2)協(xié)同過(guò)濾算法只要系統(tǒng)提供用戶對(duì)物品的評(píng)分信息集合就可以工作。其中，基于內(nèi)存的協(xié)同過(guò)濾利用相似用戶打分的習(xí)慣，使用近鄰算法篩選鄰居并預(yù)測(cè)未知評(píng)分；基于模型的協(xié)同過(guò)濾，例如貝葉斯分類器、模糊算法和矩陣分解模型，使用歷史評(píng)分?jǐn)?shù)據(jù)訓(xùn)練不同的模型用于推薦或預(yù)測(cè)。(3)混合推薦算法則融合不同類型的算法，試圖結(jié)合它們各自的優(yōu)點(diǎn)進(jìn)行推薦，但其計(jì)算復(fù)雜性更高，推薦結(jié)果可解釋性較差。

2.2 經(jīng)典算法及其問(wèn)題

在各類算法中最知名的是協(xié)同過(guò)濾算法，它的出現(xiàn)標(biāo)志個(gè)性化推薦系統(tǒng)的誕生。作為當(dāng)今應(yīng)用最為廣泛的推薦算法，協(xié)同過(guò)濾算法較其他算法復(fù)雜度更低，可解釋強(qiáng)，部署方便，可以有效緩解信息過(guò)載問(wèn)題。

所有協(xié)同過(guò)濾算法的目標(biāo)都是盡可能地減小預(yù)測(cè)誤差，提高推薦列表多樣性，增強(qiáng)推薦列表的排序質(zhì)量。但是，受到冷啟動(dòng)和稀疏性這兩個(gè)推薦系統(tǒng)固有問(wèn)題的影響，傳統(tǒng)的基于用戶或基于物品的協(xié)同過(guò)濾相似性計(jì)算方法(例如，Cosine相似性和Pearson相似性)總是因冷啟動(dòng)問(wèn)題使新用戶沒有鄰居參考，或因稀疏性問(wèn)題導(dǎo)致評(píng)分?jǐn)?shù)據(jù)不足，選擇的鄰居不準(zhǔn)確，預(yù)測(cè)結(jié)果不理想。對(duì)于這些問(wèn)題，許多研究人員提出了相應(yīng)的改進(jìn)方法，例如，NIKOLAOS等人將Pearson相似性值進(jìn)行分級(jí)處理以增加相似性高鄰居的權(quán)值；HE等人利用觀點(diǎn)傳播的理論，通過(guò)歸一化之后的評(píng)分來(lái)計(jì)算推薦系統(tǒng)用戶之間的相互影響，并以此為依據(jù)進(jìn)行預(yù)測(cè)；基于信息熵的協(xié)同過(guò)濾將熵的概念與傳統(tǒng)的相似性度量相結(jié)合以提高推薦系統(tǒng)的性能，等等。

這些方法在一定程度上確實(shí)提高了預(yù)測(cè)的準(zhǔn)確性，但是，僅考慮用戶共同評(píng)分?jǐn)?shù)值差異是不全面的，也應(yīng)同時(shí)考慮利用用戶之間共同評(píng)分物品集合中物品的數(shù)量。因?yàn)榧幢銉蓚€(gè)用戶對(duì)相同物品評(píng)分差異較大，但只要這兩個(gè)用戶具有一個(gè)較大的共同評(píng)過(guò)分的物品集合，就可以推測(cè)這兩個(gè)用戶間的相似性較高。

更進(jìn)一步來(lái)說(shuō)，還應(yīng)該考慮這個(gè)共同評(píng)分物品集合的質(zhì)量，以區(qū)分共同評(píng)分物品集合大致相等時(shí)，集合中不同物品特征對(duì)用戶相似性的影響。如果用戶的共同評(píng)分集合中熱門物品較多，其相似性應(yīng)低于共同評(píng)分集合中以冷門物品為主的用戶，因?yàn)槟切┫矚g小眾物品的用戶之間顯然更具有偏好上的相似性。

綜上所述，本文研究共同評(píng)分在總評(píng)分?jǐn)?shù)中占比的問(wèn)題和用戶共同評(píng)分物品中熱門物品的影響度量問(wèn)題。設(shè)計(jì)融合共同評(píng)分?jǐn)?shù)量和質(zhì)量的相似性度量，以及在此基礎(chǔ)上的個(gè)性化推薦算法，以實(shí)現(xiàn)提高推薦系統(tǒng)性能的目標(biāo)。

3 算法設(shè)計(jì)(Algorithm design)

3.1 基于共同評(píng)分?jǐn)?shù)值度量用戶相似性

協(xié)同過(guò)濾推薦的核心假設(shè)是相似的用戶具有相似的偏好，在此基礎(chǔ)上，可以選擇相似性較高的鄰居，利用這些鄰居對(duì)目標(biāo)物品的評(píng)分來(lái)預(yù)測(cè)目標(biāo)用戶對(duì)該物品的評(píng)分。在這類算法中，計(jì)算用戶間的相似性是算法學(xué)習(xí)過(guò)程的核心步驟。兩個(gè)用戶相似性越大，該鄰居用戶在推薦的過(guò)程中的影響就越大。一般來(lái)說(shuō)，計(jì)算用戶相似性的主要依據(jù)就是兩個(gè)用戶對(duì)同一集合中物品評(píng)分的差異。理論上，評(píng)分?jǐn)?shù)值差異越小，兩個(gè)用戶的偏好和品味就越相似；反之，數(shù)值差異越大，偏好差異也就越大。

本文采用Pearson相關(guān)系數(shù)來(lái)度量?jī)蓚€(gè)用戶間基于共同評(píng)分物品集合的評(píng)分?jǐn)?shù)值，以度量相似性的一部分權(quán)重。Pearson相關(guān)系數(shù)是統(tǒng)計(jì)學(xué)上求兩個(gè)變量關(guān)系的方法，可以用來(lái)度量?jī)蓚€(gè)用戶對(duì)相同物品集合的評(píng)分差異。具體說(shuō)來(lái)，Pearson相關(guān)系數(shù)對(duì)用戶評(píng)分的偏差進(jìn)行加權(quán)平均，結(jié)果作為用戶或物品的相似性，且其取值范圍為-1.0至1.0，計(jì)算公式如式(1)所示：

3.2 融合共同評(píng)分集合數(shù)量和質(zhì)量的相似性度量

共同評(píng)分集合元素?cái)?shù)量多的用戶間相似性應(yīng)該大于共同評(píng)分?jǐn)?shù)量少的用戶，但如果兩個(gè)用戶是共同評(píng)分物品集合中物品較為熱門的情況，則他們的相似性應(yīng)低于相似條件下物品集合中物品較為冷門的情況。本文采用杰卡德相似性來(lái)度量?jī)蓚€(gè)用戶因共同評(píng)分物品集合元素?cái)?shù)量而決定的相似性權(quán)重。

Jaccard系數(shù)公式如式(2)所示，它計(jì)算了用戶和用戶都評(píng)過(guò)分的物品個(gè)數(shù)與兩個(gè)用戶評(píng)過(guò)分的物品總個(gè)數(shù)之比。該值越大，說(shuō)明這兩個(gè)用戶之間共同評(píng)過(guò)分的物品集合與兩人評(píng)過(guò)分物品的總數(shù)之間的比例越高，說(shuō)明在不考慮評(píng)分?jǐn)?shù)值的情況下，這兩個(gè)用戶對(duì)物品的選擇是相似的。

為了進(jìn)一步度量用戶共同評(píng)分物品集合中熱門物品的特征，即用戶共同評(píng)分集合的質(zhì)量，本文設(shè)計(jì)了如式(3)所示的(,)系數(shù)以降低含有熱門物品的共同評(píng)分集合的權(quán)重。其中，共同評(píng)分物品集合中每個(gè)物品被訓(xùn)練集中所有用戶選擇的次數(shù)記為物品度值d，給定共同評(píng)分物品集合中熱門物品特征，由該集合所有物品d的最大值表示?；谑?3)，如果兩個(gè)用戶共同評(píng)分物品集合中存在一個(gè)非常流行，即度值很高的物品，則這兩個(gè)用戶之間的共同評(píng)分物品集合的質(zhì)量就相對(duì)較低，其權(quán)值在相似性計(jì)算過(guò)程中被降低。

在此基礎(chǔ)上，融合共同評(píng)分集合數(shù)量和質(zhì)量的相似性由式(4)度量，稱該系數(shù)為共同評(píng)分?jǐn)?shù)量和質(zhì)量系數(shù)(Common Rating Quantity and Quality，CRQQ)。

最終，本文設(shè)計(jì)的綜合考慮共同評(píng)分物品數(shù)值差異與集合數(shù)量和質(zhì)量的相似性計(jì)算公式如式(5)所示，即兩個(gè)用戶間評(píng)分差異小，并且共同評(píng)分物品集合數(shù)量和質(zhì)量均較高時(shí)，兩個(gè)用戶最相似。如共同評(píng)分物品數(shù)量、共同評(píng)分物品質(zhì)量或共同評(píng)分?jǐn)?shù)值差異三者當(dāng)中只有一項(xiàng)到兩項(xiàng)較高時(shí)，其權(quán)重被降低，以便更加準(zhǔn)確地度量不同用戶間的特征差異。

3.3 未知評(píng)分預(yù)測(cè)方法

基于相似性計(jì)算結(jié)果，以及按照相似性從高到低選擇的個(gè)鄰居，本文使用式(6)把鄰居用戶對(duì)預(yù)測(cè)目標(biāo)物品的評(píng)分和該鄰居平均評(píng)分的差值做加權(quán)計(jì)算，基于該鄰居和目標(biāo)用戶相似性，來(lái)實(shí)現(xiàn)預(yù)測(cè)用戶對(duì)未知物品的評(píng)分。

4 實(shí)驗(yàn)設(shè)計(jì)(Experimental design)

4.1 數(shù)據(jù)集與基準(zhǔn)算法

本文使用MovieLens數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn)，該數(shù)據(jù)集有610 個(gè)用戶對(duì)9,742 部電影的100,836 條評(píng)分信息。為了保證實(shí)驗(yàn)的有效性，實(shí)驗(yàn)采用折十交叉驗(yàn)證進(jìn)行，即數(shù)據(jù)集被分成10 份，每次實(shí)驗(yàn)取其中一份作為測(cè)試集，另外9 份作為訓(xùn)練集，共進(jìn)行10 次實(shí)驗(yàn)，最終取10 次結(jié)果的平均值作為最終實(shí)驗(yàn)結(jié)果進(jìn)行比較。

為了驗(yàn)證本文設(shè)計(jì)的CRQQ算法，用來(lái)對(duì)比的基準(zhǔn)算法有三個(gè)，分別是：多層級(jí)協(xié)同過(guò)濾(Multi-Level Collaborative Filtering,MLCF)、用戶觀點(diǎn)傳播算法(User Opinion Spreading,UOS)以及使用了信息熵的Pearson算法(Pearson Entropy)。

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

本文使用平均絕對(duì)誤差(Mean Absolute Error,MAE)、均方根誤差(Root Mean Squared Error,RMSE)衡量算法對(duì)未知評(píng)分的預(yù)測(cè)誤差，使用半衰期(Half Life Utility,HLU)度量推薦列表排序質(zhì)量，采用Accuracy和F1比較各個(gè)算法對(duì)用戶偏好分類的預(yù)測(cè)準(zhǔn)確率。

MAE和RMSE公式如式(7)和式(8)所示，其計(jì)算由算法預(yù)測(cè)值和真實(shí)值的差值加權(quán)構(gòu)成，因此兩個(gè)誤差度量參數(shù)均為越低越好。

HLU代表算法的排序能力，算法將用戶喜歡的物品排在前面的能力越好，HLU值越大，其計(jì)算方法如式(9)所示：

Accuracy和F1指標(biāo)是推薦系統(tǒng)分類預(yù)測(cè)指標(biāo)，這兩個(gè)指標(biāo)的計(jì)算公式如式(10)—式(13)所示：

其中，在一次預(yù)測(cè)中，代表算法推薦了用戶喜歡的物品的總體數(shù)量，代表算法推薦了用戶不喜歡的物品的總體數(shù)量，代表系統(tǒng)未推薦用戶喜歡的物品的總體數(shù)量，代表系統(tǒng)未推薦用戶不喜歡的物品的總體數(shù)量。這幾個(gè)參數(shù)的數(shù)值越高，算法對(duì)用戶偏好分類(喜歡或不喜歡)的預(yù)測(cè)就越準(zhǔn)確。

5 實(shí)驗(yàn)結(jié)果與分析(Experimental results and analysis)

圖1展示了四種算法隨鄰居數(shù)變化的MAE誤差結(jié)果。鄰居數(shù)為1時(shí)，CRQQ算法比Pearson Entropy算法誤差低6.68%。隨著鄰居數(shù)的增加，所有算法誤差都隨之降低，但是CRQQ算法總是能在最少的鄰居數(shù)下最先達(dá)到最小誤差值，其次是UOS、Pearson Entropy、MLCF，最終CRQQ算法將準(zhǔn)確率提高了0.57%—6.68%。結(jié)果表明，本文設(shè)計(jì)的算法能夠更快速地選取最合適的鄰居，從而得到最精準(zhǔn)的預(yù)測(cè)結(jié)果。

圖1 幾種算法的MAE結(jié)果對(duì)比Fig.1 Comparison of MAE results of different algorithms

圖2展示了四種算法的RMSE誤差對(duì)比。RMSE對(duì)大誤差加大了懲罰，此時(shí)，CRQQ算法的誤差依舊是所有算法中最低的，這代表CRQQ算法預(yù)測(cè)結(jié)果很少出現(xiàn)大誤差，結(jié)果最準(zhǔn)確。隨著鄰居數(shù)增加，CRQQ算法誤差結(jié)果迅速下降，優(yōu)勢(shì)更加明顯，分別比Pearson Entropy誤差降低了0.48%—8.41%，比UOS誤差降低了1.40%—3.24%，比MLCF誤差降低了0.92%—3.23%。由此可知，CRQQ算法無(wú)論是大誤差還是小誤差都比其他算法少，進(jìn)一步說(shuō)明本文在預(yù)測(cè)準(zhǔn)確性上的改善能力。

圖2 不同算法的RMSE結(jié)果對(duì)比Fig.2 Comparison of RMSE results of different algorithms

圖3是四種算法的HLU排序能力指標(biāo)，值越大說(shuō)明算法排序能力越好?？傮w來(lái)說(shuō)，所有算法的HLU得分前期增長(zhǎng)明顯，后期略微下降。但不變的是，CRQQ得分一直是第一，它在鄰居數(shù)為26時(shí)取值最大為1.02。相同鄰居數(shù)下，UOS值為0.99，Pearson Entropy和MLCF算法為0.96，差別不大，但MLCF后期得分比Pearson Entropy算法更加平穩(wěn)。CRQQ算法在排序能力上比其他算法提高了0.63%—10.21%，這說(shuō)明共同評(píng)分?jǐn)?shù)量和質(zhì)量在推薦算法排序能力上的優(yōu)勢(shì)也比其他算法大。

圖3 不同算法的HLU結(jié)果對(duì)比Fig.3 Comparison of HLU results of different algorithms

圖4是算法的Accuracy得分對(duì)比。Accuracy代表算法預(yù)測(cè)用戶喜歡與否正確的概率，可以判斷系統(tǒng)分類是否有效。CRQQ算法得分穩(wěn)定在0.704上下，排名第一；Pearson Entropy得分在0.703上下，排名第二；第三、第四分別是MLCF(0.700)和UOS(0.699)。CRQQ比其他算法高了0.14%—0.71%，代表本文算法在對(duì)用戶喜歡和不喜歡某物品的分類上準(zhǔn)確度最高。

圖4 不同算法的Accuracy結(jié)果對(duì)比Fig.4 Comparison of Accuracy results of different algorithms

F1代表Precision和Recall的綜合得分，得分越高，說(shuō)明模型或算法的效果越理想。從圖5中可以看到，CRQQ算法從鄰居數(shù)為1時(shí)就具有領(lǐng)先的優(yōu)勢(shì)，UOS第二，Pearson Entropy第三，MLCF最差。在鄰居數(shù)為0至50之間，CRQQ算法總是能夠取得最高的F1得分。此時(shí)，CRQQ算法比其他算法高出了0.24%—1.05%。由此可見，使用共同評(píng)分?jǐn)?shù)量和質(zhì)量校正的算法分類精度效果更好。

圖5 不同算法的F1結(jié)果對(duì)比Fig.5 Comparison of F1 results of different algorithms

以上分析了四種算法的整體表現(xiàn)，表1則記錄了在相同鄰居數(shù)下，CRQQ算法與其他算法在各指標(biāo)的對(duì)比中提升的最高百分比。

表1 最高提升百分比Tab.1 Best improvement percentage

由表1可知，本文算法在五種指標(biāo)上分別高出MLCF算法0.63%—5.98%，高出UOS算法0.70%—3.24%，高出Pearson Entropy算法4.44%—10.21%。

總體而言，本文設(shè)計(jì)的算法CRQQ綜合表現(xiàn)領(lǐng)先，Pearson Entropy算法次之，UOS算法第三，多層級(jí)協(xié)同過(guò)濾算法MLCF第四。但當(dāng)考慮算法在相同的、且較少鄰居數(shù)下的對(duì)比效果時(shí)，Pearson Entropy算法表現(xiàn)較差，因其達(dá)到最優(yōu)預(yù)測(cè)效果，在相同條件下需要更多的鄰居。值得注意的是，CRQQ算法不但各個(gè)指標(biāo)領(lǐng)先，且需要的鄰居數(shù)量也最少，體現(xiàn)出一定的性能優(yōu)越性。

6 結(jié)論(Conclusion)

為提高協(xié)同過(guò)濾個(gè)性化推薦算法的預(yù)測(cè)準(zhǔn)確性，提升推薦列表排序質(zhì)量，增強(qiáng)算法對(duì)偏好分類的準(zhǔn)確性，本文研究了兩個(gè)用戶間共同評(píng)分物品集合的數(shù)量和質(zhì)量對(duì)用戶相似性度量的影響，設(shè)計(jì)了融合共同評(píng)分?jǐn)?shù)量和質(zhì)量的相似性度量方法和對(duì)應(yīng)的協(xié)同過(guò)濾個(gè)性化推薦算法。并在MovieLens電影評(píng)分?jǐn)?shù)據(jù)集上與領(lǐng)域內(nèi)幾個(gè)典型協(xié)同過(guò)濾算法對(duì)比，研究發(fā)現(xiàn)本文設(shè)計(jì)的融合用戶共同評(píng)分?jǐn)?shù)量和質(zhì)量的協(xié)同過(guò)濾個(gè)性化推薦算法可以將預(yù)測(cè)誤差降低8.41%，將推薦列表排序性能提高10.21%，將偏好分類預(yù)測(cè)準(zhǔn)確率提高2.55%。實(shí)驗(yàn)證明，改良后的算法無(wú)論是預(yù)測(cè)準(zhǔn)確性還是分類或排序能力都有較大的提升，充分說(shuō)明共同評(píng)分物品對(duì)推薦算法評(píng)分預(yù)測(cè)的影響。在未來(lái)的工作中，可以繼續(xù)挖掘用戶公共評(píng)分的其他影響，進(jìn)一步提高算法性能。