改進的PrefixSpan算法在旅游熱門路線上的應(yīng)用

胡冰冰，蘆俊麗，鄭承宇

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

2 PrefixSpan算法

2.1 基本定義

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

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

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

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

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

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

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

表2 前綴和后綴實例

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

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

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

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

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

2.2.1 PrefixSpan算法實例

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

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

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

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

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

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

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

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

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

Step 7 以〈l3〉為首的其他前綴的擴展過程同理，以〈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ù)性問題分析及改進策略

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

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

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

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

針對以上2個問題，本文將PrefixSpan算法進行如下改進：

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

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

3 改進的PrefixSpan算法

3.1 改進的PrefixSpan算法描述

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

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

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

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

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

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

3.2 改進的PrefixSpan算法實例

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

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

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

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

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

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

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

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

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

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

4 實驗結(jié)果及性能分析

4.1 實驗數(shù)據(jù)

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

表8 實驗數(shù)據(jù)示例

4.2 實驗效果分析

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

圖1 云南省旅游熱門路線

4.3 實驗性能分析

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

4.3.1 參數(shù)

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

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

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

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

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

4.3.2 可伸縮性

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

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

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

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

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

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

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

5 結(jié)語

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

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