王 立,張 謐

(復旦大學 軟件學院,上海 201203)

(復旦大學 上海市智能信息處理重點實驗室,上海 201203)

近年來,基于位置的社交網(wǎng)絡(Location-Based Social Network,LBSN)應用飛速增長,典型的基于位置的社交網(wǎng)絡有大眾點評、微博、Foursquare、Yelp等,而人們也越來越習慣利用在線應用獲取信息.這使得我們可以更方便的收集到用戶的好友信息和歷史行為序列信息,這些社交、地理位置、時間信息都為精細化推薦提供了更大的可能性.然而,要根據(jù)有限的信息完全準確的預測出單個用戶在一個具體的時間節(jié)點出現(xiàn)在特定位置上的特定商家還是一件極具挑戰(zhàn)性的事情.但是,一旦我們可以準確的預測出用戶的行為序列,除了將推薦結(jié)果應用在現(xiàn)有的情景外,還可以推廣到其余眾多的領(lǐng)域,例如預測交通狀況,根據(jù)人們的行為趨勢,可以精準的定位交通堵塞發(fā)生的時間和地點,并提前啟動預防機制.

在機器學習領(lǐng)域,針對基于地理和時間信息POI推薦,不斷有新的推薦方法提出.這些推薦主要分為四類,分別是馬爾科夫模型、張量分解模型、RNN深度學習模型和地點向量化模型.FPMC是普通馬爾科夫模型的擴展,能夠針對不同個體提供個性化推薦,FPMC通過為每個用戶設置馬爾科夫鏈俘獲用戶的長期喜好和近期關(guān)注,同時可以通過張量分解解決轉(zhuǎn)移矩陣數(shù)據(jù)匱乏的問題.基于其特性,這種模型能夠很好的對序列進行建模,FPMC 也被成功的應用在POI推薦上[1–5].TF張量分解模型也在解決POI問題上得到應用,TF假設每一維信息為一個張量,例如用戶就是U矩陣,商戶是V矩陣,時間是T矩陣等,通過訓練得到這些矩陣就可以獲得用戶、商戶、時間等不同維度之間的關(guān)系.因為TF可以將很多非結(jié)構(gòu)化的信息鍵入模型,所以在基于時間[6]和基于地理位置信息[7,8]的模型在POI推薦上都有廣泛應用.而在深度學習在NLP和圖像領(lǐng)域大放異彩的時候,RNN在POI推薦問題上也有所應用[9],RNN模型能夠很好的對序列信息建模,同時還不需要強先后依賴關(guān)系假設,在POI推薦問題上相比 FPMC 有更好的表現(xiàn).此外,很多學者[10–12]也嘗試利用 Word Embedding類似的方式解決POI推薦問題,將商戶等轉(zhuǎn)化成為低維空間向量,然后基于向量之間的相似度為用戶推薦下一個興趣點.

雖然上述模型在一些特定的場景內(nèi)取得了令人驚喜的效果,但是它們并不能處理社交信息,也不能衡量用戶和POI之間的語義相似度.譬如,一個用戶會根據(jù)商戶的標簽信息以及朋友圈內(nèi)朋友的評價信息進行選擇.

本文提出一種基于LSTM對POI和用戶同時做Embedding的框架 POI-LSTM,將用戶的評價信息、好友關(guān)系、歷史訪問信息轉(zhuǎn)化成為向量后,輸入到LSTM內(nèi)預測用戶下一個興趣點.相比現(xiàn)有的向量化模型而言,能夠捕捉更多的序列依賴信息;而相比現(xiàn)有的RNN模型,能夠更好的處理復雜的社交關(guān)系和語義信息.

后文組織如下:第1節(jié)介紹LSTM算法及Embedding的相關(guān)背景知識;第2節(jié)介紹POI-LSTM框架的實現(xiàn)細節(jié);第3節(jié)介紹數(shù)據(jù)集以及實驗結(jié)果;第4節(jié)進行總結(jié).

1 相關(guān)背景

本節(jié)主要介紹和本模型密切相關(guān)的LSTM網(wǎng)絡結(jié)構(gòu)以及Embedding算法.

1.1 LSTM網(wǎng)絡結(jié)構(gòu)介紹

Long Short Term Memory 網(wǎng)絡是一種 RNN 特殊的類型,可以學習長期依賴信息.LSTM自提出以來,已經(jīng)被應用很多場景中,也取得了巨大的成功.

