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

（1．中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙 410075；2．中南大學(xué) 軟件學(xué)院，湖南 長沙 410075；3．湖南財政經(jīng)濟學(xué)院 網(wǎng)絡(luò)化系統(tǒng)研究所，湖南 長沙 410205）

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

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

1 問題定義

社會標簽系統(tǒng)可形式化定義為F：＝（US，TS，IS，RS），其中US為User集合，TS為Tag集合，IS為Item 集合，RS為User，Item 和Tag之間的關(guān)系集合，其中RS∈TS×US×IS［6］．標簽推薦是在用戶訪問的資源上推薦與資源相關(guān)的標簽．符號標記如表1所示．

表1 符號標記表Tab．1 Definition table of symbol

一般地，用戶對標簽的認可程度、用戶對資源的興趣程度和資源與標簽的關(guān)聯(lián)程度分別表示成用戶－標簽認可關(guān)系矩陣C、用戶－資源興趣矩陣B和資源－標簽關(guān)聯(lián)度矩陣A．l表示潛在特征空間的維數(shù)．用戶對標簽的認可程度由用戶潛在特征向量和標簽潛在特征向量的內(nèi)積得到，用戶對資源的興趣程度由用戶潛在特征向量和資源潛在特征向量的內(nèi)積得到，資源與標簽的關(guān)聯(lián)度由資源潛在特征向量和標簽潛在特征向量的內(nèi)積得到．

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

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

當用戶u在訪問資源i時，標簽的Top－N 推薦列表可以定義如下［6］：

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

2 基于UPMF的標簽推薦模型

本文提出基于聯(lián)合概率矩陣分解（UPMF）的標簽推薦算法TagRec－UPMF，算法包含3個部分：

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

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

3）根據(jù)Top－N 推薦規(guī)則，選取推薦概率排名前N的標簽推薦給用戶．

2．1 實體間關(guān)系矩陣的計算

1）用戶－資源關(guān)系矩陣．用戶－資源關(guān)系矩陣B表示m個用戶對n個資源的興趣對應(yīng)關(guān)系．B中元素bui表示用戶u對資源i感興趣的程度．

式中：hui為資源i被用戶u標注的次數(shù)；rui為用戶u對資源i的評分；g（·）為logistic函數(shù)，用于歸一化；α為平衡因子，取值為［0，1］．

2）用戶－標簽關(guān)系矩陣．用戶－標簽關(guān)系矩陣C表示m個用戶對o個標簽的偏好對應(yīng)關(guān)系．C中每個元素cut表示用戶u對標簽t的偏好或者認知程度．

式中：λut為用戶u使用標簽t的次數(shù)．

3）資源－標簽關(guān)系矩陣．資源－標簽關(guān)系矩陣A表示n個資源和o個標簽的關(guān)聯(lián)度關(guān)系．A中元素ait表示資源i和標簽t之間的關(guān)聯(lián)程度，通常認為，在資源i上標注標簽t的次數(shù)越多，表示有越多的用戶認為標簽t和資源i的關(guān)聯(lián)度大．a(chǎn)it由公式（6）計算得到：

式中：τit為資源i上標注標簽t的次數(shù)．

2．2 概率矩陣聯(lián)合分解

TagRec－UPMF標簽推薦模型的概率圖如圖1所示．

圖1 TagRec－UPMF的概率圖模型Fig．1 Probabilistic graphical model of TagRec－UPMF

其中，用戶潛在特征向量Uu由用戶－標簽關(guān)系信息和用戶－資源關(guān)系信息共享；資源潛在特征向量Vi則由用戶－資源關(guān)系信息和資源－標簽關(guān)系信息共享；標簽潛在特征向量Wt由用戶－標簽關(guān)系信息和資源－標簽關(guān)系信息共享．

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

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

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

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

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

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

其中，當資源i和標簽t有關(guān)聯(lián)時，值為1，否則為0．

由圖1 可以推導(dǎo)出U，V，W的后驗分布函數(shù)，該分布函數(shù)的自然對數(shù)形式如公式（13）所示．

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

2．3 算法復(fù)雜度分析

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

