基于知識圖譜表示學習的協同過濾推薦算法

吳璽煜,陳啟買,劉 海,賀超波

(1.華南師范大學 計算機學院,廣州 510631; 2.仲愷農業工程學院 信息科學與技術學院,廣州 510225)

0 概述

協同過濾是至今應用最廣泛的推薦技術,已經成功地應用于電子商務[1]、網上學習[2]和新聞媒體[3]等工業界領域,在學術界內也一直受到大量學者關注。協同過濾推薦主要根據用戶對資源的歷史行為信息,尋找用戶或者資源的近鄰集合,以此來計算用戶對資源的偏好值[4]。文獻[5]將Facebook用戶的個性數據融合進協同過濾中,用合并多領域數據集的方式提高了推薦的準確性。文獻[6]從評分上下文信息著手,提出了一種融合奇異性和擴散過程的協同過濾模型,解決了信息過載問題。文獻[7]融合了基于內容與協同過濾的推薦算法,提高了新聞推薦的性能。現有各種協同過濾算法都使用了用戶隱性反饋數據(比如購買記錄)、用戶顯性反饋數據(比如評分)等信息,準確地將用戶所需要的物品推薦給對方。然而這些算法主要利用物品-用戶評分矩陣這一外在信息,尚未充分考慮物品自身的內在信息。隨著知識圖譜技術的發展,業界已經積累了大量開放的語義數據,如Freebase[8]、DBpedia[9],包含了物品豐富的內涵知識。將內涵知識和外在評分融合在一起,可以使得傳統協同過濾推薦算法的信息更加完備。文獻[10]嘗試使用了知識圖譜的結構特征,將本體融進協同過濾算法。現有研究表明,知識圖譜表示學習方法能將知識圖譜嵌入到一個低維語義空間中,可以利用連續數值的向量反映知識圖譜的結構特征。這種方法可以高效地計算實體間的語義聯系。文獻[11]嘗試將知識圖譜表示學習算法與基于隱性反饋的協同過濾相結合,把原始數據轉化為偏好序列進行參數學習,加強了協同過濾推薦算法的性能。

圍繞上述背景,本文提出基于知識圖譜表示學習的協同過濾推薦算法。算法的出發點與文獻[11]相近,后者使用用戶隱性反饋數據,而本文算法是針對用戶顯性反饋數據,即物品-用戶評分矩陣。算法通過知識圖譜表示學習算法TransE[12]獲取物品的語義信息,計算物品之間的語義相似性,在推薦過程中融入物品的語義信息,更好地為用戶進行推薦。

1 相關理論

1.1 基于物品的協同過濾推薦

基于物品的協同過濾推薦[13]是一種基于最近鄰的推薦系統算法,主要基于如下假設:用戶傾向于喜歡相似的物品。在推薦系統中,算法通過計算物品之間的相似性,從而向用戶推薦最合適的物品。整個推薦過程形式化表示如下:假設有m個用戶U=(U1,U2,…,Um),n個物品I=(I1,I2,…,In),輸入的數據集是一個m×n的物品-用戶評分矩陣Rm×n:

(1)

其中,分數Rij為用戶Ui對物品Ij的評分,且該評分代表用戶i對物品j的喜好程度。矩陣元素之間的相似性度量主要采用余弦相似性實現,即通過計算兩個向量之間夾角的余弦值,度量它們之間的相似性。假設A和B為2個向量,n是它們的維度,則它們的余弦相似性表示為:

(2)

該式計算結果的值越大,向量就越相似。當simcos(A,B)值為0表示兩個向量完全不相似,1則是完全相似。

此外,針對物品-用戶評分矩陣中評分相當稀疏的問題,文獻[14]提出加入相似性權重重要性的策略,用于避免數值過分偏倚的問題。該方法采用了貝葉斯學派里收縮的思想,當只有少量評分用于相似性計算時,采取策略降低兩者之間的相似性權重。因此,改進后的物品間相似性權重計算公式為:

(3)

利用式(3),基于物品的協同過濾推薦算法將物品-用戶評分矩陣轉換成一個物品-物品相似性矩陣,并對這個相似性矩陣進行近鄰選擇。近鄰選擇是對U所挑選過的物品分別進行排序篩選,分為以下2個步驟:1)對于線下已經計算好的物品-物品相似性矩陣,進行預過濾近鄰。2)對某一個用戶,讀取內存中的數據,使用Top-k進行選擇推薦。推薦系統中用戶和物品往往數量巨大,因此需要預先過濾物品間相似性度量的數量。本文采用了2種預過濾技術:Top-N過濾和閾值過濾。對于預測的評分,本文也使用了Top-k選擇和正值選擇,使推薦效果提高。

