基于PMF進行潛在特征因子分解的標簽推薦

劉勝宗 樊曉平 廖志芳 吳言鳳

摘要： 現有社會標簽推薦技術存在數據稀疏、時間復雜度高以及可解釋性低等問題，鑒于此，提出基于概率矩陣分解（PMF）進行潛在特征因子聯合分解的標簽推薦算法（TagRecUPMF），它結合用戶、資源及標簽3方面的潛在特征，聯合構建對應的概率形式的潛在特征向量，然后根據它們兩兩之間的特征向量內積進行線性組合，從而產生TopN推薦。該算法解決了數據規(guī)模大且稀疏情況下的精度問題，算法的線性復雜度使得其可用于大規(guī)模數據。實驗結果表明，相比于TagRecCF，PITF， TTD，Tucker，NMF等算法，本文算法既提高了推薦的準確率，又降低了時間損耗。與PITF算法相比較，準確率得到了提高，而處理時間相差不明顯；與TTD算法相比較，在準確率相差不明顯的情況下，大大降低了時間損耗。因此，本文的TagRecUPMF算法相比其他算法表現出了一定的優(yōu)勢。

關鍵詞：協同過濾；潛在特征因子；標簽推薦；推薦系統；概率矩陣分解

中圖分類號：TN911。23 文獻標識碼：A

作為Web2。0的重要特征，社會標簽系統允許用戶對系統資源利用個性化標簽進行標注，從而使具有相同興趣偏好的用戶相互推薦及共享資源＼[1＼]。國內外知名社會標簽系統有音樂類標簽系統last。fm＼[2＼]、圖片類標簽系統flickr＼[3＼]、電影類標簽系統movielens＼[4＼]、書簽和出版物信息共享系統bibsonomy＼[5＼]等。這些網站采用社會標簽整合各類資源，這有助于用戶組織、瀏覽和搜索自己感興趣的資源，也能夠更好地幫助用戶之間進行溝通及共享，而標簽推薦系統可將用戶感興趣的標簽推薦給使用同一資源的用戶＼[6＼]。

標簽推薦系統基于用戶以往的標注行為進行標簽推薦，這種推薦同時依賴于用戶和資源＼[7＼]。目前廣泛應用的協同過濾推薦＼[8＼]（CF）為目標用戶尋找有相似標注行為的其他用戶（近鄰），并將近鄰在目標資源上標注過的其他標簽推薦給目標用戶，該技術簡單和實用，但也面臨著冷啟動和數據稀疏問題＼[6＼]。基于此，研究者嘗試從其他角度去研究新的推薦策略及方法，目前，大部分關于標簽推薦的研究集中在因子分解方面，比較典型的有非負矩陣分解（NMF）＼[9＼]，奇異值分解（SVD）＼[10＼]，高階奇異值分解（HOSVD）＼[6＼]，Tucker張量分解＼[8＼]，PITF張量分解＼[1＼]以及TTD張量分解＼[6＼]，這些方法在解決數據稀疏性和缺失值帶來的問題上取得了較好的效果。但這些分解技術僅考慮了標注關系，并未考慮用戶的評分偏好關系，由于用戶選擇標簽進行標注的過程中同時受自身對資源和標簽的興趣偏好影響。另外，不同用戶對標簽或資源的興趣偏好側重面不一樣[11]，標簽和資源是受某些基本的、潛在的特征支配，用戶的偏好則是由用戶對這些潛在特征喜好程度的加權綜合，用戶的標注行為除受本身偏好的影響之外，同樣還受到標簽和資源的潛在特征結構的影響＼[8＼]。這體現出一種“資源標簽”的雙重概率關系＼[12＼]，這種關系同樣存在于“用戶資源”、“用戶標簽”情形中。為了解決上述問題，本文提出一種新的標簽推薦方法（TagRecUPMF），該方法采用概率矩陣分解技術進行潛在特征因子聯合分解，然后通過潛在特征向量之間相互組合完成推薦。

湖南大學學報（自然科學版）2015年

第10期劉勝宗等：基于PMF進行潛在特征因子分解的標簽推薦

1問題定義

社會標簽系統可形式化定義為F：=（US，TS，IS，RS），其中US為User集合，TS為Tag集合，IS為Item集合，RS為User，Item和Tag之間的關系集合，其中RS∈TS×US×IS＼[6＼]。標簽推薦是在用戶訪問的資源上推薦與資源相關的標簽。符號標記如表1所示。

