基于地理位置和上下文偏好的使用Geos社會網(wǎng)絡的推薦系統(tǒng)

1、基于地理位置和上下文偏好的使用Geo社會網(wǎng)絡的數(shù)據(jù)的推薦系統(tǒng)摘要隨著基于位置的社會網(wǎng)絡逐漸流行，我們擁有了一個研究基于用戶歷史位置信息發(fā)現(xiàn)用戶偏好的良好平臺。在本文中，我們提出了一種基于位置和上下文偏好的推薦系統(tǒng)，該系統(tǒng)可以結合地理空間上的兩方面的信息，為特定的用戶推薦一系列的場所（如餐館），該系統(tǒng)需要考慮的信息包括：1）用戶偏好，用戶偏好可以通過從用戶的歷史位置信息自動學習到；2）社會評價，這個通過Local experts在位置信息中挖掘得到的。本文的推薦系統(tǒng)不僅可以在用戶的生活活躍區(qū)而且也可以在一個陌生的城市對人們的旅行進行幫助。由于一個用戶訪問地點數(shù)量的限制，用戶位置矩陣是非常稀疏的，

2、對于傳統(tǒng)的基于協(xié)同過濾算法的推薦系統(tǒng)來說是一個巨大的挑戰(zhàn)。矩陣稀疏問題對于一個剛到新城市的用戶來說更加嚴重。最后，我們提出了一種新穎的位置推薦系統(tǒng)，該系統(tǒng)主要包括兩個方面：離線模型和線上推薦。離線模型部分是通過類別層次權重（weighted category hierarchy,WCH）為用戶的個性化偏好進行建模并且推斷出每個用戶對于一個城市的知識通過不同類別的位置，根據(jù)用戶位置歷史信息使用迭代學習模型完成。在線推薦部分在地理空間上選擇候選Local experts，Local experts匹配了用戶的偏好通過使用一種感知偏好候選選擇算法，并且之后在基于已選擇的Local experts評價

3、意見中，推斷出一個對于候選位置的評分。最后，為用戶推薦出top-k的位置排名。我們的系統(tǒng)是在一個真實的大的數(shù)據(jù)集上進行評價的，該數(shù)據(jù)集搜集于Foursquare。我們的推薦結果比baseline推薦算法的效果更好，同時也可以退位置進行推薦。關鍵字：基于位置的社交網(wǎng)絡，基于位置的服務，用戶偏好，推薦系統(tǒng)簡介隨著位置信息獲得技術和無線通訊技術的發(fā)展，使得傳統(tǒng)社會網(wǎng)絡上可添加地理位置信息，滋養(yǎng)出一批基于位置的社交網(wǎng)絡服務（LBSN），例如，F(xiàn)oursquare，Loopt,和GeoLife，在這些應用服務上，用戶可以非常輕松地通過手機設備在現(xiàn)實世界中將自己的精彩生活分享出來。例如，一個用戶可以在一個

4、LBSN的站點對一家飯店的服務進行評價，之后在其他用戶去這家店時，就可以通過她的社交構成結構獲得這條評論。地理位置信息作為用戶上下文中重要組成之一隱含了大量信息，包括用戶個人興趣以及行為，這就提供給我們一個機會，那就是更好的了解用戶在一個社交結構中，不單單是用戶的線上行為，而且包括了用戶在現(xiàn)實生活中的流動性和活躍度信息。例如，如果一個人經(jīng)常去體育館，說明這個人很有可能細化體育鍛煉，如果一個人經(jīng)常去一家飯店去吃晚餐，則說明很有可能喜歡類似口味兒的飯店。有時，一些在物理位置上沒喲交集的人可能仍然是有聯(lián)系的，只要他們訪問過相同類別的地方就可以表明這些人有一種相同的興趣愛好，如到海邊或者到博物館。在這

5、種情形下，基于位置的推薦系統(tǒng)是非常有價值的，基于位置社交網(wǎng)絡服務已經(jīng)在【16,25】兩篇文章中有實現(xiàn)，特別的，位置推薦給一個用戶提供一些場所（例如一個意大利餐館或者是用戶喜歡的電影院），這些場所滿足在地理位置上滿足了人們的興趣需求【25】。當人們在一個陌生的地方旅游時，這種應用是非常有用的。然而，一個高質量的位置推薦系統(tǒng)必須同時滿足一下三個因素：1）用戶偏好：例如，一個吃貨會對一個高質量的飯店有興趣，而一個購物狂會將更多的注意力集中到附近的購物店【17】。2）用戶的當前位置：要想給用戶推薦用戶最感興趣的位置，當前用戶位置信息直接指出了用戶的空間范圍對于候選場所，并且可能會影響推薦的排名情況【1

