基于智能手机轨迹提取停留点的时空聚类算法研究

摘要

随着智能手机的普及，使用手机端传感器获取定位轨迹越来越便利，本文通过对传统聚类算法的改进，进行时空停留点的提取。以Myeclipse为主要开发环境，结合Java与Tomcat服务器实现了基于WebGIS的停留点提取系统，并对聚类结果进行统计分析。轨迹停留点研究在个性化好友推荐、出行目的地预测、商业广告推送等方面有重要的学术意义和应用价值。本文重点研究基于用户轨迹点提取停留点的时空聚类算法以及与WebGIS相结合的系统实现。
　　本文的数据来源是利用智能手机APP获取同一轨迹下四部不同Android手机用户的轨迹数据。通过统计用户停留点的实际时空位置，作为聚类结果分析评价的对比数据。然后，使用 Java程序对原始定位数据进行预处理，包括数据清洗、数据中心化和标准化三个方面，获取用户轨迹点的经纬度坐标、时间戳等信息。最后，将预处理后的数据按照一定的格式导入数据库，构成聚类分析的实验数据。
　　基于 Java语言实现聚类算法，分别使用基于层次的ST-BIRCH算法、基于密度的ST-DBSCAN和ST-OPTICS算法、以及基于网格和密度的ST-GRID四种时空聚类方法进行停留点提取。根据用户轨迹的经纬度范围、停留时长、到达同一停留点时间间隔等设置具体的算法参数，解决算法参数设置问题，实现时空停留点的提取。
　　在对不同算法的对比评价方面，以各停留点的实际时空信息为参照，从聚类算法提取的正确点、缺失点和错误点三个方面，对比不同智能手机、不同聚类算法、不同定位类型轨迹提取停留点的时空差异，对算法的性能和聚类效果进行分析评价。探讨实验中时空停留点提取的一般性结果：同一轨迹下不同智能手机的软硬件性能、定位策略、采集轨迹点数量不同，同一聚类算法提取结果存在明显差异；基站定位误差是影响时空停留点提取精度的主要因素之一；GPS信号容易受遮蔽物影响，易出现定位漂移等误差，但对停留点提取结果影响不大；在聚类算法方面，基于密度的ST-DBSCAN算法，使用以轨迹点为邻域的密度划分，能够较好的去除噪声，提取效果较好，聚类算法总体性能也优于其它算法，但对基站定位的数据误差，仍难以消除；根据实验对比，使用ST-OPTICS算法改进ST-DBSCAN聚类参数的方案适合时空停留点提取。
　　基于百度地图JavaScript API应用程序接口进行时空停留点提取的WebGIS系统开发，与Java语言实现的聚类算法及Oracle数据库相结合完成了系统的设计与实现。系统采用三层的结构划分，满足系统不同层次间数据传输接口的一致性问题。系统实现了地图基本操作、用户实际停留信息查询、用户轨迹查询、聚类算法结果展示四大模块。其中，基本操作模块包含地图的切换、漫游、缩放、测距等基础功能；用户停留信息查询用于用户实际时空停留点及缓冲区查询；用户轨迹查询模块包括结合地图海量点功能实现用户的轨迹点空间信息和属性信息的查询、利用热力图对用户轨迹进行直观展示；聚类分析模块则是通过不同手机、算法和参数的选择，与后台Java语言实现的聚类算法相结合，将聚类结果返回给浏览器端，实现聚簇点查询、停留点提取、逆地址解析和停留点街景的功能，并通过与用户停留信息查询模块对比实现聚类算法对比评价。
　　本文通过实验得出，影响用户轨迹停留点提取算法效果的主要原因是用户轨迹获取中的基站定位误差较大。基于改进的ST-OPTICS算法，实现了用于决定参数的领域知识最小化，确定ST-DBSCAN算法的聚类阈值进行时空停留点提取，对传统聚类方法有一定改进，适用于时空停留点提取。但是，算法在时间复杂度、执行效率方面有待优化，在WebGIS停留点提取系统集成方面的研究仍需进一步深入。

目录

封面

声明

目录

中文摘要

英文摘要

第1章 绪论

1.1 选题背景

1.2 国内外研究现状

1.3 研究目的及意义

1.4 研究内容、技术路线与关键问题

第2章 智能手机轨迹获取和聚类算法研究

2.1 轨迹数据获取

2. 2 聚类算法

2.3 聚类算法评价

第3章 基于时空聚类算法提取轨迹停留点

3.1 停留点提取数据准备

3.2 时空停留点提取概念定义

3.3 基于ST-BIRCH的停留点提取

3.4 基于ST-DBSCAN的停留点提取

3.5 基于ST-OPTICS的停留点提取

3.6 基于ST-GRID的停留点提取

第4章 时空聚类算法对比评价

4.1 聚类结果对比分析

4.2 聚类算法性能分析与评价

第5章 时空停留点提取系统的设计与实现

5.1 基于WebGIS的系统设计

5.2 基于WebGIS的系统实现

第6章 结论与展望

6.1 研究结论

6.2 不足之处与未来研究展望

参考文献

致谢

硕士研究生期间学术成果

发表论文

参与项目