EN中文

Journal of Geo-information Science >

2015 , Vol. 17 >Issue 10: 1152 - 1161

DOI: https://doi.org/10.3724/SP.J.1047.2015.01152

Orginal Article

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

  • LIAO Lvchao , 1, 2 ,
  • JIANG Xinhua , 1, 2, * ,
  • ZOU Fumin 2 ,
  • LI Luming 1 ,
  • LAI Hongtu 2
Expand
  • 1. School of Information Science and Engineering, Central-South University, Changsha 410075, China
  • 2. Fujian Key Laboratory for Automotive Electronics and Electric Drive , Fujian University of Technology, Fuzhou 350108, China
*Corresponding author: JIANG Xinhua, E-mail:

Received date: 2015-04-20

  Request revised date: 2015-05-18

  Online published: 2015-10-10

Copyright

《地球信息科学学报》编辑部 所有
Fold

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

Cite this article

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

1 引言

城市交通运行管理往往需要准确的基础地理数据支持,但由于新增道路、交通状态及道路交通管理的时变性（如交通拥堵、交通流量的动态变化等）,使得路网结构及车道间的通行阻抗与限制都会动态变化,对于这种变化只能通过地图数据的更新,获得部分静态变化信息。如何有效地实时获取其动态变化信息,则是交通信息服务领域的主要难题之一[1]。
近年来,随着卫星定位技术与位置服务的迅速发展,越来越多的车辆安装了GPS/北斗等定位功能的装置,这些车辆周期性上报其位置、方向及速度等信息,形成海量的浮动车轨迹数据。这些轨迹数据蕴藏了交通地理模式和用户驾驶行为习惯等丰富的潜在信息,通过充分挖掘这些潜在的、隐藏的信息,有望快速识别交通路网结构,甚至提取其独立的车道实体,发现车道之间的连通关系[2]、通行阻抗与限制[3]等交通地理信息,进而提取城市复杂路网结构信息[4]及路网拓扑特征[5],并生成交通道路网络模型[6],为交通路网规划与优化提供实时动态的地理数据支撑。
为了能从海量的浮动车轨迹数据中挖掘潜在的交通地理特性,迫切需有效的聚类方法分析其空间有向数据的相似与聚集特性,以发现浮动车轨迹数据的空间分布模式和交通地理特性之间有趣的相关性。尽管目前国内外相关研究提出了一系列的空间密度聚类算法,但这些研究主要应用于空间无向数据的聚类分析[7],而在各类轨迹数据中,方向信息隐含着重要的内在特性,其可表明数据的先后关系,也可为邻居数据的查找提供具有实际物理意义的搜寻方向与搜寻范围。同样,对于浮动车轨迹数据而言,行车方向是其重要信息之一,采用无向空间聚类方法难以深入挖掘相关的交通地理特性,如车道实体及其转向连通关系等交通路网模型 信息[8]。
本文提出的有向密度的浮动车轨迹数据快速聚类方法,通过福州市实际的浮动车数据实验分析表明,该方法可在没有地图背景数据等先验知识的情况下,实现浮动车轨迹数据的车道级聚类。并通过对各类所代表的模式进行解读从而获得道路的车道信息,以动态分析路网结构特征及其变化情况,有利于交通路网规划及其运行管理,更好地为用户提供主动交通信息服务。

2 快速聚类的相关工作

