位置社交網絡中譜嵌入增強的興趣點推薦算法

劉真，王娜娜，王曉東，孫永奇

（北京交通大學計算機與信息技術學院，北京 100044）

1 引言

基于位置的社交網絡（LBSN,location-based social network）中不僅包含原有傳統社交網絡中的社交網絡關系和用戶標注信息，還包含基于GPS 服務收集的用戶簽到位置軌跡及相關位置的標注信息[1]。用戶的移動行為模式、行動軌跡呈現一定的規律及特點[2]。隨著LBSN 服務中用戶數量的增加，包含多維度信息的LBSN 簽到數據信息量也急劇增加，感興趣的位置點（POI,point of interest）推薦成為LBSN 中的重要研究方向。為了滿足用戶尋找感興趣地點的需求，POI 推薦使用用戶歷史簽到位置、軌跡等一系列時空信息預測用戶當下可能感興趣且尚未訪問過的位置[3]，例如酒店、餐廳、博物館、商場等。

LBSN 中的多維度簽到信息包括用戶地理位置（Geo）、時間（temporal）、POI 類別信息和社交關系[4-7]。通過對LBSN 數據的深度挖掘，可以揭示更深層次的用戶的POI 偏好。利用這些信息為用戶推薦POI 可以有效幫助用戶過濾掉不感興趣的位置點，提高推薦準確率。

目前基于LBSN 的POI 推薦研究采用的模型主要有基于矩陣分解的協同過濾模型、概率模型以及神經網絡模型。Cheng 等[8]綜合考慮地理因素和社交因素，使用多中心高斯模型對地理因素建模，使用概率矩陣分解處理社交因素，最后將這兩者融入廣義矩陣分解框架中。Zheng 等[9]提出了一種新的概率方法，從用戶簽到記錄挖掘隱藏的主題，基于該主題采用跨區域協同過濾方法以推薦新的POI。

近年來，神經網絡應用于推薦系統中并取得較大進展。Ma 等[10]為融合上下文信息（如社交信息、地理信息等）和對用戶-POI 之間的交互進行非線性建模，提出了一種基于自動編碼器的模型。Zhao 等[11]提出了一種最大邊際度量地理社交多媒體網絡表示學習框架。Yang 等[12]將協同過濾與半監督學習相結合提出了一種基于神經網絡的模型PACE（preference and context embedding），該模型通過對相鄰用戶和POI 進行平滑緩解數據稀疏，構造上下文信息圖以共同學習用戶和POI 的嵌入，從而預測用戶對POI 的偏好。Ying[13]等提出了一種基于秩的方法PGRank，它將用戶地理偏好和潛在偏好集成到貝葉斯個性化排名框架中。

現有研究中還存在以下2 個問題。

1)LBSN 中包含豐富的簽到、社交等上下文信息，現有的融合上下文信息的推薦模型如果不能很好地捕捉數據的多維空間特性，將難以準確地捕獲用戶最近鄰。

2)矩陣分解模型中用戶對POI 的交互被處理為其潛在特征向量的內積，而內積只反映了潛在空間中向量之間的線性關系，忽視了用戶和POI 之間存在的非線性交互[14]。

基于上述分析，本文提出譜嵌入增強的POI 推薦算法PSC-SMLP（preference enhanced spectral clustering and spectral embedding enhanced multi-layer perceptron）。該算法由兩部分組成：偏好增強的譜聚類算法PSC 和譜嵌入增強的多層感知機SMLP。一方面，與傳統的社交網絡推薦算法不同，LBSN 豐富的信息有助于捕獲用戶之間的偏好緊密程度。因此，借助譜聚類能在任意形狀的樣本空間上聚類且收斂于全局最優解的優點，提出了融合上下文信息的偏好增強的譜聚類算法PSC，以更準確地獲得用戶最近鄰，便于更好地學習用戶對POI 的偏好。另一方面，本文提出譜嵌入增強的神經網絡SMLP，通過捕捉用戶和POI 的二分圖關系進行譜嵌入，以增強MLP（multi-layer perceptron）學習用戶與POI 之間的非線性交互能力。使用譜聚類后用戶最近鄰所形成的用戶-POI 對的拼接向量作為SMLP 網絡的輸入，通過譜嵌入和神經網絡的網絡結構和非線性激活函數對用戶與POI 之間的復雜交互進行非線性建模，以學習用戶的POI 個性化偏好。

