涂飛

（重慶理工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，重慶 400054）

基于位置的社交網(wǎng)絡(luò)LBSN[1](location based social network)實(shí)現(xiàn)了用戶對其訪問地理位置的簽到功能，并能夠發(fā)布相應(yīng)的評論、圖片、視頻信息與好友分享。通過LBSN可以提供好友推薦[2-3]、興趣點(diǎn)推薦[4-5]等多種個性化服務(wù)。興趣點(diǎn)推薦的目標(biāo)是向特定用戶推薦滿足其需求的、具有一定長度的未知興趣點(diǎn)列表，來增強(qiáng)用戶體驗。一般來說，推薦的興趣點(diǎn)包括地點(diǎn)(如飯館、商場、公園和影院等)和活動(如演唱會、公益活動等)兩類。與傳統(tǒng)電子商務(wù)網(wǎng)站的推薦系統(tǒng)不同，興趣點(diǎn)推薦有如下的特性：

1) 數(shù)據(jù)的弱語義性：傳統(tǒng)的推薦系統(tǒng)中，用戶對商品的評分是顯現(xiàn)的，可以表達(dá)其偏好程度，如五級評分制中5代表很喜歡，而1代表不喜歡。在興趣點(diǎn)推薦系統(tǒng)中，只能獲取用戶對興趣點(diǎn)的訪問次數(shù)，而簽到次數(shù)的多少并不能反映用戶的偏好程度。換句話說傳統(tǒng)的推薦數(shù)據(jù)中同時包含正例和負(fù)例，而興趣點(diǎn)推薦數(shù)據(jù)僅包含正例，這就使得很多成熟的推薦方法如協(xié)同過濾算法等并不直接適用于興趣點(diǎn)推薦。

2) 數(shù)據(jù)的稀疏性：用戶對興趣點(diǎn)的簽到矩陣相比于傳統(tǒng)的用戶-商品評分矩陣更加稀疏，如國外著名的LBSN網(wǎng)絡(luò)——Gowalla的數(shù)據(jù)稀疏度為2.08×10-4。傳統(tǒng)的推薦算法難以直接適用于興趣點(diǎn)推薦。此外用戶的歷史活動記錄具有聚集性，通常只集中在居住地或工作地等少數(shù)幾個區(qū)域。當(dāng)用戶外出時，由于缺少該區(qū)域的歷史簽到記錄無法做出準(zhǔn)確的推薦。

3) 社交影響不大：傳統(tǒng)在線社交網(wǎng)絡(luò)上的“朋友”往往具有相似的興趣愛好，因此很多推薦算法通過引入社交關(guān)系來處理數(shù)據(jù)的稀疏性問題，提高效率。但是在LBSN中的“朋友”不一定具有相同的興趣愛好，引入社交關(guān)系對興趣點(diǎn)推薦影響不大。

鑒于此，本文提出了一種新的推薦模型——用戶-內(nèi)容-區(qū)域主題模型(user-content-region topic model, UCRTM)。該模型同時分析了用戶興趣、地點(diǎn)特定主題以及所屬地理區(qū)域主題等多個特征，以隱含主題為基礎(chǔ)，用統(tǒng)一的框架將各種特征進(jìn)行融合，在一定程度上克服了用戶簽到數(shù)據(jù)的稀疏性和弱語義性等問題，實(shí)驗證明能獲得較好的用戶體驗。

1 相關(guān)工作

目前基于位置社交網(wǎng)絡(luò)的興趣點(diǎn)推薦算法可歸納為3類：

1) 傳統(tǒng)推薦算法的直接運(yùn)用：這類方法認(rèn)為用戶對興趣點(diǎn)的簽到次數(shù)能夠代表其偏好程度，構(gòu)造用戶-興趣點(diǎn)簽到矩陣并利用傳統(tǒng)的推薦算法進(jìn)行推薦。如：文獻(xiàn)[6]提出的基于用戶和興趣點(diǎn)的混合協(xié)同過濾算法；文獻(xiàn)[7]提出的基于正則化矩陣分解(RMF)算法和文獻(xiàn)[8]提出的概率矩陣分解(PMF)算法等。這類方法的本質(zhì)是盡量完善推薦模型，但由于數(shù)據(jù)集本身過度稀疏，以及數(shù)據(jù)的弱語義性導(dǎo)致推薦質(zhì)量并不高。