空间聚类分析是将空间数据集按一定的规则,划分成若干个有意义或有用的类簇,并使同一类簇数据间的相似度最大,而不同类簇间的数据相似度最小[9],其主要方法有层次聚类[10]、划分聚类[11]、网格方法[12]、密度方法[13]及模型方法[14]5大类。其中,层次法及划分法等采用全局固定的阈值聚类,较适用于空间目标分布比较均匀的场景,对于非均匀空间分布的目标对象,则容易探测到其空间分布较密集的数据簇,而不易发现空间分布稀疏区域数据间的相互关系,容易产生大量的孤立点,难以有效挖掘空间数据分布的潜在特征,不利于揭示空间数据的内在规律[15]。
密度聚类算法主要有DBSCAN[9]与OPTICS[16]算法等,其对于非均匀分布数据的聚类质量较好,可较好地避免“噪声”数据的干扰,发现任意形状的类,克服其他距离度量方法只能发现类圆形聚类的缺点。
DBSCAN算法是评估整个数据集中每一个数据对象的邻域关系,并根据其邻域内的对象数目定义核心点分布及其密度相连等数据相关性,通过密度可达实现空间对象的聚类处理。文献[17]提出了一种基于浮动车轨迹数据的兴趣点发现方法,以提取驾驶员的驾驶兴趣区域信息;文献[18]提出了一种在交通路网约束条件下进行轨迹数据聚类的NETSCAN算法,可得到路网之间的连通关系。而文献[19]则对移动目标对象在时空关键点之间的移动行为特征进行了聚类研究。
然而,DBSCAN算法在运行中需要设定最大邻域半径及最小邻居数等参数,而不同的实际数据往往需要不同的参数,无形加大了应用难度,且参数的设置通常依赖经验,不够客观。为此,文献[16]提出OPTICS空间密度聚类算法,其无需提前设定参数,且能较好地适应数据分布的空间分异性,但其在聚类处理过程中,仍通过单一的全局距离参数评估数据之间的关系,而全局距离参数的细微变化可能影响聚类结果,甚至导致聚类结构产生巨大改变,且参数的单一性仅反映单一层面的数据特征,无法从微观到宏观等多层面来综合评估数据特征。
另外,尽管基于密度的聚类方法可发现任意形状的空间数据类,但受浮动车轨迹数据的异构性(不同车辆可能采用不同的采集频率等)、不可靠性(用户的轨迹数据包含大量噪声和不精确数据)、不完整性(用户难以对轨迹数据进行持续不断的记录)等特点的影响,是一种典型的不确定数据[20],传统的密度方法,难以有效进行浮动车轨迹数据的聚类挖掘分析[21]。尤其是浮动车轨迹数据具有有向特性,完全通过无向邻域范围来进行数据距离评估,无法充分挖掘其数据的潜在特性。
为此,本文在OPTICS算法基础上,提出了有向密度的浮动车轨迹数据快速聚类方法。该方法可有效整合浮动车轨迹数据的方向信息,并通过空间矢量数据的有向密度估计,以实现浮动车轨迹数据的快速聚类分析。实验分析表明,本算法能适应浮动车轨迹数据的空间分布非均匀特性,且能有效揭示路网约束下的浮动车轨迹数据聚集模式,算法的聚类结果较为稳定。

3 定义与建模

定义1(浮动车轨迹数据)：在配置卫星定位及通信装置的车辆上,定期采集其位置、时间及速度等信息,构成了有向的浮动车轨迹数据 P → i ,则有：
P → i = { < x i , y i > , t i , v i , d i } （1）
式中, < x i , y i > 为空间位置信息; t i 为数据的时间戳; v i 为车辆的瞬时速率; d i 为车辆的当前方向信息。
定义2(计算空间)：将整个待计算区域的经度区间 [ Ln g min , Ln g max ] 与纬度区间 [ La t min , La t max ] 所围成的区域称为计算空间S,可表示为：
S = ∫ Ln g min Ln g max ( La t max - La t min ) × d Lng （2）
式中, d Lng 为经度方向的微分量。
定义3(空间网格)：将整个计算空间 S 按经纬度划分为等分 m 行 n 列形成(m×n)个网格,称为空间网格 g ( m , n ) ,所有的网格构成空间网格集 G ,则有：
G = ⋃ i = 1 m × n g i （3）
式中, S ≡ G ,且对于任何 i , j ( i ≠ j ) , g i ⋂ g j = ϕ 。同时,给定计算空间中的任意位置 p ( x , y ) ,则 ∃ g i ↦ p ∈ g i 。
定义4(网格空间索引)：将整个空间网格集从 g 0,0 到 g M , N ,按经度优先原则创建网格序号,并称为网格空间索引号 i ,则有:
i = m × N + n （4）
式中,M、N分别为网格空间的总行数与总列数,m、n分别为当前网格的行列数。
定义5(有向空间邻域)：任一数据点在指定方向区间中其邻近范围内数据构成的子集,为有向空间邻域（也称为扇形空间邻域）,即设有浮动车轨迹数据集 P 及其任一数据点 p i ,其空间邻域 N ε → ( p i ) 可表示为：
N ε → ( p i ) = { p j : d ( p i , p j ) < ε , p i , p j ∈ P → , ∠ ( p i → , p j → ) < σ } （5）
定义6(有向空间密度)：任一数据点的有向空间邻域范围内的数据量,为该位置的有向空间密度 ρ ( p i ) ,则有：
ρ ( p i ) = | N ε → ( p i ) | （6）
定义7(有向密集点)：有向空间密度大于设定阈值 Φ 的数据点为有向密集点,并记由有向密集点构成的有向数据集合为 P d → ,由数据集 P 中的所有非有向密集点构成集合为 P nd → ,则有：
P d → = { p i : ρ ( p i ) > Φ , p i ∈ P } （7）
P nd → = P \ P d → （8）
定义8(有向边界点)：任一非有向密集点的数据点,若其邻域中存在有向密集点,则称该数据点为有向边界点 P bd → ,则有：
P bd → = { p i : p i ∈ P nd , ∃ p j ∈ P d , p j ∈ N ε → ( p i ) } （9）
定义9(边界粘合点)：因对数据进行网格化划分,将密集点划分为若干网格后,产生的网格边界的非密集点称为边界粘合点 P ad ,则有：
P ad = { p i : p i ∈ P d , p j ∈ P / ( l ) , p i ∈ N ε → ( p j ) } （10）
定义10(有向噪声点)：将有向数据集中既不属于有向密集点,也不属于有向边界点与边界粘合点的数据点为有向噪声点 P noi → ,则有：
P noi → = P \ ( P d → ⋃ P bd → ⋃ P ad → ) （11）
定义11(直接有向密度可达)：设有向数据集中的任意2个有向数据点 p i 与 p j ,若满足 p i ∈ P d → 且 p j ∈ N ε → ( p i ) ,则称为 ( p i → p j ) 为直接有向密度可达(图1),并表示为DirReach (pi, pj),则有：
Dir Re a ch ( p i , p j ) ⇔ p i ∈ P d ∧ p j ∈ N ε → ( p i ) （12）
定义12(有向密度相连)：设有数据集 P 中的密集数据点 d 1 , d 2 , d 3 , ... , d ( m ) ,若 d ( i + 1 ) 从 d ( i ) 直接密度可达且具有相同的方向,其中, i = 1,2 , 3 , ... , m ,则称 d ( m ) 从 d 1 有向密度相连(图2)。由于数据点的有向性,其有向密度相连具有非对称性。
Fig. 1 Directed directly density-reachable

