PMUS-HOSGD張量分解方法及其在標簽推薦中的應用

楊 林,顧軍華,官 磊,張宇娟,彭玉青

(河北工業大學 a.計算機科學與軟件學院; b.河北省大數據重點實驗室,天津 300400)

0 概述

隨著信息技術和互聯網的發展,互聯網使用者從信息匱乏的時代步入了信息過載的時代,用戶的個性化需求也越來越大。用戶的個性化特征注重的是用戶的參與,用戶可以對資源(視頻、歌曲、圖片等)賦予自定義的標簽,逐漸形成Folksonomy的大眾分類法[1],該分類法不僅可以獲取并分析用戶的興趣特征,而且在一定程度上豐富了資源的描述信息。隨著網絡資源規模爆發式的增長[2],用于標注的標簽越來越多,用戶面對大量的數據如何選出自己需要的標簽越來越困難。解決信息過載的有效方法是個性化推薦[3],由此基于社會標注系統的標簽推薦服務應運而生。例如,給書籍和視頻提供短評的豆瓣網、論文書簽網站CiteULike和視頻推薦網站MovieLens等都是利用社會標注系統對資源進行標注,然后通過標簽推薦系統將用戶感興趣的標簽推薦給用戶。推薦系統簡化標注過程,方便用戶,提高了標簽的質量和標注的準確性。

標簽推薦系統的核心是構建“用戶-資源-標簽”三維數據,挖掘數據之間的潛在關系,從而準確的為用戶推薦標簽。目前,針對標簽推薦系統已經展開了大量的研究。文獻[4-5]將三維關系拆成“用戶-資源”、“用戶-標簽”和“資源-標簽”3個二維矩陣,使用協同過濾算法進行處理。文獻[6]受Google的PageRank算法[7]啟發提出FolkRank算法,同樣將三維關系拆分成3個二維關系。但是這些方法破壞了高維空間數據原本的特征結構,丟失了三者之間的協同關系。為解決這個問題,挖掘“用戶-資源-標簽”之間潛在的語義關聯,文獻[8]提出使用三維張量存儲“用戶-資源-標簽”數據。

在構建初始張量階段,目前使用最多的方法是用“0/1”構建張量,這種方法構建容易,可讀性強,但是不能體現出標簽在資源中的差異。文獻[9]發現由于熱門標簽通常有較大的權重,導致推薦結果偏向于熱門標簽,反而降低推薦的準確率。文獻[10-12]提出使用TF-IDF來設置懲罰項,用以區分標簽對資源的重要程度,可以減少熱門標簽對結果的影響。然而上述方法都忽略了用戶對資源的偏好程度。

對構建完成的張量進行分解,可以挖掘張量包含的潛在信息。文獻[13]將奇異值分解方法推廣到三維張量,提出高階奇異值分解(Hign Order Singular Value Decomposition,HOSVD)方法對張量進行分解,該方法保留了三者的關聯信息。文獻[14]基于矩陣奇異值分解能有效地平滑數據矩陣中的數據特點,在使用HOSVD進行分解的過程中,結合用戶朋友關系修正張量分解結果,建立張量分解模型。文獻[15]提出新的推薦算法PITF(Pairwise Interaction Tensor Factorization),該算法在張量分解的過程中加入3個二維關系之間的潛在聯系,推薦質量得到提高。針對目前推薦系統存在的稀疏性問題,文獻[16]在CubeSVD[17]的基礎上進行改進,使用ALS算法進行矩陣分解,提出CubeALS推薦算法,該算法有效提高了稀疏數據標簽推薦的準確性。文獻[18]提出一種基于上下文學習和張量分解的個性化推薦算法,將用戶和項目的上下文信息加入2個張量中,有效改善數據稀疏性。文獻[19]提出一種改進的基于張量分解的推薦算法,引入基于標簽綜合共現的譜聚類方法,使用HOSVD-HOOI算法對初始張量進行分解,進一步優化推薦效果。目前的張量分解方法多數以SVD為基礎進行改進。使用SVD方法對張量的每個維度矩陣進行分解,雖然在一定程度上提高了推薦的準確性,但由于構建的初始張量極其稀疏,需要在分解前對初始張量的展開矩陣進行填充,這樣存在2個問題:1)填充過程增加數據量,同時增加算法復雜度;2)簡單的數據填充易造成數據失真,從而影響推薦結果的準確度。

