張奧雅，石美惠，申德榮，寇 月，聶鐵錚

東北大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，沈陽 110819

隨著基于位置的社交網(wǎng)絡(luò)（location-based social network，LBSN）如Foursquare、Gowalla 的流行，用戶可以利用手機(jī)等移動設(shè)備來搜索興趣點(diǎn)，并在社交平臺上發(fā)布其簽到的興趣點(diǎn)，與朋友分享該興趣點(diǎn)的體驗(yàn)與感受。大量的簽到興趣點(diǎn)信息收集在LBSN 中，興趣點(diǎn)推薦是利用這些簽到信息，根據(jù)用戶歷史的移動行為來預(yù)測用戶的偏好，并向其推薦一組未訪問的興趣點(diǎn)。

近年來，興趣點(diǎn)推薦越來越受到人們的關(guān)注，而下一興趣點(diǎn)推薦成為興趣點(diǎn)推薦的一個新的研究熱點(diǎn)。下一興趣點(diǎn)推薦是根據(jù)用戶歷史訪問的興趣點(diǎn)，同時結(jié)合用戶當(dāng)前所訪問的興趣點(diǎn)信息，向用戶推薦下一時刻可能訪問的興趣點(diǎn)。與傳統(tǒng)的興趣點(diǎn)推薦不同，下一興趣點(diǎn)推薦考慮了用戶簽到興趣點(diǎn)的連續(xù)性以及用戶簽到興趣點(diǎn)之間的時序關(guān)系。一些較為成熟的下一興趣點(diǎn)推薦模型，如基于協(xié)同過濾的推薦模型[1]和基于馬爾可夫鏈的推薦模型[2]，只能捕獲相鄰興趣點(diǎn)之間的關(guān)系，使推薦的興趣點(diǎn)只與最近簽到的興趣點(diǎn)有關(guān)，忽略了用戶與興趣點(diǎn)的集體依賴。目前較為流行的基于深度學(xué)習(xí)的下一興趣點(diǎn)推薦模型[3-4]，考慮的影響因素比較單一，例如文獻(xiàn)[3]僅對時間演化進(jìn)行建模，文獻(xiàn)[4]采用GRU（gated recurrent unit）模型，只考慮了時間、空間上的連續(xù)性。針對下一興趣點(diǎn)推薦已有很多研究成果，但仍然難以取得滿意的推薦性能。

用戶在不同時間簽到的興趣點(diǎn)是不斷變化的，最近的一些研究嘗試?yán)糜绊懹脩艉炄氲男畔硖岣咄扑]的準(zhǔn)確性。雖然用戶在連續(xù)時間內(nèi)更傾向于訪問距離較近的興趣點(diǎn)，但并不是相鄰的興趣點(diǎn)之間的距離越近越好，如用戶在不同時間跨區(qū)域訪問興趣點(diǎn)。因此，需要捕獲某時刻興趣點(diǎn)的粗粒度信息，將某一時刻的區(qū)域信息嵌入到興趣點(diǎn)中能更加準(zhǔn)確地為用戶推薦下一興趣點(diǎn)。例如，隨著城市不斷擴(kuò)大，許多用戶工作地點(diǎn)與家距離較遠(yuǎn)，導(dǎo)致用戶的工作區(qū)域與生活區(qū)域不相同，僅僅依靠兩個興趣點(diǎn)之間的距離而不考慮區(qū)域這種粗粒度信息來進(jìn)行推薦，會導(dǎo)致推薦的興趣點(diǎn)只停留在工作區(qū)域或生活區(qū)域，這可能與用戶在不同時間段跨區(qū)域活動的需求不相符。因此，在對下一興趣點(diǎn)推薦時，應(yīng)該將每個時間段內(nèi)用戶所在的區(qū)域信息作為一個考慮因素。

眾所周知，LBSN 是一個可以提供位置信息的社交網(wǎng)絡(luò)，它可以讓用戶隨時隨地獲取經(jīng)緯度信息并與好友進(jìn)行分享。因此，用戶下一簽到的興趣點(diǎn)可能會受到用戶在LBSN 中的朋友（或稱為社交影響）的影響，朋友訪問興趣點(diǎn)信息可以在一定程度上彌補(bǔ)用戶訪問興趣點(diǎn)的數(shù)據(jù)稀疏這一問題。已有研究通過結(jié)合朋友評價信息來提升推薦準(zhǔn)確性，例如文獻(xiàn)[5]通過朋友的評論信息對用戶進(jìn)行推薦，但僅有少量用戶對興趣點(diǎn)產(chǎn)生評價。因此，這些研究仍存在數(shù)據(jù)稀疏性的問題。

