基于改进密度聚类算法的中国城市旅游活跃度分析

陈佳辉 朱蓉 黄谦 陈鹏飞 曹钰钢

摘要：近年来随着信息技术的迅速发展，人们通常会在图像共享网站上上传自己旅游时所拍摄的照片。如果我们能对这些照片进行地点和数量上的提取和分析，就可以得到我国各个城市旅游活跃度。本文用基于OPTICS的聚类算法对Flickr网站上的照片进行了聚类分析，从而得到我国城市旅游活跃度。并且通過可视化软件将实验数据可视化，对本文实验结果加以验证。城市旅游活跃度可用于一些旅游目的地推荐，旅游路线安排等。

关键词：OPTICS聚类算法；可视化；数据分析；地理位置

中图分类号：TP393 文献标识码：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.

近年来，百度、腾讯等纷纷开放网络应用平台，应用平台提供资源共享，资源共建等服务，在一定程度上加快了资讯的传播速度，扩充了用户数据。与此同时，智能手机的快速普及，推动中国进入移动互联网时代。截至2016年12月，全球网民已达30亿，占42%的全球人口，其中：中国有7.31亿，而且这个数量呈上升趋势。智能手机、平板等新型网络载体也在全球爆发出极大的生命力。截至2016年，中国境内活跃的智能手机达23.3亿部，根据eMarketer预测，2018年中国智能手机用户将占总人口的49.1%[1] 。智能手机的普及使得人们脱离网线的束缚，随时随地都可以访问网络资源，很显然，移动互联网时代的蓬勃发展，带来了海量的数据，未来的数据更将呈爆发式增长。因此，如何从海量数据中挖掘出有用的信息成为当下数据挖掘、用户行为分析等研究领域的一个热门话题。

当前，一些网络应用平台，例如：Flickr上汇集了数量庞大的有关风景名胜点的照片、描述以及评价供人们共享，如图1、图2所示。这些信息在人们获取旅游信息的过程中越来越受到关注，已成为用户选择旅游目的地的一个重要的参考因素。

因而，如何有效挖掘网络应用平台中的海量数据信息继而为人们的生活提供便利，如今已越来越受到研究者的关注。例如：Naaman等人[2]开发了PhotoCompas系统，它试图通过位置和事件分层建立相册，以便高效地搜索和浏览在特定事件和位置上的照片；聂雷刚等人[3]采用一种改进的密度算法，在不同地区有针对性地以不同的搜索半径搜索附近满足要求的景点，为游客提供一种最优的旅游规划。何奇彦[4]利用稀疏分量方法设计了基于子空间的聚类算法，实现了对旅游信息资源的利用与共享。例如：薛玉霞[5]对图片共享网站上的旅游目的地信息进行收集分析，有针对性地建立旅游目的地的形象模型；Xu等人[6]通过对图片共享网站上用户上传的照片和日志进行分析，为用户提供个性化的旅游推荐。由此可见，近年来，关于帮助用户进行旅游目的地的规划越来越受到重视。

聚类分析在许多领域受到广泛应用，包括机器学习、数据挖掘、模式识别、图像分析以及生物信息处理[7]。目前，有许多研究者将聚类算法应用到用户行为分析领域中。

例如：陈吉顺[8]研究了聚类分析在云南旅游数据挖掘中的应用，对云南省部分区域的旅游工作给出了指导性建议；吕威等人[9]提出了基于等距加密和案例推理的旅游线路聚类算法，能够为旅游者推荐合适的旅游线路。基于密度的聚类算法是聚类分析中为了寻找被低密度区域分离的高密度区域而产生的。本文将利用密度聚类算法对来自网络应用平台上的数据，特别是Flickr上的数据进行处理，并试图给出中国城市的旅游活跃度等级。这里需要特别说明的是：本文不针对照片本身的内容和用户给出的评论进行分析，仅利用照片数量以及地理位置等信息，以此来得到更加精细化的分析结果，同样适合于更小的区域，也可以扩大到一个国家。

1 密度聚类算法（OPTICS）

OPTICS （Ordering Points To Identify the Clustering Structure）算法[5]是由DBScan算法发展而来的一种密度聚类算法。密度聚类的核心思想是用一个点的ε邻域内的邻居点数衡量该点所在空间的密度。如果ε邻域内的邻居点数超过了某个指定阈值 MinPts，则认为该点处于某个簇内，称为核心点（core-point）；否则，认为该点处于某个簇的边界上，称为边界点（bounder-point）。下面给出一些相关定义：

定义1 直接密度可达（directly density-reachable）如果样本点p 是核心点，样本点 q 在 p 的ε邻域内，则 p 直接密度可达q。

