融合因子分解的上下文推薦算法研究?

喬 雨 圣文順

（南京工業(yè)大學(xué)浦江學(xué)院 南京 211200）

1 引言

傳統(tǒng)的推薦系統(tǒng)通常只考慮用戶(hù)本身的行為信息和待項(xiàng)目的基本信息，而隨著互聯(lián)網(wǎng)的發(fā)展，各類(lèi)信息量都呈快速增長(zhǎng)狀態(tài)，利用單一的“用戶(hù)-項(xiàng)目”信息產(chǎn)生推薦已經(jīng)不能夠滿(mǎn)足用戶(hù)的需求［1］。因此，為了使推薦系統(tǒng)更好地發(fā)揮其信息過(guò)濾的作用，精準(zhǔn)地定位用戶(hù)感興趣的點(diǎn)，融合上下文情景的推薦系統(tǒng)應(yīng)運(yùn)而生［2～3］，即推薦系統(tǒng)中除了要考慮基本的“用戶(hù)-項(xiàng)目”二元信息外，還需要實(shí)際應(yīng)用場(chǎng)景中所處的上下文狀態(tài)信息對(duì)推薦結(jié)果的影響?；谏舷挛那榫车耐扑]系統(tǒng)的實(shí)現(xiàn)原理是：根據(jù)收集到的用戶(hù)基本信息、評(píng)分信息、上下文情景等信息，進(jìn)行“用戶(hù)-項(xiàng)目-上下文信息”三維信息的挖掘，來(lái)分析出用戶(hù)可能的興趣點(diǎn)，并給出對(duì)應(yīng)的推薦結(jié)果。

2 相關(guān)技術(shù)介紹

2.1 奇異值分解

在需要考慮上下文信息的推薦系統(tǒng)中，常用奇異值分解［4］（Singular value decomposition，SVD）技術(shù)來(lái)對(duì)用戶(hù)行為信息矩陣進(jìn)行分解，實(shí)現(xiàn)高維度矩陣的降維，但是這樣的奇異值分解技術(shù)在應(yīng)用中會(huì)面臨由于矩陣過(guò)于稀疏（稀疏性達(dá)到95%以上）需要填充的數(shù)據(jù)量過(guò)于龐大，并且數(shù)據(jù)難以得到有效存儲(chǔ)的問(wèn)題［5］；其次，該問(wèn)題也會(huì)導(dǎo)致該方法無(wú)法適應(yīng)互聯(lián)網(wǎng)背景下的大數(shù)據(jù)級(jí)別的應(yīng)用場(chǎng)景；再者，奇異值分解技術(shù)在利用Spark等工具進(jìn)行訓(xùn)練時(shí)，存在著數(shù)據(jù)利用率不足的情況。因此，對(duì)于融合多維上下文情景的推薦系統(tǒng)，奇異值分解的方法顯得過(guò)于繁重。

2.2 多項(xiàng)式回歸

多項(xiàng)式回歸（Polynomial Regression）被應(yīng)用到推薦算法中，是能夠利用其線(xiàn)性回歸的特征來(lái)彌補(bǔ)奇異值分解技術(shù)的劣勢(shì)，利用因變量與自變量之間的相互作用［6］，將上下文信息用線(xiàn)性關(guān)系進(jìn)行表示，避免由于數(shù)據(jù)矩陣過(guò)于龐大而導(dǎo)致的存儲(chǔ)和計(jì)算效率問(wèn)題。但是另一方面，多項(xiàng)式回歸為了盡可能地?cái)M合數(shù)據(jù)，采用增加高次自變量的方式來(lái)對(duì)訓(xùn)練數(shù)據(jù)集進(jìn)行逼近，容易形成過(guò)度擬合［7］，進(jìn)而帶來(lái)訓(xùn)練不準(zhǔn)確的問(wèn)題。