1.2 知識圖譜表示學習

文獻[15]提出的Word2Vec模型,可以將詞匯嵌入到一個K維空間。這種分布式表示掀起了一股表示學習的熱潮。表示學習這一古老而又新穎的話題,又一次煥發出新的光彩。該算法的核心思想是利用類比性的優點,更好地發現詞與詞之間的相關性。文獻[12]將該思想應用于知識圖譜領域,提出了一種知識圖譜表示學習算法TransE。該算法的核心思想是將知識圖譜中的實體與關系嵌入到一個低維的向量空間里面去,同時將兩者轉化為向量表示。因此,從直觀上看,相近的實體在空間里的向量表示也是相近的。更進一步,在語義上有聯系的實體,在空間里也有所關聯。

基于上述思想,能夠通過知識圖譜表示學習,對知識圖譜中實體和關系進行語義表示學習,通過將富有語義信息的知識圖譜三元組嵌進n維語義空間并生成對應向量,從而實現了知識圖譜的數值化。通過知識圖譜表示學習,可以快速計算兩個實體間的語義相似性,并方便地將知識圖譜用到其他學習任務中。知識圖譜表示學習的實現主要有2種方法:1)基于張量分解的方法;2)翻譯的方法。前者包括了NTN[16]、RESCAL[17]等。后者包括了TransE、TransH[18]、TransR/CTransR[19]等。對于Freebase這類關系數目眾多而又非常稀疏的大規模知識庫,基于張量分解的方法效果不佳,選擇翻譯方法[20]更為合適。

2 基于知識圖譜表示學習的協同過濾推薦算法

本文提出了一種基于知識圖譜表示學習的協同過濾推薦算法,其基本思想是:對于協同過濾計算出來的最近鄰,系統推薦給用戶;而對于該用戶喜歡的物品在語義上相似的物品,系統也可以推薦給用戶。相對于協同過濾推薦算法僅使用外部評分,加入內涵知識(知識圖譜)會得到更好的效果,提高推薦的有效性。

利用知識圖譜表示學習算法,將推薦的物品嵌入到一個低維空間,然后計算物品之間的語義相似性,生成語義相似性矩陣,最終可以得到物品的語義近鄰。同時,通過調節融合比例,對語義近鄰和協同過濾潛在物品按比例融合,利用豐富的語義數據一定程度上解決了推薦系統的冷啟動問題。圖1給出了本文算法(記為TransE-CF)的流程圖。

圖1 TransE-CF算法流程

2.1 融合語義近鄰集合的協同推薦過程

2.1.1 基于TransE算法的知識圖譜表示學習

對于一個典型的知識圖譜來說,可以通過有向圖表示的三元組,以及三元組之間的相互鏈接構成一個網狀的知識集合,這種三元組攜帶著實體自身的語義信息。其中實體作為節點,實體之間的關系作為邊。

以電影領域為例,電影實體中主要包括了演員、類型、導演等主要特征。這些特征從一定程度上概括了這部電影。利用電影特征,可以得到類似圖2所示的一個電影知識圖譜的三元組。

圖2 知識圖譜三元組

在圖2中,電影實體Movie和演員實體Actor之間通過關聯,構成三元組(M,starring_actor,A),再通過三元組之間的相互鏈接形成知識圖譜。圖3為Freebase中節選的部分電影及其屬性所成的網狀結構。從圖3中可以看出,在知識圖譜中越相似的2個節點,在語義上也往往十分接近。因此,對于電影推薦來說,不僅可以利用電影的用戶評分信息,也可以使用電影自身的語義信息。協同過濾推薦認為兩物品的用戶評分分布相近,則它們被判定為近鄰。同樣地,如果該電影在知識圖譜中相近,直觀上也可以被判定為近鄰。

圖3 電影知識圖譜

基于上述思想,本文使用在翻譯方法上有較好性能的TransE算法,增強協同推薦算法中物品-用戶評分矩陣中物品的語義信息。按照TransE算法的定義,對于知識圖譜S中的一個三元組(h,r,t),可以用式(4)所示的損失公式進行訓練:

‖h′+r-t′‖]+

(4)

其中,h′和t′是錯誤的三元組向量,作為訓練的負樣本。該類負樣本是將TransE算法定義的正樣本,也就是原來正確三元組的頭實體或者尾實體隨機替換成其他實體而得。γ為間距大小,一般設γ=1。符號[·]+表示合頁損失函數,形式化描述如式(5)所示。

(5)