2 融合上下文信息的POI 推薦模型框架

2.1 問題描述

對融合上下文信息（簽到信息、社交信息）的POI 推薦定義如下。

定義1用戶簽到。假設u 為用戶，p 為POI，uID為用戶u 的ID 標識，pID為p 的ID 標識，則用戶u 在位置點p 的一次簽到可以用一個三元組來表示：，其中，t 為簽到時間。進一步地，用戶u 的簽到POI 集合可以表示為

定義2社交關系。是指用戶之間互為好友，對于一對互為好友的用戶u 和用戶v，他們之間的社交關系可以用一個二元組來表示，即。進一步地，用戶u 的好友集合可以表示為。

定義3POI 推薦。給定用戶u 及其簽到的POI集合Pu和好友集合Fu，POI 推薦為預測用戶u 對所有未有簽到記錄的POI 點p 的偏好值，按偏好值排序的前K 個POI 則為對用戶u 推薦的結果。

2.2 PSC-SMLP 推薦模型框架

本文提出的PSC-SMLP 模型框架如圖1 所示。圖1 中，通過設計偏好增強的譜聚類算法PSC 提出SP 相似度從用戶簽到偏好和社交偏好2 個方面捕捉數據的多維空間特性，更準確地捕獲用戶最近鄰，繼而使用譜聚類獲得用戶群組；進一步構造譜嵌入增強的神經網絡SMLP 挖掘用戶和POI 的非線性交互。SMLP 共分五部分，分別是輸入層、譜嵌入層、拼接層、隱藏層和輸出層。將用戶群組中的用戶-POI 標記對輸入譜嵌入層，通過用戶和POI 二分圖的譜進行潛在因子建模，獲得用戶和POI 的譜特征向量表示。然后，將用戶和POI 譜特征向量進行拼接，構造拼接向量作為隱藏層的輸入，使用多個隱藏層深度模擬用戶和POI 之間的交互。最后采用softmax 層作為輸出層產生用戶對POI 的偏好預測。

圖1 PSC-SMLP 模型框架

3 偏好增強的譜聚類算法PSC

LBSN 中用戶與用戶之間的關系可以表示為社交網絡圖G，如圖2 所示。圖G 中的頂點有兩類，分別是用戶和POI；邊有三類，分別為用戶之間表示社交關系的邊，用戶和POI 之間表示簽到關系的邊，POI 之間表示關聯關系的邊。

圖2 LBSN 社交網絡G

以LBSN 標準離線數據集 Brightkite 為例，對其社交信息的分析結果分別如表1 和圖3 所示。

表1 社交信息分析結果

圖3 社交信息分析統計結果

從表1 中可知好友之間的平均共同簽到數量遠大于非好友之間的平均共同簽到數量，這反映出好友之間有更大的簽到相似性。圖3 中，縱坐標是用戶數量，橫坐標表示用戶訪問其好友曾經訪問過位置的概率，即用戶第一次訪問該位置之前該位置已被其好友訪問過的概率。由圖3 可知，用戶初次訪問的位置中90%以上曾被其好友訪問過的用戶數量位居第三。

經過上述分析可知，社交好友之間擁有更相似的簽到偏好，用戶在選擇新的訪問地點時，更偏向于訪問其好友訪問過的位置。

因此，本文從簽到偏好和社交偏好兩方面挖掘用戶偏好的相似程度，構造偏好相似矩陣，繼而采用常用于圖領域、可識別任意形狀空間并且能收斂于全局最優解的譜聚類算法挖掘用戶最近鄰，提出了偏好增強的譜聚類（PSC）算法。

3.1 PSC 算法

PSC 算法框架如圖4 所示。

圖4 PSC 算法框架

PSC 算法詳細步驟如下。

1)偏好提取歸一化相似度矩陣W