可見，下一興趣點(diǎn)推薦還存在一定局限性。為此，本文采用殘差網(wǎng)絡(luò)模型研究不同簽入特征對用戶簽到興趣點(diǎn)的影響。一是將某一時刻興趣點(diǎn)的區(qū)域信息作為影響因素之一融入到用戶簽到興趣點(diǎn)序列中，進(jìn)一步改善數(shù)據(jù)稀疏問題，提高推薦準(zhǔn)確性。同時采用殘差網(wǎng)絡(luò)模型處理區(qū)域與用戶訪問的興趣點(diǎn)序列，使用殘差網(wǎng)絡(luò)中跳躍連接來不斷優(yōu)化模型，可有效降低訓(xùn)練模型的參數(shù)誤差，進(jìn)而提升興趣點(diǎn)推薦的準(zhǔn)確性。二是考慮社交網(wǎng)絡(luò)中朋友簽到興趣點(diǎn)對用戶的影響。已有研究大多是構(gòu)建位置信息和社交信息的異構(gòu)網(wǎng)絡(luò)，通過提取朋友評論信息來輔助用戶推薦，但仍存在一定局限性。本文融合朋友簽到的興趣點(diǎn)與用戶簽到的興趣點(diǎn)，可以有效擴(kuò)大用戶興趣點(diǎn)的推薦范圍，更好地解決數(shù)據(jù)稀疏問題。本文的主要貢獻(xiàn)如下：

（1）提出一種融合區(qū)域與朋友影響的下一興趣點(diǎn)推薦模型。引入不同時間段內(nèi)簽到興趣點(diǎn)所屬的區(qū)域，將某一時刻的興趣點(diǎn)和某一時刻的區(qū)域相結(jié)合，不僅可以改善數(shù)據(jù)稀疏問題，也可提升下一興趣點(diǎn)推薦的準(zhǔn)確性。同時將可信任的朋友簽到的興趣點(diǎn)與用戶簽到的興趣點(diǎn)進(jìn)行融合，進(jìn)一步提高用戶下一興趣點(diǎn)推薦的準(zhǔn)確性。

（2）提出一種殘差連接的結(jié)構(gòu)對興趣點(diǎn)序列進(jìn)行訓(xùn)練。通過跳躍連接構(gòu)建殘差塊，改善梯度消失和網(wǎng)絡(luò)退化的問題，提升模型的準(zhǔn)確性。

（3）通過對比實(shí)驗(yàn)，證明本文提出的模型的準(zhǔn)確性明顯優(yōu)于其他推薦模型。

1 相關(guān)工作

1.1 基于傳統(tǒng)算法的下一興趣點(diǎn)推薦

傳統(tǒng)的下一興趣點(diǎn)推薦算法主要包括協(xié)同過濾推薦、基于馬爾可夫鏈的興趣點(diǎn)推薦。

協(xié)同過濾（collaborative filtering）是比較成熟的興趣點(diǎn)推薦算法。已有的基于模型的協(xié)同過濾算法[1]，是從用戶簽到興趣點(diǎn)信息中分析用戶對興趣點(diǎn)的偏好。然而，協(xié)同過濾算法將用戶訪問的興趣點(diǎn)都考慮在一個整體中，忽略了訪問興趣點(diǎn)之間的作用。

基于馬爾可夫鏈的興趣點(diǎn)推薦算法是傳統(tǒng)下一興趣點(diǎn)推薦算法中最常見的方法之一?；隈R爾可夫鏈的推薦算法主要分為基于加性馬爾可夫鏈的算法和基于隱馬爾可夫鏈嵌入的算法。Zhang 等人[2]提出采用加性馬爾可夫鏈算法，考慮了序列對興趣點(diǎn)推薦的影響，通過挖掘序列模式將興趣點(diǎn)序列轉(zhuǎn)化成動態(tài)位置轉(zhuǎn)換圖，從而預(yù)測用戶訪問興趣點(diǎn)的概率。而Feng 等人[6]提出使用馬爾可夫鏈將興趣點(diǎn)嵌入到歐幾里德空間中，根據(jù)興趣點(diǎn)之間的歐幾里德距離計算興趣點(diǎn)之間的轉(zhuǎn)移概率?；隈R爾可夫鏈的下一興趣點(diǎn)推薦系統(tǒng)的缺點(diǎn)是顯而易見的，因?yàn)轳R爾可夫鏈的屬性是假定當(dāng)前的交互僅依賴于一個或幾個最近的交互，所以它們只能捕獲相鄰的興趣點(diǎn)之間的關(guān)系，而忽略了之前訪問的興趣點(diǎn)對其產(chǎn)生的影響。這說明它只能捕獲興趣點(diǎn)與興趣點(diǎn)之間的依賴，而忽略了用戶與興趣點(diǎn)交互的集體依賴。

1.2 基于深度學(xué)習(xí)的下一興趣點(diǎn)推薦

