基于矩陣分解的最近鄰推薦系統(tǒng)及其應用

王 娟 ，熊 巍 ，b

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

0 引言

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

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

1 文獻綜述

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

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

2 模型介紹

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

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

假設評分矩陣為Rn*m，分解為兩個矩陣Pn*k，Qk*m的乘積：

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

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

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

更新的Pik，Qkj為：

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

利用矩陣分解算法估計出每個用戶未評分項目的潛在評分，在這個過程中主要考慮了用戶與項目之間的作用關系，然后對插值后的評分矩陣進行中心化。

在中心化后的評分記錄中找出測試集用戶u的最鄰近用戶集，充分考慮用戶之間的相似性。計算最近鄰集合中對每個項目的加權評分，計算估計誤差。

采用余弦相似度計算相似性：

目標用戶u相似矩陣為：

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

用戶u對項目j的預測評分為：

根據(jù)用戶u對所有項目的預測評分計算預測誤差，評估模型預測精度。

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

3 書籍評分數(shù)據(jù)分析

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

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

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

表1 部分評分記錄

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

圖1 評分數(shù)據(jù)分布柱形圖

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

圖2 用戶累積評分分布折線圖

圖3給出了書籍累積評分分布折線圖，從書籍累積評分來看，評分最多的書籍有221個用戶評分，大約對于470本書的評分個數(shù)即達到了整體評分數(shù)的50%。

圖3 書籍累積評分分布折線圖

3.2 誤差衡量標準

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

在矩陣分解后得到矩陣R=P*Q,然后基于最近鄰集合計算測試集用戶的預測評分，填補評分矩陣的缺失值，計算測試集的誤差。

3.3 基于矩陣分解的最近鄰推薦系統(tǒng)

矩陣分解得到的R矩陣對評分矩陣插值填補，然后對1000條測試集記錄做中心化。

尋找測試集1000條記錄對應用戶的10個最近鄰集合，利用相似系數(shù)加權計算目標用戶已評分項目的預測評分并計算預測誤差RMSE和MAE。表2為矩陣分解過程中所用參數(shù)。

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

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

4 結論

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

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

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