基于稀疏約束非負(fù)矩陣分解的推薦算法

劉 煜,陳 震,劉奇龍

(貴州師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，貴州 貴陽(yáng) 550025)

0 引言

隨著互聯(lián)網(wǎng)的高速發(fā)展，用戶(hù)可以輕松的獲取網(wǎng)絡(luò)信息。近年來(lái)，電子商務(wù)的發(fā)展尤為迅速，個(gè)性化推薦也逐漸出現(xiàn)在人們的視線當(dāng)中。推薦系統(tǒng)[1-3]是利用電子商務(wù)網(wǎng)站向客戶(hù)提供商品信息和建議，幫助用戶(hù)決定應(yīng)該購(gòu)買(mǎi)什么產(chǎn)品，個(gè)性化推薦是根據(jù)用戶(hù)的興趣特點(diǎn)和購(gòu)買(mǎi)行為，向用戶(hù)推薦其所感興趣的信息和商品。隨著電子商務(wù)規(guī)模的不斷擴(kuò)大，網(wǎng)絡(luò)上數(shù)據(jù)的爆炸式增長(zhǎng)導(dǎo)致了越來(lái)越嚴(yán)重的信息過(guò)載現(xiàn)象。為了幫助用戶(hù)從海量的網(wǎng)絡(luò)數(shù)據(jù)中快速定位自己最有可能感興趣的信息，推薦系統(tǒng)應(yīng)運(yùn)而生。推薦系統(tǒng)是減輕信息過(guò)載影響和實(shí)現(xiàn)個(gè)性化服務(wù)的最有效方法之一，它已經(jīng)滲透到了我們生活的方方面面，比如愛(ài)奇藝的電影推薦、網(wǎng)易云的音樂(lè)推薦、淘寶的商品推薦、美團(tuán)的餐廳推薦、抖音的短視頻推薦等等?，F(xiàn)在最常用的推薦算法有基于內(nèi)容的推薦[4-5]、協(xié)同過(guò)濾推薦[6-12]和各種混合推薦。協(xié)同過(guò)濾算法作為一種傳統(tǒng)的推薦技術(shù)，由于其簡(jiǎn)單高效的優(yōu)點(diǎn)，越來(lái)越受到人們的青睞。算法的核心是通過(guò)挖掘用戶(hù)的歷史行為數(shù)據(jù)來(lái)發(fā)現(xiàn)用戶(hù)的偏好，根據(jù)不同的偏好將用戶(hù)分組，并將同組的其他用戶(hù)的偏好推薦給用戶(hù)。為了提高查找最近鄰用戶(hù)的準(zhǔn)確性，一些文獻(xiàn)使用K-means聚類(lèi)算法[12]。該算法首先根據(jù)用戶(hù)數(shù)據(jù)本身的特點(diǎn)對(duì)用戶(hù)數(shù)據(jù)進(jìn)行分類(lèi)，然后使用協(xié)同過(guò)濾算法進(jìn)行推薦，這種方法提高了推薦效果。但對(duì)于數(shù)據(jù)較少的新用戶(hù)或不活躍用戶(hù)，仍然無(wú)法降低用戶(hù)群劃分的難度和提高最近鄰集查找的準(zhǔn)確率。然而，協(xié)同過(guò)濾算法在實(shí)際應(yīng)用中仍然面臨著數(shù)據(jù)稀疏性和可擴(kuò)展性等挑戰(zhàn)。許多學(xué)者對(duì)算法提出了多種改進(jìn)方法。近年來(lái)，非負(fù)矩陣分解[13-17]等技術(shù)逐漸被人發(fā)現(xiàn)，由于它自身的一些性質(zhì)(良好的擴(kuò)展性、稀疏性等)可以解決處理大量數(shù)據(jù)并快速準(zhǔn)確的顯示結(jié)果，被學(xué)者廣泛關(guān)注和使用。

