一种基于空间编码技术的轨迹特征提取方法  

A trajectory feature extraction approach based on spatial coding technique

作　　者：乔少杰 韩楠[2] 李天瑞[3] 熊熙 元昌安[4] 黄江涛[4] 王晓腾[3] 

机构地区：[1]成都信息工程大学网络空间安全学院,成都610225 [2]成都信息工程大学管理学院,成都610103 [3]西南交通大学信息科学与技术学院,成都611756 [4]广西师范学院计算机与信息工程学院,南宁541004

出　　处：《中国科学：信息科学》2017年第11期1523-1537,共15页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:61772091;61100045;61363037);教育部人文社会科学研究规划基金(批准号:15YJAZH058);教育部人文社会科学研究青年基金(批准号:14YJCZH046);四川省教育厅(批准号:14ZB0458);广西自然科学基金重点项目(批准号:2014GXNSFDA118037);成都信息工程大学引进人才科研启动项目(批准号:KYTZ201715;KYTZ201750)资助

摘　　要：GPS数据存在位置精度偏差而且易受噪声干扰,大规模数据挖掘前需要进行轨迹特征提取.本文提出基于Geo Hash的空间编码技术Geo Hash Tree对时空点进行索引,提高邻域轨迹点查询效率.将Geo Hash Tree应用于轨迹聚类,提出一种改进的基于密度的轨迹聚类算法,使聚类中最近邻点查询时间复杂度由O(n^2)降为O(n log n).以提取角度变化点为基础,通过聚类对角度变化点进行深层次特征提取,实现特征点的准确识别.大量真实GPS数据上的实验结果表明:相比传统算法,基于Geo Hash Tree空间索引结构的轨迹聚类算法时间开销平均提升90.89%,同时保证聚类结果的准确性.可视化结果表明:在大规模数据集上,轨迹特征提取方法能够准确找到角度变化点,有效挖掘各类特征点.此外,算法不依赖路网数据,可根据路网实时改变时新增的轨迹数据进行动态更新.GPS data often have position deviations in precision and are apt to be affected by noise; hence, it is essential to extract features from trajectories before performing large-scale data mining. A Geo Hash-based spatial coding technique called Geo Hash Tree was used to index spatiotemporal trajectory points in order to improve the efficiency of nearest-neighbor search. The Geo Hash Tree was applied in trajectory clustering and an improved density-based clustering algorithm was proposed to reduce the time complexity of nearest-neighbor search from O（n^2） to O（n log n）. After extracting trajectory points with changing angles, the proposed clustering approach was employed to achieve deep-level feature extraction on trajectory points with changing angles, which aims to accurately identify feature points. Extensive experiments are conducted on real GPS data and the results demonstrate that the proposed trajectory-clustering algorithm based on the Geo Hash Tree spatial index structure can improve time performance by an average of 90.89% as well as guarantee the accuracy of clustering compared with the traditional clustering method. The visualization results show that the trajectory feature extraction approach can effectively find trajectory points with changing angles and discover a varying types of feature points from large-scale data sets. In addition, the proposed approach does not depend on road network data and can dynamically update with new incoming trajectory data as road networks change in real time.

关 键 词：轨迹 大数据 编码方法 聚类分析 特征提取 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]