2) 引入地理因素的推薦算法：在LBSN中，用戶與興趣點(diǎn)的地理距離也是推薦的重要因素，這也是有別于商品推薦的重要特征，這類算法將地理信息融入到模型中，如文獻(xiàn)[6]認(rèn)為用戶簽到的興趣點(diǎn)在地理位置上是符合冪律分布，文獻(xiàn)[8]則認(rèn)為用戶的活動區(qū)域是圍繞多個中心點(diǎn)展開的，進(jìn)而引入了多中心高斯分布模型。事實(shí)證明對地理信息建模有助于推薦效果的提升。

3) 引入社交影響的推薦算法：這類方法認(rèn)為社交網(wǎng)絡(luò)上的“朋友”擁有相同的興趣愛好，結(jié)合朋友的簽到訪問歷史記錄進(jìn)行推薦，如文獻(xiàn)[9]利用相似用戶進(jìn)行推薦時，直接利用好友進(jìn)行推薦，而忽略LBSN中其他用戶。文獻(xiàn)[8]將社交關(guān)系直接融入到矩陣分解(PMF)算法中，但是實(shí)驗證明社交關(guān)系對推薦準(zhǔn)確率的影響不大。

還有一些方法同時考慮了地理因素、用戶的偏好以及社交關(guān)系。如文獻(xiàn)[10]設(shè)計了一種UPS(user, proximity and social-based)算法，將社交影響因子融合到基于用戶偏好的協(xié)同過濾算法中，以此來提高用戶相似度計算的準(zhǔn)確性。實(shí)驗證明該算法在稀疏數(shù)據(jù)環(huán)境下的推薦效果并不是很好，而且該算法沒有考慮用戶在不同的地理位置的影響。文獻(xiàn)[11]提出了USG (user, social and geographical influence based recommendation)推薦算法，綜合考慮了用戶偏好、社交影響和地理影響，采用線性融合技術(shù)集成這3種因素,以此來提高算法的準(zhǔn)確率。該方法雖然考慮了地理因素，但是只考慮了用戶常駐地特征，推薦的地點(diǎn)都是常駐地附近區(qū)域，而且算法的參數(shù)不能自適應(yīng)地調(diào)節(jié)。此外還有很多學(xué)者利用概率產(chǎn)生式模型對位置社交網(wǎng)絡(luò)的推薦系統(tǒng)進(jìn)行研究，將影響用戶簽到?jīng)Q策的各種因素進(jìn)行綜合考慮和集成，比如文獻(xiàn)[12]提出的LCARS系統(tǒng)從用戶興趣、地理位置、興趣點(diǎn)當(dāng)?shù)靥厣?個方面分析，來對用戶的簽到行為進(jìn)行建模，文獻(xiàn)[13]提出的JUMAI系統(tǒng)更是從用戶興趣、興趣點(diǎn)所在區(qū)域與用戶所在區(qū)域的距離、簽到時間，以及興趣點(diǎn)類別4個角度來指導(dǎo)簽到?jīng)Q策。文獻(xiàn)[14]在此基礎(chǔ)上還考慮了用戶在新的地點(diǎn)會產(chǎn)生興趣漂移情況。但是這些模型均沒有考慮興趣點(diǎn)本身的內(nèi)容，其次上述模型在對各因素進(jìn)行建模時，沒有體現(xiàn)自適應(yīng)的特性，即針對不同的興趣點(diǎn)，何種因素對決策起支配作用。本文提出了用戶-區(qū)域-內(nèi)容主題模型，真實(shí)地模擬了用戶對興趣點(diǎn)簽到的決策過程，實(shí)驗證明在稀疏的數(shù)據(jù)集下有較理想的推薦效果。

2 用戶-區(qū)域-內(nèi)容主題模型

2.1 模型介紹

用戶是否會對特定的興趣點(diǎn)簽到，會受到以下3種因素的影響：

1) 用戶自身偏好的影響：一般來說，只有興趣點(diǎn)滿足用戶的喜好，用戶才會欣然前往并產(chǎn)生簽到行為。比如球迷可能去看CBA聯(lián)賽，而音樂愛好者可能去聽演唱會。