本文將從用戶(hù)和項(xiàng)目之間的評(píng)分構(gòu)建用戶(hù)偏好相似度，準(zhǔn)確找到用戶(hù)與用戶(hù)之間的聯(lián)系和用戶(hù)對(duì)項(xiàng)目的興趣，形成項(xiàng)目子矩陣(目標(biāo)用戶(hù))，再利用帶有向量1-范數(shù)和向量2-范數(shù)約束條件的非負(fù)矩陣分解得到未評(píng)分項(xiàng)目的預(yù)測(cè)評(píng)分矩陣，最后將得到的子矩陣聚類(lèi)[18]整合形成我們需要的預(yù)測(cè)評(píng)分，根據(jù)最后的預(yù)測(cè)評(píng)分排序推薦給目標(biāo)用戶(hù)。

1 相關(guān)工作

1.1 構(gòu)建用戶(hù)偏好相似度

Pearson相似度[18]表達(dá)式如下:

1.2 非負(fù)矩陣分解(NMF)

非負(fù)矩陣分解是對(duì)給定一個(gè)非負(fù)矩陣Q，尋找2個(gè)非負(fù)矩陣W和H，使得下列目標(biāo)函數(shù)最小

W表示非負(fù)的基矩陣，H表示非負(fù)的系數(shù)矩陣。矩陣Q中列向量可以表示為：

算法描述：

NMF是一個(gè)帶有約束的非線性?xún)?yōu)化問(wèn)題，問(wèn)題可以簡(jiǎn)單描述為：在約束條件W≥0,H≥0下，找到最優(yōu)矩陣W和H，使得目標(biāo)函數(shù)最小。Lee等[19]利用了最速下降法給出更新迭代規(guī)則，直到算法收斂時(shí)，W和H有最優(yōu)解。

NMF:Step1:任意給定非負(fù)矩陣W和H初始值;Step2:更新迭代矩陣W和H,更新迭代規(guī)則為: Wik←Wik(VHT)ik(WHHT)ik, Hkj←Hkj(WTV)kj(WTWH)kjStep3:重復(fù)Step2,直到算法收斂。

1.3 非負(fù)矩陣分解的稀疏算法(SNMF)

稀疏性：稀疏意味著大多數(shù)元素取值接近于0，而只有少數(shù)元素取非零的值。

迄今為止，文獻(xiàn)中已經(jīng)提出并使用了許多稀疏性度量[20-22]，這些度量是從Rn到R的映射，它量化了一個(gè)向量被壓縮到幾個(gè)分量中，最稀疏的向量(只有1個(gè)分量非零)的稀疏度為1，而所有元素絕對(duì)值相等的向量的稀疏度為0。

接著將使用基于L1范數(shù)和L2范數(shù)之間關(guān)系的稀疏性度量：

(1)

其中n是x的維數(shù)。因?yàn)?/p>

所以0≤sparseness(x)≤1，當(dāng)且僅當(dāng)x僅包含1個(gè)非零向量，結(jié)果為1，當(dāng)且僅當(dāng)所有分量絕對(duì)值相等時(shí)，結(jié)果為0。

另一種定義：

目標(biāo)是使NMF尋找具有所需稀疏度的解決方案。第一個(gè)要回答的問(wèn)題是：到底什么應(yīng)該是稀疏的？基矩陣W還是系數(shù)矩陣H？這是一個(gè)無(wú)法給出一般答案的問(wèn)題，這完全取決于所討論的具體應(yīng)用。所以要約束哪個(gè)(或者兩者都約束，或者都不約束)由實(shí)驗(yàn)者來(lái)選擇。例如，分析疾病模式的醫(yī)生可能會(huì)假設(shè)大多數(shù)疾病是罕見(jiàn)的(因此是稀疏的)，但是每種疾病都會(huì)導(dǎo)致大量的癥狀。假設(shè)癥狀構(gòu)成它的矩陣的行，列表示不同的個(gè)體，在這種情況下，應(yīng)該是“系數(shù)”是稀疏的，“基向量”是不受約束的；另一方面，當(dāng)試圖從圖像數(shù)據(jù)庫(kù)中學(xué)習(xí)有用的特征時(shí)，要求W和H都是稀疏的可能是有意義的，這意味著任何給定的對(duì)象都存在于少數(shù)圖像中，并且只影響圖像的小部分。

