基于簽到數(shù)據(jù)和交通工具的多目標旅游路線推薦

（福州大學(xué) 經(jīng)濟與管理學(xué)院，福建 福州 350116）

引言

隨著Web 2.0時代的到來，互聯(lián)網(wǎng)技術(shù)和移動設(shè)備的快速發(fā)展，有越來越多的用戶愿意在社交平臺上分享自己的旅游經(jīng)驗，然而分享者越多，信息就會越膨脹。近年來，隨著旅游業(yè)的蓬勃發(fā)展，越來越多的人會選擇假期出游，一般情況下，用戶新到一座城市游玩，首先會上網(wǎng)搜索該城市的旅游資訊來安排自己的旅程，而網(wǎng)絡(luò)上的旅游信息量龐大又繁雜，用戶要從這些數(shù)據(jù)中找到符合個人現(xiàn)實需求的有用信息是一件非常費時又費力的事情?，F(xiàn)如今，隨著時代的發(fā)展，用戶的旅游消費觀念也日漸理性化和個性化，景點的實際情況，如景點的類別、開放時間、票價、兩個景點之間的轉(zhuǎn)移時間和轉(zhuǎn)移費用、是否對特殊人群（如：殘疾人、老人、學(xué)生等）半價等，都會對用戶是否去該景點游玩產(chǎn)生影響。因此，個性化旅游路線推薦具有重大的研究意義。

本文主要工作如下：

（1）提出了基于簽到數(shù)據(jù)感知用戶偏好和景點流行度的景點評分機制。

（2）將交通工具的選擇這一因素納入旅游路線推薦的考量之中。在本文中，我們考慮時間和預(yù)算兩個約束條件，而選擇不同的交通工具就會導(dǎo)致兩個景點之間的轉(zhuǎn)移產(chǎn)生不同的轉(zhuǎn)移時間和轉(zhuǎn)移費用，進而影響時間和預(yù)算約束。

（3）提出基于多約束多目標的剪枝算法，為用戶推薦一條最優(yōu)旅游路線。一般情況，在滿足約束的前提下，用戶都希望花盡可能少的錢游覽盡可能多的類別不同且得分高的景點。

（4）以 Foursquare社交網(wǎng)站上的真實數(shù)據(jù)和馬蜂窩上成都著名景點的信息作為數(shù)據(jù)集，驗證了本文提出的推薦算法能夠為用戶提供更符合其需求的個性化旅游路線。

一、相關(guān)工作

在給用戶進行旅游路線推薦之前，需要知道哪些景點對于用戶而言是有吸引力的。一般情況下，景點得分越高，對用戶而言就越有吸引力。有學(xué)者提出了基于時間的用戶興趣偏好，即用戶對于某類景點的興趣程度取決于該用戶在該類景點所花費的時間，景點的得分由景點的流行度和用戶興趣偏好決定[1]。還有學(xué)者提出興趣點得分由三部分組成：興趣點的類型得分、興趣點的類別得分和關(guān)鍵字搜索得分，一類興趣點可以包含多個類別，某個興趣點所包含的關(guān)鍵字占用戶關(guān)鍵字搜索得越多、該興趣點所屬的類別在用戶感興趣的類型中占比越大，那么該興趣點的得分就會越高[2]。還可使用加權(quán)類別層級（WCH）和迭代學(xué)習模型找到本地專家，從用戶訪問過的地理位置的類別中提取出用戶的偏好，根據(jù)用戶指定地理空間范圍內(nèi)的候選本地專家來匹配其偏好，最終，基于所選本地專家的意見推斷候選位置的分數(shù)[3]。也可將旅游景點的特征與用戶的喜好進行語義匹配，評估出用戶偏好，并據(jù)此評估出可用的旅游景點[4]。

