楊曉蕾，李 勝，何熊熊，劉桂云

(浙江工業(yè)大學(xué) 信息工程學(xué)院， 杭州 310023)

E-mail:alleny_29@qq.com

1 引 言

近些年來，通信網(wǎng)絡(luò)發(fā)展飛速，移動(dòng)設(shè)備隨之普及，網(wǎng)絡(luò)社交平臺(tái)受到大眾青睞，人們可以方便地在例如微博，F(xiàn)oursquare， Instagram等平臺(tái)上交友互動(dòng)，與大家分享有趣的經(jīng)歷，這一類平臺(tái)統(tǒng)稱為基于地理位置的社交網(wǎng)絡(luò)(Location Based social networks，LBSN).用戶訪問自己感興趣的興趣點(diǎn)(Point-of-Interest，POI如：影院，健身房等)，并通過移動(dòng)設(shè)備定位發(fā)布在網(wǎng)絡(luò)上，從而產(chǎn)生了大量的用戶簽到信息.這些簽到信息中包含了許多具有挖掘價(jià)值的內(nèi)容，如：簽到時(shí)間、地點(diǎn)經(jīng)緯度、POI類別等.利用這些數(shù)據(jù)做個(gè)性化POI推薦的系統(tǒng)應(yīng)運(yùn)而生，此類系統(tǒng)不僅可以為用戶省去繁復(fù)查詢的時(shí)間，還可以幫助商家完善已有興趣點(diǎn)的服務(wù)或發(fā)掘新的興趣點(diǎn)進(jìn)行商鋪選址[1]，進(jìn)而帶來更好的經(jīng)濟(jì)效益.盡管個(gè)性化POI推薦系統(tǒng)能帶來許多便利和商機(jī)，但它也面臨著許多挑戰(zhàn).

首先，由于POI地點(diǎn)的數(shù)量巨大，用戶的簽到信息中包含的地點(diǎn)數(shù)量遠(yuǎn)遠(yuǎn)少于POI總數(shù)，特別是有一些POI地點(diǎn)尚未被人們發(fā)掘，因此簽到數(shù)據(jù)十分稀疏[2]，這將導(dǎo)致度量相似性時(shí)出現(xiàn)較大的誤差，影響推薦準(zhǔn)確率.其次，用戶的簽到信息只展示了用戶去過一些POI這一現(xiàn)實(shí)情況，但并沒有直接給出用戶對(duì)訪問過的POI的偏好.由于簽到信息只提供隱式反饋的性質(zhì)，從用戶角度來看，推薦系統(tǒng)需要分析用戶的簽到頻率和影響因素，利用用戶相似性預(yù)測(cè)用戶的偏好，推送符合偏好的興趣點(diǎn)；從興趣點(diǎn)方面出發(fā)，系統(tǒng)利用地理-社會(huì)-評(píng)論關(guān)系構(gòu)造POI相關(guān)度矩陣并聚類，得到具有興趣點(diǎn)本身代表性的推薦列表[3].

值得注意的是，一個(gè)人決定出行的過程是非常復(fù)雜的，受到很多因素影響，主要包括：

1)地理因素，Li等人[4]分析簽到信息發(fā)現(xiàn)，POI的訪問頻率通常與用戶離“常駐地”的距離成冪律分布，人們?cè)诳紤]交通便利程度和路程遠(yuǎn)近的因素后，往往會(huì)選擇離居住地較近的POI.

2)社會(huì)因素，文獻(xiàn)[5]中提到朋友之間會(huì)有相似的興趣愛好，并且朋友對(duì)POI美好的描述使得這些POI更具有吸引力，人們更傾向于選擇朋友分享過的POI.

3)時(shí)間因素，文獻(xiàn)[6，7]中研究發(fā)現(xiàn)，人們的出行規(guī)律與時(shí)間相關(guān)，他們會(huì)在特定的時(shí)間段去到特定的地點(diǎn)，比如，中午的時(shí)候，人們會(huì)去餐廳，在晚上大家則會(huì)選擇酒吧之類的地點(diǎn).

