融合時(shí)序和信任值矩陣的協(xié)同過濾推薦算法

石京京 于敬 賽娜

（達(dá)而觀信息科技（上海）有限公司 產(chǎn)品技術(shù)中心 上海市 201203）

1 引言

隨著移動(dòng)互聯(lián)網(wǎng)和大數(shù)據(jù)技術(shù)的迅猛發(fā)展，人們每天接觸到的信息種類繁多，并且成指數(shù)級(jí)增長(zhǎng)。在信息汪洋中，如何讓用戶高效并且快速地獲取自己感興趣的有價(jià)值信息，成為各大產(chǎn)品設(shè)計(jì)的重中之重事項(xiàng)。用戶獲取信息主要有兩大方式，一是當(dāng)需求比較明確時(shí)通過搜索引擎的方式找到自己感興趣的信息，二是當(dāng)需求不是很明確時(shí)會(huì)通過瀏覽被推薦的信息以篩選自己感興趣的內(nèi)容。雖然搜索引擎在一定程度上緩解了用戶篩選信息的難度，但是在很多場(chǎng)景中，如在線購物、聽音樂、看新聞等等，當(dāng)用戶無法準(zhǔn)確表達(dá)自己的信息關(guān)鍵詞時(shí)，智能推薦系統(tǒng)則顯得尤為重要。推薦系統(tǒng)通過對(duì)用戶與推薦信息的持續(xù)交互行為進(jìn)行分析挖掘，生成用戶畫像，通過推薦算法實(shí)現(xiàn)用戶和信息的精準(zhǔn)匹配，自動(dòng)地從海量信息中篩選出用戶最可能感興趣的信息推薦列表。

實(shí)踐證明推薦系統(tǒng)不僅有效地緩解了信息過載（information overload）問題，也可以很好地應(yīng)對(duì)信息長(zhǎng)尾（long tail）問題，因此一直是工業(yè)界和學(xué)術(shù)界研究的熱點(diǎn)領(lǐng)域。在眾多推薦算法中，協(xié)同過濾推薦算法因其原理簡(jiǎn)單、易于實(shí)現(xiàn)和并行化處理、無監(jiān)督學(xué)習(xí)、具有較好的解釋性等諸多優(yōu)點(diǎn)，在工業(yè)界得到了最廣泛的應(yīng)用，同時(shí)在學(xué)術(shù)界也在通過各種方式不斷地進(jìn)行算法改進(jìn)和優(yōu)化。

基于對(duì)協(xié)同過濾算法的深入研究和分析，結(jié)合推薦場(chǎng)景的數(shù)據(jù)特點(diǎn)，本文提出了一種融合時(shí)序和信任值矩陣分解的協(xié)同過濾推薦方法（SeqTMF）。該方法首先通過引入信任值矩陣表征用戶和物品間的交互行為，在一定程度上緩解了海量行為數(shù)據(jù)稀疏性對(duì)推薦效果生成的不利影響。其次在構(gòu)建信任值矩陣時(shí)融入了時(shí)序性（即用戶對(duì)物品交互行為的先后順序）的考量，從而可以在原有用戶對(duì)物品的評(píng)分矩陣基礎(chǔ)上，進(jìn)一步豐富數(shù)據(jù)的多樣性。同時(shí)分別引入了用戶和物品自身的結(jié)構(gòu)關(guān)系，即分別利用用戶和物品自身之間的內(nèi)在關(guān)聯(lián)關(guān)系以進(jìn)一步地深入刻畫用戶和物品自身的畫像，從而為推薦精準(zhǔn)度提供了可靠保障。實(shí)驗(yàn)結(jié)果表明，本文提出的SeqTMF推薦方法相對(duì)于傳統(tǒng)的協(xié)同過濾推薦方法在RMSE指標(biāo)上明顯的提升。

2 相關(guān)工作

