基于帶偏倚最大間隔二值矩陣分解的多值矩陣分層填充

胡勝元,陳盛雙,謝 良

(武漢理工大學 理學院,武漢 430070)

1 引 言

對于部分元素已知的矩陣M,如何通過已知元素重構矩陣M′,使得M和M′盡量接近的問題就是矩陣填充問題.基于特征的協(xié)同過濾也可以看作矩陣填充,在協(xié)同過濾中,Y是一個m×n的評分矩陣,m是用戶數(shù),n是項目數(shù),且Y只有部分元素已知,即只存在部分用戶對部分項目的評分,協(xié)同過濾的目標就是要預測出用戶對其它項目的評分,從而完成對于矩陣Y的填充[1].矩陣分解是解決矩陣填充問題的一個重要方法,它通過已知的評分數(shù)據(jù)來學習出用戶的潛因子矩陣Um×k和項目的潛因子矩陣Vn×k,使得UVT和原矩陣Y在已知元素位置處盡量相等,并根據(jù)UVT來對未知評分數(shù)據(jù)作出預測.

近年來,矩陣分解在國內(nèi)外得到了廣泛研究.D.D.Lee等提出了非負矩陣分解算法[2](NMF),即使得U和V中的所有元素都大于0;B.Sarwar等提出了用奇異值分解來進行矩陣分解[3];N.Srebro等則提出了最大間隔矩陣分解(MMMF)來解決稀疏多值有序評分矩陣的填充問題[4].自從MMMF被提出以來,便引起了很多研究者的關注.

在二值評分矩陣中,評分數(shù)據(jù)的取值為+1(表示喜歡)或-1(表示不喜歡).每個項目的潛因子向量(V的對應行)可以看成k維特征空間中的一個點,用戶的潛因子向量(U的對應行)可以看成該k維空間中的一個超平面,該超平面就將項目的評分數(shù)據(jù)點分成了二類.MMMF的目標就是學習到表示用戶的超平面和表示項目的k維空間中的點,使得每個用戶對應的超平面能將這些項目的點分隔開來,從而對未知評分數(shù)據(jù)進行預測.但是這樣的二值分類過程中用戶的超平面必須要過k維空間中的原點,這樣的超平面并不一定是最優(yōu)超平面,可能會影響協(xié)同過濾的效果.

在多值評分矩陣中,評分可能為 {1,2,…,R},它不同于二值評分矩陣,不能簡單的用一個超平面將數(shù)據(jù)進行分類,解決該問題就必須要解決多分類問題.N.Srebro等提出了多值矩陣下的MMMF[5],將hinge函數(shù)成功用于分解多值評分矩陣,除了求解U和V,還需要求解閾值變量θm×(r-1),但是這樣對每個用戶構造多個超平面,不能夠保持最大間隔這一性

質[1].Vikas Kumar等于是提出了HMF[1],通過多次運用二值矩陣下的MMMF,對多值評分矩陣進行了填充.

本文所做的主要工作是首先針對傳統(tǒng)的最大間隔二值矩陣分解中存在的用戶超平面過原點的約束問題,添加偏倚量γ,將二值矩陣分解成U,V,γ三部分,來對二值評分矩陣進行填充,然后將該方法擴展到處理多值評分矩陣,實現(xiàn)對多值矩陣的填充.最后在真實的多值評分數(shù)據(jù)集Movielens上實現(xiàn)所提出的填充方法,并將其與類似算法進行比較,從第6節(jié)的實驗結果中可以看到,本文所提出的方法優(yōu)于現(xiàn)有的其它算法.

2 相關工作

