潘懷奇，覃正優(yōu)

（1.廣西國際商務(wù)職業(yè)技術(shù)學(xué)院信息工程系,南寧 530007；2.南寧師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院，南寧 530100）

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)上每天都在產(chǎn)生數(shù)以億計(jì)的數(shù)據(jù)，海量的數(shù)據(jù)信息在給我們提供更多選擇的同時(shí)也給我們查找自己所需信息帶來了困擾。比如，當(dāng)我們不能清楚地描述我們需要的東西或者沒有明確的需求時(shí)，面對(duì)海量的數(shù)據(jù)我們就會(huì)無從下手。

推薦系統(tǒng)就是為解決上述問題而誕生的。協(xié)同過濾算法（collaborative filtering，CF）是推薦系統(tǒng)中最早出現(xiàn)的，也是最經(jīng)典的推薦算法。協(xié)同過濾算法可以分為基于用戶的協(xié)同過濾算法（UserCF）［1］和基于物品的協(xié)同過濾算法（Item?CF）［2］。當(dāng)使用UserCF算法為用戶作Top-N推薦時(shí)，首先根據(jù)用戶歷史行為數(shù)據(jù)為目標(biāo)用戶尋找與其最相似的K個(gè)用戶，將這K個(gè)用戶已選擇但目標(biāo)用戶沒有選擇過的N個(gè)物品推薦給目標(biāo)用戶。以電影推薦系統(tǒng)為例，假設(shè)用戶A看過電影《喜劇之王》、《功夫》、《無名之輩》，用戶B看過電影《喜劇之王》、《哪吒之魔童降世》、《速度與激情》，當(dāng)使用UserCF為用戶A推薦電影時(shí)，因?yàn)橛脩鬉和用戶B都看過《喜劇之王》，所以他們具有一定的相似性，從而推薦系統(tǒng)可以從用戶B看過而用戶A沒有看過的電影：《哪吒之魔童降世》和《速度與激情》這兩部電影推薦給用戶A。如果對(duì)用戶A的歷史行為進(jìn)行深入分析，我們可以看出，用戶A看過的《喜劇之王》和《功夫》都是周星馳主演的電影，可見用戶A很喜歡周星馳主演的電影。但是UserCF算法僅考慮了用戶的歷史行為，不能發(fā)現(xiàn)用戶具體的興趣所在。為了讓推薦的產(chǎn)品更好地滿足用戶的需要，我們必須了解用戶的興趣。為此，本文提出了一種基于知識(shí)圖譜元路徑的協(xié)同過濾算法，首先構(gòu)建領(lǐng)域知識(shí)圖譜，然后基于知識(shí)圖譜元路徑刻畫出用戶對(duì)物品各方面的興趣分布，從而可以結(jié)合用戶的興趣進(jìn)行推薦。最近的研究表明，知識(shí)圖譜能有效地處理推薦算法傳統(tǒng)的冷啟動(dòng)和數(shù)據(jù)稀疏問題，從而提升推薦算法在推薦中的準(zhǔn)確率。因此，本文提出基于知識(shí)圖譜元路徑的協(xié)同過濾算法（KGUserCF）來增強(qiáng)UserCF算法的推薦效果。本文的貢獻(xiàn)可以概括如下：①以電影數(shù)據(jù)集MovieLens-1M為基礎(chǔ)構(gòu)建了電影領(lǐng)域的知識(shí)圖譜；②基于知識(shí)圖譜元路徑計(jì)算得到用戶各方面的興趣分布；③根據(jù)用戶的興趣分布情況結(jié)合UserCF算法計(jì)算用戶的相似性，從多方面為用戶做出有效推薦；④在電影數(shù)據(jù)集MovieLens-1M上，通過實(shí)驗(yàn)驗(yàn)證KG-UserCF的有效性。

1 相關(guān)工作

1.1 基于鄰域的協(xié)同過濾算法

基于鄰域的協(xié)同過濾算法分為基于用戶的協(xié)同過濾算法和基于物品的協(xié)同過濾算法。1992年Goldberg等人提出了基于用戶的協(xié)同過濾算法，該算法的基本思想是，根據(jù)目標(biāo)用戶的歷史行為記錄尋找與其擁有相似歷史行為記錄的K個(gè)用戶，將這K個(gè)用戶有過正反饋并且目標(biāo)用戶沒有過行為的N個(gè)物品推薦給目標(biāo)用戶。這其中，最重要的是用戶之間的相似度計(jì)算，傳統(tǒng)的相似度計(jì)算使用余弦相似度，其公式為：