图1 直接有向密度可达

Fig. 2 The diagram of directed connected-density

图2 有向密度相连示意图

定义13(有向核心距离)：在给定有向邻域参数 ε 、 σ ,以及有向密度参数 Φ 的情况下,使有向数据集 P 中的任一数据点 p i 成为有向密集点的最小有向邻域半径为 p i 的核心距离 cd ( p i ) ,则有：
cd ( p i ) = eudist ( p i , N ε Φ → ( p i ) ) （13）
式中, N ε Φ → ( p i ) 为在邻域顺序数据点中,使密度达到密集数据阈值的最邻近数据点,核心距离主要在 p i 为核心点时有意义,且有 cd ( p i ) < ε ,若为非核心点,则其核心距离不存在。
定义14(有向可达距离)：在给定有向邻域参数 ε ,以及空间密度参数 Φ 的情况下,使有向数据集 P 中的任一数据点 p i 成为有向密集点,且 p i 与 p j 之间为直接有向密度可达 DirReach ( p i , p j ) 的最小邻域半径值为 p j 对于 p i 的可达距离 rd ( p i ) ,则有：
rd ( p i ) = min { η : p j ∈ N η ( x ) , | N η → ( x ) | ≥ Φ } （14）
基于以上定义,通过分析数据间的最小有向核心距离和最小有向可达距离值的关系,将进一步为实现有向数据的快速聚类提供了支撑。

4 基于有向密度的浮动车轨迹快速聚类算法

在浮动车轨迹数据中,行驶方向属性是其重要信息,也是分析交通驾驶行为特征的主要依据之一,因此,有向密度聚类方法既有利于揭示浮动车轨迹数据分布的聚簇特性,也有利于从浮动车轨迹数据中挖掘城市交通流的行为特性。本文提出的有向密度的快速聚类方法（D-OPTICS）,在计算邻域空间数据时,综合考虑了空间距离特性与方向 特性。
D-OPTICS算法首先生成代表有向密度聚类结构的一个参数化的数据集合排序,即计算每个空间数据的最小有向核心距离和最小有向可达距离值,并根据高密度聚类优先的排序原则生成参数化序列图[16]（有向可达曲线图）,根据有向可达图的峰值变化情况,生成局部聚类基本簇,并进而根据边界粘合方法将基本簇聚合成聚类簇。D-OPTICS算法可形式化描述如表1所示。
Tab. 1 FCD trajectory data based on directed density by D-OPTICS algorithm

