一種基于多信息融合的興趣點推薦模型

肖 嵩,袁景凌,盛德明,胡恒德

(武漢理工大學 計算機科學與技術學院,武漢 430070)

1 引 言

隨著智能手機功能的日益強大,人們可以很方便的在社交網絡上交流自己的想法,分享自己的生活.基于位置的社交網絡(Location-based social network,LBSN)應運而生,以Yelp、Foursquare、Facebook為代表的LBSN采集了大量的數據,包括用戶的簽到信息、興趣點的地理信息、對興趣點的評論等信息.用戶也更愿意在LBSN上分享自己的生活,發現更多有相同興趣的用戶和新的興趣點.近年來,隨著LBSN研究的深入,給推薦系統領域帶來了巨大的收益.

由于LBSN的迅速發展,使得大規模LBSN異構數據急劇增加,并且極度稀疏.因此如何克服數據稀疏性,以及如何融合多種數據類型來提高推薦性能具有挑戰性.對于簽到信息,本文需要考慮用戶與POI之間的顯式和隱式關系.對于序列信息,本文需要考慮用戶和POI之間的時序關系.對于地理信息,本文需要考慮用戶與POI之間的距離.而且在簽到信息以及社交信息極度稀疏的情況下,簽到信息和社交信息對于興趣點推薦結果的影響并不大.

針對上述問題,本文使用二分網絡嵌入來學習簽到信息并解決稀疏性問題.為了進一步提高POI推薦的準確性,我們從簽到數據中提取用戶的簽入序列模式,并使用Glove算法訓練序列.然后,基于上述內容,本文可以整合簽到信息和序列信息.最后本文使用貝葉斯算法處理LBSN中的地理信息,并提出BiGloGeoRec模型來融合這些異質信息.本文的主要貢獻如下:

1)本文提出了一種名為BiGloGeRec的多信息融合POI推薦模型.在兩個常用數據集上的結果驗證了我們的POI推薦模型的準確性和實用性;

2)本文精心設計了多種方法來處理不同類型的數據.首先我們建立了一個user-POI雙向網絡,以學習用戶與POI之間的一階和二階相似性,并進一步利用Glove算法來訓練簽入序列.然后應用貝葉斯算法處理地理位置信息,并將上述異構信息融合到一個統一的模型中,從而成功提高了模型的準確性;

3)本文嘗試通過消融實驗探索不同信息對POI推薦的影響.實驗結果表明,地理信息影響最大,序列信息次之,簽到信息最小.

2 相關工作

POI推薦:POI推薦為用戶推薦未訪問的POI.關于LBSN數據集的不同方面有不同的研究.在本節中,我們將從地理、時序以及內容3個不同方面對POI推薦進行簡要介紹.

1)地理影響.在LBSN數據中,地理位置信息是一個顯著的特征,LBSN中的推薦除了考慮用戶的偏好興趣,還需要考慮時空上下文.用戶活動范圍通常呈現出一定的規律性,因此研究用戶的移動軌跡對興趣點推薦有很大的幫助.Ye[1]等人研究發現,地理位置和距離影響人類的移動模式,用戶更加傾向于在較近的興趣點簽到,如住處或者工作地附近,LBSN 的用戶簽到活動中表現出空間聚類現象,且當距離較遠時,用戶的意向將急劇下降.興趣點與用戶的空間距離對用戶的簽到行為有著重要的影響.

2)時序影響.在LBSN數據中用戶簽到行為具有時間效應.研究人員發現POI推薦具有時間序列和時間循環兩種模式.Wu等人[2]提出了一個考慮序列和簽到時間等上下文信息的偏好學習模型 LSPL,學習POIs的上下文特性,并利用注意力機制來捕捉用戶的偏好.

3)內容影響.在 LBSN中,用戶生成的內容包括對興趣點的評分和評論,以及關于興趣點的圖片.與簽到行為相比,內容通常表達了更加明確的偏好信息,可以作為對簽到信息的一種補充.研究人員利用 POI的可用內容信息來緩解數據稀疏問題.Jiang 等人[3]提出了一種基于主題模型的協同過濾(ATCF)方法,通過結合主題模型和矩陣分解來提取用戶的偏好.

本文中提出的BiGloGeoRec模型融合了影響因素中的簽到信息,簽到序列信息和地理信息,能有效提高POI推薦準確率,解決稀疏性問題.

網絡嵌入:網絡嵌入算法有如下研究成果.

2014年Bryan Perozzi等人提出的DeepWalk[4]拉開了網絡嵌入的帷幕,其主要思路,就是利用隨機游走在網絡上生成有上下文信息的節點序列語料庫,然后基于Word2vec的思想,使用Skip-gram和Hierarchical Softmax模型對語料庫進行訓練得到嵌入向量.在此基礎上Grover A等人提出了Node2vec[5]算法,通過改變隨機游走序列生成的方式進一步擴展了DeepWalk算法.

