基于地理鄰近性的自編碼器在地點推薦中的應(yīng)用

張文翔

(天津大學(xué)管理與經(jīng)濟學(xué)部,天津 300072)

0 引 言

伴隨著基于位置的社交網(wǎng)絡(luò)(Location-based Social Networks, LBSNs)的快速發(fā)展，例如Foursquare，Brightkite和Gowalla等，簽到行為成為用戶分享生活的關(guān)鍵途徑之一[1]。因此，從用戶的簽到數(shù)據(jù)中挖掘用戶的興趣偏好——用戶地點推薦吸引了諸多學(xué)者的關(guān)注。個性化地點推薦不僅可以節(jié)省用戶時間，提高用戶滿意度，而且有利于商家的定制化營銷[2]，因此，個性化地點推薦已經(jīng)成為LBSNs發(fā)展中比較重要的一個方面，關(guān)于這方面的研究至關(guān)重要。

以往研究中，往往將所有的地點(Point of Interest, POI)同等看待，這就意味著用戶一周去6次博物館，與一周去6次超市同等看待，但是去超市比較常見，經(jīng)常去博物館極為少見，不可同等看待。因此，本文根據(jù)權(quán)重分析理論TF-IDF，將簽到頻率轉(zhuǎn)換為基于類別的用戶偏好。與傳統(tǒng)推薦任務(wù)不同的是，在POI推薦領(lǐng)域，最重要的就是地理影響[3-5]。如地理學(xué)第一定律所陳述“任何事物都相關(guān)，但是相近的事物之間關(guān)系更密切”，相近的POI之間更有可能具有密切的聯(lián)系，這種聯(lián)系叫做地理鄰近性。因此，對地理鄰近性進行建模，對于個性化地點推薦至關(guān)重要。在過去的幾年里，深度學(xué)習由于在特征挖掘方面的巨大優(yōu)勢，在機器智能領(lǐng)域取得了巨大的成功[6]。在地點推薦系統(tǒng)中，挖掘有效的地點特征是算法的關(guān)鍵。因此在本文中，利用深度自編碼器處理地點推薦任務(wù)。

1 地點推薦系統(tǒng)的研究現(xiàn)狀

1.1 地點推薦系統(tǒng)

LBSNs中地點之間存在地理鄰近性，而且很多研究發(fā)現(xiàn)，在LBSNs中的用戶簽到的POI分布上，存在某種地理聚集現(xiàn)象。例如，有部分學(xué)者根據(jù)用戶的簽到數(shù)據(jù)發(fā)現(xiàn)，被同一個用戶簽到的POIs的距離服從統(tǒng)一的分布，即冪律分布，因此可利用冪律分布計算POIs之間的關(guān)聯(lián)，最后用于預(yù)測用戶對于POI的推薦列表[7-9]。也有學(xué)者發(fā)現(xiàn)用戶的簽到行為集中在幾個中心地區(qū)，因此可利用多中心高斯分布對用戶簽到的POI進行建模，之后結(jié)合基于模型的協(xié)同過濾算法[3]。而文獻[10]利用基于二維地點坐標的核密度分布對地理鄰近性進行建模，同時結(jié)合二維核密度分布，形成基于模型的地點推薦系統(tǒng)。

本文嘗試采用一種新的方法對地理信息建模，利用基于地理鄰近性的深度自編碼器模型對POIs之間的關(guān)系進行建模，提取POIs之間潛在關(guān)系和特征。

1.2 深度學(xué)習與地點推薦

作為一種表示學(xué)習方法，深度學(xué)習具有多層表示結(jié)構(gòu)，每一層由許多簡單的非線性單元組成，且每個單元可以將底層的表示轉(zhuǎn)化到更好、更抽象的層級[6]。深度學(xué)習技術(shù)，由于在特征提取上的強大優(yōu)勢，已經(jīng)被應(yīng)用于多個領(lǐng)域，但是深度學(xué)習技術(shù)在推薦系統(tǒng)領(lǐng)域的研究剛剛起步，還沒出現(xiàn)系統(tǒng)化的研究。最早利用深度學(xué)習相關(guān)技術(shù)研究推薦系統(tǒng)的是利用受限玻爾茲曼機組成的協(xié)同過濾技術(shù)形成推薦算法[11]，但是該方法不適用于地點推薦。

