基于增量矩陣分解的協(xié)同過(guò)濾推薦模型研究

樊艷清，李明智，紀(jì)佳琪

（1.河北民族師范學(xué)院信息中心，承德 067000；2.河北民族師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，承德 067000）

0 引言

大數(shù)據(jù)時(shí)代，推薦系統(tǒng)可以幫助用戶從海量信息中選擇自身感興趣的物品。在眾多推薦模型中，協(xié)同過(guò)濾以其簡(jiǎn)單性及有效性得到了廣泛的應(yīng)用[1]。協(xié)同過(guò)濾模型通過(guò)對(duì)代表用戶喜好程度的“用戶-物品”評(píng)分矩陣進(jìn)行建模，然后計(jì)算填充該矩陣中的缺失數(shù)據(jù)，最后對(duì)這些數(shù)據(jù)進(jìn)行排行并取出前N條作為推薦結(jié)果。在建模中使用的“用戶-評(píng)分”矩陣可以分為2類(lèi)：顯示數(shù)據(jù)和隱式數(shù)據(jù)。推薦系統(tǒng)的任務(wù)也可以分為2類(lèi)[2]：評(píng)分預(yù)測(cè)和Top-N推薦。在評(píng)分預(yù)測(cè)任務(wù)中，一般使用顯示數(shù)據(jù)，對(duì)用戶評(píng)分矩陣中的未知數(shù)據(jù)進(jìn)行評(píng)分的預(yù)測(cè)，因此該任務(wù)可以轉(zhuǎn)換為回歸任務(wù)。然而收集用戶的評(píng)分?jǐn)?shù)據(jù)是十分困難的并且是稀疏的，因此很多場(chǎng)景會(huì)使用隱式數(shù)據(jù)。相對(duì)于顯示數(shù)據(jù)隱式數(shù)據(jù)更好獲取，如用戶的點(diǎn)擊、收藏、購(gòu)買(mǎi)等都可以看成隱式數(shù)據(jù)。在這種情況下，“用戶-物品”評(píng)分矩陣中存儲(chǔ)的并不是用戶對(duì)物品的評(píng)分，而是1或0值，分別表示用戶對(duì)物品有行為和無(wú)行為，此時(shí)推薦任務(wù)可以轉(zhuǎn)換成一個(gè)二分類(lèi)任務(wù)。

本文主要使用隱式數(shù)據(jù)解決Top-N推薦問(wèn)題。在之前的研究中，一般都是獲取到全部訓(xùn)練數(shù)據(jù)，然后設(shè)計(jì)推薦模型[3]。這樣的模型對(duì)于用戶興趣改變不大或物品變化不大的場(chǎng)景下比較適用，然而對(duì)于一些場(chǎng)景并不適用：如音樂(lè)或電影，用戶會(huì)隨著時(shí)間遷移，其喜好的類(lèi)型會(huì)變化；再如新聞，其更新速度較快，用戶關(guān)注點(diǎn)變化也會(huì)較快。因此本文不再使用固定數(shù)據(jù)訓(xùn)練模型，而是把數(shù)據(jù)看成數(shù)據(jù)流，是隨著時(shí)間的流逝不斷進(jìn)入到模型中的，模型要能實(shí)時(shí)處理這些進(jìn)入的數(shù)據(jù)并對(duì)其進(jìn)行訓(xùn)練，同時(shí)實(shí)時(shí)地更新模型。這類(lèi)模型稱為增量模型，在數(shù)據(jù)進(jìn)入時(shí)使用矩陣分解方法，因此本文提出的模型稱為增量矩陣分解的協(xié)同過(guò)濾推薦模型。

1 相關(guān)工作