這些算法雖然在許多數據挖掘任務中都取得了很好的效果,但大多數集中于同構網絡,該網絡僅包含一種類型的節點和邊.實際上,許多網絡通常具有多種類型的節點和邊緣,被廣泛稱為異構信息網絡(HIN),與同類網絡相比,HIN融合了更多信息并包含更豐富的語義.因此越來越多的學者開始利用異質信息網絡中蘊含的豐富信息,如Dong等人[6]采用基于元路徑的隨機游走來生成節點序列,以優化節點之間的相似性.Shi等人[7]將HIN分解為簡單的網絡,然后優化每個子網中節點之間的鄰近度.

在異質網絡數據中,二部圖網絡又是一種特殊的網絡,它有兩種類型的頂點.相比于其他的異質網絡嵌入算法,BINE[8]能夠更好地學習二部圖網絡的頂點表示.雖然二分網絡只是異質信息網絡中的一種特殊網絡,但是它廣泛存在于各類數據中,比如推薦系統中的用戶與物品的關系就可以看做是一種典型的二分網絡.生物大數據中的顯隱基因的表達也可以抽象為二分網絡的形式.因此使用二分網絡嵌入可以充分發掘二分網絡中的結構信息和語義信息,在具有二部圖網絡性質的數據中取得突出的效果.

3 BiGloGeoRec模型的提出

本文提出了一種基于網絡嵌入的多信息融合POI推薦模型BiGloGeoRec.模型通過二分網絡嵌入算法處理用戶簽到信息,得到用戶興趣點的嵌入向量,計算用戶未訪問的興趣點的分數ScoreBi.通過序列嵌入算法來處理用戶簽到序列信息,得到興趣點的嵌入向量,計算用戶未訪問的興趣點的分數ScoreGlo.然后在前面的基礎上融合兩種信息,得到一個綜合評分ScoreBiGlo.使用Naive Bayesian算法來處理地理位置信息,得到地理信息評分ScoreGeo.最后來建立一個統一的模型BiGloGeoRec融合所有信息,通過ScoreBiGlo和ScoreGeo得到最終評分,根據最終評分對用戶進行POI推薦.BiGloGeoRec模型的框架圖如圖1所示.

圖1 BiGloGeoRec模型框架圖

3.1 基于二分網絡嵌入算法處理簽到信息

本節通過用戶簽到數據,建立二分網絡,即用戶-興趣點圖.基于二分網絡嵌入算法BINE對用戶-興趣點二分網絡進行訓練,得到用戶對還未訪問的興趣點的個人興趣評分ScoreBi.用戶-興趣點二分網絡示意圖如圖2所示.

圖2 構建user-POI二分網絡

首先,本文在數據集中分離出所需要的用戶簽到信息,構建二部圖.如果用戶在興趣點產生過簽到行為,則用戶和興趣點之間存在一條邊.如果二分網絡中有直接的邊相連,我們這種關系為一階相似度.除了直接相連的關系,二分網絡中相同的頂點之間還有間接關系.反映在用戶興趣點二分網絡中,即為用戶ui(興趣點li)和用戶uj(興趣點lj)之間如果有一條路徑ui-li-…-uj相連.我們稱這種間接關系為二階相似度.為了更好的保留原始二分網絡中頂點的信息,本文需要分別對一階相似度和二階相似度建模.

一階相似度建模:通過兩個相連頂點之間的局部鄰近建模.對于用戶頂點ui和興趣點頂點lj之間的聯合概率定義為:

(1)

(2)

其中wij表示邊eij的權重.wij越大,邊eij連接的兩個節點共同出現的概率越高.

二階相似度建模:隱式關系建模需要得到相同類型的兩個節點之間的路徑數量和長度.通過隨機游走,將用戶-興趣點二分網絡轉換為用戶序列和興趣點序列兩個語料庫,然后從兩個語料庫中分別學習用戶和興趣點的嵌入向量.兩個頂點之間的二階相似度定義如公式(3)、公式(4):

(3)

(4)

在隨機游走的過程中,由于二分網絡的特殊性,DeepWalk生成的語料庫無法捕捉用戶-興趣點網絡的特征,BINE采用了偏自適應的隨機游走采集用戶興趣點頂點集,保留了用戶-興趣點網絡的頂點分布.

在得到用戶和興趣點兩個語料庫之后,為了捕獲頂點間的二階相似度,本文假定在序列中共現概率高的頂點具有相似的嵌入向量.因此,我們定義用戶語料庫DU的最大條件概率如公式(5):

(5)

其中CS(ui)表示序列S中頂點ui的上下文頂點.

本文定義興趣點語料庫DL的最大條件概率如公式(6):

(6)

