基于改進(jìn)密度聚類算法的中國城市旅游活躍度分析

陳佳輝 朱蓉 黃謙 陳鵬飛 曹鈺鋼

摘要：近年來隨著信息技術(shù)的迅速發(fā)展，人們通常會在圖像共享網(wǎng)站上上傳自己旅游時所拍攝的照片。如果我們能對這些照片進(jìn)行地點和數(shù)量上的提取和分析，就可以得到我國各個城市旅游活躍度。本文用基于OPTICS的聚類算法對Flickr網(wǎng)站上的照片進(jìn)行了聚類分析，從而得到我國城市旅游活躍度。并且通過可視化軟件將實驗數(shù)據(jù)可視化，對本文實驗結(jié)果加以驗證。城市旅游活躍度可用于一些旅游目的地推薦，旅游路線安排等。

關(guān)鍵詞：OPTICS聚類算法；可視化；數(shù)據(jù)分析；地理位置

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）22-0265-05

Abstract：With the rapid development of information technology in recent years， people usually upload photos taken while traveling on the image sharing website. If we can extract and analyze the location and quantity of these photos， we can get the tourism activity of each city in our country. In this paper， the clustering algorithm based on OPTICS is used to cluster the photos on Flickr website to get the city tourism activity in our country. Visualization of the experimental data by visualization software and verification of the experimental results in this paper. City tourism activity can be used for some tourist destination recommendations， travel routes and so on.

Key words： OPTICS clustering algorithm；visualization；data analysis.

近年來，百度、騰訊等紛紛開放網(wǎng)絡(luò)應(yīng)用平臺，應(yīng)用平臺提供資源共享，資源共建等服務(wù)，在一定程度上加快了資訊的傳播速度，擴(kuò)充了用戶數(shù)據(jù)。與此同時，智能手機(jī)的快速普及，推動中國進(jìn)入移動互聯(lián)網(wǎng)時代。截至2016年12月，全球網(wǎng)民已達(dá)30億，占42%的全球人口，其中：中國有7.31億，而且這個數(shù)量呈上升趨勢。智能手機(jī)、平板等新型網(wǎng)絡(luò)載體也在全球爆發(fā)出極大的生命力。截至2016年，中國境內(nèi)活躍的智能手機(jī)達(dá)23.3億部，根據(jù)eMarketer預(yù)測，2018年中國智能手機(jī)用戶將占總?cè)丝诘?9.1%[1] 。智能手機(jī)的普及使得人們脫離網(wǎng)線的束縛，隨時隨地都可以訪問網(wǎng)絡(luò)資源，很顯然，移動互聯(lián)網(wǎng)時代的蓬勃發(fā)展，帶來了海量的數(shù)據(jù)，未來的數(shù)據(jù)更將呈爆發(fā)式增長。因此，如何從海量數(shù)據(jù)中挖掘出有用的信息成為當(dāng)下數(shù)據(jù)挖掘、用戶行為分析等研究領(lǐng)域的一個熱門話題。

當(dāng)前，一些網(wǎng)絡(luò)應(yīng)用平臺，例如：Flickr上匯集了數(shù)量龐大的有關(guān)風(fēng)景名勝點的照片、描述以及評價供人們共享，如圖1、圖2所示。這些信息在人們獲取旅游信息的過程中越來越受到關(guān)注，已成為用戶選擇旅游目的地的一個重要的參考因素。

