孫建凱，王帥強(qiáng)，馬 軍

(山東大學(xué) 計(jì)算機(jī)學(xué)院，山東 濟(jì)南 250101)

1 引言

隨著互聯(lián)網(wǎng)的發(fā)展和普及,網(wǎng)絡(luò)己成為人們獲取各種信息和數(shù)字化資源的重要途徑。然而,網(wǎng)絡(luò)上日益增多的資源在給用戶(hù)帶來(lái)更多選擇的同時(shí),也使用戶(hù)需要花費(fèi)更多的時(shí)間和精力來(lái)查詢(xún)自己想要的資源。于是,如何解決信息過(guò)載問(wèn)題，幫助用戶(hù)更快地找到所感興趣的資源己成為當(dāng)前研究的熱點(diǎn)。個(gè)性化推薦技術(shù)的提出為信息過(guò)載問(wèn)題提供了一個(gè)行之有效的解決方案。該技術(shù)旨在通過(guò)挖掘個(gè)體用戶(hù)的興趣喜好,把用戶(hù)最感興趣的資源從浩瀚如海的網(wǎng)絡(luò)信息中抽取出來(lái)推薦給相應(yīng)用戶(hù)。個(gè)性化推薦也逐漸成為了電子商務(wù)領(lǐng)域不可缺少的工具之一,比如Amazon、Netflix和豆瓣等許多網(wǎng)站都廣泛使用了個(gè)性化推薦技術(shù)。

協(xié)同過(guò)濾推薦系統(tǒng)是一種廣泛應(yīng)用的個(gè)性化推薦技術(shù)[1]。其最大的優(yōu)點(diǎn)就是只需要評(píng)分信息，而對(duì)待推薦的對(duì)象沒(méi)有特殊要求，因此能處理電影、音樂(lè)等難以進(jìn)行文本結(jié)構(gòu)化處理的對(duì)象[2]。它分為面向評(píng)分的和面向排序的兩種[3]。面向評(píng)分的系統(tǒng)根據(jù)用戶(hù)的歷史評(píng)分信息來(lái)計(jì)算用戶(hù)之間的相似度，利用相似度高的近鄰的評(píng)分來(lái)預(yù)測(cè)目標(biāo)用戶(hù)對(duì)待推薦產(chǎn)品的評(píng)分。然而，當(dāng)用戶(hù)之間的評(píng)分差別較大時(shí)，基于評(píng)分的相似度度量方式便喪失了捕獲用戶(hù)之間偏好的相似性的能力?？捎衫?來(lái)說(shuō)明：

例1.用戶(hù)u和v對(duì)電影《畫(huà)皮》和《盜夢(mèng)空間》的實(shí)際評(píng)分分別是<1,2>和<4,5>。由基于評(píng)分的相似度度量方式，比如夾角余弦的方法來(lái)計(jì)算用戶(hù)之間的相似性，兩用戶(hù)的相似度很小。但考慮到用戶(hù)的偏好，兩人卻是一致的，都是相比于《畫(huà)皮》更喜歡《盜夢(mèng)空間》。

而且當(dāng)前的面向評(píng)分的協(xié)同過(guò)濾系統(tǒng)只是對(duì)單獨(dú)的產(chǎn)品(即例1中的電影)獨(dú)立地預(yù)測(cè)評(píng)分，而沒(méi)有考慮用戶(hù)對(duì)產(chǎn)品的偏好關(guān)系。與之不同，面向排序的協(xié)同過(guò)濾系統(tǒng)則是根據(jù)用戶(hù)對(duì)產(chǎn)品的排序來(lái)計(jì)算用戶(hù)之間的相似度，進(jìn)而產(chǎn)生滿(mǎn)足目標(biāo)用戶(hù)偏好的推薦列表。

然而當(dāng)前面向排序的協(xié)同過(guò)濾算法只是考慮用戶(hù)對(duì)產(chǎn)品對(duì)的偏好是否一致，而忽略了偏好的程度。即使不同用戶(hù)對(duì)同一產(chǎn)品對(duì)的偏好相同，但用戶(hù)之間偏好的程度卻有可能千差萬(wàn)別。可由例2說(shuō)明。