4)類別因素，Chen等人[8]提出POI類別對(duì)人們的選擇頗有影響.不同的人喜歡訪問不同種類的POI，例如，有些人愛好美食，經(jīng)常在不同的餐廳打卡，而有的人喜歡運(yùn)動(dòng)健身，他們更偏向去健身房、操場之類的地點(diǎn)進(jìn)行鍛煉.

5)地點(diǎn)流行度，一個(gè)區(qū)域的POI如果被人們簽到過多次，表明至少它在當(dāng)?shù)胤浅Ｊ苋藗儦g迎.本地用戶的頻繁訪問為該地點(diǎn)增添了熱度和知名度，這種流行現(xiàn)象直接影響異地的用戶的出行計(jì)劃，他們可能會(huì)慕名而來[9].文獻(xiàn)[10]將地理位置融入核密度估計(jì)基礎(chǔ)上，再結(jié)合興趣點(diǎn)流行度特征和時(shí)間因素推薦，考慮了用戶自身個(gè)性特征的同時(shí)體現(xiàn)了興趣點(diǎn)的特征.由于目前大部分的研究只考慮到以上兩種或三種影響因素，影響因素利用不夠全面可能導(dǎo)致推薦準(zhǔn)確率難以進(jìn)一步提高.

除了以上提到的多種因素影響外，推薦系統(tǒng)仍存在用戶/地點(diǎn)冷啟動(dòng)問題，即當(dāng)一個(gè)沒有簽到記錄的新用戶或者一個(gè)新的POI進(jìn)入系統(tǒng)時(shí)，系統(tǒng)無法得到它們的歷史記錄信息，就無法利用相似性進(jìn)行推薦.

2 相關(guān)工作

最初經(jīng)典的推薦算法是基于用戶/地點(diǎn)的協(xié)同過濾[11，12]，利用用戶/地理位置相似性預(yù)測(cè)用戶的偏好程度擇優(yōu)推薦.傳統(tǒng)的協(xié)同過濾沒有考慮到多維的影響因素，繼而出現(xiàn)了加入上下文語義信息的協(xié)同過濾[13]和融入地理、時(shí)間或社會(huì)影響的協(xié)同過濾[14].實(shí)際生活中，人們?cè)L問興趣點(diǎn)的順序存在一定行為規(guī)律，例如更多的人會(huì)在看完電影后去吃飯，而不是去運(yùn)動(dòng)，文獻(xiàn)[15-17]在分析行為的順序模式后得到了一系列連續(xù)性的POI推薦.隨著通信時(shí)代數(shù)據(jù)量的劇增，為了解決數(shù)據(jù)量大且稀疏造成計(jì)算困難的問題，矩陣分解模型被提出，它利用數(shù)據(jù)間線性關(guān)系預(yù)測(cè)未知值，緩解了數(shù)據(jù)稀疏帶來的預(yù)測(cè)困難.之后，隨著數(shù)據(jù)集的不斷完善，出現(xiàn)了加入時(shí)空影響或社會(huì)影響的矩陣分解模型[18-20]，推薦的準(zhǔn)確率也有了明顯提升，但目前大多數(shù)基于矩陣分解算法的推薦模型，僅利用了少量的影響因素，推薦系統(tǒng)在多維信息的聯(lián)合利用方面仍有很大的提升空間.貝葉斯排序(BPR)算法[21-24]是基于矩陣分解的一種排序算法，針對(duì)每一個(gè)用戶去過的興趣點(diǎn)做排序優(yōu)化推薦，雖然準(zhǔn)確率有所提升，但沒有做全局優(yōu)化，無法向用戶推薦其未訪問過的興趣點(diǎn).

