Weighted-Tau Rank: 一種采用加權Kendall Tau的面向排序的協(xié)同過濾算法

孫建凱，王帥強，馬 軍

(山東大學 計算機學院，山東 濟南 250101)

1 引言

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

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

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

而且當前的面向評分的協(xié)同過濾系統(tǒng)只是對單獨的產品(即例1中的電影)獨立地預測評分，而沒有考慮用戶對產品的偏好關系。與之不同，面向排序的協(xié)同過濾系統(tǒng)則是根據(jù)用戶對產品的排序來計算用戶之間的相似度，進而產生滿足目標用戶偏好的推薦列表。

然而當前面向排序的協(xié)同過濾算法只是考慮用戶對產品對的偏好是否一致，而忽略了偏好的程度。即使不同用戶對同一產品對的偏好相同，但用戶之間偏好的程度卻有可能千差萬別?？捎衫?說明。

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

當前面向排序的協(xié)同過濾算法不僅沒有考慮用戶對產品對的偏好程度，而且還忽略了偏好的流行度在區(qū)分用戶時所發(fā)揮的作用。例3說明如下。

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

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

本文結構組織如下： 第2節(jié)回顧相關研究工作；第3節(jié)詳細論述本文采用的Degree-Popularity加權方式以及訓練和預測模型；相關實驗和分析在第4節(jié)給出；最后總結全文。

2 相關工作

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

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

面向評分的協(xié)同過濾系統(tǒng)的算法可以分為兩類： 基于記憶(memory-based)的和基于模型(model-based)的算法[4]?；谟洃浀乃惴ㄊ歉鶕?jù)歷史評分信息進行預測。其中一個最常用的技術就是基于近鄰(neighbor-based)的方法[5]，其工作流程主要分為鄰居發(fā)現(xiàn)和評分預測兩步[6]。基于模型的算法收集評分數(shù)據(jù)進行學習并推斷用戶行為模型，進而對某個產品預測評分。

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

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

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

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

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

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

Tu,v的取值范圍為[-1,1]，值越大表示用戶之間的相似度越高。具體的計算可由例4來說明。

例4. 假設我們有產品集合{i1,i2,i3},從產品集合中抽取產品對的集合為{,,}。用戶u對這三個產品的評分為3、4和2，用戶的評分則是2、4和3。則用戶u從產品對的偏好集合為{i1i2,i1?i3,i2?i3}，用戶v對產品對的偏好集合則為{i1i2,i1?i3,i2?i3}。可知Nc=2，Nd=1。兩用戶u、v之間的相似度

然而，EigenRank只是考慮了用戶間產品偏好的一致性，而沒有考慮用戶對不同產品對的偏好程度以及偏好在用戶間的流行度。我們在之前的工作[10]中對表示為詞項的用戶偏好進行了類似TF-IDF的加權，然后采用向量空間模型進行用戶間相似度的計算,但偏好融合與預測部分采用的算法和EigenRank一樣均為貪婪算法，效率不高。

3 Weighted-Tau Rank算法

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

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

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

3) 3.3節(jié)利用加權的Kendall Tau Rank相關系數(shù)計算用戶間的相似度；

4) 3.4.1節(jié)選出與目標用戶相似度高的用戶作為近鄰來預測目標用戶對特定產品對的偏好；

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

3.1 偏好表示

我們從用戶u以及其評過分的產品集合Iu中抽取該用戶的偏好集合為{ikil|ik,il∈I∧k

ikil表示用戶對產品對ik和ik的偏好。ik?il則表示相比產品il，用戶u更喜歡ik；ikil則相反。

3.2 偏好權重

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

3.2.1 Degree

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

3.2.2 Popularity

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

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

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

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

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

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

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

3.2.3 Degree-Popularity

和TF-IDF的加權方式類似，Degree-Popularity的值為Degree和Popularity兩者的乘積。對用戶u，偏好ikil的Degree-Popularity權重定義如式(10)。

3.3 相似度計算

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

其中,wk,l為用戶u和v對偏好ikil權重的乘積，即式(12)。

3.4 排序預測

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

3.4.1 偏好預測

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

接下來我們要借助近鄰預測用戶對未知產品對的偏好關系。我們將與目標用戶u有相似偏好的用戶記為u的鄰居Nu。Nu中越多的用戶對《盜夢空間》的評分高于《畫皮》，我們就越有理由相信u相對于畫皮更喜歡《盜夢空間》。具體定義見式(13)。

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

3.4.2 偏好融合

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

算法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 實驗結果與分析

4.1 實驗設置

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

在實驗過程中，為了保證目標用戶和其鄰居的共同評分的電影具有一定的數(shù)量，我們首先對數(shù)據(jù)集做了過濾操作： EachMovie中剔除了評分數(shù)小于100的用戶，MovieLens中剔除了評分數(shù)小于50的用戶。然后隨機選取用戶評分的80%用做訓練，10%用于校驗，其余的10%用于測試。

4.2 評價指標

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

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

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

4.3 實驗結果分析

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

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

圖1 MovieLens結果對比

圖2 EachMovie結果對比

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

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

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

5 結語

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

[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] 劉建國, 周濤, 汪秉宏. 個性化推薦系統(tǒng)的研究進展[J]. 自然科學進展,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.