最近一些學(xué)者逐漸開始研究深度學(xué)習技術(shù)在地點預(yù)測領(lǐng)域的應(yīng)用。例如，在文獻[12]中，作者提出一種空間嵌入模型對LBSNs中的簽到數(shù)據(jù)進行建模，與深度學(xué)習處理詞向量的詞嵌入方式類似，該方法利用深度學(xué)習技術(shù)對簽到數(shù)據(jù)進行嵌入處理。該方法的關(guān)鍵是將多個上下文信息(用戶、地點、時間等)融合在同一個模型中，并嵌入到同一個表示空間，即利用同一個嵌入空間表示多種上下文信息的深度學(xué)習技術(shù)。而文獻[13]中，作者利用循環(huán)神經(jīng)網(wǎng)絡(luò)對短期的上下文進行建模，利用門限循環(huán)單元對長期的上下文進行建模，將長短期上下文融合到一個深度學(xué)習模型中。

與現(xiàn)存方法不同，本文試圖利用深度學(xué)習技術(shù)對地理鄰近性進行建模，而非時間、序列等信息。深度學(xué)習模型包括許多，如卷積神經(jīng)網(wǎng)絡(luò)、循環(huán)神經(jīng)網(wǎng)絡(luò)、長短期模型和門限循環(huán)單元等。但是，上述提到的模型大多是監(jiān)督學(xué)習技術(shù)，然而，人類行為具有很大的非監(jiān)督特性[6]。因此，本文嘗試挖掘深度學(xué)習技術(shù)在非監(jiān)督領(lǐng)域的優(yōu)勢。換言之，本文利用非監(jiān)督的深度學(xué)習技術(shù)(自編碼器)對LBSNs中的地理進行建模，挖掘用戶的潛在偏好，并最終應(yīng)用于地點推薦任務(wù)。

2 基于地理鄰近性的深度自編碼器在地點推薦中的應(yīng)用

2.1 基于TF-IDF的簽到數(shù)據(jù)轉(zhuǎn)換

如前文所述，不同種類中的POI的簽到頻率不能同等看待，例如休閑場所(酒吧等)，用戶的簽到頻率注定會比較高。因此，本文將用戶的簽到頻率轉(zhuǎn)化為基于類別的偏好數(shù)據(jù)。

詞頻-逆向文檔頻率(Term Frequency-Inverse Document Frequency, TF-IDF)是一種在信息檢索中比較流行的加權(quán)技術(shù)。TF-IDF的初衷是衡量一個詞對于一個文檔的重要程度，該詞的重要程度與它在該文檔中出現(xiàn)的次數(shù)成正比，同時又與它在語料庫中的頻率成反比。因此，TF-IDF具有很好的類別區(qū)分能力。受此啟發(fā)，本文將TF-IDF技術(shù)用于計算類別在簽到頻率中的重要程度。

對于一個特定的用戶i，對于地點j的簽到頻率可以進行如下轉(zhuǎn)化：

(1)

其中，xij是用戶i對于地點j的簽到頻次,αij代表模型參數(shù)，而βij則代表基于TF-IDF類別的權(quán)重：

(2)

其中，Nik代表屬于類別k的，且用戶i簽到的POI數(shù)量,集合Cat表示類別集合。Nuser表示用戶總數(shù)，Nc表示去過類別c所屬的地點的用戶總數(shù)。

2.2 基于地理鄰近性的深度自編碼器

2.2.1 地理鄰近性

許多研究發(fā)現(xiàn)，同一個用戶簽到的POI之間的距離分布服從冪律分布(Power-law Distribution, PD)[7-9，14]，分布函數(shù)中的參數(shù)可以通過簽到數(shù)據(jù)估計得到，這種地理上的分布也被叫做地理鄰近性(Geographical Proximity)。因此，本文利用冪律分布計算POIs之間的地理鄰近性：

