基于動態(tài)聚類的旅游線路推薦

肖春景，夏克文，喬永衛(wèi)，張宇翔

(1.河北工業(yè)大學(xué) 電子信息工程學(xué)院，天津 300300； 2.中國民航大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，天津 300300；3.中國民航大學(xué) 工程技術(shù)訓(xùn)練中心，天津 300300)

(*通信作者電子郵箱kwxia@hebut.edu.cn)

基于動態(tài)聚類的旅游線路推薦

肖春景1,2，夏克文1*，喬永衛(wèi)3，張宇翔2

(1.河北工業(yè)大學(xué) 電子信息工程學(xué)院，天津 300300； 2.中國民航大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，天津 300300；3.中國民航大學(xué) 工程技術(shù)訓(xùn)練中心，天津 300300)

(*通信作者電子郵箱kwxia@hebut.edu.cn)

基于會話的協(xié)同過濾用固定時間窗劃分交互歷史并將用戶興趣表示為這些階段的序列，但是旅游數(shù)據(jù)的高稀疏性會導(dǎo)致某些階段內(nèi)沒有交互行為和近鄰相似度計算困難的問題。為了緩解數(shù)據(jù)稀疏，有效利用數(shù)據(jù)特性，提出了基于動態(tài)聚類的旅游線路推薦算法。該方法首先分析了旅游數(shù)據(jù)不同于其他標(biāo)準(zhǔn)數(shù)據(jù)的特性；其次利用動態(tài)聚類得到的變長時間窗口對游客交互歷史進行劃分，利用潛在狄利克雷分布(LDA) 抽取每個階段的概率主題分布，結(jié)合時間懲罰權(quán)值建立用戶興趣漂移模型；接著，通過反映年齡、線路季節(jié)、價格等因素的游客特征向量為目標(biāo)游客選擇近鄰和候選線路集合；最后根據(jù)候選線路和游客的概率主題相關(guān)度完成線路推薦。該方法通過采用變長時間窗口不但緩解了數(shù)據(jù)稀疏，而且劃分的階段數(shù)目不需提前指定，而是根據(jù)數(shù)據(jù)特性自動生成；近鄰選擇時采用特征向量而非旅游數(shù)據(jù)進行相似度計算，避免了由于數(shù)據(jù)稀疏無法計算的問題。在實際旅游數(shù)據(jù)上的大量實驗結(jié)果表明，該方法不僅很好適應(yīng)了旅游數(shù)據(jù)特征，而且提高了旅游線路的推薦精度。

動態(tài)聚類；潛在狄利克雷分布； 興趣模型； 時間懲罰； 特征向量

0 引言

隨著人們生活水平的提高，旅游已經(jīng)成為休閑娛樂的重要方式。據(jù)統(tǒng)計近幾年來旅游人數(shù)和收入都在以10%以上的速度增長。為了爭取客源，旅游公司需了解游客的需求，制定各式各樣具有吸引力的旅游線路，但是游客從大量的線路中選出適合自己的線路是一件困難的事情。推薦系統(tǒng)成為解決“信息過載”的主要手段，將其應(yīng)用到旅游線路的推薦將極大提升游客的體驗并給旅游公司帶來收益。