本文對(duì)多項(xiàng)式回歸算法進(jìn)行了深入的研究，針對(duì)其存在的計(jì)算復(fù)雜度較高的問(wèn)題進(jìn)行分析并嘗試著改進(jìn)，提出了融合因子分解的上下文推薦算法（Context-aware Recommendation based on Factoriza?tion Machines，F(xiàn)M-CR），該算法利用因子分解的方式將多項(xiàng)式回歸中變量之間的相互作用進(jìn)行分解［8］，進(jìn)而達(dá)到降低計(jì)算復(fù)雜度的目的。式（1）給出了二階因子分解模型，其中w0∈R，v∈Rn×k，n×k表示整體數(shù)據(jù)維度；參數(shù)w0，wi和vi是模型經(jīng)過(guò)訓(xùn)練學(xué)習(xí)得出的［7］；式（2）為引入的損失函數(shù)，用來(lái)防止過(guò)度擬合。

3 FM-CR算法介紹與分析

3.1 FM-CR算法步驟

基于上下文情景的推薦在考慮基本的用戶(hù)行為信息外，還需要盡可能地考慮用戶(hù)所處的實(shí)時(shí)狀態(tài)信息［9～10］，本文提出的FM-CR算法可描述為三個(gè)核心步驟。

步驟1：確定上下文特征信息

在含有上下文信息的推薦系統(tǒng)中，由于包含了除用戶(hù)、項(xiàng)目之外的多種有關(guān)上下文情景的信息，因此將預(yù)測(cè)評(píng)分用式（3）表示：

值得說(shuō)明的是，式（3）中的上下文屬性下標(biāo)是從3開(kāi)始的，這是因?yàn)閷ⅰ坝脩?hù)”和“項(xiàng)目”分別看成了“上下文”特征信息中的第1項(xiàng)和第2項(xiàng)［11］，達(dá)到統(tǒng)一數(shù)據(jù)格式的目的。其他的上下文信息，如用戶(hù)所處的時(shí)間、心情等屬性都可以根據(jù)系統(tǒng)需要作為“上下文”輸入到推薦算法中進(jìn)行訓(xùn)練，以電影推薦系統(tǒng)為例，納入用戶(hù)的觀(guān)影項(xiàng)目I=｛movie1，mov?ie2，movie3｝、觀(guān)影心情C3=｛happy，sad，normal｝、觀(guān)影 地 址C4=｛p1，p2，p3｝、觀(guān) 影 同 伴C5=｛friend1，friend2，friend3｝這四類(lèi)因素來(lái)組成用戶(hù)所處的上下文情境。

步驟2：抽象上下文信息的特征向量

基于步驟1所述，將各“上下文信息”抽象為特征向量z進(jìn)行表示，此向量z包含了5個(gè)特征信息，分別是用戶(hù)、項(xiàng)目、心情、地點(diǎn)和同伴。例如，用戶(hù)u1與f3在心情愉快的情況下，于p2地看了電影mov?ie3，并且給了5分的評(píng)價(jià)；那么電影項(xiàng)目向量表示為z（2movie）=（0，0，1），心情向量可表示成z（3hap?py）=（1，0，0），地址向量可表示為z（4p2）=（0，1，0），同伴向量表示為z（5friend3）=（0，0，1）。因此，用戶(hù)u1的上下文信息向量如式（4）所示，綜合評(píng)分矩陣如式（5）所示。

另一種情況，若u1是與同伴friend2和friend3一起觀(guān)看的電影movie3，那么這里的同伴向量可以表示為z（5｛friend2，friend3｝）=（0，0.5，0.5），這是因?yàn)楫?dāng)某一“上下文”是分類(lèi)變量的集合時(shí)，就將該信息進(jìn)行歸一化處理，使得此分類(lèi)向量的權(quán)值總和為1?；趯?duì)這兩種情況，最終的特征信息可以通過(guò)連接映射成如式（6）所示的向量x。

步驟3：通過(guò)預(yù)測(cè)產(chǎn)生目標(biāo)推薦

確定好信息特征向量后，將向量數(shù)據(jù)輸入到libFM工具中進(jìn)行參數(shù)的訓(xùn)練。libFM是一款用來(lái)訓(xùn)練數(shù)據(jù)的開(kāi)源工具，利用它可以快速地實(shí)現(xiàn)參數(shù)的學(xué)習(xí)和評(píng)分預(yù)測(cè)［12］，信息特征向量中的行表示一個(gè)實(shí)例，“1”表示特征值存在，“0”表示特征值不存在。本實(shí)驗(yàn)采用libFM中的隨機(jī)梯度下降算法進(jìn)行實(shí)驗(yàn)數(shù)據(jù)的訓(xùn)練。訓(xùn)練過(guò)程如式（7）所示，其中參數(shù)（x，y）是樣本中的數(shù)據(jù)；μ∈R指迭代的學(xué)習(xí)效率，并且μ的取值要適中來(lái)避免造成模型無(wú)法收斂或者收斂速度過(guò)慢的情況；γθ表示正則化系數(shù)，它是經(jīng)過(guò)實(shí)驗(yàn)確定的，并且θ和γ通常取相同的值。此時(shí)基于因子分解模型（如式（1）所示）的過(guò)程可將評(píng)分預(yù)測(cè)表示為式（8）。