矩陣分解的主要目標是使重構后的矩陣UVT和原矩陣Y在Y中已知元素處盡量接近.文獻[2]為了使UVT更接近原矩陣Y,增加了潛因子矩陣U和V中的元素非負這一約束條件,它的基本思想就是通過最小化已知元素值和UVT中對應的預測值差值的平方和來學習得到因子矩陣U和V.文獻[3]通過奇異值分解來學習得到因子矩陣U和V,令Y中未知元素全部為0,從而得到一個稀疏矩陣,再通過SVD對該稀疏矩陣進行分解,雖然該方法可以適當減少原矩陣Y的維度,但是SVD在稀疏矩陣上面會面臨很嚴重的過擬合問題.N.Srebro等在文獻[4]中提出的MMMF則用U和V的Froebenius范數(shù)最小化來代替矩陣秩的最小化,可以證明MMMF其實是一個半定規(guī)劃問題,并且能用標準的半定規(guī)劃求解方法來求解.但是現(xiàn)有的半定規(guī)劃求解方法只能求解矩陣Y的秩較小時的MMMF問題,因此文獻[5]提出Fast MMMF,擴展了hinge損失函數(shù),用梯度下降法來求解MMMF,使其可以解決多值評分矩陣的填充問題,并對不同的損失函數(shù)進行了研究.此外,文獻[6]也提出了最大間隔的分類方法,并對強泛化和弱泛化進行了討論.自從文獻[5]發(fā)表以來,Fast MMMF成為一個重要的研究課題,[7-10]對該方法其后進行了進一步的研究.同時,MMMF也引起了部分研究者對二值評分矩陣的興趣[11,12],但是他們都把它作為離散值評分矩陣分解的一個特例進行研究.文獻[13]基于近似支持向量機提出了PMMMF,提高了矩陣分解的速度.文獻[14]則根據(jù)相似用戶和相似項目,將原矩陣分割成多個子矩陣,進而對每個子矩陣分別進行分解.文獻[1]則多次對二值矩陣使用MMMF,從而實現(xiàn)對多值評分矩陣的填充.也有很多學者采用低秩矩陣分解對多值矩陣進行填充,從而進行個性推薦,他們大多是對用戶或者項目的一些特性以及相似性的度量上作了許多改進,如文獻[15]將用戶的評分信譽進行分組,來識別評分矩陣中的虛假評分,從而提高矩陣填充結果;文獻[16]則添加項目的熱門因子,對皮爾遜相似性進行優(yōu)化,從而提高推薦效果.

3 矩陣分解

假設Y是一個m×n階的用戶-項目評分矩陣,yij∈{1,2,…,R}表示第i個用戶對第j個項目的評分,yij=0表示第i個用戶未對第j個項目進行評分,即為Y中的未知元素.矩陣分解的目的就是將部分元素已知的矩陣Y∈Rm×n分解成矩陣U∈Rm×k和V∈Rn×k,使得Y≈UVT,其中k是矩陣U和V的秩,也即是我們的潛因子個數(shù),它遠小于m和n.

UVT可以看成是矩陣Y的一個低秩逼近.Ui表示U的第i行,它是第i個用戶的潛因子向量,Vj表示V的第j行,它是第j個項目的潛因子向量.在低秩矩陣分解中,最終目的就是要找到滿足Y≈UVT的秩最小的U和V.矩陣分解問題其實就是一個優(yōu)化問題,它的目標函數(shù)是:

(1)

其中Y是原評分矩陣,l(·)是損失函數(shù),用來衡量Y和UVT的相近程度,R(·)是正則函數(shù),保證U和V具有低秩性,防止過擬合,λ為正則系數(shù).如果l(·)和R(·)都為凸函數(shù),則該問題可以有效求解.常用的損失函數(shù)有平方損失函數(shù)[17],似然損失函數(shù)[18],以及hinge損失函數(shù)[5].

矩陣分解問題其實也是一個以Ω={(i,j)|yij≠0,?yij∈Y}為訓練集的有監(jiān)督學習問題,它必須避免過擬合問題,因此目標函數(shù)(1)又可以寫成(2):

(2)

Fazel發(fā)現(xiàn)也可以用核范數(shù)來代替正則函數(shù)來防止過擬合[19],即目標函數(shù)(1)也可以寫成(3):

(3)

其中‖UVT‖Σ是UVT的核范數(shù),它等于UVT的所有奇異值之和.但是‖·‖Σ是一個復雜的不可微函數(shù),最優(yōu)化問題不容易求解,因此文獻[19]定義了一個和核范數(shù)等價的函數(shù),目標函數(shù)(3)可以重述為:

(4)

4 帶偏倚最大間隔二值矩陣分解