因而，如何有效挖掘網(wǎng)絡(luò)應(yīng)用平臺中的海量數(shù)據(jù)信息繼而為人們的生活提供便利，如今已越來越受到研究者的關(guān)注。例如：Naaman等人[2]開發(fā)了PhotoCompas系統(tǒng)，它試圖通過位置和事件分層建立相冊，以便高效地搜索和瀏覽在特定事件和位置上的照片；聶雷剛等人[3]采用一種改進(jìn)的密度算法，在不同地區(qū)有針對性地以不同的搜索半徑搜索附近滿足要求的景點，為游客提供一種最優(yōu)的旅游規(guī)劃。何奇彥[4]利用稀疏分量方法設(shè)計了基于子空間的聚類算法，實現(xiàn)了對旅游信息資源的利用與共享。例如：薛玉霞[5]對圖片共享網(wǎng)站上的旅游目的地信息進(jìn)行收集分析，有針對性地建立旅游目的地的形象模型；Xu等人[6]通過對圖片共享網(wǎng)站上用戶上傳的照片和日志進(jìn)行分析，為用戶提供個性化的旅游推薦。由此可見，近年來，關(guān)于幫助用戶進(jìn)行旅游目的地的規(guī)劃越來越受到重視。

聚類分析在許多領(lǐng)域受到廣泛應(yīng)用，包括機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、模式識別、圖像分析以及生物信息處理[7]。目前，有許多研究者將聚類算法應(yīng)用到用戶行為分析領(lǐng)域中。

例如：陳吉順[8]研究了聚類分析在云南旅游數(shù)據(jù)挖掘中的應(yīng)用，對云南省部分區(qū)域的旅游工作給出了指導(dǎo)性建議；呂威等人[9]提出了基于等距加密和案例推理的旅游線路聚類算法，能夠為旅游者推薦合適的旅游線路?；诿芏鹊木垲愃惴ㄊ蔷垲惙治鲋袨榱藢ふ冶坏兔芏葏^(qū)域分離的高密度區(qū)域而產(chǎn)生的。本文將利用密度聚類算法對來自網(wǎng)絡(luò)應(yīng)用平臺上的數(shù)據(jù)，特別是Flickr上的數(shù)據(jù)進(jìn)行處理，并試圖給出中國城市的旅游活躍度等級。這里需要特別說明的是：本文不針對照片本身的內(nèi)容和用戶給出的評論進(jìn)行分析，僅利用照片數(shù)量以及地理位置等信息，以此來得到更加精細(xì)化的分析結(jié)果，同樣適合于更小的區(qū)域，也可以擴(kuò)大到一個國家。

1 密度聚類算法（OPTICS）

OPTICS （Ordering Points To Identify the Clustering Structure）算法[5]是由DBScan算法發(fā)展而來的一種密度聚類算法。密度聚類的核心思想是用一個點的ε鄰域內(nèi)的鄰居點數(shù)衡量該點所在空間的密度。如果ε鄰域內(nèi)的鄰居點數(shù)超過了某個指定閾值 MinPts，則認(rèn)為該點處于某個簇內(nèi)，稱為核心點（core-point）；否則，認(rèn)為該點處于某個簇的邊界上，稱為邊界點（bounder-point）。下面給出一些相關(guān)定義：

定義1 直接密度可達(dá)（directly density-reachable）如果樣本點p 是核心點，樣本點 q 在 p 的ε鄰域內(nèi)，則 p 直接密度可達(dá)q。

定義2 密度可達(dá)（density-reachable）如果存在序列p1 ， …， pn，其中： p1 =p ， pn =q ，并且對于任意 1≤i

定義3 密度相連（density-connected ）如果樣本點o 密度可達(dá)樣本點p ， 且 o 密度可達(dá)樣本點q ， 則 p 和 q密度相連。

由圖3可知三者之間的關(guān)系[6]：密度可達(dá)是直接密度可達(dá)的傳遞；密度相連則是從同一點密度可達(dá)的任意兩點的對稱關(guān)系。如果從某個選定的核心點出發(fā)，不斷向密度可達(dá)的區(qū)域擴(kuò)張，將得到一個包括核心點和邊界點的最大化區(qū)域，，區(qū)域中任意兩點密度相連，這即為一個聚類簇。 DBScan 算法就是通過上述過程搜索和提取尺度為ε的所有簇。為了具備更為精細(xì)的刻畫能力， OPTICS算法引入了核心距離和可達(dá)距離的概念。

可見，核心距離是一個點成為核心點的最小鄰域半徑。

