內(nèi)嵌時空信息的照片數(shù)據(jù)中的游覽模式探索

徐志明,梁 循,李志宇,齊金山

(中國人民大學 信息學院 信息系,北京 100872)(淮陰師范學院 計算機科學與技術(shù)學院,江蘇 淮安 223300)

1 引 言

隨著多媒體技術(shù)和互聯(lián)網(wǎng)技術(shù)的發(fā)展,人們開始越來越多地在社交網(wǎng)站上分享自己當前的狀態(tài)以及發(fā)布自己拍攝的照片等信息.與此同時,越來越多的數(shù)碼產(chǎn)品如數(shù)碼相機、智能手機等移動設(shè)備可以拍攝帶有元數(shù)據(jù)(metadata)的照片,這些照片中除了包含圖像信息外,還包含了照片拍攝的時間、地理位置等信息.國外一些網(wǎng)站如Flickr、Panoramio等還為用戶提供了地理位置標注、檢索、瀏覽、分類以及分類等功能,這為探索用戶行為提供了更多可以使用的數(shù)據(jù).

帶有地理信息的照片是獲得用戶所處位置,了解用戶行為習慣的一個重要數(shù)據(jù)來源.研究者利用帶有地理位置標簽的照片做了很多的研究工作,具體集中在興趣點發(fā)掘和旅游推薦[1-6],照片拍攝地點預(yù)測[7,8],用戶行為模式分析[9,10]等方面.例如,文獻[1]針對地理數(shù)據(jù)的層次性,分別在全局和局部進行了聚類來找到用戶關(guān)注的興趣點并對興趣點使用關(guān)聯(lián)規(guī)則進行挖掘,文獻[4]結(jié)合了基于主題和協(xié)同過濾的方法,在用戶參觀過的興趣點較少的情況下仍然可以提取用戶特征,在數(shù)據(jù)稀疏的情況下仍然能較好地推薦.文獻[7]對照片拍攝位置以及照片內(nèi)容之間的關(guān)系進行建模,然后使用聚類的方法預(yù)測照片的拍攝位置.文獻[9]對Flickr用戶上傳的照片進行分析,探索了游客和當?shù)厝?男性和女性等不同群體用戶的拍攝習慣.在地理興趣點挖掘時,主要依靠聚類方法[1,6,11,12].如文獻[6]在進行旅游推薦之前,首先應(yīng)用DBSCAN算法對數(shù)據(jù)點進行聚類來找到旅游地標,而文獻[11]在DBSCAN聚類算法的基礎(chǔ)上針對地理應(yīng)用進行擴展,將用戶考慮到聚類中,以此得到更加魯棒的聚類結(jié)果.文獻[12]提出使用柵格結(jié)構(gòu)對地理數(shù)據(jù)進行聚類.

在文獻[13]中,作者提出利用帶有標簽信息的照片挖掘出興趣點,然后利用這些興趣點構(gòu)建用戶每天的游覽軌跡,接著對這些軌跡進行分析找出一些游覽次序上的模式.但是根據(jù)從Flickr上下載的照片數(shù)據(jù),我們發(fā)現(xiàn)一些照片的拍攝時間字段和實際情況不符.下頁圖1中為三張來自Flickr的由不同用戶拍攝的照片,根據(jù)Flickr接口提供的數(shù)據(jù),這三張照片拍攝時間均在23～24點,但是故宮的最早開放時間是早上8:00,最晚閉館時間為下午17:00,在該時間段游客是不允許進入并拍照的.而且從照片內(nèi)容可以看出,這些照片都是在白天拍攝的,所以這些照片中的時間是錯誤的,不能直接使用照片中帶有的確定的時間(如零點)作為分割照片序列的依據(jù).

圖1 三位不同用戶在“23點”拍攝的照片F(xiàn)ig.1 Three photos taken by three different users after 11 p.m.

雖然Flickr提供了部分用戶所在時區(qū),但是該數(shù)據(jù)可靠性難以保證,我們嘗試使用時區(qū)信息進行糾正,但是仍然有大量照片的內(nèi)容和拍攝時間不符.由于實際可獲得照片的拍攝時間是有偏差的(我們認為主要是因為用戶的拍照設(shè)備沒有更新時區(qū),所以照片的時間上雖然是有誤差的,但是照片拍攝的時間順序是正確的),所以使用具體的時間(如零點)對戶游覽的次序進行分割是不合理的.因此應(yīng)該找到另一個方法對用戶拍攝的照片序列進行分段,以獲得游客在各次游覽活動中拍攝的照片,來更加全面準確地反映游客的游覽行為.

圖2 2011年1月至2016年9月,6451位用戶在北京的“停留時間”分布Fig.2 Distribution of 6451 users′ stay-time from January 2011 to September 2016 in Beijing