LSTM和RNN一樣,通過重復神經(jīng)網(wǎng)絡模塊的鏈式形式來對序列數(shù)據(jù)進行學習.同時為了避免RNN的梯度爆炸和梯度彌散問題,LSTM通過在RNN的重復模塊中添加遺忘門、輸入門和輸出門來增加長序列的記憶問題.LSTM中重復模塊的結(jié)構(gòu)如圖1.

圖1 LSTM 模塊結(jié)構(gòu)

圖1中,Cell是LSTM模型維護的狀態(tài),包含了當前時間節(jié)點以前所有的信息;Input Gate用來控制當前輸入信息保留概率;Forget Gate用來控制根據(jù)當前的輸入和狀態(tài)來看,Cell含有的信息保留的概率;Output Gate用來控制當前時刻的信息的輸出概率;通過三個控制門的控制,LSTM可以不斷的吸收輸入信息,更新自己的狀態(tài),并控制輸出.LSTM的向前傳播公式如下:

其中,σ表示sigmoid函數(shù),W表示神經(jīng)網(wǎng)絡中的權(quán)重,b表示偏置項,tanh為輸出的激活函數(shù).

LSTM可以采用梯度下降法進行更新,最終使得損失函數(shù)值最小.

1.2 Embedding模型介紹

Word Embedding 算法,也被稱為 Word2Vec 算法[11],是由Bengio等于2003年提出的一個三層神經(jīng)網(wǎng)絡的自然語言模型,主要分為Skip-Gram和CBOW兩種模型.Word2Vec通過神經(jīng)網(wǎng)絡擬合一個詞序列的條件概率p(wt|w1,w2,···,wt-1),從而將文本詞語轉(zhuǎn)化成為向量空間中的向量,在模型訓練完成后,詞向量之間的相似度具有一定的語義相似度.整個模型的網(wǎng)絡結(jié)構(gòu)如圖2所示.

圖2 CBOW 模型網(wǎng)絡結(jié)構(gòu)

從圖中可以看出,Word2Vec模型主要分成兩部分,前半部分在詞向量矩陣中根據(jù)詞語的序號尋找詞向量,后半部分將詞向量經(jīng)過tanh隱藏層和softmax的激活輸出層得到輸出的詞概率估計.

訓練好的Word2Vec模型具有一定的語義相似度,例如China-Beijing≈French-Paris.正是因為這樣的相似度,我們可以根據(jù)預測得到的向量和已有興趣點向量之間的相似度來預測下一個興趣點.

2 POI-LSTM 模型

現(xiàn)有的LSTM模型和Embedding模型主要問題在于都只能模擬單源信息.在POI推薦場景中,包含大量的社交信息和語義信息,用戶并非單純的從一個地點轉(zhuǎn)移到另外一個地點,用戶除了遵從自身的喜好外,還可能會受到朋友的影響,而且用戶對以前訪問過的POI并非都持有喜愛的態(tài)度,這時候用戶以往的評論信息就顯得至關(guān)重要.單純的LSTM模型只能對用戶的行為序列進行建模,將用戶訪問過的地點信息輸入到網(wǎng)絡中,只能捕捉到用戶的訪問地點興趣信息,不加入用戶的歷史評論信息就不能精細描述用戶的興趣變化,同時也不能接受用戶好友關(guān)系對于用戶選擇的影響.而單純的使用Embedding的話,現(xiàn)有的推薦模型能夠獨立將用戶和好友、POI以及評論分別進行向量化,應用到POI推薦問題上.單獨使用其中一種信息都不能很好的進行精細化推薦,但是要是訓練三種向量的話,怎么均衡三者之間的關(guān)系,即使用權(quán)重和比例上很難把握,往往會使得模型訓練坍塌,就算能夠訓練成功,也很難在測試集合上成功應用.本模型則采用端對端的訓練方式,將用戶及其好友關(guān)系作為固有屬性,將其歷史評論信息向量化后結(jié)合當時訪問的POI信息一同輸入LSTM網(wǎng)絡中得到用戶興趣信息作為動態(tài)屬性,然后三者結(jié)合為用戶推薦下一個地點.

本節(jié)將從數(shù)據(jù)的問題定義、模型網(wǎng)絡結(jié)構(gòu)以及損失函數(shù)三方面進行描述.

