基于協(xié)同過(guò)濾和隱語(yǔ)義模型的混合推薦算法

徐 吉，李小波，陳華輝，許 浩

(1.寧波大學(xué) 信息科學(xué)與工程學(xué)院，浙江 寧波 315211；2.麗水學(xué)院 工學(xué)院，浙江 麗水 323000)

0 引 言

隨著互聯(lián)網(wǎng)的發(fā)展，人們獲取信息的方式愈加豐富，海量信息在滿足需求的同時(shí)，也為人們帶來(lái)一些困擾。大量信息中的無(wú)效信息一方面干擾了人們對(duì)正常信息的判斷，另一方面也降低了人們對(duì)信息的處理效率[1]。協(xié)同過(guò)濾算法[2]一般根據(jù)用戶的評(píng)價(jià)信息來(lái)推測(cè)用戶的喜好，但受到數(shù)據(jù)稀疏問(wèn)題[2-3]的影響，很多時(shí)候無(wú)法得到較為理想的推薦結(jié)果；除此之外，一般協(xié)同推薦算法忽略了用戶興趣的動(dòng)態(tài)變化；文中對(duì)傳統(tǒng)協(xié)同過(guò)濾算法存在的上述問(wèn)題進(jìn)行了研究，并提出了改進(jìn)后的協(xié)同過(guò)濾混合推薦推薦算法，用以解決上述問(wèn)題。

就目前的現(xiàn)狀來(lái)看，用的最多的當(dāng)屬協(xié)同過(guò)濾算法，它的突出缺點(diǎn)就在于解決數(shù)據(jù)稀疏性上表現(xiàn)不佳，導(dǎo)致在數(shù)據(jù)稀疏時(shí)，推薦性能大打折扣。LFM算法[3]是一種協(xié)同濾波算法，但是建立在模型的基礎(chǔ)之上，而經(jīng)過(guò)改進(jìn)的LFM在緩和稀疏性問(wèn)題上有一定的作用，但是它進(jìn)行降維處理時(shí)容易造成數(shù)據(jù)的丟失[4]。傳統(tǒng)的推薦算法已經(jīng)無(wú)法再產(chǎn)生較為精準(zhǔn)的模型數(shù)據(jù)，究其緣由，很大一部分是由于算法的局限性，當(dāng)然，也不排除和數(shù)據(jù)本身的差異性有關(guān)。當(dāng)前越來(lái)越多的推薦系統(tǒng)會(huì)選擇融合多種策略，將各種算法的優(yōu)點(diǎn)整合到一起，以克服單一算法的局限。

1 協(xié)同過(guò)濾算法

1.1 相似度計(jì)算方法

對(duì)于協(xié)同過(guò)濾算法來(lái)說(shuō)，其最關(guān)鍵的內(nèi)容是對(duì)用戶或者是項(xiàng)目間的相似度進(jìn)行計(jì)算[5]。在這個(gè)過(guò)程中可以采用不同的計(jì)算方法，下面對(duì)其中幾種比較典型的方法進(jìn)行介紹。

(1)Pearson相關(guān)系數(shù)法。

當(dāng)前在推薦算法中已經(jīng)較多地使用了Pearson相關(guān)系數(shù)法[6-7]對(duì)用戶或者項(xiàng)目間的相似關(guān)系進(jìn)行計(jì)算，具體如下所示：

(2)余弦相似度法[8-10]。

(2)

在實(shí)際中不同的用戶間往往存在明顯的差異性，各個(gè)用戶的評(píng)價(jià)標(biāo)準(zhǔn)也不相同。改進(jìn)的余弦相似度[9]公式如下所示：

(3)

(3)Jaccard相關(guān)系數(shù)法[8,10]。

在很多情況下主體的特征屬性值并不是連續(xù)的，在這些情形下無(wú)法直接對(duì)其相似度進(jìn)行衡量，而是需要采用一些特殊的符號(hào)進(jìn)行描述。有學(xué)者提出了Jaccard相關(guān)系數(shù)法，其公式如下所示：

(4)