圖2 中用戶和用戶之間的邊定義為偏好相似程度，本文提出同時考慮簽到關系和好友關系的sp相似度來度量用戶與用戶之間的邊權值，如式(1)～式(3)所示。其中，式(1)中代表u1和u2共同簽到的POI個數，up 表示兩用戶的興趣偏好相似度的程度；式(2)中代表u1和u2共同好友個數，uf 表示兩者的好友關系程度；式(3)中sp 相似度由up 和uf兩部分的乘積計算得到。進一步采用隨機游走的思想將用戶和用戶之間的相似度進行歸一化，構造用戶與用戶的相似度矩陣U 以作為歸一化的相似度矩陣W，如式(4)所示。

2)歸一化的Laplacian 矩陣Lsym

譜聚類算法將聚類問題看作圖分割問題，圖分割的最優化問題與求解Laplacian 矩陣特征向量問題等價，因此要得到用戶相似度矩陣對應的Laplacian矩陣。本文歸一化的相似度矩陣W 為對稱矩陣，故選擇歸一化Laplacian 矩陣Lsym，根據式(5)可以計算得到。

其中，D 為W 的對角矩陣，L=D-U。通過特征值處理，獲得用戶相似度矩陣對應Laplacian 矩陣Lsym的特征向量矩陣VT=[x1,x2,…,xn]，采用K-means對VT中的列向量進行聚類，聚類結果中x1,x2,…,xn分別所屬的類別對應用戶所屬的類別。將隸屬于相同類別的用戶歸為一個群組，從而獲得用戶最近鄰構成的群組。

3.2 PSC 算法偽代碼

PSC 算法偽代碼如算法1 所示。

算法1PSC 算法

輸入用戶簽到矩陣R、社交矩陣S

輸出用戶群組

4 SMLP 神經網絡設計

一些研究進展[10-12]證明了神經網絡在處理信息檢索和推薦任務中挖掘用戶和物品之間非線性潛在關系的有效性。

本文構建了譜嵌入增強的神經網絡SMLP，網絡結構如圖1 所示。SMLP 的網絡結構包括輸入層、譜嵌入層、拼接層、隱藏層和輸出層。通過PSC 算法獲得的用戶群組及其簽到過的POI 形成用戶-POI 對分別輸入到譜嵌入層，將獲得用戶和POI 的譜嵌入表示，通過拼接層，獲得用戶-POI 對的譜嵌入式拼接向量。在隱藏層中，對拼接向量進行學習，最后在softmax 層輸出用戶對POI 的偏好預測。

4.1 譜嵌入層

圖2 中的用戶和POI 之間的簽到關系可以表示為二分圖，包含豐富的用戶和POI 的直接或間接連通信息，間接隱含的連通度對挖掘偏好也具有重要意義。圖的譜側重于反映圖的連通性，有助于更好地挖掘潛在連通性。

圖的譜即是圖拉普拉斯矩陣的特征向量所組成的矩陣[15]。本文提出的譜嵌入層通過連通信息圖的譜對用戶和POI 進行譜映射，從而獲得用戶和POI 的譜嵌入向量。具體設計如式(6)所示。

其中，SE=Efα(Λ)ET，Λ=diag {λ1,λ2,…,λn}，fα(Λ)==diag{α1λ1,α2λ2,…,αnλn}。E 和Λ分別是用戶-POI簽到二分圖對應拉普拉斯矩陣的特征向量矩陣和特征值矩陣，fα(Λ)對特征值進行參數化以獲得更好的特征表示，eu和 ep是指定嵌入維度使用高斯分布隨機初始化的用戶特征向量和POI 特征向量，分別代表用戶譜嵌入向量和POI 譜嵌入向量。

4.2 其他各層的設計

本文使用神經網絡來擬合輸入用戶-POI 對和輸出POI 預測結果之間的關系。本文選用非線性激活函數，通過隱藏層層數的不斷加深可以使神經網絡逼近任意復雜函數，從而可以更加明確地描述輸入與輸出之間的關系，并將神經元的輸出映射到有界的區域。

因此，SMLP 神經網絡各層的輸出為

其中，Wq，bq是第q 層的參數。當q=0 時，x 為用戶-POI 對的拼接向量。

