一種基于多樣性的top－N 推薦算法＊

王 森

（重慶理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶400054）

1 引言

推薦系統(tǒng)（Recommendation System）作為信息過濾的一種重要應(yīng)用，已經(jīng)成為各主流網(wǎng)站不可缺少的個(gè)性化信息服務(wù)形式。它能夠幫助用戶從大量的互聯(lián)網(wǎng)商品中發(fā)現(xiàn)自己感興趣的商品（包括電影、書籍、餐廳、交通等）。目前的推薦算法很多，而基于預(yù)測(cè)評(píng)分值的推薦算法（簡(jiǎn)稱為預(yù)測(cè)算法）運(yùn)用最為廣泛。這類算法主要是利用用戶對(duì)已知商品的評(píng)分值、用戶的交易記錄、商品的內(nèi)容等信息預(yù)測(cè)出用戶對(duì)未知商品的評(píng)分值，進(jìn)而根據(jù)評(píng)分值大小對(duì)商品排序，選擇預(yù)測(cè)值最大的前N個(gè)商品構(gòu)成top－N推薦列表。因此，這類算法都致力于預(yù)測(cè)準(zhǔn)確率的提高。但是，在實(shí)際的推薦過程中，準(zhǔn)確率并不是增強(qiáng)用戶對(duì)推薦商品滿意度的唯一標(biāo)準(zhǔn)，推薦商品的多樣性也是一種重要指標(biāo)。比如電影推薦系統(tǒng)，可能它具有很好的評(píng)分預(yù)測(cè)功能，有很高的推薦準(zhǔn)確率，但是它可能經(jīng)常推薦同一種類型的影片給觀眾，仍然不能令用戶滿意。因此，一個(gè)好的推薦系統(tǒng)應(yīng)該同時(shí)兼顧推薦的準(zhǔn)確性和多樣性，避免向用戶推薦過于相似的商品。然而，準(zhǔn)確性和多樣性兩個(gè)標(biāo)準(zhǔn)是相互制約的，準(zhǔn)確性的增加必然會(huì)導(dǎo)致多樣性的降低，而多樣性的增加也會(huì)導(dǎo)致準(zhǔn)確性的下降，如何在這兩者之間找到平衡是一個(gè)亟待解決的問題。

本文提出了一種新的推薦方法，該方法是建立在預(yù)測(cè)推薦算法基礎(chǔ)上的，首先利用預(yù)測(cè)算法估計(jì)出用戶對(duì)未知商品的評(píng)分值，然后利用用戶－評(píng)分效用矩陣對(duì)所有商品進(jìn)行聚類，并為每個(gè)商品類別賦予相應(yīng)的權(quán)重，最后從不同的商品類中挑選商品進(jìn)入最終的推薦列表。挑選過程中同時(shí)考慮商品的預(yù)測(cè)評(píng)分值和商品所屬類別的權(quán)重，這樣能夠保證在一定準(zhǔn)確度損失的條件下，大大提高推薦列表的多樣性。

2 相關(guān)研究