表1符號標記表

Tab。1Definition table of symbol

符號標記

解釋說明

US={u1，u2，…，um}

用戶集合，共m個用戶

IS={i1，i2，…，in}

資源集合，共n個資源

TS={t1，t2，…，to}

標簽集合，共o個標簽

U∈Rl×m

用戶潛在特征矩陣

V∈Rl×n

資源潛在特征矩陣

W∈Rl×o

標簽潛在特征矩陣

l∈R

潛在特征空間維數

B={bui}，B∈Rm×n

用戶資源關系矩陣

C={but}，C∈Rm×o

用戶標簽關系矩陣

A={ait}，A∈Rn×o

資源標簽關系矩陣

一般地，用戶對標簽的認可程度、用戶對資源的興趣程度和資源與標簽的關聯程度分別表示成用戶標簽認可關系矩陣C、用戶資源興趣矩陣B和資源標簽關聯度矩陣A。l表示潛在特征空間的維數。用戶對標簽的認可程度由用戶潛在特征向量和標簽潛在特征向量的內積得到，用戶對資源的興趣程度由用戶潛在特征向量和資源潛在特征向量的內積得到，資源與標簽的關聯度由資源潛在特征向量和標簽潛在特征向量的內積得到。

設用戶u訪問資源i時，選擇標簽t的概率表示為yu，i，t，那么

yu，i，t=f（UTuVi，UTuWt，VTiWt）。（1）

式中：Uu為用戶u的潛在特征向量；Vi為資源i的潛在特征向量；Wt為標簽t的潛在特征向量；UTuVi，UTuWt，VTiWt分別用于計算用戶u對資源i的感興趣程度、用戶u對標簽t的認可程度以及標簽t與資源i的關聯程度；f（·）參數為UTuVi，UTuWt，VTiWt的函數；yu，i，t又稱為給定用戶u和資源i情況下的標簽t的推薦概率。

當用戶u在訪問資源i時，標簽的TopN推薦列表可以定義如下＼[6＼]：

Top（u，i，N）：=argmaxNt∈T（yu，i，t）。（2）

式中：N為推薦列表的長度。

2基于UPMF的標簽推薦模型

本文提出基于聯合概率矩陣分解（UPMF）的標簽推薦算法TagRecUPMF，算法包含3個部分：

1）求解潛在特征向量。首先根據訓練數據集計算實體間的關系矩陣，然后根據分解算法通過梯度下降方法，以最大化聯合的后驗概率為目標函數，學習得到用戶潛在特征向量、資源潛在特征向量以及標簽潛在特征向量。

2）根據公式（3）對給定的用戶和資源計算標簽集中各標簽的推薦概率。

yu，i，t=βUTuVi+γUTuWt+δVTiWt，

s。t。β+γ+δ=1。（3）

3）根據TopN推薦規(guī)則，選取推薦概率排名前N的標簽推薦給用戶。

2。1實體間關系矩陣的計算

1）用戶資源關系矩陣。用戶資源關系矩陣B表示m個用戶對n個資源的興趣對應關系。B中元素bui表示用戶u對資源i感興趣的程度。

bui=αg（hui）+（1-α）g（rui）。 （4）

式中：hui為資源i被用戶u標注的次數；rui為用戶u對資源i的評分；g（·）為logistic函數，用于歸一化；α為平衡因子，取值為＼[0，1＼]。

2）用戶標簽關系矩陣。用戶標簽關系矩陣C表示m個用戶對o個標簽的偏好對應關系。C中每個元素cut表示用戶u對標簽t的偏好或者認知程度。

cut=g（λut）。（5）

式中：λut為用戶u使用標簽t的次數。

3）資源標簽關系矩陣。資源標簽關系矩陣A表示n個資源和o個標簽的關聯度關系。A中元素ait表示資源i和標簽t之間的關聯程度，通常認為，在資源i上標注標簽t的次數越多，表示有越多的用戶認為標簽t和資源i的關聯度大。ait由公式（6）計算得到：

ait=g（τit）。（6）

式中：τit為資源i上標注標簽t的次數。

2。2概率矩陣聯合分解

