基于网格聚类的热点路径探测

doi:10.13229/j.cnki.jdxbgxb201501040

吉林大学学报(工学版) ›› 2015, Vol. 45 ›› Issue (1): 274-282.doi: 10.13229/j.cnki.jdxbgxb201501040

基于网格聚类的热点路径探测

吴俊伟^1，2，朱云龙¹，库涛¹，王亮^1，2

1.中国科学院沈阳自动化研究所信息服务与智能控制技术实验室，沈阳110016；
2.中国科学院大学，北京 100039

收稿日期:2013-05-13 出版日期:2015-02-01 发布日期:2015-02-01
作者简介:吴俊伟(1982)，男，博士研究生.研究方向:移动数据挖掘.E-mail:wujunwei@sia.cn
基金资助:
国家自然科学基金项目(61003208, 61174164, 61105067, 51205389).

Hot routes detection algorithm based on grid clustering

WU Jun-wei^1,2, ZHU Yun-long¹, KU Tao¹, WANG Liang^1,2

1.Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, China;
2.University of the Chinese Academy of Sciences, Beijing 100039, China

Received:2013-05-13 Online:2015-02-01 Published:2015-02-01

摘要/Abstract

摘要： 针对现有热点路径探测算法需要路网拓扑结构的支持，以及难以准确识别热点路径的复杂耦合现象的问题，提出了一种基于网格聚类的热点路径探测算法。算法将移动轨迹映射为网格序列，以邻接网格间的共有轨迹量来定义网格间的密度可达性，并据此将网格分划抽象为图模型。然后以图论中的相关理论为基础提出了网格聚类算法GridGrowth，即热点路径探测算法。实验结果表明:本文算法能有效探测热点路径，且能准确识别热点路径的复杂耦合现象。

关键词: 计算机应用, 耦合现象, 轨迹挖掘, 热点路径, 网格聚类

Abstract: Existing algorithms for hot route detection are difficult to solve the complex coupled problem of hot routes, or they need the support of road network topologies. In order to overcome these disadvantages, we present a hot route detection algorithm based on grid clustering. In this algorithm the trajectory is converted to grid sequence, and the density reachability of the neighbor grids is determined based on their common traffic, and then the grids are abstracted to a graph model. So the grid clustering algorithm, GridGrowth, can be presented based on the graph theory, i.e. the hot route detection algorithm. Experimental results show that the proposed algorithm can effectively detect the hot routes and can accurately solve the complex coupled problem of the hot routes.

Key words: computer application, coupled problem, trajectory mining, hot routes, grid clustering

中图分类号:

TP391

吴俊伟，朱云龙，库涛，王亮. 基于网格聚类的热点路径探测[J]. 吉林大学学报(工学版), 2015, 45(1): 274-282.

WU Jun-wei, ZHU Yun-long, KU Tao, WANG Liang. Hot routes detection algorithm based on grid clustering[J]. 吉林大学学报(工学版), 2015, 45(1): 274-282.

参考文献

[1] Cadez I V, Gaffney S, Smyth P. A general probabilistic framework for clustering individuals and objects[C]∥Proceedings of the Sixth ACM International Conference on Knowledge Discovery and Data Mining, 2000: 140-149.
[2] Gaffney S, Smyth P. Trajectory clustering with mixtures of regression models[C]∥Proceedings of the Fifth ACM International Conference on Knowledge Discovery and Data Mining, 1999: 63-72.
[3] Kalnis P, Mamoulis N, Bakiras S. On discovering moving clusters in spatio-temporal data[C]∥Jensen Christian S ed, Advances in Spatial and Temporal Databases, Springer, 2005: 364-381.
[4] Kostov V, Ozawa J, Yoshioka M, et al. Travel destination prediction using frequent crossing pattern from driving history[C]∥Proceedings of Intelligent Transportation Systems, IEEE, 2005: 343-350.
[5] Lee J G, Han J, Whang K Y. Trajectory clustering: a partition-and-group framework[C]∥Proceedings of the ACM International Conference on Management of Data, 2007: 593-604.
[6] Liao L, Patterson D J, Fox D, et al. Learning and inferring transportation routines[J]. Artificial Intelligence, 2007, 171: 311-331.
[7] 夏英, 温海平,张旭. 基于轨迹聚类的热点路径分析方法[J]. 重庆邮电大学学报:自然科学版, 2011, 23(5):602-606.
Xia Ying, Wen Hai-Ping, Zhang Xu. Hot route analysis method based on trajectory clustering[J]. Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition), 2011, 23(5): 602-606.
[8] 赵秀丽, 徐维祥. 一种移动物体时空轨迹聚类的相似性度量方法[J]. 信息与控制, 2012, 41(1): 63-68.
Zhao Xiu-li, Xu Wei-xiang. A similarity measurement method for clustering spatio-temporal trajectories of moving objects[J]. Information and Control, 2012, 41(1): 63-68.
[9] Li X, Han J, Lee J G, et al.Traffic density-based discovery of hot routes in road networks[C]∥LNCS,2007,4605:441-459.

相关文章 15

[1]	刘富,宗宇轩,康冰,张益萌,林彩霞,赵宏伟. 基于优化纹理特征的手背静脉识别系统[J]. 吉林大学学报(工学版), 2018, 48(6): 1844-1850.
[2]	王利民,刘洋,孙铭会,李美慧. 基于Markov blanket的无约束型K阶贝叶斯集成分类模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1851-1858.
[3]	金顺福,王宝帅,郝闪闪,贾晓光,霍占强. 基于备用虚拟机同步休眠的云数据中心节能策略及性能[J]. 吉林大学学报(工学版), 2018, 48(6): 1859-1866.
[4]	赵东,孙明玉,朱金龙,于繁华,刘光洁,陈慧灵. 结合粒子群和单纯形的改进飞蛾优化算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1867-1872.
[5]	刘恩泽,吴文福. 基于机器视觉的农作物表面多特征决策融合病变判断算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1873-1878.
[6]	欧阳丹彤, 范琪. 子句级别语境感知的开放信息抽取方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1563-1570.
[7]	刘富, 兰旭腾, 侯涛, 康冰, 刘云, 林彩霞. 基于优化k-mer频率的宏基因组聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1593-1599.
[8]	桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605.
[9]	刘元宁, 刘帅, 朱晓冬, 陈一浩, 郑少阁, 沈椿壮. 基于高斯拉普拉斯算子与自适应优化伽柏滤波的虹膜识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1606-1613.
[10]	车翔玖, 王利, 郭晓新. 基于多尺度特征融合的边界检测算法[J]. 吉林大学学报(工学版), 2018, 48(5): 1621-1628.
[11]	赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12]	黄辉, 冯西安, 魏燕, 许驰, 陈慧灵. 基于增强核极限学习机的专业选择智能系统[J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13]	傅文博, 张杰, 陈永乐. 物联网环境下抵抗路由欺骗攻击的网络拓扑发现算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14]	曹洁, 苏哲, 李晓旭. 基于Corr-LDA模型的图像标注方法[J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15]	侯永宏, 王利伟, 邢家明. 基于HTTP的动态自适应流媒体传输算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于网格聚类的热点路径探测

Hot routes detection algorithm based on grid clustering

RICH HTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0