余敦輝，張蕗怡，張笑笑*，毛 亮

（1.湖北大學(xué)計(jì)算機(jī)與信息工程學(xué)院，武漢 430062；2.湖北省教育信息化工程技術(shù)研究中心（湖北大學(xué)），武漢 430062）

0 引言

隨著互聯(lián)網(wǎng)及大數(shù)據(jù)時(shí)代的發(fā)展，信息呈爆炸式增長(zhǎng)，面對(duì)海量數(shù)據(jù)，用戶如何高效獲取自己需要的信息愈發(fā)困難，因此推薦系統(tǒng)成為各大社交平臺(tái)爭(zhēng)先關(guān)注和應(yīng)用的焦點(diǎn)?，F(xiàn)有的推薦系統(tǒng)大多建立在單一社交平臺(tái)的基礎(chǔ)上，僅僅利用單一平臺(tái)中用戶的興趣、發(fā)布的內(nèi)容和歷史記錄等進(jìn)行用戶推薦，導(dǎo)致對(duì)用戶興趣和行為信息了解不夠全面，推薦結(jié)果單一，容易出現(xiàn)數(shù)據(jù)過(guò)度擬合現(xiàn)象［1］以及用戶冷啟動(dòng)問(wèn)題［2］。例如：用戶在平臺(tái)1 上喜歡關(guān)注體育類(lèi)型的博主，在平臺(tái)2 上喜歡關(guān)注科技類(lèi)型的用戶，并且對(duì)科技類(lèi)型信息的關(guān)注活躍度高于對(duì)體育類(lèi)型的關(guān)注，但是平臺(tái)1 一直推送關(guān)于體育類(lèi)型的信息和博主給用戶，未能發(fā)掘用戶對(duì)科技類(lèi)型信息和博主的興趣，缺乏對(duì)用戶興趣信息的全面了解。

但是，融合多個(gè)社交網(wǎng)絡(luò)中的數(shù)據(jù)，存在用戶信息獲取困難、關(guān)聯(lián)效率較低的問(wèn)題，因此，如何在跨平臺(tái)社交網(wǎng)絡(luò)中進(jìn)行用戶推薦已成為一個(gè)研究熱點(diǎn)。

目前眾多學(xué)者圍繞社交網(wǎng)絡(luò)中的用戶推薦展開(kāi)研究，其中一部分是研究單一平臺(tái)中的用戶推薦：文獻(xiàn)［3］中的協(xié)同過(guò)濾（Collaborative Filtering，CF）是使用較廣泛的推薦技術(shù)，根據(jù)用戶對(duì)物品的評(píng)分信息來(lái)預(yù)測(cè)用戶的偏好；然而，協(xié)同過(guò)濾系統(tǒng)容易受到不公平評(píng)分和稀疏數(shù)據(jù)的影響。文獻(xiàn)［4］中通過(guò)基于用戶相似性的重啟隨機(jī)游走推薦社交網(wǎng)絡(luò)中的事件給用戶，但忽略了跨平臺(tái)用戶之間的關(guān)聯(lián)。文獻(xiàn)［5］中提出了基于用戶行為特征挖掘的個(gè)性化推薦算法，采用顯著數(shù)據(jù)分塊檢測(cè)方法進(jìn)行社交網(wǎng)絡(luò)用戶特征的行為信息融合處理；但是僅融合單一平臺(tái)的用戶信息，推薦的多樣性仍受到限制。單一平臺(tái)用戶信息有限，推薦結(jié)果單一，因此也有很多研究是圍繞跨平臺(tái)和跨社區(qū)的用戶推薦展開(kāi)的：文獻(xiàn)［6］中提出利用源平臺(tái)的數(shù)據(jù)豐富目標(biāo)平臺(tái)的數(shù)據(jù)來(lái)進(jìn)行推薦，以此解決目標(biāo)平臺(tái)的數(shù)據(jù)稀疏問(wèn)題和冷啟動(dòng)問(wèn)題；但是源平臺(tái)中的數(shù)據(jù)往往有限。文獻(xiàn)［7］中提出跨平臺(tái)用戶推薦方法，通過(guò)爬取用戶在不同平臺(tái)的關(guān)聯(lián)賬號(hào)匹配關(guān)系，根據(jù)平臺(tái)的應(yīng)用程序編程接口（Application Programming Interface，API）獲取用戶數(shù)據(jù)；然而無(wú)法獲取沒(méi)有關(guān)聯(lián)賬號(hào)的用戶數(shù)據(jù)，且很多平臺(tái)沒(méi)有提供API，用戶匹配較為困難。文獻(xiàn)［8］中分析了用戶與用戶之間的互動(dòng)，建立了跨社區(qū)的開(kāi)發(fā)者網(wǎng)絡(luò)，利用重啟隨機(jī)游走實(shí)現(xiàn)對(duì)開(kāi)發(fā)者的用戶推薦；但是該方法只考慮了用戶的文本和標(biāo)簽相似性，僅在特定社區(qū)效果較好，擴(kuò)展性較差。文獻(xiàn)［9］中提出了結(jié)合用戶社區(qū)和評(píng)分矩陣聯(lián)合社區(qū)的推薦模型，在面向聯(lián)合社區(qū)的矩陣中結(jié)合用戶社區(qū)進(jìn)行矩陣分解；但該模型僅考慮了用戶靜態(tài)興趣偏好與社交關(guān)系，忽略了用戶的興趣和關(guān)系的動(dòng)態(tài)變化。