TagRecUPMF標簽推薦模型的概率圖如圖1所示。

圖1TagRecUPMF的概率圖模型

Fig。1Probabilistic graphical model of TagRecUPMF

其中，用戶潛在特征向量Uu由用戶標簽關系信息和用戶資源關系信息共享；資源潛在特征向量Vi則由用戶資源關系信息和資源標簽關系信息共享；標簽潛在特征向量Wt由用戶標簽關系信息和資源標簽關系信息共享。

概率矩陣分解模型中，首先假設潛在特征向量Uu，Vi，Wt的先驗服從均值為0的高斯分布，即

p（U|σ2U）=∏mu=1N（Uu|0，σ2UI）；（7）

p（V|σ2V）=∏ni=1N（Vi|0，σ2VI）；（8）

p（W|σ2W）=∏oi=1N（Wt|0，σ2WI）。（9）

在給定用戶u，資源i的潛在特征向量（維數為l）Uu，Vi后，用戶u對i的感興趣程度bui滿足均值為g（UTuVi），方差為σ2B的高斯分布并相互獨立，因此B的條件概率分布為：

p（B|U，V，σ2B）=∏mu=1∏ni=1[N（bui|g（UTuVi），σ2B）]IBui。（10）

式中：IBui為指示函數，當用戶u訪問或標注過資源i時，其值為1，否則為0；g（ ·）為logistic函數，用于將UTuV歸一化。

用戶u對標簽t的興趣程度cut滿足均值為g（UTuWt）方差為σ2C的高斯分布且相互獨立，那么C的條件概率分布如下：

p（C|U，W，σ2C）=∏mu=1∏ot=1[N（cut|g（UTuWt），σ2C）]ICut。 （11）

其中，當用戶u使用過標簽t進行標注時，ICut為1，否則為0。

若資源i和標簽t的關聯度ait滿足均值為g（VTiWt），方差為σ2A的高斯分布且相互獨立時，A的條件概率分布為：

p（A|V，W，σ2A）=∏ni=1∏ot=1[N（ait|g（VTiWt），σ2A）]IAit。 （12）

其中，當資源i和標簽t有關聯時，IAit值為1，否則為0。

由圖1可以推導出U，V，W的后驗分布函數，該分布函數的自然對數形式如公式（13）所示。

公式（13）中，

瘙 綇 是不依賴于參數的常量。在概率矩陣分解模型中，需要最大化公式（13），這是一個無約束情況下的優(yōu)化問題，該問題的求解等價于最小化公式（14）。

lnp（U，V，W|B，C，A，σ2W，σ2V，σ2U，σ2A，σ2C，σ2B）=

-12σ2B∑mu=1∑ni=1IBui（bui-g（UTuVi））2-

12σ2C∑mu=1∑ot=1ICut（cut-g（UTuWt））2-

12σ2A∑ni=1∑ot=1IAit（ait-g（VTiWt））2-

12σ2U∑mu=1UTuUu-12σ2V∑ni=1VTiVi-12σ2W∑ot=1WTtWt-

∑mu=1∑ni=1IBuilnσB-∑mu=1∑ot=1ICutlnσC-

∑ni=1∑ot=1IAitlnσA-l∑mu=1lnσU-l∑ni=1lnσV-

l∑ot=1lnσW+

瘙 綇 ；（13）

Ω（U，V，W，B，C，A）=12∑mu=1∑ni=1IBui（bui-

g（UTuVi））2+λC2∑mu=1∑ot=1ICut（cut-g（UTuWt））2+

λA2∑ni=1∑ot=1IAit（ait-g（VTiWt））2+

λU2‖U‖2F+λV2‖V‖2F+λW2‖W‖2F；（14）

ΩUu=∑ni=1IBui（g（UTuVi）-bui）g'（UTuVi）Vi+

λC∑ot=1ICut（g（UTuWt）-cut）g'（UTuWt）Wt+λUUu； （15）

ΩVi=∑mu=1IBui（g（UTuVi）-bui）g'（UTuVi）Uu+

λA∑ot=1IAit（g（VTiWt）-ait）g'（VTiWt）Wt+λVVi；（16）

ΩWt=λC∑mu=1ICut（g（UTuWi）-cut）g'（UTuWi）Uu+