大多數(shù)對下一興趣點(diǎn)推薦的研究主要采用深度學(xué)習(xí)的模型建立用戶與興趣點(diǎn)之間的關(guān)系。最常用的是遞歸神經(jīng)網(wǎng)絡(luò)（recursive neural network，RNN），它不規(guī)定訪問興趣點(diǎn)的數(shù)量。例如，Mikolov 等人[7]提出使用遞歸連接，考慮訪問興趣點(diǎn)之間的影響；Liu等人[8]采用RNN，通過用戶歷史訪問興趣點(diǎn)序列來預(yù)測下一個可能訪問的興趣點(diǎn)。然而，僅僅使用RNN捕獲歷史訪問興趣點(diǎn)之間的關(guān)系是困難的，因此除了基本RNN 外，目前比較流行的是使用RNN 的變形,即LSTM（long short-term memory）、GRU。例如，Xu等人[9]通過忘記門、輸入門、輸出門來捕獲長短期記憶?；赗NN 的方法還處于早期階段，沒有強(qiáng)調(diào)歷史訪問信息對用戶當(dāng)前訪問興趣點(diǎn)的影響，為此Wang 等人[10]使用基于門控電流單位的RNN（GRU），捕獲序列中的長期依賴性。

1.3 基于社交和區(qū)域化的下一興趣點(diǎn)推薦

最近，下一興趣點(diǎn)推薦問題也考慮了其他影響因素，如基于社交關(guān)系的朋友推薦和基于區(qū)域化的推薦。其中興趣點(diǎn)推薦可以讓用戶簽到一個興趣點(diǎn)時能夠滿足其特定的需求。然而在LBSN 中，用戶訪問的興趣點(diǎn)數(shù)據(jù)是比較稀疏的，無法準(zhǔn)確地獲取從未簽到過的興趣點(diǎn)。為了使數(shù)據(jù)更加準(zhǔn)確，Ye等人[11]提出通過社交關(guān)系來提高興趣點(diǎn)推薦方法的準(zhǔn)確性。目前已有的興趣點(diǎn)推薦模型大多采用不同的顯性社會關(guān)系。例如，Xu 等人[12]提出的模型是采用LBSN 進(jìn)行推薦；Zhao 等人[5]提出使用異構(gòu)網(wǎng)絡(luò)對興趣點(diǎn)進(jìn)行推薦，將基于社區(qū)的社交網(wǎng)絡(luò)與基于地理位置的社交網(wǎng)絡(luò)相結(jié)合?？紤]到朋友之間的隱性關(guān)系也對用戶有很大的影響，Pan 等人[13]提出隱性朋友和顯性朋友對用戶訪問興趣點(diǎn)的影響。

最近的許多研究表明，用戶簽到興趣點(diǎn)和興趣點(diǎn)之間的距離存在密切的聯(lián)系，因此大多數(shù)下一興趣點(diǎn)推薦模型主要通過利用地理影響來提高推薦的準(zhǔn)確性。例如，Xiong 等人[14]將區(qū)域聚集成環(huán)形，但這種方法很難發(fā)現(xiàn)區(qū)域的中心興趣點(diǎn)。考慮到用戶訪問的興趣點(diǎn)可能受到鄰近區(qū)域影響，F(xiàn)eng 等人[15]使用建立二叉樹的方法將一個興趣點(diǎn)分配給多個區(qū)域，通過個人興趣和人群偏好等因素，結(jié)合區(qū)域信息對用戶簽到興趣點(diǎn)進(jìn)行推薦。

不同于已有模型，本文提出結(jié)合朋友訪問的興趣點(diǎn)以及興趣點(diǎn)所屬區(qū)域?qū)τ脩舻挠绊懀瑢^(qū)域信息嵌入到用戶簽到興趣點(diǎn)序列中，采用殘差網(wǎng)絡(luò)進(jìn)行訓(xùn)練。同時將朋友訪問的興趣點(diǎn)與其進(jìn)行融合，以提高對下一興趣點(diǎn)推薦的準(zhǔn)確性。

2 問題描述與相關(guān)定義

本章首先將興趣點(diǎn)推薦問題形式化，然后介紹重要的定義和符號。

問題描述：給定一個包含朋友關(guān)系的基于地理位置的社交網(wǎng)絡(luò)的數(shù)據(jù)集（Foursquare、Gowalla），其中包含興趣點(diǎn)（point of interest，POI）的位置和所有相關(guān)用戶的社交信息。POI預(yù)測的目標(biāo)是給目標(biāo)用戶u推薦可能訪問的POI列表。

為了便于理解，表1 描述了本文使用的重要符號。同時為了便于描述本文提出的方法，這里先給出一些相關(guān)定義。

定義1（朋友）在社交網(wǎng)絡(luò)中，每個用戶可有多個朋友，而每個用戶還可能有多種角色，用戶與朋友之間的聯(lián)系代表他們之間的交流。本文中朋友由F表示。

Table 1 Notations used in this paper表1 本文中的符號

定義2（區(qū)域）區(qū)域是指根據(jù)用戶訪問的地理位置，按照一定的范圍進(jìn)行聚類。本文認(rèn)為一個區(qū)域內(nèi)的興趣點(diǎn)有很高的密度，但是區(qū)域與區(qū)域之間的關(guān)系比較稀疏。本文中區(qū)域由R表示。

