胡冰冰，蘆俊麗，鄭承宇

(云南民族大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，云南 昆明 650500)

旅游業(yè)在地區(qū)經(jīng)濟(jì)增長(zhǎng)中一直發(fā)揮著重要作用，它能帶動(dòng)地區(qū)經(jīng)濟(jì)發(fā)展和資金的積累，促進(jìn)信息技術(shù)的傳播，增加就業(yè)機(jī)會(huì)等[1].隨著經(jīng)濟(jì)的發(fā)展和生活水平的提高，喜愛(ài)旅游的人變得越來(lái)越多，而旅游路線的選擇是人們出發(fā)前研究的一個(gè)重要問(wèn)題，是旅游中至關(guān)重要的一個(gè)環(huán)節(jié)[2-3].為了使游客游覽的內(nèi)容豐富多彩、避免迂回和往復(fù)等問(wèn)題，旅游路線的規(guī)劃對(duì)于游客至關(guān)重要.

隨著互聯(lián)網(wǎng)的發(fā)展和時(shí)代的進(jìn)步，越來(lái)越多的游客喜愛(ài)通過(guò)游記的形式在旅游平臺(tái)上分享自己的旅游經(jīng)歷，游記中含有大量不同游客的獨(dú)特體驗(yàn)和可靠的出行建議，為挖掘旅游熱門路線提供了極佳的參考依據(jù).然而，由于用戶量的日益增加，各大旅游網(wǎng)站游記數(shù)目也日益龐大.從爆炸式增長(zhǎng)、龐雜多樣的游記中，獲取歷史游客的游覽信息進(jìn)行旅游路線推薦，成為了目前旅游路線推薦的研究難點(diǎn)[4].