矩陣在數(shù)據(jù)建模的過程中會(huì)將原始數(shù)據(jù)轉(zhuǎn)換成向量形式，如用戶-地點(diǎn)向量，從實(shí)際物理含義來說，僅考慮矩陣形式會(huì)將多維數(shù)據(jù)的內(nèi)部結(jié)構(gòu)破壞.考慮到很多影響因素間具有一定的依賴性和聯(lián)系性，在矩陣分解模型的基礎(chǔ)上，衍生出了張量分解模型[25]，張量分解可以挖掘至少三種影響因子之間的潛在關(guān)系，在建模時(shí)就考慮到了數(shù)據(jù)的實(shí)際物理含義，例如，用戶-時(shí)間-地點(diǎn)張量中每個(gè)元素的含義是用戶在某個(gè)時(shí)刻某個(gè)地點(diǎn)是否有簽到信息，且張量分解能有效緩解簽到數(shù)據(jù)的稀疏問題.目前大多數(shù)基于張量分解的推薦算法[26-28]主要利用用戶-時(shí)間-地點(diǎn)建模，以社會(huì)和空間條件作為約束項(xiàng)，采用CP分解或HOSVD分解進(jìn)行優(yōu)化.

表1 基本符號(hào)

Table 1 Basic symbols

名稱符號(hào)名稱符號(hào)用戶(user)u地點(diǎn)(location)l類別(category)c時(shí)間(time)t用戶矩陣(m×r1)U地點(diǎn)矩陣(n×r2)L類別矩陣(q×r3)C核心張量(r1×r2×r3)S簽到信息(check-in)k用戶偏好(perference)p流行度(popularity)f權(quán)重(weight)w標(biāo)簽(label)z

針對(duì)現(xiàn)有研究中有待提升的點(diǎn)，結(jié)合張量分解算法的優(yōu)勢(shì)，本文提出一種基于張量分解的多維信息融合的興趣點(diǎn)推薦通用模型.主要貢獻(xiàn)點(diǎn)如下：

1) 提出了一個(gè)基于張量分解的多維信息融合的通用模型，該模型融合了時(shí)間影響、地理影響、社會(huì)影響、類別影響以及地點(diǎn)流行度影響，且模型靈活有可擴(kuò)展性，允許直接增添新的特征維度.

2) 利用地點(diǎn)分類約束了張量的大小，將上萬的地點(diǎn)規(guī)劃至三十多種常用類別下，設(shè)計(jì)了用戶-時(shí)間-類別張量，在基于HOSVD處理原始張量的基礎(chǔ)上，結(jié)合梯度下降法對(duì)張量進(jìn)行分解，緩解了簽到信息的稀疏性.

3) 提出用戶常駐地和標(biāo)簽偏好概念.設(shè)置與用戶常駐地的距離閾值，區(qū)分本地和異地推薦.針對(duì)具體情況為影響因素分配不同權(quán)重，本地推薦側(cè)重地理因素影響，異地推薦側(cè)重于標(biāo)簽偏好.

4) 針對(duì)推薦問題中的用戶/地點(diǎn)冷啟動(dòng)問題，本文有相應(yīng)的解決方案.沒有記錄的新用戶可利用社會(huì)關(guān)系在用戶畫像中找到與之相似的用戶，系統(tǒng)為其推薦相似用戶訪問過的興趣點(diǎn).沒有被簽到過的興趣點(diǎn)可通過在地點(diǎn)標(biāo)簽中找到與之距離較近的興趣點(diǎn)，利用已知POI的流行度影響帶動(dòng)發(fā)展，一起推薦給用戶.

3 模型描述

3.1 數(shù)據(jù)集及預(yù)處理

在以下實(shí)驗(yàn)中，本文使用了Foursquare數(shù)據(jù)集.在數(shù)據(jù)預(yù)處理階段，刪去了簽到消息少于10條的不活躍用戶以及簽到信息不夠完整的記錄.

3.2 基本定義

表1是關(guān)于以下本文實(shí)驗(yàn)用到的基本符號(hào)的描述.其中矩陣和核心張量的尺寸在括號(hào)中給出.

表2是一個(gè)用戶的一條簽到信息的具體內(nèi)容示例.

表2 簽到記錄示例

Table 2 Example of a check-in record

用戶ID時(shí)間地點(diǎn)IDFri Jul 2903:56:22 20114b201237f964a520d32c24e38地點(diǎn)經(jīng)度地點(diǎn)緯度34.14860530122695-118.14887700066679地點(diǎn)名稱地點(diǎn)類別Heritage WineCompanyNightlifeSpot,Food

3.3 建模過程

3.3.1 模型框架

