王亞男

（重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶 400030）

0 引言

近年來(lái)，隨著定位技術(shù)的民用化，基于位置的社交網(wǎng)絡(luò)服務(wù)迅速發(fā)展，興趣點(diǎn)呈爆炸式增長(zhǎng)，所以一個(gè)旨在幫助用戶過(guò)濾興趣點(diǎn)，減少其抉擇時(shí)間的推薦系統(tǒng)成為了迫切需要的服務(wù)。目前存在很多關(guān)于興趣點(diǎn)推薦的研究。舉個(gè)例子，Zheng等[1]首次運(yùn)用基于用戶的協(xié)同過(guò)濾方法進(jìn)行興趣點(diǎn)推薦。Hu等[2]對(duì)包含簽到興趣點(diǎn)和未簽到興趣點(diǎn)兩類數(shù)據(jù)的矩陣進(jìn)行矩陣分解。Cheng等人[3]把用戶在位置上的簽到概率模型模擬為多中心高斯模型來(lái)捕獲地理因素，繼而把社交信息和地理信息融入到一個(gè)廣義的矩陣分解模型中。Ye等人[4]綜合基于用戶的協(xié)同過(guò)濾、基于好友的協(xié)同過(guò)濾和基于地理信息的推薦方法提出混合協(xié)同過(guò)濾算法，大大提高了推薦精度。

目前存在的關(guān)于興趣點(diǎn)的推薦（如Ye[4]、Cheng[5]、Gao[6]）幾乎全部采用傳統(tǒng)的基于內(nèi)存或基于模型的協(xié)同過(guò)濾技術(shù)。但是，由于用戶數(shù)據(jù)的稀疏性，這些技術(shù)都遭受嚴(yán)重的冷啟動(dòng)問(wèn)題。

為了應(yīng)對(duì)興趣點(diǎn)推薦中的冷啟動(dòng)，本文對(duì)現(xiàn)存的興趣點(diǎn)推薦算法進(jìn)行研究，發(fā)現(xiàn)用戶的簽到行為在很大程度上受到相關(guān)用戶的影響。例如，Gao等[7]表示社交好友、簽到行為相似的用戶均會(huì)影響用戶的簽到行為；Li等[8]對(duì)Foursquare中的數(shù)據(jù)進(jìn)行了分析，發(fā)現(xiàn)“兩個(gè)用戶的活動(dòng)中心越接近，簽到興趣點(diǎn)重合度越高，即和用戶在地理位置上相近的用戶（例如鄰居）的行為會(huì)影響到用戶的簽到行為。因此，本文提出了一個(gè)能夠利用相關(guān)用戶的推薦框架，關(guān)于相關(guān)用戶會(huì)在下文給出詳細(xì)的定義。

1 相關(guān)用戶

給定用戶i，為該用戶定義了三類相關(guān)用戶：地理相關(guān)用戶、社交相關(guān)用戶、簽到相似相關(guān)用戶。

定義1（地理相關(guān)用戶）：根據(jù)用戶i的歷史簽到數(shù)據(jù)，計(jì)算出用戶i的“活動(dòng)中心”，地理相關(guān)用戶是和用戶i的“活動(dòng)中心”距離最小的f個(gè)用戶，表示為 f(Fig)，關(guān)于用戶的“活動(dòng)中心”，在用戶歷史數(shù)據(jù)集上應(yīng)用聚類算法來(lái)獲得。需要注意的是，在應(yīng)用聚類算法之前，需要去掉那些明顯偏離的興趣點(diǎn)。

定義2（社交相關(guān)用戶）：用戶i的社交相關(guān)用戶是數(shù)據(jù)集中直接給出的，表示為

定義3（簽到行為相似的相關(guān)用戶）：計(jì)算用戶i和其余用戶的簽到相似度，在計(jì)算用戶簽到相似度時(shí)把時(shí)間因素融合到算法中，簽到行為相似相關(guān)用戶是f個(gè)和目標(biāo)用戶i簽到相似度（合并時(shí)間因素）最高的用戶，表示為在下文中，將會(huì)給出如何把時(shí)間因素融入到相似度的計(jì)算中。

2 PC-Geo推薦模型

2.1 相關(guān)用戶建模

用戶的簽到行為容易受到相關(guān)聯(lián)用戶的影響，本文為每個(gè)用戶選取了三類相關(guān)用戶，并使用這些相關(guān)用戶來(lái)學(xué)習(xí)目標(biāo)用戶的潛在興趣。前面已經(jīng)獲得了社交相關(guān)用戶和地理相關(guān)用戶，現(xiàn)在還需獲得簽到相似（合并時(shí)間因素）相關(guān)用戶。

