標簽推薦Top-N列表優(yōu)化算法

朱小兵 丁明玉 肖 玉

(賽輪集團股份有限公司信息中心 山東 青島 266400)

0 引 言

信息爆炸時代，用戶每天接收的信息量遠遠超過了自身所能消費的信息量，造成信息過載現(xiàn)象[1-2]。標簽推薦系統(tǒng)允許用戶為不同內容進行簽注，用戶可以用標簽組織和搜索信息[3-4]。如今，社交媒體網(wǎng)站日益流行，標簽推薦成為一個活躍且不斷發(fā)展的研究課題[5]。

標簽可以用來表征用戶的偏好信息和物品的內容信息，用戶可以根據(jù)個人的偏好，向網(wǎng)絡上的物品資源添加各種標簽描述信息。目前而言，業(yè)界常用的標簽推薦算法主要包含了以下三個大類：基于協(xié)同過濾的標簽推薦算法、基于圖的標簽推薦算法、基于內容的標簽推薦算法。

基于協(xié)同過濾的標簽推薦算法將用戶、物品與標簽的三元關系簡化到更低的維數(shù)空間。Jaschke等[6]考慮到了不同的標簽具有不同的流行度，提出了一種基于流行度的標簽推薦算法。Rendle等[7]提出了一種基于張量(Tensor)的標簽推薦算法，該算法稱為成對交互張量分解模型PITF(two-two interaction tensor factorization)。PITF標簽推薦算法可以很好地完成對用戶、物品和標簽三者之間的建模，因而取得了較好的實驗結果。

基于圖的方法的基本思想是基于用戶的標記行為，以用戶、物品和標記為頂點構造圖，并構建邊[8]，該類算法不需要考慮物品的內容信息和標簽語義信息。Jaschke等[9]提出了一種基于圖的標簽推薦算法，該算法可以有效地獲取用戶、物品、標簽三者之間的內在聯(lián)系，稱之為FolkRank算法。Riaz等[10]考慮了標簽的時間效應，作者認為較新的標簽應該被賦予更大的權重，進而提出了TimeFolkRank標簽推薦算法。

基于內容的標簽推薦算法考慮更多是物品資源的內容信息。Feng等[11]提出了一個優(yōu)化框架，通過最大化標簽推薦曲線下的平均面積來學習最優(yōu)特征權值。Wu等[12]提出一種生成模型，該模型是基于標簽的分布狀況進行構建的，以此實現(xiàn)標簽推薦，精度有較高的提升。

但是上述所有的標簽推薦算法為每個用戶給出的標簽推薦列表均為固定數(shù)量，導致推薦效果不好、用戶的滿意度不高。為提高標簽推薦的準確性，本文采用了另一個方向，思考如何更好地求取最優(yōu)的標簽推薦列表長度，從而提高標簽推薦算法的準確度。

針對標簽推薦列表長度固定的問題，主要從以下兩個方面進行優(yōu)化:(1) 首先將大于Top-1標簽分數(shù)的1/2的標簽加入候選推薦列表，通過定義成對標簽置信度指標，計算候選列表中的標簽與Top-1標簽的相關性，按照相關性的大小順序，完成對標簽推薦列表的重排序；(2) 對于重排序以后得到的標簽推薦列表，通過計算每個子列表的相關性系數(shù)，相關性系數(shù)最高的子列表即為最佳推薦列表長度。

為評估方法有效性，選擇四個標簽算法作為對比實驗，分別是：基于流行度的標簽推薦算法Pop[6]、Rendle和Schmidt-Thieme的成對相互作用張量分解模型(PITF)[7]、著名的基于三部圖的標簽推薦算法FolkRank[9]、考慮時間效應影響的TimeFolkRank標簽推薦算法[10]。在兩個真實數(shù)據(jù)集上進行實驗驗證，證明方法的有效性。

1 相關技術理論