模型框架如圖1所示，將數(shù)據(jù)集里的用戶簽到信息進(jìn)行預(yù)處理，處理后的數(shù)據(jù)用于構(gòu)造用戶畫像和地點(diǎn)標(biāo)簽.

圖1 模型流程圖

第一部分，先構(gòu)造用戶-時(shí)間-種類的三階張量，并且加入社交網(wǎng)絡(luò)中的朋友關(guān)系作為張量模型中的約束項(xiàng).該張量中每個(gè)元素的實(shí)際物理意義為用戶u在時(shí)間t對(duì)興趣點(diǎn)類別c的偏好程度，即用戶對(duì)時(shí)間-類別標(biāo)簽的偏好度pt.接著，分析每個(gè)用戶簽到信息中的經(jīng)緯度信息，找出一個(gè)點(diǎn)與簽到信息中各地點(diǎn)的歐式距離和最小，作為用戶“常駐地”lu.

第二部分，先記錄每個(gè)POI的位置信息l(經(jīng)度，維度)；再根據(jù)時(shí)間-類別特征定義標(biāo)簽，通過用戶的簽到記錄將每個(gè)興趣點(diǎn)(帶有經(jīng)緯度)劃分到標(biāo)簽下得到初始標(biāo)簽列表za.其中，一個(gè)興趣點(diǎn)可以對(duì)應(yīng)多個(gè)標(biāo)簽，例如，有一個(gè)ID為“4b5b5cfdf964a520e9f728e3”的興趣點(diǎn)可屬于標(biāo)簽“周末下午-商店服務(wù)”，也可以屬于“周末上午-食品”.統(tǒng)計(jì)每個(gè)興趣點(diǎn)在系統(tǒng)中的簽到次數(shù)，根據(jù)次數(shù)排名給每個(gè)興趣點(diǎn)加上“地點(diǎn)流行度”fl，例如，排名第一的POI流行度為1，而倒數(shù)第一者流行度為0.01.

第三部分，利用HOSVD分解和梯度下降法得到預(yù)測(cè)后的新用戶-時(shí)間-種類三階張量，即得到了用戶對(duì)標(biāo)簽的偏好值.接著，選出張量中排名前x大的元素值，以此挑選出za中的相應(yīng)位置作為選擇標(biāo)簽列表zb.最后計(jì)算用戶“常駐地”與興趣點(diǎn)間的距離差ld，結(jié)合地點(diǎn)流行度fl和選擇標(biāo)簽列表zb加權(quán)計(jì)算得到TOP-N個(gè)POI推薦給用戶.

3.3.2 用戶畫像

用戶-時(shí)間-類別張量構(gòu)造過程如圖2(a)所示，其中，元素“1”表示用戶在該時(shí)間-類別下有簽到記錄，元素“？”表示未知.根據(jù)簽到次數(shù)在對(duì)應(yīng)元素前加一個(gè)權(quán)重值后得到原始張量，原始張量的每個(gè)元素實(shí)際物理意義為用戶對(duì)每個(gè)時(shí)間類別標(biāo)簽的偏好度，稱之為用戶標(biāo)簽偏好.

用戶朋友關(guān)系如圖2(b)所示，我們認(rèn)為用戶ui和朋友uj間去過的相同POI重合度越高，則他們之間的偏好越接近.用戶i和朋友j的相似度通過以下相似度計(jì)算公式得到，

(1)

其中，Gui和Guj分別表示用戶ui和朋友uj簽到的POI集合.f(·)為補(bǔ)償函數(shù)，|Gui-Guj|越大則補(bǔ)償數(shù)值越大，補(bǔ)償數(shù)值逐漸趨于平緩，經(jīng)過實(shí)驗(yàn)選擇，f(x)=log2(x+2)適合用于本文提出的模型.

圖2

大部分研究根據(jù)興趣點(diǎn)地理位置遠(yuǎn)近做推薦，通常只會(huì)推薦距離較近的地點(diǎn)，而未考慮對(duì)用戶進(jìn)行本地和異地推薦，因此，本文提出用戶“常駐地”概念，常駐地lu表示為，

(2)

