基于矩陣分解的最近鄰?fù)扑]系統(tǒng)及其應(yīng)用

王 娟 ，熊 巍 ，b

（對(duì)外經(jīng)濟(jì)貿(mào)易大學(xué)a.統(tǒng)計(jì)學(xué)院;b.大數(shù)據(jù)風(fēng)險(xiǎn)與管理研究中心,北京 100029）

0 引言

隨著互聯(lián)網(wǎng)的日益發(fā)展，大數(shù)據(jù)逐漸進(jìn)入人們的日常生活。海量數(shù)據(jù)的可獲得性使人們獲取信息更為便利，生活更加高效，但是在海量數(shù)據(jù)中也存在著大量的垃圾數(shù)據(jù)，對(duì)于用戶來說，如何在這些數(shù)據(jù)中精準(zhǔn)高效地找到自己需要的信息變得更加困難，開發(fā)高效推薦系統(tǒng)的需求更加強(qiáng)烈。同時(shí)大數(shù)據(jù)的可獲得性產(chǎn)生了推薦系統(tǒng)的新問題——稀疏性，大規(guī)模的用戶數(shù)據(jù)集與物品數(shù)據(jù)集可以獲得，但是每個(gè)用戶只對(duì)少量的物品做出評(píng)分，使得評(píng)分矩陣存在高度稀疏性，協(xié)同過濾及其他一些傳統(tǒng)的推薦算法表現(xiàn)不佳。矩陣分解推薦算法在稀疏性與冷啟動(dòng)問題上都有很好的表現(xiàn)，目前的矩陣分解推薦算法有隱語(yǔ)義模型、奇異值分解、非負(fù)矩陣分解等，其主要原理是根據(jù)用戶評(píng)分矩陣推斷出用戶和物品的隱語(yǔ)義向量，然后根據(jù)隱語(yǔ)義向量進(jìn)行推薦。但矩陣分解有其弱點(diǎn)，就是解釋性差，不能很好地為推薦結(jié)果做出解釋；且矩陣分解并未考慮用戶之間的相似性。本文創(chuàng)新性的將矩陣分解的結(jié)果應(yīng)用于最近鄰?fù)扑]算法，綜合二者的優(yōu)點(diǎn)預(yù)測(cè)推薦系統(tǒng)評(píng)分，并能很好地解釋推薦結(jié)果。

利用Book-Crossing圖書社區(qū)整理的278858個(gè)用戶對(duì)271379本書進(jìn)行的評(píng)分?jǐn)?shù)據(jù)，顯示評(píng)分僅有397243條，稀疏性達(dá)到99.9995%。針對(duì)稀疏矩陣首先進(jìn)行了矩陣分解插值，然后利用基于用戶的最近鄰?fù)扑]算法尋找測(cè)試集用戶的最近鄰集合，并根據(jù)最近鄰用戶的評(píng)分作出推薦。該方法先考慮了用戶與物品之間的聯(lián)系，并解決了稀疏矩陣的問題，最近鄰集合則考慮了用戶之間的相似性，并能給出推薦結(jié)果的直觀解釋。綜合矩陣分解與最近鄰?fù)扑]算法的優(yōu)勢(shì)給出了更為有效的推薦算法。

1 文獻(xiàn)綜述