筆者提出一種改進(jìn)的PrefixSpan算法來(lái)挖掘旅游熱門路線.首先從攜程旅游網(wǎng)站(https://www.ctrip.com/)爬取大量游記記錄，對(duì)游記數(shù)據(jù)進(jìn)行預(yù)處理，獲取旅行軌跡數(shù)據(jù)庫(kù).然后，采用改進(jìn)的PrefixSpan算法對(duì)數(shù)據(jù)進(jìn)行挖掘，得到旅游熱門路線.與原算法相比較，改進(jìn)的PrefixSpan算法連續(xù)性更好，比原算法效率更高，更適用于旅游路線的搜索.

1 相關(guān)工作

旅游路線問(wèn)題一直被國(guó)內(nèi)外學(xué)者所重視.目前，許多學(xué)者對(duì)旅游熱門路線進(jìn)行了深入研究，并取得了一批有價(jià)值的研究成果.2020年董飛[5]基于0-1規(guī)劃模型為旅游團(tuán)設(shè)計(jì)旅游路線，該路線主要考慮的是在時(shí)間的限制下，給出旅游團(tuán)游覽景點(diǎn)的最大時(shí)長(zhǎng)路線.同年郭斌等[6]提出一種基于群智數(shù)據(jù)的跨模態(tài)分析與情境關(guān)聯(lián)旅游路線推薦方法.首先使用跨模態(tài)分析方法將互補(bǔ)的圖像與文本相結(jié)合，再進(jìn)行分類識(shí)別，然后基于圖模型使用PhotoRank算法優(yōu)選出具有多樣性、代表性的圖片，最后采用關(guān)聯(lián)規(guī)則挖掘，得到針對(duì)不同出行人群的特定需求情境的推薦路線.同年袁絳書(shū)等[7]針對(duì)黃山景點(diǎn)眾多且過(guò)于分散，游客沒(méi)有辦法在有限的時(shí)間內(nèi)游覽完期望景點(diǎn)的問(wèn)題，建立了基于游客滿意度最大化的旅游路線優(yōu)化模型，此模型考慮了距離、年齡、性別、金錢和用戶偏好等元素，利用貪心算法求解，最終給出游客滿意度最大的最優(yōu)路線.

旅游熱門路線的好壞與旅游軌跡數(shù)據(jù)的來(lái)源和獲取方式息息相關(guān).目前，旅游軌跡的搜索方式主要有以下幾種：2015年Sobolevsky等[8]通過(guò)銀行卡終端獲得的交易數(shù)據(jù)來(lái)建模旅行者的空間和時(shí)間移動(dòng)模式.這些方式所收集數(shù)據(jù)要么在數(shù)量和地理區(qū)域上有限，要么不能免費(fèi)提供給公眾使用.2017年Vu等[9]以及2020年Kolahkaj等[10]使用Flickr軟件，通過(guò)處理帶地理標(biāo)記的照片來(lái)得到旅游軌跡，此軟件雖然免費(fèi)但畢竟不是旅游軟件，不能保證提取的數(shù)據(jù)全是游客的旅游軌跡，且上傳的旅游圖片只包含旅游路線的部分地點(diǎn)，不是完整路線.互聯(lián)網(wǎng)旅游平臺(tái)的游記是對(duì)旅游過(guò)程的完整描述，作為當(dāng)今最熱門的軟件，得到越來(lái)越多旅游研究者的重視[4, 6, 11].

序列模式挖掘是指從序列數(shù)據(jù)庫(kù)中挖掘出現(xiàn)頻率高的模式，序列模式挖掘問(wèn)題首先由Agrawal和Srikant在1995年提出，并給出了基于類Apriori的AprioriSome，AprioriAll和DynamicSome 3種序列模式挖掘算法[12]，隨后他們又提出了AprioriAll算法的擴(kuò)展算法：廣義序列模式(Generalized Sequential Pattern，GSP)挖掘算法[13]，該算法的特色是引入了時(shí)間約束、滑動(dòng)時(shí)間窗和分類層次技術(shù)，增加了掃描的約束條件.而此類基于類Apriori的算法的缺點(diǎn)是產(chǎn)生大量的候選項(xiàng)集合和必須重復(fù)掃描數(shù)據(jù)庫(kù).序列模式挖掘的模式增長(zhǎng)方法FreeSpan算法[14]，以及它的前驅(qū)算法PrefixSpan算法由Han等[15]提出，其中PrefixSpan算法因包含更少的投影庫(kù)和子序列連接，數(shù)據(jù)庫(kù)收斂更快，算法效率比之前的算法效率都高，而被廣泛應(yīng)用于序列模式挖掘中[16-19].

基于模式增長(zhǎng)策略的PrefixSpan算法是現(xiàn)有的序列模式挖掘算法中性能最好的算法之一，它不需要產(chǎn)生候選的序列模式，大大縮減了算法運(yùn)行需要的存儲(chǔ)空間.為提高PrefixSpan算法的效率以及適應(yīng)于各種應(yīng)用，很多學(xué)者提出了一些改進(jìn)算法.2019年Ganaphy等[17]對(duì)PrefixSpan算法進(jìn)行改進(jìn)，應(yīng)用于挖掘交通序列模式和基于交通序列規(guī)則的交通量預(yù)測(cè).2019年Niyazmand等[18]對(duì)PrefixSpan算法進(jìn)行改進(jìn)，應(yīng)用于發(fā)現(xiàn)不同洪水情況下的報(bào)警模式.2021年，Wang等[19]針對(duì)傳統(tǒng)的序列模式挖掘算法Prefix span存在時(shí)效性差、閾值均勻等缺點(diǎn)，提出了TVI-Prefixspan算法來(lái)挖掘傳銷模式，實(shí)驗(yàn)結(jié)果表明，TVI-Prefix span算法在效率和挖掘效果上均優(yōu)于傳統(tǒng)的序列模式挖掘算法.

序列模式挖掘在旅游熱門路線上有著廣泛的應(yīng)用，研究者們對(duì)其開(kāi)展了很多學(xué)術(shù)研究和探索.比如2017年，Vu等[9]使用Top-k序列規(guī)則挖掘算法[20]來(lái)挖掘旅游目的地，然而此算法不能有效的挖掘完整的旅游熱門線路.2019年孫文平等[21]利用PrefixSpan算法來(lái)挖掘旅游熱門景點(diǎn)，雖然挖掘到的景點(diǎn)有著時(shí)間先后關(guān)系，但是不具有線路的連續(xù)性.

2 PrefixSpan算法

2.1 基本定義

PrefixSpan算法的基本思想是使用遞歸的策略，從1階前綴開(kāi)始，不斷用頻繁的前綴劃分搜索空間，得到相應(yīng)的后綴數(shù)據(jù)庫(kù)，在后綴數(shù)據(jù)庫(kù)上進(jìn)行支持度統(tǒng)計(jì)并得到1階頻繁序列.再擴(kuò)展前綴，用高一階的前綴劃分空間，繼續(xù)向前推進(jìn).就這樣，前綴越來(lái)越長(zhǎng)，后綴數(shù)據(jù)庫(kù)中的后綴序列越來(lái)越短.最終，后綴數(shù)據(jù)庫(kù)為空時(shí)，頻繁序列搜索完畢.基于PrefixSpan算法的相關(guān)定義如下.

定義1(序列)s=〈l1,l2,…,lm〉是一個(gè)長(zhǎng)度為m的序列，li(1≤i≤m)為序列的項(xiàng)，代表一個(gè)旅游地點(diǎn)，長(zhǎng)度為m的序列為包含m個(gè)地點(diǎn)的旅游軌跡，稱為m階序列.

定義2(序列數(shù)據(jù)庫(kù))序列數(shù)據(jù)庫(kù)S是元組〈sid,s〉的集合，其中，sid是用戶ID，s是一個(gè)序列，即一個(gè)用戶的旅游軌跡.

例1表1是一個(gè)旅游的序列數(shù)據(jù)庫(kù)，s3=〈l1,l2,l6,l5〉是一個(gè)4階序列，即用戶依次旅游地點(diǎn)l1、l2、l6、l5的旅游軌跡.

表1 序列數(shù)據(jù)庫(kù)

定義3(前綴及后綴)設(shè)序列A=〈a1,a2,…,am〉，B=〈b1,b2,…,bn〉(m

例2表2為s4=〈l2,l6,l7,l8,l3,l1〉的一些前綴和對(duì)應(yīng)的后綴.

表2 前綴和后綴實(shí)例

定義4(后綴數(shù)據(jù)庫(kù)及后綴數(shù)據(jù)庫(kù)的支持度)設(shè)v為序列數(shù)據(jù)庫(kù)S中的一個(gè)序列，則v的后綴數(shù)據(jù)庫(kù)為v在序列數(shù)據(jù)庫(kù)S中后綴的集合，表示為S|v，序列v在其后綴數(shù)據(jù)庫(kù)中的支持度為序列數(shù)據(jù)庫(kù)中包含S|v的序列個(gè)數(shù).

例3序列〈l6,l7〉在表1序列數(shù)據(jù)庫(kù)S中的后綴數(shù)據(jù)庫(kù)如表3所示，即S|〈l6,l7〉={〈l5〉,〈l8,l3,l1〉,〈l4,l2,l1,l5〉}，序列〈l6,l7〉在其后綴數(shù)據(jù)庫(kù)中的支持度為3.

表3 后綴數(shù)據(jù)庫(kù)實(shí)例

定義5(頻繁序列)如果序列v在后綴數(shù)據(jù)庫(kù)S中的支持度不低于給定閾值min_support，則稱序列v為頻繁序列.

2.2 PrefixSpan算法的連續(xù)性問(wèn)題

2.2.1 PrefixSpan算法實(shí)例

下面以表1給出的序列數(shù)據(jù)庫(kù)S及min_support=2為例來(lái)描述PrefixSpan算法挖掘頻繁序列的過(guò)程.

Step 1 掃描序列數(shù)據(jù)庫(kù)S一次，找到所有的1階序列，對(duì)其進(jìn)行計(jì)數(shù).它們分別是〈l1〉:5、〈l2〉:5、〈l3〉:4、〈l4〉:2、〈l5〉:4、〈l6〉:5、〈l7〉:3和〈l8〉:1，其中符號(hào)“〈序列〉:計(jì)數(shù)”表示序列和它的支持度計(jì)數(shù).〈l8〉的支持度低于2，將〈l8〉從序列數(shù)據(jù)庫(kù)中刪去，即s4=〈l2,l6,l7,l3,l1〉.

Step 2 用每個(gè)頻繁的1階序列作為前綴來(lái)劃分空間，構(gòu)造相應(yīng)的后綴數(shù)據(jù)庫(kù)，如表4所示.

Step 3 對(duì)于每個(gè)1階前綴，統(tǒng)計(jì)后綴數(shù)據(jù)庫(kù)中各項(xiàng)的支持度計(jì)數(shù).出現(xiàn)在后綴數(shù)據(jù)庫(kù)中1階前綴后面的項(xiàng)都要統(tǒng)計(jì)其支持度，不管是否相鄰.例如：在后綴數(shù)據(jù)庫(kù)中〈l3〉前綴后面出現(xiàn)的項(xiàng)有〈l1〉、〈l2〉、〈l3〉、〈l4〉、〈l5〉、〈l6〉和〈l7〉.將滿足支持度計(jì)數(shù)的項(xiàng)〈l1〉、〈l2〉、〈l5〉和〈l6〉與當(dāng)前前綴〈l3〉進(jìn)行合并，得到新的前綴〈l3,l1〉、〈l3,l2〉、〈l3,l5〉和〈l3,l6〉.

Step 4 以新的前綴〈l3,l2〉為例來(lái)說(shuō)明后續(xù)挖掘過(guò)程，掃描以〈l3〉為前綴的后綴數(shù)據(jù)庫(kù)，構(gòu)造以〈l3,l2〉為前綴的后綴數(shù)據(jù)庫(kù)，統(tǒng)計(jì)新的后綴數(shù)據(jù)庫(kù)中各項(xiàng)的支持度計(jì)數(shù).統(tǒng)計(jì)支持度時(shí)和Step 3相似，出現(xiàn)在〈l3,l2〉后面的項(xiàng)都要統(tǒng)計(jì)，不管是否與〈l3,l2〉相鄰.結(jié)果如表5第1行所示.

Step 5 將滿足支持度計(jì)數(shù)的項(xiàng)〈l1〉、〈l5〉分別與〈l3,l2〉進(jìn)行合并，得到新的前綴〈l3,l2,l1〉和〈l3,l2,l5〉，如表5第2、3行所示.

表4 PrefixSpan算法的一階頻繁序列及后綴數(shù)據(jù)庫(kù)

表5 以〈l3,l2〉為首的頻繁序列及后綴數(shù)據(jù)庫(kù)

Step 6 此時(shí)以〈l3,l2,l5〉為前綴的后綴數(shù)據(jù)庫(kù)中沒(méi)有滿足支持度計(jì)數(shù)的單項(xiàng)，即停止對(duì)〈l3,l2,l5〉的擴(kuò)展.在以〈l3,l2,l1〉為前綴的后綴數(shù)據(jù)庫(kù)中，將滿足支持度計(jì)數(shù)的項(xiàng)〈l5〉與前綴〈l3,l2,l1〉進(jìn)行合并，得到新的前綴〈l3,l2,l1,l5〉，此時(shí)以〈l3,l2,l1,l5〉為前綴的后綴數(shù)據(jù)庫(kù)中沒(méi)有滿足支持度計(jì)數(shù)的單項(xiàng)，即停止對(duì)〈l3,l2,l1,l5〉的擴(kuò)展.即以前綴〈l3,l2〉為首的頻繁序列為〈l3,l2〉、〈l3,l2,l1〉、〈l3,l2,l5〉、〈l3,l2,l1,l5〉.

Step 7 以〈l3〉為首的其他前綴的擴(kuò)展過(guò)程同理，以〈l3〉為首的頻繁序列為：〈l3〉、〈l3,l1〉、〈l3,l2〉、〈l3,l5〉、〈l3,l6〉、〈l3,l1,l5〉、〈l3,l2,l1〉、〈l3,l2,l5〉、〈l3,l5,l6〉、〈l3,l6,l5〉、〈l3,l6,l7〉、〈l3,l2,l1,l5〉和〈l3,l6,l7,l5〉.

2.2.2 連續(xù)性問(wèn)題分析及改進(jìn)策略

將PrefixSpan算法應(yīng)用于旅游序列數(shù)據(jù)庫(kù)中，會(huì)出現(xiàn)連續(xù)性問(wèn)題.比如例5中得到的頻繁序列〈l3,l2,l5〉，雖然〈l3〉、〈l2〉與〈l5〉在序列數(shù)據(jù)庫(kù)中有著先后順序關(guān)系，可是運(yùn)用在旅游路線上，〈l3〉、〈l2〉與〈l5〉之間并不直達(dá)，頻繁序列〈l3,l2,l5〉作為一個(gè)旅游熱門路線就沒(méi)有意義，本文對(duì)這種不連續(xù)關(guān)系做了優(yōu)化改進(jìn).

PrefixSpan算法應(yīng)用在旅游熱門路線挖掘中，需要充分考慮路線的連續(xù)性，主要有兩方面不足需要改進(jìn)：

第1，PrefixSpan算法對(duì)于1階不頻繁序列，將其直接從序列數(shù)據(jù)庫(kù)中刪除，這會(huì)導(dǎo)致數(shù)據(jù)庫(kù)中包含此序列的序列不連續(xù)，進(jìn)而導(dǎo)致挖掘出的結(jié)果存在誤差.

第2，此算法在挖掘頻繁序列時(shí)，對(duì)后綴數(shù)據(jù)庫(kù)出現(xiàn)在前綴后的每個(gè)單項(xiàng)都進(jìn)行支持度計(jì)數(shù)，不管它是否緊鄰當(dāng)前的前綴，忽略了序列的連續(xù)性.挖掘出的頻繁序列跳過(guò)了一些地點(diǎn)，連貫性不足.

針對(duì)以上2個(gè)問(wèn)題，本文將PrefixSpan算法進(jìn)行如下改進(jìn)：

第1，為防止出現(xiàn)不連續(xù)的現(xiàn)象，從序列數(shù)據(jù)庫(kù)中刪去1階不頻繁序列之后，再將其左、右子序列分別放回序列數(shù)據(jù)庫(kù).

第2，為了保證挖掘到的序列是連續(xù)的，挖掘頻繁序列時(shí)，只對(duì)后綴數(shù)據(jù)庫(kù)中各序列的首項(xiàng)進(jìn)行支持度計(jì)數(shù).

3 改進(jìn)的PrefixSpan算法

3.1 改進(jìn)的PrefixSpan算法描述

改進(jìn)的PrefixSpan算法(本文稱之Im_Prefixspan算法)的主要步驟如下：

Step 1 掃描序列數(shù)據(jù)庫(kù)S一次，找到所有的1階序列，對(duì)其進(jìn)行計(jì)數(shù).如果某個(gè)1階序列的支持度小于閾值，就將其所在序列以它為界一分為二，其左、右子序列分別放回序列數(shù)據(jù)庫(kù)，并將原序列從序列數(shù)據(jù)庫(kù)中刪除.

Step 2 用所有頻繁的1階序列作為前綴來(lái)劃分空間，構(gòu)造相應(yīng)的后綴數(shù)據(jù)庫(kù).

Step 3 對(duì)于每個(gè)L(L≥1)階前綴，只掃描后綴數(shù)據(jù)庫(kù)中序列的首項(xiàng)進(jìn)行計(jì)數(shù).如果支持度計(jì)數(shù)低于閾值，則將該首項(xiàng)對(duì)應(yīng)的序列從后綴數(shù)據(jù)庫(kù)中刪去，停止對(duì)該首項(xiàng)的擴(kuò)展.

Step 4 將滿足支持度計(jì)數(shù)的各個(gè)首項(xiàng)和當(dāng)前的前綴進(jìn)行合并，得到若干新的前綴.

Step 5 令L=L+1，掃描當(dāng)前后綴數(shù)據(jù)庫(kù)，以新的前綴來(lái)構(gòu)造相應(yīng)的后綴數(shù)據(jù)庫(kù).返回到第3步，直至后綴數(shù)據(jù)庫(kù)為空.

3.2 改進(jìn)的PrefixSpan算法實(shí)例

下面以表1中的序列數(shù)據(jù)庫(kù)S及min_support=2為例，來(lái)描述Im_PrefixSpan算法挖掘過(guò)程.

Step 1 掃描序列數(shù)據(jù)庫(kù)S一次，找到所有的1階序列，對(duì)其進(jìn)行計(jì)數(shù).它們分別是〈l1〉:5、〈l2〉:5、〈l3〉:4、〈l4〉:2、〈l5〉:4、〈l6〉:5、〈l7〉:3和〈l8〉:1.〈l8〉的支持度計(jì)數(shù)小于2，將其所在序列s4=〈l6,l7,l8,l3,l1〉，以〈l8〉為界分為s4.1=〈l6,l7〉和s4.2=〈l3,l1〉 2個(gè)左、右子序列，放回序列數(shù)據(jù)庫(kù)，并將原序列s4從序列數(shù)據(jù)庫(kù)中刪除.

Step 2 用〈l1〉、〈l2〉、〈l3〉、〈l4〉、〈l5〉、〈l6〉和〈l7〉分別作為前綴來(lái)劃分空間，構(gòu)造相應(yīng)的后綴數(shù)據(jù)庫(kù)，如表6所示.

表6 Im_PrefixSpan算法的一階頻繁序列及后綴數(shù)據(jù)庫(kù)

Step 3對(duì)于每個(gè)1階前綴，只掃描后綴數(shù)據(jù)庫(kù)中序列的首項(xiàng)進(jìn)行計(jì)數(shù).以〈l3〉為例來(lái)說(shuō)明，以〈l3〉為前綴的后綴數(shù)據(jù)庫(kù)中，首項(xiàng)〈l1〉和〈l2〉的支持度計(jì)數(shù)低于閾值，則將對(duì)應(yīng)的序列〈l1〉、〈l2,l1,l5,l6〉從后綴數(shù)據(jù)庫(kù)中刪去，停止對(duì)首項(xiàng)〈l1〉和〈l2〉的擴(kuò)展.

Step 4 將滿足支持度計(jì)數(shù)的首項(xiàng)〈l6〉和當(dāng)前的前綴〈l3〉進(jìn)行合并，得到新的前綴〈l3,l6〉.

Step 5 掃描以〈l3〉為前綴的后綴數(shù)據(jù)庫(kù)，以新的前綴〈l3,l6〉來(lái)構(gòu)造相應(yīng)的后綴數(shù)據(jù)庫(kù)，如表7所示.以〈l3,l6〉為前綴的后綴數(shù)據(jù)庫(kù)中，首項(xiàng)〈l7〉滿足支持度計(jì)數(shù)，將其和當(dāng)前的前綴〈l3,l6〉進(jìn)行合并，得到新的前綴〈l3,l6,l7〉.

表7 以〈l3〉為首的頻繁序列及后綴數(shù)據(jù)庫(kù)

Step 6 掃描以〈l3,l6〉為前綴的后綴數(shù)據(jù)庫(kù)，以新的前綴〈l3,l6,l7〉來(lái)構(gòu)造相應(yīng)的后綴數(shù)據(jù)庫(kù).以〈l3,l6,l7〉為前綴的后綴數(shù)據(jù)庫(kù)中，首項(xiàng)〈l5〉和〈l4〉都不滿足支持度計(jì)數(shù)，將對(duì)應(yīng)的序列〈l5〉和〈l4,l2,l1,l5〉從后綴數(shù)據(jù)庫(kù)中刪除，后綴數(shù)據(jù)庫(kù)為空，停止對(duì)〈l3,l6,l7〉的擴(kuò)展.即以〈l3〉為首的頻繁序列為〈l3〉、〈l3,l6〉和〈l3,l6,l7〉.

通過(guò)和2.2.1節(jié)中PrefixSpan算法挖掘的結(jié)果對(duì)比可以發(fā)現(xiàn)，Im_PrefixSpan算法挖掘出的頻繁序列更連續(xù)、更簡(jiǎn)潔.

4 實(shí)驗(yàn)結(jié)果及性能分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)是在python 3.7.2版本、Intel Core i5 2.5 GHz 和4GB內(nèi)存的Windows 10實(shí)驗(yàn)環(huán)境下完成的.從攜程旅行網(wǎng)站(https://www.ctrip.com/)爬取了與云南省旅游相關(guān)的 42 639 條游記，每條游記包括旅游的時(shí)間、旅行時(shí)長(zhǎng)、人均花費(fèi)和人物類型等屬性.因?yàn)楸疚目紤]的是城市級(jí)別的旅游路線，所以對(duì)于挖掘到的結(jié)果進(jìn)行預(yù)處理，將游記中的地點(diǎn)映射到城市層面上，得到云南省的16個(gè)城市分別為昆明、大理、保山、麗江、德宏、楚雄、西雙版納、文山、曲靖、怒江、迪慶、紅河、玉溪、普洱、昭通和臨滄.刪除了路線中城市數(shù)目少于2的路線，最終獲取到 7 468 條不同的旅游軌跡數(shù)據(jù).實(shí)驗(yàn)數(shù)據(jù)示例如表8所示.

表8 實(shí)驗(yàn)數(shù)據(jù)示例

4.2 實(shí)驗(yàn)效果分析

把Im_Prefixspan算法應(yīng)用于旅行軌跡數(shù)據(jù)庫(kù)(即序列數(shù)據(jù)庫(kù))后，在min_support=70的情況下，得到了107條云南省旅游熱門路線.以經(jīng)過(guò)昆明的4條路線為例，如圖1所示，圖1(a)是游客經(jīng)過(guò)昆明的旅游最熱門路線，這也說(shuō)明了游客來(lái)云南旅行，通常會(huì)選擇昆明→大理→麗江→大理→迪慶→西雙版納這條線路，經(jīng)了解這條線路是旅行社已經(jīng)推出的經(jīng)典線路.除了圖1(a)路線以外，其他三條路線也很受游客青睞.從圖中可以看出，這些路線的城市間相鄰且距離較近，并都包含了云南省特色景點(diǎn)，是便捷高效且深入了解云南特色的重要線路，可以推薦給旅行社.

圖1 云南省旅游熱門路線

4.3 實(shí)驗(yàn)性能分析

本節(jié)，將從參數(shù)和可伸縮性兩方面對(duì)算法的性能進(jìn)行分析，結(jié)果如圖2、圖3所示.

4.3.1 參數(shù)

把Im_Prefixspan算法和PrefixSpan算法分別應(yīng)用于旅行軌跡數(shù)據(jù)庫(kù)中，在不改變數(shù)據(jù)集的情況下，只改變支持度閾值，得到的支持度閾值與頻繁序列長(zhǎng)度的關(guān)系如圖2所示，支持度閾值與算法運(yùn)行時(shí)間的關(guān)系如圖3所示.

圖2(a)是隨著支持度閾值變化得到的頻繁序列的最大長(zhǎng)度的趨勢(shì)圖. 圖2(b)是隨著支持度閾值變化得到的頻繁序列的平均長(zhǎng)度的趨勢(shì)圖.從圖2中可以看出，隨著支持度閾值的增加，Im_Prefixspan算法和PrefixSpan算法得到頻繁序列的最大長(zhǎng)度和平均長(zhǎng)度都隨之減少.支持度閾值是劃分頻繁序列與不頻繁序列的標(biāo)準(zhǔn)，支持度閾值的增加會(huì)導(dǎo)致頻繁序列的數(shù)目減少，由于頻繁序列挖掘是按照低階到高階的順序進(jìn)行工作的，因此頻繁序列的最大長(zhǎng)度和平均長(zhǎng)度也都隨之減少.在同一條件下，Im_Prefixspan算法比PrefixSpan算法得到頻繁序列的最大長(zhǎng)度和平均長(zhǎng)度要短，這是由于Im_Prefixspan算法在連續(xù)性上對(duì)PrefixSpan算法進(jìn)行改進(jìn)，在統(tǒng)計(jì)后綴數(shù)據(jù)庫(kù)中各項(xiàng)的支持度計(jì)數(shù)時(shí)，只對(duì)首項(xiàng)進(jìn)行計(jì)數(shù)來(lái)判斷序列是否為頻繁序列，而PrefixSpan算法在統(tǒng)計(jì)后綴數(shù)據(jù)庫(kù)中各項(xiàng)的支持度計(jì)數(shù)時(shí)，要掃描后綴數(shù)據(jù)庫(kù)中的每一項(xiàng)來(lái)統(tǒng)計(jì)后綴數(shù)據(jù)庫(kù)中各項(xiàng)的支持度計(jì)數(shù)，所以Im_Prefixspan算法相對(duì)于PrefixSpan算法剪掉了一部分不連續(xù)序列，從而導(dǎo)致Im_Prefixspan算法比PrefixSpan算法頻繁序列的最大長(zhǎng)度和平均長(zhǎng)度要短.

圖3是隨著支持度閾值的變化得到的算法運(yùn)行時(shí)間趨勢(shì)圖.從圖3中可以看出隨著支持度閾值的增加，Im_Prefixspan算法和PrefixSpan算法的運(yùn)行時(shí)間都隨之減少.原因是支持度閾值的增加會(huì)導(dǎo)致頻繁序列的數(shù)目減少，構(gòu)造和搜索后綴數(shù)據(jù)庫(kù)的時(shí)間都會(huì)變少. 在同一條件下， Im_Prefixspan算法比PrefixSpan算法的運(yùn)行時(shí)間要少，這是由于Im_Prefixspan算法在統(tǒng)計(jì)后綴數(shù)據(jù)庫(kù)中各項(xiàng)的支持度計(jì)數(shù)時(shí)，只對(duì)首項(xiàng)進(jìn)行計(jì)數(shù)來(lái)判斷序列是否為頻繁序列，而PrefixSpan算法在統(tǒng)計(jì)后綴數(shù)據(jù)庫(kù)中各項(xiàng)的支持度計(jì)數(shù)時(shí)，要掃描后綴數(shù)據(jù)庫(kù)中的每一項(xiàng)來(lái)統(tǒng)計(jì)后綴數(shù)據(jù)庫(kù)中各項(xiàng)的支持度計(jì)數(shù)，從而導(dǎo)致Im_Prefixspan算法比PrefixSpan算法的運(yùn)行時(shí)間要少.

圖2 支持度閾值與頻繁序列的最大、平均長(zhǎng)度的關(guān)系

圖3 支持度閾值與算法運(yùn)行時(shí)間的關(guān)系

4.3.2 可伸縮性

對(duì)旅行軌跡數(shù)據(jù)庫(kù)進(jìn)行處理，將 7 468 條序列按時(shí)間順序進(jìn)行排列，刪除距今時(shí)間最遠(yuǎn)的序列，得到前 7 000 條序列，在固定閾值min_support=70的情況下，把Im_Prefixspan算法和PrefixSpan算法分別應(yīng)用于旅行軌跡數(shù)據(jù)庫(kù)中，得到的序列數(shù)據(jù)庫(kù)規(guī)模、最長(zhǎng)序列長(zhǎng)度與算法運(yùn)行時(shí)間的關(guān)系如圖4，城市數(shù)目與算法運(yùn)行時(shí)間的關(guān)系圖5所示.

圖4 序列數(shù)據(jù)庫(kù)規(guī)模、最大序列長(zhǎng)度與算法運(yùn)行時(shí)間的關(guān)系

圖5 城市數(shù)目與算法運(yùn)行時(shí)間的關(guān)系

圖4(a)是隨著序列數(shù)據(jù)庫(kù)規(guī)模的變化得到的算法運(yùn)行時(shí)間趨勢(shì)圖.序列數(shù)據(jù)庫(kù)規(guī)模的變化是通過(guò)對(duì) 7 000 條序列以 1 000 條為步長(zhǎng)，依次刪除距今時(shí)間最遠(yuǎn)的序列得到的.從圖4(a)中可以看出，隨著序列數(shù)據(jù)庫(kù)規(guī)模的增加，Im_Prefixspan算法和PrefixSpan算法運(yùn)行時(shí)間都增長(zhǎng)很快.原因是序列數(shù)據(jù)庫(kù)規(guī)模的增加，導(dǎo)致掃描序列數(shù)據(jù)庫(kù)和構(gòu)建、掃描后綴數(shù)據(jù)庫(kù)的時(shí)間較長(zhǎng).

圖4(b)是隨著序列數(shù)據(jù)庫(kù)中最大序列長(zhǎng)度的變化得到的算法運(yùn)行時(shí)間趨勢(shì)圖.從圖4(b)中可以看出隨著序列長(zhǎng)度的增加，Im_Prefixspan算法和PrefixSpan算法運(yùn)行時(shí)間增加的都特別快.原因是隨著序列的最大長(zhǎng)度的增加，增大了掃描序列數(shù)據(jù)庫(kù)的時(shí)間，以及構(gòu)建后綴數(shù)據(jù)庫(kù)的次數(shù)，比如最大序列長(zhǎng)度為13時(shí)，最多需要構(gòu)建從第1層到第12層的后綴數(shù)據(jù)庫(kù).由圖2(a)可知序列在閾值min_support=7時(shí)，Im_Prefixspan算法得到頻繁序列的最大長(zhǎng)度是13，所以本實(shí)驗(yàn)選擇長(zhǎng)度為13以內(nèi)的序列來(lái)測(cè)試序列的最大長(zhǎng)度與算法運(yùn)行時(shí)間的關(guān)系，即將序列數(shù)據(jù)庫(kù)中序列長(zhǎng)度超過(guò)13的部分刪除，通過(guò)對(duì) 7 000 條序列從長(zhǎng)度13開(kāi)始以1為步長(zhǎng)，依次刪除來(lái)進(jìn)行測(cè)試.

圖5是隨著城市數(shù)目的變化得到的算法運(yùn)行時(shí)間趨勢(shì)圖.從圖5中可以看出隨著城市數(shù)目的增加，Im_Prefixspan算法和PrefixSpan算法的性能都有下降.原因是隨著城市數(shù)目的增加，創(chuàng)建的后綴數(shù)據(jù)庫(kù)的數(shù)目也隨之增加，比如對(duì)于兩個(gè)城市a,b,c，只需要?jiǎng)?chuàng)建關(guān)于序列a,b,c為首的后綴數(shù)據(jù)庫(kù).城市數(shù)目按照昆明、大理、保山、麗江、德宏、楚雄、西雙版納、文山、曲靖、怒江、迪慶、紅河、玉溪、普洱、昭通和臨滄的順序進(jìn)行處理，城市數(shù)目是2時(shí)，只保留序列數(shù)據(jù)庫(kù)中的城市昆明、大理，其他城市全部刪除，其他數(shù)目同理，從而得到如圖5所示隨著城市數(shù)目變化的算法性能趨勢(shì)圖.