針對上述問題,本文結合PMUS(Penalty Mechanism-User Score)張量構建方法與HOSGD(High Order Stochastic Gradient Descent)張量分解方法,提出PMUS-HOSGD算法對“用戶-資源-標簽” 三維數據進行處理,為用戶推薦個性化標簽。本文主要工作如下:1)在張量構建階段,提出懲罰機制與用戶評分相結合的張量構建方法PMUS來計算標簽的權值;2)在張量分解階段,提出基于隨機梯度下降(Stochastic Gradient Desecent,SGD)的高階張量分解方法HOSGD。

1 相關工作

1.1 張量及其矩陣展開

張量由多維數據組成,是一個N維的向量空間,一維張量是一個向量(Vector),二維張量是一個矩陣(Matrix),三維或者更高維的張量則是高維張量(Tensor)。標簽推薦系統使用三維張量存儲數據,3個維度分別代表用戶、資源、標簽。

使用aijk表示三維張量的值,其大小代表用戶i給資源j標注標簽k的概率。例如,用戶1給資源1標注了標簽2,則對應張量中的值為a112=1,其余的標注0。

矩陣展開是將一個張量的元素重新排列(即對張量的不同維度進行重新排列),得到一個矩陣的過程。三維張量A∈RI1×I2×I3在第n維度上的展開矩陣表示為X(n)∈RIn×(I1×I2×…×In-1×In+1×…×IN)。

1.2 張量分解

基本的張量分解算法HOSVD需要對張量A每個維度(n=1,2,3)的展開矩陣進行SVD分解,計算公式是:

(1)

通過上述公式對An進行奇異值分解,分別得到3個維度的展開矩陣的U矩陣和奇異值矩陣S。

張量與矩陣的模積定義為一個張量X∈RI1×I2×…×IN和一個矩陣U∈RJ×In的n-mode乘積(X×nU)∈RI1×I2×…×In-1×J×In+1×…×IN,其元素定義為:

(2)

如果J

(3)

(4)

2 PMUS-HOSGD張量分解方法

傳統的張量分解算法HOSVD可以挖掘“用戶-資源-標簽”三維數據之間的關系,但在實際應用中,用戶僅對個別資源進行標簽標注,這會導致張量中的數據極度稀疏。目前常用的HOSVD算法在張量分解的過程前需要對稀疏矩陣進行填充,這樣會造成數據的失真。因此,本文結合PMUS張量構建方法與HOSGD張量分解方法,提出PMUS-HOSGD算法對 “用戶-資源-標簽” 三維數據進行處理,為用戶推薦個性化標簽。

2.1 PMUS初始張量構建

在“用戶-資源-標簽”三維張量中,“0/1”構建方法簡單易行,但是標簽之間沒有區分度,因此可以使用PMUS的思想計算標簽的權重;同時,用戶對資源的評分可以體現出用戶對資源的偏好程度,用標簽的權重乘以評分可以很好地區分出標簽之間以及用戶和資源之間的重要度,最終構建整個張量。

PMUS的主要思想是:如果一個標簽在一個資源中出現多次,并且在其他資源中很少出現,則可以認為該標簽具有很好的區分度,同時如果一個用戶給資源的評分越高,用戶對這個資源的偏愛程度越大,則給這個視頻標注的標簽的概率就越大。

使用PMUS計算標簽權值的過程如下:

1)計算標簽t對于資源i的重要度import(t,i),針對每個資源都有一個標簽權重向量,公式如下:

(5)

2)根據重要度(import)計算標簽t在用戶u對資源i標注的標簽集中占的比例權重weight(u,t,i),公式如下:

weight(u,t,i)=import(t,i)/sum_weight(u,i)

(6)

其中,sum_weight(u,i)是用戶u給資源i標注的所有標簽的重要度的總和。

3)weight(u,t,i)乘以用戶u給資源i的評分就是張量中用戶u在資源i中使用標簽t的權值Value(u,t,i),公式如下:

Value(u,t,i)=weight(u,t,i)×score(u,i)

(7)

2.2 基于隨機梯度下降的張量分解算法HOSGD

傳統的SVD算法對二維矩陣進行分解,可以求出對應的特征矩陣,隨著用戶數量、資源數量和標簽數量的急劇增長,SVD分解帶來的誤差和復雜度也在不斷增加,正是由于這些問題,Simon Funk發表了一個只考慮已有評分的矩陣分解方法,稱為Funk-SVD,也就是被文獻[20]稱為隱語義模型的矩陣分解方法,該方法使用梯度下降法(Gradient Descent,GD)最小化訓練集中觀察值的RMSE(Root Mean Squared Error),在二維矩陣分解中取得了較好的推薦效果。

