一種應(yīng)用于旅游簽到數(shù)據(jù)的聚類算法

文 堅(jiān)，史紹亮，文益民，3 ，高文翔，龐承杰

1(桂林電子科技大學(xué) 計(jì)算機(jī)與信息安全學(xué)院，廣西 桂林 541004)

2(中國(guó)科技開發(fā)院廣西分院，南寧 530022)

3(廣西可信軟件重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004)

1 引 言

隨著經(jīng)濟(jì)的發(fā)展，旅游人數(shù)逐年上升，人們對(duì)旅游的期望越來越高.通過分析大量的微博簽到數(shù)據(jù)，可以挖掘出旅游景點(diǎn)及其位置、流行度，為游客的旅游安排提供有價(jià)值的參考.

旅游信息挖掘與個(gè)性化推薦的研究很多，文益民等人對(duì)此進(jìn)行了綜述[1].隨著基于位置的社交網(wǎng)絡(luò)(LBSN)的流行，利用位置數(shù)據(jù)挖掘旅游行為并進(jìn)行旅游推薦成為新的熱門方向[2-5].這方面的研究大多是利用實(shí)驗(yàn)儀器采集的GPS數(shù)據(jù)[6,7]、簽到數(shù)據(jù)[8-10]和Flickr網(wǎng)站上含有時(shí)間、地理標(biāo)記的照片數(shù)據(jù)[11-14].國(guó)內(nèi)缺乏類似特征的數(shù)據(jù)資源，相關(guān)研究無法應(yīng)用于國(guó)內(nèi)的旅游分析.越來越多的游客選擇在旅游目的地簽到、發(fā)微博，產(chǎn)生的大量簽到數(shù)據(jù)為挖掘國(guó)內(nèi)旅游景點(diǎn)提供了可靠的大數(shù)據(jù).而目前新浪微博的簽到數(shù)據(jù)并沒有得到很好的利用，有關(guān)研究還只是停留在統(tǒng)計(jì)分析層面[15,16].

本文將從新的視角，借助新浪微博的簽到數(shù)據(jù)，用一種新的聚類算法挖掘旅游景點(diǎn)及其位置、流行度.聚類分析是在無監(jiān)督條件下進(jìn)行數(shù)據(jù)挖掘的一個(gè)重要研究手段，已有聚類算法著重考慮數(shù)據(jù)本身的分布，對(duì)每個(gè)坐標(biāo)點(diǎn)等同對(duì)待，同時(shí)忽視坐標(biāo)點(diǎn)具有的用戶和時(shí)間屬性，因此用于旅游簽到數(shù)據(jù)分析的效果不理想.本文針對(duì)這個(gè)問題，定義權(quán)重和可擴(kuò)展鄰域的概念，并在局部中心點(diǎn)的選取條件中引入用戶和時(shí)間屬性，提出了一種基于局部中心點(diǎn)，以權(quán)重遞減方式擴(kuò)展簇邊界的聚類算法.在桂林市2015年的新浪微博簽到數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，取得了較好的效果.

2 相關(guān)工作

聚類分析用于在無標(biāo)記的數(shù)據(jù)中挖掘有用的知識(shí)，是很多領(lǐng)域的數(shù)據(jù)分析方法，在位置數(shù)據(jù)中應(yīng)用相對(duì)廣泛的主要是基于距離的聚類，基于密度的聚類和基于網(wǎng)格的聚類.

基于距離的聚類，以距離來度量劃分簇的標(biāo)準(zhǔn)，使得簇內(nèi)的對(duì)象距離較近，各簇之間的距離相對(duì)較遠(yuǎn)，實(shí)現(xiàn)簡(jiǎn)單.K-means算法是最早被提出來的聚類算法，也是基于距離的聚類算法的典型.為提高適應(yīng)性，Dhillon等人將核函數(shù)與K-means算法結(jié)合[17].王波等人在對(duì)簽到數(shù)據(jù)進(jìn)行城市的活動(dòng)時(shí)空變化分析時(shí)，利用K-means算法將南京市區(qū)粗略地劃分為多個(gè)子區(qū)域[18].實(shí)際應(yīng)用中，K值的不確定、無法區(qū)分噪聲和基于距離的方式確定簇，K-means算法常會(huì)導(dǎo)致不合理的聚類結(jié)果.

基于密度的聚類，以數(shù)據(jù)在空間分布上的稠密程度為依據(jù)進(jìn)行聚類，無需設(shè)定簇的數(shù)量，適合未知內(nèi)容的數(shù)據(jù)分析.Ester等人提出了DBSCAN算法，通過半徑和密度閾值來篩選核心點(diǎn)，將密度相連的對(duì)象標(biāo)記為同一個(gè)簇[19].因?yàn)槟馨l(fā)現(xiàn)任意形狀的簇和識(shí)別噪聲點(diǎn)，DBSCAN算法被用于一些位置數(shù)據(jù)的旅游景點(diǎn)提取中[20].但DBSCAN算法對(duì)參數(shù)敏感，不同的密度參數(shù)聚類結(jié)果差異明顯.因其在空間數(shù)據(jù)中表現(xiàn)較好，DBSCAN的研究一直很熱門，在其基礎(chǔ)上提出了大量的改進(jìn)方法[21，22].其中，Kisilevich等人改進(jìn)的P-DBSCAN算法，在Flickr照片數(shù)據(jù)集上能夠更加準(zhǔn)確地挖掘出旅游景點(diǎn)的位置[23].P-DBSCAN算法常被應(yīng)用于含有地理標(biāo)記的Flickr照片數(shù)據(jù)集上進(jìn)行聚類分析和旅游景點(diǎn)提取[24，25]，但它并沒有解決DBSCAN對(duì)參數(shù)敏感的問題.

