陳輝,王鍇鉞

(安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001)

大數(shù)據(jù)時(shí)代，由于互聯(lián)網(wǎng)和電子商務(wù)的信息量大、種類多、更新速度快，導(dǎo)致了信息超載問(wèn)題。不斷發(fā)展和尋找新的技術(shù)來(lái)與用戶進(jìn)行互動(dòng)、交流和提供個(gè)性化的體驗(yàn)，增加瀏覽量、銷售量并留住用戶是非常重要的。然而，搜索引擎只能被動(dòng)地接受命令和執(zhí)行命令，為用戶挖掘感興趣的信息并不是獨(dú)立的、主動(dòng)的。于是，利用數(shù)據(jù)的力量來(lái)預(yù)測(cè)用戶興趣的推薦系統(tǒng)(RS)得到了大量關(guān)注。在用戶不主動(dòng)搜索的情況下，RS可以根據(jù)已有數(shù)據(jù)將某些項(xiàng)目精確地推薦給有此需求的用戶，幫助用戶應(yīng)對(duì)信息超載難題，提高信息的有效利用。但RS面臨數(shù)據(jù)稀疏性、冷啟動(dòng)、負(fù)面評(píng)價(jià)影響、評(píng)分情緒傾向、商家信任度評(píng)價(jià)等問(wèn)題。

目前，RS已廣泛應(yīng)用于各個(gè)行業(yè)，不同的應(yīng)用行業(yè)采用的推薦方法同源異流?；趨f(xié)同過(guò)濾的推薦系統(tǒng)(CF)應(yīng)用最為廣泛[1]，它是一種通過(guò)從其他類似用戶或項(xiàng)目中收集評(píng)價(jià)信息來(lái)自動(dòng)預(yù)測(cè)用戶傾向的技術(shù)。以CF算法為基礎(chǔ)，針對(duì)用戶傾向相似度問(wèn)題，很多學(xué)者對(duì)其進(jìn)行了進(jìn)一步研究和改進(jìn)。Polatidis 等[2]提出了基于協(xié)同過(guò)濾的多層推薦算法，在衡量相似度時(shí)，對(duì)相似性進(jìn)行排序并分成不同等級(jí)，每個(gè)等級(jí)增加相應(yīng)的限制條件以此來(lái)增加相似度衡量的準(zhǔn)確性。王付強(qiáng)等[3]提出了一種基于位置的非對(duì)稱相似性度量的協(xié)同過(guò)濾推薦算法(LBASCF)，將余弦相似性與基于位置的相似性融合，得到一個(gè)新的非對(duì)稱用戶相似性。Suryakant等[4]考慮了用戶的評(píng)分習(xí)慣，提出一種基于均值散度度量相似性的計(jì)算方法，將余弦相似性(COS)、Jaccard相似性和MMD[5]相似性算法相結(jié)合，計(jì)算總體相似度。于金明等[6]提出了一種基于評(píng)分相似性和結(jié)構(gòu)相似性兩部分構(gòu)成的新的項(xiàng)目相似度量方法，但只考慮聯(lián)合評(píng)分用戶對(duì)相似度的影響[6]。肖文強(qiáng)等[7]在相似度計(jì)算中,分別引入了物品時(shí)間差、流行物品權(quán)重以及用戶共同評(píng)分權(quán)重來(lái)提高相似度度量的準(zhǔn)確性。Li等[8]提出一種改進(jìn)相似度和遺忘曲線相結(jié)合的推薦算法，計(jì)算用戶之間的相似度時(shí)，考慮了具有共同分?jǐn)?shù)項(xiàng)目的數(shù)量對(duì)相似度的影響，提高了相似用戶集合的準(zhǔn)確性。Fu等[9]考慮了部分用戶的個(gè)性化需求，結(jié)合K-means聚類方法，采用基于社區(qū)因子的計(jì)算方法代替?zhèn)鹘y(tǒng)的相似度計(jì)算方法，提高推薦精度。Jiang 等[10]提出了一種基于可信數(shù)據(jù)和用戶相似度融合的slope one算法，將改進(jìn)后的相似度算法與slope one算法的權(quán)值相加，得到最終的推薦結(jié)果。

