一種結合矩陣分解和深度學習技術的POI推薦模型

(西安建筑科技大學 信息與控制工程學院，西安 710055)

0 引言

近年來， LBSN平臺吸引了無數用戶并產生了大量簽到數據。通過對簽到數據建模并結合傳統推薦技術來實現用戶POI的推薦，可以從推薦結果中得出用戶的日常喜好和行為模式；幫助商家發現潛在客戶、調整經營策略，具有極大的經濟和社會效益[1]。

目前，基于LBSN的用戶POI推薦研究，無論是基于傳統協同過濾、矩陣分解方法還是基于影響因素或文本信息考慮的POI推薦模型均存在以下的問題：

大部分POI推薦研究采用傳統協同過濾算法[2-4]，對用戶和簽到的POI進行建模，給出最后推薦。但這種基于LBSN的用戶簽到信息很容易遭遇數據稀疏問題。又有研究者提出基于矩陣分解的協同過濾算法[5-6]。分別用一個隱式向量代表用戶和POI，隱式向量間的內積表示用戶和POI之間的線性交互。這些算法有效緩解了數據稀疏問題且對用戶和個性化POI特征提取做出改進。但由于隱式向量內積操作只是簡單向量間的線性乘法，不足以提取用戶和POI之間高階歷史交互特征(非線性特征)，尤其是無法捕捉用戶簽到的序列特征。

為了解決序列建模的問題，有研究者[7]利用矩陣分解和馬爾科夫模型建模用戶的序列行為，但馬氏模型只考慮用戶訪問的最近一個POI點信息，所包含信息量太少，不能很好表示用戶行為特點。深度神經網絡能夠有效學習和提取多個特征的高階非線性關系，特別是循環神經網絡(RNN)能夠很好地對序列進行建模。Q.Liu等人[8]提出ST-RNN模型，Zhao等人[9]改進提出ST-LSTM模型。這類模型雖然能有效建模用戶簽到的序列行為，但從用戶細粒度興趣來看：單一的RNN無法同時學習用戶長期和短期的興趣特征，從模型整體來看：忽略了多影響因素之間的聯合作用。

綜合以上問題，文章的具體研究內容如下：1)針對簽到數據的稀疏問題，提出一種基于分解矩陣的協同過濾方法。計算得到POI的特征向量；2)針對用戶細粒度興趣(即長期興趣和短期興趣)序列建模問題，提出一個基于注意力機制(Attention)的深度神經網絡模型。可分別提取用戶長、短期興趣特征[10-11]；3)針對多影響因素之間的聯合作用問題，將矩陣分解提取的POI特征向量以及計算得到的用戶特征向量按照用戶簽到序列輸入帶有注意力機制的深度學習網絡進行模型訓練。設計得到多特征高階非線性交互的POI推薦模型(MF-ADNN)。該模型可對LBSN中的地理、時間、社交和序列影響進行綜合考慮，分別對用戶簽到數據集的4階段(早、午、晚、夜)進行訓練，做出不同時間段的POI推薦。

1 問題定義和用戶細粒度興趣分析

POI推薦模型旨在為用戶推薦其感興趣的POI點。表1是本文用到的基本數學符號及含義。

表1 基本數學符號及含義

1.1 問題定義

U={u1,u2,...,un}表示用戶集合，P={p1,p2,...,pm}表示興趣點，給定用戶u的歷史簽到記錄Du，當前的時間t，文章所提出的POI推薦模型最終的操作是：從POI集合P中返回N個興趣點序列{pre1,pre2,...,preN}。序列集pre，即未來某階段內用戶u最有可能訪問的興趣點集。

1.2 細粒度興趣

用戶興趣隨著時間的推移可能會發生變化，即用戶簽到行為可分為長期興趣和短期興趣兩種，本文稱之為用戶的細粒度興趣。

1.2.1 用戶長期興趣