s=α×Dβ

(3)

其中，α和β代表冪律分布的參數(shù)，D代表同一個用戶簽到的2個POIs之間的距離，而s則表示2個POIs之間的地理鄰近性。用戶的簽到行為受到他們移動性的影響，這種用戶移動性可以通過他們簽到的POIs的距離分布表示。因此，本文利用基于冪律分布的地理鄰近性和簽到效用結(jié)合描述地理因素對于用戶的影響。

2.2.2 深度自編碼器

簡單的自編碼器(Auto-encoder)可以看做是一種3層神經(jīng)網(wǎng)絡(luò)[15-16]，分別是輸入層、隱藏層和輸出層。自編碼器的目的是輸出數(shù)據(jù)盡可能還原輸入數(shù)據(jù)，因此，其中輸入層到隱藏層之間的過程叫做編碼，而隱藏層到輸出層之間的過程叫做解碼。為了提高自編碼器的學(xué)習能力，可以將網(wǎng)絡(luò)擴展到多層，即隱藏層由多層網(wǎng)絡(luò)構(gòu)成，由此產(chǎn)生了深度自編碼器(Deep Auto-encoder,DAE)[17]。深度自編碼器由多層編碼網(wǎng)絡(luò)和多層解碼網(wǎng)絡(luò)組成，其中編碼網(wǎng)絡(luò)將輸入數(shù)據(jù)轉(zhuǎn)換到高層級特征表示，解碼網(wǎng)絡(luò)從高層級特征表示中還原數(shù)據(jù)。深度網(wǎng)絡(luò)中，每層特征表示抓取下一層單元之間的強關(guān)聯(lián)。

深度自編碼器的學(xué)習過程主要分為2個部分：逐層預(yù)訓(xùn)練和參數(shù)微調(diào)。首先逐層、貪婪地進行預(yù)訓(xùn)練，之后再利用后向傳播算法對網(wǎng)絡(luò)參數(shù)進行最后微調(diào)，這樣可以避免網(wǎng)絡(luò)陷入局部最小值。

1)逐層預(yù)訓(xùn)練。

本文將深度自編碼器中的每一層看做一個受限玻爾茲曼機，之后逐層訓(xùn)練受限玻爾茲曼機。每個受限玻爾茲曼機的輸出層作為下一個受限玻爾茲曼機的輸入，之后利用對比散度進行訓(xùn)練，這樣就形成了一個多層的編碼網(wǎng)絡(luò)。最后將訓(xùn)練后的多層編碼網(wǎng)絡(luò)復(fù)制展開成帶有相同權(quán)重的解碼網(wǎng)絡(luò)，形成深度自編碼器，至此，完成深度自編碼器的預(yù)訓(xùn)練過程。

2)參數(shù)微調(diào)。

深度自編碼器的參數(shù)微調(diào)過程類似傳統(tǒng)神經(jīng)網(wǎng)絡(luò)，首先訓(xùn)練數(shù)據(jù)進入網(wǎng)絡(luò)，逐層向后傳播并計算隱層，利用鏈式法則對損失函數(shù)進行求導(dǎo)，之后將數(shù)據(jù)的損失值(誤差值)逐層向后傳播，并逐層更新(微調(diào))網(wǎng)絡(luò)參數(shù)，直至收斂條件，則深度自編碼器訓(xùn)練完成。其中后向傳播是一種訓(xùn)練神經(jīng)網(wǎng)絡(luò)的流行方法，通過數(shù)據(jù)誤差的逐層向后傳播，不斷更新網(wǎng)絡(luò)參數(shù)。在后向傳播階段，本文采用輸入層輸出層之間的誤差來微調(diào)網(wǎng)絡(luò)權(quán)重。具體來說，對于每個訓(xùn)練數(shù)據(jù)t，集合Lt表示輸入層的數(shù)據(jù)單元集合，由此，本文定義誤差函數(shù)為總體平方誤差：

(4)