標準的梯度下降法在更新變量前要對所有的樣本計算誤差并匯總,導致算法收斂速度較慢,因此本文使用隨機梯度下降法,SGD是在梯度下降法的基礎上,在迭代過程中使用部分樣本計算梯度,因此其比標準梯度下降法有更高的收斂速度。

借鑒SGD在二維矩陣分解領域中的應用,本文提出HOSGD張量分解算法。HOSGD算法在張量進行分解的過程中,為提高準確性,使用SGD算法對展開矩陣分解,降低了傳統分解方法帶來的計算復雜度及誤差。

在用戶給資源標注標簽的過程中,形成了若干{用戶,資源,標簽}數據,使用PMUS方法構建利用式(5)、式(6)和式(7)計算Value(u,t,i),得到三維張量A∈RX×Y×Z,HOSGD算法對張量的展開矩陣進行SGD分解,得到3個特征矩陣,進而計算出初始張量的核心張量,然后可以得到初始張量的近似張量。算法描述如下:

算法1PMUS-HOSGD張量分解

輸入用戶、資源、標簽數據三元組(u,i,t)

輸出初始張量的近似張量

1.使用PMUS方法按照式(5)、式(6)、式(7)計算標簽的權值

2.使用張量A存儲式(7)計算得到的Value(u,t,i)

3.將張量A按照3個維度展開得到A1、A2、A3

4.for i=1 to 3

5.按照算法2對Ai進行處理,得到P1、P2、P3

6.end for

在算法1中,對于三維張量A∈RX×Y×Z,其中,用戶、資源和標簽的數量分別為X,Y和Z,初始張量A展開得到的3個矩陣A1、A2、A3的規模分別為X×YZ、Y×XZ和Z×XY,按照算法2,分別對A1、A2、A3進行分解,得到每個維度的特征矩陣P1、P2、P3,其中P1∈RX×k1,P2∈RY×k2,P3∈RZ×k3,3個特征矩陣的特征數k1、k2、k3是根據數據規模設定的,一般ki<

(8)

(9)

其中,左邊第1項是誤差項,用原始矩陣中有值的項減去P和Q對應行和列相乘得到的值,左邊第2項是正則化項,防止過擬合。對L最小化就得到了P和Q。

通過式(8)分別對PU和QI求其梯度:

(10)

(11)

其中,λ表示正則化參數,A(U)表示矩陣A第U行中不為0或者空的列,A(I)表示矩陣A第I列中不為0或者空的行,通過矩陣A第U行,可以得到矩陣P第U行的梯度,也就是PU需要更新的值:

(12)

(13)

其中,α表示步長,對矩陣P中所有的PU進行更新,或者對Q矩陣中所有的QI進行更新,就完成了一次迭代,在每次迭代的過程中,實現了P和Q矩陣的一次更新,損失函數L的值減小。算法描述如下:

算法2基于SGD的張量展開矩陣分解

輸入張量的展開矩陣Ai

輸出Ai的特征矩陣P

4.步驟2和步驟3是一次迭代的過程,多次執行步驟2和步驟3,不斷更新PU和QI的值,直到完成迭代次數t或者誤差小于閾值,得到P和Q的最優解

在算法2中,λ和α參數需要在實驗中多次調優得到。算法的核心在于每次更新PU和QI時只使用原始矩陣中有值的部分,得到P和Q的最優解,P即為對應的特征矩陣。

PMUS-HOSGD張量分解方法的時間復雜度主要是在對每個維度展開矩陣的分解基礎上進行計算的。算法2矩陣分解的時間復雜度是O(t×X×k1×n1′),據此可得算法1的時間復雜度是O(t×(X×k1×n1′+Y×k2×n2′+Z×k3×n3′)),其中,t為迭代次數,k為特征數,n′是矩陣中平均每行非空數據的數目。

3 實驗結果與分析

本文使用相同的數據集和評價標準對比張量構建方法和張量分解方法,采用常用的評價指標驗證算法的有效性。

3.1 數據集

本文使用MovieLens數據集,包含用戶對視頻的評分,以及用戶給視頻標注的標簽數據。

使用MovieLens數據集構建的三維張量極其稀疏,因此對初始數據進行預處理,預處理后的數據中每個用戶都對15個或15個以上視頻打過標簽,每個視頻都由15個或15個以上用戶打過標簽。處理后的數據中用戶、視頻、標簽的數量分別是184、122、378,有20 149條“用戶、資源、標簽”數據。

3.2 評價標準

本文使用準確率(Precision)、召回率(Recall)和F值[21]作為算法的評價標準。在推薦系統中,準確率表示在推薦列表中得到的推薦結果與測試集中實際情況相同的物品數與所有的推薦物品數的比值,召回率指的是推薦列表中準確的結果占測試樣本的比例。在實驗過程中,將預處理后的數據集分成2部分:訓練集和測試集,其中,訓練集占75%,測試集占25%。

