浮动车轨迹数据聚类的有向密度方法

doi:10.3724/SP.J.1047.2015.01152

Abstract

Abstract:

Floating car data (FCD), which is the trajectories of vehicles, are automatically collected by huge quantities of commercial vehicles which are equipped with GPS devices. Exploring and exploiting such data is essential to understand the dynamic aggregation patterns of trajectory data. However, the existing methods of spatial density clustering mainly focus on undirected data, and it is difficult to effectively find the characteristics of trajectory data. We contribute to the literatures on FCD trajectory data mining by presenting a novel method called directed density clustering method (D-OPTICS), which is formulated based on the spatial density clustering algorithm (OPTICS). In our method, the directed density is computed by a fan-shaped neighborhood region, and the density connectivity is restrained by its direction information. Then, the base clusters are generated using the curve analysis of reachable distance. Finally, the D-OPTICS cluster method is formed by the optimization method of spatial grid and cluster polymerization. This method can be naturally applied to FCD trajectory data mining, and it is also appropriate for handling other directed spatial data. It can be employed to discover the spatio-temporal distribution characteristic of traffic trajectory, and then be adopted to extract the structure information of complex road network. The experiments, with massive floating car data of Fuzhou city, show that the D-OPTICS can cluster directed spatial data effectively, and is useful to uncover the inherent distribution characteristic of the massive trajectory data. Based on its clustering result, the topology information of road network can be extracted. In this work, we extracted the topology graph for the complex road network of Fuzhou city. The experiment results also show that the algorithm can automatically determine the number of clusters, and it is found that the algorithm is not limited to globular cluster data and is capable to deal with clusters of arbitrary shapes. The key contribution of this method is that it takes the direction information into account and it can also be effective in reducing the problems caused by traditional clustering algorithms which may incorrectly merge or decompose thus naturally produce large clusters and noise data. Meanwhile, the result of performance experiments shows that, compared with DBSCAN and OPTICS, the proposed method is more suitable for large-scale data processing.

Key words: FCD trajectory data, spatial-temporal data mining, density clustering, directed density clustering, floating car data

LIAO Lvchao,JIANG Xinhua,ZOU Fumin,LI Luming,LAI Hongtu. A Fast Method of FCD Trajectory Data Clustering Based on the Directed Density[J].Journal of Geo-information Science, 2015, 17(10): 1152-1161.DOI:10.3724/SP.J.1047.2015.01152

Figures/Tables 15

Fig. 1

Fig. 2

Tab. 1

FCD trajectory data based on directed density by D-OPTICS algorithm"

输入: 浮动车轨迹数据集
输出: 不同道路、不同车道的浮动车轨迹数据簇

步骤1: 按精度要求建立空间网格

G

,并将数据按网格划分为数据子集

g i

;
repeat {
步骤2: 结合轨迹数据方向区间信息,并将数据集g_i划分为数据子集;
repeat {
步骤3: 选取一个数据子集,计算其核心距离和可达距离次序图rd_i;
} until 完成所有方向区间的

r d i

计算,方向值从大到小拼合成整个数据集的可达距离图

RD

步骤4: 根据可达距离的峰值变化生成基本簇;
步骤5: 根据道路方向变化的渐变性原则,基于凝聚层次聚类的思想,合并方向变化较小且存在共同边界粘合点的基本簇,进而得到最终的簇划分;
} until 完成所有网格数据子集的计算

Tab. 1

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Fig. 10

Fig. 11

Fig. 12

Fig. 13

Tab. 2

References 21