圖2為從Flickr上獲取的,在2011年1月1日至2016年9月30在北京拍攝照片的用戶的“停留時間”分布.“停留時間”定義為用戶在北京拍攝的最后一張照片與第一張照片的時間差.“停留時間”在一定程度上反映了用戶和北京的關(guān)系,外地游客更有可能在北京作短時間的停留,所以他們的“停留時間”較短,而北京本地人可以隨時在北京進行拍攝照片,他們的“停留時間”就比較長.從圖2可以看出,有大約50%的用戶在北京的“停留時間”少于24小時,說明了他們只有很短時間停留在北京或者在北京但只有較短時間有拍攝照片的習慣,因此我們認為在這些較短的停留時間段內(nèi),用戶有計劃地進行了一些游覽活動.隨著停留時間的增加,用戶數(shù)量呈現(xiàn)出遞減的趨勢,但是最后仍然有大量的用戶的“停留時間”很長,說明他們?yōu)楸本┍镜赜脩?或者他們有多次到北京的游覽行為.因此根據(jù)“停留時間”可以發(fā)現(xiàn)，大部分在北京拍攝照片的用戶更多的是游客,而且Flickr的用戶中北京用戶占比非常小,北京作為國際性大都市,能夠吸引來自世界各地的游客,所以在北京拍攝的照片大部分是外地游客拍攝的,在一定程度上體現(xiàn)了游客的游覽偏好.

因此,我們提出從游客拍攝的照片數(shù)據(jù)出發(fā),來挖掘游客的游覽偏好并給出部分量化指標.首先使用每個用戶照片的拍攝時間間隔對拍攝記錄進行分割,在此基礎(chǔ)上定義長途旅游記錄和短途旅游記錄,緊接著將其轉(zhuǎn)化為體現(xiàn)游覽順序的關(guān)鍵徑,最后在大量用戶關(guān)鍵徑的支持下,利用轉(zhuǎn)移頻率量化游客的游覽偏好.

2 基于關(guān)鍵徑的旅游路線挖掘

2.1 總體框架

游客只會在自己感興趣的區(qū)域拍照,很少在自己行進路線上頻繁拍照,而且用戶選擇上傳的照片也是自己拍攝照片的子集,所以能夠獲得的拍攝記錄更多反應(yīng)的是游客喜歡拍照并且把照片上傳的位置,以及游覽這些點的時間,而不是行進軌跡.所以為了找到通用性的游覽軌跡,我們應(yīng)該把那些反映少數(shù)人偏好的拍攝點刪除,把剩下的拍攝點劃分成不同的興趣區(qū)域,并以游客游覽興趣區(qū)域的順序來表示游覽路線.為了更好地表述本文的方法,我們提出以下定義.

定義1.拍攝記錄PA=,i=1,2,3,….拍攝記錄為一個用戶在特定時間段[t1,t2]拍攝行為的集合.其中pi=(lati,lgti,ti)表示拍攝點,lati和lgti分別為拍攝該照片拍攝的緯度和經(jīng)度(由于GPS偏差在本文所述模型中影響可以忽略,所以使用照片拍攝時自帶的GPS信息作為用戶拍攝照片時實際的地理坐標.),ti為用戶拍攝照片的時間,滿足p1.t=t1,p|PA|.t=t2(|PA|表示取序列的長度),且pi+1.t≥pi.t.由于用戶上傳的照片只是實際游覽時拍攝照片的子集,所以我們能獲得的數(shù)據(jù)也是不完整的.

定義2.最大記錄間隔TPA=max(pi+1.t-pi.t),i=1,…,|PA|-1.最大記錄間隔用來描述用戶拍攝記錄PA中相鄰的照片的最大拍攝時間間隔.

定義3.當拍攝記錄PA滿足條件TPA≤Δt,稱PA為旅游記錄,記為PΔt,代表一個用戶在一次活動中拍攝記錄集合.例如游客在游覽故宮時拍攝照片的記錄集合構(gòu)成了游覽拍攝記錄,若在此次游覽活動中相鄰拍攝照片的最大時間差為t′,則有Δt≥t′.對應(yīng)地,游客在花費幾天在北京游玩拍攝記錄也構(gòu)成了一個旅游記錄,只是Δt較大.

