溫彥 馬立健 陳明

摘 要：個(gè)性化旅游發(fā)展迅速，已有方法主要集中在單個(gè)旅游產(chǎn)品推薦上，而旅游行程存在明顯的序列性，并受到當(dāng)前已有行程軌跡影響。因此，提出一種旅行中后續(xù)行程序列的推薦方法SeqRem，基于所有用戶的行程序列挖掘頻繁序列模式，并以此為依據(jù)利用最大點(diǎn)權(quán)獨(dú)立集方法對(duì)用戶的歷史行程序列進(jìn)行分割，以發(fā)現(xiàn)最優(yōu)序列推薦內(nèi)容。實(shí)驗(yàn)證明，SeqRem在單點(diǎn)推薦和序列推薦準(zhǔn)確率與召回率均具有較好效果。

關(guān)鍵詞：推薦系統(tǒng);頻繁序列挖掘;興趣點(diǎn);后續(xù)行程序列;數(shù)據(jù)挖掘

DOI：10. 11907/rjdk. 182099

中圖分類號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-7800（2019）003-0053-04

0 引言

隨著人們生活水平提高，越來越多家庭注重旅游投入，追求優(yōu)質(zhì)的旅行體驗(yàn)，“主題旅游”、“定制旅游”等新型旅游模式應(yīng)運(yùn)而生。而當(dāng)前旅游市場(chǎng)對(duì)游客的個(gè)性化需求滿足遠(yuǎn)未達(dá)到用戶預(yù)期。旅游產(chǎn)品推薦是當(dāng)前個(gè)性化旅游服務(wù)的熱門話題，根據(jù)推薦內(nèi)容可分為旅游景點(diǎn)、旅游包、旅游線路推薦等，能夠根據(jù)用戶歷史旅游記錄分析用戶特征和偏好，并推薦其可能感興趣的產(chǎn)品。人們?cè)诼糜芜^程中往往存在如下需求：根據(jù)用戶當(dāng)前旅行狀態(tài)實(shí)時(shí)推薦后續(xù)一系列行程，這在不同粒度的旅游過程中均存在，例如用戶到達(dá)天安門后，需要有序?yàn)g覽故宮博物院、國(guó)家博物館、人民大會(huì)堂等景點(diǎn)，進(jìn)入故宮后需要有序?yàn)g覽故宮內(nèi)相關(guān)景點(diǎn)。事實(shí)上，旅游行程存在明顯的序列性，人們往往按照某種有序路線訪問景點(diǎn)，但這一序列性又受到用戶當(dāng)前狀態(tài)如已有行程、位置、時(shí)間以及用戶對(duì)景點(diǎn)偏好的影響。用戶已經(jīng)訪問的景點(diǎn)代表了其行程軌跡，也可以反映其當(dāng)前所處位置，對(duì)后續(xù)景點(diǎn)訪問會(huì)產(chǎn)生重要影響，因此本文主要關(guān)注如何推薦后續(xù)旅游行程序列并提出方法SeqRem。

1 相關(guān)工作

旅游點(diǎn)推薦根據(jù)產(chǎn)品內(nèi)容不同可分為：①單個(gè)旅游產(chǎn)品推薦，主要包含與旅游的食、住、行、游、娛、購(gòu)相關(guān)的單個(gè)產(chǎn)品，如文獻(xiàn)[1]、文獻(xiàn)[2]都是利用用戶在旅游網(wǎng)站上傳照片的標(biāo)簽信息挖掘其偏好相似性，并推薦其可能感興趣的景點(diǎn)，文獻(xiàn)[3]、文獻(xiàn)[4]是基于旅游知識(shí)庫(kù)的推薦系統(tǒng);②旅行包推薦是對(duì)多種旅游產(chǎn)品打包后形成的包價(jià)產(chǎn)品進(jìn)行推薦，如文獻(xiàn)[5]、文獻(xiàn)[6]利用改造的主題模型對(duì)游客與旅行包之間的關(guān)系建模并進(jìn)行推薦，文獻(xiàn)[7]采用隱語義分析模型（Latent Factor Model，LFM）和矩陣分解方法進(jìn)行旅行包推薦;③旅游線路推薦主要為用戶規(guī)劃出一條或多條合理并符合用戶興趣與期望的旅游線路，主要采用圖搜索方式滿足預(yù)設(shè)成本、時(shí)間等需求[8-9]。