假設Ym×n是一個二值評分矩陣(m為用戶數(shù),n為項目數(shù)),其中用戶對項目的評分為+1和-1,+1表示喜歡,-1表示不喜歡,因此二值評分矩陣的預測問題可以看成是一個二分類問題,對于每一個用戶而言,所有項目可以分為兩類,一類標記為+1,表示喜歡,另一類標記為-1,表示不喜歡.若將項目j表示成k維空間中的一個點Vj∈R1×k,則用戶可以看成是k維空間中的一個超平面,它將k維空間中的這n個點分隔在超平面兩側,一側是標記為+1的一類,另一側是標記為-1的一類.由于每個人的喜好不相同,他們對每個項目的分類結果也不同,則每個用戶表示的超平面也不同.根據(jù)每個用戶k維空間中的這n個點和已知的分類結果,可以學習到每個用戶的超平面.

在Ym×n中,如果某個用戶未對某一項目進行評分,令其對應位置元素為0,即yij=0,則觀測集可以用Ω={(i,j)|yij≠0,?yij∈Ym×n}來表示,它是有評分的用戶和項目對的集合.令X=UVT,表示經(jīng)過分類學習重構后得到的評分矩陣,為保證用戶對每個項目的分類盡量準確,對任意的(i,j)∈Ω,需要令yij和xij同號,即yijxij>0.但是當xij=0時,無法判斷用戶對項目的喜好,因此還需要加入硬間隔為1的約束,即yijxij>1,使得xij盡量不為0.

為了衡量分解的好壞,需要構造一個損失函數(shù)h(·),當分解效果越好時,函數(shù)h(·)的值盡量越小.當yijxij>1時,分解效果最佳,所以函數(shù)h(·)必須滿足h(yijxij)=0這個條件;而當0

(5)

然而這種分類器將用戶i的超平面定為UixT=0,該超平面必經(jīng)過k維空間中的原點(0,…,0)T,但有時經(jīng)過原點的超平面并不具有最好的分類效果.圖1是支持向量機中兩個不同的分類器L1和L2對二維數(shù)據(jù)的分類情況,L1經(jīng)過了原點,而L2沒經(jīng)過原點,從圖中可以看出分類器L1對樣本數(shù)據(jù)的分類結果沒有L2的效果好.這說明經(jīng)過原點的分類器并不一定是最優(yōu)的.

圖1 不同超平面分類器下分類結果Fig.1 Classification results under different hyperplane

因此對每個用戶的超平面進行一定的偏倚量γ,將用戶i的超平面定為UixT+γi=0,其中Ui和γi共同決定用戶i的超平面,需要根據(jù)已觀測的數(shù)據(jù)對Ui和γi進行學習.對任意的(i,j)∈Ω,不再是令yijxij>0,而是令yij(xij-γi)>0.同時任然保持最大間隔的約束,即yij(xij-γi)>1,損失函數(shù)采用hinge函數(shù),則整體的損失函數(shù)l(·)為

(6)

同時為了防止模型的過擬合,正則化函數(shù)中還應該加入γi的正則約束,即

(7)

其中γ=(γ1,…,γm)T.則矩陣分解問題的目標函數(shù)為:

(8)

最終將矩陣Y分解成U,V,γ三部分.由于hinge損失函數(shù)在每個點處可導,正則函數(shù)也可導,所以可以用最速梯度下降法對該優(yōu)化問題進行求解,其中目標函數(shù)J對Uip、Vjp、γi的導數(shù)分別為:

(9)

(10)

(11)

則可以用交替優(yōu)化的方法分別更新U、V和γ,其中每個元素的迭代公式分別為:

(12)

(13)

(14)

其中c為迭代步長.

當上述最優(yōu)化問題求得近似解U,V,γ后,根據(jù)以下分段函數(shù)對二值評分矩陣進行預測:

(15)

5 多值矩陣的分層填充

多值評分矩陣填充問題可以看成一個多分類問題,目前解決多分類問題的方法主要有兩種,一種是直接構造一個多分類目標函數(shù),建立一個多分類器;另一種是將多分類問題拆解為若干個二分類問題,建立多個二分類器,然后將二分類的結果進行組合.

