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

王 森

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

1 引言

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

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

2 相關(guān)研究

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

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

3.1 多樣性度量標準

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

假設(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）是基于用戶－評分矩陣計算的，大多數(shù)情況下該矩陣為稀疏矩陣［5］，矩陣中存在很多的空值，在計算商品相似性時，很多算法設(shè)置一些默認值來代替。這些默認值會對公式（1）中的計算準確率產(chǎn)生很大的影響。例如，將默認值設(shè)為0，那么利用余弦公式計算相似性時，相似性可能趨近于0，而相異性則趨近與1，而這個值和實際不符，主要原因是太多的0參與計算，這些默認值對最后的結(jié)果起主導(dǎo)作用。

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

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

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

3.2 推薦方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實驗

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

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

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

（1）隨機選擇數(shù)據(jù)集中2%的評分數(shù)據(jù)集T；

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

（3）在測試集中，如果評分值r（r∈T＊）是用戶u對商品i的評分，隨機選擇用戶u未評分的300個商品，并將商品i加入其中；

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

最后的查全率定義如下：

4.2 實驗結(jié)果

本文方法是在預(yù)測算法的基礎(chǔ)上進行的，我們選擇三種不同的預(yù)測算法進行比較，分別是基于項目的協(xié)同過濾算法（items－based）、基于用戶的協(xié)同過濾算法（user－based）以及SVD 算法。實驗觀察了隨著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值都是不斷增加的，而且相對于其它兩種方法，SVD 方法增加的幅度最大。因為利用SVD 方法得到的初始列表的多樣值小于0，也就是說在所有商品多樣性的平均值之下，所以隨著Threshold減小，它的增幅最大。另外，item－based和user－based方法得到的初始列表的多樣值大于0，也就是說在整個商品數(shù)據(jù)集的多樣性之上，所以它們的增幅較小。此外還能看出，隨著Threshold值的不斷減小，三種方法的Z－scores值最后趨于相等，因為此時我們的算法均使用到了相等數(shù)目的商品類，即從同樣的商品類中挑選商品作為推薦列表，最后的多樣性值近似相等。

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

此外，我們還與smyth B提出的BGS（Bounded Greedy Selection）算法進行了比較。BGS算法也是基于預(yù)測算法的，它首先根據(jù)預(yù)測值對商品進行排序，然后選擇評分預(yù)測值最大的前M個商品（M＞N），最后根據(jù)貪心算法從M個商品中選擇N個商品構(gòu)成推薦列表。實驗中N均取20，預(yù)測算法均選擇SVD 算法。當(dāng)M取不同的值時，我們觀察了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方法，而且由于本方法只用到了一些簡單的聚類算法和權(quán)重調(diào)整，時間復(fù)雜度更小，可擴展性更強。對于數(shù)據(jù)集中商品類別多、推薦列表較大的系統(tǒng)，本方法更加適用。

5 結(jié)束語

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

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

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

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

在以后的工作中，我們將進一步研究對于特定的用戶和數(shù)據(jù)集，如何設(shè)計優(yōu)化算法來自動求出最優(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.