準確率和召回率的計算公式如下:

(14)

(15)

其中,test表示測試集,top_N表示推薦的結果,N表示推薦的數目,準確率和召回率的值越高推薦效果越好。

F值作為常用評價指標,能更好地反映推薦結果的效果,F的值越高推薦效果越好。

(16)

3.3 實驗結果

為驗證PMUS方法構建張量能提高推薦結果的準確率,實驗結合使用HOSVD分解算法,分別對比“0/1”、TF-IDF和PMUS張量構建方法的準確率、召回率和F值。實驗結果如圖1～圖3所示,每個圖中各有3條曲線,分別代表“0/1”、TF-IDF和PMUS張量構建方法結合HOSVD分解方法的實驗結果,每條曲線有8個節點,橫軸代表top_N的值,縱軸分別代表準確率、召回率和F值。

圖1 3種構建方法的準確率比較

圖2 3種構建方法的召回率比較

圖3 3種構建方法的F值比較

由圖1～圖3中3種不同構建方法的對比可知,在top_1時,使用“0/1”構建的張量進行分解推薦的準確率比PMUS和TF-IDF方法要好,但是隨著N的增長,PMUS方法構建的張量的準確率要高于其他2種算法,比TF-IDF平均高0.03。在推薦數量小于10時,PMUS方法構建張量的召回率和F值要明顯高于其他2種方法,說明使用PMUS方法構建張量,張量權值在加入標簽對視頻的權重以及用戶對視頻的評分后,使用戶對視頻標注的標簽權值更加真實。在實際推薦系統中,給用戶推薦的少量標簽不止1個,因此使用PMUS方法構建張量得到的推薦結果要優于普通的“0/1”和TF-IDF構建方法。

為進一步驗證HOSGD推薦算法的性能,本文結合使用PMUS方法構建張量,對HOSGD與HOSVD、協同過濾(Collaborative Filtering,CF)和CubeALS 算法進行了對比。基于CF的標簽推薦算法是目前應用比較廣泛的個性化推薦算法;HOSVD是一種經典的張量分解算法,被大量的應用于三維數據推薦領域,而且取得了良好的實驗結果;CubeALS推薦算法與其他優秀的算法對比,推薦效果有顯著提高。

在用HOSGD分解展開矩陣的過程中,涉及到步長α、正則化系數λ、特征因子數目k、迭代次數和閾值5個參數。α過大可能會導致迭代不收斂,從而發散,因此α分別取0.01、0.05、0.1、0.2、0.3、0.6進行對比;k數目過多會導致收斂速度慢,程序時間復雜度高,因此特征因子k數目取10到20進行對比。通過多次實驗,發現在迭代50次左右誤差結果接近0.08,趨于穩定。結合實驗結果,張量分解中取步長α為0.2,正則化系數λ為0.000 3,特征因子k數目為17,迭代50次,閾值為0.08。實驗結果如圖4～圖6所示。由圖4～圖6可知,4種算法的準確率呈下降趨勢,HOSGD的準確率在top_N小于5的情況下均高于其他算法,尤其在top_1至top_4階段HOSGD的準確率平均比CubeALS提升0.07。在top_1至 top_5階段HOSGD的召回率和F值也明顯高于次優的CubeALS算法。在實際推薦系統中,給用戶提供1-5個標簽,HOSGD算法符合實際要求。實驗結果表明,使用隨機梯度下降的張量分解算法HOSGD能夠充分利用SGD方法的優勢,有效處理稀疏張量,減少誤差。

圖4 4種推薦算法的準確率比較

圖5 4種推薦算法的召回率比較

圖6 4種推薦算法的F值比較

綜上所述,使用PMUS構建張量并結合使用基于隨機梯度下降法的HOSGD進行張量分解的PMUS-HOSGD算法,可以有效提高標簽推薦的準確率。

4 結束語

在個性化標簽推薦領域,使用張量存儲“用戶-資源-標簽”數據是一種很好的數據表示形式,但由于三維數據的稀疏性,傳統的張量構建方法和張量分解方法的推薦準確率較低。因此,本文利用PMUS構建張量,并結合基于隨機梯度下降法的HOSGD對張量進行分解。實驗結果表明,與 HOSVD、CF和CubeALS算法相比,PMUS-HOSGD算法具有更好的推薦效果。下一步將重點研究在大數據量的情況下如何提高推薦速度,并使用分布式平臺運行該算法。