在推薦系統(tǒng)初期，由于Netflix[4]競(jìng)賽的盛行，研究者提出了眾多基于矩陣分解的推薦算法，這類(lèi)算法無(wú)論在推薦性能上還是時(shí)間復(fù)雜度上都優(yōu)于其他類(lèi)型的推薦算法。矩陣分解思想最初來(lái)源于信息檢索領(lǐng)域的隱語(yǔ)義索引（Latent Semantic Indexing，LSI）[5]方法，LSI使用了奇異值分解（Singular Value Decomposition，SVD）[6]算法對(duì)“文檔-詞”矩陣進(jìn)行分解。在推薦系統(tǒng)領(lǐng)域，矩陣分解（Matrix Factorization，MF）[7]算法借鑒了上述思想，通過(guò)對(duì)“用戶-物品”評(píng)分矩陣進(jìn)行分解，使得可以用一個(gè)隱空間來(lái)表示用戶和物品。假設(shè)用R表示評(píng)分矩陣，P和Q表示分解后的隱空間，即P表示用戶隱空間，Q表示物品隱空間。Pu表示P矩陣中的一行即用戶隱向量，Qi表示Q矩陣中的一列即物品隱向量，表示對(duì)矩陣R中u行和i列即用戶u對(duì)物品i的預(yù)測(cè)評(píng)分。此時(shí)推薦問(wèn)題可以轉(zhuǎn)化為公式的優(yōu)化問(wèn)題。

其中T表示訓(xùn)練數(shù)據(jù)，即用戶對(duì)物品的評(píng)分?jǐn)?shù)據(jù)，λ是正則化參數(shù)，||Pu||2+||Qi||2是正則化項(xiàng)用來(lái)避免過(guò)擬合問(wèn)題。接下來(lái)可以使用梯度下降法（Stochastic Gradient Descent，SGD）對(duì)該模型進(jìn)行優(yōu)化。對(duì)于給定的訓(xùn)練元組，可以計(jì)算預(yù)測(cè)值與真實(shí)值的誤差errui=Rui-，然后可以使用公式進(jìn)行模型優(yōu)化求解。

對(duì)于矩陣分解模型的算法描述如算法1所示。

算法1：矩陣分解模型算法

輸入：T=，k，iters，λ，η

輸出：P，Q

1. for u Users(T):

2.Pu←Vector∈Rk

3. 取值范圍為（0,1）

4. for i∈Items(T):

5.Qi←Vector∈Rk

6. 取值范圍為（0,1）

7. for count in 1 to iters:

8. forin T:

上述算法是矩陣模型的基本算法，其中T為輸入的訓(xùn)練數(shù)據(jù)，k為隱空間的維度，iters為算法的迭代次數(shù)，λ為正則化參數(shù)，η為學(xué)習(xí)率。

2 基于增量矩陣分解的協(xié)同過(guò)濾推薦模型

在上一節(jié)描述的矩陣分解模型中，訓(xùn)練數(shù)據(jù)是固定，當(dāng)有新增數(shù)據(jù)時(shí)必須從新啟動(dòng)模型的訓(xùn)練，無(wú)法適應(yīng)流式數(shù)據(jù)，即無(wú)法完成在線訓(xùn)練和實(shí)時(shí)更新。為了解決這個(gè)問(wèn)題，本文提出了一種增量矩陣分解的協(xié)同過(guò)濾算法，該模型可以適應(yīng)流式數(shù)據(jù)。即當(dāng)有新數(shù)據(jù)到來(lái)時(shí)，不必從新訓(xùn)練整個(gè)模型，而是基于當(dāng)前數(shù)據(jù)在已有模型基礎(chǔ)上訓(xùn)練并實(shí)時(shí)更新模型。其算法如算法2所示。

算法2：基于增量矩陣分解的協(xié)同過(guò)濾

輸入：流式數(shù)據(jù) T=，k，iters，λ，η

輸出：P，Q

1.forin T:

2.if u?Rows(P):

3.Pu←Vector∈Rk

4.Pu取值范圍為（0,1）

5.if i?Rows(QT):

6.Qi←Vector∈Rk

7.Qi取值范圍為（0,1）

