基于領(lǐng)域知識(shí)的自適應(yīng)近鄰?fù)扑]算法研究*

楊 輝，閉應(yīng)洲，龐健嬋，武文霖，王志遠(yuǎn)

(南寧師范大學(xué) 計(jì)算機(jī)信息工程學(xué)院，廣西 南寧 530199)

0 引言

隨著互聯(lián)網(wǎng)與大數(shù)據(jù)技術(shù)的飛速發(fā)展，可獲取的信息隨之海量增長(zhǎng)，互聯(lián)網(wǎng)用戶在快速增加，用戶對(duì)個(gè)性化信息的獲取、使用等需求也與日俱增，單靠檢索功能已無法滿足兩者增長(zhǎng)的要求，個(gè)性化推薦系統(tǒng)的出現(xiàn)能滿足這方面的要求。作為至今最經(jīng)典的推薦算法之一的協(xié)同過濾算法已被廣泛應(yīng)用于電子商務(wù)、線上商城、視頻網(wǎng)站、社交應(yīng)用等網(wǎng)絡(luò)平臺(tái)的信息獲取或商務(wù)活動(dòng)中。隨著越來越多學(xué)者投入研究，協(xié)同過濾算法的應(yīng)用技術(shù)會(huì)更成熟，作用也會(huì)越來越大。

傳統(tǒng)的協(xié)同過濾算法分為基于用戶的協(xié)同過濾算法(UserCF)[1]和基于物品的協(xié)同過濾算法(ItemCF)[2]，其推薦原理簡(jiǎn)單來說是根據(jù)用戶的歷史行為計(jì)算用戶之間、物品之間的相似度并以此作為實(shí)現(xiàn)推薦的依據(jù)。協(xié)同過濾算法推薦依賴于用戶的歷史行為，而相較于獲取用戶喜愛的具體物品，獲取用戶對(duì)物品內(nèi)在屬性的偏好會(huì)更容易。就電影推薦為例，若用戶同時(shí)喜歡《星球大戰(zhàn)》《星際穿越》《黑客帝國(guó)》3部電影，需要獲取用戶對(duì)3部電影的完整評(píng)分記錄才能為用戶提供準(zhǔn)確的推薦，而用戶對(duì)3部電影共有的“科幻”類別的內(nèi)在偏好則相對(duì)更好獲取，在面對(duì)歷史瀏覽量較大的新用戶時(shí)，以獲取用戶對(duì)電影類別、導(dǎo)演、主演等偏好來定位用戶實(shí)現(xiàn)推薦將更為高效。知識(shí)圖譜[3]作為一個(gè)由實(shí)體、關(guān)系、屬性構(gòu)成的結(jié)構(gòu)化語(yǔ)義網(wǎng)絡(luò)，提供了物品之間復(fù)雜且豐富的語(yǔ)義關(guān)聯(lián)，能在推薦中針對(duì)物品的領(lǐng)域知識(shí)實(shí)現(xiàn)具有針對(duì)性的建模。隨著知識(shí)圖譜相關(guān)研究的發(fā)展，公共圖譜數(shù)據(jù)已日漸豐富，研究者能更容易獲取物品內(nèi)在信息并構(gòu)建圖譜以實(shí)現(xiàn)更好的推薦效果。

基于上述思路，本研究提出一種基于領(lǐng)域知識(shí)的自適應(yīng)近鄰?fù)扑]方法(NDKCF)，能有效緩解傳統(tǒng)協(xié)同過濾算法的冷啟動(dòng)問題，為推薦結(jié)果提供可解釋性，并最終提升推薦效果。本研究主要內(nèi)容包括：(1)以公共電影數(shù)據(jù)集MovieLens-100K與公共語(yǔ)義數(shù)據(jù)庫(kù)DBpedia為基礎(chǔ)構(gòu)建了電影領(lǐng)域的知識(shí)圖譜；(2)結(jié)合用戶對(duì)電影的歷史評(píng)分?jǐn)?shù)據(jù)與電影知識(shí)圖譜得到用戶對(duì)電影的偏好分布，并根據(jù)偏好分布為用戶找到N個(gè)近鄰用戶組成偏好近鄰用戶組;(3)基于偏好近鄰用戶組的電影總評(píng)分為用戶提供有效推薦，結(jié)合UserCF得到最終的推薦結(jié)果;(4)在公開電影數(shù)據(jù)集MovieLens-100K上，通過反復(fù)實(shí)驗(yàn)測(cè)試，獲取最佳的推薦效果，最終驗(yàn)證算法的有效性。