越來越多研究者意識(shí)到準(zhǔn)確率已經(jīng)不是衡量一個(gè)推薦系統(tǒng)優(yōu)劣的唯一標(biāo)準(zhǔn)。McNee S M［1］首先提出了新穎性（Novelty）和新奇性（Serendipity）兩個(gè)指標(biāo)，旨在使用戶能夠發(fā)現(xiàn)一些尚未接觸的、感興趣的商品。這兩個(gè)指標(biāo)的實(shí)質(zhì)就是多樣性。Smith B［2］等真正將多樣性作為度量指標(biāo)引入到推薦系統(tǒng)中，并提出了一種貪心選擇算法（Greedy Selection），最大化推薦列表中的商品多樣性。該方法是建立在預(yù)測(cè)算法基礎(chǔ)上的。不同的是，在構(gòu)造推薦列表時(shí)，不僅要考慮商品的預(yù)測(cè)值，而且還要考慮該商品與當(dāng)前列表中其它商品的相異程度。這是一個(gè)組合優(yōu)化問題，作者采用貪心算法進(jìn)行求解。但是，當(dāng)推薦列表較大時(shí)，該方法每次選擇都要考慮商品兩兩之間的相異度，時(shí)間復(fù)雜度較高。Hurley N 等［3］也 從 優(yōu) 化 的 角 度 來 解 決 多 樣 性 問題，將其建模為一個(gè)二次規(guī)劃問題，使用一個(gè)控制因子參數(shù)來靈活控制多樣性和準(zhǔn)確度。該方法與Smith B提出的方法進(jìn)行了比較，能夠獲得相近的推薦列表，然而該方法的時(shí)間復(fù)雜度更高。Zhang M［4］利用聚類算法來推薦多樣性的問題，實(shí)驗(yàn)表明該方法時(shí)間復(fù)雜度較低，而且在保證多樣性的同時(shí)推薦準(zhǔn)確率沒有明顯降低。但是，該方法只是對(duì)用戶感興趣的商品進(jìn)行聚類，對(duì)用戶尚未接觸到的商品領(lǐng)域不予考慮，只是實(shí)現(xiàn)了用戶興趣范圍類的商品多樣化。本文提出的算法也是以聚類算法為基礎(chǔ)，在保證推薦準(zhǔn)確性的同時(shí)，在全局范圍內(nèi)實(shí)現(xiàn)商品的多樣性化。

3 基于多樣性的top－N 推薦算法

3.1 多樣性度量標(biāo)準(zhǔn)

在推薦系統(tǒng)中，商品多樣性的測(cè)量方法研究較少，Hurley N 等人提出計(jì)算列表中商品兩兩之間相異度的平均值，形式化定義如下：

假設(shè)I是商品的集合，U是用戶的集合，L（u）是用戶u（u∈U）的推薦列表，那么L（u）的多樣性D（L（u））為：其中，d（i，j）代表商品i和商品j的相異性：d（i，j）＝1－sim（i，j）（sim（i，j）表示商品i和商品j的相似性）。該方法從理論上是合理的，但是由于sim（i，j）是基于用戶－評(píng)分矩陣計(jì)算的，大多數(shù)情況下該矩陣為稀疏矩陣［5］，矩陣中存在很多的空值，在計(jì)算商品相似性時(shí)，很多算法設(shè)置一些默認(rèn)值來代替。這些默認(rèn)值會(huì)對(duì)公式（1）中的計(jì)算準(zhǔn)確率產(chǎn)生很大的影響。例如，將默認(rèn)值設(shè)為0，那么利用余弦公式計(jì)算相似性時(shí)，相似性可能趨近于0，而相異性則趨近與1，而這個(gè)值和實(shí)際不符，主要原因是太多的0參與計(jì)算，這些默認(rèn)值對(duì)最后的結(jié)果起主導(dǎo)作用。

因此，本文中，我們使用Z－Scores方法來計(jì)算多樣性。如公式（2）所示：

其中，I是商品的集合，D（I）和D（L（u））分別代表商品集合I的多樣性和用戶u的推薦列表L（u）中商品的多樣性。SD（I）為I中商品兩兩相異性值的標(biāo)準(zhǔn)差。

該計(jì)算方法與公式（1）不同，公式（1）是一種商品絕對(duì)多樣性的計(jì)算方法，而ZD（L（u））是一種相對(duì)多樣性的計(jì)算方法，它是列表L（u）相對(duì)于I的多樣性，由于引入了相異性值標(biāo)準(zhǔn)差，而不僅僅是如公式（1）中的平均值，使得多樣性的表示更加準(zhǔn)確。該方法同樣利用0作為空值的默認(rèn)值，相似性計(jì)算也采用于余弦相似性。

3.2 推薦方法

本方法是在預(yù)測(cè)算法的基礎(chǔ)上進(jìn)行的，不同的是，在top－N推薦列表的生成階段，除了考慮商品的預(yù)測(cè)值，還考慮了商品所屬的類別，對(duì)列表的多樣性進(jìn)行調(diào)整，具體步驟如下：

（1）使用聚類算法將商品劃分為N類（N為推薦列表的長度）。商品類C＝｛C1，C2，…，Cn｝，該步驟使用k－means算法實(shí)現(xiàn)（聚類數(shù)據(jù)直接使用用戶－評(píng)分矩陣），該算法可以在離線階段實(shí)現(xiàn)。