其中，yi表示輸入層單元i的真實值(輸入數(shù)據(jù))，oi∈Outputs表示輸出層單元i的預(yù)測值(模型預(yù)測值)。在本文中，對于每個訓(xùn)練實例t,只計算在真實數(shù)據(jù)集合Lt中的單元，缺失單元不納入損失函數(shù)中。

若訓(xùn)練集T中含有N個訓(xùn)練實例，則總體損失函數(shù)可以定義為：

(5)

其中，第一項是所有訓(xùn)練數(shù)據(jù)損失的平均值，第二項是正則項，用于減小參數(shù)量級帶來的影響，減緩過擬合問題。

2.2.3 深度自編碼器與地理鄰近性結(jié)合

假設(shè)所有的POIs數(shù)量是M，用戶數(shù)量是N，那么在輸入層就會有M個單元，代表所有的POIs。同時，每個用戶i都存在一個對應(yīng)的POI集合Li，代表該用戶簽到過的所有POI，并且集合Li中的所有POI都對應(yīng)于輸入層中的一個單元。假設(shè)在深度自編碼器中一共存在2R個網(wǎng)絡(luò)層，即存在R層編碼網(wǎng)絡(luò)和R層解碼網(wǎng)絡(luò)，在每一層中，本文用W(r)和b(r)表示第r層的連接權(quán)重和偏置。

然而，每個用戶簽到的POIs不盡相同，這意味著每個訓(xùn)練實例，都會在輸入層存在缺失值。本文中，每個用戶i都代表一個不同的自編碼器，并且每個自編碼器都有不同的輸入單元，代表不同的POIs。但是所有的自編碼器都共享相應(yīng)的權(quán)重和偏置，在模型訓(xùn)練階段，POI對應(yīng)的權(quán)重只會通過這些簽到過的用戶數(shù)據(jù)進行更新。

正常的DAE在輸入輸出層之間是沒有內(nèi)部鏈接的，但是在本文模型中，輸入輸出層代表POI，而且POI之間存在地理鄰近性，因此，DAE輸入輸出層之間必然存在關(guān)聯(lián)，即應(yīng)該存在內(nèi)部鏈接。由此，本文提出一種基于地理鄰近性的DAE模型(Geo-DAE)。在Geo-DAE中，本文在輸入輸出層之間加入內(nèi)部鏈接權(quán)重，并且該權(quán)重的值等于2個POIs之間的地理鄰近性(由公式(3)計算)。另外，該內(nèi)部權(quán)重不參與模型更新，即其值固定不變，只參與模型計算而本身不進行更新。因此，Geo-DAE的模型預(yù)訓(xùn)練和學(xué)習過程與傳統(tǒng)的DAE相似，唯一的不同在于計算輸入輸出值時，需要考慮內(nèi)部鏈接權(quán)重。

2.3 產(chǎn)生推薦

本文提出的模型可以輸出用戶對于所有POI的預(yù)測偏好，表示預(yù)測的興趣偏好，將這些偏好的預(yù)測值進行排序，之后輸出排名靠前的k個候選POI，即可形成推薦。

3 實驗及算法評價

3.1 實驗數(shù)據(jù)與評價指標

本文實驗部分使用了2個真實的LBSNs數(shù)據(jù)集進行實驗：Gowalla數(shù)據(jù)集和Foursquare數(shù)據(jù)集。具體信息如表1所示。

表1 Gowalla和Foursquare數(shù)據(jù)集中的統(tǒng)計數(shù)據(jù)

項目GowallaFoursquare用戶數(shù)量1545024829地點數(shù)量10458096890簽到數(shù)量412355772841

為了估計地點推薦系統(tǒng)的質(zhì)量，實驗部分采用如下評價指標：準確率(Precision)、召回率(Recall)和F1。如果給定推薦地點的個數(shù)K(K=5,10,15,20,25,30)之后，評價指標可以進行如下定義：

(6)

(7)

(8)

其中，S為測試集中地點集合，L為推薦列表中的地點集合。因此，準確率為推薦列表與測試集重合地點數(shù)在推薦列表中的占比，而召回率為所有簽到地點中被召回的比重。

