左甜甜

(沈阳理工大学 辽宁 沈阳 110159)



社交网络签到地点分类

左甜甜

(沈阳理工大学 辽宁 沈阳 110159)

随着4G和Wi-Fi技术的发展，越来越多的定位技术被运用到网络和智能终端中，对已签到的地理位置进行分类(如餐厅、商店等)成为基于地理位置的服务应用的重中之重。以Python爬取的新浪微博签到及互动数据为基础，以假设的未分类样本作为对象，将经纬度数据输入基于Java的改进DBSCAN密度聚类算法，输出其地理范围，用基于R语言的机器学习中KNN分类算法建立模型，实现社交网络签到地点的分类。

签到地点；分类；DBSCAN；KNN

位置可以是绝对的地理位置，如经纬度；也可以是相对意义的地理位置，如XX路XX号XX商场附近100米处；还可以是语义上的地理位置，如某某商场。本文以经纬度为切入点，结合已知的签到地点分类信息对未知的签到地点进行分类。

其中两个地点之间的距离采用公式：

C=sin(LatA)*sin(LatB)*cos(LonA-LonB)+cos(LatA)*cos(LatB)

Distance=R*Arccos(C)*Pi/180

LatA、LonA是A点的经度、纬度，LatB、LonB是B点的经度、纬度，R为地球半径取6371km，Pi取3.14。

一、基于DBSCAN的地点聚类

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)基于密度的聚类算法，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有“噪声”的数据中发现任意形状的聚类。

(一)DBSCAN算法流程

1.如果一个点p的ε邻域包含多于m个对象，则创建一个p作为核心对象的新簇；

2.寻找并合并核心对象直接密度可达的对象；

3.没有新点可以更新簇时，算法结束。

(二)对签到地点数据中的经纬度应用DBSCAN算法

以辽宁省沈阳市的44914个样本为例，在做过数据清洗之后剩余40967个样本，取经纬度两个特征，并将二级分类信息粗划为一级分类共11种。(参考美团、大众点评分类信息进行归类)。由于Java以及R语言对中文处理敏感，因此将一级分类标号1～11替换文字，作为DBSCAN算法的待输入数据。由于DBSCAN是将候选服务集每一个对象作为核心对象进行密度聚类，但是该应用场景不需要，只需要将未知地点分类的对象作为核心对象即可，所以，应用用Java语言编写的改进DBSCAN算法。

二、基于KNN的签到地点分类

KNN(k-NearestNeighbor)邻近算法，其主要思想是给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个“邻居”的信息来进行预测，通常，在分类任务中可使用“投票法”，即选择这k个样本中出现最多的类别标记作为预测结果；在回归任务中可使用“平均法”，即将这k个样本中出现最多的类别标记作为预测结果；还可基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。该场景应用“投票法”。

(一)KNN算法流程

1.计算距离：通常采用欧氏距离与曼哈顿距离。

2.k值的选取：通常取训练集样本数量的平方根，或通过实验的准确率确定k值。

3.准备数据：通常对数据进行0-1标准变换或z-score标准变换。

(二)对未签到地点数据应用KNN算法

以假设的未知的签到地点分类样本作为对象，通过上述DBSCAN算法确定其地理范围，然后应用基于R语言的KNN算法，通过R语言的CrossTable()命令输出交叉校验表，由此表可看出真实分类与预测分类的对比情况以及分类准确率。

通过将辽宁省沈阳市的40967个样本中抽取4338个样本作为训练样本，将余下样本分成10份作为测试集进行测试，其平均准确率达到96.7%，由此证明了模型的优秀。

三、分类模型的现实意义

(一)个性化位置推荐。流行位置推荐虽然可以给用户推荐相应的位置，但这些位置并没有考虑用户的个性化信息，即对所有用户推荐的都是相同的位置。通过找到与自己相似性高的用户，再根据这些用户访问的位置进行推荐网。也可以通过得到位置间的相关性，再根据与用户经常访问的位置相关性大的位置进行推荐。

(二)位置活动推荐。当用户指定一个位置时，可以给用户推荐在这个位置上发生的最流行的活动，当用户指定一种活动时，也可以给用户推荐进行这种活动的最流行的位置叫。可通过矩阵来描述每个位置发生的每种活动的情况，但由于在每个位置可以进行的活动是有限的，而活动的种类却是非常多的，因此这个矩阵是非常稀疏的，而进行推荐的主要依据就是矩阵中每个元素的数值。

(三)商店位置选择。为一个新的商店选择最好的位置是一个很有意义的问题。与传统的方法不同，基于LBSN中收集到的描述用户移动的细粒度数据和位置的流行性，给出问题的形式化定义，并从不同特性的角度进行商店位置预测，如密度特性、竟争特性、区域的流行性等。

[1]杨帆,徐建刚,周亮.基于DBSCAN空间聚类的广州市区餐饮集群识别及空间特征分析[J].经济地理,2016,36(10):110-116.

[2]杜蓉.基于豆瓣同城活动的线上线下社交影响研究[J].计算机学报,2014,37(1):238-245.

[3]黄文,王正林.数据挖掘:R语言实战[M].电子工业出版社,2014:111-120.

[4]BrettLantz.机器学习与R语言[J].2015:82-95.

[5]Java获取Map地图经纬度与所处地理名称相互转化.http://yegshine.blog.163.com

左甜甜(1993-)，女，满族，辽宁铁岭市人，工科硕士，沈阳理工大学通信与信息系统专业，研究方向：移动无线网络技术。