2.1 問題定義

針對POI推薦問題,我們定義P為用戶集合,Q為 POI集合,T為標簽集合.另外指定,表示用戶u、興趣點v和標簽s的d維向量.每個興趣點v都有它的經(jīng)緯度信息和標簽集合.每個用戶u綁定有其標簽集合,朋友列表以及歷史訪問記錄，其中表示用戶u在時間 訪問了興趣點q.所有用戶的歷史行為序列表示為.給定了用戶的歷史行為記錄信息和相關(guān)的好友信息，模型的任務就是預測下一次用戶最有可能去的興趣點.數(shù)據(jù)源結(jié)構(gòu)如圖3.

圖3 數(shù)據(jù)源結(jié)構(gòu)

2.2 模型框架

模型整體網(wǎng)絡架構(gòu)如圖四所示,其中直角方塊方塊部分代表了模型的四種源輸入,最左側(cè)方框代表用戶的向量輸入,中間的方框部分代表用戶的朋友向量輸入,右上側(cè)方框代表用戶對興趣點的評價信息,右側(cè)中間方框包含了興趣點的向量和地理位置(經(jīng)緯度分別歸一化到正負一之間)輸入.下側(cè)圓角虛線方框代表了模型的經(jīng)過卷積和LSTM層提取的高維特征.最右下方的圓角實線方塊則代表了模型的輸出部分.

圖4 POI-LSTM 網(wǎng)絡結(jié)構(gòu)

用戶的向量輸入和Word2Vec的輸入相似,輸入one-hot的向量作為輸入,然后經(jīng)過Embedding層得到該用戶的向量.相似的,朋友的向量是k個one-hot向量作為輸入,然后得到k個朋友的向量作為輸入,在實現(xiàn)的時候直接輸入k-hot的向量,得到代表關(guān)系網(wǎng)的向量作為該層的輸入.對于該用戶對每個興趣點的評價信息,使用單詞對應的預訓練(基于glove數(shù)據(jù)集)好的向量作為輸入,然后經(jīng)過卷積層和ROI池化層將評價信息壓縮到一維向量作為LSTM的部分輸入.此向量和興趣點的地理位置向量以及興趣點的向量拼接起來將作為LSTM層的輸入.

不同源的輸入經(jīng)過上述的過程,已經(jīng)提取成為高維的特征,分別是用戶自身的特征、社交特征、評價和行為序列特征.這些特征拼接起來后,經(jīng)過激活層即可得到下一次將要訪問的興趣點的向量表示.同時為了保證模型的準確性,我們還將高維的特征進過全連接層輸出一個地理位置信息和訪問的排序信息,以確保訪問的地點和下一次訪問的地點之間地理位置偏差較小.

特別說明,對于不同源的低維度特征模型采用不同的神經(jīng)網(wǎng)絡層來提取高維特征.用戶特征直接接入最后的全連接和激活層.社交特征即用戶的好友的信息通過CNN提取高維特征后經(jīng)過ROI池化層轉(zhuǎn)化成為固定長度的高維特征.用戶對興趣點的評論特征,和社交信息一樣,需要經(jīng)過CNN層提取高維特征后經(jīng)過ROI池化層得到固定長度的高維特征,之后＜評論特征,地理位置,興趣點特征＞將作為一個整體輸入LSTM網(wǎng)絡中作為用戶的歷史行為特征,因為LSTM可以很好的表示用戶的長期興趣,還能夠精確的捕捉到用戶近期的興趣特征.高維特征經(jīng)過tanh激活層即可得到用戶現(xiàn)有的興趣特征,這個特征就表達了用戶的下一個感興趣的興趣點;同時,這個高維特征內(nèi)還應該能表達用戶的活動范圍,利用全連接層可以提取高維特征中相應的地理位置信息.

2.3 損失函數(shù)

模型的損失函數(shù)分為兩部分,預測興趣點的向量和真實向量之間的差距以及預測地理位置和真實地理位置之間的距離.預測向量和真實向量之間的差距可以刻畫預測得到的向量的準確度,是損失函數(shù)最重要的部分.而預測地理位置和真實位置之間的差距作為調(diào)整的一部分也被加入到損失函數(shù)中,這是考慮到用戶本身的活動范圍有限,預測得到的POI不應該距離用戶的常規(guī)活動范圍有太大偏差,不然這樣的推薦將變的毫無意義.具體的損失函數(shù)如下:

