基于頻繁序列挖掘的后續(xù)行程序列推薦

溫彥 馬立健 陳明

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

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

DOI：10. 11907/rjdk. 182099

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

0 引言

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

1 相關(guān)工作

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

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

2 問題定義

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

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

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

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

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

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

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

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

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

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

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

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

4.1 頻繁序列生成

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

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

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

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

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

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

4.3 推薦序列生成

5 實驗

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

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

6 結(jié)語

本文提出一種在旅游過程中基于歷史行程序列推薦后續(xù)行程序列的方法SeqRem，基于所有用戶的行程序列挖掘頻繁序列模式，并以此為依據(jù)利用最大點權(quán)獨立集的方法對用戶歷史行程序列進(jìn)行分割，同時發(fā)現(xiàn)最優(yōu)序列推薦內(nèi)容。實驗證明，基于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]. 計算機技術(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é)任編輯：何 麗）