3.2 對比算法

本文選擇了幾個典型的模型作為對比算法，與本文算法進行實驗對比。對比算法分別為：融合地理與社交信息的傳統(tǒng)協(xié)同過濾算法(Geo-CF)[7]、基于地理影響的概率因子模型(Geo-PFM)[5]、基于受限玻爾茲曼機的推薦算法(RBM)[11]。

1)Geo-CF。該方法是傳統(tǒng)的基于內(nèi)存的協(xié)同過濾算法，將基于距離的地理鄰近性和社交影響融入?yún)f(xié)同過濾算法之中。

2)Geo-PFM。Geo-PFM是經(jīng)典的基于模型的協(xié)同過濾算法，利用考慮了地理鄰近性的隱因子模型處理地點推薦任務(wù)。

3)RBM。該方法是基于受限玻爾茲曼機的傳統(tǒng)協(xié)同過濾推薦算法。

3.3 實驗結(jié)果分析

本文算法以及其他對比算法在準確率、召回率和F1這3個指標上的實驗結(jié)果如圖1所示。

從圖1中可以看出，本文算法Geo-DAE在2個數(shù)據(jù)集上的表現(xiàn)效果都要高于其他對比算法，具體實驗效果排名為：Geo-DAE,Geo-CF,RBM,Geo-PFM。

(a) Gowalla 數(shù)據(jù)集 (b) Foursquare數(shù)據(jù)集圖1 不同算法的實驗對比

本文算法Geo-DAE和協(xié)同過濾算法Geo-CF都考慮了地理鄰近性，Geo-DAE利用深度自編碼器與地理鄰近性結(jié)合，而Geo-CF則是利用基于樸素貝葉斯的傳統(tǒng)協(xié)同過濾技術(shù)與地理鄰近性進行結(jié)合。但是Geo-DAE算法實驗效果優(yōu)于Geo-CF，說明深度學(xué)習模型對地理鄰近性建模更有效，更適合地點推薦場景。深度學(xué)習技術(shù)可以在多層空間中隱式地學(xué)習數(shù)據(jù)中的潛在特征，因此對地理鄰近性也同樣具有優(yōu)勢。

本文算法利用Geo-DAE對地理鄰近性建模，并且實驗效果明顯優(yōu)于RBM，說明Geo-DAE對于地理角度的特征進行了有效的提取，在地點推薦領(lǐng)域具有優(yōu)勢。

另一個基于模型的算法Geo-PFM，在概率矩陣分解模型中加入地理因素，即在矩陣分解算法中加入一項基于距離的參數(shù)，來對地理鄰近性建模。雖然Geo-PFM同樣考慮了地理鄰近性，但是本文算法Geo-DAE的實驗表現(xiàn)更佳，這意味著本文提出的深度自編碼器可以更加有效地對地理鄰近性建模，在POI推薦領(lǐng)域Geo-DAE具有很大的潛力。

從圖1中可以看出，雖然都考慮了地理鄰近性，但是Geo-CF算法明顯優(yōu)于Geo-PFM算法。其中一個原因可能是：雖然Geo-PFM利用復(fù)雜的模型對地理鄰近性建模，但是簡單的樸素貝葉斯方法更適合對地理鄰近性建模。在這2種算法中，都利用了與冪律分布相關(guān)的函數(shù)計算地理鄰近性。但是在Geo-PFM算法中，算法首先利用多項式分布為用戶計算多個潛在活動區(qū)域，在區(qū)域內(nèi)部計算地理鄰近性。因此，Geo-PFM效果不佳的另一個原因可能是：整體來講，用戶的移動性(移動距離)服從冪律分布，但是在某個小的區(qū)域內(nèi)可能冪律分布并不能準確地描述用戶的移動性，由此導(dǎo)致Geo-PFM的推薦效果不如Geo-CF。因此，雖然地理鄰近性有助于提高地點推薦的效果，但如何計算地理鄰近性以及有效的建模方式同樣至關(guān)重要。有效的地理鄰近性計算方法和建模方式，更有利于挖掘地理因素對于用戶簽到行為的影響。