基于網(wǎng)格的聚類，將數(shù)據(jù)劃分為有限個(gè)網(wǎng)格，所有聚類操作皆以單個(gè)網(wǎng)格為對(duì)象，在高維數(shù)據(jù)和大數(shù)據(jù)量的聚類上表現(xiàn)樂觀.Zhao等人利用網(wǎng)格聚類方法對(duì)采集的芬蘭地區(qū)的GPS位置數(shù)據(jù)進(jìn)行了聚類分析[26].針對(duì)網(wǎng)格大小如何劃分的問題，程國(guó)慶等人提出了網(wǎng)格相對(duì)密度的方法[27].黃紅偉等人提出了利用網(wǎng)格相對(duì)密度差的擴(kuò)展方法[28].改進(jìn)的網(wǎng)格聚類算法雖然在一定程度上為網(wǎng)格的劃分提供了思路，但也引入了其他不易確定的參數(shù).此外，徐正國(guó)等人提出了一種利用簇內(nèi)密度下降搜索的聚類算法，可以比較好地判斷簇的范圍[29].但該算法在計(jì)算局部密度時(shí)依賴截?cái)嗑嚯x，截?cái)嗑嚯x選擇太小，不能很好體現(xiàn)坐標(biāo)點(diǎn)的密度;截?cái)嗑嚯x選擇太大，則會(huì)導(dǎo)致相鄰的簇被合并.在位置數(shù)據(jù)挖掘的應(yīng)用上，Gennip等人利用譜聚類的方法對(duì)洛杉磯的位置數(shù)據(jù)進(jìn)行分析，挖掘幫派團(tuán)體[30].Wang等人提出了一種基于多邊形的聚類和分析框架，挖掘地理空間數(shù)據(jù)的隱藏關(guān)系，對(duì)德克薩斯州臭氧污染進(jìn)行了分析[31].

3 數(shù)據(jù)分析與挑戰(zhàn)

簽到是用戶利用移動(dòng)終端，在發(fā)布微博的同時(shí)定位并顯示其所在位置的行為，詳細(xì)記錄了包括用戶位置信息(經(jīng)緯度坐標(biāo))、時(shí)間信息、文本信息等內(nèi)容.通過調(diào)用新浪微博開放平臺(tái)的API，獲取了覆蓋桂林市2015年1月1日至2015年12月31日的簽到數(shù)據(jù)，經(jīng)過預(yù)處理，共有來自67262名用戶的190584條簽到數(shù)據(jù).每條簽到數(shù)據(jù)包含簽到時(shí)間、用戶名、位置坐標(biāo)、微博內(nèi)容、簽到位置的地點(diǎn)名等信息，如圖1所示.本文算法在聚類時(shí)利用的信息為：位置坐標(biāo)(經(jīng)度，緯度)、用戶名和簽到時(shí)間.地點(diǎn)名用于在聚類結(jié)束后，提取每個(gè)聚類簇在地理上的名字.為更好地理解簽到數(shù)據(jù)與一般聚類對(duì)象的不同，將簽到數(shù)據(jù)的幾個(gè)主要特點(diǎn)分析如下.

圖1 簽到數(shù)據(jù)信息Fig.1 Check-in data information

1)簽到數(shù)據(jù)的分布極不均勻.簽到數(shù)據(jù)往往集中在旅游景點(diǎn)、高校、商場(chǎng)等人流量大的區(qū)域，與其他簽到稀少的區(qū)域形成鮮明對(duì)比;而同屬于旅游景點(diǎn)，由于知名度和位置不同，簽到密集程度也會(huì)相差甚遠(yuǎn).將簽到坐標(biāo)映射到地圖上，每個(gè)點(diǎn)代表一個(gè)簽到位置，高度代表簽到次數(shù).圖2為桂林市中心的簽到分布圖，包含18個(gè)景點(diǎn)，其簽到數(shù)據(jù)比較密集，而且部分位置的簽到次數(shù)較多;圖3為桂林興安縣的簽到分布圖，包含3個(gè)景點(diǎn)，相比較而言，其簽到數(shù)據(jù)明顯稀疏，且在單個(gè)坐標(biāo)點(diǎn)的簽到次數(shù)也明顯減少.雖然同屬于旅游景點(diǎn)，但其簽到數(shù)據(jù)明顯極不均勻.對(duì)于這種極不均勻分布的聚類對(duì)象，基于距離和基于網(wǎng)格的聚類算法會(huì)將市中心位置相鄰的多個(gè)景點(diǎn)聚類為一個(gè)簇，將偏遠(yuǎn)區(qū)域少數(shù)零散的簽到也聚類為一個(gè)簇.

圖2 桂林市中心簽到分布圖Fig.2 Map of check-in data distribution in guilin city center

而基于密度的聚類，若參數(shù)設(shè)置嚴(yán)格，能區(qū)分市中心的各個(gè)景點(diǎn)，卻會(huì)將簽到相對(duì)稀疏的景點(diǎn)當(dāng)作噪聲處理;若參數(shù)設(shè)置寬松，又會(huì)導(dǎo)致簽到密集且位置相鄰的多個(gè)景點(diǎn)被合并為一個(gè)簇，而當(dāng)作一個(gè)景點(diǎn).

2)簽到次數(shù)呈現(xiàn)由中心向周圍遞減的分布.不同于一般的聚類對(duì)象，簽到數(shù)據(jù)存在大量用戶在同一位置簽到的情形.對(duì)于一個(gè)局部區(qū)域，如一個(gè)景點(diǎn)、一條商業(yè)街，會(huì)有一個(gè)位置的簽到次數(shù)特別多，以它為中心距離越遠(yuǎn)的位置，其簽到次數(shù)越少，呈遞減趨勢(shì)，可以抽象為圖4所示.這與微博簽到機(jī)制和用戶簽到方式有關(guān)系，一種情況是用戶使用微博的簽到功能時(shí)手動(dòng)選擇簽到地點(diǎn)，而不是系統(tǒng)通過定位自動(dòng)識(shí)別用戶所在位置，因此該條簽到數(shù)據(jù)的位置坐標(biāo)是由系統(tǒng)根據(jù)用戶手動(dòng)選擇的簽到地點(diǎn)給出的;另一種情況是用戶發(fā)布微博時(shí)上傳了照片，則系統(tǒng)會(huì)根據(jù)識(shí)別出的照片拍攝地點(diǎn)給出簽到位置坐標(biāo).因?yàn)檫@兩種情況，使得局部區(qū)域某個(gè)位置的簽到次數(shù)明顯多于附近的位置.本文提出的算法充分利用了簽到數(shù)據(jù)的這一特點(diǎn)，從而能有效確定簇的邊界.

