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

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

1 引 言

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

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

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

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

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

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

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

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

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

2.1 總體框架

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

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

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

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

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

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

定義6.拍攝興趣區(qū)r.拍攝興趣區(qū)是指游客在這里拍攝了大量照片的區(qū)域,用戶一般會(huì)在景點(diǎn)拍攝大量照片,除此之外,當(dāng)發(fā)生一些較為重要的事件時(shí)也會(huì)拍攝照片.因?yàn)樵诒疚挠懻摰姆秶鷥?nèi),拍攝興趣區(qū)均為景點(diǎn),后文與景點(diǎn)通用.

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

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

定義8.1.

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

定義8.2.

該指標(biāo)反映了拍攝興趣區(qū)ra緊挨著rb之前出現(xiàn)的頻率,體現(xiàn)了人們?cè)谟斡[rb之前喜歡從哪些地方直接過(guò)來(lái).

定義8.3.

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

定義8.4.

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

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

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

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

算法1.DPC聚類算法.

輸入:待聚類數(shù)據(jù)點(diǎn),截?cái)嗑嚯xdc

輸出:每個(gè)數(shù)據(jù)點(diǎn)所屬類

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

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

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

4.確定聚類中心

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

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

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

wbi=∑F(bi,PΔt)

(1)

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

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

(2)

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

(3)

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

(4)

當(dāng)bi是密度最大的數(shù)據(jù)點(diǎn)時(shí),

(5)

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

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

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

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

輸出:所有數(shù)據(jù)點(diǎn)聚類編號(hào)

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)鍵徑，按照時(shí)間順序訪問(wèn)用戶的每一個(gè)拍攝記錄,判斷拍攝位置是否在一個(gè)拍攝興趣區(qū)內(nèi),如果是則表示該用戶在此時(shí)刻在游覽該區(qū)域,并且如果該用戶之前未訪問(wèn)過(guò)該拍攝興趣區(qū),則在關(guān)鍵徑添加該點(diǎn),如果不是則跳過(guò)該記錄.最后即可得到該用戶游覽的關(guān)鍵徑.

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

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

(6)

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

3 實(shí)驗(yàn)及分析

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

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

表1 使用Flickr獲取照片時(shí)使用的主要參數(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照片拍攝最早時(shí)間max＿taken＿date16/9/30照片拍攝最晚時(shí)間

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

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

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

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

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

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

3.2 軌跡切割時(shí)間Δt的確定

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

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

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

圖7 長(zhǎng)途旅游和短途旅游記錄Fig.7 Short-trips and long-trips

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

3.3 關(guān)鍵徑

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

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

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

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

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

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

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

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

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

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

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

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

1)故宮作為北京“超級(jí)景點(diǎn)”,更容易作為在北京游覽的起點(diǎn),同時(shí)也吸引著來(lái)自其他景點(diǎn)的游客.

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

3)對(duì)于通過(guò)乘坐飛機(jī)這一交通方式來(lái)北京旅游的游客來(lái)說(shuō),首都國(guó)際機(jī)場(chǎng)能吸引游客在此拍照,體現(xiàn)了不同交通方式對(duì)游客拍攝行為的影響.

4 總 結(jié)

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

[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.