用戶的長期興趣一般指用戶周期性訪問的POI。RNN結構具有記憶功能，能夠很好地為用戶的簽到序列行為特征進行建模，對于捕獲用戶的長期興趣是一個好的選擇。但一般的RNN存在梯度消失的問題，故采用LSTM來捕獲用戶的長期興趣。具體模型情況參見第3.3節CF-ADNN模型的LM模塊。

1.2.2 用戶短期興趣

用戶的短期興趣最有可能影響后續的興趣點訪問，一般主要指與上一個訪問的興趣點距離和類別相近的POI。故采用帶有Attention機制的seq2seq架構。將用戶歷史興趣點編碼成一個向量，利用Attention機制關注最相近的幾個興趣點進行解碼，最終得到用戶的短期興趣。具體模型情況參見3.3節CF-ADNN模型的SM模塊。

2 結合矩陣分解和深度學習技術的POI推薦模型

本節介紹結合矩陣分解和深度學習的個性化POI推薦模型CF-ADNN的構建及訓練過程。將矩陣分解提取的POI特征向量以及計算得到的用戶特征向量作為以上兩個模塊的輸入，構建POI推薦模型CF-ADNN，并對該模型進行訓練。

2.1 基于矩陣分解的興趣點特征表示

為了解決簽到數據的稀疏問題，利用簽到數據集中興趣點的ID，地理坐標和所屬類別這三個維度信息，建立POI同現矩陣、位置近似矩陣以及類別同屬矩陣。再基于一種矩陣分解方法得到POI在同現、位置和類別特征中的隱向量，將上述三種隱向量拼接成一個整體的POI特征向量表示[12]。

2.1.1 構造特征矩陣

1)POI同現矩陣：初始化一個POI同現矩陣O∈Nn×n，表示POI在用戶訪問模式上的關聯關系，n等于POI數。具體來說，Opp′表示同時訪問過p和p′興趣點的用戶個數，對角線元素Opp表示訪問p的用戶個數。一般的，Opp′值越高，表明p和p′頻繁地被先后訪問，則證明關聯性越強。

2)位置近似矩陣：與POI同現矩陣類似，初始化一個位置近似矩陣G∈Nn×n，表示用戶的簽到行為和POI的地理位置高度關聯。引入距離閾值m=10 km，根據簽到點的經緯度坐標計算p(lon,lat)和p′(lon′,lat′)之間的距離D，若小于m，則Gpp′=1；否則Gpp′=0。特別的，Gpp=1。D的計算公式：

C=sin(lat)*sin(lat′ )*cos(lon-lon′)+cos(lat)*cos(lat′)

D=R*Arccos(C)*PI/180

(1)

其中:R為地球平均半徑6 371.004 km。

3)類別同屬矩陣：類別同屬矩陣R∈Nn×n，表示POI在類別信息上的關聯，利用了POI的內容信息。若p和p′屬于同一個類別，Rpp′=1;否則Rpp′=0。特別的，Rpp=1。

構建特征矩陣過程示例如圖1所示。

圖1 構建特征矩陣示意圖

2.1.2 對稱矩陣分解

將上述3個對稱矩陣進行矩陣分解：

1)POI同現矩陣分解：對于POI同現矩陣O∈Nn×n，把這個矩陣分解成兩個矩陣的點乘，如公式(2)所示：

O(n,n)=Eo*ETo

(2)

使兩個同階的矩陣相似程度最小，得到最接近原始矩陣，如公式(3)：

(3)

為了進一步說明對稱矩陣分解的優點，給出兩個POI隱向量的相似度近似計算公式(4)～(5)：

(4)

(5)

通過觀察近似公式可知，隱向量的相似性與用戶臨近POI訪問率有關，說明上述分解方法能夠很好地學習、表示興趣點在該特征空間的相互關聯；同時抑制了熱門POI對最終推薦結果的影響，有利于POI推薦結果的多樣化。

2)位置近似矩陣分解：與POI同現矩陣分解方法相同，具體的分解形式如式(6)所示：