表1 基于有向密度的浮动车轨迹数据聚类D-OPTICS算法

输入: 浮动车轨迹数据集
输出: 不同道路、不同车道的浮动车轨迹数据簇
步骤1: 按精度要求建立空间网格G,并将数据按网格划分为数据子集gi;
repeat {
步骤2: 结合轨迹数据方向区间信息,并将数据集gi划分为数据子集;
repeat {
步骤3: 选取一个数据子集,计算其核心距离和可达距离次序图rdi;
} until 完成所有方向区间的rdi计算,方向值从大到小拼合成整个数据集的可达距离图RD
步骤4: 根据可达距离的峰值变化生成基本簇;
步骤5: 根据道路方向变化的渐变性原则,基于凝聚层次聚类的思想,合并方向变化较小且存在共同边界粘合点的基本簇,进而得到最终的簇划分;
} until 完成所有网格数据子集的计算
D-OPTICS的基本思路是在行车方向等条件约束的情况下,寻找有向密度相连的浮动车轨迹数据,以及这些数据所在稠密区域,整个聚类过程主要分为3步。

4.1 计算有向邻域密度

为了减少计算复杂度,在进行有向密度计算时,将方向值离散化为若干个值,以福建省运营车辆安全管理平台的浮动车轨迹数据为例,将浮动车轨迹数据的方向信息离散化为0-7共8个值,正北方向为0,按顺时针转45°其方向值增加1。通过将方向值的离散化处理,在计算有向密度时,仅需要计算相同方向区间的空间数据密度（图3）,而避免了邻域内其他方向数据的距离计算,同时方向信息的离散化处理可在接收数据时进行预处理,有效简化了系统的计算复杂度。
Fig. 3 The diagram of FCD trajectory data based on directed density

图3 浮动车轨迹数据有向密度图

考虑浮动车轨迹数据分布的密度不均性,难以通过统一的参数进行有效处理,为此,通过计算数据之间的有向可达距离,实现数据之间的有向密度相连,并生成一个代表数据聚类结构的有向密度的可达距离序列。

4.2 生成基本簇

可达距离曲线直观地呈现了对象间的距离分布情况,同时,可达距离曲线对输入参数邻域距离 ε 和最小簇规模MinPts不敏感,不同的输入参数,图形形状基本相同。为了提高系统的鲁棒性,本文通过可达距离曲线分析数据的聚类结构。
可达距离曲线（图4）反映了相邻点之间的距离信息,曲线的凹陷区域说明数据点之间比较密集,而突起部分则表明数据之间的距离较大,可用于数据簇分割。考虑不同数据的有向性,提取超过阈值的局部数据峰值作为数据分割点,将数据按方向区间分类后,构造有向可达距离曲线,并在方向之间构造曲线峰值,提高数据分类效率。
Fig. 4 The diagram of reachable distance sequence

图4 可达距离序列示意图

4.3 簇聚合

有向密度的浮动车轨迹数据聚类,既要考虑方向的约束性,又要顾及空间簇整体特征,从整体上顾及路网的形状。同一个基本簇的数据方向均属于同一个方向区间,然而,随着道路的变化,方向也会发生变化,使得同一道路的数据被划分为多个数据簇,因此,基于道路约束的数据聚类还需将数据基本簇进行聚合处理。
在数据簇聚合过程中,需考察簇之间的邻近度,因此,本文在有向密度可达的基础上,定义了有向簇的凝聚系数,以描述不同有向基本簇之间的凝聚力。对于一个给定道路的浮动车轨迹数据集,可设其所有数据实体被划分为 N 个空间簇,分别记为 C 1 , C 2 ,…, C N ,并定义任意2个簇间的凝聚系数为 Cohesion ( C i , C j ) 。
Cohesion ( C i , C j ) = ( 1 + cosθ 2 ) × Dir Re a ch ( p i , p j ) （15）
式中,参数 θ 为两簇间的方向夹角;参数DirReach ( p i , p j ) 为其直接有向密度可达情况,取值为0或1。凝聚系数取值区间为[0,1],算法每次合并2个凝聚系数最大的2个簇,直到满足预设的聚类空间。

5 系统实验与分析

本文的实验运行环境是Centos 5.8操作系统,实验工作站的硬件配置是Intel(R) Xeon(R) CPU E5630@2.53GHz八核CPU,内存为32GB,算法采用Python语言编写。

