一種知識圖譜的排序學習個性化推薦算法

楊晉吉，胡 波，王欣明，伍昱燊，趙淦森

(華南師范大學 計算機學院，廣州 510631)

1 引 言

隨著大數據時代的到來，網絡上不斷涌現的信息呈指數級增長，個性化推薦系統的作用越來越重要.盡管推薦系統的研究和應用均取得了很大的進展，但是它依然面臨著很多的挑戰，比如數據稀疏性問題、冷啟動問題、時效性問題、多樣性推薦問題等[1].傳統的推薦算法主要分為三類：協同過濾推薦算法、基于內容的推薦算法和混合推薦算法.這類推薦算法在一些應用場景下能取得良好的效果，但它們各自有一些缺陷，如協同過濾主要受冷啟動影響，并且難以針對具有特殊喜好的用戶進行個性化推薦；基于內容的推薦受物品內容信息提取技術的制約，而且推薦效果比較差；混合推薦難以整合多種推薦算法間的權重.針對傳統推薦系統存在的問題，現在很多新的推薦算法被提出來，其中包括排序學習、上下文感知推薦、基于深度學習推薦和社會化推薦等.其中排序學習逐漸成為了推薦系統研究的熱點[2]，基于排序學習的推薦模型將推薦問題轉化為排序問題，構建以排序學習為基礎的推薦算法框架，利用排序學習方法的優勢去解決多特征維度的推薦問題，可以有效地組織多種推薦模型，并自動優化模型權重參數，提高推薦效果[3].知識圖譜是一種基于圖的數據結構，由節點和邊組成.在知識圖譜里，每個節點表示現實世界中存在的“實體”，每條邊為實體與實體之間的“關系”，知識圖譜是關系的最有效表示方式，并且能夠融合多源異構信息.知識圖譜表示學習能夠將知識圖譜嵌入到一個低維空間，可以利用連續數值的向量反映知識圖譜的結構特征，這種方法可以高效地計算實體間的關系.

圍繞上述背景，本文提出了一種知識圖譜的排序學習個性化推薦算法.本文算法在文獻[4]的基礎上，通過排序學習構建反饋特征模型，融合用戶興趣遷移模型，再與基礎特征模型構建混合模型，最終通過排序學習進行Top-N推薦.本文算法考慮到用戶的長短期偏好和時效性因素，并解決了知識圖譜中不同特征的融合問題，提高了個性化推薦效果.

本文的結構描述如下，第2節介紹算法的相關理論，第3節闡述了本文提出的一種知識圖譜的排序學習個性化推薦算法及其實現，最后在第4節描述了本算法所使用的數據集，并進行了參數確定和算法比較的實驗.第5節對本文工作進行了總結和展望.

2 相關理論

2.1 基于深度學習的網絡表示

近幾年來，隨著知識圖譜的發展，業界已經積累了大量的開放本體庫，例如Freebase、DBpedia、WordNet等.這些本體庫包含了豐富的本體知識，在基于知識圖譜的推薦系統中融合實體上下文信息，能夠很好的解決冷啟動和推薦物品新穎性等問題，有效提高了推薦算法的性能[5].

圖1 將知識圖譜節點嵌入到K維空間

DeepWalk[6]算法第一次將深度學習的技術引入到網絡表示學習領域，DeepWalk把節點作為自然語言處理中的單詞，通過在網絡中進行隨機游走，獲得隨機游走路徑，把隨機游走路徑作為句子，這樣獲得的數據就可直接作為Word2Vec[7]算法的輸入，通過這種方法可以將網絡中的節點嵌入到一個K維空間，這種分布式表示能夠更好地發現實體之間的相關性.Node2Vec[8]通過改變隨機游走序列生成的方式進一步擴展了DeepWalk算法.它提出了一種帶偏置的隨機游走策略，這種策略可以有效地檢索分散的相鄰節點.Node2Vec通過參數p和q能夠兼顧深度游走(Depth-First Search)和廣度游走(Breadth-First Search).

