基于用戶多樣性偏好的top-N推薦算法

劉 莉

三明學(xué)院 信息工程學(xué)院，福建 三明365004

數(shù)據(jù)爆炸式增長，使得人們從信息匱乏時代到信息過載時代，推薦系統(tǒng)作為解決信息過載的有效方法，被廣泛應(yīng)用于電子商務(wù)、音樂、新聞等多個領(lǐng)域。

推薦算法主要分為基于內(nèi)容的推薦、協(xié)同過濾推薦[1]、基于知識的推薦、混合推薦等。協(xié)同過濾推薦是最廣泛流行的一種方法，包括基于內(nèi)存的方法（memorybased）和基于模型（model-based）的方法[2]?；趦?nèi)存的方法包括基于用戶的協(xié)同過濾推薦算法（User-based Collaboration Filtering，UserCF）和基于項目的協(xié)同過濾推薦算法（Item-based Collaboration Filtering，ItemCF）[3]?；谀Ｐ偷姆椒ㄖ饕抢脵C器學(xué)習(xí)或數(shù)據(jù)挖掘方法進行訓(xùn)練學(xué)習(xí)并建立推薦模型，包括聚類、貝葉斯網(wǎng)絡(luò)、決策樹等[4]。

對于協(xié)同過濾算法，影響其性能的關(guān)鍵步驟包括相似度的計算和基于相似度如何做推薦。傳統(tǒng)相似度的計算方法主要有余弦和修正余弦相似度[5]、Pearson相關(guān)系數(shù)[6]、Jaccard相似系數(shù)、歐式距離，其中比較流行的是修正余弦相似度和Pearson相關(guān)系數(shù)，這兩種方法在中心化方式上有著細(xì)微的差別。文獻[7-8]考慮了不同用戶對同一項目的評分差異，對用戶相似度進行了改進。

典型的推薦問題有評分預(yù)測和top-N推薦，評分預(yù)測一直是推薦系統(tǒng)的研究熱點，是根據(jù)用戶的歷史評分，預(yù)測對未評分項目的評分，評分預(yù)測問題的評價指標(biāo)主要是均方根誤差（Root Mean Square Error，RMSE）和平均絕對誤差（Mean Absolute Error，MAE），而top-N推薦更符合實際的需求，是指把用戶最可能喜歡的N個項目推薦給用戶，其主要評價指標(biāo)是召回率和準(zhǔn)確率。在top-N任務(wù)中，很多文獻以評分預(yù)測指標(biāo)作為優(yōu)化目標(biāo)，即把評分預(yù)測最高的N個項目推薦給用戶，文獻[9]指出評分預(yù)測的誤差越小，top-N推薦的準(zhǔn)確度不一定越高。

僅考慮推薦的精度，忽視用戶興趣的廣泛性和用戶偏好，并不一定能獲得用戶的滿意。在不影響推薦精度的前提下，提高推薦的多樣性可以優(yōu)化用戶個性化體驗。

目前，對多樣性的研究主要包括多樣性評價指標(biāo)和多樣性優(yōu)化[10]。多樣性的定義決定了如何優(yōu)化多樣性，部分文獻用啟發(fā)式策略對傳統(tǒng)方法得到的推薦列表進行二次優(yōu)化[11]，典型的方法有重排序、目標(biāo)函數(shù)優(yōu)化、用戶模型分割。文獻[12]用項目類別衡量用戶列表的多樣性，具體考慮類別覆蓋、冗余、列表大小等因素，提出基于類別二項分布模型的重排序算法。文獻[13-14]對推薦列表也進行了二次排序。文獻[15-16]分別從用戶興趣和用戶活躍度對用戶進行分類，針對不同類作相應(yīng)的推薦。以上文獻雖然考慮了多樣性，但沒有對個體的興趣偏好進行評估。

本文提出了一種新的方法ItemCF-DP（ItemCF based on Diversity Preference），利用用戶歷史項目評分矩陣和項目類別矩陣，獲得用戶-類別權(quán)重矩陣，根據(jù)該列表的類別權(quán)重對協(xié)同過濾算法的推薦列表進行二次選擇，通過相關(guān)參數(shù)的調(diào)節(jié)可以進一步優(yōu)化推薦的準(zhǔn)確性、多樣性和用戶滿意度。

1 相關(guān)工作

1.1 多樣性指標(biāo)

多樣性指標(biāo)主要包括個體多樣性和總體多樣性。

1.1.1 個體多樣性

ILD（Intra-List Diversity）指標(biāo)是用來衡量用戶內(nèi)部的多樣性，表示用戶的推薦列表中，物品之間的不相似程度。用戶u的推薦列表多樣性定義為：

