基于随机序列GPS数据集的用户位置挖掘方法研究

作者信息：王铁军，赵礼剑，朱　熙

（国家测绘地理信息局　重庆测绘院，重庆　401121）

“

【摘要】数据挖掘是指从大规模的数据中抽取非平凡的、隐含的、未知的、有潜在使用价值信息的过程。LBS系统记录了大量的移动端用户在真实世界中的空间和时间属性，如果能从这些记录中挖掘出移动端用户的常用位置信息及其特点，可以使我们更好地理解用户，更好地为用户服务。本文根据LBS系统记录的移动端用户位置信息，利用改进的DBSCAN聚类算法，较为准确地提取移动端用户的常用位置信息，并通过实例验证该方法的可靠性。

【关键词】信息处理技术；数据挖掘；位置服务；聚类

【中图分类号】P228.4【文献标识码】B【文章编号】1672-1586（2018）02-0113-04

”

引文格式：王铁军, 赵礼剑, 朱　熙. 基于随机序列GPS数据集的用户位置挖掘方法研究[J].地理信息世界,2018,25(2):113-116.

正文

0 引　言

随着定位技术的发展和成熟，以及智能移动设备的应用和普及，基于位置的服务（Location BasedService，LBS）得到了广泛的应用。该服务利用移动互联网技术为广大移动端用户提供各类位置服务，以手机或者其他终端设备上传的位置为基础，在地理信息系统的支持下，向用户提供生活、工作、社交、休闲娱乐等多种类型的基于位置的服务，如距离较近的宾馆、餐饮以及导航或交通拥堵情况等信息。基于位置的服务通常由LBS服务平台（服务器端）和移动端两部分构成。移动端通过移动通信网络向LBS服务平台发出服务请求，LBS服务平台根据移动端请求和其当前位置进行处理，并将处理结果返回给移动端。LBS服务平台记录了用户在请求服务时的位置及时间信息，这些信息具有动态、海量、时空相关等主要特征。动态特征是指移动端处于一个不断变化的状态中，并非是停止不变的；海量特征指的是不同时间信息数据长期积累，数据量非常庞大；时空相关性是指位置数据在时间和空间上相互关联。

本文利用数据挖掘的相关理论和方法，对LBS服务平台记录的移动端用户位置信息进行聚类和关联分析，提取出移动端的常用位置信息，并进一步解析出其他相关信息，从而提供更加智能化、适应性更强的服务，达到变被动为主动的服务目的。

1 常用位置数据挖掘方法

位置数据挖掘是从移动端数据集中提炼隐含的、用户感兴趣的空间和非空间的模式、知识、规则以及相关特征的过程，是数据挖掘研究的重要分支；其概念和含义与数据挖掘类似，即从不完全的、模糊的、随机的、有噪声的、海量位置数据中，提炼出隐含在数据中、人们之前也许不知道的、但又可能具有潜在有用知识的过程。常用的数据挖掘算法有：统计分析方法、时空聚类方法、计算几何分析方法、遗传算法、神经网络方法等，各种算法都有特定的运用环境。对于位置挖掘来说，时空聚类方法是一种常用的方法，其优势在于将位置数据划分为不同的类别，不需要在模型中输入背景知识，就能够自动挖掘出数据本身的特征。目前常用的聚类方法有：基于密度、基于距离、基于层次和基于栅格的方法。基于密度的方法将密度较大的区域划为单独的类，与其他聚类方法相比，此方法可以发现任意形状的簇；基于距离的方法主要采用迭代法，根据点之间距离的远近决定某个点到底归属于哪个类别，距离是预先设定好的，不同的数据中，距离不同；基于层次的方法可以分为凝聚法和分裂法，其主要思想是自下而上合并比较小的类或者自上而下将比较大的类分割成比较小的类；基于栅格的方法主要通过划分数据的单元格来发现类。

DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法）算法是一种典型的基于密度的聚类算法，其核心思想是用某个点的邻域内的点数来衡量该点所在空间的密度，将具有足够密度的区域划分为簇，因此可以发现任意形状的聚类簇，并且不需输入要划分的聚类个数。DBSCAN算法中有两个重要参数：Eps和MinPts，前者为定义密度时的邻域半径，用于描述某一样本邻域的距离阈值，常用ε 表示；后者为定义核心点时的阈值，用于描述样本中距离为ε的邻域中样本个数，常用M表示。

