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

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

（1．中南大學 信息科學與工程學院，湖南 長沙 410075；2．中南大學 軟件學院，湖南 長沙 410075；3．湖南財政經濟學院 網絡化系統研究所，湖南 長沙 410205）

作為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］，這種關系同樣存在于“用戶－資源”、“用戶－標簽”情形中．為了解決上述問題，本文提出一種新的標簽推薦方法（TagRec－UPMF），該方法采用概率矩陣分解技術進行潛在特征因子聯合分解，然后通過潛在特征向量之間相互組合完成推薦．

1 問題定義

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

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

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

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

式中：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時，標簽的Top－N 推薦列表可以定義如下［6］：

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

2 基于UPMF的標簽推薦模型

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

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

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

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

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

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

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

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

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

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

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

2．2 概率矩陣聯合分解

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

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

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

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

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

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

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

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

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

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

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

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

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個關系矩陣中觀測數據數量呈正線性關系，意味著該算法可應用于大規模的數據．

3 實驗結果及分析

3．1 實驗設計

3．1．1 數據集

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

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

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

3．1．3 實驗設計

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

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

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

3．2 實驗分析

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

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

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

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

圖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 參數λA和λC對推薦結果的影響

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

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

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

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

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

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

表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 總 結

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

［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］．計算機學報，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］朱郁筱，呂琳媛．推薦系統評價指標綜述［J］．電子科技大學學報，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）