推薦系統(tǒng)已經(jīng)貫穿了旅游的整個過程，包括旅游前的線路推薦[1-2]，旅游中利用移動設(shè)備進行的個性化服務(wù)推薦[3-6]以及旅游結(jié)束時的信息反饋[7]。目前的線路推薦一般是根據(jù)游客的位置，利用地理信息系統(tǒng)(Geographic Information System，GIS)和移動設(shè)備對周邊線路或地點進行推薦[3-6]。但是由于游客出游往往受到氣候、時間的限制并且用戶的興趣也會隨時間而變化，因此時間對于路線的選擇至關(guān)重要。Liu等[8]以在一定時間段內(nèi)花費最少、但是到達更多的目的地為前提進行線路推薦;Shen等[9]設(shè)計了個性化相似模型并利用用戶的異構(gòu)旅行信息在某一時刻的某一地點位置進行推薦；Hasuike等[10]利用時間依賴網(wǎng)絡(luò)解決了旅游和景點次數(shù)的隨機變化問題，并通過條件概率來選擇下一個景點；孫煥良等[11]提出了基于動態(tài)轉(zhuǎn)移圖的時間敏感的旅游路線推薦方法為用戶準(zhǔn)確地推薦適合其出行時間的最佳旅游線路；She等[12]設(shè)計了兩步貪心啟發(fā)式算法來進行下一個目的地的預(yù)測，它不但考慮了時空沖突，而且解決了數(shù)據(jù)稀疏的問題；陸國鋒等[13]提取景點的開放時間、門票、GIS坐標(biāo)、景點的評價信息等提出一種基于多約束的K貪心算法，可以為游客推薦較好的旅游線路，并有效消除了推薦系統(tǒng)對先驗知識的依賴。這些推薦模型雖然都考慮了時間因素，但是僅作為約束條件或考慮了景點間的時間依賴關(guān)系。但在實際的線路選擇過程中，一條線路是否會被某用戶選擇，往往受線路主題和用戶興趣的共同影響。潛在狄利克雷分布(Latent Dirichlet Allocation，LDA)概率主題模型是文本挖掘領(lǐng)域用來發(fā)現(xiàn)文本主題的重要方法，并已擴展和應(yīng)用到推薦領(lǐng)域挖掘用戶的潛在興趣。He等[14]利用LDA從文檔中挖掘隱主題并根據(jù)協(xié)同過濾得到的預(yù)測評分決定哪個線路是最適合用戶的,但它沒有考慮用戶興趣隨時間的變化。基于會話的協(xié)同過濾(Session-based Collaborative Filtering, Session-based CF)模型利用固定的時間窗劃分用戶的交互歷史以捕獲用戶興趣模式的變化[15-16]；而將基于會話的協(xié)同過濾與LDA模型相結(jié)合挖掘每個會話的概率主題分布來建立用戶的動態(tài)興趣模型[17-18]，可以更好地捕獲用戶興趣主題的變化。但是與商品、電影等的推薦相比，旅游數(shù)據(jù)的稀疏性更高，這使得利用固定窗口對交互歷史進行劃分的過程中，某些窗口的歷史數(shù)據(jù)很少甚至沒有歷史數(shù)據(jù)，無法用來進行用戶興趣模型建立，更加劇了數(shù)據(jù)的稀疏性；而且由于數(shù)據(jù)稀疏使得選擇近鄰時的相似度計算變得十分困難。

為了緩解數(shù)據(jù)稀疏，通過結(jié)合LDA和時序信息提出了基于動態(tài)聚類的旅游線路推薦方法。該方法利用動態(tài)聚類采用變長時間窗口對游客交互歷史進行劃分，不但緩解了數(shù)據(jù)稀疏，而且聚類個數(shù)不用事先指定，而是根據(jù)游客數(shù)據(jù)自動形成，更好地適應(yīng)了數(shù)據(jù)特點；結(jié)合時間懲罰權(quán)值和概率主題分布很好地描述了用戶興趣模式隨時間的變化趨勢；根據(jù)游客年齡、出行季節(jié)特點和線路價格建立用戶特征向量解決了由于數(shù)據(jù)稀疏導(dǎo)致的近鄰選擇困難的問題。在實際旅游數(shù)據(jù)集上大量實驗結(jié)果表明，該方法有效地利用了旅游數(shù)據(jù)的特點，能較準(zhǔn)確地為游客進行線路推薦。

1 旅游數(shù)據(jù)特性分析

