一種知識(shí)圖譜的排序?qū)W習(xí)個(gè)性化推薦算法

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

(華南師范大學(xué) 計(jì)算機(jī)學(xué)院，廣州 510631)

1 引 言

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

圍繞上述背景，本文提出了一種知識(shí)圖譜的排序?qū)W習(xí)個(gè)性化推薦算法.本文算法在文獻(xiàn)[4]的基礎(chǔ)上，通過(guò)排序?qū)W習(xí)構(gòu)建反饋特征模型，融合用戶興趣遷移模型，再與基礎(chǔ)特征模型構(gòu)建混合模型，最終通過(guò)排序?qū)W習(xí)進(jìn)行Top-N推薦.本文算法考慮到用戶的長(zhǎng)短期偏好和時(shí)效性因素，并解決了知識(shí)圖譜中不同特征的融合問(wèn)題，提高了個(gè)性化推薦效果.

本文的結(jié)構(gòu)描述如下，第2節(jié)介紹算法的相關(guān)理論，第3節(jié)闡述了本文提出的一種知識(shí)圖譜的排序?qū)W習(xí)個(gè)性化推薦算法及其實(shí)現(xiàn)，最后在第4節(jié)描述了本算法所使用的數(shù)據(jù)集，并進(jìn)行了參數(shù)確定和算法比較的實(shí)驗(yàn).第5節(jié)對(duì)本文工作進(jìn)行了總結(jié)和展望.

2 相關(guān)理論

2.1 基于深度學(xué)習(xí)的網(wǎng)絡(luò)表示

近幾年來(lái)，隨著知識(shí)圖譜的發(fā)展，業(yè)界已經(jīng)積累了大量的開放本體庫(kù)，例如Freebase、DBpedia、WordNet等.這些本體庫(kù)包含了豐富的本體知識(shí)，在基于知識(shí)圖譜的推薦系統(tǒng)中融合實(shí)體上下文信息，能夠很好的解決冷啟動(dòng)和推薦物品新穎性等問(wèn)題，有效提高了推薦算法的性能[5].

圖1 將知識(shí)圖譜節(jié)點(diǎn)嵌入到K維空間

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

圖2 從節(jié)點(diǎn)u出發(fā)的BFS和DFS游走

廣度優(yōu)先游走側(cè)重鄰近的節(jié)點(diǎn)并刻畫了節(jié)點(diǎn)間的同構(gòu)性，深度優(yōu)先游走反映了更高層面上的節(jié)點(diǎn)間的同質(zhì)性.其中游走的條件概率為：

(1)

其中πvx是未歸一化的概率，Z是歸一化常數(shù)，對(duì)于最簡(jiǎn)單的情況，可以用節(jié)點(diǎn)v和x之間邊的權(quán)重ωvx作為未歸一化概率πvx=ωvx.t是上一個(gè)節(jié)點(diǎn)，v是當(dāng)前節(jié)點(diǎn)，x是下一個(gè)可能的節(jié)點(diǎn)對(duì)于2階隨機(jī)游走，未歸一化概率和權(quán)重之間的關(guān)系為：πvx=αpq(t，x)·ωvx，系數(shù)αpq(t，x)如下：

(2)

dtx表示節(jié)點(diǎn)t和x之間的最短距離，p是return參數(shù)，q是in-out參數(shù).Node2Vec能夠同時(shí)考慮到網(wǎng)絡(luò)中局部和宏觀信息，并且有很高的計(jì)算效率和適應(yīng)性，能夠有效提取網(wǎng)絡(luò)中節(jié)點(diǎn)的特征.

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

2.2 用戶興趣遷移模型

用戶對(duì)于某些物品的感興趣程度或關(guān)注程度會(huì)隨著時(shí)間推移和交互情況動(dòng)態(tài)增加或減少，然而傳統(tǒng)的推薦算法無(wú)法反映用戶行為數(shù)據(jù)的動(dòng)態(tài)變化，因此，無(wú)法正確解決用戶興趣遷移問(wèn)題，而融合用戶遷移模型的推薦系統(tǒng)能夠提高個(gè)性化推薦效果.

通過(guò)給知識(shí)圖譜模型中的節(jié)點(diǎn)間分配不同的權(quán)重可以體現(xiàn)用戶對(duì)不同物品的興趣差異.用戶興趣遷移模型通過(guò)用戶行為的時(shí)間與次數(shù)來(lái)對(duì)知識(shí)圖譜中的節(jié)點(diǎn)間連接權(quán)重進(jìn)行動(dòng)態(tài)修改，能夠反映出用戶的興趣遷移.用戶行為越接近當(dāng)前時(shí)間，同種行為的次數(shù)越多，節(jié)點(diǎn)間分配到的權(quán)重越大，用戶對(duì)該節(jié)點(diǎn)的興趣度越大.反之，節(jié)點(diǎn)之間的連接權(quán)重越小.