不同的推薦算法利用推薦系統(tǒng)中的不同信息給出推薦。基于內(nèi)容的推薦算法考慮的是用戶感興趣的物品的特征相似度，選擇與用戶已評(píng)分項(xiàng)目有相似特征的項(xiàng)目推薦給用戶。如Blancofernandez等（2008）[1]、Lops等（2011）[2]、Mooney和 Roy（2000）[3]、Pazzani和 Billsus（2007）[4]等都對(duì)基于內(nèi)容的推薦系統(tǒng)進(jìn)行了研究。Blancofernandez等（2008）[1]在分析項(xiàng)目之間的相似性時(shí)改進(jìn)了句法相似性過度專門化的問題，Mooney和Roy（2000）[3]則運(yùn)用了信息提取和機(jī)器學(xué)習(xí)算法對(duì)項(xiàng)目進(jìn)行文本分類，提升了預(yù)測(cè)精度?；谟脩舻膮f(xié)同過濾考慮了用戶之間的相似性，利用最近鄰用戶的評(píng)分預(yù)測(cè)目標(biāo)用戶的評(píng)分；基于項(xiàng)目的協(xié)同過濾則考慮了項(xiàng)目之間的相似性，該算法并未考慮項(xiàng)目的特征屬性，其主要是根據(jù)用戶的評(píng)分行為計(jì)算項(xiàng)目的相似度并給出推薦。Bell和Koren（2007）[5]改進(jìn)了最近鄰?fù)扑]中相似系數(shù)的權(quán)重計(jì)算方法，Koren（2010）[6]從評(píng)分矩陣出發(fā)提出了一種新的計(jì)算用戶之間相似性的方法來改進(jìn)協(xié)同過濾算法。在2009年的Netflix大賽上，Koren等（2009）[7]首次將矩陣分解應(yīng)用于推薦系統(tǒng)，并在Movielens數(shù)據(jù)集上得到了很高的預(yù)測(cè)精度，有效地解決了評(píng)分矩陣稀疏的問題。矩陣分解推薦算法將原始的評(píng)分矩陣分解為用戶-因子矩陣和項(xiàng)目-因子矩陣，可以有效地解決稀疏性與冷啟動(dòng)問題。目前的矩陣分解推薦算法有隱語(yǔ)義模型、奇異值分解、非負(fù)矩陣分解等，其主要原理是根據(jù)用戶評(píng)分矩陣推斷出用戶和物品的隱語(yǔ)義向量，然后根據(jù)隱語(yǔ)義向量進(jìn)行推薦，但矩陣分解的結(jié)果不易解釋且沒有考慮用戶之間的相互影響。Cacheda和Formoso（2011）[8]的分析結(jié)果表明在稀疏條件下SVD明顯好于其他一些傳統(tǒng)的推薦算法；Nguyen和Zhu(2013)[9]也研究了矩陣分解算法，創(chuàng)新性地將項(xiàng)目的內(nèi)容信息融入了矩陣分解算法中，內(nèi)容增強(qiáng)的矩陣分解算法不僅提高了推薦的準(zhǔn)確性，而且對(duì)內(nèi)容提供了有用的見解，使推薦更易于解釋。Wu(2007)[10]采用了三種不同類型的矩陣分解算法：規(guī)則化的矩陣分解、最大利潤(rùn)矩陣分解和非負(fù)矩陣分解，并將得到的結(jié)果與幾個(gè)參數(shù)結(jié)合起來實(shí)現(xiàn)了一個(gè)比Netflix系統(tǒng)更好服務(wù)的推薦算法。在單一推薦算法的發(fā)展下，一些混合推薦算法開始逐步發(fā)展起來，混合算法可以充分考慮評(píng)分矩陣的多類問題（如稀疏性、冷啟動(dòng)）而給出更為精準(zhǔn)的推薦。Melville等（2002）[11]將協(xié)同過濾與基于內(nèi)容的推薦方法結(jié)合，使用基于內(nèi)容的預(yù)測(cè)器來增強(qiáng)現(xiàn)有的用戶數(shù)據(jù)，然后通過協(xié)同過濾提供個(gè)性化的建議，實(shí)驗(yàn)結(jié)果表明內(nèi)容增強(qiáng)的協(xié)同過濾要比純粹的協(xié)同過濾和一般的混合方法要好。

目前的研究集中于協(xié)同過濾與矩陣分解兩大方向，協(xié)同過濾易于解釋，且考慮了用戶之間或用戶與項(xiàng)目之間的相似性，但在稀疏條件下則表現(xiàn)不佳。矩陣分解可以有效解決矩陣稀疏問題，但是其分解的兩個(gè)矩陣難以得到一個(gè)很好的解釋。本文提出了基于矩陣分解的最近鄰?fù)扑]算法，針對(duì)稀疏矩陣首先進(jìn)行了矩陣分解插值，然后利用基于用戶的協(xié)同過濾推薦算法尋找測(cè)試集用戶的最近鄰集合，利用最近鄰用戶的評(píng)分作出推薦，先考慮了用戶與物品之間的聯(lián)系，最近鄰集合則考慮了用戶之間的相似性。結(jié)合矩陣分解與協(xié)同過濾的優(yōu)點(diǎn)預(yù)測(cè)推薦系統(tǒng)評(píng)分，能夠很好地解釋推薦結(jié)果并提高預(yù)測(cè)精度。