旅游數(shù)據(jù)來源于廈門航空旗下的某旅游公司，共包括從2009年1月到2014年10月間的732 019條旅游記錄。本文抽取了4 737個游客對1 436條旅游線路的25 717條旅行記錄，每個游客至少旅行過3次。每條記錄包括旅客信息和線路信息，其中旅客信息包括旅游團號、姓名、性別、身份證號、出發(fā)時間、價格等；線路信息包括出發(fā)時間、價格及景點的詳細介紹。

1.1 高稀疏性

游客每年旅行的次數(shù)非常有限，但是用戶購物或看電影卻非常普遍，因此旅游數(shù)據(jù)相比其他的推薦標(biāo)準(zhǔn)數(shù)據(jù)集稀疏度更高。將本文采集的旅游數(shù)據(jù)集與標(biāo)準(zhǔn)電影推薦數(shù)據(jù)集(Movelens_100K)進行比較，而且為了更好地進行對比，電影評分?jǐn)?shù)量是旅游次數(shù)的10倍，即圖1中旅游次數(shù)是橫坐標(biāo)數(shù)值的1/10；同時采用人數(shù)百分比(即對應(yīng)橫軸數(shù)值相應(yīng)的人數(shù)占總?cè)藬?shù)的比例)作為稀疏性的衡量指標(biāo)，旅游或電影評分?jǐn)?shù)量少的人數(shù)占比越大，說明數(shù)據(jù)越稀疏。具體對比情況如圖1所示，可以看出隨著旅游次數(shù)的增加，游客的人數(shù)百分比快速下降，超過95%的游客的旅行次數(shù)都少于10(在橫坐標(biāo)在100附近)；而Movielens數(shù)據(jù)集隨著電影評分?jǐn)?shù)量的增加用戶評分的百分比也在下降，但是下降速度要明顯慢于旅游數(shù)據(jù)，而且數(shù)量越大，差距越明顯。

圖1 旅游數(shù)據(jù)集與標(biāo)準(zhǔn)電影推薦數(shù)據(jù)集的稀疏度對比Fig. 1 Comparison of sparsity between tourism data and standard movie recommendation data

1.2 時序特性

旅游是休閑娛樂的重要方法，容易受到季節(jié)、空閑時間等因素的影響。將游客的旅游線路按照月份進行劃分統(tǒng)計的結(jié)果如圖2所示，可以看出，游客更愿意在氣候宜人的春秋兩季出游。就每個游客而言，選擇出游的時間分布比較集中。

圖2 游客出游月份統(tǒng)計Fig. 2 Statistics of tourist travel month

圖3對每個游客的出行時間進行了統(tǒng)計，可以看出超過70%的游客旅行集中在4個月份以內(nèi)，說明游客會在每年相對固定的時間出游。因此可以看出游客對線路的選擇受到季節(jié)的影響，并且每個人出行的時間相對固定。

圖3 旅客出游月份分布特征Fig.3 Distribution of tourist travel month

1.3 游客年齡及線路價格特征

游客的年齡分布與是否有閑暇時間和是否有較強的經(jīng)濟實力兩個主要因素有關(guān)，根據(jù)這兩個因素將年齡按6段分別進行了統(tǒng)計，結(jié)果如圖4所示。從圖4可以看出，游客的主力軍集中在1～18歲，26～35和36～50歲，占比超過游客總數(shù)的70%。分析可能原因是1～18歲多為求學(xué)階段的學(xué)生，有時間充裕的寒暑假，他們更可能會跟隨父母或自己結(jié)伴去旅游；而他們的父母年齡多集中在26～50歲，并且26～35和36～50歲這兩個群體經(jīng)濟能力相對較強，旅游成為了他們休閑娛樂的重要方式。

圖4 游客年齡分布Fig. 4 Distribution of tourist age

電影、購物等價格往往和時間是無關(guān)的，而旅游線路價格的高低往往與旅游時長相關(guān)：旅游時間越長，價格越高；相反，旅游時間越短，價格越低。圖5統(tǒng)計了游客選擇線路的價格情況，可以看出隨著價格的增長，選擇的游客人數(shù)逐步減少，約70%的游客選擇了價格在500元以下的線路，500～2 000元的比例基本持平，3 000及3 000元以上的百分比也較接近。因此可以認為人們更喜歡價格便宜、時間短的短途旅游線路，而線路價格達到一定數(shù)值之后，價格因素的影響變小。