一個標簽推薦系統(tǒng)由用戶集U、標簽集T、物品集I組成[13]，三者之間的內在關系可以表示為S∈U×I×T，其中，(u,i,t)∈S代表用戶u給物品i打了標簽t，對于用戶u給物品i打標簽t的興趣通常由分數(shù)score(t|u,i)來估計。標簽推薦的目的是計算待推薦的用戶物品(u,i)的前N個得分最高的標簽。

1.1 PITF算法

PITF標簽推薦算法基于矩陣分解模型[14]，矩陣分解模型被認為是性能最好的模型之一。PITF標簽推薦算法從用戶、物品、標簽三元組中計算成對的排序約束[15]，可捕獲用戶和標簽之間以及物品和標簽之間的交互行為。其模型公式為:

1.2 FolkRank算法

FolkRank是基于PageRank[9]的思想設計的基于圖的標簽推薦算法。FolkRank認為當一個重要用戶使用標簽或者標記重要的物品時，標簽也應變得相對重要，對于用戶或物品而言也采用相同原則。因此，F(xiàn)olkRank標簽推薦算法將用戶-物品-標簽之間的關系表示為一個三部圖，三部圖可表示為一個鄰接矩陣A：

式中：MUT代表用戶標簽矩陣；MUI代表用戶物品矩陣；MIT代表物品標簽矩陣；對角線為0矩陣。定義排序向量(列向量)ω:

FolkRank標簽推薦算法增加了個性化偏好向量。對于給定的目標用戶和給定的目標物品，F(xiàn)olkRank標簽推薦算法的排序向量計算公式如下:

f=w1-w0

(5)

式中：w1是個性化的排序向量，通過非均勻向量p得到，維度為|U|+|I|+|T|，對于待推薦的用戶物品(u,i)，在非均勻向量對應的元素有更大的權重，通常設置為1+|U|、1+|I|，此外，非均勻向量的其他元素均為1；w0是一個全局排序向量，通過均勻向量p得到，向量元素均為1；f是FolkRank推薦算法最終排序向量。

1.3 Pop算法

假設一個標簽t對于用戶u或物品i而言是非常流行的(即經(jīng)常使用的)，那么當用戶u給物品i打標簽時，標簽t則具有強相關性。Pop模型在對標簽的受歡迎程度進行歸一化以及加權后，得到如下計算公式：

參數(shù)ρ調整基于用戶的標簽流行度以及基于物品的標簽流行度的權重。當ρ=1時，僅考慮物品的熱門標簽，將其設置為0時，僅考慮用戶的熱門標簽，默認情況下，將ρ固定為0.5，認為兩者同樣重要。Pop算法的優(yōu)點是可以快速計算，同時給出較好預測結果。

1.4 TimeFolkRank算法

TimeFolkRank是由傳統(tǒng)的FolkRank算法驅動的。TimeFolkRank感興趣的是標簽在一段時間內的重要性，幾個月前出現(xiàn)的標簽顯然比幾年前出現(xiàn)的更重要。通過對每個標簽進行加權來優(yōu)化FolkRank算法。利用式(7)計算時間加權FolkRank值。

TimeFolkRank=wi×FolkRank

(7)

式中：wi是每個標簽基于時間的權重。取決于標簽t的標記日期，標簽出現(xiàn)得越早，時間權重則越小。選擇指數(shù)方式衰減權重[16]。

W1=DR(y-ti)/12

(8)

式中：y是當前時間；ti是標簽t的標記時間；(y-ti)是以年為單位的時間間隔；DR是一個參數(shù)，參數(shù)值為0.5。

2 算法模型

標簽推薦算法的推薦列表長度常為固定值，這將導致推薦精度下降，用戶體驗感很差。為解決該問題，提出一種優(yōu)化Top-N標簽推薦列表的算法，從如下兩個方面展開介紹：

(1) 詳細介紹Top-N標簽推薦列表的重排序算法，算法思想是首先將大于Top-1標簽分數(shù)的1/2的標簽加入候選推薦列表，通過定義成對標簽置信度指標，計算候選列表中的標簽與Top-1標簽的相關性，按照相關性由小到大進行排序，完成推薦列表的重排序。