1 相關(guān)工作

1.1 協(xié)同過濾推薦

協(xié)同過濾最初是由Resnick等人[1]提出的基于用戶的協(xié)同過濾算法(User-based Collaborative Filtering Recommendations，UserCF)，隨后Sarwar等人提[2]出了基于物品的協(xié)同過濾算法(Item-based Collaborative Filtering Recommendations，ItemCF)。協(xié)同過濾算法是基于用戶對(duì)物品的歷史行為數(shù)據(jù)構(gòu)成用戶-物品評(píng)分矩陣，利用余弦相似度計(jì)算得到用戶相似度和物品相似度，UserCF根據(jù)用戶間的相似度預(yù)測(cè)興趣相投的用戶群組進(jìn)行組間推薦，ItemCF根據(jù)物品之間的相似度預(yù)測(cè)每位用戶最感興趣的物品進(jìn)行推薦。之后Daniel等人[4]提出基于物品評(píng)分的Slope One算法，能根據(jù)已評(píng)分的物品數(shù)據(jù)實(shí)現(xiàn)預(yù)測(cè)未評(píng)分物品的分值，一定程度上緩解傳統(tǒng)協(xié)同過濾的數(shù)據(jù)稀疏問題，但依賴于評(píng)分實(shí)現(xiàn)推薦。Koren等人[5]將潛在因子模型與協(xié)同過濾算法相結(jié)合，通過將用戶與物品映射到低維空間中獲取用戶與物品隱藏特征的向量表示來計(jì)算相似度。此外還有SVD[6]、NMF[7]等基于模型的推薦方法。協(xié)同過濾推薦雖然能根據(jù)用戶的歷史行為數(shù)據(jù)有效地挖掘出用戶的喜好，但一直以來都面臨著冷啟動(dòng)，缺乏可解釋性，數(shù)據(jù)稀疏性等問題，而知識(shí)圖譜的引入很大程度上解決了這些問題。

1.2 基于知識(shí)圖譜的推薦

