孫煥良， 崔 晨， 劉俊嶺

(沈陽建筑大學(xué) 信息與控制工程學(xué)院 遼寧 沈陽 110015)

基于動態(tài)轉(zhuǎn)移圖的時間敏感的旅游路線推薦方法

孫煥良， 崔 晨， 劉俊嶺

(沈陽建筑大學(xué) 信息與控制工程學(xué)院 遼寧 沈陽 110015)

提出了基于動態(tài)轉(zhuǎn)移圖的時間敏感的旅游路線推薦方法，構(gòu)建一種基于層次聚類的動態(tài)轉(zhuǎn)移圖的模式方法，設(shè)計了流行序列異常的去除方法，建立穩(wěn)定的模式規(guī)律.模式規(guī)律為用戶準(zhǔn)確地推薦適合其出行時間的最佳旅游線路.通過真實數(shù)據(jù)的實驗驗證，與現(xiàn)有工作相比，用戶的收益提高了10%以上，驗證了提出方法的有效性.

路線推薦； 時間敏感； 轉(zhuǎn)移圖模型； 簽到數(shù)據(jù)

0 引言

隨著互聯(lián)網(wǎng)和移動設(shè)備的快速發(fā)展，越來越多的用戶將旅行信息分享到在線社交平臺上，如Foursquare或Gowalla.它們收集了大量反映用戶位置與停留信息的數(shù)據(jù).利用歷史用戶的偏好和習(xí)慣進行旅游路線推薦，成為目前旅游路線推薦的研究熱點.基于簽到數(shù)據(jù)的路線推薦主要包括：基于地點流行度的路線推薦[1]、結(jié)合用戶偏好的路線搜索與推薦[2-4]、條件受限的路線推薦[4]等.

利用簽到數(shù)據(jù)進行路線推薦的做法是將用戶的簽到數(shù)據(jù)生成路線轉(zhuǎn)移圖.圖中結(jié)點表示景點，邊表示景點之間的轉(zhuǎn)移關(guān)系，景點的簽到次數(shù)表示景點流行度，邊上的權(quán)重表示邊的流行度.現(xiàn)有方法將所有的數(shù)據(jù)生成一個路線轉(zhuǎn)移圖，在圖中進行滿足條件的路線查詢[4-5].此類處理方法忽略了季節(jié)變化、節(jié)假日變化對景點流行度及轉(zhuǎn)移關(guān)系的影響.

現(xiàn)有的時間敏感路線推薦考慮各景點一天中最佳訪問時間，進行路線推薦[6-7]，而本文的研究是按全年范圍內(nèi)以星期為最小單位的時間敏感路線推薦.方法如圖1所示.由圖1可知，本文采用層次聚類算法進行概化處理對簽到數(shù)據(jù)中記錄少的景點進行聚合.根據(jù)景點流行度序列得出景點流行規(guī)律和轉(zhuǎn)移規(guī)律，對規(guī)律的學(xué)習(xí)和劃分以獲取穩(wěn)定合理的轉(zhuǎn)移圖模式集.結(jié)合轉(zhuǎn)移圖模式集的時間范圍屬性進行路線推薦實現(xiàn)了時間敏感的旅游路線推薦，有效解決了出行時間不同但路線唯一的路線推薦問題.

1 相關(guān)工作

依據(jù)所用的數(shù)據(jù)類型可以將路線的推薦分為3類：基于GPS軌跡數(shù)據(jù)的旅游路線推薦[2,8]、基于簽到記錄的旅游路線的推薦[4,8-10]和基于用戶分享的帶有地理位置信息的照片的旅游路線推薦[11-14].

文獻[15]利用景點集合、用戶訪問景點的先后次序集合以及照片數(shù)據(jù)，建立用戶的旅行轉(zhuǎn)移序列，進而進行路線推薦.文獻[16]從不確定軌跡中構(gòu)建多條有序軌跡并通過對指定地點集的挖掘得出最流行的路線.文獻[17]運用多樣化的排序算法將推薦的路線進行排序，目的是使推薦的路線包含更多的景點，使推薦的路線之間差異性更大.以上工作根據(jù)現(xiàn)有的數(shù)據(jù)挖掘流行度最高的路線對用戶進行推薦，未考慮路線是否符合用戶偏好這一重要因素.