綜上，在推薦系統(tǒng)的研究中，面臨推薦單一、跨平臺(tái)用戶匹配效率低的問(wèn)題，因此，本文提出基于知識(shí)圖譜和重啟隨機(jī)游走的跨平臺(tái)用戶推薦方法（User Recommendation method of Cross-Platform based on Knowledge graph and Restart random walk，URCP-KR），該方法包括基于知識(shí)圖譜的跨平臺(tái)用戶關(guān)系補(bǔ)全算法（Cross-Platform user Relationship Completion algorithm based on Knowledge Graph，RCCP-KG）和基于重啟隨機(jī)游走的用戶推薦算法（User Recommendation algorithm based on Restart Random Walk，UR-RRW）。首先，將目標(biāo)平臺(tái)圖譜和輔助平臺(tái)圖譜分割匹配得到相似子圖，利用多層循環(huán)神經(jīng)網(wǎng)絡(luò)（Recurrent Neural Network，RNN）得到候選用戶實(shí)體，通過(guò)用戶篩選匹配兩個(gè)不同平臺(tái)中可能相同的用戶；然后，通過(guò)關(guān)系補(bǔ)全將輔助平臺(tái)中的用戶信息補(bǔ)全到目標(biāo)平臺(tái)圖譜，完善用戶之間的關(guān)系；最后，利用重啟隨機(jī)游走算法，獲得具有相似興趣的用戶推薦列表，從而解決跨平臺(tái)用戶匹配、推薦單一的問(wèn)題，提高用戶推薦的準(zhǔn)確率及多樣性。

本文的主要工作如下：

1）提出了一種新的跨平臺(tái)數(shù)據(jù)融合算法，基于知識(shí)圖譜的跨平臺(tái)用戶關(guān)系補(bǔ)全算法RCCP-KG，把輔助平臺(tái)中的相同用戶信息補(bǔ)全到目標(biāo)平臺(tái)圖譜中，實(shí)現(xiàn)跨平臺(tái)數(shù)據(jù)融合，從而更加全面地刻畫(huà)用戶行為，同時(shí)發(fā)掘不同平臺(tái)間的潛在用戶關(guān)系，更加準(zhǔn)確地進(jìn)行相似用戶推薦。

2）提出了一種基于重啟隨機(jī)游走的用戶推薦算法URRRW，在傳統(tǒng)隨機(jī)游走的基礎(chǔ)上融入用戶興趣信息，提升了推薦的多樣性。

1 整體方案

1.1 相關(guān)定義

定義1 社交網(wǎng)絡(luò)知識(shí)圖譜（Social Network Knowledge Graph，SN-KG）。本文通過(guò)社交網(wǎng)絡(luò)有向圖構(gòu)建SN-KG，將用戶作為知識(shí)圖譜中的實(shí)體，用戶間的關(guān)注關(guān)系作為關(guān)系，用戶屬性作為實(shí)體屬性，用戶屬性值作為實(shí)體屬性值。

定義2 目標(biāo)平臺(tái)圖譜G=(V，E)，其 中：V={v1，v2，…，vi}是目標(biāo)平臺(tái)圖譜中用戶節(jié)點(diǎn)的集合，vi表示用戶節(jié)點(diǎn)向量；E={e1，2，e2，3，…，ei，j}是目標(biāo)平臺(tái)圖譜中用戶節(jié)點(diǎn)之間邊的集合，ei，j表示用戶節(jié)點(diǎn)vi和vj之間的邊。