(2) 介紹最佳Top-N推薦列表長度求取算法，算法思想是對重排序后的標簽推薦列表，通過計算每個子列表的相關性系數(shù)，相關性系數(shù)最高的子列表即為最佳推薦列表長度。

2.1 Top-N推薦列表重排序算法

本節(jié)介紹改進標簽推薦Top-N列表的算法模型(Top-N list reordering algorithm,LRA)，該算法旨在對Top-N列表進行重排序。此外，因其是對標簽推薦Top-N列表進行的優(yōu)化，所以LRA模型可以在許多標簽推薦算法中使用，是一個較通用的算法模型。

LRA模型思想：對于待推薦的用戶物品對(u,i)，在將Top-N標簽列表推薦給用戶之前，LRA對其進行改進。LRA需要個數(shù)大于N的候選標簽，然后對其重新進行排序，保留相關性更高前N個標簽作為最終的Top-N標簽推薦列表。

2.1.1算法相關定義

定義1對于給定待推薦的用戶u和物品i，用戶對標簽的興趣指數(shù)通常通過分數(shù)score(t|u,i)來估計。因此，標簽推薦算法的目的是推薦給用戶物品對(u,i)前N個得分最高的標簽：

定義2標簽的用戶列表U(t)代表的是使用過標簽t的一組用戶集合，標簽的商品列表I(t)代表的是由標簽t標注的一組商品集合。

定義3為衡量標簽t與標簽t′的相關性度量，定義成對置信度度量PCM(t→t′)，用來表示兩個標簽之間的相關性。成對置信度度量PCM在一定程度上決定了用戶在使用標簽t的基礎上使用標簽t′的興趣。成對置信度度量PCM同時考慮了用戶與物品：

成對置信度度量PCM從兩個維度(用戶和物品)挖掘標簽之間的關聯(lián)規(guī)則，能同時考慮標簽在用戶和物品上的共現(xiàn)頻率。

2.1.2LRA建模

對于標簽推薦算法來說，LRA可以作為附加算法使用，首先需要對Top-N標簽推薦列表進行擴展，然后再對擴展以后的標簽推薦列表進行重排序，并返回最終的Top-N標簽推薦列表。

按照Top-1標簽獲得的分數(shù)為基準進行Top-N標簽推薦列表的擴展，將分數(shù)大于Top-1標簽獲得分數(shù)的二分之一的標簽均加入到候選標簽推薦列表中，一個簡單的例子可以更好地理解標簽列表的擴展過程。

假設，待推薦的目標用戶為u，目標物品為i，通過標簽推薦算法輸出的Top-5推薦結果如表1所示。

表1 Top-5推薦結果

擴展后的標簽列表如表2所示。只要是分數(shù)大于Top-1分數(shù)(0.9)的一半(0.45)即可。

表2 擴展后的推薦結果

由5個擴展為6個，該算法就是從6個中重新排序選擇5個作為最終標簽推薦列表。

用D表示給定的標簽推薦列表，D是按照分數(shù)降序排列的，最高得分標簽是D[1]。相比D中的其他標簽更關注D[1]標簽，因為它是標簽推薦算法給出的最好的標簽選擇。LRA對其進行了修正，并計算所有候選標簽與D[1]相比較的成對置信度，最后根據(jù)新的分數(shù)計算公式對D中的所有標簽進行重新排序。

用新的分數(shù)計算公式對每個標簽t進行二次排序：

scorePCM(t|u,i)=(1+PCM(D[1]→t))·

score(t|u,i)

(11)

通過從用戶角度和物品角度來考慮，通常出現(xiàn)在標簽推薦列表D中第一個推薦標簽比旁邊的標簽應該具有更高的被推薦可能性。

2.2 Top-N推薦列表長度優(yōu)化算法