2) 興趣點(diǎn)自身內(nèi)容的影響：LBSN中基本包含了對興趣點(diǎn)的介紹信息，圖1是豆瓣活動網(wǎng)站的頁面信息，該頁面顯示了活動的時間、地點(diǎn)以及主題。當(dāng)用戶瀏覽該頁面時，可能被活動的主題信息中某個特征所吸引，才促使了用戶的簽到行為。

圖 1 興趣點(diǎn)簡介Fig. 1 A brief introduction of interest points

3) 興趣點(diǎn)所屬區(qū)域的影響。用戶根據(jù)自身愛好或是事先知曉興趣點(diǎn)的內(nèi)容而產(chǎn)生的簽到行為可認(rèn)為是有目的，有主觀傾向性的。但并不是所有的訪問簽到行為都是如此。用戶的某次簽到行為可能開始是漫無目的的，只是隨機(jī)選擇某一地理區(qū)域的某一興趣點(diǎn)。但是此處的隨機(jī)也受以下兩點(diǎn)約束：1)興趣點(diǎn)所屬區(qū)域離用戶的距離。當(dāng)該區(qū)域離用戶較近時，被用戶訪問的概率較大，否則訪問概率較小。2)區(qū)域的主題。當(dāng)用戶外出到新的區(qū)域時，對該區(qū)域一無所知，也無法從其“相似用戶”獲得信息，在做決策是否訪問某一興趣點(diǎn)時，往往會受到該區(qū)域主題的影響。比如該區(qū)域的風(fēng)俗習(xí)慣、當(dāng)?shù)厝说呐d趣喜好，或是當(dāng)?shù)乇容^著名的人文景點(diǎn)等。

用戶對興趣點(diǎn)簽到，必定是受到以上3種因素其中之一的影響。因此本文提出了一種基于用戶-區(qū)域-內(nèi)容的聯(lián)合推薦模型，利用隱主題因子表示上述3種因素，將用戶對3種因素的選擇過程進(jìn)行建模。

2.2 模型的形式化

圖2為用戶-區(qū)域-內(nèi)容聯(lián)合推薦模型對應(yīng)的概率圖。該圖右邊的部分是一個簡單的LDA模型，構(gòu)造了興趣點(diǎn)描述文檔的生成過程。當(dāng)用戶對興趣點(diǎn)簽到時的介紹文檔已經(jīng)存在,文檔和單詞的主題分布可分別獨(dú)立計算。當(dāng)用戶對興趣點(diǎn)簽到時，首先要確定的主題，有3種來源，分別為興趣點(diǎn)介紹文檔中出現(xiàn)過的主題、用戶的興趣以及興趣點(diǎn)所屬地理區(qū)域的主題。采用選擇變量來控制興趣點(diǎn)的主題的來源，滿足多項式分布，其值分別為user、region 和 content。

圖 2 用戶-區(qū)域-內(nèi)容聯(lián)合推薦模型Fig. 2 User-content-region based joint recommendation model

2.3 確定參數(shù)值

模型中變量的聯(lián)合概率分布為

由式(1)可知該模型需要估計以下6個參數(shù)：1)文檔的主題分布；2)主題-詞分布(參數(shù)1)、2)為基本LDA模型對應(yīng)的參數(shù)，用于求)；3)興趣點(diǎn)的主題分布(即)；4)用戶興趣分布；5)用戶活動區(qū)域分布；6)選擇概率的多項式分布(即)。

文中采用Gibbs抽樣方法，過程如下，具體的參數(shù)說明見表1。

表 1 模型參數(shù)說明Table 1 Model parameter description

1) 利用式(2)計算單詞在主題上的后驗概率，進(jìn)而對單詞的主題進(jìn)行抽樣，

2) 計算興趣點(diǎn)主題的后驗概率，分3種情況：

①當(dāng)選擇變量x=user時，抽樣方程為

②當(dāng)選擇變量x=document時，抽樣方程為

③當(dāng)選擇變量x=region時，抽樣方程為

當(dāng)式(2)～(5)迭代一定次數(shù)后狀態(tài)穩(wěn)，可用式(6)～(14)近似計算模型的參數(shù)值。

2.4 模型的推薦

這也在一定程度上解決了用戶或資源的冷啟動問題。

3 實(shí)驗結(jié)果與分析

3.1 數(shù)據(jù)集