其中，Lu={l1,l2，…，ln}為用戶u去過的地點(diǎn)集合.

對(duì)于每個(gè)用戶而言，找到一個(gè)中心點(diǎn)，使用戶簽到信息中所有地點(diǎn)與該點(diǎn)歐式距離和最小，將該點(diǎn)作為常駐地；以常駐地為中心，計(jì)算常駐地與POI之間的距離差；設(shè)置距離閾值，閾值范圍之內(nèi)的興趣點(diǎn)在推薦時(shí)側(cè)重于地理因素影響，而閾值范圍外的興趣點(diǎn)則側(cè)重于用戶偏好影響和地點(diǎn)流行度影響.

3.3.3 地點(diǎn)標(biāo)簽

圖3

初始標(biāo)簽列表如圖3(a)所示，時(shí)間-種類標(biāo)簽下存有對(duì)應(yīng)興趣點(diǎn)ID及位置信息.地點(diǎn)流行度生成圖如圖3(b)所示，統(tǒng)計(jì)每個(gè)地點(diǎn)出現(xiàn)的次數(shù)并做歸一化計(jì)算.

4 張量分解方法

4.1 HOSVD

目前許多關(guān)于張量分解的研究工作主要采用兩種方法：CP分解和Tucker分解.其中，Tucker分解通常會(huì)采用高階奇異值分解(Higher Order Singular Value Decomposition，HOSVD). 如圖4所示，本文首先采用HOSVD分解原始用戶-時(shí)間-類別張量，提取張量中重要特征，盡管HOSVD能夠起到降維和緩解數(shù)據(jù)稀疏的作用，但它并不能很好地處理缺失的數(shù)據(jù)信息.因而，在利用HOSVD處理原始張量的基礎(chǔ)上，再進(jìn)行分解，以便很好地補(bǔ)全丟失信息.

圖4 HOSVD示意圖

X=S×UU×TT×CC

(3)

其中，S∈Rr1×r2×r3，U∈Rm×r1，T∈Rn×r2，C∈Rq×r3

4.2 損失函數(shù)

(4)

4.3 張量分解過程

由于目標(biāo)函數(shù)(4)是非凸問題，尋找目標(biāo)函數(shù)的最優(yōu)結(jié)果沒有封閉形式的解，使用隨機(jī)梯度下降(SGD)來查找局部優(yōu)化.

(1)計(jì)算Yijk=S×UUi*×TTj*×CCk*

(2)分別計(jì)算關(guān)于S,U,T和C的梯度值：

?UFls(Xijk,Yijk)=(Yijk-Xijk)×S×TTj*×CCk*?TFls(Xijk,Yijk)=(Yijk-Xijk)×S×UUi*×CCk*?CFls(Xijk,Yijk)=(Yijk-Xijk)×S×UUi*×TTj*?SFls(Xijk,Yijk)=(Yijk-Xijk)×Ui*?Tj*?CCk*

算法1.張量分解算法

輸入:張量X，矩陣B

輸出:S，U，T，C

1.用較小的隨機(jī)數(shù)初始化S∈Rr1×r2×r3,U∈Rm×r1，T∈Rn×r2

C∈Rq×r3

2.設(shè)置步長η

3.for每一個(gè)不為0的Xijkdo

4.Yijk=S×UUi*×TTj*×CCk*

5.Ui*←Ui*-η?UFls-ηλ1Ui*-ηλ2LBUi*

6.Tj*←Tj*-η?TFls-ηλ1Tj*

7.Ck*←Ck*-η?CFls-ηλ1Ck*

8.S←S-η?SFls-ηλ1S

9.end for

10.returnS，U，T，C

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

本節(jié)將詳細(xì)描述實(shí)驗(yàn)數(shù)據(jù)和內(nèi)容，展示實(shí)驗(yàn)效果圖，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析.

5.1 評(píng)價(jià)指標(biāo)

本文實(shí)驗(yàn)選取了Foursquare數(shù)據(jù)集，對(duì)于每個(gè)用戶，我們隨機(jī)選擇其簽到信息的70%構(gòu)成模型訓(xùn)練集，剩余30%作為驗(yàn)證集.訓(xùn)練后的模型可得到每個(gè)用戶排名為TOP-N的興趣點(diǎn)并推薦給用戶.為了評(píng)價(jià)實(shí)驗(yàn)的性能，我們采用以下兩個(gè)指標(biāo)：