在整個訓練過程中,TransE采用了最大間距的思想,拉開正樣本和負樣本向量之間的距離進行訓練學習。通過隨機梯度下降不斷迭代,使損失函數達到最優。最終的訓練結果是:1)在知識圖譜中相似的實體,在低維空間里面的距離相近;2)頭節點的向量加上關系向量基本等于尾節點的向量。具體過程訓練見文獻[12]。

2.1.2 語義相似性度量

上一節所述的TransE算法將對象表示成為一組低維實值向量,且使得這些向量的值滿足是一組連續實數的限定條件。在不同的知識圖譜表示學習方法中,向量的含義有所不同,也就需要不同的相似性度量。式(6)給出了TransE算法中向量的表示形式:

‖h+r‖≈t

(6)

其中,h和t分別是頭實體向量和尾實體向量,r是關系向量,式子中的范數‖·‖可以選擇L1范數或者L2范數。在知識圖譜里越接近的實體,向量也就越相似,如圖4所示。

圖4 TransE模型

由于TransE算法選擇歐氏距離計算損失函數,因此本文采用同等范數的歐氏距離對實體進行相似性度量。其中,選擇的歐氏距離的范圍為[0,∞),相似性度量范圍為[0,1]。對于A和B兩個實體向量,通過數學變換使兩個值域一一對應,最終的語義相似性度量公式如式(7)所示。

(7)

從上式中可以看出,當simsem(A,B)的計算的數值越接近1,實體向量A和B就越相似,即知識圖譜里兩者的關系就越緊密。相反,如果simsem(A,B)的數值為低,則意味著A和B關系越疏遠,即語義相似度越低。

在利用語義相似性進行推薦時,使用和基于物品的協同過濾推薦類似的流程,根據式(7)生成了一個語義的物品-物品相似性矩陣,如表1所示。

表1 語義的物品-物品相似性矩陣

在表1的相似性矩陣中,aij是序號為i的物品和序號為j的物品之間的語義相似性,通過式(7)計算而得,相似性矩陣元素滿足條件aij=aji。矩陣第i行所構成的集合定義為序號i物品的語義近鄰元素,簡稱為語義近鄰。利用這種語義近鄰,將基于協同過濾推薦得到的協同過濾近鄰集進行語義融合替換,最終得到所需的推薦列表。

2.1.3 融合語義近鄰

算法1融合語義近鄰算法

輸入協同過濾近鄰集I,語義近鄰集T

輸出推薦集C

1.Set L=list(I),K=list(T)

2.for Li∈{Ll-n,Ll-n+1,…,Ll} do:

3. for Kj∈{K1,K2,…,Kn} do:

4. Li=Kj

5. end do

6.end do

7.Set C=set(L)

利用這一過程得到了最終的推薦集C。

2.2 算法描述

結合圖1的算法流程,描述本文算法如下:

算法2TransE-CF算法

輸入物品-用戶評分矩陣Rm×n,該物品所在領域的知識圖譜KG

輸出基于知識圖譜表示學習的協同過濾推薦算法TransE-CF

2)將物品與知識圖譜KG中的實體進行一一對應,得到一個實體對應表。

3)將知識圖譜KG中的實體和關系分別轉化為向量集E和R。

4)根據式(7)對第3)步得到的結果分別計算物品間的語義相似性simsem(A,B),生成語義的物品-物品相似性矩陣,并根據2.1.3節對其進行過濾,得到語義近鄰集合。

5)利用第2)步的結果,選擇融合比例,根據算法1對第1)步生成的潛在推薦物品和第4)步所生成的語義近鄰集合進行融合替換,得到最終推薦所需的物品集合推送給用戶。

3 實驗設置及結果分析

3.1 數據集

本節主要針對上述已提出的TransE-CF算法的有效性進行實驗與分析,其中實驗數據集為加州大學圣迭戈分校提供的Amazon的電影評分數據。該數據集為Amazon的商品評分及其元數據。對每條數據記錄而言,主要描述了不同用戶對電影的評分,分值從1分到5分逐漸增高,分別對應于用戶對電影的差評到好評。同時,使用metadata將每條記錄中電影的Amazon編號asin與知識圖譜里該部電影的名字所表示的電影實體一一對應。

在知識圖譜的數據集選擇方面,本文選用了2012-11-09版本的Freebase中的電影本體。該電影本體數據主要包括了電影、導演、演員等本體對象。為了將Freebase提供的多個本體對象進行融合,本文用實體的名稱替換了Freebase自身的id,提取出所需要的實體和關系。同時,為了降低噪聲數據的影響,選擇了Freebase中1979年以后發布的電影與Amazon評分進行匹配,并篩選去除了出現次數少于3次的關系,最終得到“genre” “starring_actor”等總共20個知識圖譜的語義關系。