文獻[18-20]雖然將用戶對于不同類別景點的偏好考慮在路線推薦過程中，但其中并沒有考慮景點流行度的變化，現(xiàn)實生活中景點的流行度是隨著時間的推移而變化的.本文利用簽到數(shù)據(jù)實時性和包含地點類別信息的特點，依據(jù)景點在一年中流行度的變化建立動態(tài)轉(zhuǎn)移圖模式集，為用戶推薦適合其出行時間的最佳路線.

2 問題定義

圖2左側(cè)是根據(jù)一年提取出的轉(zhuǎn)移圖的示例，右側(cè)為轉(zhuǎn)移圖中景點的類別和流行度的集合.

定義1 時間段T的景點模式. 給定時間段T，景點模式定義為P(T)=〈v1, v2, …, vi, …, vn〉.n代表結(jié)點總數(shù).景點流行度計算方法為

(1)

式中：argc∈cmax(vj.w:vj.c=vi.c)為取出vi所屬類別景點集中最大頻度的計算，此計算方法與文獻[12]提出的方法一致，優(yōu)勢在于更真實準(zhǔn)確地反饋出帶有類別的景點流行度.

定義2 時間段T的轉(zhuǎn)移圖模式.給定時間段T，轉(zhuǎn)移圖模式定義為GT=〈VT,ET〉.

定義3 時間敏感的轉(zhuǎn)移圖模式集. 時間敏感的轉(zhuǎn)移圖模式集定義為G=〈G1,G2,…,Gn〉，如圖3所示.圖3的模式集是將一年的數(shù)據(jù)通過相似度的計算和層次聚類的聚合生成的轉(zhuǎn)移圖模式集合.

圖2 轉(zhuǎn)移圖示例

(a)轉(zhuǎn)移圖模式P1(b)轉(zhuǎn)移圖模式P2

定義4 景點流行度序列.給定景點v，景點流行度序列定義為

定義5 景點相似性度量.給定時段T和時段T′，景點模式P(T)和景點模式P(T′)的相似度計算方法為

(2)

由于景點模式與詞頻向量相似，具有稀疏性，度量的要求為關(guān)注兩個模式相同的景點，以及相同景點出現(xiàn)的頻度，所以采用文本相似度中的余弦相似度為適宜.

本文采用社交網(wǎng)站Foursquare的位置分類方法對景點的類別進行描述，共分為8個類別，分別為：C={娛樂中心(c1),商場(c2),美食(c3),夜店(c4),旅行(c5),教育(c6),公園(c7),建筑(c8)}.

定義7 用戶的旅游路線查詢. 旅游路線查詢表示為Q=〈N,T,PV(u)〉,N代表用戶設(shè)定的訪問景點的個數(shù)，T為用戶出行的時間.

定義8 用戶收益. 給定用戶u、路線景點總數(shù)N和偏好集合，用戶收益定義為Profit(u).計算方法為

(3)

用戶收益代表用戶u對路線的滿意度,i表示路線中的第i個景點.

問題1 時間敏感的路線搜索.給定查詢Q=〈N,T,PV(u)〉，轉(zhuǎn)移圖的模式集G，用戶的偏好PV(u)，利用時間敏感的路線推薦方法推薦一條適合在時間T出行且收益最大的旅游路線R.

現(xiàn)設(shè)用戶的初始查詢是Q=〈3,T,PV(u)=〈0.3, 0.5, 0.2〉〉，在生成的轉(zhuǎn)移圖模式集中，T所在的模式為圖3中的模式P1.通過計算發(fā)現(xiàn)用戶的最大收益值中包含兩條路線，分別是(v1,v2,v6)和(v6,v5,v4)，但前者邊的流行度更高，所以模式P1的最佳路線RP1.road為(v1,v2,v6)，最佳路線的收益值RP1.value為0.54.

