K-近鄰矩陣分解推薦系統(tǒng)算法

郝雅嫻，孫艷蕊

(東北大學(xué) 理學(xué)院，沈陽(yáng) 110819) E-mail：Hao_yaxian@163.com

1 概 述

近幾年來(lái)，隨著Internet的發(fā)展以及電子商務(wù)網(wǎng)站迅速崛起，推薦系統(tǒng)[1]廣泛應(yīng)用于電子商務(wù)網(wǎng)站，為網(wǎng)站用戶進(jìn)行商品智能推薦，大大提高了電子商務(wù)網(wǎng)站的商業(yè)效益.因此，如何提高推薦算法的推薦結(jié)果準(zhǔn)確性成為電子商務(wù)網(wǎng)站的目標(biāo)追求.協(xié)同過濾算法[2]是目前應(yīng)用最廣泛且效果最好的推薦系統(tǒng)算法.但是，隨著電子商務(wù)網(wǎng)站不斷增加的用戶量與商品量，大數(shù)據(jù)下導(dǎo)致的數(shù)據(jù)稀疏性使得協(xié)同過濾算法已經(jīng)遠(yuǎn)遠(yuǎn)不能正確對(duì)用戶的評(píng)分值做出準(zhǔn)確的預(yù)測(cè).所以，在協(xié)同過濾算法基礎(chǔ)上進(jìn)行改進(jìn)的算法不斷出現(xiàn).例如：基于項(xiàng)目的協(xié)同過濾算法及其算法改進(jìn)[3-5]，基于神經(jīng)網(wǎng)絡(luò)的協(xié)同過濾算法[6]以及基于矩陣降維的協(xié)同過濾算法[7，8]，基于鄰域的協(xié)同過濾算法改進(jìn)[9]等.

本文算法是在基于鄰域的協(xié)同過濾算法與基于矩陣分解的協(xié)同過濾算法[10]兩方面基礎(chǔ)上提出的.主要貢獻(xiàn)是解決了大數(shù)據(jù)導(dǎo)致的極大稀疏性問題，并且能很好的找到與目標(biāo)用戶對(duì)目標(biāo)項(xiàng)目的評(píng)分相關(guān)性較大的用戶與項(xiàng)目，使得評(píng)分值更加精確，算法主要包括三個(gè)方面的內(nèi)容：一、分別對(duì)目標(biāo)用戶u與目標(biāo)項(xiàng)目i尋找其最近鄰，這一部分在4.2與4.3詳細(xì)給出，二、建立近鄰矩陣并對(duì)近鄰矩陣進(jìn)行矩陣分解，三、預(yù)測(cè)評(píng)分值，二、三部分在4.4中給出.

2 傳統(tǒng)的矩陣分解

2.1 矩陣分解模型

矩陣分解算法具有伸縮性好，靈活性高等特點(diǎn).最早的矩陣分解算法為奇異值分解算法(Singular Value Decompostion，SVD)，但是SVD有兩方面的缺點(diǎn)：一是在算法執(zhí)行之前必須補(bǔ)全原始評(píng)分矩陣中的缺失值；二是算法執(zhí)行效率太低.在SVD算法之后Simon Funk將隨機(jī)梯度下降算法應(yīng)用在推薦算法中，他利用隨機(jī)梯度下降算法高效的實(shí)現(xiàn)了評(píng)分值的預(yù)測(cè).此后，利用隨機(jī)梯度下降算法的矩陣分解被應(yīng)用于各大電子商務(wù)網(wǎng)站，成為了經(jīng)典的推薦系統(tǒng)算法.

