基于稀疏軌跡聚類的旅游目的地位置預測方法

劉 涵

(亳州職業(yè)技術學院 管理學系，安徽 亳州 236800)

經(jīng)濟全球化背景下，國家經(jīng)濟、社會發(fā)展以及人們的生活水平都在逐步提升，越來越多的人在工作之余更加注重精神享受。因此，近年來國內(nèi)外旅游業(yè)迅速發(fā)展。在社會經(jīng)濟、交通、科技信息及環(huán)保理念的飛速發(fā)展下，可供選擇的旅游景點越來越多，越來越多的人選擇自駕游或與好友結伴旅游。為了更好地發(fā)展旅游經(jīng)濟，提升偏遠地區(qū)經(jīng)濟水平，相關學者對旅游目的地位置預測進行了研究。溫惠英等提出，在生成對抗網(wǎng)絡中構建一個推薦模型，來預測某一階段人們偏好的旅游目的地[1]；張志遠等提出，面對移動對象的不確定性軌跡，在傳統(tǒng)預測模型的基礎上，引用社會特征分析行人注意力，構建行人軌跡預測模型[2]。通過對這兩個預測模型進行使用測試，發(fā)現(xiàn)傳統(tǒng)預測模型由于對旅游線路的聚類性能不佳，預測結果準確率不理想。

為解決上述問題，該文提出基于稀疏軌跡聚類的旅游目的地位置預測方法。當前，人們選擇的出行時段、出行方式以及移動軌跡向著多樣化發(fā)展，這些軌跡稱為稀疏軌跡。稀疏軌跡聚類預測方法能夠通過識別時空軌跡重復數(shù)據(jù)實現(xiàn)重復數(shù)據(jù)濾除，通過稀疏軌跡聚類可補全旅游目的地的預測軌跡，在迭代網(wǎng)絡及預測軌跡的基礎上實現(xiàn)旅游目的地位置預測，為旅游業(yè)的發(fā)展提供幫助。

一、旅游目的地位置預測方法

采集旅游者的空間走動軌跡時，需要剔除重復性數(shù)據(jù)，計算特征點到其余各點距離，將得到的特征點和不屬于重復數(shù)據(jù)集合的點重新排序，實現(xiàn)對重復數(shù)據(jù)的識別與消除。對軌跡數(shù)據(jù)聚簇分類，并利用稀疏軌跡聚類算法，實現(xiàn)對稀疏數(shù)據(jù)的補全，采用多種熵估計方法，通過迭代網(wǎng)格對上述路徑進行數(shù)據(jù)集合無用數(shù)據(jù)消除，實現(xiàn)基于稀疏軌跡聚類的旅游目的地位置預測。

(一)識別與消除時空軌跡重復數(shù)據(jù)

旅游者作為不斷變化的移動對象，在采集他們的空間運動軌跡時會出現(xiàn)重復性數(shù)據(jù)。如旅游對象A去D1地點后，直接向D2點移動，然后再去D3和D4等地。但旅游對象由于自身喜好或其他問題，可能會返回到前幾個已經(jīng)去過的位置。因此，采集到的空間軌跡會存在重復，需要剔除這些重復性數(shù)據(jù)[3]。

將帶有時間標識的空間位置序列定義為旅游對象的時空軌跡，P(sj)={p1(sj),p2(sj)，…，pn(sj)}為軌跡采樣點，其中pi(sj)∈pn(sj)表示其中的任意一個采樣點；n表示采樣點數(shù)量；sj代表移動對象標識，存在S={s1,s2,…,sJ}，其中sj∈S表示移動對象集合中的任意一個；j∈J表示移動對象數(shù)量。利用經(jīng)緯度、時間戳和移動對象標識來描述移動對象采樣點，即存在：

pi(sj)=〈(xi,yi),ti,sj〉

(1)

公式中(xi,yi)表示軌跡點位置分量；ti表示時間戳[4]。將具有相同位置信息和相同時間信息的關于sj的軌跡點定義為重復數(shù)據(jù)，即該數(shù)據(jù)時間戳與經(jīng)緯坐標完全一致，將此類數(shù)據(jù)合并處理。而在某一連續(xù)時間內(nèi)，若關于sj存在多個軌跡點，且這些點若集中于特定的小范圍區(qū)域內(nèi)，則認為這些數(shù)據(jù)為隱含重復數(shù)據(jù)。當某一類移動對象sj的軌跡點集合為

P(sj)={pa(sj),pa+1(sj),…,pb(sj)}

(2)

公式中i∈[a,b]。若存在dis(pa,pi)≤2β,dis(pa,pb+1)>2β且tb-ta<βt時，則該集合為重復點集，則該集合P′(sj)∈P(sj)。其中：dis(*)表示距離函數(shù)，β表示軌跡方向參數(shù)。重復點集篩選如圖1所示。

圖1 重復點集合篩選示意