豆瓣活動是我國最大的社交網(wǎng)絡(luò)，用戶可以在該平臺上發(fā)布和參與各類活動并簽到。該數(shù)據(jù)集包含了100 000多個用戶，300 000個事件，以及3 500 000條簽到記錄。本文經(jīng)過預(yù)處理后選擇了其中20 000個用戶、15 000個活動的150 000條簽到記錄作為實(shí)驗數(shù)據(jù)集。

Foursquare是一個大型的公開數(shù)據(jù)集，該數(shù)據(jù)集包含11 326個用戶，182 968個興趣點(diǎn)，實(shí)驗中通過篩選選擇其中10 000個用戶、25 000個興趣點(diǎn)進(jìn)行分析。

3.2 實(shí)驗結(jié)果

為了驗證算法的準(zhǔn)確性，本文采用了文獻(xiàn)[15]提出的評估方法,具體如下：

1)對于任意用戶u，隨機(jī)選擇其簽到數(shù)據(jù)中的90%作為訓(xùn)練集S，剩余的10%作為測試數(shù)據(jù)集T。由于本文要分別計算算法對本地興趣點(diǎn)和外地興趣點(diǎn)推薦的準(zhǔn)確率，T根據(jù)不同的情況劃分為本地數(shù)據(jù)和外地數(shù)據(jù)(以興趣點(diǎn)所屬城市來區(qū)分)。

2)在測試過程中，隨機(jī)選擇用戶u尚未簽到的200個活動構(gòu)成集合E，假設(shè)這些活動是用戶不感興趣的。

3)將包含用戶u的測試集中任意活動e加入到E中構(gòu)成201個新的活動集合，根據(jù)推薦算法選擇評分最高的前200個活動作為top-200推薦列表，如果活動e出現(xiàn)在推薦列表中，將hits增1，否則hits保持不變(hits為評分常量)。

4) 評估標(biāo)準(zhǔn)查全率為

本文選擇以下4種算法進(jìn)行比較：

1) 文獻(xiàn)[17]提出的IKNN算法(item-based knearest neighbors algorithm)，該算法利用 “近鄰用戶”來推薦感興趣的活動，然后根據(jù)活動地點(diǎn)離用戶的遠(yuǎn)近進(jìn)行過濾，優(yōu)先選擇離用戶較近的感興趣的活動。

2)文獻(xiàn)[16]提出了CKNN算法(categorybased k-nearest neighbors algorithm)，該方法實(shí)質(zhì)上也是協(xié)同過濾，將用戶的興趣映射到具體的主題，進(jìn)而進(jìn)行推薦。

3) 文獻(xiàn)[11]提出的 USG推薦算法，該算法的核心思想還是協(xié)同過濾，線性框融合用戶偏好、社交影響和地理影響這3種因子。

4) User-Content Topic Model(UCTM) 模型和User-Region Topic Model (URTM)模型，這兩種模型可看作UCRTM模型的子模型。當(dāng)=0時，此時模型忽略興趣點(diǎn)介紹文檔的內(nèi)容信息，UCRTM模型退化為URTM模型。當(dāng)=0時，此時模型忽略興趣點(diǎn)所處區(qū)域的主題信息，UCRTM模型退化為UCTM模型。

3.3 實(shí)驗結(jié)果

該模型有9個超參數(shù)需要設(shè)置，對于主題模型來說，超參數(shù)的值對最后的輸出結(jié)果影響不大，但是會影響模型的收斂速度，這里設(shè)置、、、為 0.1，、為 0.05， 所有的值為0.01。

1) UCRTM模型為概率產(chǎn)生式模型，本文使用困惑度(Perplexity)作為評價標(biāo)準(zhǔn)， 對本模型的預(yù)測能力進(jìn)行評估，判斷測試集Dtest中興趣點(diǎn)生成的不確定性，Perplexity的值越小，表示模型生成興趣點(diǎn)的性能越好。Perplexity的計算式為

式中p(ld)由式(15)或(16)得出。由于本模型中包含了兩個隱含變量(主題數(shù)和區(qū)域數(shù))，為了分析這兩個變量對模型生成能力的影響，首先固定隱含區(qū)域數(shù)，來觀察Perplexity隨不同主題數(shù)的變化情況。