圖5 線路價格分布Fig. 5 Distribution of route price

從以上分析可以看出，旅游數(shù)據(jù)相比其他標(biāo)準(zhǔn)數(shù)據(jù)集有更高的稀疏性，游客選擇線路受到季節(jié)、線路價格的影響，并且游客的年齡也是影響其出行的重要因素。因此，在線路推薦過程中應(yīng)充分考慮到旅游數(shù)據(jù)的特點，設(shè)計合適的推薦算法，以得到更好的推薦效果。

2 游客興趣漂移模型的建立

2.1 基于動態(tài)聚類的旅行記錄的劃分

基于會話的協(xié)同過濾用固定時間窗將用戶的交互歷史劃分成不同的階段，并將用戶的興趣模型表示成這些階段的序列表示。但是由于旅游數(shù)據(jù)的高稀疏性及游客出行時段的相對固定，固定大小時間窗的劃分不適用于旅游數(shù)據(jù)。因為采用固定時間窗進行劃分不但要用非常大的時間窗，而且會導(dǎo)致部分階段內(nèi)完全沒有旅游行為，這將加劇數(shù)據(jù)的稀疏性。因此本文考慮按照每個游客實際交互歷史的特點將其動態(tài)劃分成不同的階段。

定義游客集合U={u1,u2,…,um}，旅游歷史記錄集合H={Hu1,Hu2,…,Hum}，旅游線路集合L={l1,l2,…,ln}。首先計算所有旅客的平均旅游時間并作為最小時間窗口γ，對每個游客計算每個線路的密度并按降序排序。接著選擇密度最大的線路作為第一個聚類中心，并計算已有聚類中心與其他節(jié)點(按密度降序)的距離，如果它們之間的距離大于γ，則產(chǎn)生一個新的聚類中心；否則將兩個類進行合并，產(chǎn)生新的聚類中心，并重新計算各類間的距離，直到類間距離和聚類數(shù)都不再變化。算法偽碼如下所示。

算法1 基于動態(tài)聚類的線路劃分。

輸入 游客的旅游歷史記錄H={Hu1,Hu2,…,Hum}，最小的時間窗口γ；

輸出 游客劃分結(jié)果S={Su1,Su2,…,Sum},聚類結(jié)果C={Cu1,Cu2,…,Cum}。

1) forui∈Udo

2) 計算小于時間窗γ的線路密度并按降序排序得到列表

5) do 計算已有聚類中心與D中其他節(jié)點的距離

6) if 距離大于γthen

7) 這個點作為一個新的聚類中心

8) else

9) do{兩個類進行合并形成新的聚類中心，計算新類與其他已有類間距離}

10) until(任何兩類類間距離大于γ)

11) end if

12) until (D為空)

13) 返回Sui和Cui

14) end for

15) 輸出S,C

2.2 基于LDA的概率主題分布生成

(1)

(2)

2.3 游客興趣漂移模型的建立

(3)

(4)

width—An example of Lijin hydrologic station of the Yellow River

3 旅游線路推薦

3.1 近鄰游客選擇

由于旅游數(shù)據(jù)高稀疏性的特點，游客間共同旅游線路非常少，圖6給出了隨著共同旅游線路的數(shù)目增加游客頻次變化的情況。從圖6中可以看出超過95%游客參加過的共同旅游線路少于3次，在一個月內(nèi)參加過相同線路的游客隨著共同線路數(shù)目的增加先增大后減小，幾乎所有游客的共同次數(shù)也不多于5，這一特點為游客相似性計算帶來了巨大挑戰(zhàn)。

從而計算游客ui與us的相似性如式(5)：

(5)