Simon Funk提出的矩陣分解算法是將用戶與項(xiàng)目映射到隱語(yǔ)義空間上，因此該算法也被稱作隱語(yǔ)義模型.以電影為例，影響用戶對(duì)電影評(píng)分值的隱語(yǔ)義可能是電影的類型：悲劇、喜劇、愛情片等等.矩陣分解算法進(jìn)行商品推薦的前提是對(duì)原始評(píng)分?jǐn)?shù)據(jù)矩陣的學(xué)習(xí)，設(shè)原始評(píng)分矩陣有m個(gè)用戶，n個(gè)項(xiàng)目，記原始評(píng)分矩陣為Rm×n=(rui)m×n.f表示隱語(yǔ)義的個(gè)數(shù).每個(gè)用戶u對(duì)應(yīng)一個(gè)隱語(yǔ)義向量(用戶因子向量)pu∈Rf，每個(gè)項(xiàng)目i對(duì)應(yīng)一個(gè)隱語(yǔ)義向量(項(xiàng)目因子向量)qi∈Rf.算法通過將用戶因子向量與項(xiàng)目因子向量做內(nèi)積來(lái)對(duì)未知評(píng)分項(xiàng)做預(yù)測(cè)[10].

(1)

2.2 隨機(jī)梯度下降算法

(2)

1)已知rui-qTpu～N(0，δ2)

3)最大化p(rui)，等價(jià)于最大化lnp(rui)，由(2)得：

4)觀察lnp(rui)可知，在等式右邊的兩項(xiàng)中，只有∑∑(rui-qTpu)2為變量，所以最大化lnp(rui)，等價(jià)于最小化∑∑(rui-qTpu)2.

(3)

(4)

(5)

其中γ控制迭代的步長(zhǎng)，不宜太大，通常利用交叉驗(yàn)證得到.通過等式(4)的計(jì)算分別得到項(xiàng)目因子向量(6)與用戶因子向量(7)參數(shù)更改的定義式[10].

qi=qi+γ·(eui·pu-λ·qi)

(6)

pu=pu+γ·(eui·qi-λ·pu)

(7)

利用隨機(jī)梯度下降算法得到能夠使等式(3)最優(yōu)的參數(shù)qi∈Rf與pu∈Rf，從而得到預(yù)測(cè)評(píng)分值.Simon Funk提出的矩陣分解算法提高了算法的執(zhí)行效率，但是在大數(shù)據(jù)背景下，這一經(jīng)典算法已經(jīng)不能夠很好的反映原始數(shù)據(jù)的真實(shí)性，因?yàn)樵荚u(píng)分矩陣極大的稀疏性對(duì)實(shí)驗(yàn)結(jié)果準(zhǔn)確造成很大影響.所以在該算法上建立了很多混合算法與改進(jìn)算法來(lái)提高推薦結(jié)果的準(zhǔn)確性.本文提出了一個(gè)基于矩陣分解與最近鄰的混合協(xié)同過濾算法，該算法充分利用了矩陣分解算法與最近鄰算法的優(yōu)點(diǎn)，實(shí)驗(yàn)證明本文算法有較好的推薦效果.

3 傳統(tǒng)的最近鄰算法

基于最近鄰算法(K-Nearest Neighbor algorithm，KNN)是最常用的協(xié)同過濾算法，最先提出的是基于用戶的協(xié)同過濾算法[12].其基本思想是利用目標(biāo)用戶近鄰用戶的評(píng)分值去估計(jì)目標(biāo)用戶對(duì)項(xiàng)目的評(píng)分預(yù)測(cè)值.隨后基于項(xiàng)目的最近鄰算法被提出[13，14]，因?yàn)榛陧?xiàng)目最近鄰算法比基于用戶最近鄰算法具有更好的合理性與高效性，被廣泛應(yīng)用.在這里只介紹基于項(xiàng)目最近鄰算法的基本思想，對(duì)于目標(biāo)項(xiàng)目i的最近鄰尋找，首先定義最近鄰個(gè)數(shù)k，將計(jì)算所得的相似度按從大到小的順序排列，選取前k個(gè)作為目標(biāo)項(xiàng)目i的k個(gè)最近鄰用戶.尋找項(xiàng)目最近鄰算法的關(guān)鍵問題是通過計(jì)算相似度來(lái)尋找最近鄰，計(jì)算相似度的方法常用的有歐氏距離、余弦相似度以及皮爾遜相似度，本文采用歐氏距離方法計(jì)算相似度，計(jì)算公式如下：

(8)