旅行推薦可以看作基于位置的興趣點(diǎn)（Point of Interest，POI）推薦的一類特殊工作，根據(jù)用戶歷史軌跡推薦可能感興趣的地理位置。由于位置推薦受到物理距離影響，因此大部分工作均將位置間的距離作為推薦的重要依據(jù)之一，此外，受到社會(huì)化推薦系統(tǒng)影響，也有不少工作考慮社會(huì)關(guān)系對(duì)推薦內(nèi)容的作用[10- 11]。后續(xù)興趣點(diǎn)推薦是近年來提出的對(duì)傳統(tǒng)POI推薦的擴(kuò)展，表示根據(jù)用戶當(dāng)前所在位置推薦后續(xù)可能位置，如文獻(xiàn)[12]利用馬爾科夫鏈建模后續(xù)關(guān)系，文獻(xiàn)[13]利用一體化張量分解方法對(duì)訪問時(shí)間和位置間的前后關(guān)系建模。在旅行系統(tǒng)中，基于當(dāng)前位置推薦后續(xù)位置是常見需求，而且旅游行程體現(xiàn)出顯著的序列性特點(diǎn)，即用戶基于當(dāng)前位置，更傾向于訪問后續(xù)的n個(gè)地點(diǎn)。序列推薦能夠有效規(guī)避用戶因訪問順序不當(dāng)帶來的額外時(shí)間代價(jià)，提高旅游體驗(yàn)。當(dāng)前已有工作主要集中在單點(diǎn)推薦上，缺乏對(duì)行程序列的考慮，本文旨在提供一定模型和方法實(shí)現(xiàn)后續(xù)序列的推薦。

2 問題定義

首先給出相關(guān)概念和問題定義。

證明：根據(jù)定義3及頻繁項(xiàng)集的先驗(yàn)原理可知，若一個(gè)項(xiàng)集是頻繁的，則其所有子集一定是頻繁的，因此一個(gè)序列出現(xiàn)的概率必定小于等于其子序列出現(xiàn)的概率[14-15]。

根據(jù)性質(zhì)1可知，序列S子序列的概率必定不小于其自身，會(huì)限制有意義的長(zhǎng)序列出現(xiàn)，因此需根據(jù)序列長(zhǎng)度對(duì)后續(xù)行程序列S的概率進(jìn)行補(bǔ)償，提高長(zhǎng)序列的優(yōu)先級(jí)。

定義4 長(zhǎng)度補(bǔ)償函數(shù)[c（F）]。對(duì)于序列S，其長(zhǎng)度為[|S|]，其長(zhǎng)度補(bǔ)償函數(shù)[c（|S|）]需滿足如下條件：

3 基于歷史序列的后續(xù)序列概率模型

本文對(duì)來自國(guó)內(nèi)多個(gè)大型旅游網(wǎng)站的游客簽到數(shù)據(jù)進(jìn)行分析，通過觀察發(fā)現(xiàn)，絕大多數(shù)游客對(duì)同一景點(diǎn)的簽到記錄只有一次，且從照片時(shí)間關(guān)系來看，也都集中在同一時(shí)間段，這種現(xiàn)象也符合人們對(duì)旅行行為的一般認(rèn)知，即相同景點(diǎn)只訪問一次。這是本文的基本假設(shè)之一。

假設(shè)1：對(duì)于用戶u，他訪問過的所有地點(diǎn)在其行程中只出現(xiàn)一次。

對(duì)于目標(biāo)函數(shù)式（1），首先應(yīng)給出[P（S|H）]的計(jì)算方法。其中H是用戶已有的所有行程序列，一方面，行程序列可能很長(zhǎng)，帶來相當(dāng)程度的計(jì)算復(fù)雜性;另一方面，行程序列可以由多個(gè)行程片段組合，每個(gè)片段可以看作是一個(gè)關(guān)系較為緊密的景點(diǎn)群，而這些片段分別對(duì)后續(xù)行程產(chǎn)生相對(duì)獨(dú)立的影響。因此有如下假設(shè)：

假設(shè)2：用戶的歷史行程序列H可以分割為多組頻繁序列，而各個(gè)頻繁序列之間是互相獨(dú)立的。

根據(jù)該假設(shè)，可以對(duì)H進(jìn)行重寫。

式（2）計(jì)算需要解決3個(gè)問題：①如何根據(jù)所有用戶的歷史行程計(jì)算頻繁序列;②如何將歷史序列H重寫為[{f1，f2，？，fm}]的形式，即如何對(duì)H進(jìn)行分割;③對(duì)于所有可能訪問的地點(diǎn)，其構(gòu)成的序列數(shù)量呈指數(shù)級(jí)增長(zhǎng)，如何對(duì)可能的序列數(shù)進(jìn)行有效約減。