圖3 興安縣簽到分布圖Fig.3 Map of check-in data distribution in Xing′an County

圖4 簽到數(shù)據(jù)在局部區(qū)域的分布抽象圖Fig.4 Abstract map of check-in data in a local area

3)不同類型用戶簽到次數(shù)差異明顯.一般情況下，游客去外地旅游，一個(gè)地方每年只去一次，而且旅游時(shí)間一般在7天內(nèi)(國(guó)家最長(zhǎng)假期為7天)，本文將數(shù)據(jù)集中最后一次與第一次簽到時(shí)間之差不大于7天的用戶或者只簽到了1次的用戶稱為外地游客，否則稱為當(dāng)?shù)鼐用?本文統(tǒng)計(jì)了最后一次與第一次簽到時(shí)間的間隔天數(shù)與符合條件的用戶數(shù)量.表1列出其中1到12天的結(jié)果，可以觀察到簽到時(shí)間間隔為1天的用戶非常多.這與生活中很多游客去一個(gè)地方旅游，只發(fā)一條微博并簽到相符.隨著時(shí)間間隔的增長(zhǎng)，用戶數(shù)量不斷減少，從7天開始，用戶數(shù)量的變化趨于比較平穩(wěn)的狀態(tài)，這應(yīng)該與隨著假期時(shí)間結(jié)束外地游客離開有直接關(guān)系.對(duì)數(shù)據(jù)集進(jìn)行統(tǒng)計(jì)后還發(fā)現(xiàn)，所有簽到用戶中僅有22.7%為當(dāng)?shù)鼐用瘢浜灥酱螖?shù)卻占總簽到次數(shù)的59.3%.可以看到，當(dāng)?shù)鼐用耠m然不多，但其簽到比例卻很高.現(xiàn)有聚類算法基本都是對(duì)用戶同等看待，不區(qū)分用戶類型，這會(huì)導(dǎo)致當(dāng)?shù)鼐用窈灥捷^多的高校、商場(chǎng)等地方被聚類為簇，而誤認(rèn)為是旅游景點(diǎn).此外，當(dāng)?shù)鼐用裢谛》秶鷧^(qū)域內(nèi)多次簽到，在本文采集到的數(shù)據(jù)中，單一用戶簽到最多達(dá)931次.這有可能導(dǎo)致聚類算法得到的某些簇中簽到次數(shù)很多，但卻只包含少數(shù)幾個(gè)用戶的簽到數(shù)據(jù).本文將外地游客的簽到比例作為局部中心點(diǎn)的選擇條件，只有外地游客簽到占比多的地方才會(huì)判定為局部中心點(diǎn)，很好地避免了上述兩種不合理情況.

表1 時(shí)間間隔天數(shù)及對(duì)應(yīng)的用戶數(shù)量Table 1 Time interval and the corresponding number of users

以上為旅游簽到數(shù)據(jù)相比一般聚類對(duì)象存在的不同特點(diǎn)，利用簽到數(shù)據(jù)挖掘桂林的旅游景點(diǎn)，還存在以下困難：

1)景點(diǎn)位置相鄰.對(duì)于孤立的景點(diǎn)，如銀子巖、世外桃源，容易在聚類時(shí)發(fā)現(xiàn);但是對(duì)于兩個(gè)或者多個(gè)位置相鄰的景點(diǎn)，如象山公園和兩江四湖、大榕樹和聚龍?zhí)叮F(xiàn)有聚類方法必須嚴(yán)格挑選參數(shù)，才能有效區(qū)分，否則容易導(dǎo)致不同景點(diǎn)被聚類為一個(gè)簇，或者某些景點(diǎn)不能被發(fā)現(xiàn).而桂林多數(shù)景點(diǎn)的位置是相鄰的.

2)景點(diǎn)集中在市中心.市中心作為商業(yè)、餐飲和娛樂場(chǎng)所集中的繁華區(qū)域，同時(shí)還分布了18個(gè)旅游景點(diǎn)，流動(dòng)人口多，各種類型的簽到密集分布.如何在簽到密集的市中心區(qū)分旅游景點(diǎn)和非旅游區(qū)域的簽到數(shù)據(jù)，從而挖掘旅游景點(diǎn)的位置，現(xiàn)有算法很難實(shí)現(xiàn).

3)酒店數(shù)量多.作為一個(gè)旅游勝地，桂林擁有不同類型酒店達(dá)2000余家，而且多數(shù)分布在旅游景點(diǎn)附近.不少游客旅行一天后，回到酒店才簽到分享當(dāng)天的旅行體驗(yàn)，這導(dǎo)致酒店簽到數(shù)據(jù)的變化規(guī)律與景點(diǎn)一樣，聚類算法可能會(huì)將簽到次數(shù)多的酒店錯(cuò)誤地判斷為旅游景點(diǎn).

微博簽到數(shù)據(jù)的這些特點(diǎn)使得現(xiàn)有聚類算法很難準(zhǔn)確地挖掘旅游景點(diǎn).本文針對(duì)這些問題，提出了基于局部中心點(diǎn)權(quán)重遞減的聚類算法(local center object weight decreasing based clustering algorithm，CWDC).

4 基于局部中心點(diǎn)權(quán)重遞減的聚類算法

4.1 基本定義

