基于LBSN中錨鏈接方法的鏈路預(yù)測(cè)模型

黃壽孟，夏王霞

(三亞學(xué)院 信息與智能工程學(xué)院，海南 三亞 572022)

0 引言

大數(shù)據(jù)環(huán)境下的社交網(wǎng)絡(luò)，數(shù)據(jù)具有多維性和關(guān)聯(lián)性，那么如何充分利用好這些特性呢？這就需要構(gòu)建數(shù)學(xué)模型來挖掘出這些數(shù)據(jù)之間的潛在關(guān)系信息，比如基于地址位置的社交網(wǎng)絡(luò)(Location-based Social Network，簡稱LBSN)，一般包含兩種數(shù)據(jù)[1]67：一種是網(wǎng)絡(luò)中用戶本身的數(shù)據(jù)，另一種是用戶間存在的關(guān)系數(shù)據(jù)。從LBSN中挖掘出用戶間的時(shí)空信息進(jìn)行各種應(yīng)用活動(dòng)[2]79，比如好友推薦[3]7、興趣推薦[4]、軌跡恢復(fù)[5]108、行為預(yù)測(cè)[6]120等應(yīng)用場(chǎng)景。其實(shí)在社交網(wǎng)絡(luò)分析中，鏈路預(yù)測(cè)一直是信息推薦系統(tǒng)的研究熱點(diǎn)，它是從網(wǎng)絡(luò)中已知節(jié)點(diǎn)信息找出可能存在節(jié)點(diǎn)鏈接的信息。就目前社交網(wǎng)絡(luò)而言，在鏈路預(yù)測(cè)領(lǐng)域，可根據(jù)用戶簽到記錄和社交網(wǎng)絡(luò)兩種數(shù)據(jù)來實(shí)現(xiàn)信息推薦。Li Zhepeng等人[1]1938提出在LBSN中這兩種異構(gòu)數(shù)據(jù)融合的預(yù)測(cè)方法，利用網(wǎng)絡(luò)表示學(xué)習(xí)和矩陣分解數(shù)據(jù)節(jié)點(diǎn)信息，通過拼接融合方案完成預(yù)測(cè)任務(wù)。Hu Wei等人[2]206運(yùn)用概率學(xué)方法將網(wǎng)絡(luò)用戶時(shí)間行為與社會(huì)理論融合構(gòu)建鏈路模型。Li Jichao等人[7]10利用網(wǎng)絡(luò)結(jié)構(gòu)與節(jié)點(diǎn)形成時(shí)間的關(guān)聯(lián)信息構(gòu)建預(yù)測(cè)方法，而Liang Wenxin等人[8]1111量化用戶節(jié)點(diǎn)社交圖屬性、用戶檔案信息和移動(dòng)特征之間的關(guān)聯(lián)來建模預(yù)測(cè)好友關(guān)系，并綜合用戶話題特征和節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)構(gòu)建聯(lián)合預(yù)測(cè)模型。Ling Jiang等人[9]211研究了網(wǎng)絡(luò)交叉視圖，通過學(xué)習(xí)鏈路表示與用戶屬性表示來完成鏈路預(yù)測(cè)任務(wù)。從不同角度完成復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)任務(wù)的還有異構(gòu)數(shù)據(jù)源進(jìn)行混合預(yù)測(cè)[10]305、基于聚類分析[11]144、從信息學(xué)分析角度[12]、基于節(jié)點(diǎn)局部相似性[13]、基于資源傳輸匹配度[14]、基于互信息[15]57等。為了進(jìn)一步提升鏈路預(yù)測(cè)性能和準(zhǔn)確度，本研究提出一種錨鏈接方案取代文獻(xiàn)[1]中的數(shù)據(jù)拼接融合方案[1]1938，更深入挖掘LBSN中節(jié)點(diǎn)鏈接信息及其關(guān)聯(lián)，錨鏈接節(jié)點(diǎn)就是兩種不同數(shù)據(jù)的公共節(jié)點(diǎn)，它們的映射關(guān)系由神經(jīng)網(wǎng)絡(luò)算法完成。

1 相關(guān)工作

1.1 網(wǎng)絡(luò)表示學(xué)習(xí)