2 模型介紹

評(píng)分矩陣中普遍存在的情形是用戶、項(xiàng)目數(shù)量都很大，但是用戶只對(duì)部分項(xiàng)目有評(píng)分。用戶-書籍評(píng)分矩陣中存在大量未評(píng)分?jǐn)?shù)據(jù)，傳統(tǒng)的基于項(xiàng)目的最近鄰?fù)扑]與基于用戶的最近鄰?fù)扑]算法在稀疏矩陣中的表現(xiàn)黯然失色。

而矩陣分解算法的原理是：基于用戶的行為對(duì)項(xiàng)目進(jìn)行自動(dòng)聚類，也就是把項(xiàng)目劃分到不同類別/主題，這些主題/類別可以理解為用戶的興趣。對(duì)于一個(gè)用戶來說，他們可能有不同的興趣。例如用戶A可能喜歡文學(xué)作品、語(yǔ)言學(xué)，用戶B可能喜歡文學(xué)、經(jīng)濟(jì)與資訊類，用戶C可能喜歡軍事、歷史等，基于這樣的想法，單純對(duì)書籍的分類可能并不能反映用戶的興趣所在。本文在可見的書籍名單中歸結(jié)出幾個(gè)類別，不等于該用戶就只喜歡這幾類，對(duì)其他類別的書籍就一點(diǎn)興趣也沒有。也就是說，本文需要了解用戶對(duì)于所有類別的興趣度。對(duì)于一個(gè)給定的類來說，需要確定這個(gè)類中每本書籍屬于該類別的權(quán)重。權(quán)重有助于確定該推薦哪些書籍給用戶。

假設(shè)評(píng)分矩陣為Rn*m，分解為兩個(gè)矩陣Pn*k，Qk*m的乘積：

矩陣值Rij表示的是用戶i對(duì)項(xiàng)目j的興趣度。將R矩陣表示為P矩陣和Q矩陣相乘。其中P矩陣是用戶-類別矩陣，矩陣值Pik表示的是用戶i對(duì)類別k的興趣度；Q矩陣是類別-項(xiàng)目矩陣，矩陣值Qkj表示項(xiàng)目j在類別k中的權(quán)重，權(quán)重越高越能作為該類的代表。然后根據(jù)如下公式來計(jì)算用戶i對(duì)項(xiàng)目j的興趣度：

防止過擬合，引入正則化后的目標(biāo)函數(shù)為：

采用隨機(jī)梯度下降法求解該最優(yōu)目標(biāo)：

更新的Pik，Qkj為：

對(duì)于一個(gè)用戶來說，當(dāng)計(jì)算出他對(duì)所有項(xiàng)目的興趣度后，就可以對(duì)評(píng)分矩陣插值。矩陣分解算法從數(shù)據(jù)集中抽取出若干潛在因子，作為用戶和項(xiàng)目之間連接的橋梁。

利用矩陣分解算法估計(jì)出每個(gè)用戶未評(píng)分項(xiàng)目的潛在評(píng)分，在這個(gè)過程中主要考慮了用戶與項(xiàng)目之間的作用關(guān)系，然后對(duì)插值后的評(píng)分矩陣進(jìn)行中心化。

在中心化后的評(píng)分記錄中找出測(cè)試集用戶u的最鄰近用戶集，充分考慮用戶之間的相似性。計(jì)算最近鄰集合中對(duì)每個(gè)項(xiàng)目的加權(quán)評(píng)分，計(jì)算估計(jì)誤差。

采用余弦相似度計(jì)算相似性：

目標(biāo)用戶u相似矩陣為：

根據(jù)用戶相似矩陣尋找與目標(biāo)用u相似的k個(gè)用戶構(gòu)成最近鄰集合。

用戶u對(duì)項(xiàng)目j的預(yù)測(cè)評(píng)分為：

根據(jù)用戶u對(duì)所有項(xiàng)目的預(yù)測(cè)評(píng)分計(jì)算預(yù)測(cè)誤差，評(píng)估模型預(yù)測(cè)精度。