N為推薦列表長度，L(u)是用戶u的推薦列表，dist(i,j)是相異項目之間的差異程度，可以定義為1-sim(i,j)，sim(i,j)是項目i和項目j的相似度。

1.1.2 系統(tǒng)多樣性

根據(jù)公式（1）定義的ILD指標(biāo)，系統(tǒng)多樣性可以定義為用戶個體多樣性的平均：

U是系統(tǒng)的用戶集，另外，系統(tǒng)多樣性還可以用海明距離HD（Hanming distance）、基尼系數(shù)Gini、SSD（Self-System Diversity）等。

1.2 項目相似度度量公式

top-N推薦的主要任務(wù)是預(yù)測用戶會不會看某部電影，而不是預(yù)測用戶會給電影打多少分，因此在計算基本相似度時，忽略評分分值，將評分行為當(dāng)做一種隱式反饋，有評分為1，無評分為0。對于兩個不同項目i和j，假設(shè)用戶對這兩個項目評分行為向量分別為ri和rj，則用這兩個向量的夾角余弦值來衡量項目i和j的相似度wij，用公式表示為：

另外，也可以用集合運算表示為：

其中，Ni和Nj是分別喜歡項目i和項目j的用戶集合，分子可以理解為同時喜歡項目i和項目j的用戶數(shù)。

考慮用戶活躍度對相似度有一定的影響，修正為：

其中，N(u)為用戶u的活躍度，即用戶u喜歡的項目數(shù)。

2 基于用戶多樣性偏好的top-N推薦算法

2.1 基于內(nèi)容的用戶多樣性偏好

根據(jù)多樣性的定義，用戶多樣性體現(xiàn)在用戶項目列表中項目之間的不相似程度，本文從內(nèi)容的角度衡量多樣性。

用戶多樣性體現(xiàn)在用戶喜好項目的廣泛性上，不同用戶具有不同的多樣性需求，有的用戶興趣廣泛，喜歡看各種類型的電影，而有的用戶興趣較單一，僅喜歡看一兩種固定類型的電影。

另外，在用戶多樣性的基礎(chǔ)上，用戶對不同類別的項目偏好程度有所不同，比如某用戶看了100部電影，其中有80部是動作片，20部是動畫片，說明用戶對動作片的偏好遠(yuǎn)遠(yuǎn)勝過動畫片。在為該用戶做推薦時，兩種類型的電影都應(yīng)涉及，但動作片的占比應(yīng)更大。

因此，在推薦時，既要考慮用戶的多樣性需求，還應(yīng)考慮其興趣偏好，以提高用戶的滿意度。

本文同時定義了用戶多樣性和用戶滿意度兩個評估指標(biāo)，用戶滿意度用來評估給用戶推薦的項目列表是否符合用戶歷史的興趣偏好。

2.1.1 構(gòu)造用戶-類別權(quán)重矩陣

定義類別集合C={c1,c2,…,cs}，用戶集合U={u1,u2,…,um}，根據(jù)用戶-評分?jǐn)?shù)據(jù)和項目-類別數(shù)據(jù)，統(tǒng)計得到用戶-類別次數(shù)矩陣，如表1所示，fij為用戶ui所喜歡項目被標(biāo)記為cj的次數(shù)。規(guī)定每個項目對標(biāo)簽次數(shù)的總貢獻值為1，因此對于有多個類別標(biāo)簽的項目，應(yīng)為該類別標(biāo)簽在項目總的類別中出現(xiàn)的頻率，如某項目有三個類別標(biāo)簽，則每個類別標(biāo)簽的次數(shù)為1/3。

表1 用戶-類別次數(shù)矩陣Table 1 User-category frequency matrix

進一步可計算出用戶對每個類別的偏好用戶u對類別標(biāo)簽c的權(quán)重計算為：

其中，fuc為用戶u喜歡項目被標(biāo)記為c的次數(shù)，分母為用戶u喜歡項目的類別總標(biāo)記數(shù)。

2.1.2 基于信息熵的用戶多樣性

熵是熱力學(xué)中表示分子狀態(tài)混亂程度的物理量，信息論之父香農(nóng)據(jù)此提出了信息熵，用來描述信息的不確定度。

根據(jù)用戶-類別權(quán)重矩陣，每個用戶對應(yīng)一個標(biāo)簽分布向量，若各個類別分布均勻，則信息熵最大，表明用戶多樣性需求越大。用戶多樣性定義為：

其中，n是標(biāo)簽數(shù)量，puc是用戶u選擇類別c的概率。

2.2 改進的項目相似度計算

針對公式（5），由于僅考慮評分行為，忽略評分分值，帶來相似度計算的不準(zhǔn)確。不同用戶對項目i和j相似度有著不同的貢獻，比如用戶u對i的評分為5，對j評分為1，對于用戶u來說，i和j評分差異很大，說明它們很不相似；另一情況，用戶v對i和j評分都為5，認(rèn)為其很相似。即同一用戶對不同項目的評分差異對相似度有一定的影響，且這種分值差異影響具有非線性的特征。