在重復點集合P′(sj)中，選擇其中一個可以作為代表的軌跡點，即特征點，該點的基本信息獲取結果為

zk(sj)=〈(xk,yk),ta,tb,sj〉

(3)

公式中ta表示重復點集合的初始時間，tb表示結束時間，(xk,tk)表示特征點的坐標。特征點提取如圖2所示。

圖2 特征提取示意

通過公式(3)可得到特征點到其余各點的距離，將得到的特征點及不屬于重復數(shù)據(jù)集合的點重新排序，得到關于sj的新軌跡點序列，實現(xiàn)對重復性數(shù)據(jù)的識別與消除[5]。

(二)基于稀疏軌跡聚類補全稀疏數(shù)據(jù)

由于移動對象的移動數(shù)據(jù)具有稀疏性特征，在消除重復性數(shù)據(jù)后會存在數(shù)據(jù)缺失問題，進而影響最終的預測結果。因此，基于稀疏軌跡聚類算法可補全稀疏數(shù)據(jù)，提升數(shù)據(jù)質量。不同的旅游者在游玩的過程中會在一個固定的城區(qū)內(nèi)形成歷史軌跡點，而這些軌跡會受到移動對象性格、喜好以及偏愛的影響，具有一定的波動性。因此，基于上述假設聚類軌跡數(shù)據(jù)。稀疏軌跡聚類算法對稀疏數(shù)據(jù)的補全如圖3所示[6]。

圖3 稀疏軌跡補全示意

將聚簇內(nèi)元素的眾數(shù)，作為聚簇結果的代表值，進行初始化、距離計算樣本聚簇和結果評估。在上一節(jié)處理完畢的數(shù)據(jù)集合中，隨機選擇個軌跡聚類中心，分別為c1,c2,c3,…,cn，其中ci表示向量，其長度為L，則ci=[p1,p2,…,pi,…,pl]，代表若干個移動軌跡。根據(jù)圖3中的標注可知，軌跡集合有G={G1,G2,…,Gi,…,Gn}，該集合中的軌跡Gi={p1,p2,…,pi,…,Pl}。利用稀疏軌跡聚類算法計算中心軌跡與樣本軌跡之間的距離，公式為

Dist〈Gi,Gj〉=max{f(Gi,Gj),f(Gj,Gi)}

(4)

(5)

將樣本Gj劃分到距離最小的聚簇中，令同一組的軌跡距離盡可能縮小，不同組的軌跡盡可能擴大。樣本劃分完畢后，計算各組軌跡間的均方差和，利用下列公式評價聚類效果：

(6)

根據(jù)上述4個步驟實現(xiàn)對軌跡數(shù)據(jù)的聚簇分類，并利用稀疏軌跡聚類算法實現(xiàn)對稀疏數(shù)據(jù)的補全[7]。

(三)多種熵估計預測旅游目的地位置

在前文的基礎上，通過稀疏數(shù)據(jù)的補全獲取了旅游目的地預測位置的數(shù)據(jù)集合，此時集合中存在大量的冗余路徑，不能作為最終的旅游目的地位置預測軌跡。為此，采用多種熵估計方法，通過迭代網(wǎng)格對上述路徑進行數(shù)據(jù)集合，消除無用數(shù)據(jù)，得到準確的旅游目的地位置預測數(shù)據(jù)集合，有效解決旅游線路重復及旅游目的地位置預測效果不理想等問題。具體應用過程如下：

采用多種熵估計方法，預測旅游目的地位置。首先生成一個基于迭代網(wǎng)格和時間的軌跡序列，平均劃分每一天，并保證其時間段不重疊，即得到的時間段集合為T={t1,t2,…,tn}，其中與時間段信息相關的原始軌跡為：

(7)

公式中，tra表示軌跡，tu表示時間節(jié)點，lonu表示經(jīng)度值，latu表示緯度值，u∈n，表示個數(shù)。將tra中的所有節(jié)點映射到網(wǎng)格點和時間段上，生成帶有時間標簽的軌跡序列：

(8)

公式中，eu表示tu時段的軌跡在網(wǎng)格中的節(jié)點位置[8]。采用多種軌跡熵值預測旅游目的地位置，引入位置熵表示游客對某一旅游地點的喜愛程度。該值的計算公式為：

(9)

公式中，Nm,s表示旅游對象s訪問旅游位置m時的次數(shù)，Nm表示所有用戶訪問旅游位置m時的次數(shù)。熵值越低說明可預測性就越強，反之則越低。時間熵可以描述某一時間段內(nèi)游客在某區(qū)域內(nèi)的活躍程度，則時間的熵值為：

(10)

