一種融合用戶相似性與評分距離的個性化推薦算法

蘇 湛，黃 忠，艾 均

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

1 引言(Introduction)

隨著互聯(lián)網(wǎng)技術(shù)的廣泛應(yīng)用，在網(wǎng)上“遨游”的人們時時刻刻都在生產(chǎn)出大量的數(shù)據(jù)，人類從信息匱乏變成信息過載。海量數(shù)據(jù)使消費者很難找到自己最感興趣的信息，而互聯(lián)網(wǎng)上的商家也需要一種技術(shù)來幫助他們找到真正對產(chǎn)品感興趣的潛在消費者。尤其是當下新型冠狀病毒肺炎疫情促使人們越發(fā)依賴互聯(lián)網(wǎng)進行消費、學(xué)習和交流，從而進一步加劇了這一問題。

能夠解決這一問題的個性化推薦算法具有重要的應(yīng)用價值，設(shè)計恰當?shù)哪Ｐ腿ダ斫庥脩羝茫A(yù)測用戶行為，對人工智能和機器學(xué)習理論的進一步發(fā)展也具有重要的推動作用，因此個性化推薦算法在相關(guān)領(lǐng)域得到了廣泛的研究。亞馬遜、Facebook、京東、淘寶等公司都擁有自己的個性化推薦系統(tǒng)和算法，此外包括電影、音樂推薦等細分領(lǐng)域?qū)€性化推薦算法的應(yīng)用也同樣廣泛。

本文通過研究用戶間共同評分相似性對潛在用戶進行篩選，使用篩選之后的鄰居集合預(yù)測目標的評分，然后按照預(yù)測結(jié)果生成推薦列表，在有效的數(shù)據(jù)集上驗證算法的有效性。

2 相關(guān)工作(Related work)

2.1 推薦系統(tǒng)分類和問題

根據(jù)領(lǐng)域內(nèi)的一般理解，個性化推薦算法可以分為四種主要類型：基于內(nèi)容的推薦算法、協(xié)同過濾推薦算法、基于知識的推薦算法和混合推薦算法。

第一類，基于內(nèi)容(Content-based)的個性化推薦算法用物品的描述性屬性來進行有針對性的推薦?！皟?nèi)容”指的就是對物品特征的描述，表示內(nèi)容特征的標簽就是這一類推薦算法的一種常見計算形式。例如，當一個用戶對“史詩”類型電影常常給予高評價時，帶有“史詩”標簽的新電影就可以推薦給該用戶。算法會基于用戶歷史數(shù)據(jù)判斷出用戶對這一內(nèi)容標簽的偏好概率，并計算任意一個帶有該標簽的電影被該用戶喜歡或不喜歡的可能性，例如通過比較兩個偏好的樸素貝葉斯概率大小就是一種預(yù)測用戶對該電影偏好的常見方法。

第二類，基于記憶(Memory-based)的協(xié)同過濾(Collaborative Filtering,CF)算法和基于模型(Model-based)的協(xié)同過濾算法是協(xié)同過濾算法的兩個子類型。基于記憶的協(xié)同過濾算法，無論是基于物品還是基于用戶，都基于相似的個體表現(xiàn)出相似的評分模式行為，相似的對象更容易獲得相似的評分這樣的假設(shè)。例如，要預(yù)測一個目標用戶對某個電影的評分，如果能夠找到一組和這個用戶具有高度相似歷史評分的用戶群體(通常被稱為鄰居用戶)，因為這些鄰居用戶歷史上的評分和目標用戶高度相似，那么鄰居用戶對目標物品的評分可以很自然地作為目標用戶對該物品評分的參考數(shù)據(jù)。這類個性化推薦算法在預(yù)測中綜合考慮用戶評分均值差異和用戶之間相關(guān)性差異來得到最終的預(yù)測結(jié)果。

