一種基于遺忘機(jī)制與余弦相似度的智能推薦算法

許 馨, 郭家赫, 喬 宇, 舒萬(wàn)能

(中南民族大學(xué)計(jì)算機(jī)科學(xué)學(xué)院, 湖北 武漢 430074)

0 引言(Introduction)

近年來(lái),用戶在線活動(dòng)產(chǎn)生的信息量呈指數(shù)級(jí)增長(zhǎng),如何過(guò)濾日漸龐大的信息成為一個(gè)難題。推薦系統(tǒng)[1]是一種特殊的過(guò)濾方法,該方法根據(jù)用戶的過(guò)往興趣計(jì)算出類似的物品,再推薦給用戶,以處理信息過(guò)載[2]問(wèn)題。近年來(lái),許多學(xué)者開展了推薦算法的研究,由于商品不斷增加,用戶對(duì)推薦性能和功能的需求也不斷增長(zhǎng),因此學(xué)者們對(duì)于該領(lǐng)域的研究熱情依然高漲。

基于用戶相似性的鏈接預(yù)測(cè)方法,通過(guò)觀測(cè)用戶過(guò)往偏好的方式,研究人員設(shè)計(jì)了模型計(jì)算用戶對(duì)新物品的潛在喜好度,并將潛在喜好度高的物品個(gè)性化地推薦給用戶[3]。但在現(xiàn)實(shí)生活中,隨著新物品出現(xiàn)時(shí)間的推移,用戶會(huì)產(chǎn)生興趣漂移,進(jìn)而影響推薦的準(zhǔn)確性。傳統(tǒng)的鏈接預(yù)測(cè)算法只關(guān)注用戶-用戶或者物品-物品之間的相似度,忽略了用戶與物品之間的相似關(guān)系,對(duì)推薦算法的準(zhǔn)確性產(chǎn)生了不利影響。

為了解決這一問(wèn)題,本文提出一個(gè)依賴于復(fù)數(shù)的實(shí)部和虛部的推薦模型。推薦模型中,首先將相似或不相似的鏈接用實(shí)數(shù)加權(quán),而喜歡或不喜歡的鏈接用復(fù)數(shù)加權(quán),由于復(fù)數(shù)在實(shí)數(shù)和虛數(shù)之間提供了一個(gè)自然的代數(shù)聯(lián)系,因此推薦問(wèn)題轉(zhuǎn)化成一個(gè)鏈接預(yù)測(cè)問(wèn)題。其次結(jié)合遺忘機(jī)制,利用遺忘度為用戶對(duì)物品的偏好權(quán)重進(jìn)行加權(quán)。最后計(jì)算兩個(gè)節(jié)點(diǎn)之間的相似性,生成TOPN(前N個(gè)最高的數(shù)據(jù))推薦列表。通過(guò)在真實(shí)數(shù)據(jù)集中進(jìn)行實(shí)驗(yàn),驗(yàn)證推薦算法的性能。

1 相關(guān)工作(Related work)

1.1 相關(guān)推薦算法

推薦算法通常被分為基于內(nèi)容的個(gè)性化推薦算法和協(xié)同過(guò)濾推薦算法。基于內(nèi)容的推薦算法依賴于內(nèi)容的相似度,而協(xié)同過(guò)濾推薦算法依賴于相似用戶提供的評(píng)分,但這些推薦算法有各自的缺陷,例如“冷啟動(dòng)”“興趣漂移”“數(shù)據(jù)稀疏”等問(wèn)題極大地影響了推薦算法的準(zhǔn)確性和推薦的多樣性。在傳統(tǒng)的基于用戶或基于物品的協(xié)同過(guò)濾相似性計(jì)算方法下,新用戶沒(méi)有鄰居可以參考,文獻(xiàn)[4]提出用戶-物品偏好矩陣是高度稀疏的,因此會(huì)導(dǎo)致不準(zhǔn)確的推薦。