定義4.長途旅游記錄.針對拍攝記錄PA,通過把相鄰時間間隔小于Δt的元素分為一組即可得到旅游記錄序列,記為PP=,i=1,….對于PΔt,i如果有i=1∨(S(PΔt,i)-F(PΔt,i-1)>tmax)并且i=|PP|∨(S(PΔt,i+1)-F(PΔt,i)>tmax)則稱它為長途旅游記錄.式中∨表示邏輯表達式中的或者,(S(PΔt,i)和F(PΔt,i-1)分別表示取拍攝記錄的第一個元素的時間和最后一個元素的時間.長途旅游記錄代表了一個游客在在較長時間段之內(nèi)進行對某地僅進行了一次游覽,所以該次游覽更可能是有規(guī)劃的,系統(tǒng)性的游覽.

定義5.短途旅游記錄.針對拍攝記錄PA,通過把相鄰時間間隔小于Δt的元素分為一組即可得到旅游記錄序列,記為PP=,i=1,….對于PΔt,i如果有i>1∧(S(PΔt,i)-F(PΔt,i-1)

定義6.拍攝興趣區(qū)r.拍攝興趣區(qū)是指游客在這里拍攝了大量照片的區(qū)域,用戶一般會在景點拍攝大量照片,除此之外,當發(fā)生一些較為重要的事件時也會拍攝照片.因為在本文討論的范圍內(nèi),拍攝興趣區(qū)均為景點,后文與景點通用.

定義7.關(guān)鍵徑v=,i=1,2,3,….關(guān)鍵徑是拍攝興趣區(qū)構(gòu)成的序列,元素之間的順序體現(xiàn)了游覽順序.由于一般游客只有在一次游覽行為中經(jīng)過一個景點一次,所以令 它表示了一個游客在特定時間段內(nèi),訪問了哪些拍攝興趣區(qū)以及第一次訪問這些區(qū)域的時間順序.

定義8.轉(zhuǎn)移頻率:R.轉(zhuǎn)移頻率反應(yīng)了游客在不同拍攝興趣區(qū)之間游覽次序的偏好,包含了四個元素:緊鄰后向頻率RMN,ra,rb,緊鄰前向頻率RMP,ra,rb,全局后向頻率RN,ra,rb和平均全局后向頻率RNA,r.

定義8.1.

I(x)表示指示函數(shù),若x代表的表達式為真,該函數(shù)返回1,否則返回0.In(r,v)表示取元素r在序列v中從1開始的下標.該指標反映了拍攝興趣區(qū)rb緊挨著ra之后出現(xiàn)的頻率,體現(xiàn)了人們在游覽ra之后喜歡直接轉(zhuǎn)到哪些地方.

定義8.2.

該指標反映了拍攝興趣區(qū)ra緊挨著rb之前出現(xiàn)的頻率,體現(xiàn)了人們在游覽rb之前喜歡從哪些地方直接過來.

定義8.3.

該指標反映了拍攝興趣區(qū)ra和rb同時出現(xiàn)時,ra在rb之前出現(xiàn)的頻率,從整體上體現(xiàn)了人們在ra和rb之間游覽的先后次序偏好.

定義8.4.

關(guān)鍵徑的提取整體流程如圖3所示.在圖3(a),(b),(c)中,每個點表示用戶在該位置拍攝了照片,相同灰度的點表示來自同一個拍攝記錄(或旅游記錄),點之間的箭頭表示時間的先后關(guān)系.圖3(a)中表示了用戶拍攝記錄的初始數(shù)據(jù)PA1和PA2,包含拍攝位置以及時間(順序)信息,數(shù)據(jù)點之間的連線代表了時間上的先后關(guān)系.在圖3(b)中,根據(jù)Δt對每個用戶的拍攝記錄進行分割得到旅游記錄,由于點p1和p2之間的時間差大于閾值Δt,所以對PA1進行分組,得到兩個旅游記錄P1和P2,同時由于PA2中時間差均小于Δt,所以由它得到旅游記錄P3.在圖3(c)中,由于圖3(b)中得到的3個旅游記錄均為長途旅游記錄,所以使用它們的數(shù)據(jù)點找到拍攝興趣區(qū)ra、rb、rc、rd,如圖中虛線框所示.最后,將長途旅游記錄經(jīng)過興趣區(qū)的順序作為關(guān)鍵徑,如圖3(d)所示.

圖3 關(guān)鍵徑生成流程Fig.3 Process of generating key-path

2.2 拍攝興趣區(qū)發(fā)現(xiàn)

由于拍攝興趣區(qū)是有多名用戶拍攝了大量照片的區(qū)域,所以可以使用聚類的方法來找到這些區(qū)域,我們使用密度峰值聚類算法(DPC,Clustering by fast search and find of Density Peaks)[14]中來發(fā)現(xiàn)關(guān)鍵區(qū)域.DPC算法首先計算所有數(shù)據(jù)點的局部密度,然后將具有較大密度并且和最近更大密度數(shù)據(jù)點的距離較遠的點作為聚類中心,最后把剩下的數(shù)據(jù)點和它的最近的更大密度點的分成一類.該算法可以忽略異常數(shù)據(jù)點、使用參數(shù)較少(可以不設(shè)置聚類個數(shù))并且能夠獲得不規(guī)則的聚類[15,16].DPC聚類的步驟見算法1.

算法1.DPC聚類算法.

輸入:待聚類數(shù)據(jù)點,截斷距離dc

輸出:每個數(shù)據(jù)點所屬類

1.計算所有數(shù)據(jù)點對之間的距離

2.根據(jù)dc計算所有數(shù)據(jù)點的局部密度

3.找到所有數(shù)據(jù)點的最近更大密度點,并保存它們之間的距離

4.確定聚類中心

5.將聚類中心之外的數(shù)據(jù)點分配到相應(yīng)的類別中

使用聚類算法的目的是發(fā)現(xiàn)反映更多游客偏好的拍攝興趣區(qū),而不是將這些拍攝記錄分為幾類,所以我們對原始的DPC聚類算法進行了相應(yīng)的調(diào)整.一是使用柵格消除單個用戶在一次游覽中在相近位置拍攝大量照片對數(shù)據(jù)點局部密度的影響,二是使用平均密度來排除邊緣點,找到具有較高密度的拍攝興趣區(qū).

為了加快數(shù)據(jù)的處理速度以及反映更多游客的偏好,我們利用選定范圍內(nèi)的經(jīng)緯度坐標將拍攝點進行柵格化處理,柵格的權(quán)重定義為:

wbi=∑F(bi,PΔt)

(1)

公式(1)中柵格的權(quán)重表示在該柵格有拍攝行為的一次游覽記錄.與之前學者[11]的方法略有不同,我們在柵格化時消除單個用戶在相近位置拍攝大量照片對數(shù)據(jù)點密度造成的影響.考慮到一個用戶可能有多次游覽,而每次游覽都代表這該地區(qū)的吸引力,所以沒有使用在柵格中有拍攝記錄的用戶的數(shù)量作為柵格的權(quán)重,而是使用不同的PΔt.

對數(shù)據(jù)進行柵格化之后,使用公式(1)計算柵格的權(quán)重,然后將柵格作為待聚類的數(shù)據(jù)點,數(shù)據(jù)點的位置使用柵格所在的行和列的坐標來表示.設(shè)新的數(shù)據(jù)點集為S={bi},i=1,2,3,…,其中bi=(xi,yi,wi),柵格間的距離定義為:

(2)

數(shù)據(jù)點bi的局部密度ρi可以被被定義為:

(3)

式(3)表示ρi等于與數(shù)據(jù)點bi的距離小于dc(截斷距離)的點的權(quán)重之和,截斷距離dc需要事先確定.在求得所有數(shù)據(jù)點的局部密度之后,下一步就是確定數(shù)據(jù)點bi和最近的具有更高密度的數(shù)據(jù)點之間的距離,該距離δi的定義為:

(4)

當bi是密度最大的數(shù)據(jù)點時,

(5)

緊接著使用ρi和δi的乘積的前k大的數(shù)據(jù)點作為聚類中心.在確定了聚類中心之后,下一步就是將聚類中心之外的數(shù)據(jù)點劃分到相應(yīng)的類中.仍然是按照ρ降序的方式訪問數(shù)據(jù)點,將它們劃分所屬的類中.

原始的DPC聚類算法會將數(shù)據(jù)點劃分到相應(yīng)的類中,但是現(xiàn)在需要找到密度較高拍攝興趣區(qū),拍攝興趣區(qū)的特點是具有較高的密度,并且數(shù)據(jù)點之間的距離較近.所以在劃分數(shù)據(jù)點所屬類時,使用邊界距離db和密度系數(shù)α來判斷該數(shù)據(jù)點是否應(yīng)該加到相應(yīng)的類中.

算法2.確定聚類中心之外數(shù)據(jù)點所屬類.

輸入:已確定聚類中心數(shù)據(jù)點的聚類編號列表cluster,數(shù)據(jù)點的局部密度density,按局部密度排序?qū)?yīng)的下標sort_index,與各個數(shù)據(jù)點距離最近的具有更高(或相等)的局部密度的數(shù)據(jù)點near_index