從算法2可見(jiàn)，該模型是一種增量更新方式，當(dāng)有新的觀測(cè)數(shù)據(jù)到來(lái)時(shí)就對(duì)P和Q進(jìn)行實(shí)時(shí)更新。盡管形式上與矩陣分解模型相似，但是其區(qū)別也很明顯。首先，當(dāng)有新數(shù)據(jù)到來(lái)時(shí)只對(duì)當(dāng)前數(shù)據(jù)迭代一次，然后就更新參數(shù)P和Q。當(dāng)然當(dāng)有新數(shù)據(jù)到來(lái)時(shí)對(duì)當(dāng)前數(shù)據(jù)迭代n次也是可以的，這樣可以獲得相對(duì)更好的精度，但是考慮到迭代次數(shù)越多消耗的時(shí)間越長(zhǎng)，而本模型要適應(yīng)實(shí)時(shí)在線更新，因此權(quán)衡時(shí)間和精度等因素后本文還是采用迭代一次的方案，舍棄一點(diǎn)精度的損失來(lái)?yè)Q取時(shí)間上的減少。其次，該模型可以是已經(jīng)經(jīng)過(guò)預(yù)訓(xùn)練的，即利用之前已有的訓(xùn)練數(shù)據(jù)做一次全量訓(xùn)練（利用算法1），然后再做增量訓(xùn)練（利用算法2）。

算法2中使用的數(shù)據(jù)為隱式數(shù)據(jù)，即評(píng)分矩陣中的數(shù)據(jù)要么為1表示正例，要么為0表示負(fù)例。此時(shí)為0的負(fù)例可能有2層含義：用戶不喜歡該物品和用戶對(duì)該物品還未有過(guò)行為。本文假設(shè)為0的負(fù)例都是用戶對(duì)該物品還未有過(guò)行為。這種假設(shè)的原因是：可以抽取部分負(fù)例參與訓(xùn)練而不是全部參與訓(xùn)練。由于數(shù)據(jù)中只含有0和1，因此誤差的計(jì)算可以使用表示。

當(dāng)?shù)瓿珊螅琑矩陣中的所有位未知項(xiàng)都已計(jì)算完成，此時(shí)分別對(duì)每個(gè)用戶對(duì)物品的預(yù)測(cè)評(píng)分值進(jìn)行降序排序，然后取出前N個(gè)物品作為該用戶的推薦物品。

3 實(shí)驗(yàn)

推薦系統(tǒng)常用的評(píng)價(jià)方法是，把數(shù)據(jù)集隨機(jī)的分成訓(xùn)練集和測(cè)試集，用訓(xùn)練集對(duì)模型進(jìn)行訓(xùn)練，用測(cè)試集對(duì)模型進(jìn)行評(píng)價(jià)[8]。然而本文提出的算法并不能使用上述評(píng)價(jià)方法。主要原因如下：

●數(shù)據(jù)的順序：由于本文提出的模型要適應(yīng)流式數(shù)據(jù)，即數(shù)據(jù)的到來(lái)是有先后順序的，這種順序不能打亂。因此在拆分訓(xùn)練集和測(cè)試集時(shí)，要保證其按時(shí)間的順序性。

●實(shí)時(shí)性：本文提出的模型是一種增量更新的模型，當(dāng)有新的數(shù)據(jù)到來(lái)時(shí)，會(huì)立即使用這個(gè)新數(shù)據(jù)對(duì)已有模型進(jìn)行再訓(xùn)練然后更新模型。

因此，本文使用一種能夠適應(yīng)流式數(shù)據(jù)的評(píng)價(jià)推薦系統(tǒng)的方法。首先，我們先使用部分?jǐn)?shù)據(jù)對(duì)模型進(jìn)行一個(gè)預(yù)訓(xùn)練，形成一個(gè)基本可用的模型。然后按照數(shù)據(jù)生成的時(shí)間順序，分別把數(shù)據(jù)輸入到模型中，然后按照以下步驟進(jìn)行：

（1）如果user是一個(gè)已知用戶（即已經(jīng)在初始訓(xùn)練數(shù)據(jù)集中出現(xiàn)過(guò)的用戶），則使用當(dāng)前模型推薦N個(gè)物品給用戶user，否則進(jìn)入第3步。