3 轉(zhuǎn)移圖模式構(gòu)建

3.1 構(gòu)建模型

模型構(gòu)建的流程如圖4所示，模型分為數(shù)據(jù)預(yù)處理、景點模式建立、轉(zhuǎn)移圖模式建立和路線的推薦4部分.本文首先將基于地理信息的對象活動的相關(guān)數(shù)據(jù)采用規(guī)范的概化處理，得到符合現(xiàn)實生活的數(shù)據(jù)信息，如步驟①所示，為數(shù)據(jù)的預(yù)處理部分.

步驟②根據(jù)處理后的數(shù)據(jù)依據(jù)景點的數(shù)目，采用等深分箱技術(shù)進行劃分，統(tǒng)計每箱中景點出現(xiàn)的頻度，根據(jù)現(xiàn)實生活中主觀認為時間以星期為單位進行劃分，構(gòu)建景點模式集合和景點流行度序列集合.由于每個星期都包含工作日和休息日，故排除了二者對于模式集生成的干擾.步驟③依據(jù)景點模式統(tǒng)計所有景點的流行度的變化情況，建立景點流行序列.步驟④將景點流行序列進行異常點的處理操作，得到穩(wěn)定、均化的流行序列，依據(jù)相似性檢驗及層次聚類算法得到最終的景點模式.其中去除異常是為了讓景點流行序列均勻平滑，相似性檢驗是為了去除相鄰模式之間相似性過大帶來的相似問題.步驟⑤由景點模式與其時間范圍的轉(zhuǎn)移關(guān)系得到轉(zhuǎn)移圖模式.最后，步驟⑥通過轉(zhuǎn)移圖模式進行路線的評分與推薦.

由于區(qū)域?qū)ο罅鲃拥碾S機性造成了景點流行度的異常，如何生成合理穩(wěn)定的序列、異常點的處理和模式之間相似度的計算，成為本文研究如何生成高精度的轉(zhuǎn)移圖模式的重點.

圖4 動態(tài)轉(zhuǎn)移圖的時間敏感推薦模型圖

3.2 景點模式的處理

景點模式根據(jù)自然星期劃分建立，但模式集中景點的流行度并不穩(wěn)定，規(guī)律性不強，這使景點模式的處理成為必然.本文首先定位異常點，其次主要采用景點流行度序列局部去除異常點和均值替代法對異常的流行點進行處理.結(jié)合文本相似度的層次聚類算法，對景點模式集中相似的兩個連續(xù)模式聚合，目的是使景點模式集中所有連續(xù)的景點模式之間互不相似.

景點模式集中包含所有景點各星期的流行度，所以景點流行序列的構(gòu)建和處理成為去除景點模式集中異常流行點的關(guān)鍵.未經(jīng)處理的流行度序列如圖5所示.

圖5 初始流行序列

由圖5可知，初始模式生成的景點流行序列大多是難以發(fā)現(xiàn)其中規(guī)律的，但可以隱約看出在春季和冬季是不流行的，序列大體保持在一年中最低水平.流行序列中的異常點影響著穩(wěn)定景點序列的生成，這使得去除異常點成為穩(wěn)定景點序列生成的關(guān)鍵.

3.2.1 定位異常點 本文景點流行序列中的異常點是指在穩(wěn)定的景點流行度區(qū)間夾雜著流行度變化過大的一個時間段，此處的流行度超出穩(wěn)定序列設(shè)定的范圍，由于它的存在導(dǎo)致了穩(wěn)定流行度區(qū)間出現(xiàn)了較大的波動，因此設(shè)定為異常點.本文提出一種依據(jù)流行度波動情況有效定位局部異常點的方法，如算法1所示.

算法1 定位異常點

Input:所有景點的流行度序列集合Sn；景點集合V；

Output:景點異常點標(biāo)記集合Result，景點穩(wěn)定聚簇集合Cluster；

1) For V中的景點viDo

2) For S(vi)的時間段TjDo