4 后續(xù)序列概率模型計(jì)算與序列推薦

4.1 頻繁序列生成

生成頻繁歷史序列可采用序列模式挖掘（Sequential Pattern Mining，SPM）的方法，用于發(fā)現(xiàn)高于給定支持度且能保障頻繁序列在歷史記錄中出現(xiàn)次序的序列。GSP是其中的經(jīng)典算法[15]。本文頻繁序列的定義是傳統(tǒng)序列模式挖掘的特例：由于旅游過程中不同景點(diǎn)耗時(shí)不一致，很難給定一個(gè)固定的事件區(qū)間T，因此本文頻繁序列挖掘中不考慮長(zhǎng)短行程序列的差別，每一個(gè)用戶的歷史行程就是一個(gè)事件。為了消除長(zhǎng)程頻繁序列的影響，在頻繁序列發(fā)現(xiàn)后引入序列間距指標(biāo)，用于描述不同頻繁序列中各項(xiàng)的平均位置間隔。

給定平均間距的閾值后，就可將長(zhǎng)程頻繁序列刪去。

4.2 基于頻繁序列的歷史行程Top-K最優(yōu)劃分

考慮如何劃分用戶的歷史行程，使其成為互相獨(dú)立的頻繁序列集合。根據(jù)式（2），應(yīng)為每一個(gè)可能推薦的序列[S]構(gòu)建其歷史序列劃分，但一方面[S]的數(shù)量呈指數(shù)級(jí)，另一方面對(duì)每一個(gè)[S]求劃分也是指數(shù)級(jí)代價(jià)，因此實(shí)際上不可行。為此，引入頻繁序列關(guān)聯(lián)圖概念，利用歷史序列在所有頻繁序列上的統(tǒng)計(jì)規(guī)律，對(duì)其進(jìn)行最優(yōu)劃分。

頻繁序列關(guān)聯(lián)圖的所有節(jié)點(diǎn)包括含用戶u歷史行程的所有行程節(jié)點(diǎn)[V1]和頻繁序列[V2]。節(jié)點(diǎn)權(quán)值綜合了頻繁序列的支持度以及該序列在歷史行程中的位置。尋找歷史行程的最優(yōu)劃分，即對(duì)頻繁序列關(guān)聯(lián)圖尋找滿足如下條件的子節(jié)點(diǎn)集合：①有邊連接的兩個(gè)頂點(diǎn)不能同時(shí)選擇，保障所有歷史行程中的景點(diǎn)只訪問一次;②節(jié)點(diǎn)的權(quán)值和最大，保障劃分結(jié)果最頻繁。

該問題可直接建模為最大點(diǎn)權(quán)獨(dú)立集問題。對(duì)于某一個(gè)用戶u，應(yīng)當(dāng)推薦使得P（S | H）最大的K個(gè)序列S，而該K個(gè)序列S可能分布在對(duì)H的多個(gè)不同劃分中。因此，需要計(jì)算Top-K個(gè)最大點(diǎn)權(quán)獨(dú)立集。該問題等價(jià)于求序列H的所有極大獨(dú)立集，然后對(duì)各個(gè)獨(dú)立集求權(quán)重和并排序。該問題是NP難問題，采用兩種手段使其可計(jì)算：①縮小歷史序列的窗口大小，越遠(yuǎn)的歷史序列對(duì)后續(xù)影響越小，因此控制窗口大小可使計(jì)算量可控;②采用近似算法[16]。

4.3 推薦序列生成

5 實(shí)驗(yàn)

數(shù)據(jù)集來自國(guó)內(nèi)多個(gè)大型旅游網(wǎng)站的游客簽到數(shù)據(jù)，游客在網(wǎng)站上傳旅行照片，照片中記錄了旅行時(shí)間，從中可以抽取出游客的旅游行程。選擇某熱門旅游城市所有行程記錄，去除其中只簽到一次的用戶，得到數(shù)據(jù)集，包括5 677個(gè)用戶和33 231條簽到記錄。