例2. 用戶(hù)u和v對(duì)電影《畫(huà)皮》和《盜夢(mèng)空間》的實(shí)際評(píng)分分別是<1,5>和<4,5>，由評(píng)分可知，兩位用戶(hù)的偏好都是相比《畫(huà)皮》更喜歡《盜夢(mèng)空間》。從偏好程度上來(lái)說(shuō)則是用戶(hù)u不喜歡《畫(huà)皮》(評(píng)分不大于3分)卻非常喜歡《盜夢(mèng)空間》，而用戶(hù)v雖對(duì)兩部電影都喜歡，但相比還是更喜歡《盜夢(mèng)空間》多一些。因此用戶(hù)u與v相比，相對(duì)于《畫(huà)皮》而言偏好《盜夢(mèng)空間》的程度更深。過(guò)去的很多算法卻只會(huì)將u和v的這一偏好一致對(duì)待，而忽略了兩者的偏好程度不同這一重要信息。

當(dāng)前面向排序的協(xié)同過(guò)濾算法不僅沒(méi)有考慮用戶(hù)對(duì)產(chǎn)品對(duì)的偏好程度，而且還忽略了偏好的流行度在區(qū)分用戶(hù)時(shí)所發(fā)揮的作用。例3說(shuō)明如下。

例3. 假設(shè)所有的用戶(hù)相對(duì)于《畫(huà)皮》都更喜歡《盜夢(mèng)空間》，也就是說(shuō)該偏好在用戶(hù)間非常流行。這種流行的偏好就像一種常識(shí)性信息，即大家都知道任何人相對(duì)于《畫(huà)皮》都會(huì)更喜歡《盜夢(mèng)空間》，因此也就喪失了區(qū)分用戶(hù)的能力。也就是說(shuō)偏好在用戶(hù)間越普遍，其區(qū)分用戶(hù)的能力就會(huì)越弱。

為解決上述問(wèn)題，本文提出了一種面向排序的協(xié)同過(guò)濾算法，能夠結(jié)合用戶(hù)對(duì)產(chǎn)品對(duì)的偏好程度以及偏好的流行程度，從而產(chǎn)生具有較好用戶(hù)體驗(yàn)的推薦結(jié)果。算法主要流程如下： 首先提取出用戶(hù)對(duì)每個(gè)產(chǎn)品對(duì)的偏好，利用類(lèi)似TF-IDF的策略對(duì)用戶(hù)的偏好程度以及偏好的流行度進(jìn)行加權(quán)；然后利用加權(quán)的Kendall Tau相關(guān)系數(shù)計(jì)算用戶(hù)間的相似度，這也是本文算法被稱(chēng)為Weighted-Tau Rank的原因；接著利用與目標(biāo)用戶(hù)相似度高的近鄰預(yù)測(cè)目標(biāo)用戶(hù)對(duì)特定產(chǎn)品對(duì)的偏好；最后利用舒爾茨方法進(jìn)行偏好融合和排序以產(chǎn)生最終的推薦列表。

本文結(jié)構(gòu)組織如下： 第2節(jié)回顧相關(guān)研究工作；第3節(jié)詳細(xì)論述本文采用的Degree-Popularity加權(quán)方式以及訓(xùn)練和預(yù)測(cè)模型；相關(guān)實(shí)驗(yàn)和分析在第4節(jié)給出；最后總結(jié)全文。

2 相關(guān)工作

協(xié)同過(guò)濾是現(xiàn)在電子商務(wù)推薦系統(tǒng)中很常用的技術(shù)。它能夠充分利用用戶(hù)的歷史評(píng)分信息。這些評(píng)分信息可以是顯式(explicit)值也可以是隱式(implicit)值。比如說(shuō)在豆瓣網(wǎng)上用戶(hù)可以用1～10的數(shù)值來(lái)表示對(duì)某電影的喜好程度，這些評(píng)分信息就是顯式值。而在淘寶上用戶(hù)的瀏覽、點(diǎn)擊、評(píng)論、收藏和購(gòu)買(mǎi)的行為則是隱式值。相比顯式值，隱式值因包含較多的噪音而難以收集和處理。

在討論與協(xié)同過(guò)濾算法的具體細(xì)節(jié)之前，我們先引進(jìn)一些與之相關(guān)的概念以及符號(hào)表示。設(shè)U={u1,u2,...,um}為有m個(gè)用戶(hù)的集合，I={i1,i2,...,in}為有n個(gè)產(chǎn)品的集合。用戶(hù)對(duì)產(chǎn)品的評(píng)分信息可以用一個(gè)m×n的矩陣R來(lái)表示，R中的元素ru,i表示用戶(hù)u對(duì)產(chǎn)品的評(píng)分。ru,i=0表示u未對(duì)i評(píng)分。另外Ui表示所有對(duì)產(chǎn)品i評(píng)過(guò)分的用戶(hù)的集合，Iu則表示用戶(hù)u所有評(píng)過(guò)分的產(chǎn)品的集合。