公式（1）中，N(u)和N(v)分別表示用戶u和用戶v有過正反饋的物品集合。其次，就是計(jì)算目標(biāo)用戶對(duì)候選列表物品的感興趣程度。在與目標(biāo)用戶u最相似的K個(gè)用戶集合中，喜歡物品i的用戶越多，并且這些用戶與目標(biāo)用戶u的相似度越高，以及這些用戶對(duì)物品i的評(píng)分越高，那么目標(biāo)用戶對(duì)該物品i的感興趣程度就越大。用p(u,i)表示目標(biāo)用戶u對(duì)物品i的感興趣程度，可得到如下公式：

其中，S(u,K)表示與目標(biāo)用戶u最相似的K個(gè)用戶集合，N(i)表示喜歡物品i的用戶集合，rvi表示用戶v對(duì)物品i的評(píng)分。由于基于用戶的協(xié)同過濾算法簡單有效，因此被廣泛運(yùn)用于各種推薦系統(tǒng)當(dāng)中，但是該算法面臨數(shù)據(jù)稀疏的問題，也不能很好的對(duì)推薦結(jié)果做出解釋。Badrul Sarwar等人提出了基于物品的協(xié)同過濾算法（ItemCF），Item?CF算法同樣是基于用戶的歷史行為記錄計(jì)算物品的相似度，其主要思想認(rèn)為，若兩個(gè)物品同時(shí)出現(xiàn)在越多用戶的歷史行為記錄中，那么這兩個(gè)物品的聯(lián)系就越緊密。在給目標(biāo)用戶推薦物品時(shí)，ItemCF算法根據(jù)目標(biāo)用戶的歷史行為記錄，找到與目標(biāo)用戶有過正反饋的物品的強(qiáng)關(guān)聯(lián)物品推薦給目標(biāo)用戶，完成推薦。在電商推薦系統(tǒng)中，ItemCF算法的可解釋性通常表現(xiàn)為“購買了該商品的用戶也購買了某商品”。無論是基于用戶還是基于項(xiàng)目的協(xié)同過濾算法都是在評(píng)分矩陣的基礎(chǔ)上計(jì)算用戶或者物品的相似度，雖然在一定程度上能表示用戶或者物品之間的相似度，但是仍然面臨數(shù)據(jù)稀疏的問題。

1.2 隱語義模型

隱語義模型（latent factor model，LFM）［3］，也被稱作FunKSVD，是FunK S在2006年Netflix Prize大賽中提出的一種機(jī)器學(xué)習(xí)的推薦算法。LFM假設(shè)物品有F個(gè)隱藏的類別，通過機(jī)器學(xué)習(xí)方法在包含正負(fù)樣本的數(shù)據(jù)集上學(xué)習(xí)獲得物品在每個(gè)隱類所占的權(quán)重以及用戶對(duì)每個(gè)隱類的感興趣程度。LFM算法的損失函數(shù)如下：

其中，K是包含正負(fù)樣本的數(shù)據(jù)集，rui表示用戶u對(duì)物品i的真實(shí)評(píng)分，表示算法預(yù)測(cè)用戶u對(duì)物品i的評(píng)分，通過模型參數(shù)pu,f和qi,f計(jì)算得到，而pu,f和qi,f分別表示用戶對(duì)每個(gè)隱類的感興趣程度和物品在每個(gè)隱類所占的權(quán)重，是模型的正則化項(xiàng)。LFM模型通過不斷減小損失學(xué)習(xí)得到pu,f和qi,f兩個(gè)參數(shù)之后，就可以通過公式（4）計(jì)算用戶u對(duì)物品i的感興趣程度了。

在LFM模型之后出現(xiàn)了許多改進(jìn)的模型，比較著名的有增加偏置項(xiàng)的BiasSVD［4］和考慮領(lǐng)域的SVD++［5］，BiasSVD算法認(rèn)為用戶對(duì)物品的評(píng)分會(huì)受到用戶評(píng)分標(biāo)準(zhǔn)和物品本身受歡迎度的影響，因此在評(píng)分預(yù)測(cè)中增加了用戶和物品的偏置項(xiàng)。這一系列的模型在評(píng)分預(yù)測(cè)這一任務(wù)上取得了顯著的效果，但是我們并不明確其中每個(gè)的隱類f所代表的具體的語義，因此不能對(duì)推薦結(jié)果做出可解釋性。

1.3 基于知識(shí)圖譜的推薦算法