（2）對(duì)各商品類賦予相應(yīng)的初始權(quán)重。對(duì)于不同的用戶，各商品類的初始權(quán)重是不同的。我們將用戶－商品類別的權(quán)重關(guān)系用矩陣CW來表示，如表1所示，矩陣中的元素代表了各商品類的初始權(quán)重。

Table 1 Product category weight matrix表1 商品類別權(quán)重矩陣

這些初始權(quán)重是根據(jù)初始的推薦列表來計(jì)算的，具體方法為：假設(shè)用戶u的初始推薦列表為L（u）（這里L(fēng)（u）為預(yù)測(cè)值最大的前N個(gè)商品），每個(gè)用戶u的商品類初始權(quán)重由初始推薦列表L（u）來計(jì)算。如矩陣中的元素CWij表示在用戶ui的初始推薦列表L（ui）中，屬于類Cj的商品個(gè)數(shù)。當(dāng)CW13＝5時(shí)，表示在用戶u1的推薦列表中，有5個(gè)商品是屬于C3的。

（3）權(quán)重調(diào)整，這也是本方法的核心。按照初始的推薦列表來對(duì)各商品類的權(quán)重進(jìn)行分配，可能會(huì)導(dǎo)致某些類的權(quán)重很大，這些類中包含的商品可能非常滿足用戶的興趣，而另外某些類的權(quán)重非常小，這些類中包含的商品可能是用戶以前接觸很少的。為了提高推薦的多樣性，使用戶有機(jī)會(huì)接觸到小類中的商品，我們對(duì)初始的商品類權(quán)重進(jìn)行調(diào)整，算法如下：

算法1 權(quán)重調(diào)整

輸入：用戶u的初始推薦列表topNu，商品聚類結(jié)果C。

輸出：針對(duì)用戶u的商品類別權(quán)重CWu。

該算法涉及到兩個(gè)參數(shù)：（1）推薦列表的大小N。（2）商品類的數(shù)目K。對(duì)于特定用戶u，首先根據(jù)預(yù)測(cè)算法的推薦列表topNu來初始化每個(gè)商品類Ci的權(quán)重CWui。接著設(shè)定閾值Threshold來對(duì)各個(gè)類權(quán)重進(jìn)行調(diào)整。當(dāng)類Ci的權(quán)重大于Threshold時(shí)，找出當(dāng)前權(quán)重最小的類CWuc，將其權(quán)重加1，并將Ci的權(quán)值減1。這樣反復(fù)地調(diào)整，直到所有類的權(quán)重都小于Threshold為止。可以看出，如果Threshold值很大，而各個(gè)類的初始權(quán)重都小于Threshold，這樣就不需要調(diào)整，最后的推薦列表和預(yù)測(cè)算法產(chǎn)生的列表完全一致。相反，如果Threshold值很小，那么每一個(gè)類的權(quán)重都需要調(diào)整。最后，各個(gè)類的權(quán)重應(yīng)該是趨于均勻化。最后，在構(gòu)造推薦列表時(shí)，通過設(shè)定閾值Threshold來控制準(zhǔn)確性和多樣性的平衡。

當(dāng)各商品類的權(quán)重調(diào)整完成后，可以生成用戶u最終的推薦列表topNu＿New，在推薦的過程中，當(dāng)選出推薦商品ik時(shí)，將其所屬的商品類Ck的權(quán)重降低，以降低其同類商品被推薦的概率，來保證最后商品的多樣性。生成過程如下：

算法2 用戶u的推薦列表生成

輸入：用戶u的初始推薦列表topNu，商品初始權(quán)重矩陣CW（CWuk為用戶u對(duì)應(yīng)的商品類Ck的權(quán)重）；

輸出：用戶u最終的推薦列表topNu＿New。