λA∑ni=1IAit（g（VTiWt）-ait）g'（VTiWt）Vi+λWWt。 （17）

公式（14）中：λC=σ2Bσ2C；λA=σ2Bσ2A；λU=σ2Bσ2U；λV=σ2Bσ2V；λW=σ2Bσ2W；‖·‖2F表示F范數。公式（14）的局部最小值采用梯度下降法進行求解，參數Uu，Vi，Wt的梯度下降更新公式分別為公式（15）-式（17）。

2。3算法復雜度分析

在梯度下降法中，算法的時間開銷主要取決于目標函數Ω及其相應的梯度下降更新公式。在標簽標注數據和用戶評分數據中，存在大量的缺失值，這導致A，B，C矩陣很稀疏，容易得出公式（14）目標函數的計算時間復雜度為O（ρBl+ρCl+ρAl），其中ρA，ρB，ρC分別表示3個實體關系矩陣A，B，C的非零元素數目。同理，梯度下降公式（15）-（17）的計算復雜度分別為O（ρBl+ρCl），O（ρBl+ρAl），O（ρCl+ρAl）。所以，算法的一步迭代過程中的計算復雜度為O（ρBl+ρCl+ρAl），這表示算法的時間復雜度隨3個關系矩陣中觀測數據數量呈正線性關系，意味著該算法可應用于大規(guī)模的數據。

3實驗結果及分析

3。1實驗設計

3。1。1數據集

本文選取目前標簽推薦研究常用的201110M版movielens數據集，該數據集包含了2 113個用戶，10 197部電影以及13 222個標簽。

3。1。2算法性能評價指標

目前衡量推薦算法優(yōu)劣需要同時考慮準確率和召回率，而準確率和召回率＼[12＼]指標往往是負相關的，因此為了綜合考慮算法的性能，本文選用F1指標＼[12＼]來衡量算法的性能，F1指標定義見公式（18），其中Precision表示準確率，Recall表示召回率，其計算方法可參考文獻＼[12＼]。F1越高，算法的性能越好。

F1=2·Precision×RecallPrecision+Recall。（18）

3。1。3實驗設計

為了檢驗TagRecUPMF算法的推薦效果，本文需要通過實驗解決以下幾個方面的問題：1）潛在特征向量的維度l對推薦性能的影響；2）平衡因子α對推薦結果的影響；3）參數λA和λC對推薦結果的影響；4）TagRecUPMF算法與現有經典標簽推薦算法的準確度及時間效率比較。

實驗前，為了比較不同數據規(guī)模和稀疏情況下算法的效果，分別從實驗數據中抽取90%，70%，50%，30%作為訓練集，其余作為測試集進行實驗。

實驗過程中，通過對訓練集嘗試不同的參數值，進而在測試集上得到F1指標值。經反復測試得出參數設為α=0。4，β=γ=δ=1/3，λC=1，λA=0。6， λU=λV=λW=0。05時，算法的效果最優(yōu)。在后續(xù)的實驗中，若無特別說明，這些參數均設為最優(yōu)值。同時實驗中，TopN推薦中取N=10。

3。2實驗分析

3。2。1參數l對推薦性能的影響

該實驗用于檢測潛在特征向量的維數l對推薦算法性能的影響。圖2為l對算法準確率的影響，圖3為l對算法時間效率的影響。從圖2可以看出，隨著特征向量維數的增加，推薦準確率慢慢提高，這說明增加潛在特征向量的維數可以提高矩陣分解算法的準確性，而當l>15時，精度增加的趨勢變緩。由圖3可以看出，隨著l的增大，算法耗費的時間也成正比的增大。因此出于準確率和時間損耗的平衡考慮，選擇l=15。

3。2。2α對推薦準確率的影響

在式（4）中，利用參數α來調節(jié)資源被標注次數和資源評分在用戶對資源興趣程度中的權重比例，從而影響推薦準確率。實驗結果如圖4所示。由圖4可以看出，α值處于0。3到0。5之間時，F1的值由上升轉變?yōu)橄陆第厔?，這就意味著在這2個值之間存在一個可以使得F1最優(yōu)的α值。本文將α值選取為0。4。這說明利用資源被標注次數和資源評分的加權組合來表示用戶對資源興趣程度時的效果略好于這兩者單獨表示的情況。

l

圖2l對算法準確率的影響