6、4】。3）其他用戶對一個地點的意見：來自周圍用戶的社會意見對于推薦是非常有價值的【9】。但是一些大眾喜歡的場所不一定符合一個特別的用戶的口味。在LBSN上使用一個用戶的位置歷史信息，推斷計算出一個位置的分數(shù)是一件非常困難的事情。首先，一個用戶只能訪問到有限個物理位置，這種稀疏矩陣問題在位置推薦系統(tǒng)中經(jīng)常出現(xiàn)，例如【14】【9】，這些推薦方法都是基于物理位置的協(xié)同過濾的算法模型上的。其次，為一個沒到過幾個位置點的用戶在新的城市中推薦位置是一個很艱巨的任務（而這時人們往往又是最需要位置推薦的）。例如，在圖1中，a和b繪制出了位置信息（根據(jù)在Foursquare上的提示數(shù)據(jù)），這些位置信息是來自紐約

7、的人們訪問洛杉磯和紐約的分布情況。很明顯，訪問洛杉磯的紐約人很少，在他們的地理位置信息中，只有0.47%的數(shù)據(jù)信息這種現(xiàn)象在現(xiàn)實世界中是普遍存在的【20】。對于位置推理評分來說（如果我們想為紐約人推薦在洛杉磯的地理位置），這種現(xiàn)象加重了數(shù)據(jù)的稀疏性。在這種情況下，單獨使用CF模型是不適合的。首先，我們不能簡單的將用戶的來自不同城市的位置歷史信息放到一個用戶位置矩陣中，這種方法既沒有效果也沒有可擴展性。其次，在每個城市分別得使用協(xié)同推薦的方法不能處理新增城市問題，在圖1中顯示的問題。原因是 一個用戶通常不會有足夠的位置歷史信息在一個新的城市里?；诖?，我們提出了一個基于位置和用戶感知偏好的推薦系

8、統(tǒng)，該方法提供給特定的用戶一個場所集合，這些場所在用戶能夠接受的地理空間范圍之內，并且滿足前面提出的3個要考慮的因素。通過基于用戶位置歷史分類信息對用戶偏好進行建模在LBSN中，我們的推薦系統(tǒng)不僅可以在人們生活的附近幫助他們，而且還可以在一個陌生的城市幫助他們。構建位置推薦的兩大難點是：1）學習用戶的偏好。首先，一個用戶的偏好往往是各種興趣的一個合體，比如用戶偏好可能是購物，看電影，騎車，藝術等興趣的合體。一個用戶的偏好并不是一個簡單的二項選擇，例如，是喜歡還是不喜歡一些事物，并且，用戶偏好是有粒度的，如，“食物-意大利食物-意大利面”。再者，用戶的偏好是隨著時間的變化而變化的。人工指定用戶的

9、偏好是不實用的。因此，根據(jù)用戶的位置歷史信息對用戶偏好進行建模是件有挑戰(zhàn)的事。2）為一個用戶推斷一個沒有訪問過的地點的評分。評分的推斷需要兩個方面的考慮，一個是用戶偏好，另外一個是其他用戶的意見，尤其是Local experts【2,13】。以及用戶間的相似度。這種推斷要求三方面的計算：a）預測一個用戶的專業(yè)知識b）計算用戶之間的相似度c）將社交意見對于一個地點的推斷協(xié)同到前面兩者計算的合并結果中，例如使用系統(tǒng)過濾模型【8】【12】，他們彼此之間是相互聯(lián)系的?，F(xiàn)將我們的成果貢獻總結如下：1. 我們從一個用戶的歷史位置信息中學習用戶偏好，并且使用類別層次權值(WCH)對偏好進行建模。我們將會估計

10、兩個用戶偏好之間的相似度通過計算兩個用戶的WCHS的相似度得到。這個方法用于對用戶偏好進行建模并對位置稀疏問題進行解決。2. 我們提前計算和提取Local expert對一個城市的每個位置類別，使用一個建立在用戶位置歷史信息的迭代推理模型，這使得我們的在線推薦過程效率增強。3. 我們在線推斷一個場所的評分結合Local experts 選擇的候選集，這些候選集是通過偏好感應候選選擇算法和CF得到。這個算法可以實時給用戶一個地理位置，并且還能考慮到用戶的當前位置，偏好粒度，從Local experts中的意見。4. 我們評估我們的系統(tǒng)使用真實世界的數(shù)據(jù)，數(shù)據(jù)來源于Foursquare，包括221