定義4 實(shí)體關(guān)系三元組表示為（頭實(shí)體，關(guān)系，尾實(shí)體）(h，r，t)，邊r的類(lèi)型統(tǒng)一為“關(guān)注”關(guān)系，即用戶h關(guān)注用戶t。若干三元組的集合H={(h，r，t)|h?V，r?E，t?V}構(gòu)成一個(gè)知識(shí)圖譜，如圖1 所示，社交網(wǎng)絡(luò)知識(shí)圖譜可以表示用戶之間的關(guān)注關(guān)系。實(shí)體屬性三元組表示為（實(shí)體，屬性，屬性值）(vi，ai，Va)，其中用戶屬性集合為Ai={a1，a2，…，ai}。

圖1 社交網(wǎng)絡(luò)知識(shí)圖譜示意圖Fig.1 Schematic diagram of social network knowledge graph

定義5 目標(biāo)平臺(tái)圖譜子圖集合SG={g1，g2，…，gi}，是通過(guò)對(duì)目標(biāo)平臺(tái)圖譜進(jìn)行分割得到的子圖集合，其中g(shù)i表示目標(biāo)平臺(tái)圖譜的子圖。

定義7 用戶活躍時(shí)間關(guān)鍵詞序列(vi，Kn)，其中用戶vi在活躍時(shí)間t內(nèi)的發(fā)表的博文內(nèi)容關(guān)鍵詞kn按照時(shí)間先后順序構(gòu)成Kn={k1，k2，…，kn}。

1.2 整體框架

本文設(shè)計(jì)和實(shí)現(xiàn)了基于知識(shí)圖譜和重啟隨機(jī)游走的跨平臺(tái)用戶推薦方法，其中包括RCCP-KG算法和UR-RRW 兩個(gè)算法。具體實(shí)現(xiàn)過(guò)程如下：

1）利用社區(qū)檢測(cè)實(shí)現(xiàn)目標(biāo)平臺(tái)圖譜和輔助平臺(tái)圖譜的圖分割和子圖匹配，得到相似子圖；

2）通過(guò)輸入用戶活躍時(shí)間關(guān)鍵詞序列訓(xùn)練RNN 模型得到候選用戶實(shí)體集合；

3）通過(guò)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征相似度和用戶畫(huà)像相似度對(duì)用戶實(shí)體進(jìn)行篩選，得到跨平臺(tái)相同用戶，實(shí)現(xiàn)實(shí)體鏈接；

4）將相同用戶在輔助平臺(tái)圖譜的關(guān)系補(bǔ)全到目標(biāo)平臺(tái)圖譜；

5）通過(guò)重啟隨機(jī)游走在目標(biāo)平臺(tái)圖譜的社區(qū)中找到興趣相似程度高的用戶，形成用戶推薦列表，實(shí)現(xiàn)跨平臺(tái)用戶推薦。

方法整體框架如圖2所示。

圖2 本文方法整體框架Fig.2 Overall framework of the proposed method

2 基于知識(shí)圖譜的跨平臺(tái)用戶關(guān)系補(bǔ)全算法

用戶在不同平臺(tái)所關(guān)注的內(nèi)容和興趣點(diǎn)可能不同，但同一用戶的個(gè)人信息、好友以及影響力等具有極大的相似性。因此，識(shí)別兩個(gè)平臺(tái)中的相同用戶問(wèn)題，轉(zhuǎn)換為匹配兩個(gè)知識(shí)圖譜中相同用戶節(jié)點(diǎn)的問(wèn)題。本章提出RCCP-KG 算法。首先，利用社區(qū)檢測(cè)算法將目標(biāo)平臺(tái)圖譜和輔助平臺(tái)圖譜分割為不同的子圖，匹配跨平臺(tái)中相似的子圖；然后在相似子圖中利用多層循環(huán)神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)候選實(shí)體，再通過(guò)圖譜的拓?fù)浣Y(jié)構(gòu)、用戶畫(huà)像相似度篩選出相似度最高的用戶節(jié)點(diǎn)對(duì)；最后將相同用戶在輔助平臺(tái)圖譜中的關(guān)系補(bǔ)全到目標(biāo)平臺(tái)圖譜，實(shí)現(xiàn)跨平臺(tái)間的用戶關(guān)系補(bǔ)全。

2.1 基于社區(qū)檢測(cè)的圖譜分割及子圖匹配

由于社交網(wǎng)絡(luò)圖譜用戶數(shù)量龐大，直接匹配跨平臺(tái)間的相似用戶工作量較大，且誤差較高，因此，本文首先將圖譜分割為相似子圖，然后在子圖中匹配相似用戶。