旅游路線推薦其實就是將興趣點集通過時間序列串連起來，故了解興趣點推薦相關(guān)研究是很有必要的。Ye等學(xué)者提出了融合用戶對興趣點的偏好、地理位置影響和社會影響的統(tǒng)一協(xié)同過濾方法[5]。Gao等學(xué)者將時間影響納入矩陣分解的框架之中，針對不同時間間隙通過不同的潛在向量對每個用戶建模，提出了LRT模型[6]。Lian等學(xué)者將地理位置影響納入加權(quán)矩陣分解的框架之中，根據(jù)用戶歷史簽到記錄的空間聚集現(xiàn)象，提出GeoMF模型來模擬用戶活動區(qū)域與地理位置之間的相關(guān)關(guān)系[7]。Liu等學(xué)者提出了一種基于加權(quán)矩陣分解的IRenMF模型，該模型考慮位置級別和區(qū)域級別的影響，認為用戶對相鄰的興趣點有相似的偏好和同一區(qū)域的興趣點可能共享相似的用戶偏好[8]。還有學(xué)者結(jié)合了機器學(xué)習中的相關(guān)算法（如：監(jiān)督學(xué)習）來向用戶推薦興趣點[9]。

旅游路線推薦的目的是為用戶規(guī)劃出一條或多條符合用戶現(xiàn)實需求的個性化旅游路線。近年來，出現(xiàn)了大量關(guān)于旅游路線推薦的相關(guān)研究。在定向問題基礎(chǔ)上，通過分析用戶在社交網(wǎng)站上分享的旅游照片來獲取景點的流行度和用戶的興趣偏好，根據(jù)給定POI集合，時間預(yù)算，起點和終點，為用戶推薦一條滿足時間預(yù)算且分數(shù)最高的路線[1]。提出解決AdditiveTour問題（盡可能多地為用戶推薦得分高的景點）和CoveringTour問題（讓用戶盡可能多地訪問不同類型的景點）的方案，為不同需求下的用戶推薦旅游路線[10]。有學(xué)者利用照片共享站收集用戶帶地理標記的照片，使用均值漂移程序?qū)φ掌M行聚類，通過馬爾科夫模型和主題模型生成攝影師行為模型，用以估計攝影師訪問地標的概率，從而生成旅游路線[11]。還可使用以特征為中心的協(xié)同過濾算法來對用戶偏好建模，在假設(shè)兩個POI之間的旅行時間是確定的情況下對POI可用性建模，在不考慮POI多樣性的情況下對旅行時間的不確定性建模，以及根據(jù)LDA主題建模方法對POI多樣性建模，綜合考慮用戶偏好、POI可用性、旅行時間的不確定性以及POI多樣性來向用戶推薦最優(yōu)路線[12]。根據(jù)用戶給定的查詢位置、旅行時間約束以及用戶對景點類別選擇的集合，找到一條非重復(fù)多類別且收益最大化的最優(yōu)景點訪問路線[13]。

與上述工作相比，本文的主要工作有：提出了基于簽到數(shù)據(jù)感知用戶偏好和景點流行度的景點評分機制，將交通工具的選擇這一因素納入旅游路線推薦之中，提出了基于多約束多目標的剪枝算法，來為用戶推薦一條最優(yōu)路線。

二、基本定義

為了方便闡述所要解決的問題，定義了一些符號和公式。

定義1景點信息。對于每一個景點， 一個景點所包含的信息有：地理位置信息、類別、票價、開放時間()、得分、停留時間等。這些信息表明了景點的得分越高，對用戶的吸引力就越大，用戶愿意在該景點停留的時間就會越久，愿意為游玩該景點付出的成本就會越高。

定義2旅游路線。旅游路線是由多個旅游景點組成的序列，表示為。其中表示旅游路線中包含的景點，N為景點數(shù)目。

定義3路線地圖。有向帶權(quán)圖表示旅游區(qū)域里的路徑信息，是邊的集合，是節(jié)點的集合。

圖1：一個旅游路線推薦用戶示例

定義4兩個景點之間的轉(zhuǎn)移時間。用戶從景點到景點所需的轉(zhuǎn)移時間可定義為：

定義5兩個景點之間的轉(zhuǎn)移費用。 表示用戶從景點 到景點所需的轉(zhuǎn)移費用。在本文中，兩個景點之間的轉(zhuǎn)移費用分三種情況，當用戶選擇步行的情況下，兩個景點之間的轉(zhuǎn)移費用為0元，即；當用戶選擇乘坐公交車，兩個景點之間的轉(zhuǎn)移費用為2元，即；當用戶選擇打士，兩個景點之間的轉(zhuǎn)移費用的計算公式如下所示：

其中，我們假設(shè)有向的兩個景點之間均有一輛公交車可直達，費用為2元；有向的兩個景點之間的士均能直達，起步價為。本文所選取的定價均符合成都現(xiàn)行的實際情況。