3 實驗結(jié)果及分析

3．1 實驗設(shè)計

3．1．1 數(shù)據(jù)集

本文選取目前標簽推薦研究常用的2011－10M版movielens數(shù)據(jù)集，該數(shù)據(jù)集包含了2 113 個用戶，10 197部電影以及13 222個標簽．

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

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

3．1．3 實驗設(shè)計

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

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

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

3．2 實驗分析

3．2．1 參數(shù)l對推薦性能的影響

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

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

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

圖2 l對算法準確率的影響Fig．2 Influence on accuracy of l

圖3 l對算法時間消耗的影響Fig．3 Influence on complexity of l

圖4 平衡因子α對算法準確率的影響Fig．4 Influence on accuracy ofα

3．2．3 參數(shù)λA和λC對推薦結(jié)果的影響

概率矩陣聯(lián)合分解模型有5 個參數(shù)，分別為λA，λC，λU，λV，λW，在這部分實驗中，主要討論λA和λC的影響，而其他3個參數(shù)為了簡單起見設(shè)置為相同的值，并通過交叉驗證（cross－validation）的方式獲取這3個參數(shù)的最優(yōu)值，即λU＝λV＝λW＝0．05．TagRec－UPMF 算法中λA決定了資源－標簽關(guān)系矩陣對算法的影響權(quán)重，而λC決定了用戶－標簽關(guān)系矩陣對算法的影響權(quán)重．當這兩者同時設(shè)為0時，表示算法在進行推薦時，僅考慮用戶－資源關(guān)系矩陣，而當λA或λC設(shè)為＋∞時，則意味著僅利用資源－標簽關(guān)系矩陣或者用戶－標簽關(guān)系矩陣．實驗結(jié)果如圖5所示，圖中顯示了在λA和λC的不同取值時的算法準確率．當λA＝1，λC＝0．6時，TagRec－UPMF算法的準確率最高．這表明這兩個參數(shù)相互約束，而用戶－標簽關(guān)系矩陣的影響更顯著．這是因為面向用戶推薦標簽時，資源和標簽之間的相似關(guān)系受語義影響較大（多義或同義），而用戶和標簽之間的關(guān)系雖然受用戶的主觀影響，但依然反映了用戶對標簽的特殊偏好，因此在推薦過程中需要考慮這兩種關(guān)系的權(quán)衡，也應(yīng)更多地考慮用戶對標簽的個性化因素．

圖5 參數(shù)λA 和λC 對算法準確度的影響Fig．5 Influence on accuracy ofλAandλC

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

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

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

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

表2 TagRec－UPMF算法與其他參照算法的準確率比較Tab．2 Accuracy comparison between TagRec－UPMF and other reference algorithms

表3 TagRec－UPMF算法與其他參照算法的時間消耗比較Tab．3 Time consuming between TagRec－UPMF and other reference algorithms

4 總 結(jié)

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

［1］RENDLE S，SCHMIDT－THIEME 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］J?SCHKE R，MARINHO L，HOTHO A，etal．TagRecommendations in folksonomies［J］．Knowledge Discovery in Databases：PKDD，2007，47（2）：506－514．

［3］SIGURBJ?RNSSON 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，etal．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，J?SCHKE R，SCHMITZ C，etal．BibSonomy：A social bookmark and publication sharing system［C］／／Pro－ceedings of the Conceptual Structures Tool Interoperability Workshop at the 14th International Conference on Conceptual Structures．Aalborg，Denmark，2006：87－102．

［6］廖志芳，李玲，劉麗敏，等．三部圖張量分解標簽推薦算法［J］．計算機學(xué)報，2012，35（12）：2625－2632．

LIAO Zhi－fang，LI Lin，LIU Li－min，etal．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，etal．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．SVD－based 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］朱郁筱，呂琳媛．推薦系統(tǒng)評價指標綜述［J］．電子科技大學(xué)學(xué)報，2012，41（2）：163－175．

ZHU Yu－xiao，LV Lin－yuan．Evaluation metrics for recommender systems［J］．Journal of University of Electronic Science and Technology of China，2012，41（2）：163－175．（In Chinese）