面向評(píng)分的協(xié)同過(guò)濾系統(tǒng)的算法可以分為兩類(lèi)： 基于記憶(memory-based)的和基于模型(model-based)的算法[4]。基于記憶的算法是根據(jù)歷史評(píng)分信息進(jìn)行預(yù)測(cè)。其中一個(gè)最常用的技術(shù)就是基于近鄰(neighbor-based)的方法[5]，其工作流程主要分為鄰居發(fā)現(xiàn)和評(píng)分預(yù)測(cè)兩步[6]。基于模型的算法收集評(píng)分?jǐn)?shù)據(jù)進(jìn)行學(xué)習(xí)并推斷用戶(hù)行為模型，進(jìn)而對(duì)某個(gè)產(chǎn)品預(yù)測(cè)評(píng)分。

面向排序的協(xié)同過(guò)濾算法不再關(guān)注預(yù)測(cè)評(píng)分的精度，而是根據(jù)用戶(hù)的偏好向目標(biāo)用戶(hù)產(chǎn)生一個(gè)推薦列表。面向排序的協(xié)同過(guò)濾系統(tǒng)一般分為兩個(gè)步驟： 鄰居發(fā)現(xiàn)和預(yù)測(cè)排序。鄰居發(fā)現(xiàn)即系統(tǒng)要找出與目標(biāo)用戶(hù)相似度高的用戶(hù)作為其近鄰。預(yù)測(cè)排序在此基礎(chǔ)上系統(tǒng)根據(jù)近鄰對(duì)特定產(chǎn)品對(duì)的偏好來(lái)預(yù)測(cè)目標(biāo)用戶(hù)的偏好，然后對(duì)預(yù)測(cè)的偏好進(jìn)行融合和排序以產(chǎn)生一個(gè)盡可能滿(mǎn)足目標(biāo)用戶(hù)偏好的推薦列表。具體細(xì)節(jié)將在第3節(jié)詳細(xì)討論。

一系列面向排序的協(xié)同過(guò)濾算法的提出豐富了該領(lǐng)域的研究。比如，CoFiRank[7]采用最大化邊界的矩陣分解技術(shù)直接優(yōu)化推薦列表，以產(chǎn)生一個(gè)結(jié)構(gòu)化的預(yù)測(cè)輸出。而ListRank-MF[8]則將矩陣分解產(chǎn)生的潛在特征用于學(xué)習(xí)排序算法的訓(xùn)練，從而產(chǎn)生推薦列表。文獻(xiàn)[3]提出的EigenRank算法則根據(jù)用戶(hù)對(duì)產(chǎn)品對(duì)的偏好利用標(biāo)準(zhǔn)的Kendall Tau Rank相關(guān)系數(shù)計(jì)算用戶(hù)之間偏好的相似性，然后再根據(jù)鄰居對(duì)特定產(chǎn)品對(duì)的偏好預(yù)測(cè)目標(biāo)用戶(hù)的偏好。通過(guò)標(biāo)準(zhǔn)的Kendall Tau Rank相關(guān)系數(shù)[9]來(lái)計(jì)算用戶(hù)之間排序的相似度T的公式見(jiàn)式(1)。

其中，Nc是用戶(hù)u和v中排序相同的產(chǎn)品對(duì)數(shù)，Nd則是排序不同的產(chǎn)品對(duì)數(shù)，N=|Iu∩Iv|。

為判斷用戶(hù)之間對(duì)同一個(gè)產(chǎn)品對(duì)的偏好是否相同，我們需要引入一個(gè)指示函數(shù)sgn，對(duì)每一個(gè)產(chǎn)品對(duì)，sgnu,v(k,l)滿(mǎn)足如下定義：

用戶(hù)u和v對(duì)產(chǎn)品ik、il排序一致時(shí)，sgnu,v(k,l)=1；不一致時(shí)sgnu,v(k,l)=-1。根據(jù)式(2)我們得到式(3)。

因此式(1)中Tu,v的計(jì)算也可以用式(4)表示：