Fig。2Influence on accuracy of l

l

圖3l對算法時間消耗的影響

Fig。3Influence on complexity of l

α

圖4平衡因子α對算法準確率的影響

Fig。4Influence on accuracy of α

3。2。3參數λA和λC對推薦結果的影響

概率矩陣聯合分解模型有5個參數，分別為λA，λC，λU，λV，λW，在這部分實驗中，主要討論λA和λC的影響，而其他3個參數為了簡單起見設置為相同的值，并通過交叉驗證（crossvalidation）的

方式獲取這3個參數的最優(yōu)值，即λU=λV=λW=0。05。TagRecUPMF算法中λA決定了資源標簽關系矩陣對算法的影響權重，而λC決定了用戶標簽關系矩陣對算法的影響權重。當這兩者同時設為0時，表示算法在進行推薦時，僅考慮用戶資源關系矩陣，而當λA或λC設為+

SymboleB@ 時，則意味著僅利用資源標簽關系矩陣或者用戶標簽關系矩陣。實驗結果如圖5所示，圖中顯示了在λA和λC的不同取值時的算法準確率。當λA=1，λC=0。6時，TagRecUPMF算法的準確率最高。這表明這兩個參數相互約束，而用戶標簽關系矩陣的影響更顯著。這是因為面向用戶推薦標簽時，資源和標簽之間的相似關系受語義影響較大（多義或同義），而用戶和標簽之間的關系雖然受用戶的主觀影響，但依然反映了用戶對標簽的特殊偏好，因此在推薦過程中需要考慮這兩種關系的權衡，也應更多地考慮用戶對標簽的個性化因素。

圖5參數λA和λC對算法準確度的影響

Fig。5Influence on accuracy of λAandλC

3。2。4推薦算法的性能比較

該部分實驗是將TagRecUPMF算法和目前常見的部分經典算法從準確率和時間消耗兩個方面進行比較，選用的參照算法包括基于協同過濾的標簽推薦（TagRecCF）、基于Tucker分解的標簽推薦、非負矩陣分解標簽推薦算法（NMF）、基于三部圖張量分解標簽推薦算法（TTD）以及PITF算法。

表2是在不同訓練數據集規(guī)模時各算法的F1值（10次實驗結果取平均值）。由表1可以看出，在訓練數據集比例較?。?lt;50%）時，TagRecUPMF算法準確度相對其他算法而言均有提升，當比例較大時，TagRecUPMF算法比TTD算法的準確度略低，而相比其他算法依然高出7%～13%，其中TagRecCF算法的準確度受數據稀疏影響最大，準確率最低，實驗結果呈現這種現象的原因是Tucker，NMF，PITF算法未考慮用戶對資源的評分，影響了準確度，而TTD算法雖然沒考慮評分，但它不僅僅考慮實體間的直接關系，還考慮了兩兩實體因為第三方實體而產生的間接關系，雖然提高了準確性，但其時間損耗高，在實際應用中并不實用。

表3為時間消耗統計情況，其中時間消耗最大的是Tucker算法，其次是TTD算法，而PITF和本文的TagRecUPMF時間消耗最小，PITF算法的時間消耗略低于TagRecUPMF算法，這是由于PITF算法沒有考慮評分數據，因此在時間性能上略為占優(yōu)，但在時間復雜度上，這兩者方法依然同為線性級別。因此，比較各算法在準確率和時間消耗指標上的綜合情況，本文的TagRecUPMF算法相比其他算法而言表現出了一定的優(yōu)勢。

表2TagRecUPMF算法與其他參照算法的準確率比較

Tab。2Accuracy comparison between TagRecUPMF and other reference algorithms

訓練數據集比例/%

F1

TagRecCF

Tucker

NMF

PITF

TTD

TagRecUPMF

90

0。456 3

0。476 9

0。516 9

0。505 9

0。596 7

0。589 6

70

0。359 6

0。456 1

0。491 2

0。472 7

0。571 3

0。565 9

50

0。156 6

0。432 3

0。468 5

0。456 9

0。498 8

0。544 4

30

0。086 9

0。410 1

0。453 6

0。443 2

0。482 3

0。521 1

表3TagRecUPMF算法與其他參照算法的時間消耗比較

Tab。3Time consuming between TagRecUPMF and other reference algorithms