為了解決數(shù)據(jù)稀疏問(wèn)題,提高推薦準(zhǔn)確性,研究人員提出了基于用戶-物品交互圖的模型[5]。用戶-物品交互圖中存在兩種節(jié)點(diǎn)類型,即物品和用戶。用戶-物品交互圖中的推薦可以被轉(zhuǎn)換為鏈接預(yù)測(cè)問(wèn)題,鏈接預(yù)測(cè)主要是根據(jù)特征的相似性和節(jié)點(diǎn)之間的其他連接預(yù)測(cè)兩個(gè)節(jié)點(diǎn)之間發(fā)生連接的概率。目前,用戶-用戶或物品-物品鏈接的類型被標(biāo)記為相似或不相似,用戶和物品之間的鏈接類型被標(biāo)記為喜歡或不喜歡。經(jīng)過(guò)這樣的調(diào)整,因?yàn)橹恍枰獙⑽锲吠扑]給用戶,所以喜歡或不喜歡的物品鏈接變得更加重要。

為了解決興趣漂移問(wèn)題,文獻(xiàn)[6]提出了基于艾賓浩斯遺忘規(guī)律的算法模型,首先通過(guò)引入一個(gè)指數(shù)類型的遺忘函數(shù)量化用戶對(duì)物品的興趣衰減程度,其次根據(jù)當(dāng)前時(shí)間計(jì)算出用戶對(duì)物品的偏好權(quán)重,最后進(jìn)行排序推薦。文獻(xiàn)[7]提出了一種結(jié)合遺忘曲線和改進(jìn)相似度的組合推薦算法,通過(guò)引入大范圍加權(quán)因子改進(jìn)用戶相似度,提升高稀疏數(shù)據(jù)下用戶的相似度,再引入遺忘曲線跟蹤用戶的興趣漂移,識(shí)別用戶的短期興趣與長(zhǎng)期興趣。

1.2 余弦相似度

余弦相似度[8]是常用的相似度算法之一,它被廣泛地應(yīng)用在數(shù)據(jù)處理的各個(gè)領(lǐng)域,通常在協(xié)同過(guò)濾算法中,評(píng)分矩陣的每行向量都代表一個(gè)用戶,其值代表用戶對(duì)物品的評(píng)分,余弦相似度計(jì)算函數(shù)定義如下:

(1)

1.3 遺忘機(jī)制

人腦對(duì)新物品產(chǎn)生印象后,會(huì)隨著時(shí)間的推移而慢慢遺忘該物品,而且遺忘速度最初很快,后期會(huì)慢慢減緩[9]。根據(jù)科學(xué)家對(duì)遺忘規(guī)律的研究,將遺忘函數(shù)定義如下:

(2)

其中,遺忘函數(shù)F(t)為當(dāng)前時(shí)間用戶對(duì)新物品記憶的留存程度,t為當(dāng)前時(shí)間,ect為用戶對(duì)物品產(chǎn)生印象的時(shí)間,hv為用戶遺忘的速率,根據(jù)函數(shù)定義,記憶留存程度與hv呈反比,hv越大,則遺忘速度越慢[10]。本文將hv定義為當(dāng)前時(shí)間與用戶第一次對(duì)物品產(chǎn)生記憶的時(shí)間之間的差值。將上述理論代入推薦算法,假設(shè)用戶在t1時(shí)刻選擇物品A,在t2時(shí)刻選擇物品B,t2時(shí)刻即推薦列表產(chǎn)生的時(shí)間,當(dāng)前時(shí)刻為t,那么該用戶對(duì)于物品B的感興趣程度公式如下:

(3)

2 算法設(shè)計(jì)(Algorithm design)

2.1 融合遺忘機(jī)制的加權(quán)二部圖

推薦算法可以簡(jiǎn)單地表示為一個(gè)二部圖,在有向網(wǎng)絡(luò)中,頂點(diǎn)V表示物品,U代表用戶,E表示用戶購(gòu)買物品或是對(duì)物品的評(píng)分?jǐn)?shù)據(jù)等。設(shè)U為用戶集合,G為物品集合,則V為所有用戶和物品的并集V=U∪G。