根據現有的神經網絡嵌入方法,本文可以采用公式(7)、公式(8)來參數化條件概率P(uc|ui)和P(lc|li):

(7)

(8)

其中P(uc|ui)表示在ui的上下文中出現uc的可能性;類似的含義適用于P(lc|lj).通過公式(7)、公式(8)以及公式(5)和公式(6)中定義的目標,可以使序列中共現概率高的頂點具有相似的嵌入向量.

在得到了顯式關系和隱式關系之后,建立聯合優化框架將所有的目標函數組合起來:

maximizeO=αlogO2+βlogO3-γO1

(9)

其中參數α,β和γ為需要設定的超參數,分別用于公式中的logO2,logO3以及O1.

(10)

3.2 融合簽到序列信息

在上一節中,我們通過二分網絡嵌入訓練學習簽到信息,得到了用戶未訪問的興趣點的分數ScoreBi.為了得到更加精確的興趣點推薦,本節研究了用戶的移動模式,融合簽到序列信息.本節首先在數據集中提取出簽到序列,然后使用Glove訓練簽到序列,得到用戶對還未訪問的興趣點的評分ScoreGlo.提取學習簽到序列數據的流程如圖3所示.最后融合用戶簽到和簽到序列兩種信息.

圖3 提取學習簽到序列數據

(11)

對每個用戶u未訪問的興趣點,有兩部分得分,一個是二分網絡嵌入得分ScoreBi,一個是序列嵌入得分ScoreGlo,通過進行歸一化處理,按照公式(12),得到每個用戶u未訪問的興趣點的分數ScoreBiGlo.

(12)

3.3 地理位置信息建模

LBSN數據集中除了前兩節中融合的簽到信息和簽到序列信息,還有地理位置信息,地理位置信息是LBSN數據中最顯著的信息.對于地理位置信息,本節采用Naive Bayesian算法處理,可以根據用戶已簽到的興趣點來計算未簽到的興趣點概率.本文將一個用戶簽到過的興趣點集合作為一個類簇,那么給該用戶推薦新的興趣點就可以轉化為一個分類問題,由于用戶有很多未訪問的興趣點,所以可以使用Bayesian算法來計算用戶未興趣點屬于目標類簇的概率大小.

將樸素貝葉斯算法應用到本文中,設Li是用戶ui已經簽到的興趣點分類集合.Pr[Li]是用戶在興趣點集合中所有興趣點都簽到的概率.因為用戶的簽到概率受距離的影響,我們可以使用公式(13)計算Pr[Li]的大小:

(13)

其中d(lm,ln)代表興趣點lm和ln之間的距離.定義興趣點lm的坐標為(latm,lonm),興趣點ln的坐標為(latn,lonn),則可根據大圓距離公式計算d(lm,ln).

d(lm,ln)=R·arccos[coslatm·coslatn·cos(lonm-lonn)+sinlatm·sinlatn]

(14)

其中,R為地球半徑.當d(lm,ln)越小時,Pr[d(lm,ln)]越大,即簽到概率與距離成反比,由此可得公式(15):

(15)

對于一個興趣點lj(lj∈L-Li),用戶在興趣點lj簽到的概率可以簡化為:

(16)

由于用戶待推薦的未簽到興趣點數據很多,可能導致Pr[lj|Li]向下溢出,所以需要對公式(16)取對數,可得公式(17):

(17)

對其進行歸一化處理,設計出了用戶ui在興趣點lj的簽到得分如公式(18):

(18)

ScroceGeo即是對地理位置信息建模后用戶與興趣點間距離的度量.

3.4 建立BiGloGeoRec模型

本節在前3節得到用戶對還沒有訪問的興趣點的分數ScoreBiGlo、ScroceGeo的基礎上,建立一個統一的模型 BiGloGeoRec進行個性化POI 推薦.最終,定義興趣點lj的得分如公式(19)所示:

Score(ui,lj)=αScoreBiGlo(ui,lj)+(1-α)ScoreGeo(ui,lj)

(19)

上式中Score(ui,lj)即是用戶ui對興趣點lj的興趣、規律、距離這3個因素的度量得分,其中ScoreBiGlo(ui,lj)是用戶ui對興趣點lj的興趣、規律的度量得分,ScoreGeo(ui,lj)是用戶ui對興趣點lj的距離的度量得分.α是用來調節這兩部分得分的比重大小.

4 實 驗

4.1 實驗數據集

本文使用Weeplaces數據集和Foursquare數據集.本文準備了 Weeplaces數據中美國洛杉磯的數據.該數據集中包含2553位用戶在8054個興趣點上生成的105229條簽到記錄.Foursquare數據中美國紐約的數據,該數據集中包含1083位用戶在 12209個興趣點上生成的188349條簽到記錄.

4.2 評價標準