公式(7)中的i與j分別表示原始評(píng)分矩陣中的任意兩個(gè)項(xiàng)目，Ri與Rj分別表示項(xiàng)目i與j對(duì)應(yīng)的評(píng)分向量，Sij表示項(xiàng)目i與j之間的相似度大小.將計(jì)算所得的相似度大小保存到相似度向量矩陣中，預(yù)測(cè)評(píng)分值由評(píng)分值與相似度的加權(quán)平均值得到，記Nk(i；u)為項(xiàng)目i的最近鄰集合，j∈Nk(i;u)表示用戶u評(píng)過分的項(xiàng)目i的近鄰項(xiàng)目j[11]則：

(9)

基于最近鄰算法是最早期的協(xié)同過濾算法，當(dāng)在原始評(píng)分矩陣具有極大的稀疏性時(shí)，利用相似度計(jì)算目標(biāo)項(xiàng)目的最近鄰會(huì)出現(xiàn)誤差.因此許多學(xué)者在KNN算法執(zhí)行之前會(huì)首先對(duì)原始評(píng)分矩陣進(jìn)行預(yù)處理，從而使算法的準(zhǔn)確性提高.本文在對(duì)原始數(shù)據(jù)處理之后，同時(shí)對(duì)目標(biāo)用戶與目標(biāo)項(xiàng)目查找最近鄰，并建立近鄰評(píng)分矩陣，對(duì)新的評(píng)分矩陣進(jìn)行矩陣分解，實(shí)驗(yàn)證明本文算法提高了推薦結(jié)果的精確度.

4 K近鄰矩陣分解算法

為了更好的解決原始評(píng)分矩陣稀疏性與推薦結(jié)果的準(zhǔn)確性，許多學(xué)者建立了協(xié)同過濾算法的混合型算法，例如Yehuda Koren等人提出的混合算法[14].本文在最近鄰算法與矩陣分解算法的基礎(chǔ)上提出了一個(gè)新的混合算法——K近鄰矩陣分解算法，(A K-Nearest Neighbor Matrix Factorization for Recommender systems)簡(jiǎn)稱KNNMF.

4.1 初始化評(píng)分矩陣

因?yàn)樵荚u(píng)分矩陣極大的稀疏性，會(huì)影響算法實(shí)驗(yàn)結(jié)果的準(zhǔn)確性，所以在算法執(zhí)行之前首先對(duì)原始評(píng)分矩陣進(jìn)行初始化，本文采用文獻(xiàn)[14]中的公式(10)對(duì)原始評(píng)分矩陣進(jìn)行數(shù)據(jù)預(yù)處理.

(10)

圖1 k=2時(shí)RMSE隨參數(shù)α、f的變化分布Fig.1 DistributionofRMSEwithα、fbasedonk=2圖2 k=5時(shí)RMSE隨參數(shù)α、f的變化分布Fig.2 DistributionofRMSEwithα、fbasedonk=5

圖3 k=7時(shí)RMSE隨參數(shù)α、f的變化分布Fig.3 DistributionofRMSEwithα、fbasedonk=7圖4 k=10時(shí)RMSE隨參數(shù)α、f的變化分布Fig.4 DistributionofRMSEwithα、fbasedonk=10

5,7,10，固定f，參數(shù)α的改變對(duì)RMSE的值影響不大，如圖1-圖4.因此本文取α=500作為實(shí)驗(yàn)數(shù)據(jù)量(見圖1-圖4).

4.2 基于用戶最近鄰計(jì)算

本文算法首先計(jì)算用戶最近鄰，針對(duì)目標(biāo)用戶u尋找其前k個(gè)最近鄰，v∈Nk(u;i)表示對(duì)商品i評(píng)過分的用戶u的近鄰用戶v，建立用戶u的近鄰集合U={v|v∈Nk(u;i)}.例如表1給出了五個(gè)用戶對(duì)五個(gè)商品的評(píng)分情況，如果計(jì)算用戶User3對(duì)目標(biāo)項(xiàng)目Item1的評(píng)分(在這里取k=2).需首先尋找對(duì)項(xiàng)目Item1評(píng)過分的用戶，即表1中User1,User2,User3，利用歐氏距離計(jì)算目標(biāo)用戶與以上用戶之間相似度分別為：S13=2.2361，S23=5.8130，S53=4.5826.由歐氏距離的大小可知User1與User5為目標(biāo)用戶User3的k最近鄰用戶，此時(shí)目標(biāo)用戶的近鄰集合U={User1,User5}.