根據(jù)實(shí)驗(yàn)可得，在同等條件下Im_Prefixspan算法比PrefixSpan算法的運(yùn)行時(shí)間都要少，原理在上節(jié)“圖3 支持度閾值與算法運(yùn)行時(shí)間的關(guān)系”中已做解釋.

5 結(jié)語(yǔ)

針對(duì)旅游熱門路線的問(wèn)題，考慮游客在旅游過(guò)程中對(duì)路線連貫的需要，改進(jìn)了PrefixSpan算法，彌補(bǔ)了PrefixSpan算法應(yīng)用在旅游路線上連續(xù)性不足的問(wèn)題，并提高了算法的效率.通過(guò)示例可以看出，文中提出的算法較原算法在處理旅游熱門路線問(wèn)題上具有更好的連續(xù)性和簡(jiǎn)潔性.

本文的工作還可以從下面2個(gè)角度進(jìn)行深入研究.第1，僅對(duì)城市旅游路線進(jìn)行挖掘，以后的研究可以進(jìn)一步考慮景點(diǎn)或者國(guó)家級(jí)別的熱門旅游路線推薦.第2，在推薦熱門旅游路線上主要考慮了連續(xù)性，在以后的研究中可以考慮增加對(duì)旅游時(shí)長(zhǎng)和旅游時(shí)間的約束，為游客推薦更為人性化的結(jié)果.