用戶Ui和物品Ij兩個(gè)節(jié)點(diǎn)間連接權(quán)重如公式(3)所示：

(3)

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

2.3 基于排序?qū)W習(xí)的推薦算法

近幾年，研究人員發(fā)現(xiàn)：如果僅僅依據(jù)用戶對(duì)項(xiàng)目的評(píng)分，產(chǎn)生的推薦結(jié)果并不能準(zhǔn)確地體現(xiàn)用戶的偏好[9].為了解決傳統(tǒng)推薦算法所存在的上述問(wèn)題，研究人員考慮將排序?qū)W習(xí)技術(shù)[10]融合進(jìn)推薦算法的推薦過(guò)程中.排序?qū)W習(xí)方法把用戶間推薦得分的計(jì)算轉(zhuǎn)化為對(duì)一個(gè)多特征向量的二分類問(wèn)題，很好地解決高維特征帶來(lái)的多參數(shù)估計(jì)問(wèn)題.排序?qū)W習(xí)推薦模型基本流程如圖4所示：

(4)

相應(yīng)的標(biāo)注集合Y為

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

(5)

圖4 基于排序?qū)W習(xí)推薦模型基本流程

排序?qū)W習(xí)提出利用機(jī)器學(xué)習(xí)的方法去解決排序問(wèn)題，是基于機(jī)器學(xué)習(xí)中解決分類與回歸問(wèn)題的思想.排序?qū)W習(xí)的目標(biāo)在于自動(dòng)地從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)得到一個(gè)排序函數(shù)，使其在文本檢索中能夠針對(duì)文本的相關(guān)性、重要性等多種衡量標(biāo)準(zhǔn)對(duì)文本進(jìn)行排序.排序?qū)W習(xí)的優(yōu)勢(shì)是：整合大量復(fù)雜特征并自動(dòng)進(jìn)行參數(shù)調(diào)整，自動(dòng)學(xué)習(xí)最優(yōu)參數(shù)，降低了單一考慮排序因素的風(fēng)險(xiǎn)，同時(shí)，能夠通過(guò)眾多有效手段規(guī)避過(guò)擬合問(wèn)題.因此，基于排序?qū)W習(xí)的推薦模型能夠提高個(gè)性化推薦效果，比較典型的排序?qū)W習(xí)算法有Ranking SVM、LambdaMART、RankNet、RankBoost、AdaRank等.

3 一種知識(shí)圖譜的排序?qū)W習(xí)個(gè)性化推薦

本文提出了一種知識(shí)圖譜的排序?qū)W習(xí)個(gè)性化推薦算法，其基本思想是：首先構(gòu)建基礎(chǔ)知識(shí)圖譜，通過(guò)基于深度學(xué)習(xí)的Node2Vec網(wǎng)絡(luò)表示算法，將知識(shí)圖譜中的實(shí)體嵌入到一個(gè)低維空間，然后計(jì)算用戶物品之間的相似性，構(gòu)建訓(xùn)練模型作為排序?qū)W習(xí)的輸入，通過(guò)目標(biāo)函數(shù)調(diào)節(jié)不同特征的重要程度來(lái)達(dá)到最優(yōu)結(jié)果，對(duì)基礎(chǔ)推薦模型產(chǎn)生的特征比例權(quán)重集合，融合用戶興趣遷移模型生成混合知識(shí)圖譜，通過(guò)Node2Vec構(gòu)建反饋特征模型，與基礎(chǔ)推薦模型構(gòu)成混合模型.最終，在混合模型上進(jìn)行排序?qū)W習(xí)，產(chǎn)生Top-N推薦列表.本文算法既能解決知識(shí)圖譜異構(gòu)特征間的權(quán)重比例，也能夠考慮用戶的長(zhǎng)期、短期偏好和用戶興趣遷移等因素，能夠提高個(gè)性化推薦效果.圖5給出了本文算法的流程圖：

3.1 基于帶權(quán)深度游走的知識(shí)圖譜特征抽取

傳統(tǒng)推薦算法使用鄰接矩陣進(jìn)行數(shù)據(jù)存儲(chǔ)和運(yùn)算，這種數(shù)據(jù)表示方法受到計(jì)算效率問(wèn)題的影響.如鄰接矩陣A占用了|V|×|V|的存儲(chǔ)空間，這在|V|增長(zhǎng)到百萬(wàn)級(jí)時(shí)通常是難以計(jì)算和處理的.另一方面，鄰接矩陣中絕大多數(shù)是0，數(shù)據(jù)十分稀疏.這種數(shù)據(jù)稀疏性使得快速有效的統(tǒng)計(jì)學(xué)習(xí)方法的應(yīng)用變得困難[11].