對(duì)于此類問(wèn)題可以采用1/-1代表用戶喜歡/不喜歡，0代表未標(biāo)注，可以將用戶U，V間的Jaccard相關(guān)系數(shù)計(jì)算公式表示為：

(5)

其中，ui表示用戶u對(duì)項(xiàng)目i形成的標(biāo)注，1{*}表示指示函數(shù)。

1.2 改進(jìn)的項(xiàng)目相似度計(jì)算方法

相似度計(jì)算結(jié)果的準(zhǔn)確性比較依賴于數(shù)據(jù)量的大小，如果數(shù)據(jù)量較小，往往難以得到較好的效果。這些方法也比較容易受到數(shù)據(jù)稀疏性的影響，這必然會(huì)造成相似度計(jì)算結(jié)果的不準(zhǔn)確。可以采用合理的方式對(duì)其相似度計(jì)算方法進(jìn)行優(yōu)化，如果兩個(gè)項(xiàng)目間沒有共同評(píng)分項(xiàng)目，此時(shí)無(wú)法直接對(duì)兩個(gè)主體間的相似度進(jìn)行計(jì)算，其中的稀疏評(píng)分矩陣即如表1中所示。

表1 稀疏評(píng)分矩陣

通過(guò)表中數(shù)據(jù)可以明顯地看到，項(xiàng)目a，b不存在共同評(píng)分用戶，因此難以直接對(duì)項(xiàng)目a，b的相似度進(jìn)行計(jì)算。經(jīng)過(guò)分析可以發(fā)現(xiàn)出現(xiàn)這種問(wèn)題的主要原因是數(shù)據(jù)的稀疏性。在表1中雖然沒有直接對(duì)項(xiàng)目a，b共同評(píng)分的用戶，但可以發(fā)現(xiàn)其他項(xiàng)目與a之間含有一些共同評(píng)分用戶，其中的一些項(xiàng)目與b也有明顯的相似度關(guān)系。此時(shí)可以根據(jù)項(xiàng)目a與其余項(xiàng)目間的相似度關(guān)系構(gòu)建可信模型，然后可以間接得到項(xiàng)目a與項(xiàng)目b間的相似度關(guān)系。在表中可以發(fā)現(xiàn)c，d，e，f和a都含有可信關(guān)系，并且與b也有一定的相似性，因此可以通過(guò)間接的方式得到二者的相似度，具體的傳遞方式是b->f->a，b->e->a。

1.3 可信關(guān)系建模

首先是根據(jù)項(xiàng)目來(lái)進(jìn)行可信關(guān)系建模，然后將其應(yīng)用到相似度的傳遞過(guò)程中。在日常生活中當(dāng)有人向你推薦他信任的物品時(shí)，你會(huì)有較高的可能性去接受這種推薦，因此人們之間存在一定的信任關(guān)系。在對(duì)協(xié)同過(guò)濾算法進(jìn)行設(shè)計(jì)時(shí)可以考慮這種信任關(guān)系，然后將其應(yīng)用到信任網(wǎng)絡(luò)的構(gòu)建中。然后可以進(jìn)行可信關(guān)系建模并完成對(duì)相似度的傳遞。基于上述方式能夠?qū)崿F(xiàn)對(duì)間接相似度的計(jì)算。

由于大量的用戶可能會(huì)對(duì)這兩個(gè)項(xiàng)目進(jìn)行評(píng)分，各個(gè)用戶的評(píng)分存在一定的差異性，如果這種差異性不明顯，這說(shuō)明推薦的效果比較好。一般可以將用戶對(duì)項(xiàng)目的評(píng)分情況設(shè)置一個(gè)閾值，當(dāng)用戶的評(píng)分在閾值范圍內(nèi)時(shí)，即認(rèn)為項(xiàng)目之間存在較為可靠的信任關(guān)系。

準(zhǔn)確推薦的含義可以表述為：用戶a，b都對(duì)項(xiàng)目i進(jìn)行評(píng)分，并且其評(píng)分結(jié)果在閾值θ之內(nèi)。準(zhǔn)確度可以表示為如下公式：

Success(a,b,i)?|Ra,i-Rb,i|≤θ

(6)