圖2 從節點u出發的BFS和DFS游走

廣度優先游走側重鄰近的節點并刻畫了節點間的同構性，深度優先游走反映了更高層面上的節點間的同質性.其中游走的條件概率為：

(1)

其中πvx是未歸一化的概率，Z是歸一化常數，對于最簡單的情況，可以用節點v和x之間邊的權重ωvx作為未歸一化概率πvx=ωvx.t是上一個節點，v是當前節點，x是下一個可能的節點對于2階隨機游走，未歸一化概率和權重之間的關系為：πvx=αpq(t，x)·ωvx，系數αpq(t，x)如下：

(2)

dtx表示節點t和x之間的最短距離，p是return參數，q是in-out參數.Node2Vec能夠同時考慮到網絡中局部和宏觀信息，并且有很高的計算效率和適應性，能夠有效提取網絡中節點的特征.

圖3 Node2Vec算法(修改自文獻[8])

2.2 用戶興趣遷移模型

用戶對于某些物品的感興趣程度或關注程度會隨著時間推移和交互情況動態增加或減少，然而傳統的推薦算法無法反映用戶行為數據的動態變化，因此，無法正確解決用戶興趣遷移問題，而融合用戶遷移模型的推薦系統能夠提高個性化推薦效果.

通過給知識圖譜模型中的節點間分配不同的權重可以體現用戶對不同物品的興趣差異.用戶興趣遷移模型通過用戶行為的時間與次數來對知識圖譜中的節點間連接權重進行動態修改，能夠反映出用戶的興趣遷移.用戶行為越接近當前時間，同種行為的次數越多，節點間分配到的權重越大，用戶對該節點的興趣度越大.反之，節點之間的連接權重越小.

用戶Ui和物品Ij兩個節點間連接權重如公式(3)所示：

(3)

其中，t為當前時間，n為同種行為的次數，ts為用戶對物品產生反饋的行為時間，t0為用戶興趣遷移的時間因子，w表示權重閾值，即用戶隨著時間推移，能夠提供的推薦能力逐漸減小，最后趨于常量w，因此可以根據用戶興趣遷移模型動態更新知識圖譜.

2.3 基于排序學習的推薦算法

近幾年，研究人員發現：如果僅僅依據用戶對項目的評分，產生的推薦結果并不能準確地體現用戶的偏好[9].為了解決傳統推薦算法所存在的上述問題，研究人員考慮將排序學習技術[10]融合進推薦算法的推薦過程中.排序學習方法把用戶間推薦得分的計算轉化為對一個多特征向量的二分類問題，很好地解決高維特征帶來的多參數估計問題.排序學習推薦模型基本流程如圖4所示：

(4)

相應的標注集合Y為

Y={yU1I1，yU1I2，yU1I3，…，yUiIj}

(5)

圖4 基于排序學習推薦模型基本流程

排序學習提出利用機器學習的方法去解決排序問題，是基于機器學習中解決分類與回歸問題的思想.排序學習的目標在于自動地從訓練數據中學習得到一個排序函數，使其在文本檢索中能夠針對文本的相關性、重要性等多種衡量標準對文本進行排序.排序學習的優勢是：整合大量復雜特征并自動進行參數調整，自動學習最優參數，降低了單一考慮排序因素的風險，同時，能夠通過眾多有效手段規避過擬合問題.因此，基于排序學習的推薦模型能夠提高個性化推薦效果，比較典型的排序學習算法有Ranking SVM、LambdaMART、RankNet、RankBoost、AdaRank等.

3 一種知識圖譜的排序學習個性化推薦