Louvain 是一種基于模塊度的社區(qū)發(fā)現(xiàn)算法［10］，通過(guò)模塊度來(lái)衡量一個(gè)社區(qū)的緊密程度。關(guān)聯(lián)關(guān)注緊密的用戶可以分割在同一子圖中，能夠更好地體現(xiàn)用戶群體的特性，便于子圖相似性匹配。

首先使用Louvain 算法將目標(biāo)平臺(tái)圖譜和輔助平臺(tái)圖譜分割為不同的子圖集合SG={g1，g2，…，gi}和SG′=；然后，利用Pearson 矩陣相似度計(jì)算方法［11］匹配目標(biāo)平臺(tái)圖譜子圖集合和輔助平臺(tái)圖譜子圖集合中相似子圖對(duì)；接下來(lái)在相似子圖對(duì)中匹配相同節(jié)點(diǎn)對(duì)。

2.2 基于多層循環(huán)神經(jīng)網(wǎng)絡(luò)的用戶實(shí)體預(yù)測(cè)

首先，利用目標(biāo)平臺(tái)圖譜中的用戶實(shí)體和博文關(guān)鍵詞序列訓(xùn)練多層循環(huán)神經(jīng)網(wǎng)絡(luò)；然后，將輔助平臺(tái)圖譜中的實(shí)體輸入多層循環(huán)神經(jīng)網(wǎng)絡(luò)，經(jīng)過(guò)用戶相似度計(jì)算，得到在輔助平臺(tái)圖譜中與輸入實(shí)體匹配的多個(gè)候選用戶實(shí)體；最后，利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征相似度和用戶畫(huà)像相似度對(duì)候選用戶實(shí)體進(jìn)行篩選，選出相似度最高的一個(gè)用戶實(shí)體，與輸入實(shí)體vi組成相似用戶節(jié)點(diǎn)對(duì)vi=。

2.2.1 基于多層循環(huán)神經(jīng)網(wǎng)絡(luò)的候選用戶實(shí)體預(yù)測(cè)

用戶活躍在不同平臺(tái)的時(shí)間可能相同也可能是錯(cuò)開(kāi)的，但是發(fā)布的內(nèi)容可能是相同的。目前很多社交網(wǎng)絡(luò)平臺(tái)允許用戶分享相同的內(nèi)容到其他的社交平臺(tái)中，如知乎允許用戶將發(fā)布的內(nèi)容同時(shí)分享到微博。例如，18：00，A 用戶在知乎上發(fā)布了一條動(dòng)態(tài)，同時(shí)將此動(dòng)態(tài)分享到微博。因此，用戶在不同平臺(tái)發(fā)布內(nèi)容和時(shí)間是判斷是否為同一用戶的重要內(nèi)容。并且，用戶活躍時(shí)間關(guān)鍵詞序列可以近似地看作是一個(gè)由詞組成的句子。

RNN 是一種神經(jīng)序列模型，已經(jīng)在語(yǔ)言建模和機(jī)器翻譯等許多自然語(yǔ)言處理任務(wù)上取得了優(yōu)良的表現(xiàn)。知識(shí)圖譜中的三元組（實(shí)體，關(guān)系，實(shí)體）由句子提取，本質(zhì)上是具有序列性的。Guo等［12］在RNN的基礎(chǔ)上提出了一種用于知識(shí)圖譜補(bǔ)全的深度序列模型（Deep Sequential model for Knowledge Graph completion，DSKG），此模型具有序列特性，給定三元組中的頭實(shí)體和關(guān)系，能夠預(yù)測(cè)尾實(shí)體。DSKG 使用不同的RNN 單元處理實(shí)體v和關(guān)系r。根據(jù)模型DSKG，本文選取用戶的博文關(guān)鍵詞取代關(guān)系進(jìn)行訓(xùn)練。

因此，本文設(shè)計(jì)了一種基于多層RNN 的實(shí)體預(yù)測(cè)模型（Entity Prediction model based on Multilayer RNN，EPMRNN），如圖3 所示，輸入層為用戶vi活躍時(shí)間關(guān)鍵詞序列(vi，Kn)，然后通過(guò)多層RNN 訓(xùn)練得到用戶vi隱藏狀態(tài)hi，中間層輸入是輔助平臺(tái)圖譜用戶，輸出層是目標(biāo)平臺(tái)用戶與輔助平臺(tái)用戶的相似度概率。

圖3 基于多層RNN的實(shí)體預(yù)測(cè)模型Fig.3 Entity prediction model based on multi-layer RNN

如圖4 所示，給出了兩層RNN，其中c1、c2、c3、c4全都是各不相同的RNN 單元。使用c1、c2處理實(shí)體vi，使用c3、c4處理關(guān)鍵詞ki。