由于本文推薦的是序列而非單個(gè)景點(diǎn)，而目前還未能查到推薦旅行行程序列的論文。因此進(jìn)行如下兩項(xiàng)實(shí)驗(yàn)：①針對(duì)單個(gè)后續(xù)景點(diǎn)的推薦實(shí)驗(yàn)，并與推薦后續(xù)POI的方法LORE進(jìn)行比較[12];②后續(xù)行程序列的推薦實(shí)驗(yàn)，與單個(gè)地點(diǎn)推薦進(jìn)行比較。采取的指標(biāo)為推薦準(zhǔn)確性和召回率，實(shí)驗(yàn)中的參數(shù)值為：頻繁序列的支持度閾值為3，長(zhǎng)度補(bǔ)償函數(shù)為|S|。針對(duì)不同TOP-K的K值，實(shí)驗(yàn)結(jié)果如圖1和圖2所示。可以看出，對(duì)于后續(xù)單景點(diǎn)推薦，本文準(zhǔn)確率和召回率與其它方法基本持平，對(duì)于序列推薦而言，準(zhǔn)確率和召回率略低于單點(diǎn)推薦。

6 結(jié)語

本文提出一種在旅游過程中基于歷史行程序列推薦后續(xù)行程序列的方法SeqRem，基于所有用戶的行程序列挖掘頻繁序列模式，并以此為依據(jù)利用最大點(diǎn)權(quán)獨(dú)立集的方法對(duì)用戶歷史行程序列進(jìn)行分割，同時(shí)發(fā)現(xiàn)最優(yōu)序列推薦內(nèi)容。實(shí)驗(yàn)證明，基于SeqRem的后續(xù)行程序列推薦方法具有較好效果。

參考文獻(xiàn)：

[1] KOFLER C， CABALLERO L， MENENDEZ M， et al. Near2me： an authentic and personalized social media-based recommender for travel destinations[C]. The 3rd ACM SIGMM International Workshop on Social Media， 2011： 47-52.

[2] CAO L L， LUO J B， GALLAGHER A， et al. A worldwide tourism recommendation system based on geotagged web photos[C].The 35th International Conference on Acoustics， Speech and Signal Processing， 2010：2274-2277.

[3] 王顯飛，陳梅，李小天. 基于約束的旅游推薦系統(tǒng)的研究與設(shè)計(jì)[J]. 計(jì)算機(jī)技術(shù)與發(fā)展，2012，22（2）：141-145.

[4] CLEMENTS M，SERDUKOV P， VRIES A D， et al. Using Flickr geotags to predict user travel behavior[C]. ACM Transactions on Information Systems， 2010：851-852.

[5] TAN C，LIU Q，CHEN E， et al. Object-oriented travel package recommendation[J]. ACM Transactions on Intelligent Systems & Technology （TIST）， 2014， 5（3）： 1-26.

[6] HE J， LIU H， XIONG H. Socotraveler： travel-package recommendations leveraging social influence of different relationship types[J]. Information & Management， 2016， 53（8）： 934-950.

[7] LIU Q， GE Y， LI Z M， et al. Personalized travel package recommendation[C]. The IEEE International Conference on Data Mining， 2011：407-416.

[8] KURASHIMA T， IWATA T， LRIE G， et al. Travel route recommendation using geotags in photo sharing sites[C]. The International Conference on Information and Knowledge Management， 2010：579-588.

[9] CHAKRABORTY B. Integrating awareness in user oriented route recommendation system[C]. The International Joint Conference on Neural Networks， 2012：1-5.

[10] YE M，YIN P，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.

[11] CHENG C，YANG H，KING I，et al. Fused matrix factorization with geographical and social influence in location-based social networks[C]. 26th AAAI Conference on Artificial Intelligence，2012，12： 17-23.

[12] ZHANG J D，CHOW C Y，LI Y. Lore： exploiting sequential influence for location recommendations[C]. Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems，2014：103-112.

[13] ZHAO S， ZHAO T， YANG H， et al. Stellar： spatial-temporal latent ranking for successive point-of-interest recommendation[C]. 30th AAAI Conference on Artificial Intelligence， 2016：315-322.

[14] SRIKANT R，AGRAWAL R. Mining sequential patterns： generalizations and performance improvements[C]. 5th International Conference on Extending Database Technology， 1996：3-17.

[15] TAN P N， MICHAEL S， VIPIN K. 數(shù)據(jù)挖掘?qū)д揫M]. 范明，范宏建，譯. 北京：人民郵電出版社，2011.

[16] LAWLER E L， LENSTRA J K， RINNOOY KAN A H G. Generating all maximal independent sets： NP-hardness and polynomial-time algorithms[J]. SIAM Journal on Computing， 1980， 9（3）： 558-565.

（責(zé)任編輯：何 麗）