对于数据集D =(X1,X2,…,Xm),利用DBSCAN算法进行聚类分析步骤如下：

1）样本聚类：利用公式（1）提取样本集D 中任意点Xj邻域半径ε范围内所有点，用Nε（Xj）表示。

2）密度计算：用ρ(Xj)表示点Xj的密度，计算方法见公式（2），密度是一个整数值，且与邻域ε紧密相关。

3）核心对象判别：若ρ(Xj)≥M，则称Xj为样本D的核心对象。

4）密度直达：如果点Xi位于核心对象Xj的ε邻域中，则称Xi由Xj密度直达，反之则不一定成立。

5）密度可达：若样本集D 中存在核心对象p1，p2，p3,…,pt，t≥2，且pi +1由pi密度直达（i=1,2,…,t-1），则称pt是从p1密度可达的。

6）密度相连：若样本集D中存在核心对象p1，p2，p3，若p2和p3均可由p1密度可达，则称p2和p3密度相连，密度相连具有对称性。

2 基于随机序列GPS数据集的移动端常用位置挖掘

2.1 LBS系统位置数据分析

LBS服务器端提供的随机序列GPS数据集具有范围分布广、数据量大、时间跨度长、离散度高等特点，且在数据中存在大量的冗余信息，给数据的挖掘带来了极大的不便。因此在数据挖掘前，必须对数据进行噪声滤波，去除不必要的冗余，确保提取位置的准确性。

2.2 常用位置挖掘实施

根据所获取的数据集的特点，综合应用时空聚类和统计分析的方法处理随机序列GPS数据集，同时结合电子地图兴趣点等相关数据进行移动端常用位置的提取，在此基础上赋予用户位置语义信息，从而形成基于随机序列GPS数据集的移动端常用位置挖掘方法。数据处理流程如图1所示。

图1　基于随机序列GPS数据集的移动端常用位置挖掘流程

Fig.1 Flow of mobile location common mining based on random sequence GPS dataset

1）坐标投影转换：LBS服务平台提供的移动端位置信息用经纬度表示，给距离量算、评估等带来不便；为能直观分析和统计，根据移动用户端的位置，选择中央子午线，采用CGCS2000国家大地坐标系椭球参数进行高斯投影正算，将经纬度坐标（B，L）转换为高斯平面坐标（x，y），方法见公式（3）。

式中，l(B)为从赤道到投影点的子午线弧长，N为卯酉圈半径，t=tanB，η²=e＇²B，e＇为参考椭球第二偏心率，l=L-L，L为中央子午线经度。

2）基于时间序列的冗余位置信息处理：移动端在请求服务时上传的位置信息由LBS服务器统一存储，但部分时刻移动端请求服务时上传位置信息的频率非常高，且位置信息基本一致，不仅增加了数据处理的工作量，还增大了数据处理的难度，对位置信息提取的准确性造成了较大影响，因此在进行位置信息提取前必须进行冗余数据处理。以一定的时间间隔将待处理数据分成若干个时间段，对每一时间段内的数据进行聚类分析，对冗余位置数据进行过滤。

3）基于聚集度的移动端常用位置提取：对过滤后的移动端位置信息数据进行综合分析，采用层次化的DBSCAN算法进行移动端常用位置信息挖掘，提取移动端的常用位置信息。

①密度值计算：扫描整个数据集，进行邻域半径范围内的位置点聚类，求得任一点的密度值；

②核心对象提取：通过密度值对比，提取核心对象；

③数据聚类：以核心对象为中心，标记在邻域范围内的所有点，聚类成簇；

④过滤聚类而成的簇，重复步骤①、②、③，寻找没有被聚类的核心对象，对核心点进行扩充直到数据集中没有新的核心对象为止；

⑤常用位置提取：提取出来的核心对象在不同天、不同时间段出现的次数最多、密度最大，可以认为是移动端的常用位置。