提取網(wǎng)絡(luò)節(jié)點(diǎn)的信息方法有很多，目前比較流行的是網(wǎng)絡(luò)表示學(xué)習(xí)方法[16]，它是運(yùn)用深度學(xué)習(xí)技術(shù)對(duì)網(wǎng)絡(luò)空間量化降維過程，從而提取出網(wǎng)絡(luò)中各節(jié)點(diǎn)的特征向量。如圖1所示，Deep Walk[7]12實(shí)現(xiàn)網(wǎng)絡(luò)表示學(xué)習(xí)獲取用戶節(jié)點(diǎn)向量化的大致流程。

圖1 網(wǎng)絡(luò)表示學(xué)習(xí)流程

目前在LBSN的好友推薦領(lǐng)域，利用網(wǎng)絡(luò)表示學(xué)習(xí)可以完成低維空間向量表示、節(jié)點(diǎn)分類與聚類等任務(wù)，通過挖掘社交用戶網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的潛在關(guān)系規(guī)律及特征，對(duì)LBSN網(wǎng)絡(luò)關(guān)系進(jìn)行建模，得到以向量表示出LBSN社交關(guān)系拓?fù)浣Y(jié)構(gòu)中的各用戶節(jié)點(diǎn)和各節(jié)點(diǎn)之間的用戶關(guān)聯(lián)信息。

1.2 矩陣分解

矩陣分解其實(shí)是一種矩陣的變換方法，為了完成矩陣的降維任務(wù)，將原矩陣拆分為多個(gè)相關(guān)聯(lián)的矩陣[17]。推薦系統(tǒng)中常常使用矩陣分解來過濾某些數(shù)據(jù)從而完成推薦任務(wù)[18]。比如用戶給電影打分，假設(shè)從觀影購票系統(tǒng)獲取所有數(shù)據(jù)，構(gòu)建出用戶評(píng)分表，如圖2所示，行值為用戶ID，列值為電影ID，符號(hào)？表示缺失評(píng)分值，即某用戶對(duì)某電影未觀看不評(píng)分的現(xiàn)象?，F(xiàn)在需要預(yù)測(cè)出這些缺失的評(píng)分值(假設(shè)分值范圍為1～5)，首先將評(píng)分表矩陣分解為用戶矩陣與電影矩陣的乘積關(guān)系，希望相乘結(jié)果與原評(píng)分矩陣的分值盡可能接近(損失函數(shù)的條件)，經(jīng)過不斷的迭代多輪訓(xùn)練優(yōu)化后得到收斂模型(即損失函數(shù))，從而將相乘得到的新矩陣代替原矩陣中缺失的值，即預(yù)測(cè)出該用戶對(duì)未觀看的電影興趣值。

圖2 矩陣分解觀影評(píng)分圖

1.3 相關(guān)的預(yù)測(cè)模型

Walk2friends[15]57模型僅提取用戶移動(dòng)特征；DeepWalk[7]15模型通過游走方式提取用戶節(jié)點(diǎn)序列；LINE[9]211模型采用節(jié)點(diǎn)共現(xiàn)與條件概率建模；GraRep[2]81模型構(gòu)造轉(zhuǎn)移矩陣提取節(jié)點(diǎn)相似性；Node2vec[11]144利用網(wǎng)絡(luò)局部與全局屬性提取節(jié)點(diǎn)的領(lǐng)域；Struc2vec[8]1111模型捕獲節(jié)點(diǎn)結(jié)構(gòu)向量化建模。本研究采用節(jié)點(diǎn)信息(用戶簽到記錄)和節(jié)點(diǎn)結(jié)構(gòu)關(guān)系(矩陣表示)來進(jìn)行潛在關(guān)系建模，并使用錨鏈接算法將兩者數(shù)據(jù)融合進(jìn)行點(diǎn)對(duì)關(guān)系的向量化，通過訓(xùn)練集與測(cè)試集來優(yōu)化預(yù)測(cè)性能。

2 預(yù)測(cè)方法

2.1 基本定義

任意兩個(gè)社交網(wǎng)絡(luò)Gv=(Uv,Ev)和Gn=(Un,En)，傳統(tǒng)錨鏈接方法直接預(yù)測(cè)兩個(gè)用戶ui∪Uv和uj∪Un是否同一個(gè)人(即ui=uj)，而本文構(gòu)建AL-P模型是通過兩個(gè)LBSN中的共同用戶來調(diào)整兩者的向量空間，即錨鏈接滿足二進(jìn)制鑒別函數(shù)φ：Uv×Un→{0,1}，其對(duì)應(yīng)的公式為

其中：()DEC表示用戶節(jié)點(diǎn)的向量編碼，即節(jié)點(diǎn)相似度的量化值；()ENC表示最大維度保存網(wǎng)絡(luò)屬性，即節(jié)點(diǎn)向量化維度值；P()是由用戶定義的節(jié)點(diǎn)間相似性度量值。