知識(shí)圖譜是一個(gè)結(jié)構(gòu)化的信息庫(kù)，能為現(xiàn)實(shí)生活中的實(shí)體、屬性、概念以及關(guān)系提供針對(duì)性的建模，具有極強(qiáng)的表達(dá)能力，在醫(yī)療、商業(yè)、旅游等眾多領(lǐng)域都發(fā)揮了重要作用。近年來許多學(xué)者致力于將知識(shí)圖譜和推薦算法的融合研究，以知識(shí)圖譜提供的語(yǔ)義信息輔助推薦以取得更好的推薦效果。Yizhou Sun等人[8]針對(duì)從異構(gòu)信息網(wǎng)絡(luò)獲取不同類型對(duì)象的語(yǔ)義信息，提出了一種基于元路徑的相似度度量方法，首次利用元路徑概念獲取用戶偏好并提供個(gè)性化推薦，但依然無法有效描述用戶的偏好分布，且推薦效果依賴于完整的元路徑構(gòu)成。此外，許多研究者嘗試通過深度學(xué)習(xí)獲取知識(shí)圖譜中路徑的語(yǔ)義表示。吳璽煜等人[9]利用transE算法將知識(shí)圖譜的三元組語(yǔ)義信息嵌入低維的語(yǔ)義空間中，通過結(jié)合物品在知識(shí)圖譜中的語(yǔ)義實(shí)現(xiàn)推薦，優(yōu)化了協(xié)同過濾算法未考慮物品自身屬性的問題。Zhu Sun[10]等人利用循環(huán)神經(jīng)網(wǎng)絡(luò)(Recurrent Neural Network)對(duì)知識(shí)圖譜中的實(shí)體路徑建模，自動(dòng)學(xué)習(xí)實(shí)體間路徑的語(yǔ)義的聚合表示，以此得到更具解釋性的推薦結(jié)果。李浩[11]等人利用LSTM(Long Short-Term Memory)建模電影知識(shí)圖譜的實(shí)體路徑，將知識(shí)圖譜的語(yǔ)義路徑推薦融合傳統(tǒng)協(xié)同過濾，得到了更好的推薦效果?？笛愕热薣12]結(jié)合了transE的實(shí)體路徑嵌入方法，通過LSTM和soft attention機(jī)制獲取路徑語(yǔ)義融入到推薦中，進(jìn)一步提高了協(xié)同過濾算法的可解釋性和推薦效果。而通過學(xué)習(xí)語(yǔ)義表示輔助推薦的方法依賴于知識(shí)圖譜信息的完整，推薦效果往往取決于對(duì)于每個(gè)實(shí)體語(yǔ)義的挖掘效果，而當(dāng)推薦領(lǐng)域信息發(fā)生改變時(shí)，對(duì)于語(yǔ)義信息的更迭也將是一大難點(diǎn)。許智宏等人[13]在協(xié)同過濾中引入知識(shí)圖譜推理技術(shù),通過路徑排序算法挖掘?qū)嶓w間多路徑關(guān)系，用于計(jì)算低維空間中視頻間的語(yǔ)義相似性，在語(yǔ)義層面增強(qiáng)了推薦效果，并在一定程度上解決了數(shù)據(jù)稀疏問題，但推薦限于單領(lǐng)域，且無法對(duì)挖掘出的隱含特征進(jìn)行有效描述。

2 基于領(lǐng)域知識(shí)的自適應(yīng)近鄰?fù)扑]

本研究提出一種基于領(lǐng)域知識(shí)的自適應(yīng)近鄰?fù)扑]方法(NDKCF)，本算法分為3部分(圖1)。

圖1 基于領(lǐng)域知識(shí)的自適應(yīng)近鄰?fù)扑]

(1)由公共電影數(shù)據(jù)集MovieLens中用戶與電影的交互記錄構(gòu)建用戶-電影知識(shí)圖譜，通過提取MovieLens中每部電影的所屬類別構(gòu)建用戶-電影-電影類型知識(shí)圖譜。通過知識(shí)圖譜元路徑將用戶對(duì)電影的評(píng)分映射為用戶對(duì)每種電影類型的偏好矩陣，以此計(jì)算用戶間在電影類型偏好上的相似度，并取相似度最接近的N個(gè)近鄰用戶組成基于電影類型偏好的用戶組，將每類用戶看過且該用戶未看過的電影按照組內(nèi)總評(píng)分排序，獲得Top-K推薦列表RecT。

(2)通過MovieLens與DBpedia的映射完善電影知識(shí)圖譜，將公共語(yǔ)義數(shù)據(jù)庫(kù)DBpedia上電影相關(guān)的實(shí)體對(duì)象同MovieLens-100K中的電影相匹配，獲取電影的導(dǎo)演、主演信息，構(gòu)成用戶-電影-主演/導(dǎo)演知識(shí)圖譜，按照(1)的相似度計(jì)算獲取每位用戶基于主演/導(dǎo)演偏好的用戶組，將每類用戶看過且該用戶未看過的電影按照組內(nèi)總評(píng)分排序，獲得Top-K推薦列表RecC。

(3)由基于用戶的協(xié)同過濾算法獲取得到Top-K推薦列表RecCF，最終將各部分的推薦結(jié)果RecT、RecC和RecCF按比例融合，得到最終的推薦列表R。

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