4）常用位置提取结果分析及相应信息赋予：结合电子地图兴趣点（POI）数据、提取的常用位置及周边一定范围内的所有位置点的时间属性信息等进行常用位置相关信息赋予。如果常用位置及其周边位置点的时间属性为非工作时间段，且该常用位置位于居民小区及周边，可以判断该位置为移动端的居住地点；如果位置点的时间属性为工作时间段，且附近为办公楼等相关区域，可以认为该位置点为移动端用户的办公地点；如果位置点的时间分布无规律，且经常在周末或者节假日出现，则可以认为该位置为常用娱乐休闲场所。

3 试验与结果分析

本文利用某LBS服务平台提供的最近8个月的随机序列GPS数据集进行移动端常用位置挖掘，该数据集包含上万个用户的共计400余万条位置信息，在地理位置上覆盖我国中西部大部分城市。

为方便研究和结果验证，选择了3个移动端用户参与常用位置信息挖掘试验，每个试验用户的位置信息都在3 500条以上。以1 h为时间间隔进行冗余数据处理，以30 m为邻域半径范围进行常用位置提取，每个移动端用户均提取了3个常用位置，提取的常用位置周边的点数见表1。

表1　提取的常用位置周边的点数

Tab.1 Points extracted around common locations

从表1可以看出，提取的3个移动端用户最常用的3个位置在8个月内登陆LBS服务器的次数均在200次以上；尤其是每个用户的位置1，去除冗余数据后在同一位置登录LBS的次数仍在470次以上，也就是说平均每天都会在该位置登陆LBS服务器两次以上。

从时间属性上看，在位置1和位置3登录的基本上为非工作时段，在位置2登录的基本上为工作时段。结合电子地图兴趣点数据和位置点时间属性赋予相应的语义信息，提取的3个移动端的位置1均为居住地点，位置2均为办公地点，位置3均为休闲地点。计算3个常用位置之间的距离见表2。

表2　提取的常用位置间的距离

Tab.2 Distance between the extracted common locations

一般为方便工作和生活，会选择在工作地点附近居住，到居住或者工作地点就近休闲娱乐。也就是说，居住地点、办公地点、休闲地点三者之间不会出现都相距很远的情况，一般是两者之间比较近，或者三者之间都比较近。从表2的常用点间距离来看，每个用户至少有2个常用位置之间的距离比较近，说明了提取的位置是合理的。

为进一步直观地分析所提取的位置，将提取的用户A的3个常用位置在地图上进行标注，如图2所示。

a 位置 1

a Location 1

b 位置 2

b Location 2

c 位置 3

c Location 3

图2　移动端用户A常用位置（图中红点）标注

Fig.2 Labeling of common locations(red points)for mobile end user A

图2（另两个用户的情况类似，标图省略）进一步说明了前面的位置及其语义信息（居住地点、办公地点和休闲地点）提取是正确的。再和参与试验的移动端用户进行核实，结果与实际情况基本一致，从而直接验证了本文研究方法的正确性和有效性。

4 结束语

本文针对LBS移动端位置数据集的特点，基于DBSCAN算法设计了一种层次化的移动端常用位置挖掘方法，能够从LBS服务平台记录的移动端位置数据集中挖掘出移动端用户的常用位置及其语义信息。该方法在坐标投影转换的基础上基于时间序列去除冗余数据，然后采用基于密度的聚类算法对移动端位置信息进行聚类，提取移动端用户的常用位置，再利用位置点时间属性、兴趣点数据分析得出常用位置的语义信息。与现有的地点挖掘算法相比，该聚类算法能更好地适应移动端轨迹数据的不确定性，从而准确、高效地挖掘出移动用户的常用位置及其他有价值的信息。

利用某LBS服务平台提供的最近8个月的随机序列GPS数据集进行试验，并选择了3个移动端用户进行验证，通过常用位置间距离分析、在地图上标注直观判断等方法，说明挖掘的常用位置以及提取的语义信息正确；经用户验证与实际情况基本一致，进一步证明了上述研究方法的有效性和研究结果的正确性。

来源：地理信息世界（版权归原作者及刊载媒体所有）

编辑/王欠鑫 审核/孙浩南 卞艺潼