二部圖中的節(jié)點(diǎn)會(huì)不斷更新,其關(guān)聯(lián)程度也會(huì)不斷改變。在用戶-物品鏈接中,引入了遺忘因子,用來(lái)表示用戶對(duì)當(dāng)前物品的感興趣程度。感興趣程度低,則根據(jù)其特征進(jìn)行推薦的權(quán)重變低,感興趣程度高,則優(yōu)先進(jìn)行推薦。

(4)

其中,etij表示用戶第一次購(gòu)買基準(zhǔn)物品的時(shí)間,hvj表示遺忘速率,為推薦時(shí)間與當(dāng)前時(shí)間的差值。將遺忘機(jī)制計(jì)算的偏好權(quán)重與用戶對(duì)物品的評(píng)級(jí)結(jié)合,其公式表達(dá)如下:

δij=ωijfij

(5)

其中,ωij是用戶i對(duì)物品j的評(píng)級(jí),計(jì)算結(jié)果代表了推薦權(quán)重。

2.2 鏈接預(yù)測(cè)算法

在二部圖中,如果兩個(gè)節(jié)點(diǎn)之間有連接,那么總是有兩個(gè)相反方向的鏈路連接這個(gè)節(jié)點(diǎn)對(duì),可以通過(guò)鏈路預(yù)測(cè)圖中用戶和特定物品之間是否可能會(huì)產(chǎn)生鏈接,之后通過(guò)鏈接預(yù)測(cè)算法[11]計(jì)算任何物品與特定用戶之間的相關(guān)性。

用戶-物品二部圖的節(jié)點(diǎn)或許有兩種類型的關(guān)系。首先,對(duì)于“用戶-用戶”鏈接和“物品-物品”鏈接,兩個(gè)實(shí)體之間都存在一個(gè)相似因子,同時(shí)由于用戶會(huì)對(duì)物品產(chǎn)生偏好,所以用戶U對(duì)物品G之間的鏈接總有一個(gè)從物品G到用戶U的反向鏈接與之對(duì)應(yīng)。該模型的鏈接關(guān)系如圖1所示。

(b)類似的用戶-物品會(huì)有類似的興趣

(c)用戶-物品相似度可傳遞圖1 三角形向量乘法規(guī)則Fig.1 Triangular vector multiplication rule

該模型的鏈接關(guān)系具體表現(xiàn)如下。

(1)用戶u1對(duì)物品g感興趣,用戶u2也對(duì)物品g感興趣,那么用戶u1和u2可能相似,說(shuō)明對(duì)相同物品感興趣的用戶可能具有相似性鏈接;用戶u對(duì)物品g1感興趣,同時(shí)對(duì)物品g2感興趣,那么物品g1和物品g2可能相似,說(shuō)明同一個(gè)用戶喜歡的不同物品可能具有相似性鏈接;其公式表達(dá)如下:

(6)

(2)用戶u1和用戶u2相似,用戶u2對(duì)物品g感興趣,那么用戶u1也可能對(duì)物品g感興趣,說(shuō)明相似用戶可能會(huì)喜歡同一個(gè)物品;物品g1和物品g2相似,用戶u對(duì)物品g2感興趣,那么用戶u也可能對(duì)物品g1感興趣,說(shuō)明用戶可能會(huì)喜歡相似的物品;其公式表達(dá)如下:

ωlike=ωsimilar×ωlike

(7)

(3)物品g1和物品g2相似,物品g2和物品g3相似,那么物品g1和物品g3可能相似,說(shuō)明物品之間的相似性可傳遞;用戶u1和用戶u2相似,用戶u2和用戶u3相似,那么用戶u1和用戶u3可能相似,說(shuō)明用戶之間的相似性可傳遞。其規(guī)則可用數(shù)學(xué)表達(dá)式表示如下:

(8)

因此,只有找到兩個(gè)不同的非零整數(shù),才能解上述方程組。假設(shè)ωsimilar=1且ωlike=j,j是虛數(shù)單位,引入復(fù)數(shù)的概念后,公式(6)至公式(8)分別可以轉(zhuǎn)換成1=-j2,j=1×j和1=12。