這樣按照用戶的特征向量計算用戶間的相似性，避免了直接用高稀疏性的旅游數(shù)據(jù)難以計算相似度的問題，解決了近鄰選擇困難的問題。

圖6 相同旅游線路的游客占比Fig. 6 Proportion of tourists with common routes

3.2 候選線路集合生成

(6)

(7)

其中Nui為3.1節(jié)得到的近鄰用戶集合。

3.3 旅游線路推薦

對于游客ui候選線路集合Sui中的每條候選線路利用LDA得到其概率主題分布PLl，利用式(8)計算候選線路Ll與游客ui的|Hui|+1階段的興趣偏好的相似度：

(8)

其中Ll∈Sui。通過相似度大小對候選線路進行排序，為游客ui推薦相似度較大的Top-k線路。

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

4.1 度量標(biāo)準(zhǔn)

在Top-k推薦中常用準(zhǔn)確率(Precision)、召回率(Recall)及有效地平衡了準(zhǔn)確率和召回率的F評分進行結(jié)果評價。在實驗過程中，將每個游客的前|Hui|-1次旅游記錄作為訓(xùn)練集，第|Hui|次旅游線路信息作為測試數(shù)據(jù)，線路推薦成功的數(shù)量非0即1，因此準(zhǔn)確率的值為0或1/k，召回率為0或1，它們不再適合作為評價分類質(zhì)量衡量標(biāo)準(zhǔn)，因此提出準(zhǔn)確覆蓋率作為評價指標(biāo)，計算如式(9)。

(9)

其中:|U|為游客總數(shù)目，ρui定義如式(10)。

(10)

4.2 實驗結(jié)果及分析

4.2.1 主題數(shù)K的影響

主題是LDA的潛在變量，基于LDA的推薦中，K往往是事先設(shè)定，而不是通過數(shù)據(jù)學(xué)習(xí)獲得。本文中將準(zhǔn)確覆蓋率作為評價標(biāo)準(zhǔn)來學(xué)習(xí)最佳的主題數(shù)K，并記錄了隨著K增加的運行時間，結(jié)果如圖7所示。從圖7可知，隨著K的增加準(zhǔn)確覆蓋率先增大后減小，因為K太小不能發(fā)揮LDA發(fā)現(xiàn)潛在興趣的能力，而K太大得到的概率主題分布又被平均化。而且由于K越大，得到概率主題分布的計算量越大，因此運行時間呈增長趨勢。最佳的K是效率和精度的平衡，選取50作為主題數(shù)目。

圖7 主題數(shù)K的影響Fig. 7 Influence of topic number K

4.2.2 近鄰數(shù)n的選取

在所有基于鄰近的方法中，近鄰數(shù)目都非常重要。將近鄰數(shù)從10變化到100來評估它對結(jié)果的影響，如圖8所示。由圖8可以看出，隨著近鄰數(shù)目的增加，準(zhǔn)確覆蓋率先增大后減小。這是因為游客共同旅游線路相對較少：如果近鄰數(shù)目太小，近鄰與目標(biāo)的相似度很高，由近鄰而得到的可選候選線路集合也就越??；而近鄰的數(shù)目太大時，近鄰間的相似度較差，候選線路集合與游客實際興趣相差較大。因此本文后面的實驗選取近鄰個數(shù)為40。

圖8 近鄰數(shù)目的影響Fig. 8 Influence of neighbor number

4.2.3 與其他方法對比

為了說明本文方法的效果和預(yù)測能力，將本文方法時序潛在狄利克雷分布(Temporal Latent Dirichlet Allocation， TLDA)與以下三種方法進行了對比：

1)基于用戶的協(xié)同過濾(User-based Collaborative Filtering, UCF)[19]，它作為基于近鄰的推薦算法的代表;

2)LDA[14]：基于LDA的用戶興趣建模方法及推薦方法;

3)基于項目的隨機游走(ItemRank)[20]:建立旅線路的關(guān)聯(lián)圖，通過隨機漫步得到線路的排序。