表1 用戶-商品評(píng)分矩陣Table 1 Users- items rating matrix

4.3 基于項(xiàng)目最近鄰計(jì)算

將目標(biāo)用戶k的最近鄰保存于集合U中，接下來(lái)對(duì)目標(biāo)項(xiàng)目i尋找其前k個(gè)最近鄰，j∈Nk(i；u)表示用戶u評(píng)過分的項(xiàng)目i的近鄰項(xiàng)目j，建立項(xiàng)目i的近鄰集合J={j|j∈Nk(i;u)}.計(jì)算表1中用戶User3對(duì)目標(biāo)項(xiàng)目Item1的評(píng)分(在這里取k=2)，首先尋找用戶User3評(píng)過分的項(xiàng)目，即表1中Item2，Item3,Item4,Item5利用歐氏距離計(jì)算目標(biāo)項(xiàng)目與以上項(xiàng)目之間的相似度，分別為S12=3.4641，S13=6.7832，S14=6.4807，S15=5.6569.顯然Item2與Item5為目標(biāo)項(xiàng)目Item1的k最近鄰用戶，此時(shí)目標(biāo)項(xiàng)目的近鄰集合J={Item2,Item5}.

4.2與4.3主要計(jì)算目標(biāo)用戶與目標(biāo)項(xiàng)目的前k個(gè)最近鄰，并將計(jì)算所得的目標(biāo)用戶與目標(biāo)項(xiàng)目的最近鄰分別保存到目標(biāo)用戶近鄰集合U={v|v∈Nk(u;i)}與目標(biāo)項(xiàng)目集合J={j|j∈Nk(i;u)}，在數(shù)據(jù)集中，每一個(gè)用戶與項(xiàng)目均有最近鄰，所以可以得到用戶近鄰矩陣UKm×k=[U1,U2，…，Um]T與項(xiàng)目近鄰矩陣JKn×k=[J1,J2,…,Jn]T.用戶近鄰矩陣與項(xiàng)目近鄰矩陣為接下來(lái)建立近鄰評(píng)分矩陣做準(zhǔn)備.

4.4 矩陣分解與評(píng)分預(yù)測(cè)

預(yù)測(cè)評(píng)分值rui，目標(biāo)用戶u的k最近鄰對(duì)目標(biāo)項(xiàng)目i的k最近鄰的評(píng)分值構(gòu)成的矩陣，稱為近鄰評(píng)分矩陣，記為KR，則

這是一個(gè)k階方陣，rviji表示目標(biāo)用戶近鄰對(duì)目標(biāo)項(xiàng)目近鄰的評(píng)分值，其中vi∈U，ji∈J，I=1,2,…,k.

例如在4.2的例子中，要預(yù)測(cè)User3對(duì)目標(biāo)項(xiàng)目Item1的評(píng)分，根據(jù)定義可以建立如下近鄰評(píng)分矩陣.本算法提出的近鄰評(píng)分矩陣有效的提取了目標(biāo)用戶對(duì)目標(biāo)項(xiàng)目評(píng)分值相關(guān)性最大的近鄰用戶與近鄰商品的信息，從而降低了稀疏性對(duì)實(shí)驗(yàn)結(jié)果的影響，提高了算法的推薦精度.

DRk×k=PQT

(11)

本文提出了計(jì)算未知評(píng)分值rui的新方法.在公式(11)中，|DRk×k|表示矩陣DRk×k的行列式值，行列式的值是矩陣特征值的乘積，特征值反映了矩陣本身的性質(zhì).因?yàn)槊恳粋€(gè)用戶與項(xiàng)目作為目標(biāo)用戶與目標(biāo)項(xiàng)目的最近鄰的概率均為1/k，所以rui的值由分解之后矩陣的行列式值乘以1/k.

(12)