N.Srebro提出的FastMMMF[5]是通過構造多分類目標函數(shù)來解決多值評分矩陣預測問題,雖然該方法比其他類似的方法效果要好,但是同一個用戶具有多個平行的超平面來分類,當超平面間的間隔較小時,這種分類的方法不能保留最大間隔這一特性.而Vikas Kumar提出的分層矩陣分解(HMF)[1]則是多次對二值評分矩陣進行分解,逐次對評分進行預測,從而完成多值矩陣的填充.下面介紹采用上節(jié)中提出的改進的最大間隔二值矩陣分解方法和HMF方法完成多值矩陣的分層填充.

(16)

(17)

本文提出的解決多值矩陣的分層填充方法如表1中的算法所示,并且在下節(jié)中在真實數(shù)據(jù)集上驗證了算法的有效性.

表1 算法偽代碼
Table 1 Algorithm pseudo code

算法1.帶偏倚最大間隔二值矩陣分解對多值矩陣分層填充算法輸入:觀測的數(shù)據(jù)矩陣Y,潛因子個數(shù)k,正則系數(shù)λ輸出:填充后的數(shù)據(jù)矩陣^Y1 for q=1 to R-12 根據(jù)公式(16)計算Yq3 初始化Uq,Vq,γq4 do5 交替優(yōu)化根據(jù)公式(12)更新Uq6 交替優(yōu)化根據(jù)公式(13)更新Vq7 交替優(yōu)化根據(jù)公式(14)跟新γq8 until J收斂9 根據(jù)公式(15)計算^Yq10 根據(jù)公式(16)預測^yij=q的元素位置11 end12 根據(jù)公式(16)預測^yij=R的元素位置13 返回矩陣^Y

6 實驗及分析

為了驗證基于改進的最大間隔二值矩陣分解的多值矩陣填充方法對于多值評分矩陣預測的有效性,本文在Movielens 1M數(shù)據(jù)集上進行數(shù)據(jù)實驗.其中Movielens 1M包含了6040個用戶對3952個電影的累計1000209個評分,評分的取值為{1,2,3,4,5},其中3706個電影有用戶評論,并且每個用戶最少評論了20個電影.

圖2 不同λ值對應的ZOE值對比Fig.2 Different ZOE values for different λ

6.1 關于正則系數(shù)λ的選取研究

λ的取值對矩陣分解問題至關重要,適當?shù)摩酥悼梢苑乐鼓Ｐ瓦^擬合.本文在進行矩陣分解時所有步驟的λ均相同,為了得到最合適的λ值,本文在二值矩陣Y3上進行實驗,從Y3非0元素中隨機選取20%作為測試集,剩余的作為訓練集,計算每一個λ對應模型的ZOE值,其中ZOE值表示預測的錯誤率,其計算公式如下所示:

(18)

(19)

6.2 本文方法與其他方法的MAE值比較

本實驗采用矩陣分解領域中常用的兩種實驗方法:弱泛化與強泛化來檢驗本文方法的有效性.

弱泛化實驗:先隨機選取5000個用戶的所有評分數(shù)據(jù),再從該評分數(shù)據(jù)集中隨機選取20%的元素作為測試集,將剩下的80%的元素作為訓練集,然后用訓練集中的元素對模型進行訓練,當模型訓練好后,再對測試集中的元素進行預測,并與測試集中的真實評分結果進行比較.

強泛化實驗:分為兩個步驟,第一步隨機選取5000個用戶的評分數(shù)據(jù),用于訓練初始預測模型,第二步將剩余用戶的數(shù)據(jù)作為測試集,再從測試集中隨機選取20%的評分元素組成集合H,剩余的組成集合G,將訓練好的初始模型在G上稍作調整,然后對H中的元素進行預測,并與H中的真實評分結果進行比較.

本實驗選取的評價指標為平均絕對誤差MAE,它用來衡量預測評分與真實評分之間的偏差,MAE值越小表示預測結果越好,其計算公式如下所示:

(20)

其中Ω1為測試集.本文與目前最新的方法進行了比較,參與比較的算法有URP[20]、Attitude[20]、Fast MMMF[5]、E-MMMF[7]、PMF[21]、BPMF[22]、GP-LVM[23]、iPMMMF & iBPMMMF[9]、Gibbs MMMF & iBPMMMF[10]和HMF[1],同時為了方便比較,將每個算法得到的MAE值同除以1.6[1].