實驗中，LDA參數(shù)α=50/K，β=0.01,ItemRank的重啟動概率為0.15。圖9給出了不同算法的結(jié)果。從圖9可以看出，TLDA、LDA和ItemRank方法都優(yōu)于UCF，因為UCF僅利用共同旅游的線路尋找近鄰用戶，但是由于旅游數(shù)據(jù)的高稀疏性使得它很難找到相似度較高的近鄰用戶，影響了推薦精度。TLDA方法優(yōu)于LDA與ItemRank方法，LDA與ItemRank的性能較為接近，因為TLDA針對旅游數(shù)據(jù)的高稀疏性采用了動態(tài)聚類對線路進行聚類，緩解了數(shù)據(jù)稀疏，在用戶興趣建模階段考慮了用戶的潛在興趣及時序影響，更好地描述了用戶的動態(tài)偏好，在近鄰的選擇過程中根據(jù)旅游數(shù)據(jù)特征建立游客特征向量，并將其作為近鄰選擇衡量標(biāo)準(zhǔn)，既挖掘了用戶的潛在興趣偏好，建立了其漂移模型，又避免了近鄰游客選擇可信度不高的問題。而LDA方法雖然利用LDA挖掘了游客潛在興趣偏好，但是忽略了偏好隨時間的變化。ItemRank盡管增加了線路選擇的隨機性，但是在建立線路間的轉(zhuǎn)移關(guān)系時只利用了共同旅游線路，沒有考慮時間、價格、游客年齡等因素。

圖9 旅游線路推薦結(jié)果對比Fig. 9 Comparison of recommended results of tourist routes

5 結(jié)語

本文提出了基于動態(tài)聚類的旅游線路推薦算法。通過統(tǒng)計分析旅游數(shù)據(jù)的特性，說明了它不同于其他數(shù)據(jù)集的特點。利用動態(tài)聚類對游客的交互歷史采用變長窗口劃分成不同的階段，而且劃分個數(shù)不需事先指定，通過實驗說明其很好地適應(yīng)了數(shù)據(jù)特性，緩解了數(shù)據(jù)的高稀疏性。在每個階段利用LDA抽取用戶的潛在興趣主題并利用時間懲罰權(quán)值以建立游客興趣漂移模型,更好地挖掘了游客興趣的變化趨勢。利用游客的特征向量為游客尋找近鄰用戶，很好地解決了用數(shù)據(jù)本身計算相似度困難的問題。通過在實際旅游數(shù)據(jù)上的實驗表明，本文方法得到了較好的推薦精度。但是本文在用戶興趣建模的過程中只考慮了興趣隨時間的變化，沒有考慮游客年齡、線路價格等其他因素，因此下一步將更加充分地挖掘數(shù)據(jù)特點，更準(zhǔn)確地對游客建模。此外，在游客特征向量建立過程中可進一步挖掘游客間隱式社交關(guān)系和線路價格-時間等關(guān)系來更好地描述其近鄰關(guān)系。

References)

[1] DEVASANTHIVA C, VIGNESHWARI S, VIVERK J. An enhanced tourism recommendation system with relevancy feedback mechanism and ontological specifications [C]// Proceedings of the 2016 International Conference on Soft Computing Systems, AISC 398. New Delhi: Springer-Verlag, 2016: 281-289.

[2] AL-HASSAN M, LU H, LU J. A semantic enhanced hybrid recommendation approach: a case study of e-government tourism service recommendation system [J]. Decision Support Systems, 2015, 72: 97-109.

[3] XUE A Y, ZHANG R, ZHENG Y, et al. Destination prediction by sub-trajectory synthesis and privacy protection against such prediction [C]// ICDE 2013: Proceedings of the IEEE 2013 29th International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2013: 254-265.

[4] XUE A Y, QI J, XIE X, et al. Solving the data sparsity problem in destination prediction [J]. The VLDB Journal, 2015, 24(2): 219-243.