為更好地體現(xiàn)算法的設(shè)計(jì)思路與實(shí)現(xiàn)原理，在描述算法之前，先給出一些基本定義.

定義1. 權(quán)重(Weight)：對(duì)于任意坐標(biāo)點(diǎn)p(lon，lat)，其權(quán)重W(p)是在坐標(biāo)點(diǎn)p的簽到次數(shù).如p點(diǎn)有10條簽到信息，則W(p) = 10.

定義2. 可擴(kuò)展鄰域(Extended Neighborhood)：坐標(biāo)點(diǎn)p(lon，lat)的可擴(kuò)展鄰域E(p)，為p可以向周圍擴(kuò)展的范圍.給定擴(kuò)展半徑R，在數(shù)據(jù)集D上，p的鄰域N(p)由公式(1)表示，其中dis(q，p)為q到p的歐式距離.鄰域內(nèi)權(quán)重大于W(p)的坐標(biāo)點(diǎn)集合H(p)由公式(2)表示，則p的可擴(kuò)展鄰域E(p)可用公式(3)表示，其中WH為H(p)中坐標(biāo)點(diǎn)的權(quán)重之和，WN為N(p)中坐標(biāo)點(diǎn)的權(quán)重之和，λ為容忍度，即能容忍鄰域內(nèi)權(quán)重大于W(p)的坐標(biāo)點(diǎn)的限度.

N(p)={q∈D|dis(q，p)≤R，q≠p}

(1)

H(p)={o∈N(p)|W(o)>W(p)}

(2)

(3)

當(dāng)滿足WH/WN≤ λ的條件時(shí)，p的可擴(kuò)展鄰域就是p的鄰域.當(dāng)鄰域內(nèi)出現(xiàn)個(gè)別權(quán)重小幅增大的坐標(biāo)點(diǎn)時(shí)，容忍度λ可以避免誤認(rèn)為即將進(jìn)入另一個(gè)簇的范圍，而將當(dāng)前坐標(biāo)點(diǎn)作為簇的邊界，從而使簇的范圍界定更加合理.λ的取值對(duì)不同數(shù)據(jù)集不敏感，實(shí)驗(yàn)表明取值在0.1到0.5之間對(duì)聚類結(jié)果影響并不大，以選擇0.3為宜.結(jié)合圖5來理解可擴(kuò)展鄰域，圖中虛線圈出的是一個(gè)簇.當(dāng)一個(gè)點(diǎn)的鄰域內(nèi)坐標(biāo)點(diǎn)的權(quán)重遞減或者保持不變，這個(gè)點(diǎn)才會(huì)有可擴(kuò)展鄰域，如圖5中p1點(diǎn);簇的邊界坐標(biāo)點(diǎn)已經(jīng)沒有可以繼續(xù)擴(kuò)展的坐標(biāo)點(diǎn)，如圖中p2點(diǎn);或者即將進(jìn)入另一個(gè)簇的范圍，權(quán)重呈現(xiàn)遞增趨勢(shì)，不滿足WH/WN≤λ的條件，如圖中p3點(diǎn).因此簇的邊界坐標(biāo)點(diǎn)沒有可擴(kuò)展鄰域.圖中p4點(diǎn)，雖然其權(quán)重為2，鄰域內(nèi)有一個(gè)坐標(biāo)點(diǎn)的權(quán)重為5，但WH/WN=5/18<0.3，所以p4有可擴(kuò)展鄰域，此時(shí)不會(huì)因?yàn)闄?quán)重為5坐標(biāo)的出現(xiàn)而誤將p4點(diǎn)作為簇的邊界.

圖5 可擴(kuò)展鄰域Fig.5 Extended neighborhood

定義3. 坐標(biāo)點(diǎn)p的外地游客簽到比例K(p)：對(duì)于坐標(biāo)點(diǎn)p(lon，lat)，外地游客簽到比例K(p)可用公式(4)表示.其中WT(p)為外地游客在p簽到次數(shù)之和，W(p)為p的權(quán)重.

K(p)=WT(p)/W(p)

(4)

例如：坐標(biāo)點(diǎn)p有10條簽到信息，其中5條是來自外地游客的簽到，則坐標(biāo)點(diǎn)p的外地游客簽到比例K(p)=WT(p)/W(p)=5/10=0.5.

定義4. 外地游客的平均簽到比例α：數(shù)據(jù)集D中外地游客的平均簽到比例α可用公式(5)表示.其中WT為所有外地游客簽到的總次數(shù)，WD為所有用戶簽到的總次數(shù)，也就是數(shù)據(jù)集的大小.

α=WT/WD

(5)

外地游客的平均簽到比例α對(duì)一個(gè)數(shù)據(jù)集來說是固定的，本文數(shù)據(jù)集大小為190584，外地游客簽到總次數(shù)為77567，則α=77567/190584≈0.407.

定義5. 局部中心點(diǎn)(Local Center Object)：局部中心點(diǎn)是滿足K(p)>α且在局部區(qū)域內(nèi)權(quán)重最大的坐標(biāo)點(diǎn).

4.2 算法描述

本文通過定義坐標(biāo)點(diǎn)的權(quán)重和可擴(kuò)展鄰域，并將坐標(biāo)點(diǎn)的用戶和時(shí)間屬性用于局部中心點(diǎn)的選取，設(shè)計(jì)了基于局部中心點(diǎn)權(quán)重遞減的聚類算法，用于利用微博簽到數(shù)據(jù)挖掘旅游景點(diǎn)的位置和流行度.