定義3（興趣點(diǎn)）興趣點(diǎn)是用戶訪問一個地點(diǎn)的唯一標(biāo)識（例如公園、健身房等）。在本文提出的模型中興趣點(diǎn)由兩個特征表示，即興趣點(diǎn)編號和興趣點(diǎn)的地理位置（由經(jīng)度、緯度表示）。本文中興趣點(diǎn)由P表示。

概念1（殘差網(wǎng)絡(luò)）如圖1 所示，殘差網(wǎng)絡(luò)是堆積層結(jié)構(gòu)，identityx代表恒等映射輸入向量x。當(dāng)輸入為x時，其學(xué)習(xí)到的特征記為H(x)，可以學(xué)習(xí)到殘差F(x)=H(x)-x。其實(shí)原始的學(xué)習(xí)特征是F(x)+x，當(dāng)殘差為0 時，此時堆積層做了恒等映射，至少網(wǎng)絡(luò)性能不會下降。而實(shí)際上殘差不會為0，因此殘差網(wǎng)絡(luò)直接將輸入信息繞道傳到輸出，以保證信息的完整性。采用殘差網(wǎng)絡(luò)在反向傳播過程中，梯度連乘，不會造成梯度消失[16]。

Fig.1 Residual block of residual network圖1 殘差網(wǎng)絡(luò)的殘差塊

在深度神經(jīng)網(wǎng)絡(luò)訓(xùn)練中，隨著網(wǎng)絡(luò)層次的增加，理論上可以取得更好的結(jié)果。但是實(shí)驗(yàn)卻發(fā)現(xiàn)殘差網(wǎng)絡(luò)中的一個新的思想[17]，通過冗余層完成恒等映射，保證輸入向量經(jīng)過恒等層時保持不變。殘差網(wǎng)絡(luò)在網(wǎng)絡(luò)訓(xùn)練時自己可以判斷哪些是恒等層。

3 融合區(qū)域與朋友影響的下一興趣點(diǎn)推薦

下一興趣點(diǎn)推薦與一般的推薦任務(wù)（如商品、電影、新聞推薦）不同，因?yàn)橄乱慌d趣點(diǎn)推薦具有高度的時空依賴性，所以人們在現(xiàn)實(shí)生活中更傾向于訪問時空距離較近的，如近期訪問過的且距離較近的電影院、餐館等。這說明用戶更傾向于訪問自己熟悉的且距離自己較近的興趣點(diǎn)。然而用戶對興趣點(diǎn)的選擇是一個復(fù)雜的過程，往往受到眾多因素的影響，其中社交因素和地理因素是最重要的兩個因素。地理因素顯著影響用戶的移動行為，可以有效地提高推薦質(zhì)量，而社交關(guān)系可以通過朋友簽到的興趣點(diǎn)彌補(bǔ)數(shù)據(jù)稀疏性。

本文主要通過將不同的影響因素與用戶簽到序列相結(jié)合，以提高推薦的準(zhǔn)確性。本文認(rèn)為用戶簽到下一興趣點(diǎn)不僅與其自身相關(guān)，朋友相互之間的影響、區(qū)域的變化也是其選擇的考慮因素。因此，從社交網(wǎng)絡(luò)中朋友關(guān)系以及在不同時間段內(nèi)用戶所在的區(qū)域入手，提出融合朋友與區(qū)域信息的下一興趣點(diǎn)推薦模型。如圖2 所示，融合朋友與區(qū)域信息的下一興趣點(diǎn)推薦模型主要由殘差網(wǎng)絡(luò)訓(xùn)練區(qū)域與用戶簽到興趣點(diǎn)序列、朋友訪問中心興趣點(diǎn)、融合朋友與區(qū)域影響的下一興趣點(diǎn)推薦三部分組成?；谇叭说难芯拷Y(jié)果，根據(jù)用戶簽到興趣點(diǎn)的特征以及用戶簽到序列來選擇合適的主題模型，對用戶下一簽到的興趣點(diǎn)進(jìn)行推薦。

3.1 殘差網(wǎng)絡(luò)訓(xùn)練區(qū)域與用戶簽到興趣點(diǎn)序列

殘差網(wǎng)絡(luò)訓(xùn)練區(qū)域與用戶簽到興趣點(diǎn)序列，主要由用戶訪問興趣點(diǎn)所屬區(qū)域以及將區(qū)域與興趣點(diǎn)嵌入到殘差網(wǎng)絡(luò)中兩部分組成。接下來，將分別介紹這兩部分。

3.1.1 用戶訪問興趣點(diǎn)的區(qū)域

Fig.2 Next POI recommendation model which integrates influence of regions and friends圖2 結(jié)合朋友與區(qū)域信息的下一興趣點(diǎn)推薦模型