協(xié)同過濾（Collaborative Filtering，CF）根據(jù)用戶-物品評(píng)分矩陣或點(diǎn)擊行為交互矩陣，尋找最近鄰用戶或者物品集合，以預(yù)測(cè)用戶對(duì)未發(fā)生交互行為物品的評(píng)分。目前協(xié)同過濾推薦算法主要分為兩種，分別是基于鄰域的方法和基于模型的方法。而基于鄰域的方法又分為三種，即基于用戶的協(xié)同過濾、基于物品的協(xié)同過濾和混合推薦方法。

與傳統(tǒng)的基于鄰域的協(xié)同過濾推薦算法不同的是，基于模型的協(xié)同過濾推薦算法是結(jié)合用戶對(duì)物品的評(píng)分矩陣進(jìn)行模型的迭代訓(xùn)練，通過不斷優(yōu)化后得到最終的推薦模型，進(jìn)而對(duì)未知物品預(yù)測(cè)用戶可能的評(píng)分并最終生成推薦結(jié)果。當(dāng)前，基于模型的協(xié)同過濾推薦方法主要包括概率相關(guān)模型、聚類模型、潛在因子模型、貝葉斯層面模型等。在概率模型方面，業(yè)界也取得了諸多研究成果。Salakhutdinov等[于2007年提出了概率矩陣分解算法（Probabilistic Matrix Factorization，PMF），利用低維的近似矩陣計(jì)算代替高維矩陣的計(jì)算，降低了計(jì)算的時(shí)間復(fù)雜度，并且優(yōu)化了算力且提升了推薦效果。同時(shí)為解決PMF算法中參數(shù)調(diào)整對(duì)算法的影響，進(jìn)一步提出了貝葉斯概率矩陣分解算法(Bayesian probabilistic matrix factorization，BPMF)，在該算法中使用了馬爾可夫鏈蒙特卡洛算法（Markov Chain Monte Carlo，MCMC）進(jìn)行參數(shù)估計(jì)，實(shí)現(xiàn)了參數(shù)的自動(dòng)化訓(xùn)練，從而進(jìn)一步提升了推薦效果。

圍繞推薦效果持續(xù)優(yōu)化的深入研究，很多研究學(xué)者探索將更多維度的附加信息引入至概率矩陣分解算法中，如社交網(wǎng)絡(luò)信息、物品標(biāo)簽信息、時(shí)序信息等。Jamali等于2010年提出了SocialMF，主要思想是構(gòu)建用戶社交網(wǎng)絡(luò)關(guān)系，并將該關(guān)系應(yīng)用到用戶概率矩陣分解的協(xié)同過濾算法中，不過該方法缺乏了對(duì)產(chǎn)品之間關(guān)聯(lián)性的考慮。Wu L等于2012年提出了TagMF，即將物品標(biāo)簽引入至概率矩陣模型中進(jìn)行推薦效果優(yōu)化，結(jié)果表明該方法對(duì)矩陣分解的推薦精確性有一定的提升。

此外，不少研究學(xué)者也在探索時(shí)序信息的有效應(yīng)用，通過將時(shí)序信息加入至推薦模型中，使得模型可以動(dòng)態(tài)地學(xué)習(xí)到交互數(shù)據(jù)的動(dòng)態(tài)變化，Koren等提出了TimeSVD++，將時(shí)間特征加入到向量中，有效解決了興趣漂移的問題，且在推薦效果中取得不錯(cuò)的效果。孫光福等提出了時(shí)序矩陣分解（SequentialMF）的方法，該方法增加了對(duì)時(shí)序性和物品間的關(guān)聯(lián)性的考量。

在協(xié)同過濾算法的持續(xù)改進(jìn)的研究上，Manuel等將信任定義為商務(wù)環(huán)境中最重要的角色。Jiang等提出的一種基于改進(jìn)的融合用戶信任數(shù)據(jù)和用戶相似度的Slope One算法，解決了傳統(tǒng)的Slope One算法的準(zhǔn)確率低和不信任數(shù)據(jù)的問題。蔡曉娟提出了融合相似度和信任度的協(xié)同過濾算法，引入了信任度至協(xié)同過濾算法中，緩解了數(shù)據(jù)稀疏對(duì)推薦效果的影響。

綜上研究分析，在協(xié)同過濾推薦算法的應(yīng)用以及改進(jìn)上雖然取得了不同程度效果提升的研究成果，但是在實(shí)際應(yīng)用中，協(xié)同過濾推薦算法依然存在著問題有待持續(xù)研究，一是因評(píng)分矩陣的數(shù)據(jù)稀疏導(dǎo)致推薦置信度不高，二是構(gòu)建評(píng)分矩陣時(shí)丟棄了一部分原始數(shù)據(jù)特征，導(dǎo)致推薦過程易忽略用戶和用品的結(jié)構(gòu)關(guān)系，因而影響了推薦準(zhǔn)確率。針對(duì)上述客觀存在的問題，本文提出一種全新的融合時(shí)序和信任值矩陣的協(xié)同過濾算法，以提升推薦精準(zhǔn)度。

3 算法工作

本文提出的融入時(shí)序和信任值矩陣的協(xié)同過濾方法在一定程度上緩解了數(shù)據(jù)稀疏對(duì)效果的影響，并且充分考慮了時(shí)序性對(duì)推薦效果的影響。

首先，傳統(tǒng)的基于矩陣分解的協(xié)同過濾，所構(gòu)建的用戶-用戶相似度矩陣是對(duì)稱的，即sim（用戶A和用戶B的相似度）與sim（用戶B和用戶A的相似度）是相等的。引入了信任值的考慮之后，Trust（用戶A對(duì)用戶B的信任值）未必等同于Trust（用戶B對(duì)用戶A的信任值），則用戶-用戶信任值矩陣不是對(duì)稱矩陣。

其次，根據(jù)用戶的行為序列分別構(gòu)建了融合信任值矩陣的用戶關(guān)系網(wǎng)絡(luò)圖和物品關(guān)系網(wǎng)絡(luò)圖。傳統(tǒng)的用戶關(guān)系圖是一個(gè)無向圖，但在現(xiàn)實(shí)生活中未必如此。比如用戶A為著名人士，而用戶B為普通公民，則很大可能是用戶A對(duì)用戶B的行為影響比較大，而用戶B對(duì)用戶A的影響甚微。結(jié)合實(shí)際情況，構(gòu)建有向的用戶關(guān)系網(wǎng)絡(luò)圖更加貼合實(shí)際情況。

本節(jié)主要介紹算法的整體框架流程、用戶-用戶信任值矩陣和用戶（物品）網(wǎng)絡(luò)關(guān)系圖的構(gòu)建方法以及基于矩陣分解技術(shù)如何預(yù)測(cè)未知推薦物品的評(píng)分。

3.1 算法框架流程

本文提出的SeqTMT方法的整體框架流程圖如圖1所示。該方法的輸入為用戶-物品評(píng)分矩陣以及用戶和物品間的交互行為序列，輸出為算法預(yù)測(cè)的用戶對(duì)未知物品的評(píng)分。關(guān)鍵步驟主要分為構(gòu)建用戶-用戶信任值矩陣、構(gòu)建用戶-用戶關(guān)系網(wǎng)絡(luò)和物品-物品關(guān)系網(wǎng)絡(luò)圖和基于矩陣分解技術(shù)進(jìn)行推薦結(jié)果預(yù)測(cè)。

圖1：SeqTMF整體框架流程圖

3.2 用戶的信任值矩陣

首先，本文使用Pearson相關(guān)系數(shù)計(jì)算用戶之間的相似度，則用戶u與用戶v之間的相似度計(jì)算方法如式（1）所示。

其次，用戶u與用戶v的信任值的計(jì)算公式如式（2）所示。

其中，Trust表示用戶u對(duì)用戶v的信任值，SK表示和用戶u最相似的 K個(gè)用戶的集合，SK表示和用戶v最相似的 K個(gè)用戶的集合，sim表示用戶u和用戶j之間的相似度。

如表1-3所示，首先根據(jù)用戶-物品評(píng)分矩陣（表1）以及式（1）得到用戶-用戶相似度矩陣，則用戶-用戶相似矩陣是一個(gè)對(duì)稱的上三角矩陣。相對(duì)于傳統(tǒng)的協(xié)同過濾方法利用該對(duì)稱矩陣取TopK的相似用戶或者物品集合來預(yù)測(cè)未知評(píng)分，本文方法進(jìn)行了改進(jìn)，即根據(jù)式（2）計(jì)算得到用戶-用戶信任值矩陣，然后取Top3最相似的用戶集合。如表2所示，和用戶A最相似的用戶集合為{B,D,E}，和用戶B最相似的用戶集合為{A,D,E}，則trust=0.452，trust=0.5497，由此可見trust≠trust且用戶A對(duì)用戶B的信任相較于用戶B對(duì)用戶A的信任低一些，即用戶-用戶信任值矩陣是一個(gè)非對(duì)稱矩陣，具有方向性。

表1：用戶-物品評(píng)分矩陣

表2：用戶-用戶相似度矩陣

3.3 構(gòu)建用戶及物品關(guān)系網(wǎng)絡(luò)圖

在基于關(guān)系的矩陣分解模型中，核心步驟是獲取用戶或者物品關(guān)系。傳統(tǒng)的協(xié)同過濾方法忽略了用戶與物品交互時(shí)間的先后順序?qū)δＰ偷挠绊??？紤]到用戶之間的關(guān)系以及信任值都是有向的，則在構(gòu)建用戶之間的關(guān)系網(wǎng)絡(luò)圖時(shí)需要融合兩者，而物品間的網(wǎng)絡(luò)關(guān)系圖則比較單一。