在此，介紹一種度量稀疏度的方法，即利用向量2-范數(shù)約束基矩陣W，和向量1-范數(shù)約束系數(shù)矩陣H。得到如下的目標(biāo)函數(shù)：

文[23]對(duì)上述模型提出了非負(fù)矩陣分解的稀疏算法(SNMF)。

SNMF:Step1:任意給定非負(fù)矩陣W和H以及非負(fù)數(shù)的初始值;Step2:更新迭代矩陣W和H,更新迭代規(guī)則為:Wik←Wik(VHT)ik(WHHT)ik-βWikWia←Wia∑WiaHkj←Hkj(WTV)kj(WTWH)kj+λStep3:重復(fù)Step2,直到算法收斂。

文[23]中并沒(méi)有給出SNMF收斂性證明，下面給出SNMF的收斂性證明。

引理1 設(shè)K(ht)是一個(gè)對(duì)角矩陣：

則函數(shù)

(2)

證明當(dāng)h=ht時(shí)，G(h,ht)=G(h,h)=F(h)。若引理1成立，則必須證明：在h≠ht條件下，G(h,ht)≥F(h)成立。

F(h)在ht處的展開(kāi)式為：

(3)

聯(lián)立(2)和(3)兩式，若要證明G(h,ht)≥F(h)成立，即證明不等式：

(h-ht)T[K(ht)-WTW](h-ht)≥0成立。

而為了證明半正定矩陣，我們考慮矩陣Mab(ht)，這個(gè)矩陣是對(duì)稱(chēng)矩陣K-WTW重新調(diào)整后的元素，也即：

此時(shí)，當(dāng)且僅當(dāng)矩陣M滿(mǎn)足半正定時(shí)，K-WTW才是半正定的。

≥0

由以上證明，可以看出G(h,ht)≥F(h)成立，所以引理1中的函數(shù)G(h,ht)是函數(shù)F(h)的輔助函數(shù)。引理1得到證明。

根據(jù)上述引理證明，由于公式(2)是一個(gè)輔助函數(shù)，在這個(gè)更新規(guī)則下，F(xiàn)是不遞增的。通過(guò)互換W和H的角色，在W的更新規(guī)則下，F(xiàn)同樣可以顯示為非遞增。

2 基于SNMF的K-means算法(SNMF-K)

文[12]基于SNMF算法[20]和聚類(lèi)算法給出算法過(guò)程，利用向量1-范數(shù)和向量2-范數(shù)來(lái)稀疏約束非負(fù)矩陣，并對(duì)分解得到的基矩陣W進(jìn)行聚類(lèi)，在此基礎(chǔ)上，本節(jié)基于SNMF算法和K-means算法設(shè)計(jì)帶有向量1-范數(shù)和向量2-范數(shù)稀疏約束非負(fù)矩陣分解的K-means算法有所改進(jìn)，簡(jiǎn)稱(chēng)SNMF-K算法。