用戶訪問的興趣點(diǎn)不僅與興趣點(diǎn)之間的距離有關(guān)，與區(qū)域也是有關(guān)的，因此區(qū)域也應(yīng)該作為興趣點(diǎn)推薦時考慮的因素之一。目前大多數(shù)的工作雖然考慮到了用戶在連續(xù)訪問不同興趣點(diǎn)時距離的影響，但也僅僅停留在相鄰兩個興趣點(diǎn)的距離計算上。因?yàn)橛脩粼诓煌瑫r間段訪問的區(qū)域不同，所以確定用戶屬于哪一區(qū)域并根據(jù)區(qū)域進(jìn)行推薦可以提高準(zhǔn)確性。該方法假設(shè)大多數(shù)人的日常生活是有規(guī)律的，并且他們的偏好在一定時期內(nèi)很少改變，因此日?；顒拥姆秶鷮⒕窒抻趲讉€相對較小的區(qū)域。如圖3所示為用戶訪問興趣點(diǎn)的區(qū)域（R1、R2、R3）劃分，用戶在短時間內(nèi)訪問的興趣點(diǎn)主要集中在同一區(qū)域。

Fig.3 Region division of user check-ins圖3 用戶訪問興趣點(diǎn)的區(qū)域劃分

區(qū)域是影響用戶訪問的興趣點(diǎn)序列和用戶偏好的一個重要因素，而現(xiàn)有的基于頻率的softmax 結(jié)構(gòu)不能捕捉到興趣點(diǎn)所屬的區(qū)域。因此本文采用聚類算法，將用戶歷史訪問的興趣點(diǎn)進(jìn)行聚類，劃分出區(qū)域。區(qū)域劃分算法見算法1。

算法1區(qū)域劃分

輸入：用戶訪問的興趣點(diǎn)。

輸出：區(qū)域R，n代表區(qū)域的個數(shù)。

1.創(chuàng)建K個作為起始區(qū)域的中心興趣點(diǎn)xj（隨機(jī)選擇）

2.當(dāng)任意的區(qū)域R分配結(jié)果發(fā)生改變時

3. 訪問數(shù)據(jù)集中的

4. 對每個區(qū)域R的中心興趣點(diǎn)xj

5.dist=xj-

6. 將興趣點(diǎn)分配到距其最近的區(qū)域R

7. 對每一個區(qū)域R

8. 求出均值并將其更新為區(qū)域的中心興趣點(diǎn)xj

通過歐幾里德距離算法，計算用戶歷史訪問的興趣點(diǎn)屬于哪一區(qū)域，根據(jù)每個區(qū)域的中心點(diǎn)，計算用戶在該時刻簽到的興趣點(diǎn)與每個區(qū)域的中心興趣點(diǎn)的距離。選取距離最小的為該興趣點(diǎn)所屬的區(qū)域。興趣點(diǎn)與區(qū)域中心點(diǎn)的距離計算公式如下：

其中，代表用戶u在某一時刻訪問的興趣點(diǎn)，xj代表區(qū)域的中心興趣點(diǎn)。

3.1.2 區(qū)域與興趣點(diǎn)嵌入殘差網(wǎng)絡(luò)

本部分研究的目的是綜合考慮用戶下一簽到興趣點(diǎn)受到上一興趣點(diǎn)以及區(qū)域的影響因素。首先尋找目標(biāo)用戶的連續(xù)簽到序列，然后根據(jù)目標(biāo)用戶的連續(xù)簽到序列和用戶訪問興趣點(diǎn)的區(qū)域，共同構(gòu)建區(qū)域與用戶訪問興趣點(diǎn)嵌入的模式序列，并采用殘差網(wǎng)絡(luò)進(jìn)行訓(xùn)練。例如，采用殘差網(wǎng)絡(luò)訓(xùn)練模型時將一個用戶訪問的n個興趣點(diǎn)以及嵌入的區(qū)域構(gòu)建一組序列，具體使用殘差連接對序列進(jìn)行訓(xùn)練，過程如圖4 所示，其中圓點(diǎn)代表區(qū)域與用戶訪問興趣點(diǎn)的嵌入序列，虛線塊代表構(gòu)建的殘差塊。

Fig.4 Residual connection based check-in sequence圖4 基于殘差連接的簽到序列

殘差網(wǎng)絡(luò)方法是在用戶訪問的興趣點(diǎn)序列上增加跳躍連接，每兩層增加一個捷徑，構(gòu)成一個殘差塊，如圖4 所示，由3 個殘差塊連接在一起構(gòu)成一個殘差網(wǎng)絡(luò)。在處理用戶訪問興趣點(diǎn)的時候，不僅與自身興趣點(diǎn)有關(guān)，還與上一興趣點(diǎn)甚至更早的興趣點(diǎn)有關(guān)，因此需要用殘差網(wǎng)絡(luò)處理梯度消失問題。主要采取的算法是該用戶在這一時刻簽到的興趣點(diǎn)以及區(qū)域H(x)=x，即輸入是x，經(jīng)過該冗余層后，輸出仍然為x（如圖4 中的第一個虛線塊所示）。但要想學(xué)習(xí)H(x)=x恒等映射時的這層參數(shù)是比較困難的。殘差網(wǎng)絡(luò)能夠采用跳躍連接避免去學(xué)習(xí)該層恒等映射的參數(shù)，讓H(x)=F(x)+x，這里F(x)稱作殘差項，學(xué)習(xí)F(x)比學(xué)習(xí)H(x)簡單，因?yàn)橐话忝繉泳W(wǎng)絡(luò)中的參數(shù)初始化偏向于0，這樣更新該網(wǎng)絡(luò)層的參數(shù)來學(xué)習(xí)H(x)=x，該冗余層學(xué)習(xí)F(x)=0 的更新參數(shù)能夠更快收斂。一個殘差單元的公式如下：