POI 推薦屬于OCCF（one class collaborative filtering）問題[16]。為了特別處理POI 推薦中隱式反饋的單類性質，在隱藏層的頂部連接了一個二進制softmax 層。softmax 層是一個使用sigmoid 函數的邏輯回歸層，因此在輸入層也使用sigmoid 函數來獲得用戶對POI 的偏好程度，如式(8)所示。

本文選用對數損失函數（logloss）作為SMLP神經網絡的目標函數，如式(9)所示。

5 實驗及結果分析

5.1 實驗設置

5.1.1 數據集分析

本文實驗部分數據集采用的是LBSN 中2 個經典的數據集（Gowalla 和Yelp）。

Gowalla 數據集為斯坦福大學研究人員在Gowalla 平臺上獲得的2009 年2 月至2010 年10 月在全球范圍內生成的真實簽到數據。過濾掉簽到POI 次數少于15 的用戶及被簽到次數少于10 的POI，過濾后的數據集包括18 737 個用戶，32 510 個POI，1 278 274 次簽到。平均每個用戶簽到68 個POI，每個POI 被40 個用戶簽到過。

Yelp 數據集包含大量的POI 和若干個城市內的簽到記錄。過濾掉簽到POI 次數少于10 的用戶，過濾后的數據集包含30 887 個用戶，18 995 個POI和860 888 次簽到。平均每個用戶簽到27 個POI，每個POI 被45 個用戶簽到過。

Gowalla 和Yelp 數據集中都包括好友關系和簽到記錄，其中互為好友關系的用戶成對出現。對數據進行預處理后的基本信息如表2 所示，表中稀疏度表示為用戶-POI 簽到次數矩陣中空白項和所有項的比例。

表2 數據集基本信息

針對Gowalla 和Yelp 這2 個數據集，對用戶簽到POI 數量和POI 被簽到的用戶數量進行統計，如圖5 所示。圖5 中縱軸表示參與統計的用戶數量或POI 數量，橫軸表示簽到數量。

圖5 N1和N2的數量

將用戶簽到POI 數量標記為N1，POI 被簽到用戶數量標記為N2。從圖5 可看出在Gowalla 數據集上用戶簽到POI 數量為31～51 的用戶數目最多，而在Yelp 數據集上，用戶簽到POI 數量范圍為0～20的用戶數量最多。

5.1.2 對比算法

本文采用以下 8 個算法與本文提出的PSC-SMLP 算法進行對比。

1)iGSLR（personalized geo-social location recommendation）[17]。使用KDE（kernel density estimation）為用戶簽到行為的地理因素進行個性化建模，然后將用戶偏好、社交和地理因素融合到統一的框架中。

2)LFBCA（location-friendship bookmark-coloring algorithm）[18]?；? 種因素，分別為用戶的歷史行為、地理因素、社交因素和相似用戶，使用PPR（personalized page rank）算法，計算過程使用書簽著色算法（bookmark-coloring algorithm）。

3)LORE（location recommendation）[19]：從用戶的簽到行為中挖掘順序影響，將順序、社交和地理影響融合到統一的推薦框架LORE 中。

4)USG（user social geographical）[20]?？紤]到用戶偏好、社交及地理影響，分別使用UserCF（user collaborative filtering）、FCF（friend collaborative filtering）和冪律分布對其進行建模，最后將多個模型融合到統一的推薦框架USG 中。

5)IRenMF（instance-region neighborhood matrix factorization）[21]。通過將相鄰特征合并到加權MF（matrix factorization）中來對地理影響建模。

6)ASMF（augmented square error based matrix factorization）和ARMF（augmented ranking error based matrix factorization）[22]。考慮到社交影響、分類影響、地理影響，提出了基于平方誤差的MF 模型和基于增強的排名誤差的MF 模型。

7)PACE（preference and context embedding）[12]。考慮到LBSN 中的多種上下文因素（重點是社交影響和地理影響），將協同過濾和半監督學習相結合提出了一種通用的推薦框架。

8)LOCABAL（local and global）[13]。利用2種社會關系社交朋友和全球聲譽較高的用戶使用MF 進行建模。