輸出:所有數(shù)據(jù)點聚類編號

1. FOR i=1:n

2. IF -1 (cluster[i]

3. count[cluster[i]]=1

4. sum[cluster[i]]=local_density[i]

5. END IF

6. END FOR

7. FOR i=1:n

8. curi=sort_index[i]

9. IF -1=cluster[curi]&& -1 ( near_index[curi]

10. hCluster=cluster[near_index[curi]]

11. IF density[curi]>(Q*sum[hCluster]/count[hCluster]) && near_index[curi]>DISTANCE

12. cluster[curi]=hCluster

13. count[hCluster]=count[hCluster] + 1

14. sum[hCluster]=sum[hCluster] + density[curi]

15. END IF

16. END IF

17. END FOR

2.3 關(guān)鍵徑

在找到拍攝興趣區(qū)之后,下一步就可以將用戶的拍照記錄映射到拍攝興趣區(qū)中,生成關(guān)鍵徑，按照時間順序訪問用戶的每一個拍攝記錄,判斷拍攝位置是否在一個拍攝興趣區(qū)內(nèi),如果是則表示該用戶在此時刻在游覽該區(qū)域,并且如果該用戶之前未訪問過該拍攝興趣區(qū),則在關(guān)鍵徑添加該點,如果不是則跳過該記錄.最后即可得到該用戶游覽的關(guān)鍵徑.

關(guān)鍵徑反映了游客選擇游覽哪些拍攝興趣區(qū),以及以什么樣是順序進行游覽,這體現(xiàn)了用戶的選擇與偏好,也包含了一些規(guī)劃,如游客偏向于最后的游覽位置靠近出口.所以,游覽歷史體現(xiàn)了人們對于該景點各個子區(qū)域的游覽的規(guī)劃,通過對所有人的路徑進行分析,可以找到受到最多人歡迎的游覽順序.

為了從所有用戶的關(guān)鍵徑中挖掘出共有的游覽模式,需要度量不同關(guān)鍵徑之間的距離,在這里我們首先使用LCS(Longest Common Subsequence)算法來計算兩個關(guān)鍵徑之間的最大公共路徑長度L(P,Q),然后定義它們之間的相似性為:

(6)

根據(jù)經(jīng)驗可知,長度短的關(guān)鍵徑數(shù)量較多,更容易獲得更高的密度,長度較長的關(guān)鍵路徑數(shù)量較少,且更難發(fā)現(xiàn)距離近的其他數(shù)據(jù)點,所以不容易設(shè)定確定聚類中心的密度閾值,這里仍然使用DPC聚類算法,然后根據(jù)決策圖來確定聚類數(shù)量,然后從聚類結(jié)果中找到有價值的游覽模式.

3 實驗及分析

3.1 數(shù)據(jù)獲取

由于Flickr網(wǎng)站上有大量帶有GPS信息的照片,并且Flickr提供了下載相關(guān)數(shù)據(jù)的API( https://www.flickr.com/services/apps/create/),所以我們從Flickr上下載實驗數(shù)據(jù).我們主要使用flickr.photos.search接口來獲得需要的照片,該方法的參數(shù)主要包含照片的生成時間范圍,以及照片的拍攝地點.我們使用的參數(shù)如表1所示.由于該接口對一次檢索的照片數(shù)量有限制,所以們按月份依次獲取在該范圍內(nèi)的照片,最后對所有的數(shù)據(jù)進行匯總.

表1 使用Flickr獲取照片時使用的主要參數(shù)
Table 1 Parameters used when fetching photos with Flickr API

參數(shù)值描述minimum＿longitude115．7照片拍攝范圍的最小經(jīng)度minimum＿latitude39．4照片拍攝范圍的最小緯度maximum＿longitude117．4照片拍攝范圍的最大經(jīng)度maximum＿latitude41．6照片拍攝范圍的最大緯度min＿taken＿date11/1/1照片拍攝最早時間max＿taken＿date16/9/30照片拍攝最晚時間

在Flickr上傳照片時,如果照片的exif信息中含有拍攝時間信息,則該網(wǎng)站會把該時間作為照片的拍攝時間,否則會把該照片的上傳時間作為拍攝時間,所以在獲得了照片數(shù)據(jù)之后,把照片信息中的“taken unknown”字段為1的照片刪除,以獲得帶有正確拍攝時間的照片.

然后根據(jù)這些照片帶有的用戶ID獲取用戶的個人信息.根據(jù)用戶自己設(shè)置的所在地信息,從2011年1月1日到2016年9月30來北京參觀的游客的統(tǒng)計見圖4.圖4中除最右側(cè)的直方圖為來自中國的用戶外,其他為各個大洲在每年來北京的游客數(shù)量(亞洲為除去中國人后剩余的數(shù)量).從圖中可以發(fā)現(xiàn),發(fā)達地區(qū)每年來北京旅游的游客數(shù)量普遍高于欠發(fā)達地區(qū).

圖4 2011年1月至2016年9月到北京旅游的游客分布Fig.4 Distribution of users visited Beijing from January 2011 to September 2016

我們分別利用1月到12月拍攝的照片進行聚類,并設(shè)定聚類個數(shù)為10,總共得到16個拍攝興趣區(qū).在對每一個月份的數(shù)據(jù)進行聚類時,根據(jù)聚類中心的排名對聚類對應(yīng)的景點進行打分,從第1名到第10名的分數(shù)遞減,沒有出現(xiàn)在該月聚類結(jié)果中的興趣區(qū)得分為0.這16個景點在各個月份的得分情況如圖5所示,圖中橫坐標表示12個月份,縱坐標為16個興趣區(qū),圖中點的面積越大代表該景點在該月的排名越靠前.

圖5 16個興趣區(qū)在12個月中的排名Fig.5 Clustering results of 16 regions of interests in 12 months

從圖5中可以發(fā)現(xiàn),故宮、天安門廣場和天壇公園作為北京的標志性景點,常年是最受歡迎熱門景點之一,但是受到農(nóng)歷春節(jié)的影響,天安門廣場和天壇公園的影響力減弱,王府井的影響力增加.三里屯太古里作為一個綜合休閑娛樂區(qū)也能在一年中保持非常高的吸引力.頤和園是一座園林式景點,它的受歡迎程度受到了季節(jié)的影響,從3月到10月份的受歡迎程度高于冬天的幾個月份.

3.2 軌跡切割時間Δt的確定

為了確定合適的軌跡切割時間,我們分別令Δt為12h、24h、48h、72h和96h進行實驗,統(tǒng)計不同的Δt對每個用戶切割得到的軌跡的數(shù)量,對應(yīng)的結(jié)果如圖6所示.橫坐標代表切割所得的旅游記錄數(shù)量,縱坐標表示對應(yīng)該數(shù)量的用戶數(shù).從圖中可以發(fā)現(xiàn)隨著Δt的減小,旅游記錄數(shù)量為1的用戶數(shù)量逐漸減少,這主要是因為使用較短的Δt可會把一些使用較大Δt切割所獲得的結(jié)果再次進行切割,從而體現(xiàn)為分段數(shù)量較多的用戶數(shù)增加,圖中旅游記錄數(shù)量2-8段的曲線反映了該結(jié)果.從圖6中還可以發(fā)現(xiàn)當Δt為72h時只含有一個軌跡用戶的數(shù)目達到了一個平衡,我們認為72h是一個較為合理的切割時間.

圖6 不同的時間閾值Δt對用戶旅游記錄的影響Fig.6 Effect of Δt on the number of trip records of each user

一般本地用戶在北京進行拍攝活動會非常方便,所以在幾年間容易有較多拍攝記錄,而且這些記錄相隔時間容易大于一個時間閾值T(假設(shè)為7天),所以他們更容易有較多的軌跡.而外地游客一般在一段時間內(nèi)只來北京一次,如果在該地有較多的軌跡,那么這些軌跡的時間間隔應(yīng)該較大,一般可以達到幾個月,所以使用軌跡數(shù)量為1的數(shù)量的穩(wěn)定性可以反映是否是有計劃游覽的.對于來北京出差的用戶來說,旅游只是在閑暇時間的活動,所以可能有較大的最大記錄間隔TPA.另外由于所獲得數(shù)據(jù)是戶游覽拍攝照片的子集,時間間隔也會因用戶的選擇而擴大.

圖7 長途旅游和短途旅游記錄Fig.7 Short-trips and long-trips

在使用72h作為分割時間獲得了所有的旅游記錄后,接著使用6個月作為Tmax來分別獲取長途旅游記錄和短途旅游記錄.使用Google Earth軟件分別將短途旅游記錄和長途旅游記錄中連續(xù)的拍攝點連線并在地圖上標出,得到如圖7所示的結(jié)果.從圖中可以看出著名景點體現(xiàn)出了很強的吸引力,有大量的用戶在那里拍攝了照片,其次可以發(fā)現(xiàn)在短途旅游記錄中拍攝的照片大多分散在北京城區(qū)而長途旅游記錄中的照片明顯具有很強的集中性(景點),以及在景點之間進行轉(zhuǎn)移.因此不同類型的旅游記錄形態(tài)體現(xiàn)了分類方法的有效性.

3.3 關(guān)鍵徑

為了獲得關(guān)鍵徑,首先使用5333組長途旅游記錄中的數(shù)據(jù)點進行聚類,得到20個拍攝興趣區(qū),然后把“穿過”拍攝興趣區(qū)的旅游記錄的數(shù)量少于150的區(qū)域刪除,得到了如下聚類結(jié)果:天壇公園、鳥巢、王府井、慕田峪長城、天安門廣場、三里屯、頤和園、雍和宮、故宮、國際機場、景山公園、后海,可以發(fā)現(xiàn)所有拍攝興趣區(qū)除了國際機場外均為較為著名的景點.首都國際機場是中國最繁忙的國際空港,相比于其他典型景點,能吸引游客在此拍照的主要原因一是它的現(xiàn)代化的設(shè)施與建筑,另一個原因我們認為是它更像是一個游覽的預(yù)備點,是在北京進行游覽的起始點.

接著即可得到代表游覽這些景點次序的關(guān)鍵徑,關(guān)鍵徑的節(jié)點數(shù)目和對應(yīng)的數(shù)量關(guān)系如表2所示.從表2中可以發(fā)現(xiàn)有3274(61.39%)條關(guān)鍵徑的節(jié)點數(shù)目為0(表示未“穿過”任何拍攝興趣區(qū)),而在剩下的節(jié)點數(shù)目不為0的關(guān)鍵徑中,大部分關(guān)鍵徑節(jié)點數(shù)目為1,占比為62.17%.另外,可以發(fā)現(xiàn)隨著關(guān)鍵徑節(jié)點數(shù)量的增加,對應(yīng)的關(guān)鍵徑的數(shù)量也是逐漸減少的,最長的關(guān)鍵徑長度為10,數(shù)量為2.

表2 關(guān)鍵徑節(jié)點數(shù)量與關(guān)鍵徑數(shù)量關(guān)系
Table 2 Number of key-paths with different length

長度012345>5數(shù)量327412803481891126763

將緊鄰后向頻率超過0.2的轉(zhuǎn)移在圖中標識出來的結(jié)果見圖8.興趣區(qū)后括號中的數(shù)字為訪問次數(shù),興趣區(qū)之間的有向連線表示興趣區(qū)訪問先后次序.例如從天安門指向故宮的標有0.71的箭頭表示離開天安門后直接去故宮的頻率為0.71.從圖中可以看出,其他大部分景點到故宮的緊鄰后向頻率均超過了0.2,體現(xiàn)了故宮相對其他景點的吸引力較強.另一個顯著的特點是緊鄰后向頻率超過0.25的均發(fā)生在距離較近的景點之間,體現(xiàn)了游客偏向于游覽一個景點后去距離較近的另一個景點.從天安門廣場到故宮的轉(zhuǎn)移頻率達到了0.71,這與廣場距離故宮的距離非常近有關(guān).而且由于故宮的游覽方向是確定的,游客必須從午門(南門)進入,從神武門(北門)離開,所以游客更有可能先參觀天安門廣場然后從南門進入故宮,從而減少路途上的時間.

將所有緊鄰前向頻率大于0.2的興趣區(qū)對標出,結(jié)果如圖9所示.興趣區(qū)后括號中的數(shù)字為訪問次數(shù),興趣區(qū)之間的有向連線表示訪問先后次序.例如從故宮指向頤和園的標有0.31的箭頭表示在游覽頤和園之前有比例為0.31的用戶參觀了故宮.從圖中可以發(fā)現(xiàn)所有興趣區(qū)和故宮的緊鄰前向頻率均超過了0.2,表明了對所有其他興趣區(qū)而言,有相當大的比例游客剛?cè)ミ^故宮,故宮像一個“興趣核心”,輻射到其它興趣區(qū).

圖9 所有興趣區(qū)之間不小于0.2的緊鄰前向頻率Fig.9 Regions of Interest with previous visit frequency no less than 0.2

將全局后向頻率超過0.7的興趣區(qū)對在圖中標出,得到如圖10所示的結(jié)果,每個興趣區(qū)括號中的數(shù)字為平均全局轉(zhuǎn)移概率.箭頭的指向表示興趣區(qū)排列的先后關(guān)系.例如從天安門廣場指向故宮標有0.78的箭頭表示在天安門廣場和故宮同時出現(xiàn)的關(guān)鍵徑中,天安門廣場排在故宮前面的頻率為0.78(故宮排在天安門廣場后面的頻率為0.22).從整體上來看,平均全局后向頻率超過0.6的只有故宮和天安門廣場,表明這兩個景點是游客最早參觀的,同時天安門廣場的0.66大于故宮的0.60也與之前的游客先去天安門廣場再去故宮相互呼應(yīng).平均全局后向頻率最低的是慕田峪長城和鳥巢,說明游客偏向于最后再去這兩個地方.

圖10 所有興趣區(qū)之間不小于0.7的全局后向頻率Fig.10 Regions of Interest with average global next visit frequency no less than 0.7

通過觀察全局后向頻率超過0.7的興趣區(qū)可以發(fā)現(xiàn),由天安門廣場指出的箭頭最多,說明這里更普遍地被作為游覽的起點.由天安門廣場出發(fā),經(jīng)(故宮、)頤和園、三里屯和雍和宮形成了一個較長的游覽路徑,在這條路徑中頤和園(0.46)和三里屯(0.51)的平均全局后向頻率較低,但是仍然有相對于其他興趣區(qū)(分別對應(yīng)三里屯和雍和宮)有較強的優(yōu)先性.從圖還可以發(fā)現(xiàn),存在由國際機場在前的全局后向頻率達到0.7,同時也存在國際機場在后的全局后向頻率達到0.7.表明部分游客從國際機場出發(fā),進行游覽,最后也有很多游客從國際機場離開.這種情形導致了國際機場的平均全局后向頻率趨近于0.5.這體現(xiàn)了國際機場對來北京旅游的游客的重要性.

上文的分析只能找到任意兩個興趣點對之間的游覽先后次序關(guān)系,并不能從整體上發(fā)現(xiàn)常見的游覽模式.所以接下來通過對所有的關(guān)鍵徑聚類的方法找到頻繁出現(xiàn)的游覽行為.通過之前的實驗可以發(fā)現(xiàn),故宮和天安門廣場作為最熱門的景點,共同出現(xiàn)的頻率很高,而且由于兩者在地理位置上也比較近,所以在接下來的實驗中我們將天安門廣場作為故宮的一部分.然后選取所有長度不小于3的關(guān)鍵徑進行聚類,選取排名前5的聚類中心,它們分別是:(故宮->鳥巢->天壇公園)、(故宮->天壇公園->鳥巢)、(故宮->后海->天壇公園)、(故宮->天壇公園->后海)、(故宮->天壇公園->慕田峪長城),可以發(fā)現(xiàn)所有的關(guān)鍵徑都以故宮為起點,并且包含天壇公園,說明了游客大多是以故宮作為游覽的起點.它們之間的區(qū)別主要是第三個景點是哪里,以及以什么樣的順序?qū)λ鼈冞M行游覽.

最后將發(fā)現(xiàn)概括如下:

1)故宮作為北京“超級景點”,更容易作為在北京游覽的起點,同時也吸引著來自其他景點的游客.