優(yōu)點(diǎn)：先利用矩陣分解尋找用戶與項(xiàng)目之間作用關(guān)系，通過提取項(xiàng)目的不同屬性，以及用戶對(duì)不用屬性的興趣度，計(jì)算用戶對(duì)該項(xiàng)目的整體興趣度作為第一步得出插值，再利用用戶之間的相似性找出目標(biāo)用戶的最近鄰集合，利用最近鄰集合的加權(quán)評(píng)分作為目標(biāo)用戶對(duì)于項(xiàng)目的預(yù)測(cè)評(píng)分。在這個(gè)模型分析中，從用戶與項(xiàng)目之間的相關(guān)性及用戶之間的相似性兩個(gè)維度出發(fā)預(yù)測(cè)評(píng)分，充分利用了評(píng)分矩陣中的信息。

3 書籍評(píng)分?jǐn)?shù)據(jù)分析

本文通過book-crossing數(shù)據(jù)集來驗(yàn)證所提出的基于矩陣分解的協(xié)同過濾算法的推薦效率，Book-Crossing圖書社區(qū)收集了278858個(gè)用戶對(duì)271379本書的評(píng)分，包括顯式和隱式的評(píng)分。評(píng)分記錄共計(jì)1048575條，其中顯式評(píng)分有397243條，評(píng)分范圍為1～10，1分表示極不滿意，10分表示很滿意。隱式評(píng)分有651332條，用0表示，隱式評(píng)分是指用戶的瀏覽購(gòu)買記錄，一般用0和1表示，0表示沒有瀏覽/購(gòu)買，1表示瀏覽/購(gòu)買。如果用戶瀏覽過，但是沒有給出評(píng)分，可以推斷他不喜歡該項(xiàng)目，而沒有瀏覽過只能表明用戶暫時(shí)沒有接觸過這個(gè)項(xiàng)目。本文的實(shí)證部分采取顯式評(píng)分進(jìn)行分析。Book-Crossing數(shù)據(jù)包括三個(gè)數(shù)據(jù)集；用戶信息集包括用戶ID、年齡、所在國(guó)家、州等人口統(tǒng)計(jì)學(xué)屬性；書籍信息集包括書籍ISDN編碼、書籍名稱、作者、出版社、出版年份信息；還有用戶評(píng)分?jǐn)?shù)據(jù)集。原始數(shù)據(jù)中存在部分無效數(shù)據(jù)，首先要對(duì)數(shù)據(jù)進(jìn)行一系列預(yù)處理。

3.1 數(shù)據(jù)處理

考慮到數(shù)據(jù)過于稀疏，在本文的分析中，首先對(duì)數(shù)據(jù)進(jìn)行了統(tǒng)計(jì)，只選取評(píng)分書籍不小于20本的用戶以及評(píng)分用戶不小于20個(gè)的書籍，篩選過后的用戶共計(jì)2789名，書籍總數(shù)達(dá)到1846本。評(píng)分記錄共計(jì)38854條，數(shù)據(jù)稀疏性為99.25%。從評(píng)分記錄中隨機(jī)抽取1000條記錄作為測(cè)試集。評(píng)分記錄如表1所示。

表1 部分評(píng)分記錄

圖1展示了各類評(píng)分?jǐn)?shù)據(jù)頻率分布，從圖1可知，評(píng)分矩陣中用戶傾向于給出較高的分?jǐn)?shù)，評(píng)分眾數(shù)和中位數(shù)均為8，平均評(píng)分為7.94。

圖1 評(píng)分?jǐn)?shù)據(jù)分布柱形圖

圖2給出了用戶累積評(píng)分分布折線圖，對(duì)用戶評(píng)分頻率降序累積排列并畫出折線圖，評(píng)分最多的用戶做出了913個(gè)評(píng)分，大約483個(gè)用戶評(píng)分?jǐn)?shù)據(jù)占到了所有評(píng)分?jǐn)?shù)據(jù)的50%。

圖2 用戶累積評(píng)分分布折線圖