本文使用了4 個評價指標用于衡量算法的性能，即準確率（Pre@K）、召回率（Rec@K）、歸一化折扣累積增益（nDCG@K）和平均精度（MAP@K），其中，K 表示推薦列表的大小。

5.2 參數設置實驗

采用留一法方案[12]，根據文獻[23]的策略為每個用戶真實簽到的POI 隨機選擇100 個未簽到的POI 作為負樣本，然后將真實簽到的POI 和負樣本混合構造測試集。

5.2.1 PSC 中聚類簇數k 的設置

本文選擇常用的聚類評估指標。CH 指標（Calinski-Harabaz index）分數來進行聚類簇數k 的評價。CH 指標分數越大說明聚類效果越好。

對于k 個簇，CH 指標分數由簇間離散平均值與簇內離散之比得出

其中，N 是數據集的數量，Bk是簇內離散矩陣，Wk是簇間離散矩陣。Bk和Wk的定義如式(11)和式(12)所示。

其中，Cq是簇q 的中心，c 是數據集的中心，nq是簇q 的數據點的數量。

假設k 分別為2、5、8、10、15，對數據集Gowalla和Yelp 使用CH 指標分數來評估聚類效果，結果如圖6 所示。從圖6 中可以看出，對于數據集Gowalla，當聚類簇數k 為8 時聚類效果最好。對于Yelp 數據集，當k 為2 時，聚類效果最好，但是考慮到該數據集的整體平均情況，選擇聚類效果次優的k=8 的值。因此，設置聚類簇數k 為8。選用用戶數量最多的群組分別進行后續實驗，最后在Gowalla 和Yelp 數據集上分別選用用戶群組2 和用戶群組1，這2 個群組的用戶數量分別為8 302 和9 233。

圖6 聚類簇數k 對聚類效果的影響

5.2.2 神經網絡結構的評估

本文通過改變神經網絡架構中隱藏層的層數以及每個隱藏層的容量（即神經網絡的深度和寬度）來討論PSC-SMLP 中學習用戶偏好的有效性。

本文設置用戶和POI 嵌入到共享維度空間[16]。輸入層是用戶和POI 的聯結向量，所以隱藏層的輸入層容量是2 的倍數，受文獻[12]啟發，將隱藏層以2 的指數衰減進行架構的設計。

1)首先令聚類簇數k=8，按照32→16→8→4設計神經網絡的架構（為避免過飽和，設置較為適中的網絡結構），設推薦列表數量為10，以Gowalla為數據集討論迭代次數對于損失函數值loss 和命中率HitRatio@10 的影響，如圖7 所示。從圖7 中可以發現隨著迭代次數的增加，訓練目標函數的loss越來越小，且在迭代次數為20 時，loss 急劇下降。綜合考慮HitRatio@10 和loss，本文將迭代次數設為50。

圖7 迭代次數對命中率和損失值的影響

2)在 Gowalla 數據集上對所有數據使用accuracy 來評估神經網絡深度和寬度的影響。accuracy 通過預測值和實際值之間差值來衡量神經網絡在不同網絡結構下的訓練效果，如表3 所示，其中h 為神經網絡層數。

表3 不同神經網絡結構的accuracy

設置其它參數，如學習率為0.000 1。從表3 中可以看出，當只使用一層神經網絡時，神經元的個數越多，accuracy 越高。一般來說，固定最后一層的容量大小，隨著層數的增加，accuracy 增大。當最后一層的容量較大時，隱藏層層數的增加會給模型帶來飽和，例如表3 中當層數為4，最后一層神經元的個數為64 時，本文提出的神經網絡模型對于已固定的其他參數而言，達到了飽和狀態。

5.3 性能比較

5.3.1 與對比算法的比較

圖8 表示在Gowalla 和Yelp 這2 個數據集上PSC-SMLP 與其他算法的性能，PSC-SMLP 在各項指標上均優于其他模型。圖8(a)～圖8(d)所示在Gowalla 數據集上的各個算法性能均優于圖8(e)～圖8(h)所示在Yelp 數據集上的算法性能，這是因為Gowalla 數據集的簽到信息和社交信息較Yelp數據集更為豐富，充分表明利用PSC 融合上下文信息給模型帶來的優勢。