Tu,v的取值范圍為[-1,1]，值越大表示用戶(hù)之間的相似度越高。具體的計(jì)算可由例4來(lái)說(shuō)明。

例4. 假設(shè)我們有產(chǎn)品集合{i1,i2,i3},從產(chǎn)品集合中抽取產(chǎn)品對(duì)的集合為{,,}。用戶(hù)u對(duì)這三個(gè)產(chǎn)品的評(píng)分為3、4和2，用戶(hù)的評(píng)分則是2、4和3。則用戶(hù)u從產(chǎn)品對(duì)的偏好集合為{i1i2,i1?i3,i2?i3}，用戶(hù)v對(duì)產(chǎn)品對(duì)的偏好集合則為{i1i2,i1?i3,i2?i3}?？芍狽c=2，Nd=1。兩用戶(hù)u、v之間的相似度

然而，EigenRank只是考慮了用戶(hù)間產(chǎn)品偏好的一致性，而沒(méi)有考慮用戶(hù)對(duì)不同產(chǎn)品對(duì)的偏好程度以及偏好在用戶(hù)間的流行度。我們?cè)谥暗墓ぷ鱗10]中對(duì)表示為詞項(xiàng)的用戶(hù)偏好進(jìn)行了類(lèi)似TF-IDF的加權(quán)，然后采用向量空間模型進(jìn)行用戶(hù)間相似度的計(jì)算,但偏好融合與預(yù)測(cè)部分采用的算法和EigenRank一樣均為貪婪算法，效率不高。

3 Weighted-Tau Rank算法

本節(jié)將詳細(xì)介紹本文提出的Weighted-Tau Rank算法，算法流程如下：

1) 從歷史信息中抽取用戶(hù)對(duì)產(chǎn)品對(duì)的偏好，即3.1節(jié)的偏好表示部分；

2) 然后利用3.2節(jié)的偏好權(quán)重度量偏好的程度以及流行度以便對(duì)該偏好加權(quán)；

3) 3.3節(jié)利用加權(quán)的Kendall Tau Rank相關(guān)系數(shù)計(jì)算用戶(hù)間的相似度；

4) 3.4.1節(jié)選出與目標(biāo)用戶(hù)相似度高的用戶(hù)作為近鄰來(lái)預(yù)測(cè)目標(biāo)用戶(hù)對(duì)特定產(chǎn)品對(duì)的偏好；

5) 最后3.4.2節(jié)利用基于投票的舒爾茨方法進(jìn)行偏好融合和排序以產(chǎn)生最終的推薦列表。

3.1 偏好表示

我們從用戶(hù)u以及其評(píng)過(guò)分的產(chǎn)品集合Iu中抽取該用戶(hù)的偏好集合為{ikil|ik,il∈I∧k

ikil表示用戶(hù)對(duì)產(chǎn)品對(duì)ik和ik的偏好。ik?il則表示相比產(chǎn)品il，用戶(hù)u更喜歡ik；ikil則相反。

3.2 偏好權(quán)重

偏好權(quán)重的定義由兩部分組成： 用戶(hù)對(duì)產(chǎn)品對(duì)的偏好程度Degree和偏好在用戶(hù)間的流行度Popularity。正如Term Frequency(TF)可用來(lái)描述文檔的內(nèi)容，Degree可以用來(lái)描述用戶(hù)的愛(ài)好；正如Inverse Document Frequency (IDF)可用來(lái)區(qū)分該詞項(xiàng)所在文檔與其他文檔，Popularity可以用來(lái)區(qū)分不同的用戶(hù)。

3.2.1 Degree

偏好ikil的Degree值表示用戶(hù)對(duì)產(chǎn)品對(duì)的偏好程度。根據(jù)用戶(hù)對(duì)產(chǎn)品對(duì)的評(píng)分，我們可以得到該用戶(hù)的偏好程度的信息。在本文中，我們采用類(lèi)似TF的定義，如式(6)所示。

3.2.2 Popularity

Popularity可衡量偏好在用戶(hù)集合中的流行程度。對(duì)偏好ikil，我們有兩個(gè)實(shí)體：ikil和ik?il，因此我們并不能直接使用類(lèi)似IDF的公式log來(lái)計(jì)算Popularity值，其中|U|為用戶(hù)的數(shù)量，Nikil為偏好ikil出現(xiàn)的次數(shù)。

對(duì)于用戶(hù)的一個(gè)特定偏好ik?il，該偏好的流行度，是相對(duì)于偏好ikil出現(xiàn)的次數(shù)而言的。因此我們應(yīng)該把|U|修改為Nik?il+Nikil。得到Popularity的一種可能的計(jì)算公式如式(7)。

但是式(7)的定義會(huì)出現(xiàn)例 5中描述的問(wèn)題。

例5.有產(chǎn)品{i1,i2,i3,i4}，用戶(hù)總數(shù)為10 000。有1 000名用戶(hù)給i1,i2打過(guò)分，其中800名用戶(hù)相對(duì)于i2更喜歡i1，其他200名用戶(hù)偏好則相反，即Ni1?i2=800，Ni1i2=200。對(duì)i3、i4，則有100名用戶(hù)對(duì)它們?cè)u(píng)過(guò)分，其中Ni3?i4=80，Ni3i4=20。