同時,為了使得Amazon評分數據和Freebase更好地匹配,本文對電影名稱進行了進一步的處理。由于知識圖譜采用的是無監督或者是半監督的關系抽取手段[21],因此Freebase中的電影名稱抽取結果受限于該處理手段,存在物品名稱和本體實體名稱字面無法完全匹配的問題。例如,存在有的電影使用羅馬數字II,而有的使用阿拉伯數字2。此外,例如電影Here Comes the Groom(1934)和電影Here Comes the Groom實質上是同一部電影但由于物品版本號的不同,造成Amazon電影名和Freebase電影本體的名稱匹配時無法完全對應。

針對上述問題,本文采用了編輯距離和字符串規則匹配相結合的方式對電影名稱進行了版本號刪除等數據預清洗工作。通過編輯距離算法對原數據進行字符串字面相似性識別矯正,得到了較好的清洗結果。經過最終處理得到包括672 910項用戶數據和41 255部電影數據,以及20個語義關系的實驗數據集。本文對該評分數據集進行了劃分,其中80%作為訓練集,20%作為測試集,訓練集用于構建評分矩陣,測試集用于測試算法性能。

3.2 評價指標

對于推薦系統算法推薦的結果,使用3個指標對其進行分析:準確率(Precision),召回率(Recall),F值(F-measure)。這3個指標可以從混淆矩陣中導出,如表2所示。

表2 混淆矩陣

根據混淆矩陣,有公式如下:

召回率(Recall):

(8)

準確率(Precision):

(9)

F值:

(10)

召回率反映了被推薦系統所推薦的物品占用戶真正喜歡的物品的比重。準確率反映了推薦系統的推薦水平,能將用戶喜歡的物品推薦給用戶,而用戶不喜歡的物品則不推薦。F值是準確率和召回率的加權平均,均勻地反映了推薦效果。

3.3 實驗結果分析

實驗硬件處理器型號為Intel(R) Core(TM) i7-6700,內存為8 GB;實驗軟件環境為Python 3.5。

3.3.1 混合比例的調整確定

本文所提出的算法中可調節的參數為兩者的融合比例,在融合比例取不同值時,所取得的推薦效果也有所不同。選取Top-k的鄰居數k=100,表示學習嵌入為200,實驗從完全使用語義進行推薦(0∶10)到完全使用協同過濾進行推薦(10∶0)分別取值,圖5～圖7分別為準確率、召回率和F值曲線。對于每一組實驗,均循環10次并取其平均值。

圖5 k=100時的召回率

圖6 k=100時的準確率

圖7 k=100時的F值

從圖5～圖7可以看出,隨著融合比例的提高,準確率、召回率和F值均有所提升,并在比例為5∶5時達到了頂峰。對于k=100的情況,融合比例為5∶5時效果最好。

3.3.2 表示學習的嵌入維度比較

知識圖譜表示學習是將知識圖譜嵌進一個低維的空間里,對于不同維度會有不同的效果。選取100維～500維分別進行實驗,對于每一組實驗,均循環10次并取其平均值。

從圖8～圖10可以看出各個維度對推薦效果的影響。從圖中得出,在選取200維時取得最佳。

圖8 不同維度的召回率

圖9 不同維度的準確率

圖10 不同維度的F值

3.3.3 算法比較

這里選取F值最高的比例作為代表,與其他協同過濾推薦算法進行比較。選取嵌入維度為200,k近鄰數分別為60、80、100、120。對于每一組實驗,均循環10次并取其平均值。

從圖11～圖13可以看出,本文提出的基于知識圖譜表示學習的協同過濾推薦算法,優于協同過濾推薦算法,利用語義信息可以在一定程度上對協同過濾推薦算法進行改進,在召回率、準確率和F值上均有所提升,可以在語義上彌補基于物品的協同過濾算法的不足。

圖11 不同k值的召回率

圖12 不同k值的準確率

圖13 不同k值的F值

4 結束語

本文提出了一種基于知識圖譜表示學習的協同過濾推薦算法,既利用了物品本身內在的語義信息,又使用了物品外在的評分矩陣,能夠更加全面地反映物品的屬性。算法通過知識圖譜表示學習將實體嵌入到低維空間里,計算實體間的語義相似性,并將其融入到推薦系統中,在語義的層面上增強了協同過濾推薦的效果,解決了協同過濾推薦未考慮語義的問題,提高協同過濾推薦的精度;同時又利用語義的信息,在一定程度上解決了冷啟動問題。實驗表明,基于知識圖譜表示學習的協同過濾推薦算法能夠提高推薦算法的效果。下一步將嘗試把該算法應用于電影本體以外內容進行推薦,并進一步優化推薦性能。