表3：用戶-用戶信任值矩陣

在用戶關(guān)系網(wǎng)絡(luò)圖G={U,E}中，U表示用戶集合，E表示邊集合，W表示邊的權(quán)重。如果在一定時(shí)間內(nèi)，用戶u和用戶v先后與同一個(gè)物品產(chǎn)生交互行為，則邊E的權(quán)重W自增1，遍歷完所有物品會(huì)后，即得到邊E的權(quán)重W?？紤]用戶信任值的影響，本文定義用戶間的相互影響的關(guān)系權(quán)重計(jì)算方式如式（3）所示。

其中I表示和用戶u產(chǎn)生交互行為的物品集合，I表示和用戶v產(chǎn)生交互行為的物品集合。

同理，我們可以建立物品的關(guān)系網(wǎng)絡(luò)圖，與用戶關(guān)系圖類似，其節(jié)點(diǎn)物品，其邊表示有多少用戶與邊關(guān)聯(lián)的兩個(gè)節(jié)點(diǎn)都產(chǎn)生過交互行為。構(gòu)建物品網(wǎng)絡(luò)圖中，可以利用式（4）計(jì)算節(jié)點(diǎn)之間的相關(guān)影響的關(guān)系權(quán)重。

其中，U表示與物品i產(chǎn)生交互行為的用戶集合，U表示與物品j產(chǎn)生交互行為的用戶集合。