根據(jù)公式(7)有：λi1?i2=λi3?i4，λi1i2=λi3i4。雖然i1和i2、i3和i4的評(píng)分用戶(hù)數(shù)有顯著差異，但最后的比值卻是相同的，公式(7)存在小樣本問(wèn)題。樣本數(shù)越小，Nik?il+Nikil越小，公式(7)得到的結(jié)果可信度就不高，不確定性就越大，因而結(jié)果需要較大地調(diào)整。相反，Nik?il+Nikil越大，公式(7)得到的結(jié)果可信度就越高，就需要較小甚至不需要調(diào)整。為此，我們引入可信因子α，定義見(jiàn)式(8)。

最后綜合考慮λikil和αik,il，偏好ikil的Popularity值的定義如式(9)。

其中，αu,ik,il值越小，可信度越低，λu,ikil調(diào)整的幅度就越大；相反αu,ik,il越大，與λu,ikil的差別就越小。

3.2.3 Degree-Popularity

和TF-IDF的加權(quán)方式類(lèi)似，Degree-Popularity的值為Degree和Popularity兩者的乘積。對(duì)用戶(hù)u，偏好ikil的Degree-Popularity權(quán)重定義如式(10)。

3.3 相似度計(jì)算

在面向排序的協(xié)同過(guò)濾算法中，可以通過(guò)式(4)中的標(biāo)準(zhǔn)Kendall Tau Rank相關(guān)系數(shù)[3]來(lái)計(jì)算用戶(hù)之間排序的相似度T。但從式(4)可以看出，Tu,v用戶(hù)相似度的計(jì)算過(guò)程中，只是考慮了用戶(hù)之間的偏好是否一致，而沒(méi)有考慮偏好的程度以及偏好的流行度。為了能夠綜合考量用戶(hù)偏好的一致性、用戶(hù)偏好程度以及偏好的流行度，本文對(duì)式(4)進(jìn)行改進(jìn)采用加權(quán)的Kendall Tau Rank相關(guān)系數(shù)來(lái)計(jì)算兩用戶(hù)偏好之間的相似性，如式(11)所示。

其中,wk,l為用戶(hù)u和v對(duì)偏好ikil權(quán)重的乘積，即式(12)。

3.4 排序預(yù)測(cè)

在3.2和3.3節(jié)中我們利用Degree-Popularity加權(quán)用戶(hù)偏好，通過(guò)加權(quán)Kendall Tau Rank相關(guān)系數(shù)來(lái)計(jì)算用戶(hù)之間的相似度。在這節(jié)我們討論如何進(jìn)行排序預(yù)測(cè)。排序預(yù)測(cè)主要分為兩步： 偏好預(yù)測(cè)與偏好融合。

3.4.1 偏好預(yù)測(cè)

首先我們定義一個(gè)偏好函數(shù)Ψ。Ψ(i,j)>0表示相對(duì)于產(chǎn)品j用戶(hù)更喜歡i。|Ψ(i,j)|大小表示用戶(hù)對(duì)這兩個(gè)產(chǎn)品的偏好程度。Ψ(i,j)=0表示用戶(hù)對(duì)i和j沒(méi)有偏好。Ψ有反對(duì)稱(chēng)的性質(zhì)，即Ψ(i,j)=-Ψ(j,i)，但不保證具有傳遞性，即由Ψ(i,j)>0和Ψ(j,k)>0，并不能得到Ψ(i,k)>0。