公共電影數(shù)據(jù)集MovieLens-100K包含943名用戶對(duì)1682部電影的100000項(xiàng)評(píng)分與每部電影所屬的18種電影類別，其中每項(xiàng)評(píng)分分值:1～5，電影類型包括“Action”“Adventure”“Animation”等18個(gè)類別名稱，未記錄類型的電影則標(biāo)記為“Unknown”。Ostuni等人[14]已經(jīng)通過映射獲取了MovieLens-100K中的1570部電影在DBpedia上的實(shí)體表示，利用Sparql語(yǔ)句獲取到DBpedia上對(duì)應(yīng)電影的導(dǎo)演、主演信息用于補(bǔ)全電影知識(shí)圖譜。最終獲取到1682部電影的6408條類別關(guān)系、1423條導(dǎo)演關(guān)系和6216條主演關(guān)系。將電影、電影類型、導(dǎo)演、主演作為實(shí)體，以三元組的形式構(gòu)建知識(shí)圖譜K=(E,R,S)，其中E為頭實(shí)體集合，R為關(guān)系集合，S為尾實(shí)體集合。

2.2 元路徑搜尋偏好用戶組

圖2 用戶偏好分布

用戶A的元路徑偏好推導(dǎo)：

用戶A-評(píng)分→True Romance-電影類型→Romance;

用戶A-評(píng)分→Top Gun-電影類型→Romance;

用戶A-評(píng)分→True Romance-電影導(dǎo)演→TonyScott;

用戶A-評(píng)分→Top Gun-電影導(dǎo)演→TonyScott。

用戶B的元路徑偏好推導(dǎo)：

用戶B-評(píng)分→True Romance-電影類型→Crime;

用戶B-評(píng)分→Rumble in the Bronx-電影類型→Crime。

用戶-電影矩陣1

電影-偏好矩陣2

用戶-偏好矩陣3

根據(jù)用戶A評(píng)價(jià)過的兩部電影通過元路徑挖掘出他對(duì)電影類型Romance和導(dǎo)演TonyScott有較高的興趣偏好，同樣用戶B看過的兩部電影能反映出他對(duì)電影類型Crime擁有較高的興趣偏好。通過元路徑對(duì)用戶偏好的搜尋可以獲取用戶的所有偏好分布。

根據(jù)用戶與對(duì)應(yīng)電影偏好之間構(gòu)成的元路徑數(shù)量作為用戶對(duì)電影偏好的喜愛程度，最終得到用戶在電影類別、電影導(dǎo)演和電影主演上的偏好矩陣wut、wud和wus。

用戶-電影主演偏好分布矩陣5/wud

用戶-電影主演偏好分布矩陣6/wus

將所有用戶的偏好分布視作該偏好空間中的向量，用戶在偏好空間中的距離越近，用戶在該類電影偏好上的相似度就越高。

通過計(jì)算用戶偏好向量之間的歐式距離計(jì)算用戶之間的偏好相似度：

(1)

(2)

式中DT(Ua,Ub)為用戶a與用戶b在電影類別偏好空間內(nèi)的歐式距離，DC(Ua,Ub)為用戶a與用戶b在劇組人員偏好空間內(nèi)的歐式距離。根據(jù)每個(gè)用戶在不同偏好空間中的距離判斷用戶對(duì)于該種偏好的近似程度，最終取相距最近的N個(gè)近鄰用戶組成偏好用戶組。

根據(jù)所得的偏好用戶組，統(tǒng)計(jì)每個(gè)用戶對(duì)所有電影的評(píng)分，獲取得到電影類別偏好用戶組最喜愛的電影列表RecT與劇組人員偏好用戶組最喜愛的電影列表RecC。根據(jù)兩個(gè)列表中總評(píng)分最高且用戶未看過的電影作為最終的推薦結(jié)果。

2.3 協(xié)同過濾推薦