3) Find(vi, tj)//找到Si.max、Si.min中流行度的最大值max，最小值min

4) 計算最大值與最小值的差Si.len=max-min

6) For S(vi)的時間段TkDo

7) Result[i][k]=FindOutlier(j, flu(Si), Si, cluster[i]);//確定異常點位置

8) Cluster[i]=FindCluster(i, flu(Si), Si);//穩(wěn)定聚簇

9) Delete(Si. k)//刪除j的流行程度

3.2.2 異常點的處理 異常點的流行度經(jīng)過算法1的處理已被刪除，但異常點留下的空缺使得各景點的流行序列曲線出現(xiàn)斷裂之處，所以要對此進行處理.本文采用現(xiàn)有數(shù)據(jù)挖掘知識中數(shù)據(jù)清洗技術(shù)的均值替代法對空缺之處進行填補.如算法2所示，

算法2 異常點的處理

Input: Result為存儲異常點的鏈表；Cluster為存儲景點穩(wěn)定序列的鏈表；景點的流行度序列集合Sn；景點集合V；

Output:處理后的景點流行度的序列集合Sn；

1) For V中的景點viDo //遍歷所有景點

2) For Sn中Series(vi)的時間段TjDo

3) IF(Result[i][j] == 1) THEN //找尋異常標(biāo)記

4) clusternum = cluster[j]

5) For Sn中Series(vi)的時間段TkDo

6) IF(cluster[k] == clusternum&&Result[i][k]!=1) THEN

7) sum = sum+Si.k.w//計算相同聚簇里的流行度總和

8) Update(Si.k, avg(sum));//得到穩(wěn)定序列內(nèi)的流行程度的平均值,更新S

9) Else continue.

算法2的步驟1)～4)是對所有景點的流行序列進行異常點處理的操作.檢驗景點在當(dāng)前時間是否為異常點標(biāo)記，如果是,則將所屬穩(wěn)定聚簇記錄在clusternum中.步驟5)～9)首先是在該景點的所有時間點中發(fā)現(xiàn)與clusternum相同的穩(wěn)定聚簇的值，即屬于同一穩(wěn)定聚簇，其次對所有該聚簇的流行度進行求平均值的操作，求和及求平均值時都不考慮異常點的影響.用均值代替異常點，并更新景點流行度序列集合Sn.啟用異常處理之后的流動序列曲線與處理之前的對比如圖6所示.

圖6 異常處理的流行序列

圖6中的散點為異常點，反映異常點處理前后的對比.本文采用聚簇均值替代的方法，將景點的穩(wěn)定流行聚簇內(nèi)包含的時間段的流行度的值，用聚簇內(nèi)流行度的均值進行替換，使得每個聚簇都能成為絕對穩(wěn)定的聚簇，流行序列曲線成為階梯狀的變化，反映景點在各個時間段內(nèi)流行度的變化，最終的景點流行序列如圖7所示.

如圖7，景點的流行度是隨時間變化的序列，每條水平的線段都代表穩(wěn)定的流行聚簇.由于單周的流行程度不具有代表性，故穩(wěn)定流行序列的長度至少為2.

3.3 轉(zhuǎn)移圖模式的構(gòu)建

圖7 處理后的流行序列

構(gòu)建轉(zhuǎn)移圖模式的前提是相似的景點模式.由于異常點處理后的景點模式之間存在相似的可能，相似且相鄰的模式可能推薦相同或相似的路線，所以本文通過文本相似度的計算方法進行模式之間相似度的計算.文本相似度的計算方法如本文定義5所示.結(jié)合文本相似度采用層次聚類的方法將相似度矩陣中滿足聚合要求且相鄰的模式進行聚合，利用景點模式中景點的轉(zhuǎn)移關(guān)系建立轉(zhuǎn)移圖模式.具體的轉(zhuǎn)移圖生成原則會在4.1節(jié)的轉(zhuǎn)移圖生成過程中詳細說明.模式的生成如算法3所示.

算法3 轉(zhuǎn)移圖模式生成