另一方面，基于模型的協(xié)同過濾個性化推薦算法包括聚類模型、距離模型、最大熵模型、矩陣分解模型和相似性網(wǎng)絡(luò)模型等多種類型的設(shè)計方案。基于模型的協(xié)同過濾算法同樣需要預(yù)測目標用戶和社區(qū)用戶的評分數(shù)據(jù)，但這類推薦算法通常先構(gòu)造描述推薦系統(tǒng)的某種模型，并訓(xùn)練獲得這些模型的必要參數(shù)，然后基于這些訓(xùn)練獲得的參數(shù)來對未知評分進行預(yù)測。矩陣分解模型本質(zhì)上擬合平均矩陣中高度相關(guān)的那些用戶評分，通過分解來對評分矩陣降維，抽象出用戶特征矩陣和物品特征矩陣。在這一過程中，那個不易被擬合的評分被適當忽略。

第三類，基于知識的個性化推薦算法有兩種常見形式，包括基于約束條件的推薦算法和基于案例的推薦算法。在實際生活中，很多商品的消費行為常常是頻度很低的，如房屋、汽車、珠寶等，肯定不能像書籍、電影或外賣一樣被用戶高頻度消費和評價。一方面，因為這些物品的價格更高；另一方面，一個用戶的評價對另一個用戶的參考價值也相對更低。因此，基于知識的個性化推薦系統(tǒng)需要將已知的物品數(shù)據(jù)基于專家知識進行建模和抽象，抽象結(jié)果數(shù)值作為知識系統(tǒng)存儲，并在用戶提出自己需求的時候，通過約束條件疊加進行篩選和推薦，或者基于案例篩選并通過參數(shù)條件的替換進行推薦。

第四類，混合推薦算法則綜合上述多種不同類型的推薦算法，力求獲得更好的推薦性能，或者滿足不同條件下的推薦需求，其混合方案包括加權(quán)型、切換型、交叉型、特征組合型、瀑布型、特征增強型和元級型等混合推薦策略。

盡管針對推薦系統(tǒng)已經(jīng)涌現(xiàn)了很多研究并應(yīng)用比較廣泛，但仍有一些挑戰(zhàn)吸引著相關(guān)領(lǐng)域的科學(xué)家，例如冷啟動問題、數(shù)據(jù)稀疏性問題、算法的可擴展性、預(yù)測的準確性、運行時間和推薦多樣性。

冷啟動指的是加入系統(tǒng)的新用戶和新物品在沒有評價數(shù)據(jù)等關(guān)鍵信息條件下的推薦問題；數(shù)據(jù)稀疏性則是指用戶或物品評價評分數(shù)據(jù)量不足造成的推薦不準確或不適當問題；算法的可擴展性既包括算法訓(xùn)練、預(yù)測時間復(fù)雜度，也包括算法學(xué)習之后需要存儲的模型相關(guān)數(shù)據(jù)大小代表的空間復(fù)雜度；預(yù)測的準確性則可以從推薦算法對評分的預(yù)測誤差數(shù)值大小、對用戶喜歡和不喜歡兩種偏好評價的預(yù)測準確性或推薦列表是否能將用戶喜歡的物品排在前列這三種情況進行度量；推薦多樣性則考查推薦的物品列表中，各種物品的特征差異大小，一般情況下一個推薦列表中的物品相似性越低，物品流行度越多樣，推薦算法的多樣性就越好。

最緊迫的問題仍然是提高推薦預(yù)測的準確性，為此許多學(xué)者提出了改進的相似性計算算法。為了測量相似性，HAWASHIN等人基于用戶興趣設(shè)計了一種混合的相似性度量方法。SINGH等人在確定相似性時分別考慮消費者對單個商品相似特征的好惡。AI等人使用相似性來建模用戶-用戶網(wǎng)絡(luò)，并將中心性度量作為提高預(yù)測準確性的一個因素。通過引入指定的距離函數(shù)，MU等人增加了Pearson相似度。JOORABLOO等人提出了一種新的用戶/項目鄰域重新排序方法，該方法考慮了用戶/項目相似性的未來趨勢，如Slope One算法及其變體，將評分差異視為用戶之間的距離，并使用該距離來預(yù)測推薦的未知評分。所有這些技術(shù)都提高了推薦預(yù)測的準確性。

盡管Slope One算法計算過程簡潔，其模型簡單，易于理解，可解釋性強，但它將所有符合條件的用戶都作為鄰居使用，不考慮用戶間的相關(guān)性大小，這就導(dǎo)致這一算法在應(yīng)用中需要緩存大量的鄰居間距離數(shù)據(jù)作為學(xué)習結(jié)果。