5.1 算法实验数据集

本文采用福建省福州市的浮动车轨迹数据作为算法实验测试数据集,数据主要包括车辆ID、经纬度、速度、方向及车辆类型等字段信息。其中,方向被离散化为8个方向值,分别从0-7,0代表正北方向,顺时针转45°方向值加1。
整个数据集由2014年5月1日的浮动车轨迹数据组成,数据集覆盖地理空间的经度范围为[119.113,119.684],纬度范围为[25.904,26.155],区域面积约为1430 km2,覆盖了福州市主城区及周边区域,数据集包括出租车、两客一危,重型货车、半挂牵引车等11类共28 916辆,包含了约2300万条浮动车位置信息,浮动车轨迹总里程约485万 km。

5.2 数据预处理

浮动车轨迹数据中的方向及定位信息主要通过GPS计算获得,但受定位失败等因素影响,容易出现异常数据。以其中某一天的数据为例进行不同方向的数据统计分析（图5）,发现方向为0的数据远远大于其他方向的数据,说明方向值为0的数据中存在大量的异常数据。
Fig. 5 The statistical chart of direction data

图5 方向数据统计图

为了避免这些噪声数据对聚类算法的影响,本文首先对数据集进行清洗处理,具体包括清洗方向异常的数据及定位异常的数据。其中,车辆定位信息的异常主要通过求取定位信息一阶差分的标准差(式(16))进行判断。
σ i = 1 N i ∑ j = 1 N i Δ p j 2 - μ ) （16）
式中, N i 为第 i 辆浮动车的FCD数量; Δ p j 为第j个经纬度一阶方差值; μ 为其一阶方差的均值。对 σ i 值大于设定阈值的异常数据进行滤除。同样,对于方向的异常值,首先通过经纬度值的方差值判断其活动范围,对于活动范围大的车辆数据,若其方向值的标准差接近0,则可判断为方向异常数据。
通过对数据集进行噪声数据清洗,共滤除方向异常的车辆2493辆,GPS定位异常的数据780辆,清洗滤除的车辆数据占总数据集的11.3%,通过清洗处理后,各个方向的数据基本接近均衡。

5.3 聚类效果实验分析

为了避免DBSCAN、OPTICS等传统密度聚类算法在两两计算距离值时,难以支持大规模数据处理的问题,本文首先将整个地理空间划分为一系列的空间信息网格。实验中以长宽均为1 km的长度进行空间网格划分,将空间信息网格投影到谷歌地球可进行直观的可视化分析（图6）。
Fig. 6 The image of spatial information grid

图6 空间信息网格图

通过空间信息网格的划分,密度计算仅需在空间网格内部及其相邻网格的数据间进行,其中相邻网格包括具有共同边或具有共同顶点的网格,从而避免了在整个数据集中两两计算,有效减少了算法的计算量,提高了系统的处理性能,为大规模浮动车轨迹数据的快速处理提供了可能。
基于划分的空间网格,通过D-OPTICS算法,对以上经过清洗的浮动车轨迹数据进行聚类处理,可得到浮动车轨迹数据分类信息,将各类聚类道路投影到空间平面得到路网空间平面图(图7)。从图7可知,交通数据轨迹基本覆盖了整个福州市区道路、绕城高速及周边其他道路与桥梁等。
Fig. 7 The image of polymeric road network (for Fuzhou city)

图7 交通路网聚合图（福州市）

对每一空间网格的数据进行有向可达距离计算,以评估有向数据间的距离关系,进而可得到网格数据的有向可达距离图（图8）。图8中几个主要峰值点是数据分类的主要分裂点,而曲线的波谷区域是数据的主要密集区域。
Fig. 8 The diagram of directly reachable distance (single grid)

图8 有向可达距离图（单网格）

提取数据聚类后的局部图,并将不同分类以不同颜色表示,可得到浮动车轨迹数据的D-OPTICS的聚类效果图（图9）。从图9可知,D-OPTICS算法在聚类处理过程中,充分体现了数据的方向特性,有利于提取路网结构信息。
Fig. 9 The diagram of clustering based on D-OPTICS algorithm

图9 D-OPTICS聚类效果图

为了对比D-OPTICS与DBSCAN与经典OPTICS算法的差异,提取任一典型区域（平行车道）的浮动车轨迹数据,对3个算法进行了实验分析（图10）。其中,DBSCAN的eps参数分别设置为0.004与0.005（经纬度值,实际地理空间距离分别约40 m与50 m）, MinPts设置为2。
Fig. 10 Comparison of the resultant clustering effects between D-OPTICS, DBSCAN and OPTICS algorithms