Input: 根據(jù)Sn得到的景點模式P;

Output:轉(zhuǎn)移圖模式集G；

1) While(Sim Rt.max()≥thr) Do//相似度矩陣中相似度的最大值不小于閾值

2) For景點模式P中的景點模式PkDo

3) Sim Rt= Sim(Pk, P(k+1), k, k+1);//生成相似度矩陣，不相鄰的模式相似度為0

4) max= Sim Rt.max;//得到相似度矩陣的最大值

5) location= Sim Rt.location;//確定最大值位置

6) Cluster(location);

7) Update(P);//更新P景點模式集合

8) For景點模式P中的景點模式PiDo

9) Gi=creategraph(Pi);//每個景點模式生成轉(zhuǎn)移圖

算法3的步驟1)設(shè)定條件，景點模式中相似度矩陣的最大值超過閾值則聚合條件滿足，景點模式發(fā)生聚合.步驟2)～7)為提取景點模式，計算景點模式之間的相似度生成相似度矩陣，并依據(jù)層次聚類算法進行聚合.步驟8)～9)是利用聚合后的景點模式，依據(jù)轉(zhuǎn)移圖生成規(guī)則，分別建立轉(zhuǎn)移圖.

3.4 基于動態(tài)轉(zhuǎn)移圖的時間敏感的旅游路線推薦

基于動態(tài)轉(zhuǎn)移圖的時間敏感的旅游路線推薦方法是根據(jù)用戶給定的出行時間和預(yù)計訪問的景點數(shù)目，將最佳收益的路線為用戶推薦.具體過程如算法4所示.

算法4 基于動態(tài)轉(zhuǎn)移圖的時間敏感的旅游路線推薦方法

Input:出行用戶的偏好PV，用戶預(yù)計的出行時間t，用戶預(yù)計訪問景點總數(shù)N；轉(zhuǎn)移圖模式集合G，景點集合V；

Output:對象R，存儲最大收益路線R.road以及R.profit用戶最大收益值；

1) 初始化棧W，路線存儲R，路線數(shù)組A[N]，收益存儲Profit，存儲鄰接表list

4) list.i.add(j); //建立鄰接表

5) For景點集合V中所有景點viDo

6) A[N]=TRDG(vi,N, t, list); //得到vi為起點的最佳路線

7) W.push(A)

8) For(k = 0;k

9) Profit = Profit + A[k].c*p(ui,c)

10) IF(Profit>R.profit)

11) R.profit =Profit

12) R.road=A

13) ELSE W.pop(A)

算法4描述了基于動態(tài)轉(zhuǎn)移圖的時間敏感的旅游路線推薦算法的流程.步驟1)初始化路線搜索.步驟2)～4)建立鄰接表，提升路線查詢速度.步驟5)～13)根據(jù)鄰接表進行基于動態(tài)轉(zhuǎn)移圖的時間敏感的旅游路線推薦算法的路線搜索，將起始結(jié)點vi的最佳路線分別入棧，計算路線的收益，并與當(dāng)前最大收益路線進行比較，如果比當(dāng)前的收益大，便將R進行替換，否則將路線出棧，繼續(xù)執(zhí)行基于動態(tài)轉(zhuǎn)移圖的時間敏感的旅游路線推薦算法，直到鄰接表中的所有結(jié)點都已查詢完畢.基于動態(tài)轉(zhuǎn)移圖的時間敏感的旅游路線推薦方法是按照模式的規(guī)模搜索最佳路線，并非全年數(shù)據(jù)，因此效率大大提高.

4 實驗評價

本文提出并實現(xiàn)基于動態(tài)轉(zhuǎn)移圖的時間敏感的旅游路線推薦方法(time-sensitive route recommendation based on dynamic transfer graph,TRDG)的算法，并與以下3種算法進行了比較，分別是基于月份的時間敏感的路線推薦(month time-sensitive route recommendation, MTR)、基于季度的時間敏感的路線推薦(season time-sensitive route recommendation, STR)和文獻[18]的原始的結(jié)合用戶偏好的路線推薦(initial preference route recommendation, IPR).

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