基于用戶的協(xié)同過濾通過用戶評(píng)分過的所有電影找到評(píng)分趨勢(shì)最為相近的用戶，根據(jù)計(jì)算用戶之間對(duì)物品評(píng)價(jià)的余弦相似度找到數(shù)個(gè)相似用戶，算式：

(3)

式中N(u)與N(v)表示用戶u與用戶v喜歡的電影集合，|N(u)∩N(v)|表示用戶u與用戶v共同喜歡的電影集合|N(u)|×|N(v)|表示用戶u與用戶v喜歡的電影數(shù)量的乘積，wuv為計(jì)算得到的用戶u與用戶v的相似度。最終根據(jù)用戶相似度找到K個(gè)最相近用戶，計(jì)算用戶u對(duì)相近用戶喜歡的電影i的感興趣程度：

P(u,i)=∑v∈S(u,K)∩N(i)wuv×rvi

(4)

式中S(u,K)表示通過余弦相似度計(jì)算得到的用戶u的K個(gè)相似用戶，N(i)表示喜歡電影i的用戶集合，v為相似用戶中對(duì)喜歡電影i的部分用戶，wuv為用戶u與所有相似用戶v之間的余弦相似度，rvi為相似用戶v對(duì)電影i評(píng)分，通過計(jì)算所有相似用戶的wuv與rvi乘積之和得到用戶u對(duì)電影i的感興趣程度P(u,i)。最終根據(jù)用戶u對(duì)所有電影的感興趣程度進(jìn)行排序后得到Top-K推薦列表RecCF。

2.4 NDKCF算法

輸入：電影知識(shí)圖譜元路徑三元組集E，歷史評(píng)分集T，相似用戶數(shù)量K，推薦列表長(zhǎng)度N；

輸出：推薦結(jié)果R、precision、recall、F1-score；

(1)根據(jù)集合E與集合T得到用戶與電影歷史評(píng)價(jià)分布wuv，用戶對(duì)電影類別的偏好分布wut和對(duì)劇組人員的偏好分布wuc；

(2)根據(jù)wut與式(1)，得到K個(gè)電影類別偏好近鄰集合UT；

(3)根據(jù)wuc與式(2)，得到K個(gè)劇組人員偏好近鄰集合UC；

(4)根據(jù)UT，UC的電影總評(píng)分排序生成候選推薦列表RecT，RecC；

(5)根據(jù)wuv與式(3)與式(4)生成推薦列表RecCF；

(6)按比例融合RecT，RecC，RecCF得到最終推薦列表R。

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

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

本研究使用的數(shù)據(jù)集MovieLens_100K包含943名用戶對(duì)1682部電影的100000項(xiàng)評(píng)分以及對(duì)應(yīng)電影的18項(xiàng)類別。將電影作為實(shí)體通過Dbpedia公共數(shù)據(jù)集映射后獲取到896個(gè)導(dǎo)演的1423條導(dǎo)演關(guān)系和3287個(gè)主演的6216條主演關(guān)系。由于與電影集合僅有單一關(guān)系的偏好節(jié)點(diǎn)對(duì)于用戶偏好的挖掘貢獻(xiàn)很少，因而該條元路徑不計(jì)入偏好數(shù)，最終數(shù)據(jù)見表1。

表1 實(shí)驗(yàn)數(shù)據(jù)集信息

為使實(shí)驗(yàn)具有可比性，所有實(shí)驗(yàn)采用的訓(xùn)練集與測(cè)試集均由用戶的100000項(xiàng)評(píng)分以8∶2的比例隨機(jī)劃分構(gòu)成。

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

本研究采用準(zhǔn)確率(precision)、召回率(recall)、F1值(F1-score)作為評(píng)價(jià)指標(biāo)，3個(gè)指標(biāo)的算式如下：

(5)

(6)

(7)