圖4 兩層RNN示意圖Fig.4 Schematic diagram of two-layer RNN

c表示一個(gè)RNN 單元，它將之前的隱藏狀態(tài)和當(dāng)前元素作為輸入，預(yù)測(cè)下一個(gè)隱藏狀態(tài)，計(jì)算如下：

得到隱藏狀態(tài)之后，預(yù)測(cè)用戶實(shí)體的隱藏狀態(tài)hv與輔助平臺(tái)用戶實(shí)體概率：

最后，通過(guò)最小化真實(shí)值和預(yù)測(cè)值間的交叉熵?fù)p失來(lái)訓(xùn)練模型。

其中：qi為預(yù)測(cè)概率分布，pi為真實(shí)的概率分布。

與用戶vi相似度概率值大于等于閾值δ的輔助平臺(tái)用戶構(gòu)成候選用戶實(shí)體集Cv=，進(jìn)入下一步篩選。

2.2.2 基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征相似度的用戶實(shí)體篩選

根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征相似度將用戶vi與其候選用戶實(shí)體集合Cv=中的用戶進(jìn)行篩選。目標(biāo)平臺(tái)圖譜節(jié)點(diǎn)vi的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征集合為由度中心性［13］DC(i)和聚類(lèi)系數(shù)［14］CLi構(gòu)成，計(jì)算如下：

使用余弦相似度計(jì)算目標(biāo)平臺(tái)圖譜網(wǎng)絡(luò)子圖節(jié)點(diǎn)vi和輔助平臺(tái)圖譜中的候選節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)特征相似度：

在Cv=中，篩選出拓?fù)浣Y(jié)構(gòu)特征相似度大于等于拓?fù)浣Y(jié)構(gòu)特征相似度閾值λ的用戶，組成新的候選用戶集合，進(jìn)入下一步基于用戶畫(huà)像相似度的用戶實(shí)體篩選。

2.2.3 基于用戶畫(huà)像相似度的用戶實(shí)體篩選

用戶在社交網(wǎng)絡(luò)中的公開(kāi)信息可以用于描述一個(gè)人的特征。使用用戶畫(huà)像可以快速、有效地描述社交網(wǎng)絡(luò)中用戶的個(gè)人信息及特征，如性別、年齡、職業(yè)、所在地、畢業(yè)院校等客觀信息。聯(lián)系電話和電子郵箱可以標(biāo)識(shí)唯一的用戶，因此，如果不同平臺(tái)用戶節(jié)點(diǎn)的聯(lián)系電話或者電子郵箱相同，則認(rèn)為是同一用戶［15］。

首先，使用Word2vec［16］方法把用戶實(shí)體的畫(huà)像和屬性Ai信息轉(zhuǎn)化為畫(huà)像特征向量F，進(jìn)而通過(guò)用戶畫(huà)像的相似性度量用戶節(jié)點(diǎn)的相似性。計(jì)算目標(biāo)平臺(tái)圖譜用戶與候選用戶集合中用戶的用戶畫(huà)像相似度SimF(vi，)：

其中：F目標(biāo)平臺(tái)圖譜節(jié)點(diǎn)的用戶畫(huà)像特征向量，F(xiàn)′為候選用戶集合中的用戶畫(huà)像特征向量。

2.3 基于輔助平臺(tái)圖譜的目標(biāo)平臺(tái)圖譜關(guān)系補(bǔ)全

首先，通過(guò)廣度優(yōu)先遍歷［17］，獲取目標(biāo)平臺(tái)圖譜用戶節(jié)點(diǎn)vi所有的關(guān)系集合Ri={ri1，ri2，…，rij}，其中關(guān)系為一階關(guān)系，即記錄可到達(dá)的下一個(gè)鄰接用戶節(jié)點(diǎn)的路徑，rij=vi→vj。同理，在輔助平臺(tái)圖譜中獲取相似子圖中用戶節(jié)點(diǎn)vi的所有路徑集合。然后，根據(jù)上一節(jié)識(shí)別出的所有相同用戶節(jié)點(diǎn)隊(duì)，將輔助平臺(tái)圖譜路徑中的相同用戶替換為目標(biāo)平臺(tái)圖譜的用戶，去除相同的關(guān)系，即得到用戶vi需要補(bǔ)全的關(guān)系集合Ri。