由于矩陣分解模型具有良好的可擴(kuò)展性和較強(qiáng)的理論基礎(chǔ)，在基于模型的推薦系統(tǒng)中得到了廣泛的應(yīng)用,許多學(xué)者從不同的角度對(duì)其進(jìn)行了建模。Forsati等[11]介紹了一種基于社交排名的協(xié)同過(guò)濾模型PushTrust，從用戶的社交環(huán)境中提取用戶的潛在特征并進(jìn)行排名，能夠同時(shí)利用信任、不信任和中立關(guān)系，將其整合到矩陣分解算法中。Yang等[12]提出了基于概率矩陣分解的TrustPMF推薦模型，該模型對(duì)基于矩陣因子分解的社會(huì)推薦模型提供了概率解釋，整合用戶評(píng)分?jǐn)?shù)據(jù)和這些用戶之間的社會(huì)信任網(wǎng)絡(luò)來(lái)提高推薦的性能。Xu[13]提出了一種基于矩陣分解的結(jié)合社會(huì)信息和物品關(guān)系的推薦算法，對(duì)物品的特征信息進(jìn)行正則化約束，在矩陣分解和降維過(guò)程中保持?jǐn)?shù)據(jù)特征的穩(wěn)定性。

然而，由于CF的性質(zhì)，評(píng)分矩陣過(guò)于稀疏是基于該技術(shù)的推薦系統(tǒng)存在的關(guān)鍵性問(wèn)題，如商業(yè)推薦系統(tǒng)的可用評(píng)分信息密度通常不到1%[14]。傳統(tǒng)的計(jì)算相似性的方法，如余弦相似性(COS)、修正余弦相似性(ACOS)、皮爾遜相關(guān)系數(shù)(PCC)以及約束皮爾遜相關(guān)系數(shù)(CPC)[15]等都是針對(duì)用戶間的聯(lián)合評(píng)分來(lái)進(jìn)行相似用戶查找的,在面對(duì)稀疏的數(shù)據(jù)集上顯得力不從心。同時(shí)，幾乎所有基于內(nèi)容和基于模型的CF算法都無(wú)法處理從未對(duì)任何項(xiàng)目進(jìn)行評(píng)分的用戶[16]。但事實(shí)上，現(xiàn)實(shí)生活中產(chǎn)生的數(shù)據(jù)是龐大且稀疏的，大部分用戶的評(píng)分都低于20項(xiàng)，這使得用戶之間缺少聯(lián)合評(píng)分，由此計(jì)算的推薦結(jié)果準(zhǔn)確率較低。從這個(gè)角度來(lái)看，傳統(tǒng)的忽略非聯(lián)合評(píng)分項(xiàng)的推薦系統(tǒng)可能不再適用。

為了提高傳統(tǒng)協(xié)同過(guò)濾算法的效果，本文利用KL散度計(jì)算用戶間的聯(lián)合評(píng)分項(xiàng)以及非聯(lián)合評(píng)分項(xiàng)，充分利用評(píng)價(jià)信息找到信任度較高的同傾向用戶，提出一種運(yùn)用用戶信任度正則項(xiàng)約束概率矩陣分解模型的推薦算法。該算法通過(guò)在概率矩陣分解模型(PMF)[17]中加入用戶信任度正則項(xiàng)，緩解推薦系統(tǒng)冷啟動(dòng)以及稀疏性問(wèn)題，通過(guò)實(shí)驗(yàn)逐步建立改進(jìn)算法所涉及的不同參數(shù)值，并在MovieLens 1M和Epinions數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)。

1 相關(guān)工作

1.1 評(píng)分矩陣

在CF中給用戶的建議取決于兩種收集用戶傾向信息的方式，一種是顯式反饋信息，即用戶對(duì)該項(xiàng)目的評(píng)分；另一種是隱式反饋信息，即瀏覽網(wǎng)頁(yè)次數(shù)、購(gòu)買次數(shù)等，與該用戶喜好相似的其他用戶對(duì)該項(xiàng)目的評(píng)分也屬于隱式反饋的一種。用戶對(duì)項(xiàng)目的評(píng)分可以用一個(gè)用戶-項(xiàng)目矩陣來(lái)表示，矩陣中的每個(gè)項(xiàng)表示各個(gè)用戶對(duì)各個(gè)項(xiàng)目的傾向值。

假設(shè)U={u1,u2,…,um}是一個(gè)用戶集，I={i1,i2,…,in}是一個(gè)項(xiàng)目集，所有用戶對(duì)所有項(xiàng)目的評(píng)分構(gòu)成評(píng)分矩陣，見(jiàn)表1。

表1 用戶-項(xiàng)目評(píng)分矩陣Tab.1 User-item rating matrix