2)游客偏向于在游覽了一個景點之后去更近的下一個景點,特別是能明顯節(jié)省旅游時間時.

3)對于通過乘坐飛機這一交通方式來北京旅游的游客來說,首都國際機場能吸引游客在此拍照,體現(xiàn)了不同交通方式對游客拍攝行為的影響.

4 總 結(jié)

本文提出一種對連續(xù)拍攝照片的時間分割準則,并基于密度峰值聚類(DPC)的方法定義拍攝興趣區(qū)和游覽路徑,接著還定義了緊鄰后向頻率,緊鄰前向頻率,全局后向頻率和平均全局后向頻率.基于在北京地區(qū)拍攝的20萬張照片的時空信息,使用提出的方法對游客游覽北京的模式進行了分析,驗證了方法的有效性.本文所做的工作仍然處于初級階段,找到更加精準地描述游覽行為的模型需要付出更多的努力.

[1] Ickjai Lee,Cai Guo-chen,Kyungmi Lee.Exploration of geo-tagged photos through data mining approaches[J].Expert Systems with Applications,2014,41(2):397-405.

[2] Imran Memon,Chen Ling,Abdul Majid,et al.Travel recommendation using geo-tagged photos in social media for tourist[J].Wireless Personal Communications,2015,80(4):1347-1362.