知識(shí)圖譜以結(jié)構(gòu)化的形式描述客觀世界中的概念、實(shí)體及其關(guān)系，將互聯(lián)網(wǎng)的信息表達(dá)成更接近人類認(rèn)知的形式，提供了一種更好地組織、管理和理解互聯(lián)網(wǎng)海量信息的能力。知識(shí)圖譜由于包含豐富的實(shí)體、屬性、概念及其之間的關(guān)系，因此被廣泛應(yīng)用于推薦系統(tǒng)中。Yizhou Sun等人［6］將知識(shí)圖譜視為一個(gè)異構(gòu)信息網(wǎng)絡(luò)，提出元路徑的概念來計(jì)算異構(gòu)信息網(wǎng)絡(luò)中節(jié)點(diǎn)之間的相似性。Huang Z等人［7］針對(duì)元路徑不能處理異構(gòu)信息網(wǎng)絡(luò)中節(jié)點(diǎn)之間更復(fù)雜的關(guān)系提出了元結(jié)構(gòu)來度量節(jié)點(diǎn)之間的相似性。此外，還有使用知識(shí)圖譜結(jié)合深度學(xué)習(xí)的方法，如，Palumbo E等人［8］根據(jù)關(guān)系類型在電影知識(shí)圖譜上劃分子圖，使用node2vec［9］的方法將各個(gè)子圖的電影實(shí)體和用戶實(shí)體嵌入到低維向量空間中，然后將得到的實(shí)體在各個(gè)子圖中的表示作為實(shí)體特征輸入LambdaMart排序算法中，最后將排在前面的N個(gè)電影推薦給相應(yīng)的用戶。吳璽煜等人［10］針對(duì)協(xié)同過濾算未考慮物品自身語義信息的問題，提出了基于知識(shí)圖譜表示學(xué)習(xí)的協(xié)同過濾推薦算法TransE-CF，TransE-CF首先利用TransE［11］模型將知識(shí)圖譜中的實(shí)體映射到低維的向量空間，再融合協(xié)同過濾算法做出推薦。

傳統(tǒng)的協(xié)同過濾算法和隱語義模型都是基于評(píng)分矩陣，忽略了物品本身的語義信息；基于元路徑或元結(jié)構(gòu)的方法在計(jì)算相同類型節(jié)點(diǎn)的相似性時(shí)，拋棄了原有的用戶評(píng)分信息；結(jié)合知識(shí)圖譜和深度學(xué)習(xí)的方法不能很好地對(duì)推薦結(jié)果做出解釋。綜上所述，本文提出一種基于知識(shí)圖譜元路徑的協(xié)同過濾算法KG-UserCF，在考慮物品自身語義信息的同時(shí)也結(jié)合了用戶-物品的評(píng)分矩陣，既能彌補(bǔ)傳統(tǒng)協(xié)同過濾算法所面臨的數(shù)據(jù)稀疏問題又能夠?qū)ν扑]結(jié)果做出可解釋性。

2 電影知識(shí)圖譜的構(gòu)建

電影數(shù)據(jù)集MovieLens-1M包含6 040名用戶對(duì)大約3900部電影的1000209條評(píng)分。在先前的研究中，Ostuni V C等人［12］已經(jīng)將電影數(shù)據(jù)集MovieLens-1M中的3900部電影映射到了開放鏈接數(shù)據(jù)DBpedia相應(yīng)的實(shí)體表示，因?yàn)椴⒉皇敲恳徊侩娪岸寄茉谡业紻Bpedia相應(yīng)的實(shí)體表示，映射后共得到3226部電影實(shí)體在DBpedia中的實(shí)體表示。在此基礎(chǔ)上，我們利用Sparql查詢語言在DBpedia的終端獲取這3226部電影實(shí)體的導(dǎo)演、主演、編劇、語言、電影類型等相關(guān)屬性，我們最終獲得了其中3226部電影的6100多名演員和1630多名導(dǎo)演。將得到的數(shù)據(jù)存儲(chǔ)在圖數(shù)據(jù)庫Neo4j中，形成包含16860個(gè)節(jié)點(diǎn)和397631條關(guān)系的電影知識(shí)圖譜。

3 基于知識(shí)圖譜元路徑的協(xié)同過濾算法

本節(jié)將具體介紹基于知識(shí)圖譜元路徑的協(xié)同過濾算法。元路徑是定義在知識(shí)圖譜架構(gòu)層上的路徑，節(jié)點(diǎn)代表實(shí)體類型，邊代表關(guān)系類型。在圖1（a）中，我們示例出了兩條元路徑P1和P2，P1是從用戶到電影再到演員的元路徑，P2是從用戶到電影再到導(dǎo)演的元路徑。在電影知識(shí)圖譜中為每一位用戶匹配P1、P2兩條元路徑下的具體實(shí)例路徑，例如，對(duì)于用戶1我們使用Cypher查詢語句在Neo4j中可得到如圖1（b）中的具體實(shí)例路徑，它們分別表示用戶1觀看過Apollo_13_（film）這部電影，而且這部電影的主演有Tom_HanKs，導(dǎo)演是Ron_Howard。通俗地講，如果用戶1對(duì)m部電影有過正反饋，其中的n部電影是演員a1主演的，那么用戶1對(duì)演員a1的興趣程度為n/m，通過公式（5）和（6）可以計(jì)算得到用戶對(duì)演員的興趣分布矩陣wua和用戶對(duì)導(dǎo)演的興趣分布矩陣wud。