圖8 Gowalla 和Yelp 數據集上的性能對比

對比算法中PACE 屬于神經網絡模型，其他算法模型都是基于傳統的協同過濾矩陣分解模型。PSC-SMLP 和PACE 在各指標上性能的優越性充分表明了神經網絡結構和非線性激活函數對于復雜交互場景下的學習能力。PSC-SMLP 在Gowalla 數據集 Rec@K 中平均提高約3%，最高達13%。在Pre@K 中提高最高達1.9%。在Yelp 數據集中Rec@K 中平均提高約4%，在Pre@K 中提高最高達2.1%，從在同一數據集上算法的性能提升來看，PSC-SMLP 算法在稀疏數據集上比PACE 模型的有效性更明顯。一方面是因為PSC 不僅從用戶簽到偏好和社交影響2 個方面捕捉相似用戶獲得用戶群組，而且從聚類角度緩解數據稀疏；另一方面，模型的SMLP 部分有效地利用神經網絡和非線性激活函數的優勢捕獲用戶和POI 之間的復雜交互，更好地學習了用戶偏好。

充分利用簽到信息和社交信息，更有利于提高算法的性能。PSC-SMLP 在Gowalla 上的平均性能比IRenMF 提高約3%，其中，在Recall@10 上的改進高達7.9%。在Yelp 數據集上，PSC-SMLP 優于IRenMF 約3.2%，可以發現PSC-SMLP 在稀疏度更大的Yelp 數據集上實現的性能提高優于在Gowalla 數據集上實現的提高，這也說明利用更多的上下文信息，PSC-SMLP 可以緩解數據稀疏。

5.3.2 PSC-SMLP 與SMLP 的比較

在Gowala 數據集和Yelp 數據集上，從Pre@K和Rec@K 這2 個指標來對比PSC-SMLP 和SMLP算法，以衡量PSC 譜聚類所起的作用，如圖9 所示。從圖9 可以發現，PSC-SMLP 在2 個指標上均優于SMLP，在 Gowalla Pre@K 上，性能提升約為0.2%～1.6%；在Gowalla Rec@K 上性能最高提升約為2.11%。在Yelp Pre@K 指標上PSC-SMLP 性能提升約為0.5%～1.8%；在Yelp Rec@K 上性能最高提升約為3.08%。從這些數據中可發現，PSC-SMLP相比于SMLP 在Yelp 上性能改進均大于Gowalla。由此可知，在數據稀疏度大于Gowalla 的Yelp 數據集上，PSC 能更有效地捕捉數據的多維空間特性，準確地定位用戶最近鄰。

圖9 PSC-SMLP and SMLP 的對比

6 結束語

LBSN 中豐富的上下文信息（簽到信息、社交信息）為充分學習用戶偏好，提高POI 推薦算法的準確率提供了機遇。然而將上下文信息直接融入到推薦模型中會引起數據維度增大，也將增加用戶和POI 非線性交互的挖掘難度。本文提出了一種新的POI 推薦算法PSC-SMLP。在圖模型基礎上提出了偏好增強的譜聚類算法PSC 進行用戶偏好上下文的挖掘，PSC 可從用戶偏好和社交偏好2 個方面捕捉用戶對POI 簽到的相似性，基于譜聚類的PSC 也能在多維數據構成的任意形狀空間中具有良好的空間識別能力。本文進一步構造了譜嵌入增強的神經網絡SMLP，譜嵌入層通過連通信息圖的譜對用戶群組和POI 進行譜映射，更好地捕捉用戶和POI之間的連通信息，從而獲得用戶和POI 的譜嵌入向量，構造的深層網絡結構和非線性激活函數基于譜嵌入層充分學習了用戶對POI 的偏好。在Gowalla和Yelp 這2個數據集中與傳統的協同過濾和復合模型算法進行了對比，在多個評價指標上，本文算法推薦性能更優。

更進一步的研究將考慮自注意力模型，從多個層次來捕獲用戶對不同POI 的關注度，以進一步提高推薦準確率。