基于知識圖譜的興趣點推薦算法

文/周翔宇 高仲合

1 引言

當下互聯網發展迅速，導致各類互聯網產品存在嚴重的信息過載問題，因此研究構建推薦系統來為個人用戶在使用互聯網應用的場景下盡可能的捕捉用戶需求，從而推測用戶可能最為感興趣的信息給用戶推送。推薦系統能夠有效解決信息爆炸帶來的信息過載的現狀，有效地提升用戶獲取所需信息的效率，為了進一步提升用戶對產品的易用性，構建推薦系統也成為目前擁有大量數據信息的互聯網企業研究的重要方向。將知識圖譜應用于推薦算法之中，無疑會解決一系列難題。

2 基于知識圖譜的推薦算法

2.1 傳統推薦算法

構建一個推薦系統最核心的部分就是選擇合適的推薦策略。協同過濾算法是一種經典的推薦算法，協同過濾的中心思想是通過計算推薦用戶或者推薦項之間的相似度來作為度量指標進行排序，協同過濾算法的適用場景多為特征維度較低的物品推薦。且其算法思想易于理解，而對于高維數據協同過濾的推薦效果并不理想，這是因為對于如電影、圖像此類對象，不適用于對其進行特征工程構建。

基于高維數據的推薦系統構建通常會使用深度學習方法，這是因為深度學習技術的技術無需對原始數據進行復雜的特征工程，直接通過構建網絡結構并將數據進行向量化輸入訓練，網絡模型會自行學到樣本數據中隱藏的特征和關系，通過輸入用戶和推薦項的向量化的特征表示，預測推薦項得分或點擊率的預估值作為輸出。深度學習的也存在弊端，一是在樣本量不足的情況下非常容易過擬合，二是不具有良好的可解釋性。

2.2 知識圖譜概述

知識圖譜技術具有強大語義處理能力和知識表達能力。知識圖譜的特點是具有強表述能力，它將知識抽象化成“實體”和“關系”，而“實體”是一個個離散的個體，“關系”將各個分開的實體聯系起來組成了知識，這種節點和連接線組成的數據結構是一種圖的結構，因此稱為知識圖譜。

在構建知識圖譜的過程中，為了方便計算機對知識進行理解和處理，通常會使用“三元組”的結構來對知識進行表述。比如“小周就讀于曲阜師范大學”這一條知識，實體是“小周”和“曲阜師范大學”，關系是“就讀于”。這條知識的拓撲結構如圖1所示。

以上是一條知識的示例，通過將不同的多個知識匯聚起來，就稱為知識庫。通過構建知識圖譜可以有效地將客觀物質世界存在的知識進行表述，不僅滿足適合計算機的理解和處理，也十分接近人類對知識的認知。可以說知識圖譜是一種能夠有效將海量信息進行管理和組織的表述方式。

2.3 基于知識圖譜進行推薦的算法

由于傳統的協同過濾的推薦方法存在一定的缺陷，深度學習的方法更偏向于一個黑盒模型不具有可解釋性，所以本文提出一種通過構造知識圖譜的思路對協同過濾進行優化，應用于興趣點的推薦領域。用戶行為數據具有稀疏性和時序性的特點，待推薦的興趣點之間又有著復雜的關系。因此非常適合使用知識圖譜來對興趣點數據和用戶數據進行信息抽取，通過建立一個完善的興趣點推薦領域的知識圖譜，來實現基于某個領域知識圖譜的個性化推薦系統。

本節將提出一種適用于對興趣點推薦的策略，由三個步驟構成，分別為興趣點實體提取、構建興趣點實體關系網絡、興趣點知識推薦。

2.3.1 興趣點實體提取

興趣點實體提取分為兩步，首先進行候選興趣點實體的選取，然后從候選實體集中過濾抽取關鍵詞。候選興趣點實體提取的思路如下：

輸入：興趣點領域用戶數據集D

過程：

遍歷數據集D：

（1）構建一個空的候選實體集S

（2）對數據集中的每條簽到樣本Xi分詞，得到詞匯集Wi

圖1：知識拓撲結構圖

圖2：組合屬性知識圖

（3）對Wi中內容進行關鍵詞提取作為實體集Si

（4）將Si的內容追加到實體集S中

（5）遍歷實體集S：

對S中每個實體Si在剩余實體中遍歷相同語義的實體Sj

在實體集S中刪除Sj元素

輸出：篩選后的實體集S

2.3.2 構建興趣點實體關系網絡與興趣點知識推薦

興趣點領域知識圖譜就是對興趣點實體的進行構建的屬性關系網，這種圖模型結構能夠很好的表達出實體之間的關系，這個興趣點關系網絡可以是具有同樣屬性的興趣點，也可以是具有上下文特征的興趣點實體關系。對于構建一個推薦系統來說，這個興趣點圖譜中的各個實體不僅僅是推薦的興趣點內容，它還包含了如用戶的信息、標簽等信息，所以知識圖譜能夠為興趣點實體推薦提供一個有效的關系網絡。

構建興趣點實體關系網絡的方法包含屬性遍歷、上下文特征實體遍歷、多路徑遍歷對比3種方法。

屬性遍歷是根據興趣點實體之間的強相關性進行連接，知識圖譜中存在一些實體具有相同的父實體，通過父實體能夠連接都其他具有一階關聯的興趣點實體，如圖2所示，此類場景是在推薦中最適用，比如用戶曾搜索過漢庭酒店，則找到漢庭酒店的父實體，通過父實體可以理解為用戶希望尋找一個酒店，此時推薦如銀座酒店、如家快捷酒店一類的連接同一父實體的子實體，這樣的推薦結果是非常符合實際的用戶需求的。