其中，y和x均為殘差塊所在層的輸入與輸出向量，函數(shù)F(x,wi)為訓(xùn)練殘差映射所學(xué)習(xí)到的每個殘差塊。

采用殘差網(wǎng)絡(luò)訓(xùn)練區(qū)域與用戶簽到興趣點(diǎn)構(gòu)建的序列公式如下：

其中，PT代表用戶推薦的下一時刻的訪問興趣點(diǎn)，PR代表區(qū)域向量，Pt代表用戶某一時刻訪問的興趣點(diǎn)向量。

3.2 朋友訪問中心興趣點(diǎn)

本文考慮到朋友對用戶訪問興趣點(diǎn)是有影響的，因此將用戶的多個朋友訪問多個興趣點(diǎn)進(jìn)行向量融合，即計算多個朋友在多個時間訪問興趣點(diǎn)的中心點(diǎn)。由于朋友訪問興趣點(diǎn)可能存在偶然性，如出差這種情況，會導(dǎo)致數(shù)據(jù)比較分散，求出的朋友訪問的中心點(diǎn)不準(zhǔn)確。因此本文設(shè)定一個閾值，只考慮一定范圍內(nèi)朋友訪問的興趣點(diǎn)。多個朋友訪問興趣點(diǎn)融合公式如下：

其中，代表用戶u所有朋友訪問興趣點(diǎn)的中心興趣點(diǎn)，代表用戶u的一個朋友訪問的興趣點(diǎn)，通過數(shù)據(jù)預(yù)處理得到其朋友訪問的興趣點(diǎn)。

3.3 融合朋友與區(qū)域影響的下一興趣點(diǎn)推薦

為了捕捉用戶u訪問興趣點(diǎn)的區(qū)域和朋友影響，將殘差網(wǎng)絡(luò)處理區(qū)域與用戶訪問興趣點(diǎn)序列的輸出和朋友訪問中心興趣點(diǎn)向量連接在一起。如圖5 所示，采用殘差網(wǎng)絡(luò)將區(qū)域向量嵌入到用戶歷史簽到興趣點(diǎn)序列中，與朋友訪問興趣點(diǎn)向量進(jìn)行拼接。

Fig.5 Next POI recommendation:fusing region factor and friends'information圖5 融合區(qū)域、朋友信息的下一興趣點(diǎn)推薦

融合朋友與區(qū)域影響的興趣點(diǎn)推薦公式如下：

其中，w′和b′分別是輸出層的權(quán)重矩陣和偏差項。PT代表融合區(qū)域后用戶推薦的下一時刻的訪問興趣點(diǎn)，代表用戶u所有朋友訪問興趣點(diǎn)的中心興趣點(diǎn)，代表融合朋友與區(qū)域影響的下一興趣點(diǎn)推薦。

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

本章展示了所提出的融合區(qū)域與朋友影響的下一興趣點(diǎn)推薦模型的實(shí)驗(yàn)結(jié)果，通過與最新工作比較來評估本文提出的模型（Proposed）的有效性。

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

本文在兩個數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)以驗(yàn)證模型的可行性，其中所使用的數(shù)據(jù)集為興趣點(diǎn)推薦研究常用的數(shù)據(jù)集，分別為Foursquare、Gowalla 數(shù)據(jù)集，在這兩個數(shù)據(jù)集上進(jìn)行預(yù)處理，具體見表2。

Table 2 Statistics of datasets表2 數(shù)據(jù)集統(tǒng)計

Foursquare 數(shù)據(jù)集：Foursquare 社交網(wǎng)絡(luò)可以提供許多基于位置的信息，例如興趣點(diǎn)登記。該數(shù)據(jù)集來自美國加利福尼亞州舊金山地區(qū)的4 163 名用戶，包括身份、姓名、登記時間和經(jīng)緯度信息。

Gowalla 數(shù)據(jù)集：Gowalla 是一個典型的LBSN，用戶可以隨時共享其位置信息。簽到數(shù)據(jù)由簽到時間、地點(diǎn)、用戶ID 和用戶的社會關(guān)系構(gòu)成。數(shù)據(jù)收集了用戶在2009 年2 月至2010 年10 月期間6 442 890次簽到信息。

4.2 對比實(shí)驗(yàn)

為了驗(yàn)證本文提出的推薦模型的可行性，設(shè)置了一些對比實(shí)驗(yàn)，所要對比的流行算法如下：