[3] Peng Pai,Shou Li-dan,Chen Ke,et al.The knowing camera:recognizing places-of-interest in smartphone photos[J].Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval,ACM,2013:969-972.

[4] Jiang Shu-hui,Qian Xue-ming,Shen Jia-lie,et al.Author topic model-based collaborative filtering for personalized POI recommendations[J].IEEE Transactions on Multimedia,2015,17(6):907-918.

[5] Kwan Hui Lim.Recommending tours and places-of-interest based on user interests from geo-tagged photos[C].Proceedings of the 2015 ACM SIGMOD on PhD Symposium,ACM,2015:33-38.

[6] Sun Ye-ran,Fan Hong-chao,Mohamed Bakillah,et al.Road-based travel recommendation using geo-tagged images[J].Computers,Environment and Urban Systems,2015,53:110-122.

[7] Li Li-jia,Rahul Kumar Jha,Bart Thomee,et al.Where the photos were taken:location prediction by learning from flickr photos[M].Large-Scale Visual Geo-Localization.Springer International Publishing,2016:41-58.

[8] Andrew Gallagher,Dhiraj Joshi,Yu Jie,et al.Geo-location inference from image content and user tags[C].IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops,IEEE,2009:55-62.

[9] Cao Yan-peng,Kay O′Halloran.Learning human photo shooting patterns from large-scale community photo collections[J].Multimedia Tools and Applications,2015,74(24):11499-11516.