算法的執(zhí)行過程如算法1所示.第1行首先計(jì)算外地游客的平均簽到比例α;2-7行對(duì)數(shù)據(jù)集D中的所有坐標(biāo)點(diǎn)進(jìn)行遍歷，得到每個(gè)坐標(biāo)點(diǎn)的權(quán)重W(p)、外地游客簽到比例K(p)，去除相同的坐標(biāo)點(diǎn)，組成新的數(shù)據(jù)集D′;8-15行對(duì)數(shù)據(jù)集D′中每個(gè)坐標(biāo)點(diǎn)標(biāo)記為未訪問，并計(jì)算其可擴(kuò)展鄰域E(p);16-28行以滿足K(p) >α且為當(dāng)前未訪問過的權(quán)重最大的坐標(biāo)點(diǎn)為局部中心點(diǎn)建立新簇，按照權(quán)重遞減的思想，迭代地將坐標(biāo)點(diǎn)的可擴(kuò)展鄰域E(p)納入簇內(nèi)，并標(biāo)記為已訪問，以此方式不斷向周圍擴(kuò)展簇的邊界，直到?jīng)]有可擴(kuò)展鄰域時(shí)，結(jié)束擴(kuò)展，確定當(dāng)前簇的邊界.循環(huán)執(zhí)行上述過程，沒有被納入任何簇的坐標(biāo)點(diǎn)則為噪聲數(shù)據(jù).

簇的擴(kuò)展過程可用圖6表示，局部中心點(diǎn)p1首先擴(kuò)展到p2、p3，然后p2迭代地?cái)U(kuò)展到p4、p5，p3迭代地?cái)U(kuò)展到p6、p7.p5由于不滿足WH/WN≤λ的條件，因此沒有可擴(kuò)展鄰域，而結(jié)束擴(kuò)展;p7由于沒有可以繼續(xù)擴(kuò)展的坐標(biāo)點(diǎn)，也沒有可擴(kuò)展鄰域，而結(jié)束擴(kuò)展.p1、p2、p3、p4、p5、p6、p7組成了以p1為局部中心點(diǎn)的簇.

圖6 簇的擴(kuò)展過程Fig.6 Process of cluster expansion

為了排除高校、商場(chǎng)等非旅游區(qū)域，算法在確定局部中心點(diǎn)時(shí)，要求中心點(diǎn)的外地游客簽到比例高于數(shù)據(jù)集中外地游客的平均簽到比例.因?yàn)榉锹糜螀^(qū)域大部分是當(dāng)?shù)鼐用竦暮灥綌?shù)據(jù)，而旅游景點(diǎn)往往外地游客簽到比例更高.

圖7 CWDC聚類結(jié)果示意圖Fig.7 Illustration of CWDC clustering results

若兩個(gè)簇相鄰，從局部中心點(diǎn)以權(quán)重遞減的方式向四周擴(kuò)展簇的范圍，權(quán)重會(huì)呈現(xiàn)遞減趨勢(shì).當(dāng)擴(kuò)展到簇的邊緣區(qū)域，這時(shí)因?yàn)檫吔琰c(diǎn)沒有可擴(kuò)展鄰域而結(jié)束該簇的繼續(xù)擴(kuò)展，不至于將相鄰的簇合并為一個(gè).因此能有效區(qū)分位置相鄰的旅游景點(diǎn)，如圖7所示.

本算法的創(chuàng)新之處在于：(1)提出權(quán)重的概念，使每個(gè)坐標(biāo)點(diǎn)具有權(quán)重，權(quán)重的計(jì)算不需要任何參數(shù);(2)引入坐標(biāo)點(diǎn)的用戶和時(shí)間屬性，與權(quán)重一起確定聚類時(shí)的局部中心點(diǎn);(3)定義可擴(kuò)展鄰域，從局部中心點(diǎn)以權(quán)重遞減的方式擴(kuò)展簇的邊界.

算法1.CWDC算法偽代碼

Input：

D：datasets of points with coordinate，user and time

R：neighborhood radius for extend

Output：Set of cluster

1. Computeα//計(jì)算外地游客的平均簽到比例α

2. For each coordinate pointpinD

3. ComputeW(p) //坐標(biāo)點(diǎn)p的權(quán)重W(p)

4. ComputeK(p) //坐標(biāo)點(diǎn)p的外地游客簽到比例K(p)

5. The same coordinates only keep one //相同坐標(biāo)點(diǎn)只保留一個(gè)

6. End For

7.D′ is a new data set of non-repeating coordinates //D′為去除重復(fù)坐標(biāo)組成的新數(shù)據(jù)集

8. For each coordinate pointPinD′

9. MarkPis unvisited //標(biāo)記P為未訪問

10. ComputeN(P) //N(P)為P的鄰域

11. ComputeH(P) //H(P)為鄰域內(nèi)權(quán)重大于W(P)的坐標(biāo)點(diǎn)集合

12. IfWH/WN≤λ //若滿足條件，建立P的可擴(kuò)展鄰域E(P)

13. Set extended neighborhoodE(P)

14. End If

15. End For

16. For eachPinD′ meetsK(P)>α&&W(P)is maximum of unvisited coordinates //對(duì)每個(gè)局部中心點(diǎn)執(zhí)行

17. MarkPis visited //標(biāo)記P已訪問

18. Create a new clusterC，addPtoC//創(chuàng)建一個(gè)新簇，并將P添加到簇C中

19. For each pointP′ inE(P) //迭代地將可擴(kuò)展鄰域中不屬于任何簇的坐標(biāo)點(diǎn)添加到C

20. IfP′ is unvisited

21. AddP′ toC

22. MarkP′ is visited

23. IfP′ have extended neighborhoodE(P′) //迭代擴(kuò)展

24. Add them toE(P)

25. End If

26. End If

27. End For

28. End For

29. For eachOinD′ is unvisited mark as noise //不屬于任何簇的坐標(biāo)點(diǎn)即為噪聲

30. Output the Set of cluster //輸出聚類結(jié)果

5 實(shí)驗(yàn)與分析

5.1 聚類簇命名

為了計(jì)算各聚類算法從簽到數(shù)據(jù)中挖掘出旅游景點(diǎn)的數(shù)量，聚類結(jié)束后，統(tǒng)計(jì)每個(gè)簇中坐標(biāo)點(diǎn)對(duì)應(yīng)的地點(diǎn)名，以多數(shù)表決的方式，出現(xiàn)次數(shù)最多的地點(diǎn)名作為該簇的名字.