準(zhǔn)確率：

召回率：

其中，N表示給用戶u推薦的POI個(gè)數(shù)，M為總用戶數(shù)量，Su為推薦給用戶u的TOP-N興趣點(diǎn)的集合，Vu是用戶u訪問的地點(diǎn)集合.上述指標(biāo)對(duì)應(yīng)于一個(gè)試驗(yàn)，推薦算法的最終性能通過5次獨(dú)立試驗(yàn)的平均指標(biāo)得出的.

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

5.2.1 用戶常駐地聚類圖

圖5中每個(gè)圓點(diǎn)表示用戶簽到過的一個(gè)地點(diǎn)，五角星表示用戶常駐地.

圖5 單個(gè)用戶常駐地示例

5.2.2 張量分解損失值圖

圖6表明迭代次數(shù)超過20次后，矩陣U，T，C及核心張量S的損失值變化趨于平穩(wěn)；圖7顯示迭代次數(shù)超過15次后，張量損失函數(shù)值逐漸收斂.

圖6 矩陣及核心張量損失差值圖

圖7 張量損失函數(shù)圖

5.2.3 對(duì)比實(shí)驗(yàn)

本文在張量分解的基礎(chǔ)上主要利用了地理位置、時(shí)間因素、社會(huì)關(guān)系和地點(diǎn)流行度因素，提出一種基于張量分解的多維信息融合興趣點(diǎn)推薦算法(Multi-dimensional Information Fused Point-of-Interest Recommendation based on Tensor Decomposition，MIFTD)，選取以下算法作為對(duì)比：

對(duì)比實(shí)驗(yàn)1：基于時(shí)間權(quán)重的矩陣分解推薦算法(Time Matrix Factorization，簡寫為TMF)，該算法中考慮了時(shí)間，朋友關(guān)系和地理因素，根據(jù)人們?cè)诓煌瑫r(shí)間段的訪問活躍度給矩陣元素加上時(shí)間權(quán)重[29].

對(duì)比實(shí)驗(yàn)2：基于加性馬爾科夫鏈的推薦算法(Additive Markov Chain，簡寫為AMC)，該算法中融合了朋友關(guān)系、時(shí)間影響、地理因素以及地點(diǎn)流行度[30].

表3為N=5時(shí)，三種算法的實(shí)驗(yàn)準(zhǔn)確率和召回率具體數(shù)值.

表3 N=5時(shí)，推薦準(zhǔn)確率最高

Table 3 N=5，the highest recommendation accuracy

方法準(zhǔn)確率(%)召回率(%)MIFTD7.883.74TMF6.883.27AMC7.552.87

由圖8和圖9可知，隨著N取值的增大，推薦算法的準(zhǔn)確率呈現(xiàn)下降趨勢(shì)，召回率呈現(xiàn)上升趨勢(shì).對(duì)比推薦表現(xiàn)相對(duì)較好的TMF算法，在5次不同的N取值下，本文算法平均推薦準(zhǔn)確率提升了約17%.

圖8 準(zhǔn)確率對(duì)比圖

圖9 召回率對(duì)比圖

6 結(jié)束語

本文提出了一種基于張量分解的多維信息融合的興趣點(diǎn)推薦通用算法，用戶畫像中提出用戶常駐地概念，利用三階張量融合時(shí)間、社會(huì)關(guān)系和類別影響，地點(diǎn)標(biāo)簽中利用了地理影響和區(qū)域流行度影響，結(jié)合兩者并為影響因素分配權(quán)重得到最終推薦的TOP-N興趣點(diǎn).該模型靈活通用，方便增添新的特征維度，且有效解決了數(shù)據(jù)稀疏和冷啟動(dòng)問題.考慮到用戶行為順序特征，即通常人們?cè)L問POI具有一定的先后順序規(guī)律，所以推薦興趣點(diǎn)還應(yīng)當(dāng)注意時(shí)序問題.