用戶u對項目i和j的相似度影響定義如下：

其中，rui和ruj是用戶u分別對項目i和項目j的評分。

結(jié)合顯性評分的項目相似度計算公式為：

對項目相似度矩陣w進行最大值歸一化，可以提高推薦準(zhǔn)確率。歸一化的相似度[17]為：

因此，用戶u對項目i的興趣計算公式為：

其中，N(u)是用戶u喜歡的項目集合，S(i,K)是與項目i最相似的K個項目的集合，ruj是用戶u對項目j的興趣，基于隱式反饋，有評分行為值為1，反之為0。

2.3 ItemCF-DP算法

2.3.1 算法基本描述

對于用戶u的top-N推薦，根據(jù)公式（11）計算用戶對未選擇過的項目的興趣rui，得到一個降序排列的初始推薦序列（長度為M，M>N），M的值可以調(diào)節(jié)。對于初始序列中的每個項目，根據(jù)用戶對不同類別的偏好決定是否對該項目進行推薦，直到項目數(shù)量為N或者遍歷完初始序列，最終得到一個長度為N的推薦列表。

在N一定的情況下，本文算法涉及了幾個重要的參數(shù)：

（1）初始推薦序列長度M

該參數(shù)為初始推薦序列的長度，通過多次實驗，可以找到一個最優(yōu)的參數(shù)使推薦性能最好。

（2）用戶偏好誤差門限threshold

該參數(shù)可用于調(diào)節(jié)用戶偏好誤差容忍度，即容許與用戶歷史偏好有一定的差距，threshold∈[0,1]，設(shè)置為0，表示用戶偏好權(quán)重至少與歷史偏好相等，大于0時，表示用戶偏好權(quán)重比歷史偏好權(quán)重減少，值越大，減少的程度越大。

2.3.2 算法具體步驟

輸入：目標(biāo)用戶u、用戶-類別權(quán)重矩陣P、近鄰項目個數(shù)K

輸出：用戶u的top-N推薦序列R'(u)

步驟1根據(jù)公式（11）計算結(jié)果，得到一個降序排列的長度為M的初始推薦序列R(u)。

步驟2根據(jù)用戶-類別權(quán)重矩陣P和推薦列表長度N，得到推薦列表中每個標(biāo)簽應(yīng)有的次數(shù)CNuc。

步驟3遍歷初始推薦序列，每選擇一個項目，計算其每個類別標(biāo)簽次數(shù)，假設(shè)為tuc，判斷該用戶對應(yīng)的標(biāo)簽剩余次數(shù)CNuc是否大于誤差門限threshold，是則放入序列R(u)（如果一個項目有多個標(biāo)簽，則只要一個標(biāo)簽大于門限則放入），對應(yīng)的剩余標(biāo)簽個數(shù)CNuc更新為CNuc-tuc，否則跳過該項目。該遍歷過程直到R'(u)序列長度為N中止。

步驟4如果遍歷完R(u)，R'(u)序列長度仍然小于N，則按順序把之前跳過的商品加入R'(u)直到長度為N。

3 實驗結(jié)果與分析

3.1 數(shù)據(jù)集

實驗采用開源數(shù)據(jù)集Movielens的1M（ml-1m）和100k（ml-100k）版本，ml-1m包括6 040個用戶對3 900部電影的1 000 209個評分，ml-100k包括943個用戶對1 682部電影的100 000個評分，每個用戶至少對20部電影進行評分。評分僅為整數(shù)，從1到5分。電影類別包括action、Adventure、Animation等18個標(biāo)簽，每部電影可有多個類別。實驗隨機選擇數(shù)據(jù)集的80%作為訓(xùn)練集，20%作為測試集。

3.2 評估指標(biāo)

本文用準(zhǔn)確率（Precision）、召回率（Recall）、多樣性（Diversity）、用戶滿意度（Satisfaction）作為評估指標(biāo)。對用戶u推薦的N個項目記為R(u)，令用戶u在測試集上喜歡的項目集合為T(u)，召回率和準(zhǔn)確率的計算方法如下：

多樣性定義如公式（2）所示。

本文提出了一個新的指標(biāo)：用戶滿意度，以用戶訓(xùn)練集的用戶-類別權(quán)重向量xu與推薦列表中用戶-類別權(quán)重向量yu之間的歐式距離來度量。具體計算公式如下：

其中，d(xu,yu)表示兩個向量之間的歐式距離。

3.3 實驗結(jié)果