5.2 實(shí)驗(yàn)設(shè)計(jì)與評(píng)價(jià)指標(biāo)

將在位置數(shù)據(jù)聚類分析中經(jīng)常使用的聚類算法K-means、DBSCAN、P-DBSCAN，以及近期由文獻(xiàn)[29]提出的LDCDS作為對(duì)比算法，并在桂林市2015年的新浪微博簽到數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，通過以下4個(gè)評(píng)價(jià)指標(biāo)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行比較，其中前兩個(gè)是結(jié)合應(yīng)用背景由本文提出的，后兩個(gè)是推薦系統(tǒng)中常見的評(píng)價(jià)指標(biāo).

1)景點(diǎn)簇?cái)?shù)量：名字是景點(diǎn)的聚類簇的數(shù)量，該指標(biāo)越大表示越多的聚類簇是景點(diǎn).

2)景點(diǎn)數(shù)量：由于存在地理位置不同的聚類簇，而其名字卻是相同的.比如“漓江”會(huì)至少在兩個(gè)簇的名字中出現(xiàn)，這是因?yàn)椤袄旖笔且粋€(gè)跨度很長(zhǎng)的景點(diǎn)，在不同精華段，游客簽到的地點(diǎn)名都是“漓江”.對(duì)于這種情況，本文視為只挖掘出了一個(gè)景點(diǎn)，用景點(diǎn)數(shù)量表示聚類簇的名字中含有相互不同的景點(diǎn)名數(shù)量，該指標(biāo)越大表示挖掘出的景點(diǎn)越多.

3)準(zhǔn)確率：準(zhǔn)確率=景點(diǎn)簇?cái)?shù)量 / 聚類簇總數(shù)，該指標(biāo)越大表示景點(diǎn)簇?cái)?shù)量占聚類簇總數(shù)的比例越高.

4)覆蓋率：覆蓋率=景點(diǎn)數(shù)量 / 桂林景點(diǎn)總數(shù)，該指標(biāo)越大表示挖掘出的景點(diǎn)數(shù)量占景點(diǎn)總數(shù)的比例越高，將桂林流行度較高的62個(gè)景點(diǎn)作為考慮對(duì)象，設(shè)置景點(diǎn)總數(shù)為62.

5.3 實(shí)驗(yàn)結(jié)果與分析

本文的數(shù)據(jù)集為從新浪微博API接口獲取的2015年1月1日到2015年12月31日桂林市的.各比較算法均選擇最優(yōu)參數(shù)，實(shí)驗(yàn)結(jié)果如表2所示.

表2 不同算法聚類結(jié)果比較Table 2 Clustering results of different algorithms comparison

通過實(shí)驗(yàn)結(jié)果對(duì)比，本文算法CWDC在景點(diǎn)簇?cái)?shù)量、景點(diǎn)數(shù)量、準(zhǔn)確率和覆蓋率四個(gè)指標(biāo)上都優(yōu)于其他算法.因?yàn)樵诰植恐行狞c(diǎn)的選取條件上，綜合考慮了坐標(biāo)點(diǎn)的權(quán)重和外地游客簽到比例，所以本文算法CWDC能排除非旅游區(qū)域，在分布極不均勻的簽到數(shù)據(jù)中準(zhǔn)確定位旅游景點(diǎn)位置;從局部中心點(diǎn)以權(quán)重遞減的方式擴(kuò)展簇的范圍，有效判斷了每個(gè)旅游景點(diǎn)的邊界，可以區(qū)分相鄰的旅游景點(diǎn);此外，在簇從局部中心點(diǎn)向周圍擴(kuò)展的過程中，可擴(kuò)展鄰域避免了權(quán)重小幅度增大的坐標(biāo)點(diǎn)對(duì)簇邊界的干擾，使旅游景點(diǎn)的范圍界定更加合乎現(xiàn)實(shí).正是因?yàn)檫@些原因，而其他聚類算法不能很好地實(shí)現(xiàn)，所以CWDC算法能更加準(zhǔn)確地挖掘出旅游景點(diǎn).

表3 不同算法執(zhí)行時(shí)間比較Table 3 Comparison of different algorithm calculating time

各算法均用C++語言實(shí)現(xiàn)，用Visual Studio2013作為編譯工具.實(shí)驗(yàn)平臺(tái)為Intel Core i5-4460S處理器，8GB內(nèi)存，Windows 7操作系統(tǒng).在算法的執(zhí)行時(shí)間上，K-means能得到快速響應(yīng).因?yàn)镈BSCAN與P-DBSCAN核心點(diǎn)的判斷、LDCDS局部密度的計(jì)算，都需要耗費(fèi)較長(zhǎng)時(shí)間，并將很多時(shí)間浪費(fèi)在了相同坐標(biāo)點(diǎn)的距離計(jì)算上;而CWDC計(jì)算坐標(biāo)點(diǎn)權(quán)重、外地游客簽到比例只需做簡(jiǎn)單的比較，相同的坐標(biāo)只保留一個(gè)，大幅度減少了可擴(kuò)展鄰域部分歐氏距離的計(jì)算量，所以CWDC在計(jì)算時(shí)間方面會(huì)有一定優(yōu)勢(shì)，如表3所示.此外，本文提出的CWDC算法還具有以下幾個(gè)優(yōu)點(diǎn).

1)能準(zhǔn)確定位旅游景點(diǎn)位置.桂林市流行度較高的62個(gè)景點(diǎn)，本文提出的CWDC算法挖掘出了其中52個(gè)，且聚類簇的位置與真實(shí)景點(diǎn)相符，有效排除了市中心簽到密集的非旅游區(qū)域.將CWDC的聚類結(jié)果映射到地圖上，為方便觀察，截取市中心區(qū)域，圖上大面積分布的點(diǎn)是聚類得到的噪聲點(diǎn)，其他標(biāo)識(shí)的是算法判斷的不同景點(diǎn)，如圖8所示.可以看到，算法能在簽到構(gòu)成復(fù)雜、分布密集的市中心區(qū)域，準(zhǔn)確定位旅游景點(diǎn)所在位置，且其中多數(shù)景點(diǎn)相距較近.