接下來(lái)我們要借助近鄰預(yù)測(cè)用戶(hù)對(duì)未知產(chǎn)品對(duì)的偏好關(guān)系。我們將與目標(biāo)用戶(hù)u有相似偏好的用戶(hù)記為u的鄰居Nu。Nu中越多的用戶(hù)對(duì)《盜夢(mèng)空間》的評(píng)分高于《畫(huà)皮》，我們就越有理由相信u相對(duì)于畫(huà)皮更喜歡《盜夢(mèng)空間》。具體定義見(jiàn)式(13)。

得到目標(biāo)用戶(hù)對(duì)未知產(chǎn)品對(duì)的偏好關(guān)系的預(yù)測(cè)結(jié)果后，我們要生成一個(gè)排序列表使其盡可能地滿(mǎn)足Ψ的結(jié)果。然而由于Ψ不具有傳遞性，排序預(yù)測(cè)為NP完全問(wèn)題[9]。文獻(xiàn)[3]和文獻(xiàn)[10]通過(guò)構(gòu)建價(jià)值函數(shù)，利用貪婪算法最大化價(jià)值函數(shù)，得到近似最優(yōu)解的排序列表。但這種方法需要構(gòu)建價(jià)值函數(shù)的中間步驟，算法效率低。本文則不用構(gòu)建價(jià)值函數(shù)，直接利用基于投票的舒爾茨方法來(lái)解決偏好融合與排序問(wèn)題，能夠大大提高效率。

3.4.2 偏好融合

偏好融合是指根據(jù)Ψ對(duì)目標(biāo)用戶(hù)產(chǎn)生的偏好關(guān)系進(jìn)行排序產(chǎn)生推薦列表的過(guò)程。本文利用舒爾茨方法來(lái)實(shí)現(xiàn)偏好融合以產(chǎn)生推薦列表。舒爾茨方法是Markus Schulze提出的投票算法。該方法能夠利用用戶(hù)有偏好的投票產(chǎn)生勝者列表。本文將Ψu(i,j)表示為用戶(hù)u對(duì)產(chǎn)品對(duì)的投票，Ψu(i,j)>0表示用戶(hù)將票投給i?j，相反Ψu(i,j)<0則表示用戶(hù)將票投給ij。|Ψu(i,j)|則為投票的權(quán)重。

算法1： 舒爾茨算法

# Input: d[i,j]，d[i,j]=Ψu(i,j).

# Output: p[i,j], the strength of the strongest path from item i to item j.

for i from 1 to C

for j from 1 to C

if (i ≠ j) then

if (d[i,j] > d[j,i]) then

p[i,j] := d[i,j]

else

p[i,j] := 0

for i from 1 to C

for j from 1 to C

if (i ≠ j) then

for k from 1 to C

if (i ≠ k and j ≠ k) then

p[j,k] := max (p[j,k],

min (p[j,i], p[i,k]))

end

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)設(shè)置

為驗(yàn)證本文所提算法的有效性，我們采用了兩個(gè)具有真實(shí)評(píng)分的電影數(shù)據(jù)集： EachMovie和MovieLens。EachMovie中有74 418名用戶(hù)，1 648部電影，約有281萬(wàn)條評(píng)分；MovieLens則有6 040名用戶(hù)，3 883部電影，100萬(wàn)條左右的評(píng)分。

在實(shí)驗(yàn)過(guò)程中，為了保證目標(biāo)用戶(hù)和其鄰居的共同評(píng)分的電影具有一定的數(shù)量，我們首先對(duì)數(shù)據(jù)集做了過(guò)濾操作： EachMovie中剔除了評(píng)分?jǐn)?shù)小于100的用戶(hù)，MovieLens中剔除了評(píng)分?jǐn)?shù)小于50的用戶(hù)。然后隨機(jī)選取用戶(hù)評(píng)分的80%用做訓(xùn)練，10%用于校驗(yàn)，其余的10%用于測(cè)試。

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

對(duì)于面向評(píng)分的協(xié)同過(guò)濾系統(tǒng)，評(píng)價(jià)指標(biāo)主要用于衡量系統(tǒng)預(yù)測(cè)評(píng)分的精度。比如精確度衡量的兩個(gè)典型的指標(biāo)平均絕對(duì)誤差(Mean Absolute Error, MAE)和平均平方誤差(Mean Squared Error, MSE)就用來(lái)衡量用戶(hù)實(shí)際評(píng)分和預(yù)測(cè)評(píng)分之間的差異[11]。然而本文的算法是面向提高推薦列表排序的精度而不是預(yù)測(cè)評(píng)分的精度。因此本文采用的評(píng)價(jià)指標(biāo)為Normalized Discounted Cumulative Gain(NDCG)[12]。對(duì)于給定的用戶(hù)u，NDCG在第n位的值的定義如式(14)所示。