SNMF-K: 輸入:數(shù)據(jù)集C,目標(biāo)用戶(hù)id,預(yù)設(shè)的聚類(lèi)數(shù)目k,預(yù)設(shè)輸出的電影個(gè)數(shù)y。輸出:目標(biāo)用戶(hù)的推薦電影名稱(chēng)及個(gè)數(shù)。1)將輸入數(shù)據(jù)集C構(gòu)造成用戶(hù)-項(xiàng)目的評(píng)分矩陣Vm×n,如表1,其中,每一列為一個(gè)數(shù)據(jù)樣本,m表示m個(gè)項(xiàng)目,n表示有n個(gè)用戶(hù)。2)調(diào)用SNMF算法[23]得到稀疏約束NMF后的系數(shù)矩陣H。3)在矩陣Hk×n中隨機(jī)選取k個(gè)中心點(diǎn)進(jìn)行聚類(lèi),計(jì)算歐氏距離,選定新的聚類(lèi)中心,直到中心不再改變,得到聚類(lèi)結(jié)果C?=(C1,C2,…,Ck)。4)確定用戶(hù)id所屬的類(lèi)別,計(jì)算用戶(hù)id與所屬類(lèi)的其它用戶(hù)的相似度關(guān)系。通過(guò)讀取評(píng)分矩陣,得到前y的相似度值和用戶(hù)id矩陣,獲取前y名相似度矩陣,讀取電影數(shù)據(jù),定義好推薦電影的空集和前y名相似度所有電影,可以得到最相似用戶(hù)的評(píng)分矩陣。接著獲取此用戶(hù)評(píng)價(jià)為5分的最高的電影評(píng)分矩陣,從而得到電影名。最后追加電影名到先前定義好的空集中,去重,防止y個(gè)最相似用戶(hù)推薦的電影有重復(fù)。5)輸出目標(biāo)用戶(hù)id的y個(gè)推薦電影名稱(chēng)。

該算法的優(yōu)勢(shì)在于調(diào)用SNMF算法后，對(duì)系數(shù)矩陣H進(jìn)行聚類(lèi)，可以快速得到最相似用戶(hù)的評(píng)分矩陣，并且快速計(jì)算得到結(jié)果。

表1 用戶(hù)-項(xiàng)目評(píng)分矩陣

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

3.1 實(shí)驗(yàn)數(shù)據(jù)的選取

實(shí)驗(yàn)數(shù)據(jù)是從Movielens電影評(píng)分?jǐn)?shù)據(jù)集[24]中選取兩組數(shù)據(jù)集，這兩組數(shù)據(jù)集是個(gè)性化推薦系統(tǒng)研究者的最常用的數(shù)據(jù)集。數(shù)據(jù)包括用戶(hù)個(gè)數(shù)、電影數(shù)目和相對(duì)應(yīng)用戶(hù)的評(píng)分。評(píng)分表示用戶(hù)對(duì)電影的喜愛(ài)程度，評(píng)分越高，喜愛(ài)程度越高。

3.2 改進(jìn)后的推薦算法的評(píng)價(jià)指標(biāo)

推薦系統(tǒng)中對(duì)推薦算法的誤差評(píng)價(jià)指標(biāo)有很多種，都是計(jì)算真實(shí)值和預(yù)測(cè)值之間的誤差，評(píng)價(jià)指標(biāo)的數(shù)值越小，預(yù)測(cè)值就越準(zhǔn)確。本文采取3種基本的指標(biāo)：均方誤差(MSE)、平方絕對(duì)值誤差(MAE)和均方根誤差(RMSE)。具體公式如下：

均方誤差(MSE)：

平方絕對(duì)值誤差(MAE)：

均方根誤差(RMSE)：

均方根誤差是均方誤差的算術(shù)平方根。換句話(huà)說(shuō)，是觀測(cè)值與真值(或模擬值)偏差(而不是觀測(cè)值與其平均值之間的偏差)的平方與觀測(cè)次數(shù)T比值的平方根。在實(shí)際測(cè)量中，觀測(cè)次數(shù)T總是有限的，真值只能用最佳值來(lái)代替。標(biāo)準(zhǔn)誤差對(duì)一組測(cè)量中的特大或特小誤差反映非常敏感，所以，標(biāo)準(zhǔn)誤差能夠很好地反映出測(cè)量的精密度。因此，標(biāo)準(zhǔn)差是用來(lái)衡量一組數(shù)自身的離散程度，而均方根誤差是用來(lái)衡量觀測(cè)值同真值之間的偏差。