從圖3可以看出，當(dāng)區(qū)域個數(shù)固定為R=30時，對于不同的主題數(shù)，Perplexity 均隨著迭代次數(shù)的增加不斷減小，當(dāng)?shù)螖?shù)達(dá)到40次后，Perplexity趨于收斂。而且Perplexity還隨著主題數(shù)K的增大不斷減小，當(dāng)主題數(shù)增加到一定程度后，Perplexity不會持續(xù)下降，反而會有一些回升。如當(dāng)K=160時， Perplexity的值相比于K=80時反而增大了，這也在一定程度上說明，合適的主題數(shù)K可以提高模型的推薦效果。同理固定主題數(shù)K=80，來觀察隱含區(qū)域數(shù)R對Perplexity的影響。如圖4所示，區(qū)域數(shù)與主題數(shù)的變化情況類似，當(dāng)R=30時，可以得到最小的Perplexity值。因此本實(shí)驗中主題數(shù)K設(shè)置為80，而區(qū)域數(shù)R為30。

圖 3 困惑度在不同隱含主題下的變化情況Fig. 3 The perplexity changes in the number of different hidden themes

圖 4 困惑度隨不同隱含區(qū)域下的變化情況Fig. 4 The perplexity changes in the number of different hidden region

2) 其次比較了各種算法的推薦準(zhǔn)確率，因為用戶的簽到具有地域聚集性，本文將測試集分為兩類：用戶的本地活動測試集、用戶的外地活動測試集。對豆瓣數(shù)據(jù)集和Foursquare數(shù)據(jù)集進(jìn)行了分析。圖5～8分別給出了6種算法在兩種數(shù)據(jù)集下的top-N推薦準(zhǔn)確率，推薦列表的長度N在2～20變化。

圖 5 豆瓣數(shù)據(jù)集外地活動的推薦準(zhǔn)確率比較Fig. 5 Comparison of recommended accuracy out of town for Douban dataset

圖 6 Foursquare數(shù)據(jù)外地活動的推薦準(zhǔn)確率比較Fig. 6 Comparison of recommended accuracy out of town for Foursquare dataset

圖 7 豆瓣數(shù)據(jù)集本地活動的推薦準(zhǔn)確率比較Fig. 7 Comparison of recommended accuracy in locality for Douban dataset

圖 8 Foursquare數(shù)據(jù)本地活動的推薦確率比較Fig. 8 Comparison of recommended accuracy in locality for Foursquare dataset

由圖5和圖6可以看出，隨著N的不斷增加，各種算法的準(zhǔn)確率都是不斷提高的。對于外地活動的推薦,UCRTM、UCTM、URTM優(yōu)于USG、CKNN、IKNN算法，因為后3種方法為協(xié)同過濾算法，數(shù)據(jù)的稀疏性對其影響較大，用戶或地點(diǎn)相似性在稀疏的環(huán)境下計算不準(zhǔn)確，導(dǎo)致推薦準(zhǔn)確率不高。由于USG算法考慮了社交好友的影響，推薦效果略好于CKNN和IKNN算法。而隱含主題模型受數(shù)據(jù)稀疏性的影響較小，在模型中興趣點(diǎn)的隱含主題同時由用戶興趣分布、興趣點(diǎn)介紹文檔主題分布以及興趣點(diǎn)所屬區(qū)域的主題分布的影響，這些信息是對用戶簽到數(shù)據(jù)的有益補(bǔ)充。UCTM和URTM均只考慮了其中兩方面的影響，所以其推薦的準(zhǔn)確程度不如UCRTM模型。

由圖7和圖8可以看出，在本地活動推薦中，UCRTM模型同樣優(yōu)于其他各種方法，但考慮到用戶本地簽到的數(shù)據(jù)較多，采用協(xié)同過濾類的算法本身能夠準(zhǔn)確計算用戶的相似性，不需要其他補(bǔ)充信息也能獲得較高的準(zhǔn)確率，因此最終各種方法的性能差距不大。但是本模型能夠擴(kuò)展更多的上下文信息，可靠性更高。

4 結(jié)束語

本文提出的用戶-區(qū)域-內(nèi)容聯(lián)合推薦模型能夠克服數(shù)據(jù)稀疏性以及弱語義性的影響，與其他方法相比有較高的推薦的準(zhǔn)確率。以后還將進(jìn)一步改善模型，增加環(huán)境、時間等上下文因素。其次該模型除了應(yīng)用于興趣點(diǎn)推薦外，還能將學(xué)習(xí)出的重要參數(shù)(如用戶的興趣愛好、用戶的活動特性、地理區(qū)域的主題等)用于其他的web服務(wù)中。