定義6景點得分。根據(jù)用戶的歷史簽到數(shù)據(jù)感知用戶偏好和景點的流行度給出景點的評分方法。景點的得分可定義為：

定義7景點的停留時間。陌生城市對于一個用戶而言，在該城市某一景點的停留時間可能會基于自己對于這一景點類別的偏好程度以及該景點的流行程度，但是用戶一旦到達了某個景點，不管該景點實際情況如何，都至少會在該景點停留常數(shù)T的時間。景點的停留時間可定義為：

定義 8旅行時間和旅行費用。根據(jù)用戶給定的起點和終點，對于一段旅游路線，其旅行時間和旅行費用的計算公式如下所示：

定義9有效行程。假設(shè)，和分別表示用戶旅程的開始時間、旅程的結(jié)束時間以及預(yù)算，一段有效的行程必須滿足 ， 。

三、旅游路線推薦方法

（一）旅游路線推薦框架

如圖2所示，本文所提出的旅游路線推薦系統(tǒng)分為兩個階段，第一階段為離線學(xué)習階段，在該階段，從旅游網(wǎng)站搜集景點的相關(guān)信息，以及根據(jù)用戶的歷史簽到數(shù)據(jù)感知用戶偏好和景點流行度；第二階段為在線推薦階段，根據(jù)用戶輸入，通過基于多約束多目標的剪枝算法，為用戶推薦一條最優(yōu)旅游路線

圖2：旅游路線推薦框架

（二）基于簽到數(shù)據(jù)感知用戶偏好和景點流行度的景點評分機制

在進行路線推薦之前，需要了解每個景點對于用戶的吸引力。在本文中，景點對于用戶的吸引力取決于景點的得分，而景點得分又包含用戶偏好和景點流行度兩個方面。學(xué)習用戶偏好，可以感知哪一類景點對用戶而言是有吸引力的。一般，人們新到一個城市，并不了解該城市的具體情況，通常都會傾向于逛一些熱門景點，本文考慮，某一景點簽到的人越多，就說明該景點越流行。故，融合用戶偏好和景點流行度對景點進行評分，更符合實際、更具個性化。

1.用戶偏好

2.景點的流行度

根據(jù)景點的用戶歷史簽到記錄，挖掘景點的流行度。景點流行度的計算公式如下所示：

3.基于簽到數(shù)據(jù)感知用戶偏好和景點流行度的景點評分機制

在本文中，景點的得分既要考慮用戶偏好也要考慮景點流行度，因此，公式（3）對用戶偏好和景點流行度進行融合，最終得到景點的得分。

（三）旅游路線推薦算法

1.簡單的多約束剪枝算法 MCPA算法

在有向帶權(quán)圖G中，通過遍歷滿足用戶需求的所有可行路徑，將景點總得分最高的旅游路線推薦給用戶，具體算法描述如下。

算法1 MCPA算法

輸出：一條最優(yōu)旅行路線。

步驟1 根據(jù)景點得分，選擇Top-K個景點；

步驟3 根據(jù)用戶輸入的預(yù)計訪問的景點數(shù)，生成 條旅游路線；

步驟9 將 路線推薦給用戶。

如果只是簡單地將景點總得分最高的路線推薦給用戶，不考慮景點的多樣性，那我們所推薦路線就可能存在多個景點都屬于同一類別的現(xiàn)象，這樣的推薦結(jié)果可能并不是用戶想要的。

2.考慮景點多樣性的多約束剪枝算法 MCPA-D算法

為進一步接近用戶的真實需求，我們提出了MCPA-D算法。

多樣性值的計算公式如下所示[15]：

路線得分的計算公式，更新為如下所示：

算法2 MCPA-D算法

更新算法1的步驟8-步驟9

步驟9 將 路線推薦給用戶。

3.基于多約束多目標的剪枝算法 MCPA-MO算法

一般情況下，人們都希望花盡可能少的時間游覽盡可能多的類別不同且得分高的景點，故在滿足時間約束和費用約束的前提下，費用低的行程對用戶而言會更具吸引力，自然，用戶的滿意度也會更高，故再考慮旅程的花銷得分和時間得分也很有必要?；ㄤN得分和時間得分的計算公式如下所示：

據(jù)此，一條旅游路線的最終得分，計算公式如下所示：

算法3 MCPA-MO算法