訓練數據集比例/%

運行時間/min

TagRecCF

Tucker

NMF

PITF

TTD

TagRecUPMF

90

165

378

243

87

356

88

70

99

201

120

47

183

49

50

65

128

53

27

129

31

30

50

96

34

21

98

22

4總結

在社會標簽推薦系統中，由于數據非常稀疏，加上現有的標簽推薦算法并未充分利用標簽標注系統中的相關信息，因此精度不高，而矩陣、張量分解等技術用一種降維的方法表示稀疏數據，緩解了數據稀疏帶來的精度問題。本文基于概率矩陣分解，將用戶、標簽、資源三方面的潛在特征因子進行聯合分解，并將求得的特征向量兩兩之間的內積進行線性加權并產生推薦。在實驗過程中討論了TagRecUPMF算法中各參數對結果的影響，根據實驗結果綜合精度和時間損耗指標可以得出，TagRecUPMF算法相比當前流行的算法具有一定的優(yōu)勢。

參考文獻

[1]RENDLE S， SCHMIDTTHIEME L。 Pairwise interaction tensor actorization for personalized tag recommendation ＼[C＼]//Proceedings of the 3rd ACM International Conference on Web Search and Data Mining。 New York，USA：ACM，2010：81-90。

[2]JSCHKE R， MARINHO L， HOTHO A， et al。 TagRecommendations in folksonomies＼[J＼]。 Knowledge Discovery in Databases： PKDD，2007，47（2）： 506-514。

[3]SIGURBJRNSSON B， VAN ZWOL R。 Flickr tag recommendation based on collective knowledge＼[C＼] //Proceedings of the 17th International Conference on World Wide Web。 Beijing：ACM， 2008： 327-336。

[4]SEN S， LAM S K， RASHID A M， et al。 Tagging， communities， vocabulary， evolution＼[C＼]//Proceedings of the 2006 20th Anniversary Conference on Computer Supported Cooperative Work。 New York， USA：ACM， 2006： 181-190。

[5]HOTHO A， JSCHKE R， SCHMITZ C， et al。 BibSonomy： A social bookmark and publication sharing system＼[C＼]//Proceedings of the Conceptual Structures Tool Interoperability Workshop at the 14th International Conference on Conceptual Structures。 Aalborg， Denmark， 2006：87-102。

[6]廖志芳，李玲，劉麗敏，等。三部圖張量分解標簽推薦算法＼[J＼]。計算機學報，2012，35（12）：2625-2632。

LIAO Zhifang， LI Lin， LIU Limin，et al。 A tripartite decomposition of tensor for social tagging ＼[J＼]。Chinese Journal of Computers， 2012，35（12）：2625-2632。（In Chinese）

[7]MA H， YANG H， LYU M R， et al。 Sorec： Social recommend dation using probabilistic matrix factorization ＼[C＼]//Proceedings of the 17th ACM Conference on Information and Knowledge Management。 New York， USA：ACM， 2008： 931-940。

[8]SYMEONIDIS P， NANOPOULOS A， MANOLOPOULOS Y。 TagRecommendations based on tensor dimensionality reduction＼[C＼]//Proceedings of the 2008 ACM Conference on Recommender Systems。 Lausanne， Switzerland：ACM， 2008： 43-50。

[9]LANGSETH H， NIELSEN T D。 A latent model for collaborative filtering＼[J＼]。 International Journal of Approximate Reasoning， 2012， 53（4）： 447-466。

[10]POLAT H， DU W。 SVDbased collaborative filtering with privacy＼[C＼]//Proceedings of the 2005 ACM Symposium on Applied Computing。New York， USA：ACM，2005： 791-795。

[11]MA H， KING I， LYU M R。 Learning to recommend with social trust ensemble＼[C＼]//Proceedings of the 32nd Inter National ACM SIGIR Conference on Research and Development in Information Retrieval。 Boston，USA：ACM，2009： 203-210。

[12]朱郁筱，呂琳媛。推薦系統評價指標綜述＼[J＼]。電子科技大學學報，2012，41（2）：163-175。

ZHU Yuxiao， LV Linyuan。 Evaluation metrics for recommender systems＼[J＼]。 Journal of University of Electronic Science and Technology of China， 2012， 41（2）： 163-175。 （In Chinese）