圖3：帶有權重的知識圖

圖4：美食店鋪名稱詞云

上下文特征實體遍歷適用于具有上下位關系的實體推薦，具體的含義為在事件1發生后的下一步操作或必要條件、在興趣點領域的推薦中，例如在餐飲等類型發生簽到行為，則可以根據下位關系推測用戶下一步的簽到點可能為休閑娛樂類型的實體。不過也不是所有的具有下位關系的實體都是能具有較高的推薦優先級的，例如：筆記本貼紙與筆記本相關，但不是每個人都會貼筆記本貼紙，因此得出結論，下位關系事件也存在低概率發生的情況，這部分低概率事件應該排列在推薦列表中其他的高概率遍歷實體之后。

在構建的興趣點領域知識圖譜中，實體和實體之間的關系是網狀的，所以在遍歷圖的時候會存在兩個實體之間可以通過多種遍歷邏輯推理得到，即由一個實體到另一個實體之間可能有多個連接關系。此時需要采取一種方式來多種遍歷邏輯的結果是最應該采用的。多路徑遍歷對比可以有效解決這個問題，根據邊的權重計算得到兩個實體的相關度。如圖3所示。

多路徑遍歷算法計算過程如下：

輸入：知識三元組的集合S={(e0,w1,e1),(e1,w2,e2),…,(en,wm,em)}

過程：

遍歷集合S：

（1）定義一個空的路徑集合L{}；

（2）讀取Tuple3i，取Tuple3中下標為2的實體元素Tuple3i(2)；

（3）定義一個空的實體集合si；

（4） 遍 歷 集 合 S，將 Tuple3(0)=Tuple3i(2)的實體元素；

（5）將滿足條件的實體元素追加到si中；

（6）將si追加到L{}中；

（7）得到所有的路徑集合L；

（8）計算L中各個路徑的權重之和，得到最優路徑l。

通過多路徑遍歷算法可以得到當用戶發生某個實體表示的行為時，可以預測出用戶后續可能會發生的多個行為，因此根據此預測結果進行推薦是具有實際價值的。

3 實驗驗證

3.1 實驗方案及目的

實驗使用Python爬蟲美團網站的興趣點數據，構建面向興趣點的知識圖譜并實現推薦算法，通過展現召回率來對算法進行性能評估。本次實驗目的是通過算法來驗證知識圖譜技術在推薦領域的技術可行性并嘗試構建興趣點領域合適的圖譜來完成用戶喜好預測的功能。

3.2 實驗步驟

3.2.1 圖譜實體獲取

通過Python編程抓取美團美食店鋪信息，獲得興趣點信息詞條，按照篩法提取名詞（分批進行，每批維護一個不可重集合）。將各個批次詞求交集，生成興趣點詞典，獲取每個詞條的所屬類別，同時剔除不屬于興趣點的無關詞條。在進行實體獲取的時候對詞條考慮上下文特征，使用一個滑動窗口，假設窗口大小為3，每次看3個單詞，看完之后往后滑一格，最后得到一組句子層面的特征，其中包括word feature和 position feature。Word feature包括每個詞本身和其上下文單詞的詞向量表示，Position feature是指每個單詞到實體的距離。如圖4所示。

3.2.2 命名實體識別

將去重后的實體集識別為命名實體（person，location，type），若實體庫沒有，則進行手工標注。對于非命名實體部分，采用一定的詞組合和詞性規則，在O(n)時間掃描所有分詞，過濾掉不可能為興趣點實體的部分（例如動詞肯定不是興趣點實體），對剩余詞及詞組合，匹配知識庫中以分好類的實體。如果沒有匹配到實體，或者匹配到的實體屬于0類（即非實體），則將其過濾掉。

3.2.3 實體關系抽取

實體關系抽取需要分析詞法特征，詞法特征大致包括實體本身詞的詞性，實體之前單詞序列、詞的上位詞等特征。對詞法層面的特征：將詞轉化成詞向量，使用詞向量來表示詞法層面的特征。對句法層面的特征： 考慮上下文特征，使用一個滑動窗口，假設窗口大小為3，每次看3個單詞，看完之后往后滑一格，最后得到一組句子層面的特征。包括word feature和position feature。Word feature包括每個詞本身和其上下文單詞的詞向量表示，Position feature是指每個單詞到實體的距離。利用語句的詞法、句法、語義等信息可以得到實體間的關系。

為了方便進行圖計算，將抽取的實體關系使用Neo4j進行存儲，傳統關系型數據庫的表示形式如下，存儲是數據表模型包含實體表和關系表。

表1：實體表

表2：關系表

Neo4j的鄰接表；

根據核心數據源，對興趣點的不同類別進行相關推薦，輸入信息表，輸出相關推薦表格。

3.3 實驗結果分析

通過構建圖數據表，實驗結果展示如下：

輸入：總表poi_excel_all(poi_excel.csv)、item的推薦表(poi_excel_name.csv)、觸發詞

輸出：興趣點推薦

例如：

trigger_word = '火鍋'

item_recomend(search_word,poi_excel_all,recomend_item,topn = 10)

返回結果：

如表3所示。

通過召回率來表示圖譜推薦性能，實體識別召回率=實體解析正確數/相關實體總數；

通過表4可以分析得出，適當增加實體的數目能夠有效提升圖譜的推薦性能，這恰好符合實際的應用場景，當實體數目過少時圖譜會被迫得分較低的興趣點實體中選擇加入推薦列表。當實體數目足夠時，才能夠有效進行圖譜推薦。

表3：推薦列表示例

表4：實體數目與召回率關系表