(6)

3)類別同屬矩陣分解：與上述矩陣分解方法相同，具體的分解如公式(7)所示：

(7)

2.1.3 計算特征向量

拼接上述3個矩陣分解所得的隱向量，得到一個整體的POI特征向量表示。具體如公式(8)：

(8)

2.2 用戶特征向量計算

計算用戶特征向量時，可結合考慮用戶的社交影響因素，即共同計算用戶與用戶好友特征向量。文章將用戶特征向量表示成該用戶與該用戶的好友訪問過的所有POI的特征向量的期望，從而得到用戶特征向量。用戶特征向量eu計算公式(9)如下：

(9)

Pu和Pu′分別表示用戶u和他的好友u′訪問過的POI集合，|Pu|表示用戶u訪問過的POI數量。

2.3 POI推薦模型CF-ADNN

CF-ADNN模型旨在構建不同的神經網絡模型分別學習用戶長期和短期興趣特征。將前兩節基于矩陣分解提取的POI特征向量，以及計算得到的用戶特征向量按用戶簽到序列輸入模型，訓練模型的高階交互特征，預測未來最有可能訪問的興趣點集。

2.3.1 CF-ADNN模型結構

圖2展示了CF-ADNN模型的整體架構。該模型主要分為兩個主要模塊:LM模塊獲取的是用戶的長期興趣的隱含向量；SM模塊獲取的是短期的隱含向量。

圖2 CF-ADNN模型整體架構圖

1)LM模塊：

用戶的長期興趣主要考慮的是用戶周期性訪問的模式。為了捕獲長期興趣，采用LSTM來捕獲用戶的長期興趣。具體的公式如下:

(10)

(11)

(12)

2)SM模塊：

用戶的短期興趣主要指與上一個訪問的興趣點相近的(距離和類別)的興趣點。選擇相同類別且兩個連續簽到點距離小于10 km的興趣點作為用戶的短期興趣。SM模塊采用帶有Attention+seq2seq架構，seq2seq架構主要分為Encoder和Decoder。用戶的短期興趣表示方法：通過Encoder把用戶訪問的興趣點編碼成一個向量，編碼方式選擇LSTM網絡。編碼過程公式如下:

(13)

(14)

具體公式如下:

Ct=∑sαtshs

(15)

(16)

score(hn,hs)=vTtanh(ω1hn+ω2hs)

(17)

其中:vT、ω1和ω2是模型需要學習得到的參數。這里Ct最為重要，表示通過Attention計算得到的上下文向量。進一步計算得到引入注意力的隱藏狀態向量：

Sn=f(Ct,hn)=tanh(Wc[Ct+hn])

(18)

以及解碼器生產的目標興趣點序列：

S[yt|{y1,y2…yt-1},Ct]=softmax(WcSn)

(19)

長期興趣Lt+1以及短期興趣序列St+1結合起來，得到最終的推薦結果Ot+1：

Ot+1=Lt+1∪St+1

(20)

2.3.2 推薦模型訓練

從時間維度分析，為了訓練一個模型來適應不同時間段的用戶簽到，這里將簽到數據分為4個時間段：夜(0∶01-6∶00)、早(6∶01-12∶00)、午(12∶01-18∶00)、晚(18∶01-24∶00)分別進行訓練，得到適應不同時間段的POI推薦模型。

CF-ADNN推薦模型學習算法

輸入：eu、ep、t、T

輸出：Ot+1(最終的推薦結果)L(最小損失值)

1.Repeat

2.Foreachu∈UDo

3.輸入eu和ep，SM訓練用戶短期興趣S

4.Fort

5.輸入eu和ep，LM訓練用戶長期興趣L

7. End for

9.梯度下降法最小化損失lu

10. ift>Torlu足夠小

11.End for

12.Returnlu、Ot+1

13.End procedure

3 實驗與分析

3.1 實驗數據集