目前各高校圖書(shū)館還不具備專(zhuān)業(yè)的布展設(shè)施，往往根據(jù)臨時(shí)的展覽活動(dòng)需求及展覽規(guī)模，在館內(nèi)現(xiàn)有空間內(nèi)因地制宜尋找相應(yīng)的展覽地點(diǎn)，并根據(jù)需要、展品珍貴程度、財(cái)力大小選擇租用陳列柜。但這在展覽的呈現(xiàn)效果及專(zhuān)業(yè)度上都顯得不足，展柜等配置不能與展品良好地匹配，無(wú)法營(yíng)造較為專(zhuān)業(yè)化的觀展體驗(yàn)。

同理，獲取子圖中所有節(jié)點(diǎn)需要補(bǔ)全的關(guān)系集合。

當(dāng)目標(biāo)平臺(tái)圖譜中缺少輔助平臺(tái)圖譜的相似用戶節(jié)點(diǎn)時(shí)，建立對(duì)應(yīng)的虛擬節(jié)點(diǎn)與之替換，當(dāng)新的節(jié)點(diǎn)出現(xiàn)在目標(biāo)平臺(tái)圖譜時(shí)，可以與之比較，建立相應(yīng)關(guān)系。

最后，按照關(guān)系集合中的關(guān)系，補(bǔ)全目標(biāo)平臺(tái)圖譜中節(jié)點(diǎn)之間的關(guān)系。

2.4 算法執(zhí)行過(guò)程

算法1 RCCP-KG算法。

輸入 目標(biāo)平臺(tái)圖譜G=(V，E)，輔助平臺(tái)圖譜G′=(V′，E′)，用戶博文的時(shí)間關(guān)鍵詞序列(vi，Kn)；

輸出 關(guān)系補(bǔ)全后的目標(biāo)平臺(tái)圖譜G=(V，E)。

3 基于重啟隨機(jī)游走的用戶推薦算法

傳統(tǒng)的隨機(jī)游走算法利用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，只考慮圖的出度和入度，忽略了節(jié)點(diǎn)本身的特性。因此本文提出了基于重啟隨機(jī)游走的用戶推薦算法UR-RRW，在補(bǔ)全后的目標(biāo)平臺(tái)圖譜中，融合用戶興趣和用戶間關(guān)系，采用重啟隨機(jī)游走完成用戶推薦。社交網(wǎng)絡(luò)知識(shí)圖譜中的部分重啟隨機(jī)游走，如圖5所示。

圖5 重啟隨機(jī)游走示意圖Fig.5 Schematic diagram of restart random walk

在補(bǔ)全后的目標(biāo)平臺(tái)圖譜中，首先，確保用戶節(jié)點(diǎn)間有較高的緊密連接，使用社區(qū)檢測(cè)Louvain算法再次將用戶實(shí)體進(jìn)行社區(qū)劃分，得到社區(qū)集合S={s1，s2，…，si}，然后在每個(gè)社區(qū)中建立用戶興趣相似度矩陣，通過(guò)隨機(jī)游走來(lái)尋找相似用戶，計(jì)算用戶間游走的平穩(wěn)概率值，將其降序排列得到用戶推薦列表。

3.1 用戶興趣相似度矩陣建立

首先，通過(guò)社區(qū)檢測(cè)將用戶劃分成不同社區(qū)。在目標(biāo)平臺(tái)圖譜，對(duì)于新添加的關(guān)系，給予與輔助平臺(tái)圖譜中相同的權(quán)重值。在原有社區(qū)的基礎(chǔ)上，再次利用社區(qū)檢測(cè)Louvain 算法，重新對(duì)社區(qū)內(nèi)的用戶節(jié)點(diǎn)進(jìn)行模塊度計(jì)算［18］。根據(jù)模塊度變化值，增加或刪除社區(qū)內(nèi)的節(jié)點(diǎn)，最終確定目標(biāo)平臺(tái)圖譜中的社區(qū)劃分，得到新的社區(qū)集合S={s1，s2，…，si}。

然后，定義用戶的興趣相似度矩陣。用戶間興趣相似度需滿足以下條件：

1）同一社區(qū)的用戶間共同關(guān)注的用戶的類(lèi)型種類(lèi)數(shù)li越多，則相似度越高；

2）同一社區(qū)的用戶間對(duì)單一類(lèi)型用戶的關(guān)注次數(shù)Ni越多，則相似度越高。

為滿足以上條件，定義矩陣M∈Rn×n，矩陣元素mij為vi∈V與vj∈V之間的相似度評(píng)分，如用戶間無(wú)共同關(guān)注則mij=0，其形式如式（11）所示：