11、,128個位置點信息，這些位置信息在紐約，由49,062個用戶產生，104478個在洛杉磯由31544個用戶產生的位置信息。我們的實驗結果說明我們的位置推薦比baseline方法更有效果。第二部分給出概述，第三部分和第四部分是系統(tǒng)實現(xiàn)的主要部分：離線模型和線上推薦。第五章是討論，第六章是總結相關工作。最后是總結全文。2概述這節(jié)首先介紹關鍵的數(shù)據(jù)結構，之后介紹了應用場景和位置推薦系統(tǒng)的整體架構。2.1 準備在圖2中顯示出五個關機的數(shù)據(jù)結構：1）user，2）venue，3）check-in，4）user location history，5）category hierarchy。在一個基于位置的

12、社交網(wǎng)絡中，一個用戶u需要維護他的個人信息，如ID，姓名，年齡，性別，籍貫等。同時，當用戶到達一個場所，并在LBSN中，在該場所進行簽到，那么該用戶可以標記該場所（如餐館）并對其進行評論，一個用戶可以訪問多個地點并可在每個地點進行簽到，如圖2 a)中實線部分。用戶的所有簽到信息影響該用戶的在現(xiàn)實生活中的位置歷史信息，像在squares地圖描述的那樣，一個場所的位置信息與一對地理位置坐標和表示其功能的一組類別相關聯(lián)。場所的類別有不同的粒度，如圖2a）底部所示。例如，食物類別包括中國餐館和意大利餐館等。在本系統(tǒng)中，我們使用從Foursquare獲取的兩層類別層次，如圖2b）所示。2.2應用場所圖3

13、顯示了一個我們的應用場景，在這個場景中，有N=10個場所匹配了用戶的偏好，這些場所是基于當前視角geo-地區(qū)進行推薦的，在此，推薦場所的數(shù)量以及地理區(qū)域的規(guī)模是由用戶決定的（通過放大縮小地圖區(qū)域，同時推薦地點的排名是在后天系統(tǒng)中完成的，根據(jù)用戶位置信息和其他用戶的意見）。通常，屬于一個類別推薦位置的數(shù)量是根據(jù)用戶偏好的類別分布而定的。例如，一個用戶（用戶的位置如圖3中釘子所在）的最喜歡的位置類別是“中國餐館”，第二個喜歡的是“購物中心”，那么，在圖3 a中，那么“中國餐館”的推薦力度就比“購物中心”的大，當這個用戶在唐人街時。當我們將位置定位到第七街時，如圖3b所示，購物中心將會最主要的推薦選

14、項，盡管中國餐館是用戶的第一興趣，即跟用戶所處的地理環(huán)境有關系。原因是根據(jù)人們在特別區(qū)域的位置歷史記錄，購物中心比中國餐館更有價值。這是對個人偏好和社會評價的一個權衡。2.3 系統(tǒng)結構離線模型：離線模型主要由兩個方面構成：1）社會知識學習；2）個人用戶偏好發(fā)現(xiàn)。如圖4下半部分所示。對于社會知識學習過程，每個用戶在每個類別的專業(yè)知識根據(jù)用戶位置歷史信息得到。給一個預先定義好的類別層次，如圖2b，我們將用戶在一個城市中的位置歷史信息break出來并分到不同的位置類別組中。之后，我們對每個位置歷史信息類別組使用用戶位置矩陣進行建模，在矩陣中，每個條目指示一個用戶對地點的訪問次數(shù)。通過應用一個迭代的推

15、斷模型對每個用戶位置矩陣，我們計算出一個得分W.r.t是對每個用戶的一個類別，表示一個用戶在一個城市中的類別的專業(yè)知識。通過對類別得分進行排序，我們可以發(fā)現(xiàn)在一個城市中的不同類別的Local experts。每個用戶的推斷知識將會在之后的感應偏好候選算法中使用，以及對在線部分產生高效地推薦而使用較少的計算。對于第二部分模型，即個人偏好發(fā)現(xiàn)，每個用戶的個人偏好使用一個WCH，利用位置類別信息根據(jù)用戶的位置歷史，使用這種方法可以克服數(shù)據(jù)稀疏問題。特別地，一個WCH是一個預先設定的類別層次的子樹，每個節(jié)點攜帶了關于用戶訪問一個類型的次數(shù)。這些值將被進一步規(guī)范化在每一個使用TF-IDF的WCH層在線推