知識(shí)圖譜能夠融合語(yǔ)義、上下文和異構(gòu)特征信息，通過(guò)邊的權(quán)重能夠體現(xiàn)節(jié)點(diǎn)間的相互關(guān)系.本文提出的一種知識(shí)圖譜的排序?qū)W習(xí)推薦算法在知識(shí)圖譜上進(jìn)行深度游走，既能夠考慮節(jié)點(diǎn)間的同構(gòu)性也能夠考慮節(jié)點(diǎn)間的同質(zhì)性，并且能夠很好支持異構(gòu)信息的融合和考慮用戶興趣遷移情況.

圖5 一種知識(shí)圖譜的排序?qū)W習(xí)個(gè)性化推薦算法流程

以電影領(lǐng)域?yàn)槔娪皩?shí)體中主要包括了演員、類型、導(dǎo)演等主要特征.這些異構(gòu)特征從一定的程度上概括了這部電影.利用電影特征，可以得到類似圖6所示的一個(gè)電影知識(shí)圖譜.

圖6 融合上下文和異構(gòu)信息，構(gòu)建電影知識(shí)圖譜

在本文算法中使用Node2Vec進(jìn)行知識(shí)圖譜網(wǎng)絡(luò)特征學(xué)習(xí)，將實(shí)體映射到K維空間，在K維向量空間中，幾何上越接近的實(shí)體相關(guān)性越大，本文算法通過(guò)向量的余弦相似度來(lái)計(jì)算實(shí)體ei和ej之間的相關(guān)性Sim(ei，ej).

(6)

(7)

此外，在知識(shí)圖譜中權(quán)重可以代表用戶對(duì)物品的偏好情況，物品和特征間的相關(guān)性.在文獻(xiàn)[4]推薦算法中，把數(shù)據(jù)集中評(píng)分大于4用以表明用戶User和物品Item間有關(guān)系，設(shè)置邊的權(quán)重為1，沒(méi)有關(guān)系則設(shè)置為0.把邊僅僅簡(jiǎn)單地看作0，1值，因此該算法沒(méi)有考慮不同特征對(duì)推薦結(jié)果的重要性是不同的，也沒(méi)有考慮到用戶的偏好因素影響，也沒(méi)有考慮到人們興趣隨著時(shí)間發(fā)生偏移的情況.

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

3.2 融合長(zhǎng)短期偏好和興趣遷移的混合推薦模型

從長(zhǎng)期來(lái)看，用戶的興趣喜好是相對(duì)穩(wěn)定的，基于用戶大量的歷史數(shù)據(jù)進(jìn)行推薦可以基本反映用戶的一般偏好.但是，從心理學(xué)角度看，用戶偏好受長(zhǎng)期個(gè)人興趣和短期個(gè)人興趣兩方面影響，并且存在一定的相互聯(lián)系.

基于上述原因，本文在基于排序?qū)W習(xí)的Top-N推薦框架上進(jìn)行拓展，用基礎(chǔ)知識(shí)圖譜衡量用戶的長(zhǎng)期偏好.通過(guò)反饋模型和用戶興趣偏移模型構(gòu)建混合知識(shí)圖譜模型，用它衡量物品內(nèi)容的動(dòng)態(tài)變化、用戶興趣的短期波動(dòng)等時(shí)效性因素.

通過(guò)3.1節(jié)中基于基礎(chǔ)知識(shí)圖譜的排序?qū)W習(xí)推薦模型能夠獲得多維特征對(duì)推薦結(jié)果的權(quán)重集合Z={η1，η2，η3，…，η|feature|}，通過(guò)把影響權(quán)重因子集合Z和用戶興趣遷移模型融合，構(gòu)建混合知識(shí)圖譜.

混合知識(shí)圖譜實(shí)體間權(quán)重更新策略如下：

(8)

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

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

(9)

3.3 算法描述

算法步驟如表1所示.

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

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

本文所用的基礎(chǔ)數(shù)據(jù)集是Movielens 1M[12]，包含6040個(gè)用戶，3900個(gè)電影和100多萬(wàn)條匿名評(píng)分組成.由于本文算法驗(yàn)證用戶興趣隨著時(shí)間的動(dòng)態(tài)遷移情況，故將融合DBpedia上下文信息后的數(shù)據(jù)集[13]，按照時(shí)間戳順序劃分為8：2，分別作為訓(xùn)練集和測(cè)試集.

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

本文實(shí)驗(yàn)中所用到的評(píng)估指標(biāo)[14]主要有P@N、MAP，下面分別對(duì)其進(jìn)行說(shuō)明.

P@N本身是Precision@N的簡(jiǎn)稱，指的是對(duì)特定的查詢，考慮位置因素，檢測(cè)前N條結(jié)果的準(zhǔn)確率.例如對(duì)單次搜索的結(jié)果中前100篇，如果有82篇為相關(guān)文檔，則P@100=82/100=0.82.