（2）對(duì)當(dāng)前的推薦進(jìn)行評(píng)價(jià)的計(jì)算。

（3）用當(dāng)前數(shù)據(jù)重新訓(xùn)練模型并進(jìn)行模型更新。

（4）等待下一個(gè)（批）數(shù)據(jù)的到來(lái)，然后轉(zhuǎn)向1。

3.1 數(shù)據(jù)集

本文使用3個(gè)數(shù)據(jù)集進(jìn)行模型的評(píng)價(jià)，其詳細(xì)描述見(jiàn)表1。所有的數(shù)據(jù)集都會(huì)處理成按時(shí)間順序排列的形式。其中MovieLens①https://movielens.org/是一個(gè)經(jīng)常用于評(píng)價(jià)推薦系統(tǒng)性能的數(shù)據(jù)集，其評(píng)分范圍從1-5并且含有時(shí)間戳信息。Lastfm②https://grouplens.org/datasets/hetrec-2011/是關(guān)于用戶聽(tīng)歌序列的數(shù)據(jù)集，它有兩個(gè)文件，聽(tīng)歌記錄與用戶信息。MovieT-weetings 10k③http://research.yahoo.com/Academic_Relations來(lái)自于Twitter的電影分級(jí)數(shù)據(jù)集，評(píng)分值從1-10。

表1 數(shù)據(jù)集詳情

3.2 結(jié)果分析

本文與 ItemKNN（Item-based Collaborative Filtering）[9-10]和 BPRMF（Bayesian Personlized Ranking Matrix Factorization）[11]2個(gè)基線算法進(jìn)行了對(duì)比。ItemKNN是推薦系統(tǒng)中較早的模型，目前已廣泛用于工業(yè)實(shí)踐，因此與之對(duì)比有一定的實(shí)踐意義。BPRMF是使用矩陣分解方法并取得較好效果的推薦模型，本文也是在其基礎(chǔ)上進(jìn)行了增量更新的改進(jìn)。

本文使用召回率（Recall）和模型更新時(shí)間（Update Time）作為評(píng)價(jià)指標(biāo)。其中Recall@N表示推薦N個(gè)物品時(shí)的召回率。實(shí)驗(yàn)結(jié)果見(jiàn)表2。

表2 實(shí)驗(yàn)結(jié)果

從實(shí)驗(yàn)結(jié)果可以看出，本文提出的模型在更新時(shí)間上明顯快于其他2個(gè)模型，在三個(gè)數(shù)據(jù)集上比排在第二的模型分別快10.8倍、25.4倍和7.1倍。召回率上，本文模型在Lastfm和MovieTweetings 10k數(shù)據(jù)集上明顯高于另外兩個(gè)模型。雖然在MovieLens 1M數(shù)據(jù)集上Recall低于其他兩個(gè)模型，但是差異并非很大，與之相對(duì)，在更新時(shí)間上分別快于其他兩個(gè)模型1639倍和10.8倍。因此綜合看來(lái)，本文提出的模型在增量更新的性能上明顯優(yōu)于其他2個(gè)模型。

4 結(jié)語(yǔ)

目前眾多的推薦模型都是離線完成模型訓(xùn)練然后上線使用，在積累了一定的新數(shù)據(jù)后在離線從新進(jìn)行訓(xùn)練，為了能夠?qū)崟r(shí)更新推薦模型以適應(yīng)在線更新，本文提出了一種基于增量矩陣分解的協(xié)同過(guò)濾模型用于完成Top-N推薦任務(wù)。當(dāng)每次有新數(shù)據(jù)到來(lái)時(shí)就進(jìn)行模型的訓(xùn)練和更新，使得模型能夠?qū)崟r(shí)應(yīng)用。在下一步的工作中，我們將比較更多的數(shù)據(jù)集和更多的基線算法，同時(shí)進(jìn)一步優(yōu)化已有模型。