本章利用真實LBSNs中的簽到數(shù)據(jù)，對4種相關(guān)的算法進行了實驗和分析。通過與3種典型POI推薦算法的分析，證明了本文算法Geo-DAE在多種指標上都具有明顯優(yōu)勢。

4 結(jié)束語

本文先根據(jù)IF-IDF加權(quán)理論，將用戶簽到頻率轉(zhuǎn)換成基于類別的偏好數(shù)據(jù)。之后提出一種基于Geo-DAE的地點推薦算法，充分挖掘POI之間的地理鄰近性。最后為了驗證本文算法的有效性，利用真實數(shù)據(jù)進行了實驗分析，實驗結(jié)果證明本文提出的算法相對于對比算法具有明顯的優(yōu)勢。

參考文獻：

[1] Li Nan, Chen Guanling. Sharing location in online social networks[J]. IEEE Network, 2010,24(5):20-25.

[2] Liang Ting-peng, Lai Hung-Jen, Ku Yi-cheng. Personalized content recommendation and user satisfaction: Theoretical synthesis and empirical findings[J]. Journal of Management Information Systems, 2006,23(3):45-70.

[3] Cheng Chen, Yang Haiqin, King I, et al. A unified point-of-interest recommendation framework in location-based social networks[J]. ACM Transactions on Intelligent Systems and Technology, 2016,8(1): Article No. 10.

[4] 胥皇,於志文,封云,等. 基于LBSN的個性化旅游包推薦系統(tǒng)[J]. 計算機與現(xiàn)代化, 2014(1):186-191.

[5] Liu Bin, Xiong Hui, Papadimitriou S, et al. A general geographical probabilistic factor model for point of interest recommendation[J]. IEEE Transactions on Knowledge and Data Engineering, 2015,27(5):1167-1179.

[6] LeCun Y, Bengio Y, Hinton G. Deep learning[J]. Nature, 2015,521(7553): 436-444.

[7] Ye Mao, Yin Peifeng, Lee W C, et al. Exploiting geographical influence for collaborative point-of-interest recommendation[C]// Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2011:325-334.

[8] Brockmann D, Hufnagel L, Geisel T. The scaling laws of human travel[J]. Nature, 2006,439(7075):462-465.

[9] Gonzalez M C, Hidalgo C A, Barabasi A L. Understanding individual human mobility patterns[J]. Nature, 2008,453(7196):779-782.

[10] Zhang Jia-dong, Chow C Y. CoRe: Exploiting the personalized influence of two-dimensional geographic coordinates for location recommendations[J]. Information Sciences, 2015,293:163-181.

[11] Salakhutdinov R, Mnih A, Hinton G. Restricted Boltzmann machines for collaborative filtering[C]// Proceedings of the 24th International Conference on Machine Learning. 2007:791-798.

[12] Zhou Ningnan, Zhao W X, Zhang Xiao, et al. A general multi-context embedding model for mining human trajectory data[J]. IEEE Transactions on Knowledge and Data Engineering, 2016,28(8):1945-1958.

[13] Song Xuan, Zhang Quanshi, Sekimoto Y, et al. Prediction and simulation of human mobility following natural disasters[J]. ACM Transactions on Intelligent Systems and Technology, 2017,8(2): Article No. 29.

[14] Miller H J. Tobler’s first law and spatial analysis[J]. Annals of the Association of American Geographers, 2004,94(2):284-289.

[15] Hinton G E, Salakhutdinov R R. Reducing the dimensionality of data with neural networks[J]. Science, 2006,313(5786):504-507.

[16] 牛玉虎. 卷積稀疏自編碼神經(jīng)網(wǎng)絡(luò)[J]. 計算機與現(xiàn)代化, 2017(2):22-29.

[17] 曲建嶺,杜辰飛,邸亞洲,等. 深度自動編碼器的研究與展望[J]. 計算機與現(xiàn)代化, 2014(8):128-134.