3.2 FM-CR算法時(shí)間復(fù)雜度分析

在傳統(tǒng)的推薦系統(tǒng)中，若采用多項(xiàng)式回歸進(jìn)行學(xué)習(xí)，考慮特征數(shù)量為k，上下文因素的維數(shù)n，則需要學(xué)習(xí)的參數(shù)量為k（k-1）/2［13］；而因式分解模型需要學(xué)習(xí)的參數(shù)量為k×n，并且上下文影響因素的維度n通常情況下是遠(yuǎn)低于特征數(shù)量k的，因此可認(rèn)為該方法的一次完整迭代時(shí)間復(fù)雜度為O（nk）。

4.1 實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)數(shù)據(jù)

1）實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)環(huán)境是基于虛擬機(jī)VMWare10中的Ubun?tu操作系統(tǒng)，利用libFM軟件中提供的SGD方法對(duì)數(shù)據(jù)進(jìn)行學(xué)習(xí)訓(xùn)練，產(chǎn)生實(shí)驗(yàn)結(jié)果。

2）實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)采用由新浪提供的在線(xiàn)測(cè)評(píng)數(shù)據(jù)集，是目前公開(kāi)的大規(guī)模數(shù)據(jù)集之一，通常用于用戶(hù)社交關(guān)系的推薦研究。該數(shù)據(jù)集包含2300000位用戶(hù)，6000個(gè)項(xiàng)目，108000000條數(shù)據(jù)記錄，分為用戶(hù)基本信息、用戶(hù)關(guān)注的信息、關(guān)鍵詞信息、行為信息、待推薦信息等［6］。

4.2 實(shí)驗(yàn)結(jié)果分析

1）準(zhǔn)確度分析

本實(shí)驗(yàn)采用平均準(zhǔn)確率MAP（Mean Average Precision）指標(biāo)來(lái)衡量推薦的準(zhǔn)確度，該指標(biāo)體現(xiàn)了所推薦的結(jié)果中被用戶(hù)接納的比例［14～15］。計(jì)算方式如式（9）所示，式中N表示推薦列表中的項(xiàng)目數(shù)，這里取值為5，表示推薦列表中有5個(gè)項(xiàng)目，并計(jì)算出整體的平均準(zhǔn)確率。n表示待推薦的項(xiàng)目集合，則ap@n表示用戶(hù)對(duì)于推薦系統(tǒng)的總體接受程度，ap@ni表示用戶(hù)對(duì)推薦集合n中第i個(gè)推薦對(duì)象的接受度，采用ap@ni=（i-1）/i的計(jì)算方式，表示待推薦項(xiàng)目集合n中的前i項(xiàng)均被用戶(hù)考慮并且存在實(shí)際的接受項(xiàng)目；需要注意的是，當(dāng)推薦列表中的第1項(xiàng)（即i=1時(shí)）就被用戶(hù)接受時(shí)，此時(shí)ap@n1=1/1=100%。

例如，在5個(gè)待推薦的候選項(xiàng)目中用戶(hù)實(shí)際接受了兩個(gè)，分別是第1、4個(gè)，那么ap@5=（1/1+3/4）/5=0.35，即可認(rèn)為用戶(hù)對(duì)于當(dāng)前的推薦結(jié)果接受度為35%；以此類(lèi)推，當(dāng)計(jì)算出所有用戶(hù)的MAP值后，就可得出系統(tǒng)的整體推薦準(zhǔn)確度，如式（10）所示。當(dāng)整體的MAP值越大時(shí)，表示推薦的項(xiàng)目被用戶(hù)接受的程度就越高，系統(tǒng)的推薦就越有效。