實驗選取Gowalla社交網(wǎng)站的數(shù)據(jù)集中美國舊金山市北部從2009年11月到2010年10月的簽到記錄.通過概化處理和統(tǒng)計去除一年中景點平均一個星期出現(xiàn)次數(shù)小于5次的景點和相應(yīng)記錄.根據(jù)景點模式包含的景點和所屬時段，如果同一用戶的連續(xù)簽到記錄的時間間隔是大于1小時且小于6小時，則兩點之間生成一條有向邊，并對邊出現(xiàn)的頻度進行統(tǒng)計生成轉(zhuǎn)移圖.

4.2 推薦路線的評分分析與對比

本節(jié)將從訪問地點數(shù)目N的變化收益效果和出行時間不同的收益效果對TRDG算法、MTR、STR和IPR進行實驗對比，驗證TRDG算法的有效性和優(yōu)越性.

4.2.1 訪問地點數(shù)目變化的收益效果對比 圖8(a)是在用戶偏好相同，3月1日出行的條件下，profit隨著訪問地點數(shù)目N的變化.每種算法的profit都隨著訪問地點數(shù)目N的增加而增加，表明地點數(shù)目越大，用戶的收益越高.其中，STR和IPR推薦效果較差，MTR稍好，TRDG的收益比其他3種算法高15%左右.圖8b是profit在用戶偏好相同，9月1日出行的條件下，隨著訪問地點數(shù)目N的變化.與圖8a類似，MTR和STR推薦效果較差， IPR稍好，TRDG的收益比其他3種算法高25%左右.

綜上所述，在用戶偏好確定出行時間相同的情況下，驗證訪問地點數(shù)目的變化時，在用戶收益方面，TRDG比其他3種方法有著很大的優(yōu)勢.

4.2.2 出行時間不同的收益效果對比 圖9a是在相同用戶訪問景點個數(shù)為3的條件下，在3月1日、6月1日、9月1日和12月1日，4個不同月份，不同季節(jié)的出行時間，采用4種算法進行用戶收益的比較.其中，STR和IPR推薦效果依然較差，比MTR收益高10%.

圖8 訪問地點數(shù)目N對profit的影響

圖9 出行日期對profit的影響

圖9b是在相同用戶訪問景點個數(shù)為4的條件下，在與圖9a同樣的4個出行時間，采用4種算法進行用戶收益的比較.與圖9a類似，TRDG的用戶收益比其他3種路線推薦算法的收益至少高15%.

綜上所述，在用戶偏好確定、訪問地點數(shù)目相同的情況下，驗證訪問出行時間的變化，在用戶收益方面，TRDG算法比其他3種方法有很大優(yōu)勢.

5 結(jié)論

本文提出了一種新的路線推薦方法：基于動態(tài)轉(zhuǎn)移圖的時間敏感的旅游路線推薦.根據(jù)自然星期劃分法得到了景點模式，結(jié)合相似度采用層次聚類方法進行模式的聚合.實驗對算法的有效性和用戶的收益進行了分析比較，驗證了該問題的正確性和算法的優(yōu)越性.

[1] BAO J, ZHENG Y, WILKIE D, et al. Recommendations in location-based social networks: a survey[J]. Geoinformatica, 2015, 19(3): 525-565.