可見，p 與o 相關(guān)的可達(dá)距離即是從 o 直接密度可達(dá) p 的最小距離，該距離與空間密度直接相關(guān)。如果該點的所在空間密度大，它從相鄰點直接密度可達(dá)的距離就?。环粗嗳?。因此，若朝著數(shù)據(jù)盡量稠密的空間進(jìn)行擴(kuò)張， 那么可達(dá)距離最小的點就是最佳的選擇。

OPTICS算法具體過程如下：

輸入：數(shù)據(jù)樣本D，最少點數(shù)MinPts和半徑ε。

步驟1：初始化所有點的核心距離和可達(dá)距離并建立兩個隊列：有序隊列（核心點及該核心點的直接密度可達(dá)點）和結(jié)果隊列（存儲樣本輸出及處理次序）；

步驟2：如果D中數(shù)據(jù)全部處理完，則算法結(jié)束；否則，從D中選擇一個未處理的核心點，將該核心點放入結(jié)果隊列，該核心點的直接密度可達(dá)點放入有序隊列，直接密度可達(dá)點按可達(dá)距離升序排列；

步驟3：如果有序序列為空，則回到步驟2，否則從有序隊列中取出第一個點；

步驟3.1 判斷該點是否為核心點，不是則回到步驟3；若是則將該點存入結(jié)果隊列（如果該點不在結(jié)果隊列）；

步驟3.2 若該點是核心點，則找到其所有直接密度可達(dá)點，并將這些點放入有序隊列，并將有序隊列中的點按照可達(dá)距離重新排序，如果該點已經(jīng)在有序隊列中且新的可達(dá)距離較小，則更新該點的可達(dá)距離；

步驟3.3 重復(fù)步驟3，直至有序隊列為空。

步驟4：算法結(jié)束。

輸出：根據(jù)結(jié)果隊列中的處理次序輸出可達(dá)距離矩陣rd。

2 基于加權(quán)OPTICS的城市旅游活躍度分析方法

基于傳統(tǒng)OPTICS的城市旅游活躍度分析，是根據(jù)某個城市位置點信息密集程度，旅游活躍度高低。既位置點密集，旅游活躍度高，位置點稀疏，旅游活躍度低。然而，通常網(wǎng)絡(luò)應(yīng)用平臺上除了提供位置點信息以外，還包含各個位置點上傳照片的數(shù)量信息，而這些照片數(shù)量的信息對于旅游目的地的活躍度分析具有重要的應(yīng)用價值。顯然，由于 傳統(tǒng) OPTICS算法具有自身的局限性，其只能對出現(xiàn)數(shù)據(jù)的位置點進(jìn)行密度上的分析，不適合實際需求。

如圖4所示，如果直接使用傳統(tǒng)OPTICS算法對A、B兩個城市進(jìn)行密度上的分析，A城市中位置點更密集，得出的結(jié)論必然是A城市的旅游活躍度高于B城市。但從圖4中又可見，假設(shè)A市所有位置點中的照片數(shù)量和為a，B市所有位置點中的照片數(shù)量和為b，若b>>a，則B市的旅游活躍度應(yīng)高于A市。

針對這一不足，本文對原有OPTICS算法進(jìn)行了改進(jìn)，提出一種基于加權(quán)OPTICS的城市旅游活躍度分析方法。

首先，利用基本的OPTICS算法得到各個樣本點核心距離（core-distance）和可達(dá)距離（reachability-distance）；然后，計算核心距離的平均值A(chǔ)verage（core-distance）和可達(dá)距離的平均值A(chǔ)verage（reachability-distance）。由于，核心距離（core-distance）越小，表明該地區(qū)的密集程度越高，因而我們在改進(jìn)算法中采用的倒數(shù)（即核心距離（core-distance）的倒數(shù)越大，表明該地區(qū)的密集程度越高）。最后，在針對位置點照片數(shù)量的處理中，我們將照片數(shù)量與可達(dá)距離的平均值A(chǔ)verage（reachability-distance）相除，以獲取某個地區(qū)照片數(shù)量的平均值?？紤]到某個地區(qū)的照片數(shù)量的多少更能體現(xiàn)出該地區(qū)的旅游活躍程度，因而，本文中城市旅游活躍度的值 來源于兩個方面，位置點的密集程度 位置點照片數(shù)量的權(quán)值，在這里，我們將因此，在這里我們將位置點的密集程度的權(quán)值設(shè)置為0.4，位置點上的照片數(shù)量的權(quán)值設(shè)置為0.6。