本文提出了一種知識圖譜的排序學習個性化推薦算法，其基本思想是：首先構建基礎知識圖譜，通過基于深度學習的Node2Vec網絡表示算法，將知識圖譜中的實體嵌入到一個低維空間，然后計算用戶物品之間的相似性，構建訓練模型作為排序學習的輸入，通過目標函數調節不同特征的重要程度來達到最優結果，對基礎推薦模型產生的特征比例權重集合，融合用戶興趣遷移模型生成混合知識圖譜，通過Node2Vec構建反饋特征模型，與基礎推薦模型構成混合模型.最終，在混合模型上進行排序學習，產生Top-N推薦列表.本文算法既能解決知識圖譜異構特征間的權重比例，也能夠考慮用戶的長期、短期偏好和用戶興趣遷移等因素，能夠提高個性化推薦效果.圖5給出了本文算法的流程圖：

3.1 基于帶權深度游走的知識圖譜特征抽取

傳統推薦算法使用鄰接矩陣進行數據存儲和運算，這種數據表示方法受到計算效率問題的影響.如鄰接矩陣A占用了|V|×|V|的存儲空間，這在|V|增長到百萬級時通常是難以計算和處理的.另一方面，鄰接矩陣中絕大多數是0，數據十分稀疏.這種數據稀疏性使得快速有效的統計學習方法的應用變得困難[11].

知識圖譜能夠融合語義、上下文和異構特征信息，通過邊的權重能夠體現節點間的相互關系.本文提出的一種知識圖譜的排序學習推薦算法在知識圖譜上進行深度游走，既能夠考慮節點間的同構性也能夠考慮節點間的同質性，并且能夠很好支持異構信息的融合和考慮用戶興趣遷移情況.

圖5 一種知識圖譜的排序學習個性化推薦算法流程

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

圖6 融合上下文和異構信息，構建電影知識圖譜

在本文算法中使用Node2Vec進行知識圖譜網絡特征學習，將實體映射到K維空間，在K維向量空間中，幾何上越接近的實體相關性越大，本文算法通過向量的余弦相似度來計算實體ei和ej之間的相關性Sim(ei，ej).

(6)

(7)

此外，在知識圖譜中權重可以代表用戶對物品的偏好情況，物品和特征間的相關性.在文獻[4]推薦算法中，把數據集中評分大于4用以表明用戶User和物品Item間有關系，設置邊的權重為1，沒有關系則設置為0.把邊僅僅簡單地看作0，1值，因此該算法沒有考慮不同特征對推薦結果的重要性是不同的，也沒有考慮到用戶的偏好因素影響，也沒有考慮到人們興趣隨著時間發生偏移的情況.

由于上述原因，本文在該算法基礎上，提出了一種融合基礎模型，反饋模型和用戶興趣遷移的混合推薦模型.

3.2 融合長短期偏好和興趣遷移的混合推薦模型

從長期來看，用戶的興趣喜好是相對穩定的，基于用戶大量的歷史數據進行推薦可以基本反映用戶的一般偏好.但是，從心理學角度看，用戶偏好受長期個人興趣和短期個人興趣兩方面影響，并且存在一定的相互聯系.

基于上述原因，本文在基于排序學習的Top-N推薦框架上進行拓展，用基礎知識圖譜衡量用戶的長期偏好.通過反饋模型和用戶興趣偏移模型構建混合知識圖譜模型，用它衡量物品內容的動態變化、用戶興趣的短期波動等時效性因素.

通過3.1節中基于基礎知識圖譜的排序學習推薦模型能夠獲得多維特征對推薦結果的權重集合Z={η1，η2，η3，…，η|feature|}，通過把影響權重因子集合Z和用戶興趣遷移模型融合，構建混合知識圖譜.

混合知識圖譜實體間權重更新策略如下：

(8)

其中RWij為更新后實體i和實體j之間邊的權重，wij是經用戶興趣遷移模型計算后的興趣度，關系k指的是用戶i和物品j之間是評分關系，rating是用戶對物品的評分，λ是歸一化因子，使得λ×rating歸一化于初始權重1，防止評分過大而對隨機游走造成影響.

對訓練集中的用戶物品對(Ui，Ij)，在融合了所有物品特征和用戶興趣遷移的混合知識圖譜上進行Node2Vec深度游走，抽取相似性特征Sim(Ui，Ij)mix.與3.1節公式(7)構建混合特征模型：