2.1節(jié)介紹了Top-N列表重排序LRA模型，該算法實現(xiàn)了Top-N標簽推薦列表的重排序，但是推薦給用戶的標簽列表仍然是長度固定的Top-N列表，當N很大時，推薦的標簽列表中包含大量與待推薦的用戶、物品相關性較低的標簽，從而造成推薦質量不高。針對該問題，本節(jié)在LRA完成Top-N列表重排序的基礎上，進一步提出一種確定推薦列表最優(yōu)大小的無參數(shù)算法(Parameter-free algorithm with optimal size of recommendation list,PFA)，引入關聯(lián)性度量，以從給定的推薦標簽列表中找到最相關的標簽。通過推薦一些更相關的標簽，排除相關性較低的標簽，從而調整列表的長度，提高標簽推薦的質量。

2.2.1PFA基礎

標簽推薦算法旨在推薦最合適的標簽，這是以用戶為中心的Web 2.0的重要組成部分。標簽推薦的主要挑戰(zhàn)之一是其推薦列表的有效性，現(xiàn)有的標簽推薦算法通常使用固定數(shù)量的標簽推薦列表。

本節(jié)提出的算法遵循另一個方向，通過優(yōu)化推薦列表長度以提高標簽推薦的準確性。給目標用戶u推薦的標簽列表為LN={t1,t2,…,tN}，PFA的目的是求取出推薦列表LN的一個子列表，該子列表與待推薦的用戶物品的相關性最大，并用該子列表替換推薦列表LN，實現(xiàn)更好的用戶體驗，更好的推薦精度。

LN的所有子列表的大小是遞增的,以便保持標簽順序，如圖1所示。

圖1 子列表示意圖

為標簽推薦列表LN引入了相關性的度量方法，相關性度量Rel(LN|u,i)估計了用戶u使用LN中所有推薦標簽對物品i進行打標簽的可能性。基于該相關性度量，計算出將向用戶推薦的最佳列表(the one having the optimal size,bls)：

bls=max(s|s∈S)

(12)

S={s|s≤N∧?n≤N,Rel(Ln|u,i)≤Rel(Ls|u,i)}

(13)

算法可以動態(tài)調整推薦標簽列表的大小，從而提高推薦的準確性。PFA是建立在2.1節(jié)提出的LRA的基礎之上，并對LRA進行了擴展，PFA與LRA都是標簽推薦算法的附加算法，可以認為標簽推薦算法的一個頂部過濾器，PFA與LRA的目的都是通過優(yōu)化標簽列表進而提高標簽推薦算法的準確度。

2.2.2PFA建模

本節(jié)將詳細介紹PFA的相關性度量計算方式以及用于從給定標簽推薦列表中檢索最佳子列表的算法。假設Rel(LN|u,i)代表的是用戶u、物品i與標簽t的相關性，LN是一個N個標簽組成的有序標簽推薦列表，用戶u和物品i與標簽t推薦列表LN的相關性定義如下：

式中：ω(LN|u,i)表示調整標簽推薦列表相關性的權重，使得列表相關性計算不會一味地傾向于更短的標簽推薦列表，推薦列表長度越長則ω(LN|u,i)越大。Rel(LN|u,i)是標簽對用戶u和物品i的相關性，表示用戶u使用標簽t標記物品i的可能性。

Max代表最長標簽推薦列表長度，Rel(LMax|u,i)代表用戶u物品i與推薦列表LMax的相關性。算法從Max依次遞減至1，尋找最佳的推薦列表長度，每當遞減一次，都會計算當前子列表與用戶u、物品i的相關性，記錄并更新推薦列表的最佳長度，如果兩個不同長度的標簽推薦子列表具有相同的相關性，算法則將優(yōu)先選擇最長的作為推薦列表的最佳長度。

現(xiàn)在常用的計算相關性的方法是將已知標簽(用戶曾使用過或者物品曾被打過)與其他標簽區(qū)分開來，與其他標簽相比，歷史上與用戶或物品相關的標簽更值得進行推薦，下面介紹該算法的思想。

用PN=LN∩T(u)∩T(i)來表示在推薦列表LN當中包含已知標簽的子列表，為已知標簽子列表中的標簽賦予一個較大的權重，而為其他非已知標簽賦予一個較小的權重，從而做到突出已知標簽：