通過該改進(jìn)算法我們可以得到如下結(jié)論：公式4中H的值越大，該地區(qū)的旅游活躍度就越高。

3 實驗結(jié)果及分析

3.1 Flickr網(wǎng)站

Flickr，雅虎旗下圖片分享網(wǎng)站。為一家提供免費及付費數(shù)位照片儲存、分享方案之線上服務(wù)，也提供網(wǎng)絡(luò)社群服務(wù)的平臺。Flickr集合了借由使用者間的關(guān)系而相互連接的數(shù)位影像，影像可依其內(nèi)容彼此產(chǎn)生關(guān)聯(lián)。圖片上傳者可自己定義該相片的關(guān)鍵字，也就是“標(biāo)簽（Tags）”（是元資料（Metadata）的一種格式），如此一來搜尋者可以很快的找到想要的相片，例如指定拍攝地點或照片的主題，而創(chuàng)作者也能很快了解相同標(biāo)簽（Tags）下有哪些由其他人所分享的照片，F(xiàn)lickr也會挑選出最受歡迎的標(biāo)簽名單，縮短搜尋相片的時間。

3.2 實驗數(shù)據(jù)獲取

Flickr對研究者們提供了官方API，可通過https：//www.flickr.com/services/api/獲取API，具體步驟如下：

第一步：請求API密鑰（key），簽上API請求。

第二步：閱讀社區(qū)準(zhǔn)則和使用的API條款。

第三步：建置和測試。

通過獲取的API以及我國主要城市的WOEID本文得到了查詢數(shù)據(jù)的url： https：//api.flickr.com/services/rest/？&method;=flickr.places.getChildrenWithPhotosPublic&api;_key=4546584af 9f2b266fa311357cff1701b&format;=json&woe;_id=（要查詢的位置）。再通過這個API 獲得我國主要城市在Flickr網(wǎng)站中的精度，維度以及該區(qū)域上傳照片的數(shù)量。

例如：上海的WOEID為12578012通過URL：https：//api.flickr.com/services/rest/？&method;=flickr.places.getChildrenWithPhotosPublic&api;_key=4546584af9f2b266fa311357cff1701b&format;=json&woe;_id=12578012

可以獲得上海區(qū)域的精度維度和上傳照片數(shù)量（精度：121.472， 緯度：31.247，照片數(shù)量：525788）如圖5所示。

3.3 實驗結(jié)果

首先利用本文中提出的基于加權(quán)的OPTICS算法對使用WOEID獲得的3012個地區(qū)的經(jīng)緯度進(jìn)行了分析，得到了每個點的可達(dá)距離和核心距離，示意圖如圖7、圖8所示：

再利用加權(quán)的OPTICS算法對所得的3012個地區(qū)的圖片數(shù)量進(jìn)行處理，便獲得了各地區(qū)的旅游活躍度。如圖9所示：

根據(jù)核心距離圖可知每個凹的區(qū)域可以看成一個聚類，且該區(qū)域中的地點密度較為密集，例如：天津，上海，?？?，昆明，廣東等地方。如圖9所示。本文將地區(qū)活躍度分為5級：

5級為旅游活躍度高于5萬的地區(qū)。如：北京，上海，天津，香港（九龍，觀塘，灣仔，油尖旺）。

4級為旅游活躍度高于3萬且低于5萬的地區(qū)。如：重慶，大連。

3級為旅游活躍度高于1萬且低于3萬的地區(qū)。如：陜西（長安，席王），山西（東社，新城）。

2級為旅游活躍度高于7950且低于1萬的地區(qū)。如：安徽，吉林。