本文采用Foursquare簽到網站的開源數據集作為實驗數據，驗證模型的有效性。選取美國舊金山市(SFO)的用戶簽到信息，統計結果如表2所示。

表2 用戶簽到信息統計表

訓練時，將用戶前80%的簽到數據集作為訓練集，最近的20%作為測試集。

3.2 評價指標

性能評價指標選用準確率、召回率，分別用PRE@N，REC@N表示。對于一個用戶u，模型的推薦結果是：

(21)

用戶真實的訪問序列是：

(22)

其中:N為模型預測返回的POI個數。

則準確率和召回率的公式如下：

(23)

(24)

3.3 實驗結果及分析

3.3.1 參數影響

訓練模型時選取的參數會對推薦結果造成影響。本文主要討論影響模型最重要的兩個參數：

1)特征向量維度d：eu和ep作為模型的輸入可以看出，特征向量維度d是影響整個模型的重要因素。d越大模型需要的計算量越大。

圖3 特征向量維度d對模型影響

固定矩陣分解中的正則項參數λo=λg=λr=0.000 01，設置維度d為100、150、200、250、300。實驗結果如圖3所示，當維度超過200后模型的性能開始降低，故本實驗將d設置成200。

2)關注長度δ：用戶短期興趣建模主要用到基于Attention機制的序列模型，Attention關注長度δ對模型十分重要。δ過長，模型會變得復雜;δ過短，可能會使得數據不足。

圖4 關注長度δ對模型影響

分別設置關注長度δ為 5，10，20，40 進行試驗，實驗結果如圖4所示，當δ為10模型效果最好。

3.3.2 不同推薦模型對比結果

為了驗證CF-ADNN模型的性能，文章選擇3個在矩陣分解和深度學習POI推薦算法領域，具有代表性的模型進行試驗對比。GeoMF[5]：基于矩陣分解的地理位置信息POI推薦；ST-RNN[8]：基于時空上下文RNN模型的POI推薦；ST-LSTM[9]：基于時空上下文LSTM模型的POI推薦。

CF-ADNN模型與以上3種算法的性能對比結果如圖5所示。

圖5 算法性能對比結果圖

從圖5的對比結果可知，GeoMF模型的指標率最低。這說明基于矩陣分解方法的POI推薦模型雖然有效緩解了數據稀疏性，但由于隱式向量內積操作只是簡單向量間的線性乘法，不足以提取用戶和POI之間高階歷史交互特征尤其無法捕捉用戶簽到的序列特征。而ST-RNN和ST-LSTM模型將用戶的歷史簽到記錄用序列方式傳入RNN來學習用戶及POI的向量表達，可有效建模用戶簽到的序列行為，故推薦性能指標明顯高于GeoMF模型。同時，ST-LSTM模型對ST-RNN進行改進，避免了梯度消失，故ST-LSTM模型推薦性能優于ST-RNN。而MF-ADNN結合矩陣分解技術和帶有注意力機制的用戶簽到序列建模技術，可以降低簽到數據的稀疏性；細粒度建模用戶興趣；更好學習聯合影響因素的高階非線性交互特征。因此與其它3個模型相比，MF-ADNN在準確率和召回率上均有更優的表現。

5 結束語

文章提出一個結合矩陣分解和帶有注意力機制深度學習技術的POI推薦模型。該模型融合了時間影響、地理影響、社交影響以及序列影響4個因素實現用戶POI推薦。主要任務包括：通過構建特征矩陣緩解簽到數據稀疏問題，矩陣分解得到隱藏因子，計算POI的特征向量；構建一種帶注意力機制的用戶細粒度興趣的序列建模方式，有效學習用戶長期和短期的興趣特征，提高POI推薦精確度；結合上述兩種方法，最終得到可以融合多種影響因素的POI推薦模型。試驗結果表明，該POI推薦模型具有較好性能。文章未考慮的影響因素還有很多，如評論信息、文本信息等，未來的工作將考慮在模型中融入這些特征，進一步提升推薦算法的性能。