表2 不同算法的MAE值比較
Table 2 Different MAE in different algorithm

算法弱泛化強泛化URP0.4341±0.00230.4444±0.0032Attitude0.4320±0.00550.4375±0.0028Fast MMMF0.4156±0.00370.4203±0.0138E-MMMF0.4029±0.00270.4071±0.0093PMF0.4332±0.00330.4413±0.0074BPMF0.4235±0.00230.4450±0.0085GP-LVM0.4026±0.00200.3994±0.0145iPMMMF & iBPMMMF0.4031±0.00300.4089±0.0145Gibbs MMMF & iPMMMF0.4037±0.00050.4040±0.0055HMF0.4019±0.00440.4032±0.0022本文方法0.4005±0.00140.3986±0.0085

在實驗過程中所有算法的潛因子個數(shù)都取為100,將弱泛化和強泛化分別進行三次實驗,取三次實驗結果中的MAE的最大值和最小值作為實驗結果,得到本文方法以及其他方法的MAE值見表2.

從表2中可以看出,本文的方法在Movielens 1M數(shù)據(jù)集上,無論是弱泛化實驗還是強泛化實驗,MAE均值都小于其他方法,表明本文方法對評分矩陣預測的準確率都要比其他方法略高,驗證了本文方法的有效性.

6.3 關于潛因子個數(shù)的分析

潛因子個數(shù)k的取值對評分矩陣預測的準確率有著重要影響,當k取值較小時,特征空間維數(shù)較小,不能完整表達出用戶和項目的信息;當k值較大時,進行矩陣分解的計算復雜度成幾何倍數(shù)增長,影響矩陣分解求解.為了確定本文方法中k的取值的影響程度,本文在數(shù)據(jù)集Movielens 100K上進行實驗.Movielens 100K數(shù)據(jù)集包含了943個用戶對1682個電影的累計100000個評分,評分的取值為{1,2,3,4,5},且每個用戶最少評論了20個電影.

圖3 不同k值下的MAE值比較Fig.3 Different MAE with different k

在實驗中隨機選取80%的評分數(shù)據(jù)作為訓練集,剩余20%作為測試集,計算不同k值下,取最優(yōu)的λ值時所對應的MAE值,同時計算Fast MMMF和HMF方法下的MAE值與之比較,其中k的取值為{30,40,50,60,70,80,90,100},得到不同k值下三種方法的MAE值對比圖,見圖3.

從圖3中可以看出,當k值減小時,Fast MMMF的MAE值變化非常巨大,表明Fast MMMF方法中特征表示空間維數(shù)很大,不利于算法的擴展性;HMF的MAE值變化比較平緩,在較適中的特征空間中可以進行問題求解;而本文提出的方法的MAE值基本上無變化,表明本文方法在較小的特征空間中就能夠完成問題求解,且具有較高的分解效果.因此本文的方法可以保證在不降低準確率的情形下進一步減少潛因子個數(shù),從而提高矩陣填充的速度.

7 總結與展望

本文對傳統(tǒng)的最大間隔二值矩陣分解方法進行了改進,并將其運用到多值評分矩陣的填充問題,實驗表明,本文提出的方法對多值評分矩陣預測的準確率優(yōu)于其他方法,同時本文提出的方法能夠將矩陣分解在一個較低維度特征空間中進行,能在保證預測準確率基本不變的前提下,提高矩陣分解速度,并大幅減少計算過程中的空間占用.

本文提出的方法在進行多次二值矩陣分解時,采用了相同的正則系數(shù)λ和潛因子個數(shù)k,這可能會導致這兩個模型參數(shù)不能夠很好適應不同步驟下的評分矩陣.在今后的工作中我們可以對每次二值矩陣分解單獨學習這兩個模型參數(shù),以加強矩陣填充的準確率.另一方面,本文提出的方法沒有考慮數(shù)據(jù)的均衡性,在分類問題中,不同類別樣本數(shù)據(jù)的不均衡可能會引起分類器更加偏向于某一類,從而導致分類器不能很好地適應新數(shù)據(jù),出現(xiàn)大量的錯分類的情況.在未來的工作中,我們會對這一類問題進行研究,使得模型有更好的魯棒性,能夠不受數(shù)據(jù)不均衡性的影響.