其中，N(u)表示用戶u有過正反饋的電影集合，A(m)表示電影m的演員的集合，D(m)表示電影m的導(dǎo)演的集合，a表示演員，d表示導(dǎo)演。

獲得用戶的興趣分布矩陣之后，就可以利用UserCF算法分別計(jì)算用戶在演員方面和導(dǎo)演方面上的相似性。與傳統(tǒng)UserCF算法不同的是，KG_UserCF算法不再使用原始的用戶-物品評(píng)分矩陣，而是使用經(jīng)過電影知識(shí)圖譜元路徑映射后的用戶-演員、用戶-導(dǎo)演興趣分布矩陣，通過結(jié)合物品本身的語義信息來詳細(xì)刻畫用戶的興趣所在，從而達(dá)到緩解數(shù)據(jù)稀疏的問題和對(duì)推薦結(jié)果做出解釋的目的。用戶之間在演員方面上的相似性可用數(shù)學(xué)公式可描述如下：

其中，A(u)和A(v)分別表示用戶u和用戶v有過正反饋的電影的演員集合，min(wua,wva)表示取wua和wva中最小的值。用戶之間在導(dǎo)演方面上的相似性計(jì)算如下式：

在得到用戶之間在演員方面和導(dǎo)演方面上的相似性之后，分別選取與目標(biāo)用戶在演員方面上最相似的K個(gè)用戶和在導(dǎo)演方面上最相似的K個(gè)用戶，再將這2K個(gè)用戶有過正反饋且目標(biāo)用戶未觀看過的電影作為兩個(gè)候選列表，接著通過公式（9）和（10）對(duì)候選列表分別進(jìn)行排序：

選取排序靠前的N個(gè)物品生成推薦列表，最后融合基于用戶對(duì)演員興趣生成的推薦列表和基于用戶對(duì)導(dǎo)演興趣生成的列表得到最終的推薦列表。整個(gè)KG_UserCF算法流程如圖2所示。

圖1 元路徑與實(shí)例路徑

圖2 KG_UserCF算法流程

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

4.1 數(shù)據(jù)集介紹

本文使用電影數(shù)據(jù)集MovieLens-1M作為實(shí)驗(yàn)數(shù)據(jù)，該數(shù)據(jù)集包含6040名用戶對(duì)大約3900部電影的1000209條評(píng)分。我們通過將3900部電影實(shí)體映射到開放鏈接數(shù)據(jù)DBpedia后獲得了其中3226部電影共6100多名演員和1630多名導(dǎo)演。以此構(gòu)建的電影知識(shí)圖譜包含用戶、電影、演員和導(dǎo)演4種實(shí)體類型以及feedbacK、starring和di?recting 3種關(guān)系類型，共16860個(gè)實(shí)體節(jié)點(diǎn)和397631條關(guān)系。

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

本文最終主要是給用戶作Top-N推薦，因此采用推薦系統(tǒng)中常用的準(zhǔn)確率（precision）、召回率（recall）和F1-score作為評(píng)價(jià)標(biāo)準(zhǔn)。準(zhǔn)確率表示在電影推薦列表中用戶有過正反饋的電影數(shù)量占推薦列表總電影數(shù)的比例，本實(shí)驗(yàn)取推薦列表的長度N=10。準(zhǔn)確率的公式如下：

其中，R(u)是根據(jù)用戶在訓(xùn)練集上的行為給用戶u做出的推薦列表，T(u)是用戶u在測(cè)試集上的行為列表。召回率描述的是推薦列表中用戶有過正反饋的電影數(shù)量占測(cè)試集中電影數(shù)的比例。其公式如下：

而F1-score則綜合了準(zhǔn)確率和召回率來衡量推薦效果的好壞，的值越大表示推薦的效果越好。其公式表示如下：

4.3 實(shí)驗(yàn)對(duì)比