在本文提出的推薦算法中，共分為兩個(gè)階段。第一階段為離線階段，主要用到k－means聚類算法，時(shí)間復(fù)雜度為O（INmn），其中，I為算法的迭代次數(shù)，N為聚類的類別數(shù)，m為商品數(shù)，n為用戶數(shù)。由于迭代次數(shù)有限，而且N＜＜m，該步驟的時(shí)間復(fù)雜度為O（mn）。第二階段為在線階段，主要涉及到文中的算法1和算法2。算法1 為權(quán)重調(diào)整階段，將權(quán)重較大的類別變小，權(quán)重較小的類別增大，其時(shí)間復(fù)雜度為O（N）。算法2通過掃描初始列表來生成新的推薦列表，最壞的情況下其時(shí)間復(fù)雜度為O（m）。因此，算法總的時(shí)間復(fù)雜度為O（mn）。該時(shí)間復(fù)雜度遠(yuǎn)小于其他算法，具有高度的可擴(kuò)展性。

4 實(shí)驗(yàn)

4.1 數(shù)據(jù)集和評(píng)估方法

我們采用MovieLens站點(diǎn)提供的數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，該站點(diǎn)提供了用戶對(duì)電影的評(píng)分（評(píng)分值為1～5五個(gè)等級(jí)），目前該站點(diǎn)的用戶超過50 000人，用戶評(píng)分的電影超過3 500部。我們選取實(shí)驗(yàn)數(shù)據(jù)集中包含6 000個(gè)用戶和3 900部電影以及100 000個(gè)評(píng)分?jǐn)?shù)據(jù)。

為了測(cè)量算法的準(zhǔn)確度，我們選擇Cremonesi P［6］提出的評(píng)估方法。該方法以信息檢索領(lǐng)域常用的查全率作為基礎(chǔ)，在此基礎(chǔ)上作了相應(yīng)的變化，具體如下：

（1）隨機(jī)選擇數(shù)據(jù)集中2%的評(píng)分?jǐn)?shù)據(jù)集T；

（2）在T中選擇評(píng)分值為5 的數(shù)據(jù)作為測(cè)試集T＊；

（3）在測(cè)試集中，如果評(píng)分值r（r∈T＊）是用戶u對(duì)商品i的評(píng)分，隨機(jī)選擇用戶u未評(píng)分的300個(gè)商品，并將商品i加入其中；

（4）對(duì)這301個(gè)商品利用預(yù)測(cè)算法進(jìn)行評(píng)分，并從中選擇分值最高的前300個(gè)商品作為top－300推薦列表，如果商品i在推薦列表中，將常量hits加1，否則hits的值不變。

最后的查全率定義如下：

4.2 實(shí)驗(yàn)結(jié)果

本文方法是在預(yù)測(cè)算法的基礎(chǔ)上進(jìn)行的，我們選擇三種不同的預(yù)測(cè)算法進(jìn)行比較，分別是基于項(xiàng)目的協(xié)同過濾算法（items－based）、基于用戶的協(xié)同過濾算法（user－based）以及SVD 算法。實(shí)驗(yàn)觀察了隨著Threshold值的變化，查全率（Recall）和多樣性（Z－scores）的變化情況，如圖1和圖2所示。

Figure 1 Change of Z－scores under different thresholds圖1 不同Threshold 下Z－scores的變化情況

Figure 2 Change of recall under different thresholds圖2 不同Threshold 下Recall的變化情況

從圖1可以看出，隨著Threshold減小，三種方法的Z－scores值都是不斷增加的，而且相對(duì)于其它兩種方法，SVD 方法增加的幅度最大。因?yàn)槔肧VD 方法得到的初始列表的多樣值小于0，也就是說在所有商品多樣性的平均值之下，所以隨著Threshold減小，它的增幅最大。另外，item－based和user－based方法得到的初始列表的多樣值大于0，也就是說在整個(gè)商品數(shù)據(jù)集的多樣性之上，所以它們的增幅較小。此外還能看出，隨著Threshold值的不斷減小，三種方法的Z－scores值最后趨于相等，因?yàn)榇藭r(shí)我們的算法均使用到了相等數(shù)目的商品類，即從同樣的商品類中挑選商品作為推薦列表，最后的多樣性值近似相等。

從圖2可以看出，隨著Threshold不斷減小，三種方法的Recall值也是不斷減小的，這也客觀說明 了Z－scores和Recall是 對(duì) 立 的。當(dāng)Threshold取10時(shí)，Recall下降很少，而Z－scores有一定程度的提高。因此，對(duì)于不同的推薦系統(tǒng)，只要合理地設(shè)置Threshold值，就達(dá)到平衡多樣性和準(zhǔn)確性的目的。