其中，U是用戶集合，R(u)是通過訓(xùn)練集計(jì)算后為用戶u推薦的N個(gè)結(jié)果，T(u)是測(cè)試集中用戶的歷史評(píng)分。準(zhǔn)確率表示的是正確預(yù)測(cè)的推薦項(xiàng)目在推薦的所有項(xiàng)目中的占比，召回率表示正確預(yù)測(cè)的項(xiàng)目在測(cè)試集中所有項(xiàng)目的占比，兩者越接近1則預(yù)測(cè)效果越好。F1值為平衡了準(zhǔn)確率和召回率的綜合評(píng)價(jià)標(biāo)準(zhǔn)。

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

圖3 準(zhǔn)確率

為了證明基于領(lǐng)域知識(shí)的自適應(yīng)近鄰?fù)扑]方法對(duì)于協(xié)同過濾推薦的有效性，以推薦列表長(zhǎng)度N=10，相似用戶數(shù)與偏好近鄰數(shù)K取值為：10～40，每5次做1次對(duì)比。為避免實(shí)驗(yàn)結(jié)果的偶然性，每次對(duì)比的結(jié)果都是對(duì)應(yīng)算法10次結(jié)果的平均值。其中，藍(lán)線為基于領(lǐng)域知識(shí)的自適應(yīng)近鄰?fù)扑]方法(NDKCF)，NDKCF將推薦列表RecCF、RecT、RecC以8∶1∶1混合；綠線為只考慮電影類型的基于電影類型與協(xié)同過濾的自適應(yīng)近鄰算法(TDKCF)，TDKCF將推薦列表RecCF、RecT以9∶1混合；紅線為基于用戶的協(xié)同過濾算法(UserCF)，推薦結(jié)果全由推薦列表RecCF構(gòu)成。

圖4 召回率

圖5 F1值

當(dāng)選擇的相似用戶數(shù)相同時(shí)，NDKCF和TDKCF在3種評(píng)測(cè)標(biāo)準(zhǔn)上均有優(yōu)于UserCF的表現(xiàn)，且偏好信息更充足的NDKCF普遍優(yōu)于只考慮電影類型偏好的TDKCF。實(shí)驗(yàn)結(jié)果說明基于領(lǐng)域知識(shí)的自適應(yīng)近鄰?fù)扑]方法有效提高了協(xié)同過濾的推薦效果，且隨著對(duì)電影偏好知識(shí)圖譜的完善，NDKCF能有更好的效果。

取推薦列表長(zhǎng)度N=10，相似用戶數(shù)K=20，將NDKCF與熱門推薦MostPop、奇異值分解SVD、TDKCF、UserCF、itemCF對(duì)比，結(jié)果見表2。

表2 六種推薦方法的準(zhǔn)確率、召回率、F1值對(duì)比

NDKCF在3個(gè)指標(biāo)上都優(yōu)于傳統(tǒng)的協(xié)同過濾ItemCF與UserCF，且當(dāng)用戶偏好不完善時(shí)，也能通過知識(shí)圖譜搜尋部分方面的偏好近鄰實(shí)現(xiàn)較好的推薦效果。實(shí)驗(yàn)驗(yàn)證了NDKCF在提升了推薦個(gè)性化與可解釋性的情況下具有更好的推薦效果。

4 結(jié) 語(yǔ)

本研究基于領(lǐng)域知識(shí)的自適應(yīng)近鄰?fù)扑]方法，通過搜尋知識(shí)圖譜元路徑獲得用戶在各個(gè)偏好上的最近鄰，根據(jù)偏好近鄰用戶組得到更有針對(duì)性的個(gè)性化推薦。實(shí)驗(yàn)證明了在偏好信息不完全的情況下該方法依然具有較好的推薦效果，能應(yīng)對(duì)新用戶難以獲取完整偏好的問題，有效緩解冷啟動(dòng)情況。未來我們將嘗試完善電影知識(shí)圖譜的偏好構(gòu)成，通過圖深度學(xué)習(xí)的方法挖掘并利用領(lǐng)域知識(shí)中更復(fù)雜的偏好特征融入推薦過程中，以獲取更好的推薦效果。