[2] BAO J, ZHENG Y, MOKBEL M F. Location-based and preference-aware recommendation using sparse geo-social networking data[C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems. Redondo Beach, 2012: 199-208.

[3] FUNKE S, STORANDT S. Personalized route planning in road networks[C]//Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. Seattle, 2015: 45.

[4] LU E H C, CHEN C Y, TSENG V S. Personalized trip recommendation with multiple constraints by mining user check-in behaviors[C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems. Redondo Beach, 2012: 209-218.

[5] WANG S, LIN W, YANG Y, et al. Efficient route planning on public transportation networks: a labelling approach[C]//Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. Melbourne, 2015: 967-982.

[6] HSIEH H P, LI C T, LIN S D. Exploiting large-scale check-in data to recommend time-sensitive routes[C]//Proceedings of the ACM SIGKDD International Workshop on Urban Computing. Beijing, 2012: 55-62.

[7] YUAN Q, CONG G, MA Z, et al. Time-aware point-of-interest recommendation[C]//Proceedings of the 36th international ACM SIGIR Conference on Research and Development in Information Retrieval. Dublin, 2013: 363-372.

[8] ZHENG Y, XIE X. Learning travel recommendations from user-generated GPS traces[J]. ACM transactions on intelligent systems and technology, 2011, 2(1): 389-396.

[9] LIAN D, XIE X. Learning location naming from user check-in histories[C]//Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Chicago, 2011: 112-121.

[10]HSIEH H P, LI C T. Composing traveling paths from location-based services[C]//Proceedings of the 6th International AAAI Conference on Weblogs and Social Media.Dublin, 2012.

[11]LIM K H. Recommending tours and places-of-interest based on user interests from geo-tagged photos[C]//Proceedings of the 2015 ACM SIGMOD on PhD Symposium. Melbourne, 2015: 33-38.

[12]MAJID A, CHEN L, MIRZA H T, et al. Mining context-aware significant travel sequences from geo-tagged social media[C]//Proceedings of the AAAI. Toronto, 2012: 2443-2444.

[13]KURASHIMA T, IWATA T, IRIE G, et al. Travel route recommendation using geotagged photos[J]. Knowledge and information systems, 2013, 37(1): 37-60.

[14]CAO X, CHEN L, CONG G, et al. Keyword-aware optimal route search[J]. Proceedings of the VLDB endowment, 2012, 5(11): 1136-1147.

[15]MASTHOFF J. Group recommender systems: combining individual models[M].New York:Springer,2011: 677-702.

[16]WEI L Y, ZHENG Y, PENG W C. Constructing popular routes from uncertain trajectories[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Beijing, 2012: 195-203.

[17]YIN Z, CAO L, HAN J, et al. Diversified trajectory pattern ranking in geo-tagged social media[C]//IEEE Intermational Conference on Data Mining. Vancouver, 2011: 980-991.

[18]DAI J, YANG B, GUO C, et al. Personalized route recommendation using big trajectory data[C]//Data Engineering (ICDE), IEEE International Conference on Data Engineering. Atlantic, 2015: 543-554.

[19]GARCIA I, PAJARES S, SEBASTIA L, et al. Preference elicitation techniques for group recommender systems[J]. Information sciences, 2012, 189(7): 155-175.

[20]宋曉宇,許鴻斐,孫煥良,等. 基于簽到數(shù)據(jù)的短時間體驗式路線搜索[J]. 計算機學(xué)報，2013，36(8)：1693-1703.

(責(zé)任編輯：王浩毅)

Time-sensitive Travel Route Recommendation Method Based on Dynamic Transfer Graph

SUN Huanliang, CUI Chen, LIU Junling

(SchoolofInformationandControlEngineering,ShenyangJianzhuUniversity,Shenyang110015,China)

The time-sensitive travel route recommendation methods were put forward based on dynamic transfer graph. A pattern-building method of dynamic transfer graphs was proposed based on hierarchy clustering and designs methods to remove outliers with popularity sequence to construct stable pattern rules. The use of pattern rules could accurately recommend the best travel routes that were most suitable for travel time for the user. With the verification of the real data, the profit of users increased by more than 10% compared with the existing work, which indicated the effectiveness of this method.

route recommendation; time-sensitive; transfer graph pattern; check-in data

2016-09-28

國家自然科學(xué)基金項目(61070024,61272180).

孫煥良(1969—)，男，黑龍江望奎人，教授，主要從事空間數(shù)據(jù)庫和數(shù)據(jù)挖掘研究,E-mail:sunhl@sjzu.edu.cn.

TP311

A

1671-6841(2017)01-0050-08

10.13705/j.issn.1671-6841.2016031