[5] ZHU L C, LI Z J, JIANG S X. LBSN-based personalized routes recommendation [J]. Applied Mechanics and Materials, 2014, 644-650: 3230-3234.

[6] 馬磊.基于智能解決方案的自助旅游系統(tǒng)[J].計算機系統(tǒng)應(yīng)用，2017,26(3)：57-62. (MA L. Independent travel system based on intelligent solution [J]. Computer Systems Applications, 2017, 26(3)： 57-62.)

[7] SU H, ZHENG K, HUAN J, et al. A crowd-based route recommendation system — CrowdPlanner [C]// Proceedings of 2014 IEEE 30th International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2014: 1178-1181.

[8] LIU H-L, LI J-H, PENG J. A novel recommendation system for the personalized smart tourism route: design and implementation [C]// Proceedings of the 2015 IEEE 14th International Conference on Cognitive Informatics and Cognitive Computing. Washington, DC: IEEE Computer Society, 2015: 291-296.

[9] SHEN J, DENG C, GAO X. Attraction recommendation: towards personalized tourism via collective intelligence [J]. Neurocomputing, 2016, 173: 789-798.

[10] HASUIKE T, KATAGIRI H, TSUBAKI H, et al. A route recommendation system for sightseeing with network optimization and conditional probability [C]// Proceedings of 2015 IEEE International Conference on Systems, Man, and Cybernetics. Piscataway, NJ: IEEE, 2015: 2672-2677.

[11] 孫煥良,崔晨,劉俊嶺.基于動態(tài)轉(zhuǎn)移圖的時間敏感的旅游路線推薦[J]. 鄭州大學(xué)學(xué)報(理學(xué)版),2017,49(1):50-57. (SUN H L, CUI C, LIU J L. Time-sensitive travel route recommendation method based on dynamic transfer graph [J]. Journal of Zhengzhou University (Nature Science Edition), 2017, 49(1): 50-57.)

[12] SHE J, TONG Y, CHEN L. Utility-aware event-participant planning [C]// SIGMOD ’15: Proceedings of the 36th ACM International Conference on Management of Data. New York: ACM, 2015: 1629-1643.

[13] 陸國鋒,黃曉燕,呂紹和，等.基于互聯(lián)網(wǎng)信息的多約束多目標(biāo)旅游線路推薦[J].計算機工程與科學(xué),2016,38(1):163-170. (LU G F, HUANG X Y, LYU S H, et al. Multi-constraint and multi-objective trip recommendation based on Internet information [J]. Computer Engineering & Science, 2016, 38(1): 163-170.)

[14] HE Z, WU Z, ZHOU B, et al. Tourist routs recommendation based on latent Dirichlet allocation model [C]// Proceedings of 2015 12th Web Information System and Application Conference. Washington, DC: IEEE Computer Society, 2015: 201-206.

[15] YU J, ZHU T. Combining long- term and short-term user interest for personalized hashtag recommendation [J]. Frontiers of Computer Science, 2015, 9(4): 608-622.

[16] XIANG L, YUAN Q, ZHAO S, et al. Temporal recommendation on graphs via long- and short-term preference fusion [C]// KDD ’10: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2010: 723-732.

[17] HONG W, LI L, LI T. Product recommendation with temporal dynamics [J]. Expert Systems with Applications, 2012, 39(16): 12398-12406.

[18] RICARDO D, FONSECA M J. Improving music recommendation in session-based collaborative filtering by using temporal context [C]// ICTAI ’13: Proceeding of IEEE 25th International on Tools with Artificial Intelligence. Washington, DC: IEEE Computer Society, 2013: 783-788.

[19] RESNICK P, IACOVOU N, SUCHAK M, et al. GroupLens: an open architecture for collaborative filtering of netnews [C]// CSCW ’94: Proceedings of the 1994 ACM Conference on Computer Supported Cooperative Work. New York, ACM, 1994: 175-186.