圖3給出了書籍累積評(píng)分分布折線圖，從書籍累積評(píng)分來看，評(píng)分最多的書籍有221個(gè)用戶評(píng)分，大約對(duì)于470本書的評(píng)分個(gè)數(shù)即達(dá)到了整體評(píng)分?jǐn)?shù)的50%。

圖3 書籍累積評(píng)分分布折線圖

3.2 誤差衡量標(biāo)準(zhǔn)

推薦系統(tǒng)常用的誤差衡量指標(biāo)有均方誤差（RMSE）、平均絕對(duì)誤差（MAE）。測(cè)試集共1000個(gè)數(shù)據(jù)。

在矩陣分解后得到矩陣R=P*Q,然后基于最近鄰集合計(jì)算測(cè)試集用戶的預(yù)測(cè)評(píng)分，填補(bǔ)評(píng)分矩陣的缺失值，計(jì)算測(cè)試集的誤差。

3.3 基于矩陣分解的最近鄰?fù)扑]系統(tǒng)

矩陣分解得到的R矩陣對(duì)評(píng)分矩陣插值填補(bǔ)，然后對(duì)1000條測(cè)試集記錄做中心化。

尋找測(cè)試集1000條記錄對(duì)應(yīng)用戶的10個(gè)最近鄰集合，利用相似系數(shù)加權(quán)計(jì)算目標(biāo)用戶已評(píng)分項(xiàng)目的預(yù)測(cè)評(píng)分并計(jì)算預(yù)測(cè)誤差RMSE和MAE。表2為矩陣分解過程中所用參數(shù)。

表2 梯度下降法求解矩陣分解中的參數(shù)設(shè)置

表3（見下頁(yè)）為不同矩陣分解主題下的MF-CF方法的預(yù)測(cè)誤差。由表3可知，隨著k值的增加，預(yù)測(cè)誤差首先表現(xiàn)為逐漸減小，當(dāng)k值大于30以后，預(yù)測(cè)誤差不再減小，并會(huì)隨著k值的增大出現(xiàn)小幅增加。當(dāng)k值為30時(shí)，MF-CF預(yù)測(cè)方法的平均絕對(duì)誤差為0.74，回顧原始數(shù)據(jù)評(píng)分為1～10，間距較大，其平均預(yù)測(cè)誤差較小，預(yù)測(cè)變化較小，表明了MF-CF方法在Book-Crossing數(shù)據(jù)集上得到了較為合理的結(jié)果。

4 結(jié)論

本文首先對(duì)稀疏矩陣做了矩陣分解，并用梯度下降法求出對(duì)應(yīng)的P、Q矩陣，從用戶對(duì)項(xiàng)目的偏好角度預(yù)測(cè)用戶評(píng)分，然后利用已插值的評(píng)分矩陣計(jì)算目標(biāo)用戶的最近鄰集合，并利用最近鄰用戶的評(píng)分預(yù)測(cè)目標(biāo)用戶的評(píng)分。在模型估計(jì)部分計(jì)算了不同k值下的矩陣分解的誤差，并選取了最優(yōu)的k值進(jìn)行預(yù)測(cè)。

本文只是從稀疏矩陣出發(fā)對(duì)分層混合推薦方法的一個(gè)嘗試，在混合推薦算法的具體應(yīng)用中，還有較多的算法未能應(yīng)用在此與文中算法進(jìn)行對(duì)比。從數(shù)據(jù)來看，本文所設(shè)計(jì)的數(shù)據(jù)只是對(duì)原始數(shù)據(jù)中顯式評(píng)分?jǐn)?shù)據(jù)的建模，原始數(shù)據(jù)中包含有大量的隱式評(píng)分并未在該方法中考慮，在以后的分析中可以應(yīng)用隱式評(píng)分對(duì)Book-Crossing完整數(shù)據(jù)集進(jìn)行分析。作為該想法的擴(kuò)展研究，原始數(shù)據(jù)集中還包括了用戶的一些基本人口統(tǒng)計(jì)學(xué)信息及書籍的基本信息，利用數(shù)據(jù)挖掘和文本分析等方法充分利用這些信息提高推薦系統(tǒng)的質(zhì)量也是繼續(xù)深入研究的一個(gè)方向。

表3 不同參數(shù)下推薦性能比較