其中：lij為用戶vi與用戶vj共同關(guān)注用戶的類(lèi)型權(quán)重，li和lj分別是用戶vi與用戶vj關(guān)注的用戶類(lèi)型種類(lèi)數(shù)；zij為用戶vi與用戶vj共同關(guān)注用戶的次數(shù)權(quán)重。

對(duì)M進(jìn)行歸一化處理得到用戶興趣相似度矩陣M′。

3.2 基于重啟隨機(jī)游走的用戶推薦

本文采用基于用戶興趣相似度的重啟隨機(jī)游走算法，將得到的用戶興趣相似度矩陣M作為概率轉(zhuǎn)移矩陣并輸入到重啟隨機(jī)游走模型中，通過(guò)歸一化的用戶興趣相似度矩陣計(jì)算得到平穩(wěn)概率值［4］。

其中：yLast為經(jīng)過(guò)n步游走后所得到的平穩(wěn)概率值；θ為下一步游走到其最近鄰節(jié)點(diǎn)的概率，θ為可調(diào)參數(shù)，通過(guò)實(shí)驗(yàn)驗(yàn)證θ取0.1；y0為用戶的列向量，是向量y的初始向量，向量y中的每一項(xiàng)值代表著從用戶vi經(jīng)過(guò)n步游走后到達(dá)各個(gè)節(jié)點(diǎn)的概率值。

最后將平穩(wěn)概率值yLast進(jìn)行降序排序，形成用戶推薦列表RL={u1，u2，…，uj}，將 用戶列表中未關(guān)注的用戶進(jìn)行推薦。

3.3 算法執(zhí)行過(guò)程

算法2 UR-RRW。

輸入 目標(biāo)平臺(tái)圖譜G=(V，E)；

輸出 用戶推薦列表RL={u1，u2，…，uj}。

4 實(shí)驗(yàn)與分析

本實(shí)驗(yàn)選取經(jīng)典的協(xié)同過(guò)濾（CF）算法［3］、基于跨平臺(tái)的在線社交網(wǎng)絡(luò)用戶推薦算法（User Recommendation algorithm based on Cross-Platform online social network，URCP）［7］，以及使用重啟隨機(jī)游走的基于多開(kāi)發(fā)者社區(qū)的用戶推薦算法（User Recommendation algorithm based on Multi-developer Community，UR-MC）［8］作為對(duì)比方法與本文提出的URCP-KR方法相比較。當(dāng)改變用戶數(shù)量、用戶平均關(guān)聯(lián)關(guān)系數(shù)量以及用戶平均博文數(shù)量時(shí)，本文選取精確率pre（precision）、召回率rec（recall）、F1 值F1、覆蓋率cov（coverage）作為評(píng)價(jià)指標(biāo)，具體指標(biāo)介紹及公式如下：

精確率pre為正確推薦用戶數(shù)TP與推薦列表用戶總數(shù)|RL|的比值：

召回率rec為正確推薦用戶數(shù)TP與目標(biāo)平臺(tái)中的好友總數(shù)FN的比值：

F1值均勻地反映了推薦效果：

覆蓋率cov為推薦用戶總量|RL|與總用戶數(shù)量|V|的比值，反映推薦的多樣性：

4.1 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)在具有2.8 GHz Inter Core i7 處理器和16 GB 內(nèi)存的機(jī)器上運(yùn)行，操作系統(tǒng)為Windows 10，編程語(yǔ)言為Python。

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

本實(shí)驗(yàn)選取微博作為目標(biāo)平臺(tái)，選取知乎作為輔助平臺(tái)圖譜。從微博和知乎采集了用戶信息及其發(fā)布內(nèi)容，把從已知的實(shí)名認(rèn)證的用戶作為起始節(jié)點(diǎn)爬取用戶相關(guān)信息。通過(guò)深度優(yōu)先搜索的方法采集節(jié)點(diǎn)的鄰居信息，根據(jù)小世界理論［19］，本文將深度優(yōu)先搜索的深度設(shè)置為4。數(shù)據(jù)集包含用戶的21 萬(wàn)條微博數(shù)據(jù)，19 萬(wàn)條知乎數(shù)據(jù)，共36 萬(wàn)對(duì)用戶間關(guān)注關(guān)系數(shù)據(jù)。

4.3 參數(shù)設(shè)置

本文中用戶相似度概率閾值β、拓?fù)浣Y(jié)構(gòu)特征相似度閾值λ和重啟隨機(jī)游走可調(diào)參數(shù)θ通過(guò)在測(cè)試集數(shù)據(jù)上實(shí)驗(yàn)，根據(jù)用戶推薦F1 值的變化確定。由圖6 可知，當(dāng)β=0.4，λ=0.6，θ=0.1時(shí)，用戶推薦的F1值最優(yōu)。