對(duì)矩陣KR進(jìn)行分解時(shí)需要考慮因子個(gè)數(shù)對(duì)推薦準(zhǔn)確度的影響.本文以MovieLine數(shù)據(jù)集為實(shí)驗(yàn)數(shù)據(jù)，在參數(shù)α=500的條件下，尋找矩陣分解實(shí)驗(yàn)的最優(yōu)隱因子個(gè)數(shù)f，如圖5，圖中iterlatent為隱語(yǔ)義個(gè)數(shù)f，通過實(shí)驗(yàn)可知，當(dāng)因子個(gè)數(shù)為5與2時(shí)推薦結(jié)果的準(zhǔn)確度幾乎相近.所以當(dāng)因子個(gè)數(shù)取5與2時(shí)，推薦結(jié)果是最好的，從而下面的實(shí)驗(yàn)中均取f=5.

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

5.1 評(píng)價(jià)標(biāo)準(zhǔn)

本算法利用均方根誤差(RMSE)驗(yàn)證實(shí)驗(yàn)結(jié)果的準(zhǔn)確性，以RMSE值作為實(shí)驗(yàn)準(zhǔn)確性的評(píng)價(jià)指標(biāo)，RMSE的值越小算法實(shí)驗(yàn)結(jié)果越優(yōu).計(jì)算公式如下：其中TestSet表示測(cè)試集[15].

(13)

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

本文實(shí)驗(yàn)所采用的數(shù)據(jù)集為MovieLens數(shù)據(jù)集，MovieLens數(shù)據(jù)集是包含943個(gè)用戶與1682部電影的評(píng)分矩陣.本文算法與三種算法進(jìn)行比較：

圖6為本文提出的K近鄰矩陣分解算法(K-Nearest Neighbor Matrix Factorization，KNNMF)與原始矩陣分解算法(Matrix Factorization，MF)的實(shí)驗(yàn)結(jié)果對(duì)比圖，由圖可知，對(duì)k=2,5,7,10時(shí)，隨著隱因子個(gè)數(shù)的變化，KNNMF算法所得的RMSE值低于MF算法的RMSE值，所以本文算法的實(shí)驗(yàn)結(jié)果更加精確.

圖5 RMSE隨參數(shù)的f變化分布Fig.5 DistributionofRMSEwithf圖6 原始矩陣分解與K近鄰矩陣分解算法RMSE比較Fig.6 RMSEcomparisonofmatrixfactorizationandKNNMF

圖7為本文提出的KNNMF算法與Y.Koren等人提出的聯(lián)合近鄰插值算法[14]的實(shí)驗(yàn)結(jié)果對(duì)比，由圖中數(shù)據(jù)可知，取相同的k近鄰時(shí)，本文算法KNNMF的RMSE值遠(yuǎn)遠(yuǎn)的小于KNNw的RMSE值，所以，本文算法極大的提高了推薦結(jié)果的精確度.

圖7 聯(lián)合近鄰插值算法與K近鄰矩陣分解算法RMSE比較Fig.7 RMSEcomparisonofKNNwandKNNMF圖8 基于PCA與聯(lián)合近鄰權(quán)值的協(xié)同過濾算法與基于近鄰與矩陣分解混合算法RMSE比較Fig.8 RMSEcomparisonofPCAwithjointlyderivedneighborhoodandKNNMF

圖8為本文提出的KNNMF算法與基于PCA與聯(lián)合近鄰權(quán)值的協(xié)同過濾算法(PCAwKNN)的實(shí)驗(yàn)結(jié)果對(duì)比，PCAwKNN算法是將主成分分析(Principal Component Analysis，PCA)與文獻(xiàn)[14]中的近鄰插值算法混合，從數(shù)據(jù)中可知，KNNMF算法的精確度遠(yuǎn)遠(yuǎn)高于PCAwKNN算法的精確度.

從三組實(shí)驗(yàn)結(jié)果的實(shí)驗(yàn)數(shù)據(jù)對(duì)比中可知，本算法極大的剔除了與目標(biāo)用戶以及目標(biāo)項(xiàng)目無(wú)關(guān)的數(shù)據(jù)影響，不僅降低了原始評(píng)分矩陣的稀疏性影響，而且有效的提高了算法的準(zhǔn)確性.

6 總 結(jié)

