基于LBS的定位系统的研究与设计

高　翔，张成文

（兰州文理学院　电子信息工程学院，甘肃　兰州　730000）



基于LBS的定位系统的研究与设计

高翔，张成文

（兰州文理学院电子信息工程学院，甘肃兰州730000）

摘要：LBS的广泛应用带来海量的位置信息数据，如何充分利用这些数据并从中挖掘出隐含其中的知识为决策提供数据支持，已经成为空间数据挖掘技术的重要内容.本文重点研究了空间数据挖掘中的聚类分析算法，以此提出了基于LBS的定位系统.该系统分析了DBSCAN和K-means算法，并提出了一种改进算法，实现异常位置检测.基于上述研究设计实现了基于LBS的定位系统，实现了实时定位查询，时空查询，异常轨迹分析等功能.

关键词：LBS；聚类算法；定位系统

1　引言

基于位置的空间信息服务(Location Based Service, LBS)[1]是基于地理信息系统，通过移动计算技术在无线环境下实现资源共享和数据传输而衍生的信息服务.LBS通过移动终端确定移动用户的实际地理位置，从而提高用户所需要的与位置相关的服务信息.位置服务技术广泛的应用在民用和军事的诸多方面，为人们的生活提供极大的便利.随着无线通信技术和GPS技术的发展，基于位置的信息数据呈指数倍增长，海量的信息已经远远超过了人工分析的能力，如何对这些信息进行有效的集成和分析，挖掘出这些空间数据背后隐藏的知识，从中发现出目标的运行规律，然后利用这些规律进行决策，实现决策的科学化合理化.

聚类分析是空间数据挖掘的常用方法，其通过将特征相近的空间数据归结到一个组内，最终根据不同的特征将数据划分为几个组.聚类分析结果中组与组之间的差别尽可能大，而组内差异尽可能的小.聚类分析广泛的应用在市场研究，模式识别和图像处理等，本文采用的方法主要涉及到DBSCAN (Density- Based Spatial Clustering of Applications with Noise)[2]和K- means算法[3].DBSCAN算法是基于密度的聚类算法，其最重要的两个参数为区域半径E，以及给定点在E邻域内成为核心对象的最小邻域点数MinPts，这两个参数在开始时刻设定，该算法的主要缺点是聚类结果对这两个参数的依赖性非常大，当数据分布不均匀时，参数的取定对聚类的结果和质量有很大的影响.K- means算法需给定初始值K，以及K个初始中心值，不同的K以及初始中心值带来的聚类结果是不同的，上述两个值的不同导致应用上的局限性.

针对上述问题，提出了异常轨迹点的查找算法，并基于该算法实现基于LBS的定位系统.该系统主要通过异常点检测算法发现特殊人群的异常轨迹，从而判断监控对象活动的异常区域，这对异常监控对象监控具有非常具有实际意义.本文的剩余部分安排如下，第二节主要介绍异常轨迹点的查找算法，第三节介绍了基于LBS的定位系统的设计，并给出相关实现结果，第四节对全文进行总结并分析未来研究方向.

2　异常轨迹点的查找算法

异常轨迹点的查找算法的中心思想就是在聚类分析过程中，将异常点尽可能的识别出来，然后在这些异常点中进行查找.通过对DBSCAN算法的分析，可以发现该算法具有良好的异常点检测能力，然而由于算法的的特性，过多的将正常点归类与异常点；而由于K- means算法将所有的点划分到不同的类别中，如果没有事先定义好相关的K值和K个初始聚类中心，会导致聚类结果不尽人意.由此可见可以将两种方法结合，然后对他们的优缺点进行互补，将DBSCAN的聚类结果由K- means进行二次分析，从而找出最异常的点.

异常轨迹点查找算法的具体步骤如下：

（1）将目标的定位数据定义为数据集Dataset，并确定该Dataset的参数E和MinPts，由于本文中是定位系统，因此这里的聚类相似度参考值设为点与点之间的距离；

（a）随机抽取部分数据，并计算各点之间的距离，去中间值作为该Dataset的参数E；

（b）观察目标在空间中的分布图，确定MinPts的值；

（2）根据步骤（1）中确定的参数E和MinPts，对数据集D进行DBSCAN算法聚类，具体聚类步骤如下；