[10] Su Shi-liang,Wan Chen,Hu Yi-xuan,et al.Characterizing geographical preferences of international tourists and the local influential factors in China using geo-tagged photos on social media[J].Applied Geography,2016,73:26-37.

[11] Slava Kisilevich,Florian Mansmann,Daniel Keim.P-DBSCAN:a density based clustering algorithm for exploration and analysis of attractive areas using collections of geo-tagged photos[C].Proceedings of the 1st International Conference and Exhibition on Computing for Geospatial Research & Application,ACM,2010:38.

[12] Zhao Qin-pei,Shi Yang,Liu Qin,et al.A grid-growing clustering algorithm for geo-spatial data[J].Pattern Recognition Letters,2015,53:77-84.

[13] Zheng Yan-tao,Zha Zheng-jun,Tat-Seng Chua.Mining travel patterns from geotagged photos[J].ACM Transactions on Intelligent Systems and Technology (TIST),2012,3(3):1-18.

[14] Alex Rodriguez,Alessandro Laio.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):492-1496.

[15] Nurjahan Begum,Liudmila Ulanova,Wang Jun,et al.Accelerating dynamic time warping clustering with a novel admissible pruning strategy[C].Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,ACM,2015:49-58.

[16] Zhang Yang,Xia Yun-qing,Liu Yi,et al.Clustering sentences with density peaks for multi-document summarization[C].Proceedings of Human Language Technologies:the 2015 Annual Conference of the North American Chapter of the ACL,2015:1262-1267.