圖8 CWDC在桂林市中心挖掘出的旅游景點(diǎn)位置Fig.8 CWDC mining the tourist attractions location in Guilin city center

2)能判斷旅游景點(diǎn)的流行度.簽到越多意味著景點(diǎn)越流行，以簇內(nèi)所有坐標(biāo)點(diǎn)的權(quán)重之和表示流行度，將CWDC發(fā)現(xiàn)的52個(gè)不同的景點(diǎn)按照流行度從高到低排序(如表4所示)，與百度旅游、攜程等旅游網(wǎng)站上桂林市景點(diǎn)排名大致吻合，其中排名前44的景點(diǎn)全部被發(fā)現(xiàn).

值得說明的是，CWDC算法聚類得到的79個(gè)簇中，除了60個(gè)簇是景點(diǎn)，另外19個(gè)簇雖然不是景點(diǎn)，但也是游客常去的地方.這些地方的外地游客簽到比例也高于數(shù)據(jù)集中外地游客的平均簽到比例，具有和景點(diǎn)相同的簽到特征.這19個(gè)簇表示的地點(diǎn)，分別是2個(gè)火車站、1個(gè)汽車站、3個(gè)去景點(diǎn)途中需要經(jīng)過的鄉(xiāng)鎮(zhèn)、2個(gè)特色餐廳(椿記燒鵝、星巴克)和11家桂林人氣最高的五星級(jí)酒店.而其他聚類算法得到的結(jié)果中包含了多個(gè)高校、商場(chǎng)、醫(yī)院等非旅游區(qū)域.

6 結(jié) 論

本文在分析已有聚類算法實(shí)現(xiàn)原理和不足的基礎(chǔ)上，通過定義權(quán)重和可擴(kuò)展鄰域，并將坐標(biāo)點(diǎn)的用戶和時(shí)間屬性引入到局部中心點(diǎn)的選取條件中，提出了一種能在簽到數(shù)據(jù)上有效挖掘旅游景點(diǎn)及其位置、流行度的新聚類算法.算法在確定局部中心點(diǎn)后，以權(quán)重遞減的方式擴(kuò)展簇的邊界.通過在桂林地區(qū)2015年的微博簽到數(shù)據(jù)集上與其他典型聚類算法進(jìn)行對(duì)比實(shí)驗(yàn)，本文提出的基于局部中心點(diǎn)權(quán)重遞減的聚類算法在四個(gè)評(píng)價(jià)指標(biāo)上都優(yōu)于其他算法，表明本文的算法更適合從旅游簽到數(shù)據(jù)中挖掘景點(diǎn)信息.如何將本文算法應(yīng)用于實(shí)時(shí)數(shù)據(jù)中，是下一步研究的重點(diǎn).

表4 CWDC聚類得到的旅游景點(diǎn)流行度排名Table 4 Popularity ranking of tourist attractions clustered by CWDC

：

[1] Wen Yi-min, Shi Yi-fan, Cai Guo-yong, et al. A survey of personalized travel recommendation[EB/OL]. Sciencepaper Online,http://www.paper.edu.cn/releasepaper/content/201407-56,2014.

[2] Yu Z，Xu H，Yang Z，et al.Personalized travel package with multi-point-of-interest recommendation based on crowdsourced user footprints[J].IEEE Transactions on Human-Machine Systems，2016，46(1)：151-158.

[3] Guo L，Shao J，Tan K L，et al.WhereToGo：personalized travel recommendation for individuals and groups[C].Proceedings of the 15th International Conference on Mobile Data Management，IEEE，2014：49-58.

[4] Chen Y Y，Cheng A J，Hsu W H.Travel recommendation by mining people attributes and travel group types from community-contributed photos[J].IEEE Transactions on Multimedia，2013，15(6)：1283-1295.

[5] Wang H，Terrovitis M，Mamoulis N.Location recommendation in location-based social networks using user check-in data[C].Proceedings of the 21st ACM SIGSPA-TIAL International Conference on Advances in Geographic Information Systems，ACM，2013：374-383.

[6] Zheng Y，Zhang L，Xie X，et al.Mining interesting locations and travel sequences from GPS trajectories[C].Proceedings of the 18th International Conference on World Wide Web，ACM，2009：791-800.

[7] Huang Xiao-ting，Ma Xiu-jun.Study on tourists′ rhythm of activities based on GPS data [J].Tourism Tribune，2011，26(12)：26-29.

[8] Hsieh H P，Li C T，Lin S D.Exploiting large-scale check-in data to recommend time-sensitive routes[C].Proceedings of the 14th ACM SIGKDD International Workshop on Urban Computing，ACM，2012：55-62.

[9] Yin H，Zhou X，Shao Y，et al.Joint modeling of user check-in behaviors for point-of-interest recommendation[C].Proceedings of the 24th ACM International Conference on Information and Knowledge Management,ACM，2016：1631-1640.

[10] Song Xiao-yu，Xu Hong-fei，Sun Huang-liang，et al.Short-term experience route based on check-in data[J].Chinese Journal of Computers，2013，36(8)：1693-1703.

[11] Zheng Y T，Zha Z J，Chua T S.Mining travel patterns from geotagged photos[J].ACM Transactions on Intelligent Systems & Technology，2012，3(3)：1-18.

[12] Lim K H.Recommending tours and places-of-interest based on user interests from geotagged photos[C].Proceedings of the 2015,ACM SIGMOD on PhD Symposium,ACM，2015：33-38.