[1] 李文海,許舒人.基于Hadoop的電子商務推薦系統的設計與實現[J].計算機工程與設計,2014,35(1):130-136.

[2] SONG Bo,GAO Jie.The Enhancement and Application of Collaborative Filtering in e-Learning System[C]//Proceedings of International Conference in Swarm Intelligence.Berlin,Germany:Springer,2014:188-195.

[3] GARCIN F,ZHOU K,FALTINGS B,et al.Person-alized News Recommendation Based on Collaborative Filtering[C]//Proceedings of International Joint Con-ferences on Web Intelligence and Intelligent Agent Tech-nology.Washington D.C.,USA:IEEE Press,2012:164-173.

[4] 文俊浩,袁培雷,曾 駿,等.基于標簽主題的協同過濾推薦算法研究[J].計算機工程,2017,43(1):247-252,258.

[6] 楊興耀,于 炯,吐爾根·依布拉音,等.融合奇異性和擴散過程的協同過濾模型[J].軟件學報,2013,24(8):1868-1883.

[7] 楊 武,唐 瑞,盧 玲.基于內容的推薦與協同過濾融合的新聞推薦方法[J].計算機應用,2016,36(2):414-418.

[8] BOLLACKER K,EVANS C,PARITOSH P,et al.Freebase:A Collaboratively Created Graph Database for Structuring Human Knowledge[C]//Proceedings of ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2008:1247-1250.

[9] BIZER C,LEHMANN J,KOBILAROV G,et al.DBpedia——A Crystallization Point for the Web of Data[J].Web Semantics Science Services & Agents on the World Wide Web,2009,7(3):154-165.

[10] ZHANG Zijian,GONG Lin,XIE Jian.Ontology-based Collaborative Filtering Recommendation Algorithm[C]//Proceedings of International Conference on Brain Inspired Cognitive Systems.Berlin,Germany:Springer,2013:172-181.

[11] ZHANG Fuzheng,YUAN N J,LIAN Defu,et al.Collaborative Knowledge Base Embedding for Recom-mender Systems[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2016:353-362.

[12] BORDES A,USUNIER N,GARCIA-DURAN A,et al.Translating Embeddings for Modeling Multi-relational Data[C]//Proceedings of International Conference on Neural Information Processing Systems.New York,USA:ACM Press,2013:2787-2795.

[13] SARWAR B,KARYPIS G,KONSTAN J,et al.Item-based Collaborative Filtering Recommendation Algori-thms[C]//Proceedings of International Conference on World Wide Web.New York,USA:ACM Press,2001:285-295.

[14] BELL R,KOREN Y,VOLINSKY C.Modeling Relation-ships at Multiple Scales to Improve Accuracy of Large Recommender Systems[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2007:95-104.

[15] MIKOLOV T,SUTSKEVER I,CHEN K,et al.Distributed Representations of Words and Phrases and Their Com-positionality[C]//Proceedings of International Conference on Neural Information Processing Systems.New York,USA:ACM Press,2013:3111-3119.

[16] SOCHER R,CHEN Danqi,MANNING C D,et al.Reasoning with Neural Tensor Networks for Knowledge Base Completion[C]//Proceedings of International Conference on Neural Information Processing Systems.New York,USA:ACM Press,2013:926-934.

[17] NICKEL M,TRESP V,KRIEGEL H P.A Three-way Model for Collective Learning on Multi-relational Data[C]//Proceedings of the 28th International Conference on Machine Learning.Berlin,Germany:Springer,2011:809-816.

[18] WANG Zhen,ZHANG Jianwen,FENG Jianlin,et al.Knowledge Graph Embedding by Translating on Hyperplanes[C]//Proceedings of the 28th AAAI Conference on Artificial Intelligence.Berlin,Germany:Springer,2014:1112-1119.

[19] LIN Yankai,LIU Zhiyuan,ZHU Xuan,et al.Learning Entity and Relation Embeddings for Knowledge Graph Completion[C]//Proceedings of the 29th AAAI Con-ference on Artificial Intelligence.Berlin,Germany:Springer,2015:2181-2187.

[20] 劉 康,張元哲,紀國良,等.基于表示學習的知識庫問答研究進展與展望[J].自動化學報,2016,42(6):807-818.

[21] 肖 明,邱小花,黃 界,等.知識圖譜工具比較研究[J].圖書館雜志,2013,32(3):61-69.