LORE[2]：提出采用挖掘序列模式的模型。將用戶訪問的興趣點(diǎn)表示為動態(tài)位置轉(zhuǎn)換圖，并采用馬爾可夫鏈預(yù)測用戶訪問興趣點(diǎn)的概率，同時將地理影響和社會影響融合到一個統(tǒng)一的推薦框架中。

PRME[6]：提出一種個性化的等級度量嵌入方法。采用度量嵌入的方法進(jìn)行推薦，結(jié)合了興趣點(diǎn)序列、用戶偏好和地理影響。

RNN[8]：提出距離偏好對下一個POI 的影響。將用戶的順序偏好和連續(xù)興趣點(diǎn)之間的距離通過RNN模型進(jìn)行訓(xùn)練，通過融合空間偏好和順序偏好對下一興趣點(diǎn)進(jìn)行推薦。

POI2Vec[15]：提出結(jié)合地理因素影響的潛在表示模型?？紤]用戶的個人偏好和簽到興趣點(diǎn)序列順序的影響，給潛在的用戶推薦興趣點(diǎn)。

FPMC[18]：提出一個矩陣分解和馬爾可夫鏈相結(jié)合的模型。每一個用戶對應(yīng)一個轉(zhuǎn)移矩陣，同時引入個性化排序的框架來處理簽到數(shù)據(jù)。

Proposed：本文提出的融合區(qū)域與朋友關(guān)系的用戶下一興趣點(diǎn)推薦模型，采用殘差網(wǎng)絡(luò)模型將用戶簽到興趣點(diǎn)的信息與興趣點(diǎn)所屬區(qū)域信息進(jìn)行嵌入訓(xùn)練，避免網(wǎng)絡(luò)退化。通過融合朋友信息，緩解數(shù)據(jù)稀疏性，提高推薦的準(zhǔn)確性。

4.3 評價標(biāo)準(zhǔn)

本文研究的關(guān)鍵問題是如何準(zhǔn)確地給目標(biāo)用戶推薦下一時刻訪問的興趣點(diǎn)。本文使用準(zhǔn)確率（Precision）、召回率（Recall）來檢查和驗(yàn)證融合區(qū)域與朋友影響的用戶訪問興趣點(diǎn)模型的有效性，其定義如下所示，分別為：

4.4 結(jié)果與分析

4.4.1 本文模型的測試結(jié)果

本實(shí)驗(yàn)在兩個數(shù)據(jù)集上測試本文模型的準(zhǔn)確率、召回率得分，表3 展示了本文模型在Top5、Top10、Top15、Top20、Top25 時的準(zhǔn)確率、召回率的實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)中，通過80%、10%、10%劃分?jǐn)?shù)據(jù)集，并進(jìn)行反復(fù)實(shí)驗(yàn)。采用的殘差網(wǎng)絡(luò)一共24 層，每一層卷積核數(shù)量為24，卷積核大小為8。

4.4.2 與基線模型對比與分析

本實(shí)驗(yàn)選取當(dāng)基線模型具有自己最佳表現(xiàn)時采用的參數(shù)值，分別在Foursquare 和Gowalla 數(shù)據(jù)集上，測試了本文模型和基線模型的推薦準(zhǔn)確率和召回率，對比結(jié)果見圖6、圖7 和圖8、圖9。

測試結(jié)果如下：

（1）從圖6 和圖8 中可以看到，F(xiàn)PMC 的各項推薦表現(xiàn)都是最差的，并且圖7、圖9 也顯示FPMC 的召回率得分也是最差的。這是因?yàn)镕PMC 方法只關(guān)注于從用戶的簽到歷史數(shù)據(jù)中挖掘用戶的偏好信息，而沒有考慮任何用戶簽到興趣點(diǎn)的影響因素。

（2）PRME 和POI2Vec 這兩種模型的實(shí)驗(yàn)結(jié)果都略好于FPMC 方法。這是因?yàn)檫@兩種方法分別結(jié)合了地理信息和個人偏好信息。其中PRME 將個人偏好和地理影響嵌入到基于成對排序度量框架中。而POI2Vec 結(jié)合興趣點(diǎn)地理坐標(biāo)構(gòu)建二叉樹的方法，將興趣點(diǎn)分到不同的區(qū)域中，在每個區(qū)域的興趣點(diǎn)上構(gòu)建一個二叉樹。通過這兩種方法驗(yàn)證了影響因素對興趣點(diǎn)推薦是有效的。

Table 3 Accuracy and recall of proposed model表3 本文模型的準(zhǔn)確率、召回率

Fig.7 Comparison of recall on Foursquare圖7 在Foursquare數(shù)據(jù)集上的召回率對比

Fig.8 Comparison of accuracy on Gowalla圖8 在Gowalla 數(shù)據(jù)集上的準(zhǔn)確率對比