[13] Kurashima T，Iwata T，Irie G，et al.Travel route recommendation using geotags in photo sharing sites[C].Proceedings of the 19th ACM International Conference on Information and Knowledge Management，ACM，2010：579-588.

[14] Majid A，Chen L，Chen G，et al.GoThere：travel suggestions using geotagged photos [C].Proceedings of the 21st International Conference on World Wide Web，ACM，2012：577-578.

[15] Zhang Zi-ang，Huang Zhen-fang，Jin Cheng，et al.Research on spatial-temporal characteristics scenic tourist activity based on sina microblog：a case study of nanjing zhongshan mountain national park[J].Geography and Geoinformation Science，2015，31(4)：121-126.

[16] Han Hua-rui，Dai Zhen-yong.The analysis of space difference of check-in activities in hubei province：an expirical analysis of sina micro-blog[J].Geomatics & Spatial Information Technology，2016，39(10)：159-162.

[17] Dhillon I S，Guan Y，Kulis B.Kernel k-means：spectral clustering and normalized cuts[C].Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,ACM，2004：551-556.

[18] Wang Bo，Zhen Feng，Zhang Hao.Dynamics changes of urban space-time activity and activity zoning based on check-in data in sina Web[J].Scientia Geographica Sinica，2015，35(2)：151-160.

[19] Ester M，Kriegel H P，Sander J，et al.A density-based algorithm for discovering clusters in large spatial databases with noise[C].Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining,ACM，1996：226-231.

[20] Memon I，Chen L，Majid A，et al.Travel recommendation using Geo-tagged photos in social media for tourist[J].Wireless Personal Communications，2015，80 (4)：1347-1362.

[21] Feng Zhen-hua，Qian Xue-zhong，Zhao Na-na.Greedy DBSCAN：an inproved DBSCAN algorithm on multi-density clustering[J].Application Research of Computers，2016，33(9)：2693-2696.

[22] Birant D，Kut A.ST-DBSCAN：an algorithm for clustering spatial-temporal data[J].Data & Knowledge Engineering，2007，60(1)：208-221.

[23] Kisilevich S，Mansmann F，Keim D.P-DBSCAN：a density based clustering algorithm for exploration and analy sis of attractive areas using collections of geotagged photos[C].Proceedings of the 1st International Conference and Exhibition on Computing for Geospatial Research & Application,ACM，2010：38：1-38：4.

[24] Vu H Q，Gang L，Law R，et al.Exploring the travel behaviors of inbound tourists to Hong Kong using geotagged photos[J].Tourism Management，2015，46(1)：222-232.

[25] Majid A，Chen L，Mirza H T，et al.A system for mining interesting tourist locations and travel sequences from public geotagged photos[J].Data & Knowledge Engineering，2015，95(1)：66-86.

[26] Zhao Q，Shi Y，Liu Q，et al.A gridgrowing clustering algorithm for geospatial data[J].Pattern Recognition Letters，2015，53(53)：77-84.

[27] Cheng Guo-qing，Chen Xiao-yun.Clustering algorithm for multi-density based on grid relative density[J].Computer Engineering and Applications，2009，45(1)：156-158.

[28] Huang Hong-wei，Huang Tian-min.Extension clustering algorithm based on relative grid density difference[J].Application Research of Computers，2014，31(6)：1702-1705.

[29] Xu Zheng-guo，Zheng Hui，He Liang，et al.Self-adaptive clustering based on local density by descending search [J].Journal of Computer Research and Development，2016，53(8)：1719-1728.

[30] Gennip Y V，Hunter B，Ahn R，et al.Community detection using spectral custering on sparse geosocial data[J].Siam Journal on Applied Mathematics，2012，73(1)：67-83.

[31] Wang S，Eick C F.A polygon-based clustering and analysis framework for mining spatial datasets[J].GeoInformatica，2014，18(3)：569-594.

附中文參考文獻(xiàn)：

[1] 文益民,史一帆,蔡國(guó)永,等.個(gè)性化旅游推薦研究綜述[EB/OL].中國(guó)科技論文在線,http://www.paper.edu.cn/releasepaper/content/201407-56,2014.

[7] 黃瀟婷，馬修軍.基于GPS數(shù)據(jù)的旅游者活動(dòng)節(jié)奏研究[J].旅游學(xué)刊，2011，26(12)：26-29.

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

[15] 張子昂，黃震方，靳 誠，等.基于微博簽到數(shù)據(jù)的景區(qū)旅游活動(dòng)時(shí)空行為特征研究——以南京鐘山風(fēng)景名勝區(qū)為例[J].地理與地理信息科學(xué)，2015，31(4)：121-126.

[16] 韓華瑞，代偵勇.湖北省微博簽到活動(dòng)空間差異分析——以新浪微博為例[J].測(cè)繪與空間地理信息，2016，39(10)：159-162.

[18] 王 波，甄 峰，張 浩.基于簽到數(shù)據(jù)的城市活動(dòng)時(shí)空間動(dòng)態(tài)變化及區(qū)劃研究[J].地理科學(xué)，2015，35(2)：151-160.

[21] 馮振華，錢雪忠，趙娜娜.Greedy DBSCAN：一種針對(duì)多密度聚類的DBSCAN改進(jìn)算法[J].計(jì)算機(jī)應(yīng)用研究，2016，33(9)：2693-2696.

[27] 程國(guó)慶，陳曉云.基于網(wǎng)格相對(duì)密度的多密度聚類算法[J].計(jì)算機(jī)工程與應(yīng)用，2009，45(1)：156-158.

[28] 黃紅偉，黃天民.基于網(wǎng)格相對(duì)密度差的擴(kuò)展聚類算法[J].計(jì)算機(jī)應(yīng)用研究，2014，31(6)：1702-1705.

[29] 徐正國(guó)，鄭 輝，賀 亮，等.基于局部密度下降搜索的自適應(yīng)聚類方法[J].計(jì)算機(jī)研究與發(fā)展，2016，53(8)：1719-1728.