定义2 密度可达（density-reachable）如果存在序列p1 ， …， pn，其中： p1 =p ， pn =q ，并且对于任意 1≤i

定义3 密度相连（density-connected ）如果样本点o 密度可达样本点p ， 且 o 密度可达样本点q ， 则 p 和 q密度相连。

由图3可知三者之间的关系[6]：密度可达是直接密度可达的传递；密度相连则是从同一点密度可达的任意两点的对称关系。如果从某个选定的核心点出发，不断向密度可达的区域扩张，将得到一个包括核心点和边界点的最大化区域，，区域中任意两点密度相连，这即为一个聚类簇。 DBScan 算法就是通过上述过程搜索和提取尺度为ε的所有簇。为了具备更为精细的刻画能力， OPTICS算法引入了核心距离和可达距离的概念。

可见，核心距离是一个点成为核心点的最小邻域半径。

可见，p 与o 相关的可达距离即是从 o 直接密度可达 p 的最小距离，该距离与空间密度直接相关。如果该点的所在空间密度大，它从相邻点直接密度可达的距离就小；反之亦然。因此，若朝着数据尽量稠密的空间进行扩张， 那么可达距离最小的点就是最佳的选择。

OPTICS算法具体过程如下：

输入：数据样本D，最少点数MinPts和半径ε。

步骤1：初始化所有点的核心距离和可达距离并建立两个队列：有序队列（核心点及该核心点的直接密度可达点）和结果队列（存储样本输出及处理次序）；

步骤2：如果D中数据全部处理完，则算法结束；否则，从D中选择一个未处理的核心点，将该核心点放入结果队列，该核心点的直接密度可达点放入有序队列，直接密度可达点按可达距离升序排列；

步骤3：如果有序序列为空，则回到步骤2，否则从有序队列中取出第一个点；

步骤3.1 判断该点是否为核心点，不是则回到步骤3；若是则将该点存入结果队列（如果该点不在结果队列）；

步骤3.2 若该点是核心点，则找到其所有直接密度可达点，并将这些点放入有序队列，并将有序队列中的点按照可达距离重新排序，如果該点已经在有序队列中且新的可达距离较小，则更新该点的可达距离；

步骤3.3 重复步骤3，直至有序队列为空。

步骤4：算法结束。

输出：根据结果队列中的处理次序输出可达距离矩阵rd。

2 基于加权OPTICS的城市旅游活跃度分析方法

基于传统OPTICS的城市旅游活跃度分析，是根据某个城市位置点信息密集程度，旅游活跃度高低。既位置点密集，旅游活跃度高，位置点稀疏，旅游活跃度低。然而，通常网络应用平台上除了提供位置点信息以外，还包含各个位置点上传照片的数量信息，而这些照片数量的信息对于旅游目的地的活跃度分析具有重要的应用价值。显然，由于 传统 OPTICS算法具有自身的局限性，其只能对出现数据的位置点进行密度上的分析，不适合实际需求。

如图4所示，如果直接使用传统OPTICS算法对A、B两个城市进行密度上的分析，A城市中位置点更密集，得出的结论必然是A城市的旅游活跃度高于B城市。但从图4中又可见，假设A市所有位置点中的照片数量和为a，B市所有位置点中的照片数量和为b，若b>>a，则B市的旅游活跃度应高于A市。

针对这一不足，本文对原有OPTICS算法进行了改进，提出一种基于加权OPTICS的城市旅游活跃度分析方法。

首先，利用基本的OPTICS算法得到各个样本点核心距离（core-distance）和可达距离（reachability-distance）；然后，计算核心距离的平均值Average（core-distance）和可达距离的平均值Average（reachability-distance）。由于，核心距离（core-distance）越小，表明该地区的密集程度越高，因而我们在改进算法中采用的倒数（即核心距离（core-distance）的倒数越大，表明该地区的密集程度越高）。最后，在针对位置点照片数量的处理中，我们将照片数量与可达距离的平均值Average（reachability-distance）相除，以获取某个地区照片数量的平均值。考虑到某个地区的照片数量的多少更能体现出该地区的旅游活跃程度，因而，本文中城市旅游活跃度的值 来源于两个方面，位置点的密集程度 位置点照片数量的权值，在这里，我们将因此，在这里我们将位置点的密集程度的权值设置为0.4，位置点上的照片数量的权值设置为0.6。

通过该改进算法我们可以得到如下结论：公式4中H的值越大，该地区的旅游活跃度就越高。

3 实验结果及分析

3.1 Flickr网站