表1中，rui表示用戶u對(duì)項(xiàng)目i的評(píng)分，代表用戶的傾向程度。如果用戶u對(duì)項(xiàng)目i沒(méi)有進(jìn)行評(píng)分，則rui=0。實(shí)際上，用戶-項(xiàng)目矩陣非常稀疏，它意味著矩陣中有許多項(xiàng)的值為0。為了克服這一問(wèn)題，本文運(yùn)用PMF算法對(duì)用戶-項(xiàng)目矩陣進(jìn)行隱式反饋信息的尋找，并且考慮用戶間的信任度，通過(guò)KL散度相似性算法尋找傾向程度相似的用戶，設(shè)計(jì)規(guī)范化項(xiàng)來(lái)約束目標(biāo)函數(shù)，提高推薦系統(tǒng)的準(zhǔn)確率。

1.2 概率矩陣分解模型

PMF是基于模型的CF推薦算法的一種，將高維的評(píng)價(jià)矩陣降維，得到用戶隱藏特征矩陣和項(xiàng)目隱藏特征矩陣，通過(guò)計(jì)算二者的內(nèi)積對(duì)評(píng)價(jià)矩陣的缺失值進(jìn)行進(jìn)一步的預(yù)測(cè)。

給定一個(gè)m×n評(píng)價(jià)矩陣R，采用秩為d的兩個(gè)低維矩陣U、V來(lái)擬合，擬合式為

R≈UVT，

(1)

式中：U∈m×d；V∈d×n，d≤min{m,n}；U代表每個(gè)用戶對(duì)d種特征的傾向程度；V代表d種特征在每一個(gè)項(xiàng)目中的存在程度。

p(R|U,V,σ2)=

(2)

(3)

2 融合用戶信任度的概率矩陣分解推薦算法

2.1 基于KL散度的相似性計(jì)算

相似性計(jì)算在CF中處于重要地位，常用的相似性度量方法無(wú)法完整地利用評(píng)分信息，只考慮了用戶間的聯(lián)合評(píng)分項(xiàng)，不適宜處理非線性的情況。但在實(shí)際生活中，極度稀疏的數(shù)據(jù)集上的聯(lián)合評(píng)分項(xiàng)較為匱乏，利用傳統(tǒng)算法尋找相似用戶會(huì)出現(xiàn)誤差，影響推薦結(jié)果。

KL散度(kullback-leibler divergence) 是一種廣泛應(yīng)用于評(píng)價(jià)兩種概率分布差異的度量方法[18]，若兩個(gè)對(duì)象分別服從兩個(gè)相同或不同的概率分布，使用 KL散度能高效地區(qū)分重疊現(xiàn)象較為嚴(yán)重的對(duì)象。因此，本文綜合用戶間的聯(lián)合評(píng)分項(xiàng)以及非聯(lián)合評(píng)分項(xiàng)，利用KL散度的優(yōu)勢(shì)提出項(xiàng)目相似度計(jì)算模型。

在評(píng)分矩陣中，可將所有用戶對(duì)某兩個(gè)項(xiàng)目i和j的評(píng)分看成兩個(gè)離散數(shù)組，替換KL散度公式中的概率密度函數(shù)，得到i與j的KL距離計(jì)算公式為

(4)

兩項(xiàng)目間的相似性計(jì)算公式為

(5)

雖然KL 距離是非對(duì)稱的，但在評(píng)分矩陣中，運(yùn)用項(xiàng)目i所有評(píng)價(jià)信息來(lái)近似項(xiàng)目j所得的誤差和運(yùn)用項(xiàng)目j的所有評(píng)價(jià)信息來(lái)近似項(xiàng)目i所得的誤差具有相同的意義。所以，采用式(6)代替式(5)中的D(i,j):

Ds(i,j)=(D(i,j)+D(j,i))/2,

(6)

則項(xiàng)目i和項(xiàng)目j的KL相似度改寫為

(7)

用戶對(duì)某個(gè)項(xiàng)目的傾向程度會(huì)受到相似用戶的影響，也就是說(shuō)，用戶的特征向量與他的相似用戶差別不大。對(duì)基于KL散度的相似性計(jì)算結(jié)果進(jìn)行排序，來(lái)獲得用戶間的信任度排名，得到用戶的前K個(gè)相似用戶。設(shè)用戶u，v對(duì)項(xiàng)目i，j評(píng)分為(rui,-)和(-,rvj)，沒(méi)有聯(lián)合評(píng)分項(xiàng)，在極度稀疏的評(píng)分矩陣中這樣的問(wèn)題屢見(jiàn)不鮮，為此，利用稀疏數(shù)據(jù)集中普遍存在的非聯(lián)合評(píng)分項(xiàng)，計(jì)算用戶u和用戶v的信任度：

(8)

2.2 基于用戶信任度的概率矩陣分解模型