式中：rmax和rmin由我們指定某一具體數(shù)值，rmax設置為原推薦列表固定長度，通常設置為5，rmin設置為1。式(15)經(jīng)過化簡可以得到式(16)。

(16)

通過式(16)可以看出相關性Rel(LN|u,i)僅與|PN|與N的比值相關，當且僅當|PN|與N相同時(即推薦列表當中所有標簽均為已知標簽)，相關性最大，相關性為1。因此，推薦列表的相關性可以進一步化簡為：

上述方法優(yōu)點是思路清晰簡單，所需計算數(shù)據(jù)均可從數(shù)據(jù)集中統(tǒng)計得到；缺點是當推薦列表當中的標簽全為已知標簽時，相關性為1，無法繼續(xù)篩選其他的推薦子列表，從而無法得出最佳列表長度。

為了更加準確地計算標簽列表的相關性，本文使用另一種改進的方案：將標簽的相關性值與從可用數(shù)據(jù)(訓練集)中獲得的一些統(tǒng)計數(shù)據(jù)聯(lián)系起來，簡稱為bls算法。本節(jié)提出的相關性度量方法同時考慮了用戶以及物品的標簽流行度，式(18)給出了標簽的相關性計算方法。

式中：U(i,t)代表給物品i打標簽t的用戶集合；I(u,t)代表用戶u使用標簽t打過的物品集合；U(i)代表給物品i打標簽的用戶集合；I(u)代表用戶u打過標簽的物品集合。此外，標簽的相關性根據(jù)其在推薦列表中的排名降低(第一個標簽的相關性高，最后一個的相關性低)，為了避免算法一味地偏向于較短的標簽推薦列表，因此有必要在計算標簽推薦列表的相關性時使用加權方法。考慮到標簽隨著其位置的靠后，相關性自然減少，定義推薦列表的權重：

此權重函數(shù)計算了推薦列表大小的重要性，可以在推薦長推薦列表的同時懲罰短的推薦列表。因此，結合式(19)，得出了一個新的列表相關性度量：

至此，本文提出的優(yōu)化標簽Top-N推薦列表的PFA介紹完畢，PFA的總結如算法1所示。

算法1PFA

輸入：LRA算法重排序后的列表LMax。

輸出：bls。

bls←Max

//bls:最佳列表長度

blR←Rel(LMax|u,i)

//blR:最佳列表的相關性

forN=(Max-1) to 1 do

ifRel(LN|u,i)>blRthen

bls←N

blR←Rel(LN|u,i)

end

end

Returnbls

3 實驗結果

3.1 實驗數(shù)據(jù)和實驗準備

3.1.1實驗數(shù)據(jù)

數(shù)據(jù)集為HetRec于2011年發(fā)布的MovieLens數(shù)據(jù)集(HetRec-MovieLens)和MovieLens-10M數(shù)據(jù)集。這兩個數(shù)據(jù)集既包含了物品的屬性信息，也包含了用戶打標簽的行為。HetRec-MovieLens數(shù)據(jù)集包含2 113個用戶、5 908個物品、9 079個標簽和47 957個打標簽記錄；MovieLens-10M數(shù)據(jù)集包含4 009個用戶、7 601個物品和95 580個打標簽記錄。

首先，對MovieLens-10M數(shù)據(jù)集中的標簽進行了預處理，剔除無效標簽，合并相似標簽。由于標簽數(shù)據(jù)過于稀疏，采用p-core=5對兩個數(shù)據(jù)集進行預處理，即保留出現(xiàn)超過5次的用戶、物品和標簽的數(shù)據(jù)。數(shù)據(jù)預處理后數(shù)據(jù)集的具體統(tǒng)計信息如表3所示。

表3 兩個數(shù)據(jù)集的統(tǒng)計信息

3.1.2評價指標

使用訓練集推薦算法進行訓練，使用測試集進行預測。評價指標選擇F1值，因為F1既考慮到了準確率也考慮到了召回率。下面給出準確率、召回率、F1的計算公式：

式中：A代表算法推薦的標簽；B代表用戶實際打的標簽。

3.1.3實驗準備