Flickr，雅虎旗下图片分享网站。为一家提供免费及付费数位照片储存、分享方案之线上服务，也提供网络社群服务的平台。Flickr集合了借由使用者间的关系而相互连接的数位影像，影像可依其内容彼此产生关联。图片上传者可自己定义该相片的关键字，也就是“标签（Tags）”（是元资料（Metadata）的一种格式），如此一来搜寻者可以很快的找到想要的相片，例如指定拍摄地点或照片的主题，而创作者也能很快了解相同标签（Tags）下有哪些由其他人所分享的照片，Flickr也会挑选出最受欢迎的标签名单，缩短搜寻相片的时间。

3.2 实验数据获取

Flickr对研究者们提供了官方API，可通过https：//www.flickr.com/services/api/获取API，具体步骤如下：

第一步：请求API密钥（key），签上API请求。

第二步：阅读社区准则和使用的API条款。

第三步：建置和测试。

通过获取的API以及我国主要城市的WOEID本文得到了查询数据的url： https：//api.flickr.com/services/rest/？&method;=flickr.places.getChildrenWithPhotosPublic&api;_key=4546584af 9f2b266fa311357cff1701b&format;=json&woe;_id=（要查询的位置）。再通过这个API 获得我国主要城市在Flickr网站中的精度，维度以及该区域上传照片的数量。

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

可以获得上海区域的精度维度和上传照片数量（精度：121.472， 纬度：31.247，照片数量：525788）如图5所示。

3.3 实验结果

首先利用本文中提出的基于加权的OPTICS算法对使用WOEID获得的3012个地区的经纬度进行了分析，得到了每个点的可达距离和核心距离，示意图如图7、图8所示：

再利用加权的OPTICS算法对所得的3012个地区的图片数量进行处理，便获得了各地区的旅游活跃度。如图9所示：

根据核心距离图可知每个凹的区域可以看成一个聚类，且该区域中的地点密度较为密集，例如：天津，上海，海口，昆明，广东等地方。如图9所示。本文将地区活跃度分为5级：

5级为旅游活跃度高于5万的地区。如：北京，上海，天津，香港（九龙，观塘，湾仔，油尖旺）。

4级为旅游活跃度高于3万且低于5万的地区。如：重庆，大连。

3级为旅游活跃度高于1万且低于3万的地区。如：陕西（长安，席王），山西（东社，新城）。

2级为旅游活跃度高于7950且低于1万的地区。如：安徽，吉林。

1级为所剩的地区。

4 可视化

为了给出更直观的实验结果，本文针对“http：//echarts.baidu.com/gallery/editor.html？c=scatter-map”将前面得到的3012个地区的信息放入，实现对数据的可视化显示。鼠标移动至数据点会出现类似99：1这样的数据，冒号前的是位置代码，后者为该地点照片总数。如图10所示，左下角为照片数量的范围，若该地区照片数量在此范围中则会在图中显示。

本文基于改进的OPTICS算法获得实验结果，对网络用户分布密度进行了分析，并得出用户的活跃度等级。然后将活跃度分析、可视化图像及中国入境旅游时空地域分析结果三者进行综合分析，推导出网络用户的分布以及发展走向：

上传照片的中国网民分布也是成聚类分布，以北京，上海，海口，香港，台北市为中心向周围进行发散，分布十分密集，且活跃度极高，形成一个个大聚类，中心都是一级活跃度，周边二级，三级紧密相连，从图11中可见。以杭州，广州，南京，重庆，福建为小中心，周边有一定的分布密度，周边活跃度相对于中心低得多，以苏州，青岛，拉萨，桂林，重庆，丽江为中心的极小聚类分布，特点中心点活跃度高，达活跃度二级，周边活跃度大多都是五级，极少的四级。其余地区拉萨，桂林，哈尔滨显得孤立，单独的活跃度达三级，甚至部分地区达2级，但周边都是活跃度为五级的，并且密度极低。其余的零散分布，不成聚类，并且活跃度都是五级，极少出现四级情况。

参考文献：

[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] 聂雷刚，李咏梅，余元辉.基于聚类分析算法的智能旅游规划[J]. 电脑开发与应用，2012（2）28-30.

[4] 何奇彦.基于稀疏聚类算法的关中地区旅游信息资源共享研究[J]. 自动化与仪器仪表，2017（2）116-118.

[5] 薛玉霞.基于图片共享网络的旅游目的地形象传播策略[D].四川：電子科技大学，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] 陈吉顺.模糊聚类分析在云南旅游数据挖掘中的研究及应用[D].云南大学，2006.

[9] 吕威，倪玉华.基于等距加密和案例推理的旅游线路聚类算法[J].计算机工程与应用，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] 李创新，马耀峰，王永明.1993-2012年中国入境旅游时空地域格局分异与动态演进——基于全局K-Means谱聚类法的“典型区域”实证研究[J].资源科学，2015（11）.

【通联编辑：唐一东】