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

孫煥良， 崔 晨， 劉俊嶺

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

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

孫煥良， 崔 晨， 劉俊嶺

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

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

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

0 引言

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

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

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

1 相關(guān)工作

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

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

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

2 問(wèn)題定義

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

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

(1)

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

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

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

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

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

定義4 景點(diǎn)流行度序列.給定景點(diǎn)v，景點(diǎn)流行度序列定義為

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

(2)

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

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

定義7 用戶(hù)的旅游路線(xiàn)查詢(xún). 旅游路線(xiàn)查詢(xún)表示為Q=〈N,T,PV(u)〉,N代表用戶(hù)設(shè)定的訪(fǎng)問(wèn)景點(diǎn)的個(gè)數(shù)，T為用戶(hù)出行的時(shí)間.

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

(3)

用戶(hù)收益代表用戶(hù)u對(duì)路線(xiàn)的滿(mǎn)意度,i表示路線(xiàn)中的第i個(gè)景點(diǎn).

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

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

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

3.1 構(gòu)建模型

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

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

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

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

3.2 景點(diǎn)模式的處理

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

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

圖5 初始流行序列

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

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

算法1 定位異常點(diǎn)

Input:所有景點(diǎn)的流行度序列集合Sn；景點(diǎn)集合V；

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

1) For V中的景點(diǎn)viDo

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

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

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

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

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

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

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

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

算法2 異常點(diǎn)的處理

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

Output:處理后的景點(diǎn)流行度的序列集合Sn；

1) For V中的景點(diǎn)viDo //遍歷所有景點(diǎn)

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

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

4) clusternum = cluster[j]

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

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

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

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

9) Else continue.

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

圖6 異常處理的流行序列

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

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

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

圖7 處理后的流行序列

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

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

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

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

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

2) For景點(diǎn)模式P中的景點(diǎn)模式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景點(diǎn)模式集合

8) For景點(diǎn)模式P中的景點(diǎn)模式PiDo

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

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

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

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

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

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

Output:對(duì)象R，存儲(chǔ)最大收益路線(xiàn)R.road以及R.profit用戶(hù)最大收益值；

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

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

5) For景點(diǎn)集合V中所有景點(diǎn)viDo

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

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

4 實(shí)驗(yàn)評(píng)價(jià)

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

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

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

4.2 推薦路線(xiàn)的評(píng)分分析與對(duì)比

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

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

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

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

圖8 訪(fǎng)問(wèn)地點(diǎn)數(shù)目N對(duì)profit的影響

圖9 出行日期對(duì)profit的影響

圖9b是在相同用戶(hù)訪(fǎng)問(wèn)景點(diǎn)個(gè)數(shù)為4的條件下，在與圖9a同樣的4個(gè)出行時(shí)間，采用4種算法進(jìn)行用戶(hù)收益的比較.與圖9a類(lèi)似，TRDG的用戶(hù)收益比其他3種路線(xiàn)推薦算法的收益至少高15%.

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

5 結(jié)論

本文提出了一種新的路線(xiàn)推薦方法：基于動(dòng)態(tài)轉(zhuǎn)移圖的時(shí)間敏感的旅游路線(xiàn)推薦.根據(jù)自然星期劃分法得到了景點(diǎn)模式，結(jié)合相似度采用層次聚類(lèi)方法進(jìn)行模式的聚合.實(shí)驗(yàn)對(duì)算法的有效性和用戶(hù)的收益進(jìn)行了分析比較，驗(yàn)證了該問(wèn)題的正確性和算法的優(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ù)的短時(shí)間體驗(yàn)式路線(xiàn)搜索[J]. 計(jì)算機(jī)學(xué)報(bào)，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

國(guó)家自然科學(xué)基金項(xiàng)目(61070024,61272180).

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

TP311

A

1671-6841(2017)01-0050-08

10.13705/j.issn.1671-6841.2016031