根據(jù)相同的定義，當(dāng)用戶u對(duì)兩個(gè)項(xiàng)目i,j都評(píng)分，而用戶a對(duì)項(xiàng)目i進(jìn)行評(píng)分，此時(shí)可以將正確推薦的公式表示為：

Success(i,j,u)?|Ru,i-Ru,i|≤θ

(7)

項(xiàng)目j可以正確推薦項(xiàng)目i的集合如下所示：

SuccessSet(i,j)={(u,v,i):success(u,v,i)}

(8)

項(xiàng)目間的信任關(guān)系可以表示為：

(9)

基于先前的分析可知，正確推薦所占據(jù)的比例對(duì)存在明顯的影響。此外，信任關(guān)系還與其自身可靠性相關(guān)。但是還需要注意一個(gè)問(wèn)題，即當(dāng)其權(quán)重和用戶的評(píng)分?jǐn)?shù)目是正相關(guān)關(guān)系時(shí)，會(huì)導(dǎo)致評(píng)分?jǐn)?shù)目多的項(xiàng)目受到更大的影響，此時(shí)應(yīng)該使用一個(gè)影響權(quán)重進(jìn)行處理，其可以表示為如下公式：

(10)

在傳遞相似度時(shí)，兩個(gè)物品i,j的信任關(guān)系即為：

(11)

1.4 相似度傳遞的計(jì)算

由于數(shù)據(jù)中往往存在明顯的稀疏問(wèn)題，將會(huì)影響到相似度的計(jì)算結(jié)果，因此需要通過(guò)對(duì)相似度的傳遞來(lái)解決此問(wèn)題。在這個(gè)過(guò)程中要利用項(xiàng)目之間的信任關(guān)系進(jìn)行分析，其具體的過(guò)程如下所示：首先根據(jù)信任矩陣得到信任度最高的項(xiàng)目集合，然后根據(jù)步驟1中的結(jié)果得到項(xiàng)目間的間接相似關(guān)系。

首先需要根據(jù)信任矩陣得到項(xiàng)目i的信任集合，并且已知p屬于I，然后求解兩個(gè)項(xiàng)目i,j的間接相似度，其中傳遞時(shí)的權(quán)值是項(xiàng)目i對(duì)項(xiàng)目p的信任關(guān)系，最后采用加權(quán)平均的方式計(jì)算間接相似indirectsim(i,j)，其公式如下所示：

其中直接相似度可以采用余弦相似度方法進(jìn)行計(jì)算，而間接相似度的計(jì)算過(guò)程較為復(fù)雜，其需要先根據(jù)項(xiàng)目之間的信任關(guān)系進(jìn)行建模，在此基礎(chǔ)上傳遞直接相似度。整個(gè)算法可以劃分為如下多個(gè)過(guò)程：

(1)根據(jù)用戶項(xiàng)目評(píng)分矩陣對(duì)其相似度進(jìn)行計(jì)算；

(2)根據(jù)用戶項(xiàng)目評(píng)分矩陣來(lái)構(gòu)建可信關(guān)系模型；

(3)基于上一步得到的可信關(guān)系模型來(lái)傳遞相似度，并得到其間接相似度；

(4)根據(jù)得到的直接與間接相似度進(jìn)行加權(quán)計(jì)算，可以計(jì)算出項(xiàng)目間的相似度；

(5)根據(jù)相似度獲取項(xiàng)目的最近項(xiàng)目鄰居集合；

(6)可以對(duì)未評(píng)分項(xiàng)目進(jìn)行評(píng)分。

2 隱語(yǔ)義模型

2.1 定 義

隱語(yǔ)義模型[11]是一種利用矩陣分解得到結(jié)果的算法，實(shí)質(zhì)就是通過(guò)降維的方法將一些沒有用的信息和噪聲剔除，從而提高預(yù)測(cè)數(shù)據(jù)的準(zhǔn)確性，也在一定程度上緩和了數(shù)據(jù)稀疏帶來(lái)的不良影響。LFM當(dāng)屬矩陣分解算法中最適合推薦系統(tǒng)的模型。

Simon Funk[12]將高維矩陣進(jìn)行分解，得到維數(shù)較低的兩個(gè)矩陣的乘積，如下所示:

R=PTQ

(13)

其中，P是m行k列的矩陣，Q則為n行k列的矩陣，m和n則分別代表用戶的數(shù)量與項(xiàng)目的數(shù)量。則用戶u對(duì)項(xiàng)目i的評(píng)分可以表示為：

(14)

可見，隱語(yǔ)義模型的思想本質(zhì)上是借助最小化的評(píng)價(jià)方法RMSE[13-15]對(duì)矩陣P、Q學(xué)習(xí)的一個(gè)過(guò)程，其中puk=P(u,f)，qik=Q(i,f)。

2.2 用戶興趣遷移模型

隱語(yǔ)義模型著重強(qiáng)調(diào)的是最小化求解原則，用戶對(duì)項(xiàng)目的評(píng)分是在保持條件不發(fā)生變化的理想條件下的，但是事實(shí)情況是，用戶的興趣有一個(gè)變化的過(guò)程，這在傳統(tǒng)的隱語(yǔ)義模型中并沒有得到體現(xiàn)。

在進(jìn)行樣本訓(xùn)練的過(guò)程中發(fā)現(xiàn)，與推薦時(shí)間最接近時(shí)，用戶對(duì)項(xiàng)目的評(píng)分最能反映出用戶的喜愛程度。為了比較客觀地反映這種喜好，則需要將每個(gè)時(shí)間段的評(píng)分按照時(shí)間由遠(yuǎn)到近的順序選取一個(gè)相應(yīng)的權(quán)重系數(shù)，就可以很好地反映出用戶的愛好在這段時(shí)間里的一個(gè)變化過(guò)程[16]。在面對(duì)這種問(wèn)題時(shí)，需要將時(shí)間因素納入到整個(gè)評(píng)分計(jì)算公式中，作為推薦算法的一個(gè)部分，可以更好地反映出哪些更加合適用戶的個(gè)人喜好。這當(dāng)中的一個(gè)典型模型就是基于遺忘的興趣模型。目前，心理學(xué)家普遍認(rèn)為，喜好和記憶遵循著相似的變化規(guī)律，即隨著時(shí)間向后推移而慢慢弱化，直至被人遺忘，并且，越到最后遺忘的越慢，最終會(huì)達(dá)到一種穩(wěn)定狀態(tài)。世界文明的一個(gè)心理學(xué)家—艾賓浩斯，對(duì)人類的遺忘現(xiàn)象做過(guò)一個(gè)數(shù)學(xué)統(tǒng)一，得到一條遺忘特性曲線，這就是著名的艾賓浩斯遺忘曲線[17]，如圖1所示。

圖1 艾賓浩斯遺忘曲線

接著，便逐漸開始有學(xué)者將這種規(guī)律運(yùn)用到推薦算法的模型中。Koychev等人[18]利用推薦系統(tǒng)將用戶的喜好漂移導(dǎo)入了興趣模型中，在他們看來(lái)，人們喜好的變化會(huì)按照艾賓浩斯曲線規(guī)律發(fā)展，因此，他們提出了一個(gè)遺忘規(guī)律性的興趣變化模型。這種模型在記憶曲線的基礎(chǔ)上對(duì)不同項(xiàng)的評(píng)分分配一個(gè)比重系數(shù)，并且設(shè)置一個(gè)閾值，如果權(quán)重的取值低于這個(gè)閾值就忽略不計(jì)。Maloof[19]在此基礎(chǔ)上又提出了一種基于遺忘窗口的興趣變化模型，在這種模型中，用戶的評(píng)分會(huì)隨著權(quán)重的推移而慢慢減少。

但是在實(shí)際的推算中發(fā)現(xiàn)一個(gè)問(wèn)題，那就是直接將記憶曲線導(dǎo)入推薦系統(tǒng)中會(huì)導(dǎo)致與推薦時(shí)間接近的興趣值被過(guò)分放大，反之，較遠(yuǎn)的興趣值會(huì)被基本忽略。對(duì)于上述問(wèn)題，需要改進(jìn)一下函數(shù)，重新建立一個(gè)模型，如下表示：