為用戶推薦的項(xiàng)目應(yīng)該與用戶的傾向程度越接近越好，而相似的用戶之間具有相似的傾向程度。基于這一假設(shè)，在計(jì)算用戶信任度時(shí)利用KL散度，從中選擇信任度最大的K個(gè)相似用戶，并在矩陣分解過(guò)程中保持這種聯(lián)系，使得相似用戶間的特征向量更加接近，并且可以根據(jù)信任度的不同而對(duì)不同用戶區(qū)別對(duì)待。因此，在式(3)的損失函數(shù)中加入一個(gè)正則項(xiàng)：

(9)

式中：K(u)表示用戶u的前K個(gè)最為相似的用戶；Uf表示用戶的第f個(gè)相似用戶的特征向量；α表示用戶相似度正則系數(shù)。該正則項(xiàng)表示相似用戶間的信任度差距，最小化目標(biāo)函數(shù)使它們之間的差距最小，使得用戶特征向量更加貼近其相似用戶的特征向量。得到如下模型：

(10)

目標(biāo)函數(shù)局部最小值采用隨機(jī)梯度下降法求得，對(duì)式(10)中Uu和Vi的偏導(dǎo)數(shù)如下：

(11)

(12)

參數(shù)更新方式：

(13)

(14)

式中β為學(xué)習(xí)速率，選取的值太大會(huì)導(dǎo)致迭代結(jié)果發(fā)散，越來(lái)越偏離最小值；β越小雖然會(huì)得到更精確的結(jié)果，但是時(shí)間代價(jià)太大，因此需進(jìn)行實(shí)驗(yàn)，選擇合適的學(xué)習(xí)速率。

2.3 算法描述

利用2.1節(jié)中用戶信任度計(jì)算和2.2節(jié)中的PMF模型，得到融合KL散度用戶信任度計(jì)算的概率矩陣分解協(xié)同過(guò)濾推薦算法(MDCF-KL) 偽代碼如下：

Algorithm1 MDCF-KL算法 Input:用戶-項(xiàng)目評(píng)分矩陣,正則化參數(shù)α、λ和η,最大迭代次數(shù)H,學(xué)習(xí)速率β,特征向量維度d,相似用戶數(shù)量K以及推薦項(xiàng)目數(shù)量N。Output:用戶隱藏特征矩陣U,項(xiàng)目隱藏特征矩陣V,預(yù)測(cè)評(píng)分值Pre_R以及N個(gè)推薦項(xiàng)目。Initialize:隨機(jī)初始化U、V(σ2=1的標(biāo)準(zhǔn)正態(tài)分布),根據(jù)3.3節(jié)中表3設(shè)置參數(shù)值。1.forv<=mdo2.fori<=ndo3.forj<=ndo4.calculateKL(i,j)5.calculateS(u,v)6.endfor7.endfor8.N[v]=S(u,v)9.endfor10.Sim-K=sorted(N[v],num=K)11.forh<=Hdo12.forallrui∈Rdo13.Uu←Uu-β?L?Uu14.Vi←Vi-β?L?Vi15.endfor16.h=h+117.endfor18.Pre_R=U?V19.Top-N=sorted(Pre_R[u][],num=N)

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

3.1 數(shù)據(jù)集

本文實(shí)驗(yàn)采用的數(shù)據(jù)集為MovieLens1M和Epinions。MovieLens1M只允許對(duì)自己看過(guò)的電影進(jìn)行評(píng)分，分值在1～5之間。在這組數(shù)據(jù)中，每個(gè)人至少給20部電影打分，電影包括19種類型。Epinions涵蓋了分布在美國(guó)和歐洲的消費(fèi)者對(duì)商品的評(píng)價(jià)。數(shù)據(jù)集的具體信息見(jiàn)表2。

表2 數(shù)據(jù)集信息Tab.2 Datasets information

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

在對(duì)算法性能和有效性進(jìn)行評(píng)價(jià)時(shí)，采用平均絕對(duì)誤差(MAE)、準(zhǔn)確率(Precision)和召回率(Recall)三種指標(biāo)，計(jì)算表達(dá)式為：

(15)

(16)

(17)

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

為了得到理想的對(duì)比結(jié)果，本文根據(jù)參考文獻(xiàn)推薦的參數(shù)值以及參數(shù)調(diào)優(yōu)的結(jié)果選擇最優(yōu)實(shí)驗(yàn)參數(shù)，實(shí)驗(yàn)參數(shù)設(shè)置見(jiàn)表3。

表3 參數(shù)設(shè)置Tab.3 Parameter settings

MDCF-KL算法和HITUCF[8]、ICCF[9]以及trust-CF[10]三種對(duì)比算法在MovieLens1M和Epinions兩個(gè)數(shù)據(jù)集上的MAE測(cè)試效果如圖1所示。