本文探索的核心科學(xué)問題是與預(yù)測目標負相關(guān)的用戶在基于距離的推薦模型中是否對預(yù)測起到正面作用，這些作用有多大；這些潛在的正面作用是否可以適當犧牲來降低預(yù)測需要的鄰居，以換取算法可擴展性的提升。

概括地講，本文的研究主要有兩點貢獻。

(1)基于實際數(shù)據(jù)研究了相關(guān)性較低鄰居用戶的推薦的影響，發(fā)現(xiàn)負相關(guān)和相關(guān)性低的鄰居用戶可以在預(yù)測中省略，這種省略會給推薦過程中的預(yù)測帶來多方面的正面作用；

(2)基于上述發(fā)現(xiàn)，本文設(shè)計了基于融合用戶相似性與評分距離的個性化推薦算法，該方法成功降低了傳統(tǒng)距離模型算法的空間復(fù)雜度，顯著減少了預(yù)測時所需的用戶數(shù)量，同時還提高了預(yù)測準確性、推薦列表排序質(zhì)量和推薦列表的多樣性。

2.2 用戶相似性度量

基于用戶共同評分物品集合計算的用戶相關(guān)性，在推薦系統(tǒng)研究中一般被稱為用戶間的相似性(User Similarity)。以基于記憶的協(xié)同過濾推薦算法為例，其核心思想就是通過利用與目標用戶興趣偏好相似的用戶群體的喜好程度來預(yù)測和推薦。具體來說就是計算目標用戶與其他所有用戶兩兩之間的相似性，再通過相似性從高到低來選擇必要的個鄰居，最后根據(jù)鄰居的評分來對目標用戶進行預(yù)測，相似性是這一過程的核心。

因此，推薦系統(tǒng)領(lǐng)域提出了許多方法來解決這個問題，例如皮爾遜相關(guān)系數(shù)、余弦相似、歐幾里得距離、置信度相似度、均方距離、用戶行為概率、Jaccard、Spearman相關(guān)性向量相似度、Bhattacharyya系數(shù)及用戶意見傳播等。這些相似性算法各有特點，考慮不同的因素和計算方式來度量用戶間的相似性。

2.3 基于距離模型的協(xié)同過濾

基于距離模型的協(xié)同過濾不考慮用戶間的相似性，以Slope One算法為例，該算法是一種基于模型的協(xié)同過濾推薦算法，先基于用戶評分計算用戶間的評分距離，其核心思想是根據(jù)兩用戶間之前的電影評分采用線性回歸分析方法。假設(shè)用戶和之間的評分具有線性關(guān)系：=+。在預(yù)測時，不用刻意選擇那些相關(guān)性高的用戶，所有對目標物品評過分，且與目標用戶有距離的用戶都將被選擇作為鄰居來進行預(yù)測。根據(jù)計算的兩用戶間評分的偏差值，加上已知用戶評分來計算未知評分。最終的預(yù)測結(jié)果是所有符合上述條件預(yù)測的平均值。

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

3.1 符號說明

將已知評分數(shù)據(jù)集分為訓(xùn)練集trainingSet和測試集testSet。通過訓(xùn)練集進行學(xué)習，基于學(xué)習的結(jié)果對測試集中的評分進行預(yù)測，并考查預(yù)測結(jié)果和真實結(jié)果之間的差異，從而度量算法的性能。

3.2 算法原理

已知用戶、和三人對物品的評分分別為1、2、4.5，對物品的評分分別為3、2.5、1，預(yù)測的目標是用戶對物品的評分，而已知r=1.5，r=2。

按照皮爾遜相關(guān)系數(shù)計算相似性，s=1.0，s=-1.0。按照Slope One算法計算用戶間評分距離，得到=0.25，=-0.5，

從這個例子可以看出，相似性和距離模型對用戶間關(guān)系的計算是有明顯差異的?？梢詫@一差異加以利用，以提升推薦算法的可擴展性和預(yù)測性能。