其中,Zu為歸一化因子,ru,i為用戶(hù)u對(duì)處于推薦列表第i位的電影的評(píng)分。最后對(duì)所有用戶(hù)的NDCG值求平均：

NDCG值的取值范圍為[0,1]，值越大，推薦效果就越好。對(duì)推薦的結(jié)果，大部分用戶(hù)只會(huì)查看排在推薦列表前面的產(chǎn)品，因此排名相對(duì)靠前的產(chǎn)品對(duì)用戶(hù)的價(jià)值相對(duì)較大，這就要求評(píng)價(jià)指標(biāo)能夠給予排名靠前的產(chǎn)品更多的關(guān)注。NDCG的分母log(1+i)隨著排序位置的增加而增大，使得NDCG對(duì)排名靠前的產(chǎn)品比較敏感。

4.3 實(shí)驗(yàn)結(jié)果分析

我們使用現(xiàn)在兩種比較流行的面向排序協(xié)同過(guò)濾算法: EigenRank[3]和CoFiRank[7]作為本文的主要對(duì)比方法。EigenRank使用標(biāo)準(zhǔn)Kendall相關(guān)系數(shù)來(lái)度量用戶(hù)之間的相似性，通過(guò)鄰居來(lái)預(yù)測(cè)用戶(hù)對(duì)特定產(chǎn)品對(duì)的偏好，然后利用貪婪算法解決偏好融合問(wèn)題，最后向用戶(hù)產(chǎn)生一個(gè)有序的推薦列表。CoFiRank則利用最大化邊界的矩陣分解技術(shù)，直接優(yōu)化推薦列表，產(chǎn)生一個(gè)結(jié)構(gòu)化的輸出。同時(shí)，我們還使用了一種傳統(tǒng)的面向用戶(hù)的協(xié)同過(guò)濾算法，稱(chēng)之為UVS。UVS采用夾角余弦作為相似度的度量方式，采用利用近鄰預(yù)測(cè)評(píng)分,最后根據(jù)產(chǎn)品的預(yù)測(cè)評(píng)分對(duì)用戶(hù)的推薦列表排序。

圖1和圖2展示了在NDCG評(píng)測(cè)指標(biāo)下，本文提出的算法Weighted-Tau Rank以及其他對(duì)比方法在MovieLens和EachMovie數(shù)據(jù)集上的表現(xiàn)。從中我們可以看出：

圖1 MovieLens結(jié)果對(duì)比

圖2 EachMovie結(jié)果對(duì)比

(1) Weighted-Tau Rank在兩個(gè)數(shù)據(jù)集上結(jié)果的精確度要高于其他所有的對(duì)比方法。比如說(shuō)，在MovieLens上，Weighted-Tau Rank的NDCG@1-2的結(jié)果為0.733和0.743，和EigenRank的0.690 8和0.713 8相比提高了6.1%和4.1%。在EachMovie上，Weighted-Tau Rank的NDCG@1-2的結(jié)果為0.733 9和0.744 7，和CoFiRank的0.681 3和0.699 6相比提高了7.7%和6.55%。這是因?yàn)镋igenRank、CoFirank只是考慮用戶(hù)對(duì)項(xiàng)目對(duì)偏好的存在情況，而沒(méi)有考慮偏好的程度以及流行度，Weighted-Tau Rank則由于綜合考慮了用戶(hù)偏好的各方面信息，使得推薦效果更加精確。

(2) 在NDCG評(píng)測(cè)指標(biāo)下，面向排序的協(xié)同過(guò)濾算法的效果要優(yōu)于面向評(píng)分的協(xié)同過(guò)濾算法。這是因?yàn)閁VS算法只關(guān)注預(yù)測(cè)評(píng)分的精度，但預(yù)測(cè)評(píng)分的精度和排序的效果兩者之間并沒(méi)有必然的聯(lián)系，這從本文的實(shí)驗(yàn)結(jié)果中就可以看出。比如，在MovieLens上，本文提出的算法Weighted-Tau Rank的NDCG@1-2的結(jié)果相比UVS分別提高了9%和8%，而在EachMovie上，則分別提高了13.4%和12.7%。