圖6 F1值隨λ、β和θ的變化結(jié)果Fig.6 F1 changing with λ，β and θ

表1 實(shí)驗(yàn)參數(shù)表Tab.1 Experimental parameter table

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

將數(shù)據(jù)分為訓(xùn)練集和測(cè)試集，其中訓(xùn)練集用于訓(xùn)練模型，測(cè)試集用于衡量模型的性能。使用十折交叉驗(yàn)證，訓(xùn)練集采用總數(shù)據(jù)集的90%數(shù)據(jù)量，測(cè)試集使用10%。

由圖7 可知，在用戶數(shù) |V| 較小時(shí)，本文提出的URCP-KR方法在精確率、召回率、F1 值和覆蓋率都要優(yōu)于對(duì)比方法；隨著用戶數(shù)量的不斷增加，由于用戶數(shù)量增長(zhǎng)幅度比用戶推薦數(shù)量增加幅度大，因此四種方法精確率、召回率和F1 值都有所下降，但是URCP-KR 方法下降趨勢(shì)緩慢；在覆蓋率方面，URCP-KR 方法先增后減，當(dāng)用戶數(shù)量為60 000 時(shí)，覆蓋率最高為88.42%，推薦多樣性優(yōu)于對(duì)比方法。

圖7 用戶數(shù)|V|變化時(shí)各方法的度量指標(biāo)對(duì)比Fig.7 Comparison of metrics of each method when changing user numbers|V|

由圖8 可知，隨著用戶平均關(guān)聯(lián)關(guān)系數(shù)rn不斷增加，URCP-KR 方法的精確率先增加后減小，當(dāng)用戶平均關(guān)聯(lián)關(guān)系數(shù)量為40 時(shí)精確率達(dá)到最大，為95.31%；覆蓋率方面逐步增加。因?yàn)閁RCP-KR 方法將不同平臺(tái)的用戶關(guān)系進(jìn)行融合，豐富了目標(biāo)平臺(tái)的用戶關(guān)系。CF 算法和UR-MC 算法則隨用戶平均關(guān)聯(lián)關(guān)系數(shù)量增加到一定程度而受到用戶評(píng)分?jǐn)?shù)量和用戶標(biāo)簽數(shù)量的限制。

圖8 rn變化時(shí)各方法的度量指標(biāo)對(duì)比Fig.8 Comparison of metrics of each method when changing average number of user relationships rn

由圖9 可知，隨著用戶平均博文數(shù)pb增加，URCP-KR 方法的精確率和覆蓋率逐步增加并趨于平穩(wěn)，因?yàn)橛脩舨┪臄?shù)據(jù)越多，實(shí)體鏈接效率越高。同樣，URCP 算法獲取到的用戶興趣愛(ài)好主題數(shù)量增加，推薦精確率和覆蓋率有較大的提高；但由于URCP算法通過(guò)API獲取相同用戶數(shù)量的有限性，因此推薦效果受限。

圖9 pb變化時(shí)各方法的度量指標(biāo)對(duì)比Fig.9 Comparison of metrics of each method when changing average number of user’s blogs pb

5 結(jié)語(yǔ)

在跨平臺(tái)推薦系統(tǒng)環(huán)境下，本文提出了基于知識(shí)圖譜和重啟隨機(jī)游走的跨平臺(tái)用戶推薦方法。首先，提出了基于知識(shí)圖譜的跨平臺(tái)用戶關(guān)系補(bǔ)全算法RCCP-KG，利用改進(jìn)的多層RNN 預(yù)測(cè)出候選用戶實(shí)體，篩選出不同平臺(tái)中可能相同的用戶；然后，通過(guò)關(guān)系補(bǔ)全將輔助平臺(tái)圖譜中的用戶信息補(bǔ)全到目標(biāo)平臺(tái)，完善用戶之間的關(guān)系；最后，提出了基于重啟隨機(jī)游走的用戶推薦算法UR-RRW，利用重啟隨機(jī)游走算法計(jì)算同一社區(qū)中用戶的相似性，形成用戶推薦列表，從而解決跨平臺(tái)用戶推薦問(wèn)題，提高用戶推薦的準(zhǔn)確率及多樣性。未來(lái)將對(duì)實(shí)體及關(guān)系消歧進(jìn)行研究，增強(qiáng)跨平臺(tái)間相同用戶的匹配，進(jìn)一步提高跨平臺(tái)用戶間的推薦準(zhǔn)確性和多樣性。