[1]	Steenbruggen J, Borzacchiello M T, Nijkamp P, et al.Mobile phone data from GSM networks for traffic parameter and urban spatial pattern assessment: a review of applications and opportunities[J]. GeoJournal, 2013,78(2):223-243.
[2]	Llorca D F, Sotelo M, Sánchez S, et al.Traffic data collection for floating car data enhancement in V2I networks[J]. EURASIP Journal on Advances in Signal Processing, 2010,7:1-13.
[3]	Mandir E.Potential of traffic information to optimize route and departure time choice[D]. Zugl.: Stuttgart, Universität Stuttgart, Diss., 2012.
[4]	段滢滢,陆锋.基于道路结构特征识别的城市交通状态空间自相关分析[J].地球信息科学学报,2012,14(6):768-774.
[5]	刘康,段滢滢,陆锋.基于拓扑与形态特征的城市道路交通状态空间自相关分析[J].地球信息科学学报,2014,16(3):390-395.
[6]	Ben-Akiva M E, Gao S, Wei Z, et al. A dynamic traffic assignment model for highly congested urban networks[J]. Transportation Research Part C: Emerging Technologies, 2012,24(10):62-82.
[7]	Xu R, Wunsch D.Survey of clustering algorithms[J]. Neural Networks, IEEE Transactions on, 2005,16(3):645-678.
[8]	Barthélemy M.Spatial networks[J]. Physics Reports, 2011,499(1):1-101.
[9]	Ester M, Kriegel H P, Sander J, et al.A density-based algorithm for discovering clusters in large spatial databases with noise[C]. Proceedings of Kdd-96, 1996,96(34):226-231.
[10]	Carvalho A X Y, Albuquerque P H M, De Almeida Junior G R, et al. Spatial Hierarchical clustering[J]. Revista Brasileira de Biometria, 2009,27(3):411-442.
[11]	Tvrdík J, Křivý I.Differential evolution with competing strategies applied to partitional clustering[M]. In: Swarm and Evolutionary Computation. Springer Berlin Heidelberg, 2012:136-144.
[12]	Pilevar A H, Sukumar M.GCHL: A grid-clustering algorithm for high-dimensional very large spatial data bases[J]. Pattern recognition letters, 2005,26(7):999-1010.
[13]	Sander J, Ester M, Kriegel H-P, et al.Density-based clustering in spatial databases: The algorithm gdbscan and its applications[J]. Data mining and knowledge discovery, 1998,2(2):169-194.
[14]	Fraley C, Raftery A E.Model-based clustering, discriminant analysis, and density estimation[J]. Journal of the American Statistical Association, 2002,97(458):611-631.
[15]	张震,汪斌强,伊鹏,等. 一种分层组合的半监督近邻传播聚类算法[J].电子与信息学报,2013,35(3):645-651.
[16]	Ankerst M, Breunig M M, Kriegel H P, et al.OPTICS: ordering points to identify the clustering structure[C]. ACM Sigmod Record, 1999,28(2):49-60.
[17]	Palma A T, Bogorny V, Kuijpers B, et al.A clustering-based approach for discovering interesting places in trajectories[C]. Proceedings of the 2008 ACM symposium on Applied computing, 2008:863-868.
[18]	Kharrat A, Popa I S, Zeitouni K, et al.Clustering algorithm for network constraint trajectories[M]. In: Headway in Spatial Data Handling. Springer Berlin Heidelberg, 2008:631-647.
[19]	Rocha J A M R, Oliveira G, Alvares L O, et al. DB-SMoT: A direction-based spatio-temporal clustering method[C]. Intelligent systems (IS), 2010 5th IEEE international conference, 2010:114-119.
[20]	Aggarwal C C, Yu P S.A survey of uncertain data algorithms and applications[J]. IEEE Transactions on Knowledge and Data Engineering, 2009,21(5):609-623.
[21]	吴一全,沈毅,陶飞翔.基于局部空间信息KFCM的遥感图像聚类算法[J].地球信息科学学报,2014,16(5):769-775.

序号	样本量（个）	邻域半径（m）	MinPts	DBSCAN	OPTICS	D-OPTICS
1	5000	100	10	2.14	5.73	4.31
2	10 000	50	20	4.66	13.81	9.63
3	50 000	10	20	34.86	93.56	63.29
4	100 000	10	20	214.51	221.31	136.79
5	500 000	10	20	2216.42	1286.36	739.18

A Fast Method of FCD Trajectory Data Clustering Based on the Directed Density

RichHTML

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 15

References 21

Related Articles 2

Metrics

Comments

Recommended 0

[1]	LIU Kang,DUAN Yingying,ZHANG Hengcai. A Driving Route Planning Method Based on Road Network Topological Hierarchy Expression [J]. Journal of Geo-information Science, 2015, 17(9): 1039-1046.
[2]	ZHANG Xirui,FANG Zhixiang,LI Qingquan,LU Shiwei. A Spatio-temporal Analysis on the Heterogeneous Distribution of Urban Road Network Capacity Based on Floating Car Data [J]. Journal of Geo-information Science, 2015, 17(3): 336-343.