(3) 在MovieLens上，EigenRank除NDCG@1之外，其他結(jié)果均優(yōu)于CoFiRank。在EachMovie上，EigenRank的NDCG@1-2的值優(yōu)于CoFiRank。Weighted-Tau Rank在所有數(shù)據(jù)集上表現(xiàn)是最好的，而UVS則是最差的。因此這四個(gè)推薦算法在MovieLens和EachMovie上的優(yōu)劣關(guān)系為： Weighted-Tau Rank>EigenRank>CoFiRank>UVS。

5 結(jié)語(yǔ)

在本文中，我們提出了一種使用加權(quán)Kendall Tau Rank相關(guān)系數(shù)的面向排序的協(xié)同過(guò)濾算法Weighted-Tau Rank。本文的主要貢獻(xiàn)有： 與其他的面向排序的協(xié)同過(guò)濾算法一致對(duì)待用戶(hù)對(duì)不同產(chǎn)品對(duì)的偏好不同，Weighted-Tau Rank使用類(lèi)似TF-IDF的Degree-Popularity加權(quán)策略對(duì)用戶(hù)的偏好加權(quán)；與其他的面向排序的協(xié)同過(guò)濾算法需要構(gòu)建價(jià)值函數(shù)利用貪婪算法進(jìn)行偏好融合和排序不同，Weighted-Tau Rank直接利用基于投票的舒爾茨方法直接進(jìn)行偏好融合和排序。在兩個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果也證明了Weighted-Tau Rank的有效性。我們未來(lái)擬開(kāi)展的研究包括： (1)研究不同的加權(quán)方式對(duì)推薦效果的影響；(2)研究不同的相似度度量方式對(duì)推薦效果的影響；(3)優(yōu)化算法，提高算法效率；(4)將推薦結(jié)果的多樣性等因素考慮到算法當(dāng)中去。

[1] Su X, Khoshgoftaar TM. A survey of collaborative filtering techniques[J]. Adv. in Artif. Intell. 2009,2009:2-2.

[2] Hu Y, Koren Y, Volinsky C. Collaborative Filtering for Implicit Feedback Datasets[C]//Proceedings of the 2008 Eighth IEEE International Conference on Data Mining: IEEE Computer Society; 2008: 263-272.

[3] Liu NN, Yang Q. EigenRank: a ranking-oriented approach to collaborative filtering[C]//Proceedings of the 31st annual international ACM SIGIR conference on research and development in information retrieval. Singapore, Singapore: ACM; 2008: 83-90.

[4] Sarwar B, Karypis G, Konstan J, Riedl J. Item-based collaborative filtering recommendation algorithms[C]//Proceedings of the 10th international conference on World Wide Web. Hong Kong, Hong Kong: ACM; 2001: 285-295.

[5] 劉建國(guó), 周濤, 汪秉宏. 個(gè)性化推薦系統(tǒng)的研究進(jìn)展[J]. 自然科學(xué)進(jìn)展,2008,19:15.

[6] Adomavicius G, Tuzhilin A. Toward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions[J]. Knowledge and Data Engineering, IEEE Transactions, 2005,17:734-749.

[7] Weimer, Markus, Karatzoglou, et al. COFIRANK—Maximum Margin Matrix Factorization for Collaborative Ranking[C]//Proceedings of NIPS; 2007.

[8] Shi Y, Larson M, Hanjalic A. List-wise learning to rank with matrix factorization for collaborative filtering[C]//Proceedings of the fourth ACM conference on recommender systems. Barcelona, Spain: ACM; 2010: 269-272.

[9] Cohen W W, Schapire R E, Singer Y. Learning to order things[J]. Artif. Int. Res. 1999,10:243-270.

[10] Wang S, Sun J, Gao B J, et al. Adapting Vector Space Model to Ranking-based Collaborative Filtering[C]//Proceedings of CIKM; 2012.

[11] Gunawardana A, Shani G. A Survey of Accuracy Evaluation Metrics of Recommendation Tasks[J]. Mach. Learn. Res. 2009,10:2935-2962.

[12] Valizadegan H J R, Zhang R, Mao J. Learning to Rank by Optimizing NDCG Measure[C]//Proceedings of the Conference on Neural Information Processing Systems (NIPS); 2009.