本節選用準確率 Precision、召回率 Recall 、F1值和正確率Accuracy 4個評價指標來驗證BiGloGeoRec模型的性能.準確率指正確推薦的興趣點個數占總推薦興趣點個數的比率.召回率指正確推薦的興趣點個數占興趣點總數的比率.F1值用來對準確率和召回率進行整體評價,是準確率和召回率的調和平均值.正確率指推薦正確的興趣點個數占測試集大小的比率.4個評價指標具體公式如公式(20)-公式(23)所示.

(20)

(21)

(22)

(23)

其中Svisited為用戶訪問過的興趣點集合,SK,rec為前k個被推薦的興趣點集合,hit@K是測試集中預測正確的總數,|Stest|為測試集的大小.

4.3 實驗結果與分析

在本節中我們選取了FML、BINE、CoRe 3個對比模型來驗證 BiGloGeoRec模型的性能:

FML:分解度量學習模型.FML 從位置和距離的角度考慮推薦問題,直接將距離矩陣分解為用戶和項目密集嵌入,用戶和項目被表示為多維坐標系(即度量向量空間)中的點,根據估計距離進行推薦任務.

BINE:用于學習Bipartite網絡的頂點表示.通過有目的地執行偏向隨機游走,生成的頂點序列可以很好地保留原始二分網絡中頂點的長尾分布.將學習到的嵌入向量用于推薦.

CoRe:該模型基于魯棒性規則將用戶偏好融合到具有社會影響和地理影響的興趣點推薦中,提出了一個統一的興趣點推薦框架進行協同過濾推薦.

4.3.1 標準情況下的BiGloGeoRec模型實驗

在BiGloGeoRec模型中,使用二分網絡嵌入對簽到數據建模時,通過實驗,我們將嵌入向量大小設置為128,將損失權衡參數α,β和γ分別設置為最佳值0.01,0.01和0.1.通過交叉驗證設置3.4節中的α為0.2.在Weeplaces和FourSquare兩個數據集上的實驗結果如表1.在Weeplaces數據集上的對比實驗結果如圖4-圖6所示.

表1 在兩個數據集上的對比試驗結果

從圖4-圖6可以看出,本文提出的BiGloGeoRec方法可有效提高POI推薦的性能.從表1中可以看到在Weeplaces和FourSquare兩個數據集上,在Precison,Recall,F1,Accuracy 4個評價指標上BiGloGeoRec均優于對比模型.BINE模型只用到用戶簽到信息,沒有辦法全面獲取用戶對興趣點的偏好,

圖4 4個模型的準確率隨k值的變化

圖5 4個模型的召回率隨k值的變化

圖6 4個模型的F1值隨k值的變化

因此效果不佳.CoRe模型同時考慮到了用戶的社會關系信息和地理位置信息,但是沒有用到簽到序列信息.它使用健壯的規則來整合用戶的社會關系信息和地理位置信息.對于地理位置信息,使用核密度估計進行建模,因此它的表現僅次于BiGloGeoRec.FML模型僅從位置和距離的角度考慮推薦問題,但與BINE相比,它考慮了地理位置信息,因此其性能優于BINE模型.實驗結果表明,充分利用多種信息可以減輕數據稀疏性,提高興趣點推薦系統的性能.

4.3.2 BiGloGeoRec模型中各因素對實驗結果的影響

實驗數據集仍采用Weeplaces和Foursquare數據集.實驗參數的設置與4.3.1相同,評價指標采用Accuracy.實驗結果如圖7、圖8所示.

圖7 在Weeplaces數據集上的對比

圖8 在Foursquare數據集上的對比

GloGeoRec:本文所提出的模型去掉簽到數據信息之后的模型.

BiGeoRec:本文所提出的模型去掉簽到序列信息之后的模型.

BiGloRec:本文所提出的模型去掉地理信息之后的模型.

從實驗結果可以發現,對于Weeplaces和Foursquare數據集以及本文提出的BiGloGeoRec模型,GloGeoRec模型性能下降最小,而BiGloRe模型性能下降最大.我們可以得出各種信息對推薦效果的影響:地理信息>簽到序列信息>簽到信息.

5 結 論

由于人們活動的隨機性,LBSN數據集的稀疏性和異質性,POI建議面臨著獨特的挑戰.許多學者使用LBSN的社交信息,地理位置信息,簽到序列信息,時間信息來提高POI推薦系統的性能,但是很少有方法通過融合各種信息來提高推薦系統的性能.為了解決上述問題,本文提出了一種基于多信息嵌入和位置信息融合的興趣點推薦算法.整合了用戶簽到信息,簽到順序信息和地理位置信息,建立了一個多信息融合的POI推薦模型.實驗結果證明,BiGloGeoRec模型可以有效解決數據異構且稀疏的問題,提高了POI推薦的效果.