16、薦模型：在線推薦部分給每個用戶提供了一個場所列表，考慮每個用戶的偏好，當前的位置，來自被選擇的Local experts的社會評價，具體細節(jié)分成兩個部分：1）感知偏好候選選擇。這個部分是選擇一個Local experts集合，這些experts是訪問過這些場所，這些場所是在用戶的推薦范圍R之內的，并且在用戶喜歡的類別中，這些experts有一個很高的專業(yè)知識。一個感知偏好候選選擇算法被構造出來是為了適當?shù)倪x擇Local experts從不同的類別，這些類別是根據(jù)一個用戶的不同的偏好權重在用戶的WCH中的取得。2）位置評分計算。這部分第一個要計算的是每個被選擇的Localexperts和用戶的相

17、似度，相似度的計算是使用相似度函數(shù)基于他們的WCHs。計算相似度得分將會被引入到CF模型中，計算出一個評分用來預測該用戶對一個未訪問過的場所的喜好程度。之后，這些場所推薦得分將會被返回到作為推薦部分的內容。3離線模型在這個章節(jié)中，我們的離線模型包括：1）社會知識學習，這個是評價一個用戶的專業(yè)知識并發(fā)現(xiàn)一個城市中的Local experts；2）個人偏好發(fā)現(xiàn)。這個事提取出一個用戶的偏好從他的位置歷史信息中。3.1 社會知識學習為了識別一個位置類別的Local experts，比如像“中國飲食”，“購物中心”等類別，這個部分要計算一個用戶在不同城市中的每個類別，以封裝在用戶位置歷史信息為基礎。直觀

18、的，一種類別的Local experts能夠比普通用戶發(fā)現(xiàn)高質量的該種類型的場所。再者，使用Local experts我們可以忽略一些極少的用戶，這些用戶只有很少的數(shù)據(jù)信息在位置類別上。這樣就可以減少一些不必要的在線計算量。在我們的方法中，我們首先將說的用戶位置歷史信息進行分割，通過城市來分割，因為一個用戶的的知識一般是通過地理信息得到的。例如，一個紐約旅游experts也許對北京的一些有趣的場所是不清楚的。再者，用戶也許在不同的位置類別中有不同的知識儲備，比如，一個喜歡“中國餐飲”的用戶不需要知道太多關于“意大利餐飲”的知識，這樣，我們進一步分割用戶在一個城市中的那些用戶訪問過的位置歷史信息

19、。最終，一個城市中有n個用戶-位置矩陣，其中，n是預定的類別的總數(shù)。之后，我們應用HITS（超文本誘導主題搜索），基于推薦模型【4】【10】，對每個基于類別的的用戶位置矩陣，推斷出一個用戶對于該類別的專業(yè)知識程度。如圖5，本方法認為一個用戶對一個場所的訪問產生一條從用戶到場所的有向邊，每個用戶有一個hub score來代表他的知識水平，每個位置被用戶連接，其擁有一個authority score用來表示他的興趣度。【29】這樣，那些在同一地區(qū)訪問過許多高質量的場所的人就有豐富的關于這個區(qū)域的專業(yè)知識。反過來，一個被許多擁有專業(yè)知識的人訪問過的場所就是高質量的場所。這樣，如公式1和2 所示，一個

20、用戶的專業(yè)知識能夠使用被該用戶訪問過的場所的authority score（例如興趣等級）之和進行計算，一個場所的的興趣等級可以使用那些訪問過該場所的用戶的Hub score之和進行計算。使用一個強大的迭代推到方法，我們產生了一個最終的對于每個用戶和每個場所的得分公式，那些擁有高authority score的用戶被認為是Local experts在這個類別中。其中，代表在類別c中用戶u的Hub score，代表場所v的authority score。我們定義分別代表在第n次迭代的authority scores和Hub scores，M代表用戶-類別矩陣，那么最終的結果是：其中，我們初始化a

21、uthority和Hub score使用一個用戶訪問的次數(shù)。?3.2 個人偏好發(fā)現(xiàn)我們提取用戶的偏好是通過用戶訪問的地點的類別得到的。如圖6，首先，我們構建一個用戶位置歷史信息根據(jù)所有的已經(jīng)預定義好的類別層次的城市，那些節(jié)點出現(xiàn)的層次越低說明劃分粒度越細。這樣，每一個節(jié)點和一個值聯(lián)系起來，這個值代表一個用戶對于一個類別的訪問次數(shù)。在實際中，一個人的偏好是由多重興趣構成。（比如購物和徒步旅行），而這些多重興趣又有不同粒度的劃分，例如，“餐飲”-“中國餐飲”。第二，我們計算了在一個層次中每個節(jié)點的TF-IDF值，其中，每個用戶的位置歷史信息看做一個文檔，類別認為是在該文檔中的一個條目。直觀上看，一