公式中，Mt,s表示旅游對象s在t時間段內(nèi)訪問的旅游位置總數(shù)量，Mt表示所有用戶在同一時間段內(nèi)訪問的旅游位置總數(shù)量。生成軌跡序列后，利用一階馬爾可夫鏈量化軌跡規(guī)律[9-10]。馬爾可夫鏈狀態(tài)與每個網(wǎng)格中的軌跡對應，而軌跡從一個網(wǎng)格移動到另一個網(wǎng)格時，則為馬爾可夫鏈的狀態(tài)轉換。根據(jù)已經(jīng)給定的所有軌跡tra構造轉移概率矩陣Z，生成馬爾可夫鏈F(tra)，以此計算狀態(tài)之間的轉移熵，進而分析軌跡規(guī)律。用軌跡轉移熵矩陣H表示所有狀態(tài)之間的隨機性：

Hi,j=H(Zi,j)=-∑i,jλZi,jlogZi,j

(11)

公式中，λ表示軌跡馬爾可夫鏈F(tra)的平穩(wěn)分布。已知轉移概率矩陣Z，則用軌跡空間中網(wǎng)格i與j之間的移動數(shù)據(jù)除以所有網(wǎng)格之間的移動數(shù)目，得到網(wǎng)格i與j之間的轉移概率：

(12)

公式中，Q表示網(wǎng)格，Len(tra)表示對馬爾可夫鏈的量化結果。根據(jù)上述內(nèi)容，通過多種熵估計結果，預測旅游目的地位置。二階馬爾可夫生成的用戶軌跡預測模型見表1。

表1 用戶軌跡預測模型

利用表1所示的預測模型預測旅游目的地位置軌跡。預測結果為

(13)

公式中qi、qn、tj分別為給出的網(wǎng)格和時間段集合中的任意數(shù)值。通過以上過程實現(xiàn)基于稀疏軌跡聚類的旅游目的地位置預測。

二、實驗研究

通過對比實驗比較基于稀疏軌跡聚類的位置預測方法與傳統(tǒng)位置預測方法之間的差異性。

(一)算法性能測試

模擬設置若干個旅游目的地位置和旅游軌跡，通過實驗對比方法和稀疏軌跡聚類算法，以各個時段的劃分作為聚類標準，計算各個時段內(nèi)的軌跡之間的距離平方差，圖4為不同聚類值下求得的最小SSE值。

圖4 不同K值下SSE值變化曲線

根據(jù)圖4顯示的曲線變化可知，當初始選擇聚簇分組數(shù)為8時，SSE的取值結果最小，對應的聚類效果也最好。因此，該算法可將聚簇分組數(shù)設置為8，補全聚類前后的軌跡數(shù)量、軌跡點個數(shù)和單軌跡平均軌跡點個數(shù)的變化情況(圖5)。

圖5 聚類前后軌跡數(shù)據(jù)質量對比

從圖5可以看出，通過重復性數(shù)據(jù)識別664 718個重復軌跡點之后，預測方法進行重復數(shù)據(jù)刪除操作，得到8 364 012個有效軌跡點數(shù)，同時獲得799 935條軌跡。然后利用稀疏軌跡聚類算法補全缺失數(shù)據(jù)，使有效軌跡點數(shù)增加了873 552個，軌跡增加了335 454條?？梢娫摼垲愃惴ㄌ嵘藲v史數(shù)據(jù)質量。

(二)對比測試

將提出的預測方法作為實驗組測試對象，將兩個傳統(tǒng)預測模型分別作為對照1組測試對象和對照2組測試對象，模擬一條旅游軌跡(圖6)。

圖6 軌跡預測標準

以圖6中的軌跡為最終目標，圖7為3個測試組的旅游目的地軌跡預測結果。

(a) 實驗組測試結果

根據(jù)圖中曲線走勢可知，實驗組的預測軌跡與圖6所示的標準軌跡之間的偏離值更小，而兩個對照組的預測軌跡與標準軌跡之間的偏離值更大。進一步計算預測軌跡與標準軌跡之間的偏離值，結果如表2所示。

表2 平均偏離值計算結果

根據(jù)表中的計算結果可知，實驗組的5組偏離數(shù)值均在200 m左右，對照組的5組偏離數(shù)值在500～800 m之間。經(jīng)計算，5次測試下實驗組的平均偏離值為222.12 m，對照組的平均偏離值分別為570.07 m和678.776 m?？梢娞岢龅念A測方法效果更佳。

綜上，該文提出的旅游目的地位置預測方法充分發(fā)揮了稀疏聚類算法的計算特征，實現(xiàn)了對復雜空間數(shù)據(jù)和時間數(shù)據(jù)的特征分析與挖掘。該方法利用稀疏軌跡聚類算法補全缺失數(shù)據(jù)，使有效軌跡點數(shù)增加了873 552個，軌跡增加了335 454條，說明該方法的聚類效果較好。5次測試下，該方法的平均偏離值為222.12 m，說明此方法能夠提升旅游目的地位置預測效果。未來研究將繼續(xù)降低預測軌跡與標準軌跡之間的平均偏離值，以期得到更好的旅游軌跡預測結果。