對(duì)K-means算法與SNMF-K算法的聚類(lèi)結(jié)果進(jìn)行對(duì)比分析，用分類(lèi)準(zhǔn)確率來(lái)對(duì)聚類(lèi)結(jié)果進(jìn)行評(píng)價(jià)，分類(lèi)準(zhǔn)確率公式為：

式中：k為聚類(lèi)的個(gè)數(shù)，i為正確聚類(lèi)時(shí)對(duì)應(yīng)類(lèi)別中樣本的個(gè)數(shù)，n為樣本總數(shù)。顯然，CA的值越大，表明聚類(lèi)結(jié)果越好。其中RMSE越小表示模型推薦更加準(zhǔn)確，性能更好。相反RMSE越大表示推薦與真實(shí)情況差距越大，性能越差。

通過(guò)對(duì)兩組數(shù)據(jù)集對(duì)比的算法包括基于非負(fù)矩陣分解的推薦算法(NMF)、基于稀疏約束的非負(fù)矩陣分解的算法(SNMF)和SNMF-K算法。

第1組實(shí)驗(yàn)：

第1組數(shù)據(jù)包括943個(gè)用戶(hù)、1 682部電影以及用戶(hù)對(duì)看過(guò)的電影的評(píng)分。評(píng)分由1～5組成，并且利用公式(1)可得到該數(shù)據(jù)集的稀疏度為0.94。第一組數(shù)據(jù)集對(duì)比實(shí)驗(yàn)結(jié)果見(jiàn)圖1。從圖1中可看出，對(duì)于所取數(shù)據(jù)算法SNMF-K比NMF和SNMF具有較小的誤差。

圖1 第1組數(shù)據(jù)集對(duì)比實(shí)驗(yàn)結(jié)果

表2是迭代次數(shù)K值為90時(shí)，測(cè)試兩種推薦算法的性能的差異。由表2看出，迭代次數(shù)K值為10的條件下，SNMF-K算法在原來(lái)的基礎(chǔ)上，誤差減少了3.4%。當(dāng)K值達(dá)到90左右時(shí)，算法的推薦性能最佳。

表2 第1組數(shù)據(jù)不同K值對(duì)兩種算法RMSE的影響

第2組實(shí)驗(yàn)：

第2組數(shù)據(jù)包括1 024個(gè)用戶(hù)、2 316部電影以及用戶(hù)對(duì)看過(guò)的電影的評(píng)分。評(píng)分由1～5組成，并且利用公式(1)可得到該數(shù)據(jù)集的稀疏度為0.96。第2組數(shù)據(jù)集對(duì)比實(shí)驗(yàn)結(jié)果見(jiàn)圖2，圖2表明算法SNMF-K比NMF和SNMF具有較小的誤差。

圖2 第2組數(shù)據(jù)集對(duì)比實(shí)驗(yàn)結(jié)果

表3是迭代次數(shù)K值為100時(shí)，測(cè)試兩種推薦算法的性能的差異。由表3看出，迭代次數(shù)K值為10的條件下，SNMF-K算法在原來(lái)的基礎(chǔ)上，誤差減少了3.2%。當(dāng)K值達(dá)到100左右時(shí)，算法的推薦性能最佳。

表3 第2組數(shù)據(jù)不同K值對(duì)兩種算法RMSE的影響

通過(guò)兩組實(shí)驗(yàn)結(jié)果，可以看出，提出的SNMF-K算法在3個(gè)指標(biāo)都優(yōu)于其他兩種算法。實(shí)驗(yàn)表明所提出的算法具有良好的性能。

4 結(jié)論

本文提出了非負(fù)矩陣分解的稀疏模型。該模型通過(guò)稀疏得到的用戶(hù)評(píng)分矩陣，利用用戶(hù)偏好相似度對(duì)用戶(hù)進(jìn)行聚類(lèi)，從而最后獲得相似度矩陣，改進(jìn)后的算法在誤差上至少減少了3.2%，優(yōu)化了最后的推薦性能。