為了測試PFA的性能，實驗采用以下方法作為baseline算法：

(1) Pop：基于流行度的標簽推薦算法。

(2) PITF(成對交互張量分解)：一種基于張量分解的標簽推薦算法。

(3) FolkRank：FolkRank標簽推薦算法擴展了自適應PageRank算法，該算法的核心思想是利用用戶偏好向量對標簽進行排序。

(4) TimeFolkRank：基于FolkRank標簽推薦算法，考慮標簽時間信息，標簽越新推薦的權重就越大。

3.2 實驗設置和實驗結果

3.2.1實驗設置

為降低實驗結果的偶然性，將整個數(shù)據(jù)集按照隨機劃分的原則將其劃分成完全相等的十個部分，每次隨機選取其中的八個部分當作訓練集，剩下的作為測試集，將以上步驟重復五次，最終將五次實驗結果取平均值，以此作為最終實驗結果。

3.2.2實驗對比與分析

PFA是FolkRank以及其他標簽推薦算法的一個附加算法，是對以上算法推薦列表的改進。選擇四個標簽推薦算法進行對比實驗，在命名上，以FolkRank標簽推薦算法為例，對比算法命名為FolkRank，改進算法命名為PFA-FolkRank，其他算法也是如此。本文實驗結果如表4所示。

表4 兩個數(shù)據(jù)集的統(tǒng)計信息

為更加直觀地顯示實驗結果，對每個對比算法的實驗結果逐一進行畫圖，其中，橫坐標為標簽推薦列表長度，縱坐標為標簽推薦算法的F1數(shù)值。具體的實驗結果如圖2-圖5所示。

(a) HetRec-MovieLens(b) MovieLens-10M圖2 Pop算法在兩個數(shù)據(jù)集上的F1值

(a) HetRec-MovieLens(b) MovieLens-10M圖3 FolkRank算法在兩個數(shù)據(jù)集上的F1值

(a) HetRec-MovieLens(b) MovieLens-10M圖4 PITF算法在兩個數(shù)據(jù)集上的F1值

(a) HetRec-MovieLens(b) MovieLens-10M圖5 TimeFolkRank算法在兩個數(shù)據(jù)集上的F1值

PFA可以作為標簽算法的一種附加算法，主要用于對各種標簽推薦算法生成的Top-N推薦列表進行改進優(yōu)化。傳統(tǒng)的標簽推薦算法，如FolkRank標簽推薦算法，通常都是為目標用戶目標物品生成一個固定長度的推薦列表，這種方式，在一定程度上降低了用戶的滿意度，而PFA可以有效緩解該問題。PFA首先對Top-N標簽推薦列表進行了重排序，又對重排序后的推薦列表挑選出來最佳的子列表，從而在優(yōu)化列表的基礎上實現(xiàn)了列表變短的操作，保留下的標簽理論上是與待推薦的目標用戶與目標物品相關性較高的標簽，從而提高了標簽推薦的性能。經(jīng)過兩個數(shù)據(jù)集的驗證，本文提出的PFA對于標簽推薦算法是有效的。

4 結 語

本文提出一種優(yōu)化標簽推薦算法Top-N推薦列表的算法。首先，詳細介紹了Top-N標簽推薦列表的重排序算法，算法的思想是首先將大于Top-1標簽分數(shù)的1/2的標簽加入候選推薦列表，通過定義成對標簽置信度指標，計算候選列表中的標簽與Top-1標簽的相關性，按照相關性大小，完成推薦列表的重排序；其次，介紹了最佳Top-N推薦列表長度求取算法，算法的思想是對重排序后的標簽推薦列表，計算每個子列表的相關性系數(shù)，相關性系數(shù)最高的子列表即為最佳推薦列表長度。

在HetRec-MovieLens和MovieLens-10M數(shù)據(jù)集上的實驗表明，本文提出的RFA優(yōu)化Top-N列表算法可以有效地提高傳統(tǒng)算法的F1值，因此，作為FolkRank以及其他標簽推薦算法的附加算法，該算法可以有效地提高標簽推薦的質量。