3.4 生成預(yù)測(cè)評(píng)分

基于前述得到的用戶關(guān)系網(wǎng)絡(luò)以及物品關(guān)系網(wǎng)絡(luò)，尋找到用戶或者物品的最近鄰集合，并且將此應(yīng)用到矩陣分解中。則用戶和物品的特征向量主要受其最近鄰特征向量的影響，如式（5）所示。

通過貝葉斯推斷，其后驗(yàn)概率如式（8）所示。

為了方便求解，式（8）得到的后驗(yàn)概率的對(duì)數(shù)函數(shù)的處理方式如式（9）所示。

其中，g函數(shù)表示sigmod函數(shù)。接下來需要最大化后驗(yàn)概率，即通過式（10）求解目標(biāo)函數(shù)的最小化。

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

為了驗(yàn)證本文提出的SeqTMF方法的有效性，本文在公開數(shù)據(jù)集MovieLens-1M上進(jìn)行實(shí)驗(yàn)，并計(jì)算RMSE指標(biāo)以驗(yàn)證效果，實(shí)驗(yàn)結(jié)果表明推薦效果優(yōu)于其它對(duì)比方法。

4.1 實(shí)驗(yàn)數(shù)據(jù)集

MovieLens（ML-1M）數(shù)據(jù)集的相關(guān)信息如表4所示。