時(shí)間因素在興趣點(diǎn)推薦中起著重要的作用，因?yàn)橛脩魞A向于在一天的不同時(shí)段訪問(wèn)不同的興趣點(diǎn)。例如，用戶習(xí)慣上午9點(diǎn)左右去上班，中午11點(diǎn)吃午飯，晚上十點(diǎn)左右和朋友去酒吧，人類的簽到活動(dòng)表現(xiàn)出了明顯的時(shí)間性。因此，在計(jì)算簽到相似度時(shí)把時(shí)間作為一個(gè)影響因素考慮進(jìn)去能更好地了解人類的移動(dòng)行為，設(shè)計(jì)精確度更高的推薦系統(tǒng)。

為了證明時(shí)間因素確實(shí)會(huì)影響用戶的簽到行為，實(shí)驗(yàn)時(shí)，從Foursquare中隨機(jī)選擇多個(gè)用戶，對(duì)其簽到行為隨時(shí)間的變化進(jìn)行了統(tǒng)計(jì)分析，圖1顯示了其中一個(gè)用戶的簽到頻率隨時(shí)間的變化，從圖中可以看出，該用戶發(fā)生的大部分簽到行為集中在少數(shù)的時(shí)間段內(nèi)，很多時(shí)段基本沒(méi)有簽到行為，其余的用戶也呈現(xiàn)類似的趨勢(shì)。因此，用戶的簽到行為呈現(xiàn)出很明顯的時(shí)間模式。

圖1 簽到頻率在每個(gè)時(shí)間狀態(tài)上的分布

從上面的分析來(lái)看，時(shí)間因素確實(shí)是影響用戶簽到行為的一個(gè)重要因素，因此，本文在考慮用戶簽到的相似度的時(shí)候增加了時(shí)間因素，采用把時(shí)間離散化的手段進(jìn)行研究。首先，把一天分為多個(gè)離散時(shí)間段，定義為T。然后，把原始的用戶-興趣點(diǎn)矩陣按照簽到時(shí)間分成24個(gè)時(shí)段-用戶-興趣點(diǎn)矩陣。基于時(shí)段-用戶-興趣點(diǎn)矩陣，兩個(gè)用戶基于時(shí)間的相似性表示為：

然而，原始的用戶-興趣點(diǎn)矩陣就是一個(gè)稀疏矩陣，經(jīng)過(guò)時(shí)間處理之后得到的時(shí)段-用戶-興趣點(diǎn)矩陣更加稀疏。因此，不能直接使用時(shí)段-用戶-興趣點(diǎn)矩陣去計(jì)算兩個(gè)用戶之間的相似度?？梢韵壤肶uan等[9]中的方式對(duì)矩陣平移，然后在進(jìn)行相似度的計(jì)算。平移過(guò)程如下所示：

給定目標(biāo)用戶i，用戶i在t∈T的簽到向量為：ri,t={ri,t,1,..ri,t,L}。計(jì)算該用戶在任意兩個(gè)時(shí)段的簽到向量的相似性，取數(shù)據(jù)集中所有用戶在這兩個(gè)時(shí)段的相似值的平均值作為這兩個(gè)時(shí)段相似度，表示如下：

利用時(shí)段簽到相似矩陣TS來(lái)對(duì)時(shí)間-用戶-興趣點(diǎn)矩陣進(jìn)行平移，具體平移公式如下：

然后通過(guò)平移過(guò)后的時(shí)段-用戶-興趣點(diǎn)矩陣就可以進(jìn)行用戶簽到相似度的計(jì)算了。

最后，把f個(gè)簽到相似相關(guān)用戶和f個(gè)地理相關(guān)用戶和社交相關(guān)用戶求并集作為目標(biāo)用戶的相關(guān)用戶。

2.2 地理信息建模

不同于傳統(tǒng)的非空間物品的推薦，在LBSN中，每個(gè)興趣點(diǎn)都有獨(dú)特的地理位置，用戶在在消費(fèi)產(chǎn)品或者享受服務(wù)的同時(shí)需要和興趣點(diǎn)有位置上的交互，地理因素是影響用戶簽到行為的一個(gè)重要的內(nèi)容。