（3）LORE 表現(xiàn)出了較好的推薦性能。LORE 采用馬爾可夫鏈給用戶推薦一個最可能訪問的興趣點(diǎn)，并將訪問興趣點(diǎn)之間的順序、地理影響和社交關(guān)系融合到一個統(tǒng)一的推薦框架中。LORE 的實(shí)驗(yàn)數(shù)據(jù)表明社交關(guān)系對下一個興趣點(diǎn)推薦起到重要作用，同時也說明了馬爾可夫鏈對下一個興趣點(diǎn)推薦的有效性。但LORE 在推薦下一個興趣點(diǎn)時沒有將待推薦的興趣點(diǎn)限制在一個局部區(qū)域內(nèi)，這也是限制其推薦性能的一個因素。

（4）RNN 通過對給定的興趣點(diǎn)順序依賴性和空間偏好建模來推薦下一個可能訪問的興趣點(diǎn)。從表3中可以觀察到RNN 對下一興趣點(diǎn)推薦的準(zhǔn)確率較低，這說明隨著連續(xù)訪問興趣點(diǎn)的數(shù)量增多，采用深度學(xué)習(xí)框架存在梯度消失和退化的問題。

Fig.9 Comparison of recall on Gowalla圖9 在Gowalla 數(shù)據(jù)集上的召回率對比

總體上，本文模型在準(zhǔn)確率、召回率得分方面的性能始終優(yōu)于基線模型，主要是將區(qū)域與朋友影響有效地集成到統(tǒng)一的推薦過程當(dāng)中，并考慮訪問興趣點(diǎn)的先后順序。通過綜合興趣點(diǎn)所屬區(qū)域，將區(qū)域信息與用戶簽到興趣點(diǎn)序列進(jìn)行嵌入，捕獲粗粒度信息動態(tài)地預(yù)測用戶的偏好。同時將朋友簽到興趣點(diǎn)與嵌入?yún)^(qū)域的用戶簽到興趣點(diǎn)進(jìn)行融合，克服了簽到數(shù)據(jù)稀疏的問題。同時本文采用了殘差網(wǎng)絡(luò)，通過增加跳躍連接層構(gòu)成殘差塊[17]，將輸入信息繞道傳到輸出，保證信息的完整性。同時在反向傳播過程中，梯度連乘，不會造成梯度消失[16]，因此它不會像RNN 隨著網(wǎng)路層次的加深，而發(fā)生準(zhǔn)確率下降的問題。

4.4.3 不同用戶序列窗口長度的影響

用戶序列窗口長度是融合區(qū)域和朋友影響的用戶訪問興趣點(diǎn)模型的重要因素，本文在兩個數(shù)據(jù)集上設(shè)置不同長度的用戶序列窗口進(jìn)行實(shí)驗(yàn)。表4 說明了在用戶序列不同長度窗口下評估本文推薦模型的準(zhǔn)確性。在Foursquare 數(shù)據(jù)集上，可以觀察到，當(dāng)用戶序列長度為25，取Top20 時，模型獲得了最佳的預(yù)測性能。在Gowalla 數(shù)據(jù)集上，當(dāng)用戶序列長度為10，取Top20 時，模型獲得了最佳的預(yù)測性能。同時觀察到，即使用戶序列的長度不是最佳的，本文模型的性能也優(yōu)于最先進(jìn)的模型。

Table 4 Influence of window length of check-in sequence on model accuracy表4 訪問序列的窗口長度對模型準(zhǔn)確性的影響

4.4.4 本文方法中不同因素的影響

本文在用戶簽到興趣點(diǎn)序列中嵌入了區(qū)域信息和朋友簽到興趣點(diǎn)信息，為了評估這兩種嵌入信息的性能，本小節(jié)將本文模型和只考慮區(qū)域信息或只考慮朋友信息的模型在用戶序列窗口長度為10，取Top5時的性能進(jìn)行了比較。如圖10 所示，在Foursquare數(shù)據(jù)集上，本文模型分別與只考慮區(qū)域信息的模型和只考慮朋友信息的模型進(jìn)行比較，本文模型在準(zhǔn)確度上分別提高了0.131 和0.074。在Gowalla數(shù)據(jù)集上，本文模型在準(zhǔn)確度上分別提高了0.083 和0.042?？梢?，融合區(qū)域或朋友信息都提高了推薦的準(zhǔn)確性。

Fig.10 Influence of different factors on performance of proposed model圖10 不同的因素對本文模型性能的影響

5 結(jié)束語

本文提出了融合區(qū)域與朋友影響的用戶訪問興趣點(diǎn)的推薦模型。該模型充分利用了殘差網(wǎng)絡(luò)避免網(wǎng)絡(luò)退化的問題來進(jìn)行序列推薦。利用區(qū)域影響因素捕獲粗粒度信息，同時利用朋友訪問興趣點(diǎn)的信息避免數(shù)據(jù)的稀疏性。在兩個真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文提出的模型在推薦準(zhǔn)確性上明顯優(yōu)于其他對比模型。接下來，會進(jìn)一步圍繞上述兩種影響因素對用戶簽到興趣點(diǎn)的影響進(jìn)行研究，爭取獲得更深層次的發(fā)現(xiàn)。