基于上述分析，本研究設(shè)計了一種融合用戶相似性與評分距離的個性化推薦算法(Fusion of User Similarity and Distance,FSD)。理論上，該算法既可以應(yīng)用于用戶間相似性與評分距離的融合，也可以應(yīng)用于物品間相似性與評分距離的融合。為了簡便起見，本文在討論中僅討論用戶間的相似性和評分距離。

通過觀測上述例子和分析原理可以發(fā)現(xiàn)，用戶評分距離不帶有相關(guān)性含義，評分距離近的鄰居并不一定比評分距離遠的鄰居更具參考意義。相反，相似性高的用戶在理論上與預(yù)測目標更相關(guān)，在預(yù)測中應(yīng)該有更高的權(quán)重。

因此，F(xiàn)SD假設(shè)相似性低的鄰居用戶在距離模型中作用更低。閾值T表示相似性在FSD模型中可以保留鄰居的最小值，通過這一設(shè)置，去除一部分權(quán)重小的鄰居，再基于距離模型考查預(yù)測特征的變化，以決定T合適的取值。

這樣，F(xiàn)SD模型融合了用戶間相似性與距離特征，進行推薦系統(tǒng)的評分預(yù)測。

3.3 FSD算法的計算方法

本文設(shè)計的FSD使用皮爾遜相關(guān)系數(shù)，基于評分訓(xùn)練集計算用戶之間的相似性。一般來說，兩個用戶之間的相似性越大，兩個用戶的評分相關(guān)性就越強，該鄰居用戶在預(yù)測中的重要性就越高。

FSD用戶之間的評分距離計算公式定義如下：

FSD算法根據(jù)公式(1)計算用戶之間的相似性，并通過公式(3)過濾用戶，選擇符合條件的用戶作為預(yù)測目標的鄰居用戶。

其中，N是用戶選擇的鄰居集， s是用戶和的相似性，T是FSD設(shè)定的閾值。

在此基礎(chǔ)上，公式(2)用來計算用戶間的評分距離，公式(4)用來預(yù)測未知用戶對物品的評分。

其中,N是用戶的鄰居， d是用戶和對物品的評分距離，||是鄰居的數(shù)量。

4 實驗設(shè)計(Experimental design)

4.1 實驗數(shù)據(jù)集

本實驗使用MoviesLens25 M數(shù)據(jù)集，包括有關(guān)電影屬性和用戶評分的信息。該數(shù)據(jù)集評分分數(shù)范圍為0.5—5，評分間隔為0.5，包括162,541 個用戶對62,423 部電影的25,000,095 個評分。本文實驗隨機選擇其中1,000 個用戶對62,423 個電影的146,533 個評分。

為了保證實驗的可靠性，本文采用了十折交叉驗證，在實驗中數(shù)據(jù)集被隨機分為10 份。每次使用1 份作為測試集，而其他9 組作為訓(xùn)練集，進行訓(xùn)練學(xué)習和預(yù)測檢驗，最終的結(jié)果為10 次實驗的平均值。

4.2 基準算法

本文將所提出的FSD算法與原Slope One算法、加權(quán)Slope One算法(Weighted Slope One,2013)、信息熵皮爾遜協(xié)同過濾(Pearson Entropy,2020)、資源分配協(xié)同過濾(RA,2014)、用戶觀點傳播(UOS,2015)、多級協(xié)同過濾(MLCF,2016)、用戶行為概率(UBP,2021)等近幾年領(lǐng)域內(nèi)科學(xué)家們設(shè)計的經(jīng)典算法進行比較。

4.3 評價指標

實驗主要考查了設(shè)計算法FSD與基準算法間在評分預(yù)測誤差、推薦列表排序質(zhì)量、推薦列表多樣性及算法可擴展性四個方面的性能差異。

本文使用平均絕對誤差(MAE)、均方根誤差(RMSE)來評估算法預(yù)測的誤差水平，預(yù)測誤差越低，算法對未知評分的預(yù)測越準確。采用半衰期效用指數(shù)(HLU)、歸一化折扣累積增益(NDCG)來評估推薦結(jié)果的排序性能。推薦列表的質(zhì)量越高，這兩項度量參數(shù)的評分越高。