DBSCAN(D, E, MinPts)

C = 0

for each unvisited point P in dataset D

mark P as visited

NeighborPts = regionQuery(P, E)

if sizeof(NeighborPts) < MinPts

mark P as NOISE

else

C = next cluster

expandCluster(P, NeighborPts, C, E, MinPts)

expandCluster(P, NeighborPts, C, E, MinPts)

add P to cluster C

for each point P' in NeighborPts

if P' is not visited

mark P' as visited

NeighborPts' = regionQuery(P', E)

if sizeof(NeighborPts') >= MinPts

NeighborPts = NeighborPts joined with NeighborPts'

if P' is not yet member of any cluster

add P' to cluster C

regionQuery(P, E)

return all points within P's E- neighborhood (including P)

（3）经过DBSCAN算法计算得来的所有类簇，并把所有异常点定义为新的簇，并计算出每个簇的数目N1，N2，…，Nn，这些簇分别为W1，W2，…，Wn，其中心分别为C1，C2，…，Cn，最后对整个数据集D进行K- means聚类，其中K=n，聚类中心点为C1，C2，…，CN，具体步骤如下：

repeat

根据聚类中点的均值，将每个点指派到最相似的聚类；

更新聚类均值，即计算每个聚类中点的均值Zj(W)；

until聚类不再发生变化

其中收敛准则函数为差方和函数

（5）输出聚类结果集，算法结束.

3　定位系统的设计

3.1系统框架设计

本系统采用BS结构，使用MVC框架[4]，通过定位终端系统采集到的定位数据进行处理，并且将分析结果在地图上显示，总体框架如图1所示.

图1　系统总框架

3.2数据库设计

系统主要使用的数据包括历史位置信息，对这些数据进行分析和处理，需要对相关数据进行划分，这些信息分为时空属性和非时空属性，因此系统使用主要的数据表如下.

系统监控对象信息表，主要记录待定位监控对象的相关信息.

表1　监控对象信息表(PersonInfo)

监控对象位置信息表，主要记录待定位监控对象的位置信息.

监控对象历史位置信息表，从结构上这和监控对象位置信息表相同，每隔一段时间PersonLocationInfo的内容转存入监控对象历史位置信息表.将主要记录待定位监控对象的历史位置信息.

表2　监控对象位置信息表(PersonLocationInfo)

表3　监控对象历史位置信息表(PersonHistoryLocationInfo)

用户组表，主要记录用户组信息.

表4　用户组表(PersonGroup)

表5　用户表(SubUserInfo)

3.3系统功能设计

本系统主要功能包括查询结果展示，当前位置查询，历史轨迹查询，区域查询和时空查询等功能，具体如图2所示.

图2　系统功能图

其中历史轨迹查询，区域查询和时空查询使用了异常轨迹点的查找算法得到的结果，具体结果如下所示.

图3　系统主界面

4　结束语

本文提出了基于LBS定位的定位系统，主要根据对象的历史位置信息进行时空数据挖掘.本文首先分析了DBSCAN和K- means算法在时空数据挖掘中的优缺点，并根据这两种算法提出一种异常轨迹点的查找算法，从而发现对象的经常出现的位置信息，基于上述研究设计实现了基于LBS的定位系统，实现了实时定位查询，时空查询，异常轨迹分析等功能.通过异常点检测算法发现特殊人群的异常轨迹，从而判断监控对象活动的异常区域，这对异常监控对象监控具有非常实际意义.

参考文献：

〔1〕黄潇婷，柴彦威.面向LBS使用者的时间地理学研究评介[J].地理科学进展，2009，28(6):962-969.

〔2〕周水庚，周傲英，曹晶，等.基于数据分区的DBSCAN算法[J].计算机研究与发展，2000，37(10):1153-1159.

〔3〕杨善林，李永森，胡笑旋，等.K-means算法中的k值优化问题研究[J].系统工程理论与实践，2006，26(2):97-101.

〔4〕张宇，王映辉，张翔南，等.基于Spring的MVC框架设计与实现[J].计算机工程，2010，36(4):59-62.

中图分类号：TP393

文献标识码：A

文章编号：1673- 260X（2015）03- 0009- 03