22、個用戶喜歡一個地點的類別，那么他將經(jīng)常訪問這種類別的地方。更進一步，如果一個用戶經(jīng)常訪問一個其他用戶很少訪問的地方，那么該用戶會更喜歡屬于這種類型的地方。例如，餐館的訪問次數(shù)就遠比像博物館這樣類別地方的多。這并不意味著餐飲就是所有人的第一大興趣，這時，如果發(fā)現(xiàn)一個用戶經(jīng)常去訪問博物館，那么他的興趣領域很可能是藝術或歷史方面的?？傊粋€用戶的偏好權重可用公式5進行計算，其中，第一部分的等式是在一個用戶的位置歷史中類別c的TF值，第二個部分代表一個類別的IDF值。其中，是一個用戶在類別c中訪問的個數(shù)，是代表用戶總體的訪問次數(shù)。代表在系統(tǒng)中訪問過類別c的用戶數(shù)，經(jīng)過計算之后，使用IDF，計算WCH

23、，中國餐館不再是用戶的第一興趣，顏色變淺。這個WCH代表了用戶的興趣。就有下面的有優(yōu)點：1）由于不同的用戶有不同的數(shù)據(jù)規(guī)模，使用WCH可以不用考慮數(shù)據(jù)規(guī)模2）可處理稀疏數(shù)據(jù)的問題，并可減少計算下面介紹的用戶相似度計算量3）可以計算用戶間的相似度，這些用戶是沒有任何物理位置信息的，如生活在不同的城市。4 在線模型在線模型主要包括：1）感應偏好候選集選擇。這個根據(jù)用戶的偏好選擇候選Local expert。2）地點評分計算。這是指一個候選地點的預測評分，基于CF推斷模型，使用相似度對用戶和被選擇的Local experts進行比較。4.1 偏好候選集選擇這個部分選擇一組候選Local expert

24、s和場所在用戶指定的地理范圍內，使用我們的偏好候選選擇算法（如算法1所示），該算法可以保證候選地點符合用戶指定的個數(shù)并且候選Local experts也匹配用戶的偏好。特別的，用戶制定一個地理范圍R，這個算法一開始檢索位于這個地理范圍的的場所集合V和訪問過這些場所的用戶集合U（第1,2行）。候選Local experts選擇過程從個人的WCH的底層進行初始化，如果候選場所的數(shù)目沒有達到要求的推薦的數(shù)目則將移入上一層。當在WCH的一層中選擇好了場所，我們將選擇一個節(jié)點（一個類別），這個節(jié)點具有最小值，之后，我們計算一個k值使用來決定我們要在這個類別中國要選的Local experts的個數(shù)，之后

25、，前k個擁有高Hub score的用戶在類別c中的被選擇出來作為候選experts e （第7-8行），那些分布在R范圍內的并被e中的用戶訪問過的場所將會被加入到V中，之后，候選experts集合e和集合E合并（第9-11行）。算法會在我們獲得了一個足夠數(shù)量的場所集合或者所有在R范圍內的用戶都被檢索完成時結束。作為結果，一個地點集合V和一個Local experts結合E將被返回。4.2位置評分推斷第一步：用戶相似度計算。在這一步中，我們將要計算一個提出推薦請求的用戶和Local experts E中的每個expert計算相似度得分根據(jù)他們的WCHs。因為從本質上看，WCH是一顆樹，我們計算兩個WCH的相似度，通過哪些樹中重疊的節(jié)點。特別的，我們分解兩個WCHs的相似度作為一個權重和，這個和是在每一WCH中對應的層次的相似度，例如。層次越深權重越大，這樣符合用戶的偏好。更進一步，連個不同的WCH的同一層的相似度是通過下面兩個方面計算：一方面是在同一層中重疊的個數(shù)和他們的值，如等式6所示。兩個WCH重疊的個數(shù)越多，兩個用戶就月相似。最小的重疊節(jié)點c的偏好權重會被選出來作為兩個用戶的共同興趣。另外一個部分是每個層次的熵，這個熵可以有效的計算一個用戶偏好的多樣性【7】，如等式7所示。其中，是一個戶