更新算法1的步驟8-步驟9

（四）路線規(guī)劃

為了更好的展示本文所提出的算法，我們將以圖 1為例進行說明，給定景點的集合，每個景點的信息如表1所示。

表1：景點信息

表2表示由公式（7）計算出的用戶偏好得分。表3表示由公式（8）計算出的景點流行度得分；假定，景點得分由公式（3）計算得出，結(jié)果如表4所示。

表2：用戶的類別偏好

表2：用戶的類別偏好

類別 類別偏好得分0 0.403 5 0.084 7 0

表3：景點流行度

表4：景點得分

四、實驗結(jié)果與分析

（一）實驗數(shù)據(jù)

本文用于實驗的數(shù)據(jù)分為兩個部分，一部分來源于Foursquare真實數(shù)據(jù)集[15]，采集的是2009年12月至2013年6月期間在加利福尼亞的簽到數(shù)據(jù)，包括用戶ID、興趣點ID、興趣點經(jīng)緯度及其類別信息。數(shù)據(jù)集中一共含有2551名用戶，13474個興趣點及124933條簽到記錄；另一部分來源于馬蜂窩，獲取數(shù)據(jù)時間截至到2019年2月，獲取的數(shù)據(jù)是成都198個具有不少于10個用戶簽到的景點數(shù)據(jù)，包括景點ID、景點位置、景點類別信息、景點開放時間、景點門票以及是否對特殊人群半價（如：學(xué)生、老年人）等。另外，通過百度地圖，挖掘這些景點的GPS坐標信息。

（二）實驗結(jié)果與分析

1.MCPA算法與MCPA-D算法推薦效果對比

本文將MCPA算法得到的排名與MCPA-D算法得到的排名相同的top 51條路線進行對比，證明考慮景點多樣性的必要性。

圖3：MCPA算法與MCPA-D算法下計算的值

從圖3可以看出，兩種算法得出top 51條路線的∑score值，其差值范圍在[0，0.017]， 而MCPA-D算法得出的∑score值居然略小于 MCPA算法下得出的∑score值，此時，我們再將景點的多樣性考慮進去，對比兩種算法的(∑score + diversity(R))值，結(jié)果如圖4所示。

圖4：MCPA算法與MCPA-D算法下計算的值

從圖4可以看出，top 51、top 41、top 39和top 30路線，兩種算法得出的值相去甚遠，查看數(shù)據(jù)結(jié)果，發(fā)現(xiàn)這4條路徑，在MCPA算法下，路線中存在類別相同的景點；而在MCPA-D算法下，路線中不存在景點類別相同的景點，路線景點類別情況，如表5所示。

表5：四條路線的景點類別情況

綜上，犧牲小部分的∑score值，可獲得類別不同的路線。故，考慮景點的多樣性是很有必要的。

2.MCPA-D算法與MCPA-MO算法推薦效果對比

本文將MCPA-D算法與MCPA-MO算法分別得到的排名第一的路線進行對比，結(jié)果如圖5所示，MCPA-D算法與MCPA-MO算法得到的（∑score + diversity（R））值和旅程所花費的時間基本相當，而MCPA-MO算法計算出的花銷占比只有2.6%。充分說明考慮花銷得分和時間得分的必要性.

圖5：MCPA-D算法與MCPA-MO算法top 1對比

五、結(jié)論與展望

本文針對用戶希望花盡可能少的錢游覽盡可能多的類別不同且得分高的景點這一旅游推薦問題，提出了基于簽到數(shù)據(jù)感知用戶偏好和景點流行度的景點評分機制以及基于多約束多目標的剪枝算法。在本文中，我們考慮到了用戶偏好、景點流行度以及不同交通工具的選擇會對時間和預(yù)算約束產(chǎn)生影響，并且使用MCPA-MO算法計算出一條最優(yōu)旅游路線推薦給用戶，以Foursquare社交網(wǎng)站上的真實數(shù)據(jù)和馬蜂窩上成都著名景點的信息作為數(shù)據(jù)集，實現(xiàn)并評估了推薦算法。實驗結(jié)果表明，該方法能夠為用戶推薦更符合現(xiàn)實需求的個性化旅游路線。在未來的工作中，我們將會考慮用戶對歷史景點的主觀評價，通過語義分析對不同推薦結(jié)果打正負標簽，進一步優(yōu)化推薦效果。