表4：MovieLens(ML-1M)數(shù)據(jù)集信息

因本文著重考慮時(shí)序性且防止數(shù)據(jù)穿越，因此按照時(shí)間嚴(yán)格將數(shù)據(jù)集劃分成8:2，其中8份為訓(xùn)練集，2份為測(cè)試集。

4.2 評(píng)價(jià)指標(biāo)

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

為了充分驗(yàn)證本文提出的SeqTMF方法的有效性，在實(shí)驗(yàn)中選擇了多個(gè)基線方法進(jìn)行對(duì)比。各基線方法的簡(jiǎn)單說明如表5所示。

表5：實(shí)驗(yàn)對(duì)比方法說明

在數(shù)據(jù)集上進(jìn)行充分實(shí)驗(yàn)，當(dāng)設(shè)置不同的K值,各推薦方法的RMSE趨勢(shì)如圖2所示。從圖中數(shù)據(jù)來看，隨著K值的提升，RMSE值越來越低，表明推薦效果隨著K值的增加會(huì)越來越好。SocialMF的效果相對(duì)BPTF略差，這主要是本實(shí)驗(yàn)中的SocialMF方法所構(gòu)建的社交網(wǎng)絡(luò)關(guān)系數(shù)據(jù)過于稀疏導(dǎo)致的。而TagMF的效果優(yōu)于BPMF，表明引入物品側(cè)的標(biāo)簽對(duì)推薦效果的影響是正向的。SequentialMF效果優(yōu)于SocialMF和TagMF，說明時(shí)序性對(duì)推薦效果的影響大于物品側(cè)，且大于社交數(shù)據(jù)相對(duì)稀疏的SocialMF方法。SeqTMF在幾種算法中推薦效果表現(xiàn)最優(yōu)，從側(cè)面說明了時(shí)序性、用戶間的信任值、物品間的關(guān)聯(lián)性三者的融合推薦效果是大于單一因素的考量。

圖2：各推薦方法在不同K值下的RMSE變化趨勢(shì)圖

5 總結(jié)及展望

本文通過對(duì)協(xié)同過濾推薦算法進(jìn)行深入地研究分析，并對(duì)比目前的一些研究成果，結(jié)合在實(shí)際應(yīng)用中的相關(guān)問題的調(diào)研，提出了一種改進(jìn)的融合時(shí)序和信任值矩陣的協(xié)同過濾推薦方法。首先基于用戶和物品的交互行為數(shù)據(jù)構(gòu)建用戶-物品評(píng)分矩陣，然后生成用戶-用戶相似度矩陣，接著得到非對(duì)稱矩陣的用戶-用戶信任值矩陣，進(jìn)一步地融入行為數(shù)據(jù)的時(shí)序特征，最終生成用戶-用戶關(guān)系網(wǎng)絡(luò)圖和物品-物品關(guān)系網(wǎng)絡(luò)圖。其次，將中間結(jié)果保存的關(guān)系網(wǎng)絡(luò)圖數(shù)據(jù)引入到矩陣分解的協(xié)同過濾推薦算法中，得到最后的推薦結(jié)果。實(shí)驗(yàn)結(jié)果表明，本文提出的推薦方法，在一定程度上提升了推薦精準(zhǔn)度。在今后的研究工作中，會(huì)進(jìn)一步探索將社交關(guān)系、物品標(biāo)簽、用戶靜態(tài)屬性等融入至SeqTMF算法中，以期進(jìn)一步提升推薦結(jié)果的精度。