并行化流式数据聚类及其在交通热点挖掘中的应用

摘要

随着交通、GPS监控等方面数据量的海量增长,伴随出现交通实时路况延时性、交通预测不准确等现象,对流式数据的实时处理提出更高的要求,挖掘交通热点区域成为交通领域研究热点;尽管目前对交通领域流式数据聚类的研究已取得显著成就,但仍存在聚类时效性、伸缩性差,不可实现任意形状类簇等缺点。因此,为高精度实时的挖掘交通热点区域,减少城市交通拥堵和方便资源调度,提出两阶段快速流式数据聚类框架并在Storm集群下实现并行化。
　　本文提出的两阶段快速流式数据聚类框架(Canopy-Kmeans,简称CK)针对流式数据,在线阶段选择改进Canopy算法粗聚类产生宏簇并缓存概要信息;离线阶段使用Kmeans算法细聚类;引入滑动时间窗口并抽取概要信息以自动确定Kmeans初始输入和微簇时间标志。为增加聚类实时性,将CK算法在Storm集群并行化,提出并行化流式数据聚类算法(Parallel-Canopy-Kmeans,简称PCK)并实现。
　　为验证PCK算法性能,选取测试数据集对PCK、CK、Kmeans进行聚类就准确性、执行时间对比;对PCK自身就扩展性对比。为提高交通热点区域挖掘的可行性,选取北京市某七天的出租车定位数据模拟流式数据,使用PCK算法聚类生成微簇集合并结合热力图和电子地图可视化表达。实验结果表明:生成的交通热力图可直观地发现出租车活动较为频繁的热点区域和线路,且与日常出行经验相符合;生成的微簇集合可实现用户在任意时间窗口范围内交通状况实时查询,提高流式数据的聚类质量的同时保证交通路况预测实时性,为交通活动实时分析、城市车辆实时调度、物流园区车货调度等方面提供有价值的理论参考依据。

目录

声明

摘要

第1章 绪论

1．1 研究背景与研究意义

1．1．1 研究背景

1．1．2 研究意义

1．2 国内外研究现状

1．2．1 流式数据聚类的研究现状

1．2．2 交通路况的研究现状

1．3 研究内容和组织结构

1．3．1 研究内容

1．3．2 论文组织结构

第2章 相关理论概述

2．1 流式数据概述

2．1．1 流式数据的概念

2．1．2 流式数据挖掘技术

2．2 聚类算法概述

2．2．1 聚类分析的概念

2．2．2 常见聚类算法划分

2．2．3 流式数据聚类算法的要求

2．2．4 流式数据聚类模型与算法

2．3 流式计算框架概述

2．3．1 流式计算框架的比较

2．3．2 流式计算Storm框架

2．4 本章小结

第3章 PCK流式数据聚类模型的构建与分析

3．1 两阶段快速流式数据聚类框架的建立

3．1．1 两阶段流式数据聚类框架

3．1．2 在线粗聚类阶段

3．1．3 离线细聚类阶段

3．2 CK流式数据聚类算法设置与调整

3．2．1 CK算法设置

3．2．2 CK算法参数调整

3．3 PCK流式数据聚类算法的并行化计算实现

3．3．1 Storm并行化

3．3．2 PCK算法设计

3．3．3 PCK算法实现

3．4 实验与结果分析

3．4．1 实验环境与数据

3．4．2 实验验证

3．4．3 性能分析

3．5 本章小结

第4章 PCK算法在交通热点挖掘中的应用

4．1 实验目的

4．2 实验准备

4．2．1 数据集选取

4．2．2 PCK并行化设置

4．2．3 PCK参数设置

4．3 实验结果

4．3．1 交通热点区域挖掘

4．3．2 PCK参数影响力分析

4．3．3 带时间跨度的交通热点实时演变

4．4 本章小结

第5章 总结与展望

5．1 研究总结

5．2 研究展望

参考文献

致谢