預測得到的向量和真實向量之間的差距采用余弦相似度衡量,預測得到的興趣點向量為,我們采用當前t時刻之后的用戶訪問的k個興趣點來判定預測準確度:

地理位置之間的相似度采用歐式距離,預測得到的地理位置設置為,同樣測量其和未來k個興趣點之間的距離.損失函數(shù)如下:

最終,模型的損失函數(shù)如下:

3 實驗分析

我們使用的數(shù)據(jù)集為美國最大的點評網(wǎng)站Yelp公開的內(nèi)部數(shù)據(jù)集以及基于用戶地理位置信息的分享網(wǎng)站Foursquare公開的數(shù)據(jù)集.兩份數(shù)據(jù)集都采用數(shù)據(jù)標注城市為紐約的興趣點,以及評價過這些興趣點的用戶,數(shù)據(jù)規(guī)模如表1所示:

表1 數(shù)據(jù)集

3.1 評測標準

由于是預測下一個興趣點,所以我們的評測標準是Precesion@N,表示預測出TopN個作為推薦列表,其中推薦對的占推薦列表中所有的被推薦的興趣點的比例.

對于每份數(shù)據(jù)集,我們都按照1:4的比例分配測試集和訓練集,即每個用戶的訪問序列的前80%數(shù)據(jù)用來訓練,后20%數(shù)據(jù)用來測試.

選取的對比實驗有FPMC[1],Rank-GeoFM[8],POI2Vec[12]以及ST-RNN[9].FPMC是個性化馬爾可夫鏈模型的代表,該模型為每個用戶建立一個轉(zhuǎn)移矩陣,形成轉(zhuǎn)移矩陣立方體,然后使用張量分解模型對轉(zhuǎn)移立方體進行學習,彌補其數(shù)據(jù)稀疏的問題.Rank-GeoFM是一種基于時間序列的張量分解模型,將時間分段后獲取用戶的對興趣點的多個評分矩陣,然后使用張量分解學習這些評分矩陣.POI2Vec采用了Embedding的思想,將用戶訪問過的地點序列比擬作為NLP中的語句,然后構(gòu)建興趣點之間的后驗概率.ST-RNN則利用了循環(huán)神經(jīng)網(wǎng)絡的思想,基于興趣點的維度構(gòu)建RNN預測模型,輸出的興趣點向量,然后參照張量分解的思想和用戶向量相乘作為用戶訪問該興趣點的概率.選用的四個對比實驗涵蓋了當前比較主流的POI推薦模型種類,并且采用的比較新的模型結(jié)構(gòu).

3.2 實驗結(jié)果和分析

經(jīng)過多次實驗比較,我們分別測試了Precision@1、Precision@3、Precision@5.特別注意,由于每個用戶訪問的序列長度不同,我們會篩選測試序列長度大于等于N的部分.所以N越大,測試數(shù)據(jù)集的數(shù)量越小.實驗結(jié)果見圖5及圖6.

圖5表示在Foursquare上的精確度比較,圖6表示在Yelp上的精確度比較.可以看到POI-LSTM在兩個數(shù)據(jù)集上都表現(xiàn)搶眼,這說明向LSTM模型中加入用戶的社交信息以及評論和地理位置信息對提升興趣點預測的準確度有明顯作用.而模型在Foursquare上相比其它模型效果較Yelp上效果提升更明顯,這是因為Foursquare數(shù)據(jù)集比Yelp的數(shù)據(jù)集平均序列長度更短,使用額外的非序列信息對于提高準確度幫助更大,說明我們的模型在應對冷啟動問題上也有很大的效果.

圖5 Foursquare 數(shù)據(jù)集 Pre@N

圖6 Yelp 數(shù)據(jù)集 Pre@N

4 結(jié)語

本文成功的將LSTM和Embedding算法結(jié)合,并成功應用在興趣點推薦場景下,通過Embedding的思想把用戶的社交信息和標簽、評論信息變成向量輸入到循環(huán)神經(jīng)網(wǎng)絡中捕捉用戶的長期特征和短期愛好.實驗表明,該方法可以有效的提升興趣點預測的準確度,并能部分解決推薦場景中的冷啟動問題.