fu,i=α+(1-α)*e-(tnow-tu,i)

(15)

其中，α是一個(gè)0-1之間的變量，表示興趣變化的影響范圍，tnow是現(xiàn)在的時(shí)間到初始時(shí)間之間的差值，tu,i是用戶u進(jìn)行項(xiàng)目評(píng)分時(shí)的時(shí)間和初始時(shí)間的差值，初始時(shí)間的選取一般選擇某個(gè)時(shí)間點(diǎn)作為參考點(diǎn)。

通過(guò)對(duì)該函數(shù)的定義進(jìn)行簡(jiǎn)單分析可知，用戶對(duì)項(xiàng)目的這種愛好程度會(huì)推著時(shí)間的推移而呈現(xiàn)出一個(gè)衰減的狀態(tài)。在推薦時(shí)間的節(jié)點(diǎn)處，函數(shù)取得最大值，當(dāng)時(shí)間趨向無(wú)窮遠(yuǎn)處時(shí)，函數(shù)取得最小值，無(wú)限接近α。關(guān)于α的取值，1代表的是它將用戶的評(píng)分同等看待，這和傳統(tǒng)算法是完全一致的，若α的取值是0，則意味著用戶喜好的變化遵循艾賓浩斯曲線的規(guī)律特性。可見，通過(guò)對(duì)α的值進(jìn)行調(diào)節(jié)，可以找到一個(gè)合適的值，使得用戶的興趣喜好可以很好地與評(píng)分匹配，更能滿足用戶的客觀需求。

2.3 引入時(shí)間參數(shù)的隱語(yǔ)義模型

把含有用戶興趣變化的函數(shù)引入到改進(jìn)的模型中，改進(jìn)之后的RMSE可以更好地對(duì)樣本集進(jìn)行訓(xùn)練，以此來(lái)求出最佳的P、Q。所以，改進(jìn)后模型的損失函數(shù)重新進(jìn)行如下定義：

(16)

為了將該損失函數(shù)最小化，需要通過(guò)梯度下降方法[20]將其做最優(yōu)化處理。函數(shù)在迭代的過(guò)程中，經(jīng)歷一段時(shí)間的運(yùn)算，便會(huì)到達(dá)一種穩(wěn)定的狀態(tài)，為此，可以設(shè)置一個(gè)合適的閾值，當(dāng)?shù)?jì)算到這一步時(shí)，就可以停止繼續(xù)迭代。

文中算法先設(shè)定一個(gè)數(shù)值K來(lái)判斷該函數(shù)是否需要繼續(xù)運(yùn)算，通過(guò)梯度下降的方法進(jìn)行求解的過(guò)程如下所示：

(1)設(shè)定兩個(gè)參數(shù)變量α和K，前者表示迭代的步長(zhǎng)，而后者表示需要進(jìn)行迭代的次數(shù)。需要指出的是，隨著迭代過(guò)程的推進(jìn)，步長(zhǎng)會(huì)慢慢的縮減。

(17)

使用下面的公式進(jìn)行迭代計(jì)算，刷新puk和qik的數(shù)值。

(18)

(3)記錄迭代計(jì)算的次數(shù)與K值進(jìn)行比較，當(dāng)?shù)螖?shù)超過(guò)K時(shí)，停止迭代計(jì)算，反之再進(jìn)入第二步。

一般情況下，函數(shù)CostFunction在迭代過(guò)程中一定會(huì)找到一個(gè)極值，如果不出意外的話，這一點(diǎn)就是要求的最小值。

3 混合推薦算法

嘗試著將以上兩種算法整合到一起，既可以解決降維處理時(shí)的數(shù)據(jù)丟失問(wèn)題，也可以在一定程度上緩和稀疏問(wèn)題。時(shí)間函數(shù)的引入可以很好地反映出用戶的喜好興趣的變化，更有助于提高系統(tǒng)的推薦性。在融合時(shí)，采用將兩種算法隔離開來(lái)同時(shí)運(yùn)行，得到的運(yùn)算結(jié)果再進(jìn)行加權(quán)求和的方式。

具體的計(jì)算公式如下：

(19)