本文比較了提出的ItemCF-DP算法與UserCF、ItemCF、ItemCF-Norm（歸一化相似度）三種經(jīng)典算法，還分析了幾個重要參數(shù)對推薦結(jié)果的影響。

經(jīng)驗證，參數(shù)K（近鄰項目個數(shù)）取值為10，ItemCF性能最優(yōu)，在該參數(shù)相同的情況下對比ItemCF-DP與其他算法。另外，推薦列表長度N設(shè)定為10，對于數(shù)據(jù)集ml-1m，ItemCF-DP算法的誤差門限為0.4，對于數(shù)據(jù)集ml-100k，ItemCF-DP算法的誤差門限為0.6。各算法推薦性能對比如表2所示。

表2 各算法推薦性能對比Table 2 Comparison of recommendation performance of each algorithm

由表2可以觀察到，提出的ItemCF-DP算法明顯優(yōu)于其他算法。首先，在各個數(shù)據(jù)集上，準(zhǔn)確率和召回率比其他算法都有所提升，這主要是因為在計算項目相似度時，考慮了用戶對不同項目的評分差異。由于在生成推薦列表時考慮了用戶歷史興趣偏好，用戶滿意度較其他算法有顯著的提高。在ml-1m數(shù)據(jù)集上，ItemCF-DP算法比ItemCF算法在多樣性上降低了1.5%，而在用戶滿意度上提高了6.7%；比ItemCF-Norm算法在用戶滿意度上提高了5.2%；在m1-100k數(shù)據(jù)集上，比ItemCF和ItemCF-Norm算法在多樣性上降低了2.8%，而用戶滿意度上比ItemCF算法提高了8%，比ItemCF-Norm算法提高了7.1%。

幾個重要參數(shù)的影響：

（1）初始推薦序列長度M

M設(shè)置為推薦序列長度N的倍數(shù)，M=[1，2，3，4，5，6]，該參數(shù)對準(zhǔn)確率的影響如圖1所示，可以看出，隨著N的增大，準(zhǔn)確率有所下降，同樣地，當(dāng)M為N的2倍時，準(zhǔn)確率提升并趨于飽和。因此，M設(shè)置為2×N，推薦效果最好。

圖1 不同M對應(yīng)的PrecisionFig.1 Precision of different M

該參數(shù)對用戶滿意度的影響如圖2所示，可以看出，當(dāng)N=10和20時，當(dāng)M為N的1倍時，算法退化為Item-Norm結(jié)合評分差異，當(dāng)M為N的2倍時，用戶滿意度有所上升，并趨于飽和。

圖2 不同M對應(yīng)的SatisfactionFig.2 Satisfaction of different M

（2）用戶偏好誤差門限threshold

誤差門限threshold=[0，0.2，0.4，0.6，0.8，1]，該參數(shù)對準(zhǔn)確率的影響如圖3所示。

圖3 不同threshold對應(yīng)的PrecisionFig.3 Precision of different threshold

由圖3可以看出，門限對于準(zhǔn)確率的影響較小，門限設(shè)置過大或過小，極端情況相當(dāng)于直接取初始序列的前N個項目。

該參數(shù)對用戶滿意度的影響如圖4所示，對于ml-1m數(shù)據(jù)集，門限為0.4時，用戶滿意度性能最優(yōu)，比最低值（門限為0）提高了3.1%。對于ml-100k數(shù)據(jù)集，門限為0.6時，用戶滿意度性能最優(yōu)，比最低值（門限為0）提高了4.8%。因此，對于不同數(shù)據(jù)集，通過調(diào)節(jié)誤差門限可以優(yōu)化推薦算法性能，在保證準(zhǔn)確率的前提下，提高推薦系統(tǒng)的用戶滿意度。

圖4 不同threshold對應(yīng)的SatisfactionFig.4 Satisfaction of different threshold

4 結(jié)束語

本文針對用戶多樣性偏好的需求，根據(jù)用戶歷史評分矩陣獲得用戶多樣性偏好權(quán)重矩陣，在計算項目相似度時結(jié)合了隱性反饋和顯性評分，提高了相似度計算的準(zhǔn)確性，在最終為用戶生成推薦列表時，通過參數(shù)設(shè)置初始推薦序列長度，根據(jù)用戶偏好權(quán)重進行推薦，滿足了用戶的多樣性和興趣偏好。通過誤差門限參數(shù)可以提高推薦系統(tǒng)的用戶滿意度。實驗結(jié)果表明，該算法可以在保證準(zhǔn)確率和多樣性的同時，提高用戶滿意度。由于本文僅從項目的類別屬性建立用戶興趣模型，下一步工作將考慮用更多的項目屬性建立更準(zhǔn)確的用戶興趣模型。另外，對于誤差門限，將進一步研究根據(jù)不同用戶進行自適應(yīng)設(shè)置，以提高用戶的滿意度。