MAE反映了算法預(yù)測的用戶評分與用戶實際評分的偏差，RMSE表示算法預(yù)測的用戶評分與實際評分之間偏差的均方根值。MAE值表示誤差，RMSE在開方之前將誤差的平方相加，從而增加對絕對值大于1的誤差的懲罰，減小對絕對值小于1的誤差的懲罰，故RMSE對大誤差更敏感。MAE和RMSE值越小，預(yù)測結(jié)果與實際評分的誤差越小，預(yù)測精度越高。實驗中測試集預(yù)測目標數(shù)量用表示，用戶的預(yù)測得分值用r'表示，用戶的實際評分值用 r表示。MAE和RMSE的定義如下：

HLU評估用戶真實評分和實際評分之間的差異，以衡量推薦列表對用戶的實用性，其定義如下所示：

其中，為推薦給每個用戶推薦列表中電影的數(shù)量， r為用戶對電影的評分，為訓(xùn)練集中的平均評分值，為需要提供推薦的用戶數(shù)量，為推薦列表的半衰期(本文實驗中的值取2)。HLU的值越大，算法將用戶喜歡的電影排在推薦列表前面的能力越強，系統(tǒng)排序質(zhì)量越高。

NDCG假設(shè)用戶最喜歡的電影在推薦列表中排名第一會更大程度上增加用戶的使用體驗。電影越相關(guān)，排名越高，用戶對系統(tǒng)的滿意度就越高，從而節(jié)省了用戶的時間，其定義如下：

其中，DCG是根據(jù)每個用戶的真實評分和預(yù)測評分列表計算的； R表示用戶是否喜歡在中排名的電影，R=1表示用戶喜歡該電影，R=0表示用戶不喜歡該電影。本文實驗中將用戶評分高于平均評分的評價看作喜歡，將低于、等于平均評分的評價看作不喜歡。NDCG是DCG的歸一化形式，由公式(9)得出，它將DCG歸一化到0—1。

5 實驗結(jié)果與分析(Experimental results and analysis)

依據(jù)公式(3)，通過給定的相似性閾值篩選距離模型需要的鄰居，圖1中顯示了相似性不同取值下，距離模型評分預(yù)測的誤差大小。

圖1 相似性閾值 Th 不同情況下FSD算法的評分預(yù)測誤差大小Fig.1 Prediction error of FSD algorithm with different threshold Th

圖1表明，合適的相似性閾值為T=0.0，所提出的FSD具有最佳預(yù)測精度，MAE為0.667，RMSE為0.874。此時，距離模型中相似性為負值的鄰居均已經(jīng)被除去。

圖2中MAE的比較結(jié)果表明，當鄰居數(shù)大于10時，所有算法的MAE都優(yōu)于MLCF預(yù)測方法。所提出的FSD算法的MAE為0.6997，表明相比之下預(yù)測精度次高，僅次于UBP算法。原Slope One算法的MAE為0.7055，相比之下FSD減少了0.8%的誤差。與所有其他算法相比，MAE平均提高了1.5%。

圖2 FSD與其他算法的MAE對比結(jié)果Fig.2 MAE comparison result of FSD and other algorithms

如圖3所示，RMSE也表示推薦系統(tǒng)預(yù)測誤差的大小，和MAE相比，RMSE對較大的誤差更敏感。FSD算法的RMSE最小，為0.8749；原始Slope One算法的RMSE次好，為0.8800。FSD將誤差降低了0.51%，相比于其他幾種算法，RMSE平均提高了2.3%。

圖3 FSD與其他算法的RMSE對比結(jié)果Fig.3 RMSE comparison result of FSD and other algorithms

通過圖2和圖3可以看出，MAE和RMSE中的FSD算法與其他算法相比，具有更小的預(yù)測誤差。這說明FSD算法既降低了整體誤差，也降低了較大的預(yù)測誤差。

圖4展示了NDCG的比較結(jié)果。NDCG體現(xiàn)了推薦列表的排名質(zhì)量，得數(shù)越高越好。FSD算法的最高分是0.7472，比原Slope One算法(其得分為0.7394)高出1%，加權(quán)Slope One表現(xiàn)要差些；與其他算法相比，平均提高了3.8%。

圖4 FSD與其他算法的NDCG對比結(jié)果Fig.4 NDCG comparison result of FSD and other algorithms