(9)

3.3 算法描述

算法步驟如表1所示.

4 實驗結果及分析

4.1 數據集

本文所用的基礎數據集是Movielens 1M[12]，包含6040個用戶，3900個電影和100多萬條匿名評分組成.由于本文算法驗證用戶興趣隨著時間的動態遷移情況，故將融合DBpedia上下文信息后的數據集[13]，按照時間戳順序劃分為8：2，分別作為訓練集和測試集.

4.2 評價指標

本文實驗中所用到的評估指標[14]主要有P@N、MAP，下面分別對其進行說明.

P@N本身是Precision@N的簡稱，指的是對特定的查詢，考慮位置因素，檢測前N條結果的準確率.例如對單次搜索的結果中前100篇，如果有82篇為相關文檔，則P@100=82/100=0.82.

表1 算法步驟

測試通常會使用一個查詢集合，包含若干條不同的查詢詞，在實際使用P@N進行評估時，通常使用所有查詢的P@N數據，計算算術平均值，用來評判該系統的整體搜索結果質量.

(10)

MAP指標通常用于衡量系統在所有排序結果中相關文檔的排序質量.在一個排序結果中，AP(平均查準率)用來計算一個查詢的排序結果的精度，MAP是對所有查詢的精度取平均值.其相關定義如下所示：

(11)

(12)

(13)

其中，yi，j表示相關度，取二元值0和1.若第i個查詢的第j個文檔是相關的，p(j)計算查詢i排序結果中排在文檔j前面的相關文檔的比例.

對于Top-N的電影推薦結果，電影排得越靠前，被用戶瀏覽到的可能性就越大，因此在評測的過程中，相關度越高的電影，在最終的結果列表中排得位置越靠前，評測函數應該給予更高的權重.

4.3 實驗結果分析1

實驗硬件，處理器型號為Intel(R)Xeon(R)CPU E5-2620 v2 @ 2.10GHz，內存為80GB；實驗軟件環境為Python 2.7.12、JDK 1.8.

4.3.1 調整確定特征參數

本文所提出算法的參數參考文獻[6]通過在該數據集上實驗所確定的最佳參數.

通過表2能夠發現在該數據集上，p，q分別為1，4時實驗效果最好，并用LambdaMark算法進行排序學習.

表2 排序學習算法在不同p，q下結果

通過表3能發現經過排序學習訓練完決策函數后，該數據集中不同特征對推薦結果的比例權重是不同的.我們通過決策函數反饋的集合Z={η1，η2，η3，…，η|features|}和用戶興趣遷移模型構建反饋模型.

表3 特征權重比例

4.3.2 算法比較

最后在該數據集上，使用基于Python的開源庫SurpriseLib實現對比實驗，排序算法使用基于Java的開源RankLib庫實現.對比結果如表4.

表4 對比實驗結果

通過表4能夠發現，本文提出的一種知識圖譜的排序學習個性化推薦算法在P@N和MAP上均有所提升，算法能夠充分考慮到長短期偏好和用戶興趣的遷移.

5 結束語

本文提出了一種知識圖譜的排序學習個性化推薦算法，不但利用了人和物品間的評分信息，也包含了物品的上下文信息，并且考慮長期、短期偏好，因此能夠全面地反映出人和物品之間的關系.針對傳統推薦算法中多維特征的參數難以估計的痛點，本文算法通過排序學習方法獲取不同特征的權重比例進行反饋，構建混合知識圖譜，通過基于深度學習的網絡特征表示模型構建特征模型，最終與基礎特征模型結合，構建混合模型進行推薦.通過在Movielens數據集上驗證了本文算法的有效性.

本文算法模型沒有融合用戶的畫像特征，而這些特征對推薦系統的意義十分重要.未來將會嘗試把用戶畫像特征融合到本算法模型中，挖掘用戶的行為模式，并實現在線學習系統.