2.2 預(yù)測(cè)模型

圖3 AL-P預(yù)測(cè)模型

2.3 錨鏈接算法

輸入：兩個(gè)異構(gòu)網(wǎng)絡(luò)Gv和Gn；預(yù)訓(xùn)練函數(shù)φ和F；參數(shù)W和b，有標(biāo)簽的錨鏈接集合Ev。

1:repeat

2: for each epoch do

3:for i = 1 to N do

6:根據(jù)更新參數(shù)W和b

7:end for

8:計(jì)算y=Ftrue和a=o′(Fpredicted)

9:再次更新參數(shù)W和b

10:end for

11:until 收斂

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)準(zhǔn)備工作

本實(shí)驗(yàn)采用基于LBSN的Gowalla和Foursquare兩種不同的開源數(shù)據(jù)集[9]213(其中@NY表示紐約，@TY表示東京，@WHG表示華盛頓，@CCG表示芝加哥)，如表1所示，從中提取用戶關(guān)系拓?fù)鋱D和用戶簽到記錄，以及對(duì)相關(guān)數(shù)據(jù)進(jìn)行預(yù)處理操作，其結(jié)果如下表2所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集情況

表2 數(shù)據(jù)預(yù)處理結(jié)果

本實(shí)驗(yàn)對(duì)照基準(zhǔn)模型有Walk2friends[5]108和DeepWalk[6]122，其中Walk2friends提取用戶移動(dòng)特征，而DeepWalk提取用戶節(jié)點(diǎn)序列，兩種模型的操作方法統(tǒng)一用隨機(jī)選擇平均Average。評(píng)估指標(biāo)有AUC、精度、查全率和F1值(精度與查全率的調(diào)和平均)。

3.2 實(shí)驗(yàn)結(jié)果

評(píng)估指標(biāo)AUC可以檢測(cè)鏈路預(yù)測(cè)模型的性能，它表示正/負(fù)樣本的概率值，其實(shí)驗(yàn)結(jié)果如表3所示，說明在不同的數(shù)據(jù)集中，AL-P模型的AUC值都優(yōu)于現(xiàn)有模型Walk2friends，DeepWalk，LINE，GraRep，Node2vec和Struc2vec，這里的數(shù)據(jù)融合操作統(tǒng)一采用Average操作。

表3 AL-P的AUC預(yù)測(cè)結(jié)果

對(duì)于Foursquare數(shù)據(jù)集(@NY與@TY)和Gowalla數(shù)據(jù)集(@WHG與@CCG)，完成評(píng)估指標(biāo)精度、查全率、F1值的衡量實(shí)驗(yàn)，其中表4是Foursquare數(shù)據(jù)集的預(yù)測(cè)結(jié)果，表5是Gowalla數(shù)據(jù)集的預(yù)測(cè)結(jié)果。從表4和表5中可以得到在鏈路預(yù)測(cè)任務(wù)中，AL-P預(yù)測(cè)效果在兩個(gè)數(shù)據(jù)集中是最佳的，這是因?yàn)锳L-P模型加入用戶簽到偏好信息，讓社交網(wǎng)絡(luò)信息比用戶移動(dòng)信息更具有指示性，有效提升鏈路預(yù)測(cè)的準(zhǔn)確度，而walk2friends結(jié)果差是由于預(yù)測(cè)時(shí)缺少用戶網(wǎng)絡(luò)結(jié)構(gòu)信息。

表4 Foursquare數(shù)據(jù)集的預(yù)測(cè)結(jié)果

表5 Gowalla數(shù)據(jù)集的預(yù)測(cè)結(jié)果

4 結(jié)語

為了提升鏈路預(yù)測(cè)的效果，本研究提出一種錨鏈方法，通過用戶向量對(duì)齊完成兩個(gè)異構(gòu)空間的映射，得到新的用戶訪問偏好向量，訓(xùn)練融合后更新出社交關(guān)系向量，從而進(jìn)一步提升鏈路預(yù)測(cè)的綜合性能。不足之處是從移動(dòng)數(shù)據(jù)和社交數(shù)據(jù)中如何學(xué)到更好的用戶表示，挖掘相關(guān)用戶數(shù)據(jù)的潛在價(jià)值，若在時(shí)空行為上建模，則能更好完成預(yù)測(cè)任務(wù)。

(責(zé)任編輯：潘姝靜)