基于頻繁序列挖掘的后續行程序列推薦

溫彥 馬立健 陳明

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

關鍵詞：推薦系統;頻繁序列挖掘;興趣點;后續行程序列;數據挖掘

DOI：10. 11907/rjdk. 182099

中圖分類號：TP301文獻標識碼：A文章編號：1672-7800（2019）003-0053-04

0 引言

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

1 相關工作

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

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

2 問題定義

首先給出相關概念和問題定義。

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

根據性質1可知，序列S子序列的概率必定不小于其自身，會限制有意義的長序列出現，因此需根據序列長度對后續行程序列S的概率進行補償，提高長序列的優先級。

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

3 基于歷史序列的后續序列概率模型

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

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

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

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

根據該假設，可以對H進行重寫。

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

4 后續序列概率模型計算與序列推薦

4.1 頻繁序列生成

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

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

4.2 基于頻繁序列的歷史行程Top-K最優劃分

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

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

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

4.3 推薦序列生成

5 實驗

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

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

6 結語

本文提出一種在旅游過程中基于歷史行程序列推薦后續行程序列的方法SeqRem，基于所有用戶的行程序列挖掘頻繁序列模式，并以此為依據利用最大點權獨立集的方法對用戶歷史行程序列進行分割，同時發現最優序列推薦內容。實驗證明，基于SeqRem的后續行程序列推薦方法具有較好效果。

參考文獻：

[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] 王顯飛，陳梅，李小天. 基于約束的旅游推薦系統的研究與設計[J]. 計算機技術與發展，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. 數據挖掘導論[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.

（責任編輯：何 麗）