此外，我們還與smyth B提出的BGS（Bounded Greedy Selection）算法進(jìn)行了比較。BGS算法也是基于預(yù)測(cè)算法的，它首先根據(jù)預(yù)測(cè)值對(duì)商品進(jìn)行排序，然后選擇評(píng)分預(yù)測(cè)值最大的前M個(gè)商品（M＞N），最后根據(jù)貪心算法從M個(gè)商品中選擇N個(gè)商品構(gòu)成推薦列表。實(shí)驗(yàn)中N均取20，預(yù)測(cè)算法均選擇SVD 算法。當(dāng)M取不同的值時(shí)，我們觀察了BGS和本文算法在查全率和多樣性上的變化，如圖3所示。

Figure 3 Comparison of different methods’recall under the same Z－scores圖3 不同方法在相同Z－scores是下的Recall比較

從圖3 可以看出，隨著Z－scores值的不斷增加，各種方法的Recall都是下降的。在相同的多樣性下，本方法的查全率都優(yōu)于BGS方法，而且由于本方法只用到了一些簡(jiǎn)單的聚類算法和權(quán)重調(diào)整，時(shí)間復(fù)雜度更小，可擴(kuò)展性更強(qiáng)。對(duì)于數(shù)據(jù)集中商品類別多、推薦列表較大的系統(tǒng)，本方法更加適用。

5 結(jié)束語

本文提出了一種基于多樣性的推薦算法，來保證推薦列表中商品盡可能地多樣化，以滿足用戶廣泛的興趣。實(shí)驗(yàn)表明，該方法在增加商品多樣化的同時(shí)，查全率下降較少，使得多樣性和準(zhǔn)確性這兩個(gè)推薦時(shí)的對(duì)立屬性在一定程度上達(dá)到平衡。此外本方法還有如下優(yōu)點(diǎn)：

（1）用戶可以根據(jù)自身需要改變權(quán)重閾值大小，進(jìn)而改變參與排序的商品類的數(shù)目，以此來改變推薦列表的多樣性水平。

（2）本方法相當(dāng)于是在預(yù)測(cè)算法的基礎(chǔ)上進(jìn)行的二次調(diào)整，可以很好地與目前一些高效的預(yù)測(cè)算法進(jìn)行無縫對(duì)接。

（3）本方法的時(shí)間復(fù)雜度較小，離線階段使用基本的k－means算法，在線階段的核心步驟就是權(quán)重初始化和權(quán)重調(diào)整，只需少量的迭代計(jì)算即可完成，保證推薦系統(tǒng)具有很好的可擴(kuò)展性。

在以后的工作中，我們將進(jìn)一步研究對(duì)于特定的用戶和數(shù)據(jù)集，如何設(shè)計(jì)優(yōu)化算法來自動(dòng)求出最優(yōu)的閾值（Threshold），使算法更加智能高效。

［1］ McNee S M，Riedl J，Konstan J A.Being accurate is not enough：How accuray metrics have hurt recommender systems［C］∥Proc of Conference on Human Factors in Computing Systems，2006：1097－1101.

［2］ Smyth B，McClave P.Similarity vs diversity［C］∥Proc of the 4th International Conference on Case－based Reasoning，2001：347－361.

［3］ Hurley N，Zhang M.Novelty and diversity intop－Nrecommendation analysis and evaluation［J］.ACM Transactions on Internet Technology，2011，10（4）：Article 14，doi＝10.1145/1944339.1944341.

［4］ Zhang M，Hurley N.Avoid monotony：Improving the diversity of recommendation lists［C］∥Proc of the 2nd ACM Conference on Recommender System，2009：123－130.

［5］ Desrosiers C，Karypis G.A comprehensive survey of neighborhood－based recommendation methods［M］∥Recommendation Systems Handbook，New York：Springer，2011：107－144.

［6］ Cremonsi P，Koren Y.Performance of recommendation algorithms ontop－Nrecommendation tasks［C］∥Proc of the 4th ACM Conference on Recommender Systems，2010：39－46.