傳統(tǒng)意義上的協(xié)同算法，計(jì)算相似度時(shí)，主要借助的是相關(guān)系數(shù)法。文中擬采用線性回歸法進(jìn)行求解，為此，需要改寫上面的計(jì)算公式：

(20)

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

4.1 實(shí)驗(yàn)數(shù)據(jù)集

本節(jié)將通過(guò)實(shí)驗(yàn)的方式對(duì)算法的具體效果進(jìn)行驗(yàn)證。在進(jìn)行測(cè)試時(shí)首先需要獲取實(shí)驗(yàn)數(shù)據(jù)集，這里采用的是MovieLens[21]。MovieLens數(shù)據(jù)集中含有的用戶數(shù)目與電影數(shù)目分別是968和1 762，用戶評(píng)分范圍是在1～5之間，各個(gè)用戶已經(jīng)評(píng)分的電影數(shù)目都高于1/5；為了有效地對(duì)算法的效果進(jìn)行驗(yàn)證，需要將所有數(shù)據(jù)劃分為訓(xùn)練集與測(cè)試集，其比例分別是70%與30%。將鄰居集合數(shù)目設(shè)置為多個(gè)不同的值。

RMSE[22-23]在推薦系統(tǒng)的評(píng)價(jià)體系中占據(jù)著非常重要的位置，是衡量系統(tǒng)性能的一個(gè)不可或缺的指標(biāo)。一般的推薦系統(tǒng)會(huì)在用戶登錄系統(tǒng)的那一天就開始推薦，但是因?yàn)橛脩襞d趣的變化不斷，理論上，和推薦當(dāng)天距離最短的興趣就越有可能被推薦為當(dāng)天的興趣，在RMSE中將這些興趣點(diǎn)所對(duì)應(yīng)的時(shí)間的比例增加，對(duì)模型中的RMSE做了如下修改：

(21)

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

(1)參數(shù)α值對(duì)RMSE的影響。

參數(shù)α的作用就是控制時(shí)間造成的用戶興趣的變化，同時(shí)會(huì)以最小權(quán)重的方式設(shè)置下限值。事實(shí)上，用戶喜好的變化是有一定的規(guī)律可循的，因此，需要設(shè)置不同的時(shí)間權(quán)重進(jìn)行數(shù)次實(shí)驗(yàn)。將鄰居集合數(shù)目設(shè)置為100，迭代次數(shù)為200，學(xué)習(xí)速率為0.05，實(shí)驗(yàn)得到的RMSE數(shù)值如圖2所示。

圖2 不同參數(shù)α下的RMSE

從圖2可以看出，在α值變化的過(guò)程中，RMSE的數(shù)值也會(huì)相應(yīng)地發(fā)生變化。當(dāng)α的取值是0.5時(shí)，得到的結(jié)果是最好的。

圖3 不同鄰居個(gè)數(shù)下各融合策略下的RMSE比較

(2)多種算法對(duì)MovieLens數(shù)據(jù)集的測(cè)試。

采用多種算法對(duì)數(shù)據(jù)集進(jìn)行了測(cè)試，設(shè)置不同的鄰居集合，得到了不同鄰居集合下的RMSE，如圖3所示。

通過(guò)圖3能夠明顯看到，提出的LFTRS_CF算法的RMSE值最小，說(shuō)明其在準(zhǔn)確性方面能夠達(dá)到較好的效果，優(yōu)于其他的四種算法。

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

文中詳細(xì)研究了推薦算法的優(yōu)化策略，提出了兩種算法，基于項(xiàng)目相似度的協(xié)同過(guò)濾算法和基于用戶興趣遷移的隱語(yǔ)義模型算法，并在此基礎(chǔ)上對(duì)其進(jìn)行線性融合，使得其中存在的數(shù)據(jù)稀疏性問(wèn)題和用戶興趣遷移問(wèn)題得到了較好的解決。提出的混合推薦算法既可以對(duì)丟失的信息進(jìn)行補(bǔ)充，較好地適應(yīng)用戶興趣的變化，同時(shí)大大弱化了數(shù)據(jù)的稀疏導(dǎo)致的一系列負(fù)面影響。