[20] GORI M, PUCCI A. ItemRank: a random-walk based scoring algorithm for recommender engines [C]// IJCAI ’07: Proceedings of the 20th International Joint Conference on Artifical Intelligence. San Francisco, CA: Morgan Kaufmann Publishers Inc., 2007: 2766-2771.

This work is partially supported by the National Natural Science Foundation of China (U1533104), the Natural Science Foundation of Hebei Province (E2016202341), the Natural Science Foundation of Tianjin (14JCZDJC32500), the Fundamental Research Funds for the Central Universities (ZXH2012P009).

XIAOChunjing, born in 1978, Ph. D. candidate, lecturer. Her research interests include recommendation system, data mining.

XIAKewen, born in 1964, Ph. D., professor. His research interests include intelligent information processing, data mining.

QIAOYongwei, born in 1976, M. S., lecturer. His research interests include machine learning, intelligent information processing.

ZHANGYuxiang, born in 1975, Ph. D., associate professor. His research interests include machine learning, data mining, artificial intelligence.

Tourismrouterecommendationbasedondynamicclustering

XIAO Chunjing1,2, XIA Kewen1*, QIAO Yongwei3, ZHANG Yuxiang2

(1.SchoolofElectronicsandInformationEngineering,HebeiUniversityofTechnology,Tianjin300300,China；2.SchoolofComputerScienceandTechnology,CivilAviationUniversityofChina,Tianjin300300,China；3.EngineeringandTechnicalTrainingCenter,CivilAviationUniversityofChina,Tianjin300300,China)

In session-based Collaborative Filtering (CF), a user interaction history is divided into sessions using fixed time window and user preference is expressed by sequences of them.But in tourism data, there is no interaction in some sessions and it is difficult to select neighbors because of high sparsity. To alleviate data sparsity and better use the characteristics of the tourism data, a new tourism route recommendation method based on dynamic clustering was proposed. Firstly, the different characteristics of tourism data and other standard data were analyzed. Secondly, a user interaction history was divided into sessions by variable time window using dynamic clustering and user preference model was built by combining probabilistic topic distribution obtained by Latent Dirichlet Allocation (LDA) from each session and time penalty weights. Then, the set of neighbors and candidate routes were obtained through the feature vector of users, which reflected the characteristics of tourist age, route season and price. Finally, routes were recommended according to the relevance of probabilistic topic distribution between candidate routes and tourists. It not only alleviates data sparsity by using variable time window, but also generates the optimal number of time windows which is automatically obtained from data. User feature vector was used instead of similarity of tourism data to select neighbors, so as to the avoid the computational difficulty caused by data sparsity. The experimental results on real tourism data indicate that the proposed method not only adapts to the characteristics of tourism data, but also improves the recommendation accuracy.

dynamic clustering; Latent Dirichlet Allocation (LDA); preference model; time penalty; feature vector

TP391; TP181

A

2017- 02- 08;

2017- 04- 10。

國家自然科學(xué)基金資助項目(U1533104)；河北省自然科學(xué)基金資助項目(E2016202341);天津市自然科學(xué)基金資助項目(14JCZDJC32500);中央高校基本科研業(yè)務(wù)費資助項目(ZXH2012P009)。

肖春景(1978—)，女，河北唐山人，講師，博士研究生，主要研究方向：推薦系統(tǒng)、數(shù)據(jù)挖掘； 夏克文(1965—)，男，湖南武岡人，教授，博士，主要研究方向：智能信息處理、數(shù)據(jù)挖掘； 喬永衛(wèi)(1976—)，男，山西祁縣人，講師，碩士，主要研究方向：機器學(xué)習(xí)、智能信息處理；張宇翔(1975—)，男，山西大同人，副教授，博士，主要研究方向：機器學(xué)習(xí)、數(shù)據(jù)挖掘、人工智能。

1001- 9081(2017)08- 2395- 06

10.11772/j.issn.1001- 9081.2017.08.2395