在將各上下文信息作為整體考慮的情況下，分別確定用戶(hù)所具有的各類(lèi)屬性信息所占的權(quán)值。具體做法是：首先，通過(guò)交叉驗(yàn)證的方式計(jì)算出各個(gè)用戶(hù)特征的權(quán)重，在本實(shí)驗(yàn)中是選取了用戶(hù)的鄰居數(shù)f1、用戶(hù)的粉絲數(shù)f2、用戶(hù)所處的上下文情景f3作為特征信息。其次，利用線(xiàn)性疊加的形式（式（11））得出用戶(hù)的偏置參數(shù)B［16］，其中fi表示特征i，θi表示特征fi所占的權(quán)重。

本文在基于上下文屬性的影響程度的基礎(chǔ)上，將結(jié)合因子分解的推薦算法與多項(xiàng)式推薦進(jìn)行精確度比較，以此驗(yàn)證算法的有效性，比較結(jié)果如圖1所示。從圖中可看出基于多項(xiàng)式回歸的推薦算法與本文提出的融合因子分解的推薦算法在推薦準(zhǔn)確度方面差距不是很大，峰值出現(xiàn)在θ3取值為0.5（即“上下文”特征信息的權(quán)值為0.5）時(shí)，兩者的MAP值相差最大，但是差值小于0.05；因此也可認(rèn)為融合因子分解的推薦算法在考慮上下文特征信息的推薦精確度上基本與多項(xiàng)式回歸的推薦算法相持平。

2）時(shí)間復(fù)雜度比較

本實(shí)驗(yàn)將融合因子分解的上下文推薦算法分別與基于奇異值分解的推薦算法和基于多項(xiàng)式回歸的推薦算法在時(shí)間運(yùn)行方面進(jìn)行比較，結(jié)果分別如圖2和圖3所示。從圖2中可以看出基于奇異值分解的推薦算法在耗時(shí)上明顯高于本文提出的FM-CR算法，這是因?yàn)槠娈愔捣纸夥椒▽?duì)于矩陣數(shù)據(jù)的訓(xùn)練需要大量的時(shí)間；而圖3中FM-CR算法與基于多項(xiàng)式分解的算法在運(yùn)行時(shí)間的差距上就相對(duì)縮小了很多，尤其是在上下文屬性維度小于3時(shí)兩者的差距并不明顯，當(dāng)屬性維度大于3時(shí)，運(yùn)行時(shí)間上才有了較為明顯的差距。因此可以得出，當(dāng)推薦算法中考慮的屬性維度達(dá)到一定程度的時(shí)候，融合因子分解的推薦算法運(yùn)行效率上較優(yōu)于基于多項(xiàng)式回歸的推薦算法。

圖1 融合因子分解的推薦算法與多項(xiàng)式回歸推薦算法的準(zhǔn)確度比較

圖2 融合因子分解的推薦算法與基于奇異值分解的推薦算法運(yùn)行時(shí)間比較

圖3 融合因子分解的推薦算法與基于多項(xiàng)式回歸的推薦算法運(yùn)行時(shí)間比較

5 結(jié)語(yǔ)

本文針對(duì)包含上下文信息的推薦系統(tǒng)進(jìn)行了調(diào)研和研究，通過(guò)分析上下文情景推薦中常用的奇異值分解技術(shù)和多項(xiàng)式分解技術(shù)的特點(diǎn)與過(guò)程，針對(duì)其存在的問(wèn)題進(jìn)行新技術(shù)的嘗試，提出了融合因子分解技術(shù)的推薦算法，并設(shè)計(jì)了驗(yàn)證用戶(hù)對(duì)于推薦結(jié)果接受率和算法運(yùn)行時(shí)間的實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明該算法具有一定的有效性，并且在時(shí)間復(fù)雜度方面有了較為明顯的改善。未來(lái)的研究工作中，縱向上可以在此基礎(chǔ)上繼續(xù)研究不同的上下文特征信息對(duì)推薦結(jié)果準(zhǔn)確性的影響程度，研究是否可以抽象出相關(guān)的規(guī)則來(lái)覆蓋多種場(chǎng)景；其次，在時(shí)間效率方面，可以采用不同的數(shù)據(jù)處理平臺(tái)，橫向?qū)Ρ人惴ǖ男阅茏兓卣?，進(jìn)一步提升算法處理的效率。