HLU反映了用戶對推薦列表的興趣程度，如圖5所示，其分數(shù)越高，用戶對有限頁面越感興趣。FSD算法的得分為1.0065，原始的Slope One算法得分為0.977，提高了3%；與其他算法相比，平均提高了3.3%。

圖5 FSD與其他算法的HLU對比結(jié)果Fig.5 HLU comparison result of FSD and other algorithms

通過分析圖4和圖5可知，F(xiàn)SD算法在NDCG方面有更高的值，說明FSD算法的排序能力較好；隨著HLU值中鄰居數(shù)的增加，略差于RA算法。但是FSD算法比Slope One等算法提高很多，而且比RA算法預(yù)測誤差更小，所以在排序質(zhì)量指標上有很好的表現(xiàn)，性能也更穩(wěn)定。

圖6顯示了每個算法在預(yù)測過程中對測試集中所有目標使用的平均鄰居數(shù)。圖中除FSD和Slope One之外(與Weighted Slope One重合)，其他曲線幾乎重合在一起，這些算法選擇的鄰居數(shù)量是相同的。由于滿足對目標電影評分條件的用戶數(shù)量有限，預(yù)測的目標用戶只能接觸到少數(shù)符合條件的用戶，因此增長緩慢，即使水平坐標中計劃使用的鄰居數(shù)量繼續(xù)線性增長。盡管在圖2中預(yù)測誤差降低的絕對數(shù)值較小，但預(yù)測中使用的鄰居數(shù)量如圖6所示卻減少很多，這提升了算法的可擴展性。

圖6 用于預(yù)測的實際鄰居數(shù)與算法計劃選擇的鄰居數(shù)Fig.6 The actual number of neighbors for prediction and the number of neighbors the algorithm plans to choose

實驗中，F(xiàn)SD算法平均使用55 個鄰居進行預(yù)測，優(yōu)于原Slope One算法的78 個鄰居,其預(yù)測時所需鄰居使用量減少了29.49%。這一巨大提升既加快了距離部分的計算速度，也減少了訓(xùn)練之后需要保存的數(shù)據(jù)數(shù)量(主要是用戶間評分距離數(shù)據(jù))，通過增加相似性部分的計算和篩選，有效降低了算法的空間復(fù)雜度，進而提升了算法的可擴展性。

相同硬件和參數(shù)下算法訓(xùn)練測試所需時間如表1所示。相同條件下每種算法所需的計算時間差異較大，F(xiàn)SD算法在性能整體提升非常明顯的情況下，需要將原Slope One算法的計算時間輕微增加1.9%。

表1 相同硬件和參數(shù)下算法訓(xùn)練與測試所需時間Tab.1 Time required for algorithm training and testing with the same hardware and parameters

6 結(jié)論(Conclusion)

本文為了提升距離個性化推薦算法的可擴展性和其他主要性能，將用戶間相似性低于閾值的潛在鄰居從預(yù)測目標的鄰居集合中剔除，再利用用戶間評分距離估計目標用戶對未知物品的評分，設(shè)計了一種融合用戶相似性與評分距離的個性化推薦算法。

與原距離模型算法相比，所提出的方法不僅在預(yù)測過程中所需的鄰居數(shù)減少了29.49%，而且預(yù)測誤差也降低了，推薦列表排名性能提高了3.8%，有效地提升了距離模型的可擴展性和其他各項主要性能。

研究表明，在推薦系統(tǒng)的預(yù)測問題中，通常是通過相似性選擇過濾掉不是很相關(guān)的鄰居。雖然相關(guān)性較低的鄰居也可以計算出評分距離，但相關(guān)性不強，會對預(yù)測產(chǎn)生負面影響。與預(yù)測目標不夠相似的鄰居用戶對預(yù)測造成的弊大于利，應(yīng)該被丟棄。這種丟棄不僅可以提高算法的可擴展性，還可以提高其預(yù)測和推薦性能，應(yīng)該在未來的研究中得到更多的考慮。

本文的不足之處是預(yù)測誤差提升幅度不大，希望能在未來的研究工作中在融合相似性和評分距離的基礎(chǔ)上，進一步擴展算法的性能。