當(dāng)用戶不喜歡物品時(shí),從用戶到物品之間的鏈接用-j進(jìn)行加權(quán),從物品到用戶之間的鏈接則用j加權(quán)。相對(duì)于相似的鏈接,只有同時(shí)知道鏈接權(quán)重的符號(hào)和鏈接的方向,才能區(qū)分用戶喜歡與不喜歡,而權(quán)重的值則代表了用戶不喜歡的程度。最后,將遺忘因子與鏈接權(quán)重相乘,即可以得到新的興趣度權(quán)重。

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

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

本文使用MovieLens數(shù)據(jù)集[12]進(jìn)行實(shí)驗(yàn),該數(shù)據(jù)集由943名用戶、1 682部電影以及100 000條用戶對(duì)電影的評(píng)分組成。

首先,隨機(jī)選取每個(gè)用戶評(píng)分的10%的項(xiàng)目創(chuàng)建臨時(shí)測(cè)試集,而臨時(shí)訓(xùn)練集則包含其他評(píng)分。其次,將臨時(shí)測(cè)試集中的“5星”評(píng)分篩選出來(lái)作為最終測(cè)試集中的評(píng)分,將臨時(shí)測(cè)試集中剩余的評(píng)分合并到臨時(shí)訓(xùn)練集中作為最終訓(xùn)練集中的評(píng)分。

3.2 評(píng)價(jià)指標(biāo)

本文研究的重點(diǎn)是測(cè)試集中有多少相關(guān)的物品可以推薦給用戶,還計(jì)算了向所有用戶推薦物品的總體比例。因此,比較方法的性能可以通過(guò)命中率和覆蓋率進(jìn)行衡量,在TOPN推薦的情況下,總體命中率和覆蓋率通過(guò)平均所有測(cè)試用例的結(jié)果進(jìn)行描述。

(9)

(10)

當(dāng)用戶u的推薦列表中出現(xiàn)物品g時(shí),測(cè)試集中的每一對(duì)相關(guān)的用戶-物品對(duì)都將獲得一次命中,總的命中數(shù)用#hits表示,測(cè)試對(duì)的數(shù)量用|T|表示。因此,命中率可以被定義為向用戶推薦物品的能力,覆蓋率為系統(tǒng)可以推薦物品的百分比,當(dāng)這兩個(gè)指標(biāo)的值較高時(shí),表示算法的性能較好。

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

首先,將數(shù)據(jù)集中的評(píng)級(jí)轉(zhuǎn)換為復(fù)數(shù),得到一個(gè)鄰接矩陣。其次,應(yīng)用余弦相似度理論測(cè)量數(shù)據(jù)集中的用戶-物品評(píng)級(jí)矩陣,再引入遺忘機(jī)制為用戶對(duì)物品的喜好度加權(quán)。最后,得到用戶-用戶余弦相似度矩陣和物品-物品余弦相似度矩陣。組合這些矩陣后,將這兩個(gè)數(shù)據(jù)集的主要鄰接矩陣構(gòu)造為方陣。節(jié)點(diǎn)之間的緊密度值是通過(guò)鄰接矩陣的冪進(jìn)行衡量的,因此可以利用雙曲正弦函數(shù)作為鏈路預(yù)測(cè)函數(shù)。計(jì)算二部圖中奇次冪的和,并給出不同長(zhǎng)度的最短路徑。連接兩個(gè)節(jié)點(diǎn)的路徑越多,該函數(shù)的得分就越高,兩個(gè)節(jié)點(diǎn)之間的關(guān)系也越重要。因此,本文設(shè)計(jì)了實(shí)驗(yàn)測(cè)試在不同路徑長(zhǎng)度下,FMS(Forgetting Mechanism and Cosine)鏈接預(yù)測(cè)方法的推薦性能。圖2和圖3分別展示了FMS算法在路徑長(zhǎng)度為3、5、7和9的命中率和覆蓋率對(duì)比。圖2表明,隨著路徑長(zhǎng)度的增加,算法的命中率有所降低。顯然,當(dāng)路徑長(zhǎng)度為3時(shí),算法的綜合推薦性能更好。

圖2 不同路徑長(zhǎng)度的命中率比較Fig.2 Hit rates comparison of different path lengths