現(xiàn)存的興趣點(diǎn)推薦的研究中，設(shè)計(jì)到基于地理信息的興趣點(diǎn)推薦大多只是簡(jiǎn)單地利用用戶的歷史位置和待訪問(wèn)的興趣點(diǎn)之間在距離上呈現(xiàn)的反比關(guān)系進(jìn)行推薦，或者將同一用戶簽到過(guò)的任意兩個(gè)興趣點(diǎn)間的距離視為冪率分布或多中心的高斯分布進(jìn)行推薦。但這些方法均存在很多局限。首先，用戶訪問(wèn)興趣點(diǎn)的概率不是距離上的單調(diào)，因?yàn)樵L問(wèn)的概率不僅受距離的影響還受位置固有屬性的影響。其次，每個(gè)用戶的簽到行為是獨(dú)特的，采用通用的分布函數(shù)不能體現(xiàn)用戶的個(gè)性化特征。本文采用核密度估計(jì)捕獲地理模型，通過(guò)該算法可以為每個(gè)用戶學(xué)習(xí)到獨(dú)特的概率密度函數(shù)，體現(xiàn)出用戶的個(gè)性化。

采用核密度估計(jì)捕獲地理模型方法簡(jiǎn)述如下：首先，對(duì)于目標(biāo)用戶i,其歷史簽到數(shù)據(jù)表示為L(zhǎng)i={l1,l2,……ln}。用戶i對(duì)興趣點(diǎn)j的偏好度表示為Wi={w1,w2,……wn}。興趣點(diǎn)的位置表示為lj:(xj,yj）。論文使用高斯分布作為核密度估計(jì)中的中心函數(shù)，最終本文的核密估計(jì)函數(shù)如下：

其中，h1,h2是固定帶寬，h是根據(jù)用戶i的歷史簽到數(shù)據(jù)的標(biāo)準(zhǔn)差σ得到的。

但是，只有固定的帶寬并不能反映這樣一個(gè)事實(shí)：密集的城市地區(qū)有較高的簽到密度，人口稀少的農(nóng)村地區(qū)將會(huì)有較低的簽到密度，所以可以增加一個(gè)可調(diào)節(jié)的局部帶寬，這個(gè)局部帶寬hj的計(jì)算方式如下：

其中，α∈[0,1]是一個(gè)靈敏度參數(shù)，g是幾何平均數(shù)，因此，最終的核密度公式如下：

至此，完成了通過(guò)核密度估計(jì)算法為每個(gè)用戶學(xué)習(xí)到獨(dú)特的概率密度函數(shù)，通過(guò)學(xué)習(xí)到的概率密度函數(shù)，可以捕捉地理信息對(duì)于用戶簽到的影響。

2.3 用戶的潛在興趣選擇策略

在獲得用戶的相關(guān)用戶之后，把相關(guān)用戶簽到過(guò)但用戶并未簽到過(guò)的部分興趣點(diǎn)作為用戶的潛在興趣。但是由于待選擇的興趣點(diǎn)太多，本文采用線性合并用戶興趣和地理因素的算法去衡量用戶對(duì)興趣點(diǎn)的偏好：

θ是控制用戶偏好和地理因素比例的調(diào)和參數(shù)。是用戶i和其相關(guān)用戶就興趣點(diǎn)j偏好的相似性。Geoi,j是地理對(duì)用戶簽到行為的影響，使用fi(l)進(jìn)行計(jì)算。最終，選擇s個(gè) pri,j值最大的興趣點(diǎn)作為用戶i的潛在興趣點(diǎn)。

2.4 矩陣分解和地理因素的融合

矩陣分解是一種在推薦算法中被廣泛使用的技術(shù)，不同于原始的矩陣分解，本文需要先把用戶潛在興趣點(diǎn)合并到用戶-興趣點(diǎn)矩陣中，緩解矩陣的稀疏性之后，在通過(guò)矩陣分解技術(shù)[10]構(gòu)建推薦模型。對(duì)于每個(gè)用戶i，把興趣點(diǎn)分為三類：Li是用戶簽到過(guò)的興趣點(diǎn)集合。Pi是用戶潛在興趣點(diǎn)集合。Ui是用戶沒(méi)有簽到過(guò)且非潛在興趣點(diǎn)的集合，新的用戶-興趣點(diǎn)矩陣和權(quán)重矩陣如下所示：

φ,μ∈[0,1]都屬于調(diào)節(jié)參數(shù)。φ+pri,j是潛在興趣點(diǎn)的概率，設(shè)置的過(guò)小，和未簽到興趣點(diǎn)的區(qū)別就不明顯了，設(shè)置的過(guò)大，會(huì)造成噪聲，所以設(shè)置它的值在0.1到0.15之間。最后本文的矩陣分解模型如下：

為了最小化損失函數(shù)，并且保證比快速收斂，本文采用隨機(jī)梯度下降算法，算法如表1所示：

表1 梯度下降算法

最后，本文合并地理因素對(duì)用戶簽到影響到矩陣分解中，獲得推薦模型如下所示：

3 實(shí)驗(yàn)設(shè)計(jì)

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

表2 Foursquare數(shù)據(jù)集統(tǒng)計(jì)信息

本文采用真實(shí)的數(shù)據(jù)集Foursquare，該數(shù)據(jù)集共包含兩個(gè)文件，一個(gè)是關(guān)于用戶的社交關(guān)系，表示為：〈用戶ID，好友用戶ID〉；一個(gè)是用戶的簽到日志表示為：〈簽到序號(hào)，用戶ID，簽到時(shí)間戳，興趣點(diǎn)ID（經(jīng)度，緯度，區(qū)域），主題〉。數(shù)據(jù)集中所有的興趣點(diǎn)都在加利福尼亞范圍內(nèi)，表2給出了數(shù)據(jù)集的詳細(xì)信息。

從表2可以看到，用戶-興趣點(diǎn)矩陣的簽到稀疏度為5.34×10-4，是一個(gè)非常低的值。該矩陣的稀疏導(dǎo)致大多數(shù)主流的興趣點(diǎn)推薦算法的精度普遍不高。所以，基于比較低的用戶－興趣點(diǎn)矩陣密度，最終得到普遍偏低的預(yù)測(cè)準(zhǔn)確率和召回率是合理的。

本文從簽到記錄中隨機(jī)抽取80%作為訓(xùn)練集，訓(xùn)練隱興趣矩陣U和V，利用剩余的20%作測(cè)試集來(lái)驗(yàn)證PC-Geo模型的推薦性能。為了提高實(shí)驗(yàn)的可靠性，實(shí)驗(yàn)采取交叉驗(yàn)證的策略。

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

本文采用推薦系統(tǒng)中常使用的評(píng)價(jià)標(biāo)準(zhǔn)準(zhǔn)確率和召回率作為評(píng)價(jià)指標(biāo)，具定義如下：

其中，L（i）表示用戶簽到過(guò)的位置集合，Topk（i）表示向用戶推薦的位置集合。實(shí)驗(yàn)中，k值設(shè)置為5,10。隱式空間的維度設(shè)置為10，相關(guān)用戶的個(gè)數(shù)f設(shè)置為10，用戶潛在興趣點(diǎn)s設(shè)置為300，重構(gòu)矩陣的調(diào)節(jié)參數(shù)φ為0.1μ為0.3。在梯度下降中，學(xué)習(xí)速率設(shè)置為0.002，用戶和興趣點(diǎn)的權(quán)重設(shè)置為相同的0.02。

3.3 不同推薦算法的對(duì)比

本文選定三個(gè)優(yōu)秀的推薦算法進(jìn)行對(duì)比。

BaseMF：對(duì)原始的用戶-興趣點(diǎn)矩陣進(jìn)行矩陣分解[11]。DRW：基于動(dòng)態(tài)隨機(jī)游走模型，融合用戶社會(huì)關(guān)系、類別信息和流行度信息進(jìn)行推薦[12]。LRT：把用戶簽到的時(shí)序模式合并到矩陣分解中進(jìn)行推薦[6]。

3.4 實(shí)驗(yàn)結(jié)果

圖2表示模型PC-Geo與上述三種推薦模型在準(zhǔn)確率和召回率的對(duì)比結(jié)果。

圖2 PC-Geo和其他推薦算法對(duì)比

BMF:這種方法已經(jīng)被廣泛的應(yīng)用在推薦系統(tǒng)中了，通常會(huì)通過(guò)最小化目標(biāo)函數(shù)來(lái)獲得局部最優(yōu)解。然而，由于用戶簽到矩陣的稀疏性，這種直接矩陣分解的方法會(huì)導(dǎo)致最后的推薦精度很低。

DRW:這種方法采用動(dòng)態(tài)的隨機(jī)游走模型，融合了用戶的社交關(guān)系、相關(guān)類別信息以及流行度信息，但是，該方法沒(méi)有考慮地理位置因素對(duì)于用戶簽到行為的影響。因此，它最終體現(xiàn)出較差的推薦效果。

LRT:這種方法引入了用戶簽到行為的兩個(gè)時(shí)間特性：1非統(tǒng)一性，即用戶在一天內(nèi)的不同時(shí)間段展現(xiàn)出不同的簽到偏好；2連續(xù)性，即用戶在一天內(nèi)連續(xù)時(shí)間段上的簽到偏好比非連續(xù)時(shí)間段上的偏好更加相似。LRT是在矩陣分解的基礎(chǔ)上加入了用戶社會(huì)行為的時(shí)模式，在模型中反映出簽到偏好隨時(shí)間狀態(tài)的遷移。但是，這種方法僅僅考慮了時(shí)間因素對(duì)用戶簽到行為的影響，并沒(méi)有考慮到其他的情景因素（地理，社交）用戶簽到行為的影響，因此，它的推薦精度也較差。

PC-Geo:該模型在精度和召回率上都取得了最好效果，原因總結(jié)如下：

（1）充分利用相關(guān)用戶會(huì)對(duì)用戶的簽到行為產(chǎn)生影響這一事實(shí)，利用相關(guān)用戶學(xué)習(xí)目標(biāo)用戶的潛在興趣，這能在一定程度上緩解冷啟動(dòng)問(wèn)題。

（2）使用核密度估計(jì)方法捕獲地理因素對(duì)用戶簽到行為的影響，為每個(gè)用戶獲得獨(dú)特的密度函數(shù)。

（3）一個(gè)額外的優(yōu)勢(shì)是容易把時(shí)間因素融入到推薦模型中，用戶的簽到行為具有時(shí)間模式，因此融入時(shí)間因素，也可以在一定程度上提高推薦模型的質(zhì)量。

圖3展示了PC模型（只合并了潛在興趣到用戶-興趣點(diǎn)矩陣中，并沒(méi)有合并最后的地理因素對(duì)用戶簽到行為的影響）和PC-Geo模型準(zhǔn)確率和召回率的對(duì)比。結(jié)果表示在基于社交網(wǎng)絡(luò)的興趣點(diǎn)推薦中考慮地理因素對(duì)用戶簽到行為的影響是必要的。

圖3 PC-Geo和PC的對(duì)比

3 結(jié)語(yǔ)

本文提出了一個(gè)對(duì)于興趣點(diǎn)的推薦框架：首先，使用情境信息（空間信息、時(shí)間信息、社交信息）來(lái)為目標(biāo)用戶定義相關(guān)用戶；其次，設(shè)計(jì)一個(gè)結(jié)合用戶興趣和地理信息的算法，利用相關(guān)用戶的歷史簽到數(shù)據(jù)，使用該算法學(xué)習(xí)目標(biāo)用戶的潛在興趣，緩解簽到矩陣的稀疏性。接著，把地理信息和矩陣分解的結(jié)果融合，最后完成對(duì)用戶的推薦。在未來(lái)的工作中，希望能把用戶的評(píng)論添加到框架中，以提高推薦效率。

[1]Zheng Y,Zhang L,Ma Z,et al.Recommending Friends and Locations Based on Individual Location History[J].ACM Transactions on the Web,2011,5（1）:5.

[2]Hu Y,Koren Y,Volinsky C.Collaborative Filtering for Implicit Feedback Datasets[C].Eighth IEEE International Conference on Data Mining.IEEE,2009:263-272.

[3]Cheng C,Yang H,King I,et al.Fused Matrix Factorization with Geographical and Social Influence in Location-Based Social Networks[C].AAAI Conference on Artificial Intelligence,2012.

[4]Ye M,Yin P,Lee W C,et al.Exploiting Geographical Influence for Collaborative Point-of-Interest Recommendation[C].ACM,2011:325-334.

[5]Cheng C,Yang H,Lyu M R,et al.Where You Like to Go Next:Successive Point-of-Interest Recommendation[C].International Joint Conference on Artificial Intelligence.AAAI Press,2013.

[6]Gao H,Tang J,Hu X,et al.Exploring Temporal Effects for Location Recommendation on Location-based Social Networks[C].ACM Conference on Recommender Systems.ACM,2013:93-100.

[7]Gao H,Liu H.Data Analysis on Location-Based Social Networks[J].2014:165-194.

[8]Li H,Ge Y,Zhu H,et al.Point-of-Interest Recommendations:Learning Potential Check-ins from Friends[C].ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2016:975-984.

[9]Yuan Q,Cong G,Ma Z,et al.Time-aware Point-of-Interest Recommendation[C].International ACM SIGIR Conference on Research and Development in Information Retrieval.ACM,2013:363-372.

[10]Koren Y,Bell R,Volinsky C.Matrix Factorization Techniques for Recommender Systems[J].Computer,2009,42（8）:30-37.

[11]Salakhutdinov R,Mnih A.Bayesian Probabilistic Matrix Factorization using Markov Chain Monte Carlo[C].International Conference on Machine Learning.ACM,2008:880-887.

[12]Ying J C,Kuo W N,Tseng V S,et al.Mining User Check-In Behavior with a Random Walk for Urban Point-of-Interest Recommendations[J].ACM Transactions on Intelligent Systems&Technology,2014,5（3）:1-26.