(a)MovieLens 1M數(shù)據(jù)集

(b)Epinions數(shù)據(jù)集圖1 兩種數(shù)據(jù)集上MAE比較Fig.1 Comparison of MAE values on two datasets

從圖1可以看出，隨著相似用戶數(shù)量的增加，四種算法的曲線都呈下降走向，而且逐步趨于平緩。在MovieLens1M數(shù)據(jù)集上trust-CF、ICCF在相似用戶數(shù)量為70時(shí)達(dá)到最優(yōu)值，MDCF-KL、HITUCF在相似用戶數(shù)量為50時(shí)更快地達(dá)到最優(yōu)值，MDCF-KL算法相比較于其他三種算法平均絕對(duì)誤差明顯減少。在Epinions數(shù)據(jù)集上ICCF與其他三種算法有較大差距，主要原因是ICCF算法過(guò)于追求用戶的個(gè)性化需求，導(dǎo)致符合條件可以參與計(jì)算的評(píng)分項(xiàng)目極其稀少，不適用于更為稀疏的數(shù)據(jù)集。其他三種算法的平均絕對(duì)誤差雖然有所增加，但仍能保持一個(gè)相對(duì)良好的性能，尤其是MDCF-KL算法，能通過(guò)非聯(lián)合評(píng)分項(xiàng)判斷相似用戶并結(jié)合概率矩陣分解，在較為稀疏的Epinions數(shù)據(jù)集上更有優(yōu)勢(shì)。

為了進(jìn)一步驗(yàn)證MDCF-KL算法的有效性，分別在MovieLens1M和Epinions數(shù)據(jù)集上針對(duì)不同相似用戶數(shù)量，采用召回率和準(zhǔn)確率兩個(gè)指標(biāo)對(duì)各算法的表現(xiàn)進(jìn)行實(shí)驗(yàn)比較，如圖2、圖3所示。

(a)準(zhǔn)確率比較

(b)召回率比較圖2 MovieLens 1M數(shù)據(jù)集上準(zhǔn)確率和召回率比較Fig.2 Comparison of precision and recall on MovieLens 1M dataset

從圖2可以看出，在MovieLens1M這個(gè)評(píng)分矩陣密度相對(duì)較高的數(shù)據(jù)集上，MDCF-KL、HITUCF和trust-CF的準(zhǔn)確率和召回率較為相近，相似用戶數(shù)量少于30時(shí)，三種算法表現(xiàn)各有優(yōu)劣，但在相似用戶數(shù)量為40時(shí)，MDCF-KL準(zhǔn)確率得到了最優(yōu)結(jié)果。隨著相似用戶取值逐漸增加，推測(cè)出的用戶喜歡物品范圍越來(lái)越小，導(dǎo)致MDCF-KL召回率下降，但仍然優(yōu)于其他三種算法。

(a)準(zhǔn)確率比較

(b)召回率比較圖3 Epinions數(shù)據(jù)集上準(zhǔn)確率和召回率比較Fig.3 Comparison of precision and recall on Epinions dataset

從圖3可以看出，Epinions數(shù)據(jù)集上，隨著數(shù)據(jù)稀疏程度增大，MDCF-KL算法在相似用戶數(shù)量小于40時(shí)，準(zhǔn)確率相比較于其他三種算法有明顯的提高，并在相似用戶數(shù)量達(dá)到60時(shí)準(zhǔn)確率和召回率取得最優(yōu)結(jié)果。這是由于本文算法充分考慮了非聯(lián)合評(píng)分項(xiàng)，增加了評(píng)分的利用率，在面對(duì)更為稀疏的數(shù)據(jù)集時(shí)有著較為明顯的優(yōu)勢(shì)。

4 結(jié)束語(yǔ)

為了解決冷啟動(dòng)以及數(shù)據(jù)稀疏的問(wèn)題，本文將用戶非聯(lián)合評(píng)分引入PMF推薦系統(tǒng)，提出了一種基于概率矩陣分解和正則約束用戶信任度關(guān)系的算法。通過(guò)對(duì)MovieLens1M以及Epinions數(shù)據(jù)集的實(shí)驗(yàn)分析表明，MDCF-KL方法能有效提升推薦性能，并且在更稀疏的Epinions數(shù)據(jù)集上取得了明顯成效。在下一步的研究工作中，將會(huì)考慮需求中的長(zhǎng)尾效應(yīng)，挖掘零散、個(gè)性化但數(shù)量極大的尾部需求；利用拉普拉斯等分布來(lái)更有效地?cái)M合潛在特征向量，貼合實(shí)際情況，提高長(zhǎng)尾項(xiàng)目建模的能力。