基于張量分解的多維信息融合興趣點推薦算法

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

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

E-mail:alleny_29@qq.com

1 引 言

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

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

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

1)地理因素，Li等人[4]分析簽到信息發現，POI的訪問頻率通常與用戶離“常駐地”的距離成冪律分布，人們在考慮交通便利程度和路程遠近的因素后，往往會選擇離居住地較近的POI.

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

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

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

5)地點流行度，一個區域的POI如果被人們簽到過多次，表明至少它在當地非常受人們歡迎.本地用戶的頻繁訪問為該地點增添了熱度和知名度，這種流行現象直接影響異地的用戶的出行計劃，他們可能會慕名而來[9].文獻[10]將地理位置融入核密度估計基礎上，再結合興趣點流行度特征和時間因素推薦，考慮了用戶自身個性特征的同時體現了興趣點的特征.由于目前大部分的研究只考慮到以上兩種或三種影響因素，影響因素利用不夠全面可能導致推薦準確率難以進一步提高.

除了以上提到的多種因素影響外，推薦系統仍存在用戶/地點冷啟動問題，即當一個沒有簽到記錄的新用戶或者一個新的POI進入系統時，系統無法得到它們的歷史記錄信息，就無法利用相似性進行推薦.

2 相關工作

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

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

表1 基本符號

Table 1 Basic symbols

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

針對現有研究中有待提升的點，結合張量分解算法的優勢，本文提出一種基于張量分解的多維信息融合的興趣點推薦通用模型.主要貢獻點如下：

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

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

3) 提出用戶常駐地和標簽偏好概念.設置與用戶常駐地的距離閾值，區分本地和異地推薦.針對具體情況為影響因素分配不同權重，本地推薦側重地理因素影響，異地推薦側重于標簽偏好.

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

3 模型描述

3.1 數據集及預處理

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

3.2 基本定義

表1是關于以下本文實驗用到的基本符號的描述.其中矩陣和核心張量的尺寸在括號中給出.

表2是一個用戶的一條簽到信息的具體內容示例.

表2 簽到記錄示例

Table 2 Example of a check-in record

用戶ID時間地點IDFri Jul 2903:56:22 20114b201237f964a520d32c24e38地點經度地點緯度34.14860530122695-118.14887700066679地點名稱地點類別Heritage WineCompanyNightlifeSpot,Food

3.3 建模過程

3.3.1 模型框架

模型框架如圖1所示，將數據集里的用戶簽到信息進行預處理，處理后的數據用于構造用戶畫像和地點標簽.

圖1 模型流程圖

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

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

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

3.3.2 用戶畫像

用戶-時間-類別張量構造過程如圖2(a)所示，其中，元素“1”表示用戶在該時間-類別下有簽到記錄，元素“？”表示未知.根據簽到次數在對應元素前加一個權重值后得到原始張量，原始張量的每個元素實際物理意義為用戶對每個時間類別標簽的偏好度，稱之為用戶標簽偏好.

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

(1)

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

圖2

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

(2)

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

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

3.3.3 地點標簽

圖3

初始標簽列表如圖3(a)所示，時間-種類標簽下存有對應興趣點ID及位置信息.地點流行度生成圖如圖3(b)所示，統計每個地點出現的次數并做歸一化計算.

4 張量分解方法

4.1 HOSVD

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

圖4 HOSVD示意圖

X=S×UU×TT×CC

(3)

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

4.2 損失函數

(4)

4.3 張量分解過程

由于目標函數(4)是非凸問題，尋找目標函數的最優結果沒有封閉形式的解，使用隨機梯度下降(SGD)來查找局部優化.

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

(2)分別計算關于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.用較小的隨機數初始化S∈Rr1×r2×r3,U∈Rm×r1，T∈Rn×r2

C∈Rq×r3

2.設置步長η

3.for每一個不為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 實驗分析

本節將詳細描述實驗數據和內容，展示實驗效果圖，并對實驗結果進行分析.

5.1 評價指標

本文實驗選取了Foursquare數據集，對于每個用戶，我們隨機選擇其簽到信息的70%構成模型訓練集，剩余30%作為驗證集.訓練后的模型可得到每個用戶排名為TOP-N的興趣點并推薦給用戶.為了評價實驗的性能，我們采用以下兩個指標：

準確率：

召回率：

其中，N表示給用戶u推薦的POI個數，M為總用戶數量，Su為推薦給用戶u的TOP-N興趣點的集合，Vu是用戶u訪問的地點集合.上述指標對應于一個試驗，推薦算法的最終性能通過5次獨立試驗的平均指標得出的.

5.2 實驗結果

5.2.1 用戶常駐地聚類圖

圖5中每個圓點表示用戶簽到過的一個地點，五角星表示用戶常駐地.

圖5 單個用戶常駐地示例

5.2.2 張量分解損失值圖

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

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

圖7 張量損失函數圖

5.2.3 對比實驗

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

對比實驗1：基于時間權重的矩陣分解推薦算法(Time Matrix Factorization，簡寫為TMF)，該算法中考慮了時間，朋友關系和地理因素，根據人們在不同時間段的訪問活躍度給矩陣元素加上時間權重[29].

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

表3為N=5時，三種算法的實驗準確率和召回率具體數值.

表3 N=5時，推薦準確率最高

Table 3 N=5，the highest recommendation accuracy

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

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

圖8 準確率對比圖

圖9 召回率對比圖

6 結束語

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