KG_UserCF作為傳統(tǒng)UserCF算法的改進(jìn)，我們將UserCF、ItemCF、最近鄰算法ItemKNN，以及隱語義模型系列的LFM、SVD、NMF模型作為對(duì)比。此外，為了驗(yàn)證KG_UserCF融合了用戶多方面興趣特點(diǎn)的有效性，我們還對(duì)比了僅考慮用戶對(duì)演員單方面興趣時(shí)的推薦方法KG_User?CF_BoA和僅考慮用戶對(duì)導(dǎo)演單方面興趣時(shí)的推薦方法KG_UserCF_BoD。

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

4.4.1 實(shí)驗(yàn)參數(shù)設(shè)置

我們將原始的1000209條評(píng)分?jǐn)?shù)據(jù)按8∶2的比例隨機(jī)劃分為訓(xùn)練集和測(cè)試集。推薦列表的長度N=10。為了確定相似用戶的數(shù)量K最佳取值，我們以10為步長，從［20,80］中選取不同的值進(jìn)行實(shí)驗(yàn)，得到不同K值下的準(zhǔn)確率、召回率和覆蓋率，分別如圖3、圖4和圖5所示。從圖3中可以看出當(dāng)相似用戶數(shù)量達(dá)到50后，準(zhǔn)確率的上升趨勢(shì)減緩；而圖4中的召回率整體變化不大；但是在圖5中，當(dāng)相似用戶數(shù)量到達(dá)30以后，覆蓋率就明顯下降，這說明選取的相似用戶數(shù)量越多，推薦的結(jié)果就越趨于大眾化，因此，綜合考慮，我們?cè)趯?duì)比其他算法時(shí)統(tǒng)一選取相似用戶數(shù)量K=50，在確保較高的準(zhǔn)確率的同時(shí)又不至于導(dǎo)致覆蓋率太低。

圖3 不同K值的準(zhǔn)確率

圖4 不同K值的召回率

圖5 不同K值的覆蓋率

4.4.2 算法對(duì)比

對(duì)于隱語義模型（LFM），隱含類別F=100，學(xué)習(xí)率α=0.02，λ=0.01，正負(fù)樣本的比率ratio=1。為了避免實(shí)驗(yàn)的偶然性，每種算法的結(jié)果都是通過10次實(shí)驗(yàn)取平均值，最終得到的實(shí)驗(yàn)結(jié)果如表1所示。從結(jié)果中，我們可以看出，隱語義模型系列的算法LFM、SVD、NMF相對(duì)于傳統(tǒng)的協(xié)同過濾算法，在各種指標(biāo)上都相差巨大，原因是隱語義模型系列的算法雖然能夠在評(píng)分預(yù)測(cè)任務(wù)上較好地預(yù)測(cè)用戶對(duì)物品的評(píng)分，但是在大量評(píng)分高的候選集當(dāng)中，隱語義模型系列的算法并不明確目標(biāo)用戶的興趣所在，因此，從大量評(píng)分高的物品候選集中選出少量的物品推薦給用戶時(shí)，推薦效果不理想。對(duì)比基于鄰域的兩個(gè)算法ItemCF和UserCF，KG_UserCF算法在準(zhǔn)確率上分別提升了2.77%和2.10%，說明通過元路徑在知識(shí)圖譜上統(tǒng)計(jì)分析能夠準(zhǔn)確的掌握用戶的興趣的分布情況，從而更能針對(duì)用戶的興趣進(jìn)行推薦，推薦效果更加個(gè)性化、精確化，具有一定可解釋性。對(duì)于綜合用戶多方面興趣的KG_User?CF，很顯然效果要好于僅考慮用戶單方面興趣的KG_UserCF_BoA和KG_UserCF_BoD，驗(yàn) 證 了KG_UserCF融合用戶多方面興趣特點(diǎn)的有效性。

表1 多種模型在MovieLens-1M數(shù)據(jù)集上的準(zhǔn)確率、召回率和F1-score

5 結(jié)語

本文提出了一種基于知識(shí)圖譜元路徑的協(xié)同過濾算法，在知識(shí)圖譜的輔助作用下獲得物品的語義信息，使用元路徑的概念統(tǒng)計(jì)分析了用戶的興趣分布情況，根據(jù)用戶的興趣分布再結(jié)合基于用戶的協(xié)同過濾算法，綜合考慮用戶多方面的興趣為用戶作出了個(gè)性化的推薦，通過實(shí)驗(yàn)驗(yàn)證了算法的有效性。不足的地方是本文只融合了用戶在演員和導(dǎo)演兩方面的興趣。在未來的工作中，將不斷豐富電影知識(shí)圖譜，結(jié)合知識(shí)圖譜中更多的語義信息，使用深度學(xué)習(xí)方法增強(qiáng)推薦效果。