本文提出的K近鄰矩陣分解推薦算法，結(jié)合了經(jīng)典矩陣分解算法與最近鄰算法的優(yōu)點(diǎn).在對(duì)未知評(píng)分項(xiàng)預(yù)測(cè)時(shí)，同時(shí)考慮目標(biāo)用戶與目標(biāo)項(xiàng)目的最近鄰，大大減少了無(wú)關(guān)用戶與項(xiàng)目的相關(guān)評(píng)分值影響.并提出了新的近鄰評(píng)分矩陣，對(duì)近鄰評(píng)分矩陣進(jìn)行矩陣分解，給出了計(jì)算未知評(píng)分項(xiàng)的新方法.實(shí)驗(yàn)結(jié)果證明，本文提出的算法對(duì)比傳統(tǒng)的協(xié)同過濾推薦算法得到更準(zhǔn)確的推薦結(jié)果.

[1] Schafer J B，Konstan J A，Riedl J.E-commerce recommendation applications[J].Data Mining and Knowledge Discovery，2001，5(1)：115-153.

[2] Adomavicius G，ATuzhilin.Towards the next generation of recommend systems：a survey of the state-of-the-art and possible extensions[J].IEEE Transactions on Knowledge and Data Engineering，2005，17(6)：734-749.

[3] KaryPis G.Evaluation of item-based top-n recommendation algorithms[C].Proceedings of the 10th International Conference on Information and Knowledge Management，New York：ACM Press，2001：247-254.

[4] Sarwar B，KaryPis G，Konstan J，et al.Item-based collaborative filtering recommendation algorithms[C].Proceedings of the 10th International Conference on World Wide Web,New York：ACM Press，2001：285-295.

[5] Wu Yan-wen,Wang Jie,Wang Fei.Collaborative filtering recommendation model based on hybrid particle swarm optimization and genetic algorithm[J].Journal of Chinese Computer Systems，2017，38(3)：527-530.

[6] Zhang Feng，Chang Hui-you.Employing BP neural networks to alleviate the sparsity issue in collaborative filtering recommendation algorithms[J].Journal of Computer Research and Development，2006，43(4)：667-672.

[7] Sarwar B M，Karypis G，Konstan J A，et al.Application of dimensionality reduction in recommender system-a case study，TR 00—043 [R].Minneapolis，USA：Department of Computer Science and Engineering，University of Minnesota，2000.

[8] Zhao Liang，Hu Nai-jing，Zhang Shou-zhi.Algorithm design for personalization recommendation systems[J].Journal of Computer Research and Development，2002，39(8)：986-991.

[9] Bell R，Koren Y，Volinsky C.Modeling relationships at multiple scales to improve accuracy of large recommender systems[C].Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD′07)，2007：95-104.

[10] Koren Y，bell R，Volinsky C.Matrix factorization techniques for recommender systems[J].IEEE Computer Society，2009，42(8)：30-37.

[11] Hu Yi-fan，Yehuda Koren，Chris Volinsky.Collaborative filtering for implicit feedback datasets[C].IEEE International Conference on Data Mining(ICDM′08)，2008：263-272.

[12] Herlocker J L，Konstan J A，Riedl J.An algorithmic framework for performing collaborative filtering[C].Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval，1999：230-237.

[13] Linden G，Smith B，York J.Amazon.com recommendations：item-to-item collaborative filtering[J].IEEE Internet Computing，2003，7(1)：76-80.

[14] Bell and Koren Y.Scalable collaborative filtering with jointly derived neighborhood interpolation weights[C].IEEE International Conference on Data Mining(ICDM′07)，2007：43-52.

[15] Koren Y.Factorization meets the neighborhood：a multifaceted collaborative filtering model[C].Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD′08)，2008：426-434.

附中文參考文獻(xiàn)：

[5] 吳彥文，王 潔，王 飛.混合粒子群遺傳算法的協(xié)同過濾推薦模型[J].小型微型計(jì)算機(jī)系統(tǒng)，2017，38(3)：527-530.

[6] 張 鋒，常會(huì)友.使用BP神經(jīng)網(wǎng)絡(luò)緩解協(xié)同過濾算法的稀疏性問題[J].計(jì)算機(jī)研究與發(fā)展，2006，43(4)：667-672.

[8] 趙 亮，胡乃靜.張守志.個(gè)性化推薦算法設(shè)計(jì)[J].計(jì)算機(jī)研究與發(fā)展，2002，39(8)：986-991.