图10 D-OPITCS与DBSCAN、OPTICS算法聚类效果对比图

实验结果表明,DBSCAN受参数的影响很大,当eps为0.004时(图10(c)),产生大量的聚类簇,每个簇之间没有实质的物理意义,而当eps为0.005时（图10(d)）,只生成一个聚类簇,无法有效区分不同车道的浮动车轨迹数据。而OPTICS算法尽管避免了参数设置的影响,但数据仍都集中在一个聚类簇(图10(b))。采用D-OPTICS算法则可有效地将浮动车轨迹数据,按不同车道分为相应的簇（图10(a)）。
为进一步测试D-OPTICS各类路网的聚类分析能力,分别对在平行道路、非完全平行道路、交叉道路及分支道路等交通路网主要场景进行聚类分析（图11）。其中,图11(a)为低密度的场景,图11(d)为高密度的场景。从图11可知,D-OPTICS算法可很好地结合方向与密度信息,实现各种道路环境的浮动车轨迹数据的聚类,同时,算法既能在空间局部密度较高区域发现浮动车轨迹数据的聚类信息,也能适用于密度较低的路网场景。
Fig. 11 The diagrams of clustering based on D-OPTICS algorithm

图11 D-OPITCS算法聚类效果图

通过D-OPTICS聚类分析,可从浮动车轨迹数据发现路网信息,以及路网的新增道路信息及其单向限行等道路通行属性。图12为针对新增道路发现的实验分析图,图12(a)为旧版的交通道路矢量底图,鉴此,对浮动车轨迹数据进行D-OPTICS聚类分析,并将聚类簇与底图进行匹配,没有相应矢量底图的聚类簇即为新增道路（图12(b)）。实验表明,D-OPTICS算法,可在海量的浮动车轨迹数据中发现有效路网信息。
Fig. 12 The diagrams of new road detection experiment

图12 新增道路检测实验图

同时,进一步根据D-OPTICS算法聚类结果,以每个聚类数据集生成一条有向边,并以数据集与数据集之间的交点作为节点,则可对复杂路网快速构建其拓扑结构图。图13为生成的福州市区路网有向拓扑结构图。
Fig. 13 The road network topology of Fuzhou urban area

图13 福州市区路网拓扑结构图

5.4 系统性能测试

为了测试本算法的系统处理性能,本文通过提取实验数据集中随机抽取不同样本量的数据子集进行实验,并横向对比DBSCAN及OPTICS等主要的传统空间密度聚类算法(表2)。
Tab. 2 The comparison of algorithms’ performance

表2 算法性能测试对比表

序号 样本量（个） 邻域半径（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
从实验测试可知,在小数据集时,DBSCAN算法的处理性能最佳,D-OPTICS算法其次,OPTICS算法最低,而当数据达到一定规模时,DBSCAN的处理效率急剧下降,OPTICS出现小幅的非线性下降,而D-OPTICS的则保持相对的线性稳定。因此,D-OPTICS算法能更好地支持大规模的浮动车轨迹数据处理要求,同时通过其方向特性,聚类的结果更符合其空间数据的内在分布规律。

6 结束语

时空轨迹数据的聚类分析,是数据挖掘领域中一项重要的研究课题。针对浮动车轨迹数据的有向性、不连续性和非稳态分布等特点,本文提出的有向密度的浮动车轨迹数据快速聚类算法,可有效结合空间数据的方向信息,并通过空间矢量数据的有向密度估计,以实现浮动车轨迹数据的快速聚类分析,算法能自动确定簇数量并发现任意形状簇,而不再局限于超球状的簇数据,并克服传统空间密度聚类算法无法处理不同数据簇的交叉重叠问题。同时,通过整合方向信息,也可有效减少因传统聚类算法可能会错误地合并或分解自然簇而产生大量噪声数据的问题。
以浮动车轨迹数据进行实验分析表明,本算法能适应浮动车轨迹数据的空间分布非均匀特性,并能有效揭示路网约束下的浮动车轨迹数据聚集模式,以提取复杂路网的结构信息,且算法的聚类结果较为稳定。

The authors have declared that no competing interests exist.

References

Publishing order | Descend order by publishing year | Descend order by cited within
[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.

Options
Outlines

/

〈 〉