表1 算法步驟

測(cè)試通常會(huì)使用一個(gè)查詢集合，包含若干條不同的查詢?cè)~，在實(shí)際使用P@N進(jìn)行評(píng)估時(shí)，通常使用所有查詢的P@N數(shù)據(jù)，計(jì)算算術(shù)平均值，用來(lái)評(píng)判該系統(tǒng)的整體搜索結(jié)果質(zhì)量.

(10)

MAP指標(biāo)通常用于衡量系統(tǒng)在所有排序結(jié)果中相關(guān)文檔的排序質(zhì)量.在一個(gè)排序結(jié)果中，AP(平均查準(zhǔn)率)用來(lái)計(jì)算一個(gè)查詢的排序結(jié)果的精度，MAP是對(duì)所有查詢的精度取平均值.其相關(guān)定義如下所示：

(11)

(12)

(13)

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

對(duì)于Top-N的電影推薦結(jié)果，電影排得越靠前，被用戶瀏覽到的可能性就越大，因此在評(píng)測(cè)的過(guò)程中，相關(guān)度越高的電影，在最終的結(jié)果列表中排得位置越靠前，評(píng)測(cè)函數(shù)應(yīng)該給予更高的權(quán)重.

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

實(shí)驗(yàn)硬件，處理器型號(hào)為Intel(R)Xeon(R)CPU E5-2620 v2 @ 2.10GHz，內(nèi)存為80GB；實(shí)驗(yàn)軟件環(huán)境為Python 2.7.12、JDK 1.8.

4.3.1 調(diào)整確定特征參數(shù)

本文所提出算法的參數(shù)參考文獻(xiàn)[6]通過(guò)在該數(shù)據(jù)集上實(shí)驗(yàn)所確定的最佳參數(shù).

通過(guò)表2能夠發(fā)現(xiàn)在該數(shù)據(jù)集上，p，q分別為1，4時(shí)實(shí)驗(yàn)效果最好，并用LambdaMark算法進(jìn)行排序?qū)W習(xí).

表2 排序?qū)W習(xí)算法在不同p，q下結(jié)果

通過(guò)表3能發(fā)現(xiàn)經(jīng)過(guò)排序?qū)W習(xí)訓(xùn)練完決策函數(shù)后，該數(shù)據(jù)集中不同特征對(duì)推薦結(jié)果的比例權(quán)重是不同的.我們通過(guò)決策函數(shù)反饋的集合Z={η1，η2，η3，…，η|features|}和用戶興趣遷移模型構(gòu)建反饋模型.

表3 特征權(quán)重比例

4.3.2 算法比較

最后在該數(shù)據(jù)集上，使用基于Python的開源庫(kù)SurpriseLib實(shí)現(xiàn)對(duì)比實(shí)驗(yàn)，排序算法使用基于Java的開源RankLib庫(kù)實(shí)現(xiàn).對(duì)比結(jié)果如表4.

表4 對(duì)比實(shí)驗(yàn)結(jié)果

通過(guò)表4能夠發(fā)現(xiàn)，本文提出的一種知識(shí)圖譜的排序?qū)W習(xí)個(gè)性化推薦算法在P@N和MAP上均有所提升，算法能夠充分考慮到長(zhǎng)短期偏好和用戶興趣的遷移.

5 結(jié)束語(yǔ)

本文提出了一種知識(shí)圖譜的排序?qū)W習(xí)個(gè)性化推薦算法，不但利用了人和物品間的評(píng)分信息，也包含了物品的上下文信息，并且考慮長(zhǎng)期、短期偏好，因此能夠全面地反映出人和物品之間的關(guān)系.針對(duì)傳統(tǒng)推薦算法中多維特征的參數(shù)難以估計(jì)的痛點(diǎn)，本文算法通過(guò)排序?qū)W習(xí)方法獲取不同特征的權(quán)重比例進(jìn)行反饋，構(gòu)建混合知識(shí)圖譜，通過(guò)基于深度學(xué)習(xí)的網(wǎng)絡(luò)特征表示模型構(gòu)建特征模型，最終與基礎(chǔ)特征模型結(jié)合，構(gòu)建混合模型進(jìn)行推薦.通過(guò)在Movielens數(shù)據(jù)集上驗(yàn)證了本文算法的有效性.

本文算法模型沒(méi)有融合用戶的畫像特征，而這些特征對(duì)推薦系統(tǒng)的意義十分重要.未來(lái)將會(huì)嘗試把用戶畫像特征融合到本算法模型中，挖掘用戶的行為模式，并實(shí)現(xiàn)在線學(xué)習(xí)系統(tǒng).