1級為所剩的地區(qū)。

4 可視化

為了給出更直觀的實驗結(jié)果，本文針對“http：//echarts.baidu.com/gallery/editor.html？c=scatter-map”將前面得到的3012個地區(qū)的信息放入，實現(xiàn)對數(shù)據(jù)的可視化顯示。鼠標(biāo)移動至數(shù)據(jù)點會出現(xiàn)類似99：1這樣的數(shù)據(jù)，冒號前的是位置代碼，后者為該地點照片總數(shù)。如圖10所示，左下角為照片數(shù)量的范圍，若該地區(qū)照片數(shù)量在此范圍中則會在圖中顯示。

本文基于改進(jìn)的OPTICS算法獲得實驗結(jié)果，對網(wǎng)絡(luò)用戶分布密度進(jìn)行了分析，并得出用戶的活躍度等級。然后將活躍度分析、可視化圖像及中國入境旅游時空地域分析結(jié)果三者進(jìn)行綜合分析，推導(dǎo)出網(wǎng)絡(luò)用戶的分布以及發(fā)展走向：

上傳照片的中國網(wǎng)民分布也是成聚類分布，以北京，上海，?？冢愀?，臺北市為中心向周圍進(jìn)行發(fā)散，分布十分密集，且活躍度極高，形成一個個大聚類，中心都是一級活躍度，周邊二級，三級緊密相連，從圖11中可見。以杭州，廣州，南京，重慶，福建為小中心，周邊有一定的分布密度，周邊活躍度相對于中心低得多，以蘇州，青島，拉薩，桂林，重慶，麗江為中心的極小聚類分布，特點中心點活躍度高，達(dá)活躍度二級，周邊活躍度大多都是五級，極少的四級。其余地區(qū)拉薩，桂林，哈爾濱顯得孤立，單獨的活躍度達(dá)三級，甚至部分地區(qū)達(dá)2級，但周邊都是活躍度為五級的，并且密度極低。其余的零散分布，不成聚類，并且活躍度都是五級，極少出現(xiàn)四級情況。

參考文獻(xiàn)：

[1] http：//www.199it.com/archives/316361.html.

[2] Dhiraj J.， Andrew G.， Jie Y.， Jiebo L. Inferring photographic location using geotagged web images [J].Multimed Tools Appl， 2012， 56： 131-153.

[3] 聶雷剛，李詠梅，余元輝.基于聚類分析算法的智能旅游規(guī)劃[J]. 電腦開發(fā)與應(yīng)用，2012（2）28-30.

[4] 何奇彥.基于稀疏聚類算法的關(guān)中地區(qū)旅游信息資源共享研究[J]. 自動化與儀器儀表，2017（2）116-118.

[5] 薛玉霞.基于圖片共享網(wǎng)絡(luò)的旅游目的地形象傳播策略[D].四川：電子科技大學(xué)，2013.

[6] Zhenxing Xu，Ling Chen，Haodong Guo etal.User Similarity based Gender-Aware Travel Location Recommendation by Mining Geotagged Photos[C].

[7] https：//zh.wikipedia.org/wiki/%E8%81%9A%E7%B1%BB%E5%88%86%E6%9E%90.

[8] 陳吉順.模糊聚類分析在云南旅游數(shù)據(jù)挖掘中的研究及應(yīng)用[D].云南大學(xué)，2006.

[9] 呂威，倪玉華.基于等距加密和案例推理的旅游線路聚類算法[J].計算機(jī)工程與應(yīng)用，2010，46（11）：223-225，239.

[10] Smile_tina.OpticsMatlab[EB/OL]http：//www.cnblogs.com/tina-smile/archive/2014/01/06/3507627.html.2014（1）.

[11] 李創(chuàng)新，馬耀峰，王永明.1993-2012年中國入境旅游時空地域格局分異與動態(tài)演進(jìn)——基于全局K-Means譜聚類法的“典型區(qū)域”實證研究[J].資源科學(xué)，2015（11）.

【通聯(lián)編輯：唐一東】