圖3 不同路徑長(zhǎng)度的覆蓋率比較Fig.3 Coverage comparison of different path lengths

圖3表明,路徑長(zhǎng)度為3時(shí),算法的覆蓋率最高。但是,隨著TOPN推薦列表的增加,路徑長(zhǎng)度為5的覆蓋率逐漸增長(zhǎng)到與路徑長(zhǎng)度為3的覆蓋率持平,路徑長(zhǎng)度為7或者9時(shí),算法覆蓋率遠(yuǎn)遠(yuǎn)低于路徑長(zhǎng)度為3或者5。

采用基于物品的TOPN推薦算法對(duì)FMS進(jìn)行性能評(píng)估,將TOPN推薦列表的長(zhǎng)度從10增加到100,將這些結(jié)果與文獻(xiàn)[11]中引入的一種復(fù)雜項(xiàng)目推薦的鏈接預(yù)測(cè)方法CORLP(Complex Representation-based Link Prediction)進(jìn)行對(duì)比,實(shí)驗(yàn)結(jié)果如下:圖4和圖5分別展示了FMS算法和CORLP算法在路徑長(zhǎng)度為3和5時(shí)的命中率和覆蓋率的對(duì)比。顯然,隨著TOPN推薦列表的增加,命中率和覆蓋率也持續(xù)增大,并且在路徑長(zhǎng)度為3或者5的情況下,FMS算法的命中率均顯著高于CORLP算法。

圖4 與CORLP算法的命中率比較Fig.4 Hit rates comparison of FMS and CORLP

圖5 與CORLP算法的覆蓋率比較Fig.5 Coverage comparison of algorithm FMS and CORLP

圖5表明,路徑長(zhǎng)度為3或者5的情況下,FMS算法與CORLP算法的覆蓋率幾乎相同。FMS算法在路徑長(zhǎng)度為3和5時(shí)均擁有較好的性能,而CORLP算法僅在路徑長(zhǎng)度為3時(shí)表現(xiàn)出的綜合性能較好。

4 結(jié)論(Conclusion)

為了解決基于相似度的推薦算法在復(fù)雜域中未考慮到用戶對(duì)物品喜好度以及用戶“興趣漂移”的問(wèn)題,本文研究了用戶和物品之間的相似性因素,并通過(guò)遺忘因子對(duì)用戶相似性進(jìn)行度量,設(shè)計(jì)了一種結(jié)合遺忘機(jī)制和用戶相似性的推薦算法,通過(guò)在MovieLens數(shù)據(jù)集上與其他算法進(jìn)行對(duì)比實(shí)驗(yàn),本文提出的FMS算法在覆蓋率和命中率方面均優(yōu)于其他算法。基于圖4的對(duì)比結(jié)果,本文提出的算法在TOP100(前100個(gè)相似物品)的情況下命中率顯著優(yōu)于CORLP算法,在路徑長(zhǎng)度為3時(shí),命中率提高了10%,在路徑長(zhǎng)度為5時(shí),命中率提高了12%。在TOP40下優(yōu)勢(shì)不明顯,但在路徑長(zhǎng)度為3和5時(shí),命中率依然分別提高了2%和6%,經(jīng)過(guò)20組數(shù)據(jù)對(duì)比取平均值,本文提出的FMS算法相較于其他算法命中率提高了約7%。通過(guò)對(duì)鏈路預(yù)測(cè)函數(shù)進(jìn)行縮放參數(shù)的修改,該方法獲得了更高的命中率,在較小的參數(shù)規(guī)模下具有較高的覆蓋率。實(shí)驗(yàn)證明,經(jīng)過(guò)改進(jìn)后的算法在推薦準(zhǔn)確性上有了較大的提升,說(shuō)明用戶與物品之間的相似度度量以及遺忘因子對(duì)推薦算法性能具有一程度的影響。接下來(lái),可以考慮在算法中融入圖像之間的語(yǔ)義關(guān)系,設(shè)計(jì)基于圖像語(yǔ)義的推薦系統(tǒng),進(jìn)一步提升推薦算法的性能。