一种基于移动对象时空信息轨迹分段聚类的方法

摘要

本发明公开了一种基于移动对象时空信息轨迹分段聚类的方法，该基于移动对象时空信息轨迹分段聚类的方法包括：引入时间、速度和方向三个属性，并给出他们的相似度计算公式来分析移动对象轨迹内外部结构；首先根据轨迹的空间密度将轨迹划分成若干轨迹段，然后通过计算各轨迹段在空间、时间、速度和方向上的差异来判断轨迹段的相似度，最后，基于第一次聚类结果，将非显著簇中的轨迹段删除或并入邻近的显著簇，使聚类空间形态体现出全局性的移动规律。本发明提高了聚类效果，具有更强的应用价值，采用空间四叉树对轨迹段进行索引，在大规模轨迹数集环境下极大提升聚类效率，可对轨迹进行有效聚类。

说明书

技术领域

本发明属于轨迹地理坐标值进行聚类技术领域，尤其涉及一种基于移动对 象时空信息轨迹分段聚类的方法。

背景技术

时空轨迹是移动对象的位置和时间的记录序列，包括了时间、位置、速度 等基础信息。随着移动互联网、定位系统等技术的快速发展，在交通、物流等 应用领域，通过智能移动终端能够及时收集大量的时空轨迹(Trajectory)数据。 作为一种重要的时空对象数据类型和信息源，时空轨迹数据蕴含着丰富的知识， 其应用范围涵盖了人类行为、交通物流、应急疏散管理、动物习性和市场营销 等诸多方面。聚类分析是对数据对象进行分组，使得同一组中对象之间具有较 高的相似度，而不同组中的对象具有较低的相似度。轨迹聚类的目标是寻找那 些具有相同运动模式的轨迹，通过对轨迹内部运动模式和特征信息的分析，确 定轨迹间的相似程度，然后将相似程度较高的轨迹归为一类。通过对各种时空 轨迹数据进行聚类分析，提取时空轨迹数据中的相似性与异常特征，有助于发 现其中有意义的模式。

近年来，世界各国的研究人员提出了多种轨迹聚类方法，，如K-MEANS、 BIRCH，DBSCAN、OPTICS、STING等[5]。KREVELD等[6]首次将轨迹的 时间依赖关系引入到形状依赖的轨迹分析中，KNORR等将轨迹的起始位置、 方向等要素引入轨迹间的相似度计算。张延玲等通过轨迹聚类得到运动模式， Ping等提出了路网空间下基于密度的轨迹聚类方法，该方法首先根据移动对象 经过的道路计算出繁忙路径，然后根据用户设置的密度参数对子轨迹进行聚类。 Sang等提出首先计算重叠路段长度的相似度，然后进行聚类。Ying等提出了 在路网约束下综合考虑时间和空间约束的轨迹相似性度量方法，并应用于轨迹 聚类。这些方法大多是基于整条轨迹采样点空间信息进行聚类，没有全面考虑 轨迹的局部特征和移动属性，难以匹配路径较长或较复杂的轨迹。

目前直接以轨迹地理坐标值进行聚类，导致聚类效果降低。

发明内容

本发明实施例的目的在于提供一种基于移动对象时空信息轨迹分段聚类的 方法，旨在解决目前直接以轨迹地理坐标值进行聚类，导致聚类效果降低的问 题。

本发明实施例是这样实现的，一种基于移动对象时空信息轨迹分段聚类的 方法，该基于移动对象时空信息轨迹分段聚类的方法包括以下步骤：

第一步，轨迹和轨迹段：

定义1轨迹：三维空间中的有序点集称为轨迹，轨迹TR_i定义：TR_i={p₁， p₂，...，p_k}，其中p_k＝{x_k，y_k，t_k}，分别代表该点的二维空间坐标和采用时间，不同 轨迹长度可能不一样；

定义2轨迹段：为TR_i内连续的部分三维点集，如：SubTrajectory_s={p₁,...， p_k}(1≤s≤k)，k为该轨迹段所属轨迹的采样点总数；

第二步，Hausdorff距离：给定两个轨迹段P和Q，使用Hausdorff距离进 行相似性测量：

$\left(\begin{array}{c}H(P,Q)=\max \{h(P,Q),h(Q,P)\}\\ h(P,Q)=\underset{p\in P}{\max }\underset{q\in Q}{\min }\left\{d(p,q)\right\}\\ h(P,Q)=\underset{p\in P}{\max }\underset{q\in Q}{\min }\left\{d(p,q)\right\}\end{array}\right)---\left(1\right)$

其中，d(p，q)为点p和q之间某个属性上的距离公式，Hausdorff距离用以量 度轨迹段之间的空间和时间差异度；

第三步，轨迹段速度：

通过如下公式得到每个采样点速度：

$v_p=\frac{\mathrm{dis}\tan \mathrm{ce}(p_{-},p)+\mathrm{dis}\tan \mathrm{ce}(p,p_{+})}{t_{p_{+}}-t_{p_{-}}}---\left(2\right)$

其中，p_-为p点之前的相邻采样点，p₊为p点之后的相邻采样点，和分 别代表p_-和p₊的采样时间；

第四步，轨迹段方向

轨迹段的总体移动方向之间主要方向差别，运动方向角：其中，(x_s，y_s)轨迹段起点，(x_e，y_e)为轨迹段终点；

第五步，轨迹段邻域：

定义3轨迹段L_i的ξ邻域N_x(L_i)：N_x(L_i)＝{L_i危D|d（L_i，L_j)l}；

其中，D为所有轨迹段数据集合，轨迹段领域用以在DBSCAN轨迹密度聚 类中，判断每个轨迹段的当前空间密度，进而将空间密度较大的轨迹段聚为同 一组；

第六步，轨迹分割；通过采样点在某个时间段内的速度变化来分割轨迹；

定义4断点：假设存在一轨迹段，位于轨迹段上的任何两点之间的距离不 超过阈值ε，并且这段子轨迹的采样点数s大于阈值E，则将这段子轨迹中的第 [s／2]个点设置为断点，同时将位于段子轨迹上其余的点删除；如果一条轨迹上 有t个断点，则轨迹被分割为t+1个轨迹段；

第七步，轨迹段相似性比较：轨迹段之间的相似性通过轨迹段之间的差异 度获取，包括：空间差异度、时间差异度、方向差异度和速度差异度；

第八步，VOC-TC算法：对轨迹进行分割后，再利用DBSCAN密度算法， 采用距离公式，对轨迹段进行聚类，设聚类簇C中包含的轨迹数目为簇基数n_cb， 簇基数n_b与聚类中轨迹段数目n_c之比为簇显著度n_cs，给定阈值τ和γ，进行如下 定义：

定义5显著簇：C_sig＝{C|C吻O n_cb>t?n_cs g}，其中，O为第一次聚类的结 果集，即簇基数n_b高于τ且簇显著度n_s高于γ聚类称为显著簇；

定义6非显著簇：C_unsig={C|C吻O C□O_sig}，其中，O_sig为显著簇集合，即 显著簇之外的聚类都为非显著簇；

进行第二次聚类，将第一次聚类中非显著簇删除，同时将该其中包含的轨 迹段归并到离其最距离小于阈值μ且包含同一条轨迹的聚类中，最终获取那些能 反映主题变化的显著簇，非显著簇的轨迹段归并到其他簇不会改变这些簇中的 轨迹数量。

进一步，在第三步中，进行Hausdorff距离进行相似性测量的计算公式利用 移动对象在三个连续采用点的平均速度作为当前点的速度，轨迹段的速度通过 该轨迹段中的最小速度、最大速度和平均速度来衡量：

${\bar{V}}_{\mathrm{SubTrajectory}}=(1-w_m-w_a)v_{\min }+w_m{v}_{\max }+w_a\frac{v_i+v_{i+1}+...+v_j}{j-i+1}$

其中，ω_m+ω_a≤1，v_min为轨迹段中速度最低值，v_max为轨迹段中速度最高值， i和j分别为该轨迹段采样点的下标。

进一步，在第七步中，空间差异度与时间差异度采用Hausdorff距离计算得 到，方向差异度和速度差异度直接采用属性差值绝对值表示即可；结合得到一 个统一的表达轨迹段相似性公式：

subDis＝w_s创spatialDis+w_t tempoDis+w_o创OrientDis+w_v velocityDis，

且w_s+w_t+w_o+w_v=1

其中，spatialDis、tempoDis、OrientDi和seolocityDis分别为轨迹段之间的 空间差异度、时间差异度、方向差异度和速度差异度，轨迹段相似性公式为：

subSIM=1-tanh(subDis)

其中，tanh(subDis)为三角函数归一化公式。

进一步，在第八步中，从不同的聚类开始进行顺序显著簇的判断和轨迹段 归并，最终会得到相同的聚类形态，计算每个轨迹段邻域的时间复杂度为O (n²)，采用四叉树空间索引，将时间复杂度降为O(nlogn)。

本发明提供的基于移动对象时空信息轨迹分段聚类的方法，通过引入时间、 速度和方向三个属性，并给出他们的相似度计算公式来分析移动对象轨迹内外 部结构。首先根据轨迹的空间密度将轨迹划分成若干轨迹段，然后通过计算各 轨迹段在空间、时间、速度和方向上的差异来判断轨迹段的相似度，最后，基 于第一次聚类结果，将非显著簇中的轨迹段删除或并入邻近的显著簇，使聚类 空间形态体现出全局性的移动规律。本发明首次对不重要聚类中的轨迹段进行 适当处理，或者将其并入其他邻接的重要聚类，或者作为噪音删除，从而提高 了聚类效果，具有更强的应用价值，在进行聚类时需获取每条轨迹的邻近轨迹 段，计算量比较大，采用空间四叉树对轨迹段进行索引，在大规模轨迹数集环 境下极大提升聚类效率。实验结果表明，本发明可对轨迹进行有效聚类。

附图说明

图1是本发明实施例提供的基于移动对象时空信息轨迹分段聚类的方法流 程图；

图2是本发明实施例提供的轨迹聚类效果示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合实施例， 对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以 解释本发明，并不用于限定本发明。

下面结合附图及具体实施例对本发明的应用原理作进一步描述。

如图1所示，本发明实施例的基于移动对象时空信息轨迹分段聚类的方法 包括以下步骤：

S101：通过引入时间、速度和方向三个属性，并给出他们的相似度计算公 式来分析移动对象轨迹内外部结构；

S102：根据轨迹的空间密度将轨迹划分成若干轨迹段；

S103：然后通过计算各轨迹段在空间、时间、速度和方向上的差异来判断 轨迹段的相似度；

S104：最后，基于第一次聚类结果，将非显著簇中的轨迹段删除或并入邻 近的显著簇，使聚类空间形态体现出全局性的移动规律。

本发明的具体步骤为：

第一步，轨迹和轨迹段：

定义1轨迹：三维空间中的有序点集称为轨迹，轨迹TR_i定义：TR_i＝{p₁， p₂，...,p_k}，其中p_k={x_k，y_k，t_k}，分别代表该点的二维空间坐标和采用时间，不同 轨迹长度可能不一样；

定义2轨迹段：为TR_i内连续的部分三维点集，如：SubTrajectory_s={p₁，...， p_k}(1≤s≤k)，k为该轨迹段所属轨迹的采样点总数；

第二步，Hausdorff距离：

Hausdorff距离是描述两组点集之间相似程度的一种度量，也是集合之间距 离的一种定义形式，给定两个轨迹段P和Q，可直接使用Hausdorff距离对其进 行相似性测量：

$\left(\begin{array}{c}H(P,Q)=\max \{h(P,Q),h(Q,P)\}\\ h(P,Q)=\underset{p\in P}{\max }\underset{q\in Q}{\min }\left\{d(p,q)\right\}\\ h(P,Q)=\underset{p\in P}{\max }\underset{q\in Q}{\min }\left\{d(p,q)\right\}\end{array}\right)---\left(1\right)$

其中，d(p，q)为点p和q之间某个属性上的距离公式，Hausdorff距离在本发 明用以量度轨迹段之间的空间和时间差异度；

第三步，轨迹段速度：

轨迹段速度表达了某段时间内该该轨迹所在路径的通达程度，具有十分重 要的意义，由于实验数据集缺失采样点的速度，因此，通过如下公式得到每个 采样点速度：

$v_p=\frac{\mathrm{dis}\tan \mathrm{ce}(p_{-},p)+\mathrm{dis}\tan \mathrm{ce}(p,p_{+})}{t_{p_{+}}-t_{p_{-}}}---\left(2\right)$

其中，p_-为p点之前的相邻采样点，p₊为p点之后的相邻采样点，和分 别代表p_-和p₊的采样时间，该计算公式利用移动对象在三个连续采用点的平均 速度作为当前点的速度，轨迹段的速度通过该轨迹段中的最小速度、最大速度 和平均速度来衡量：

${\bar{V}}_{\mathrm{SubTrajectory}}=(1-w_m-w_a)v_{\min }+w_m{v}_{\max }+w_a\frac{v_i+v_{i+1}+...+v_j}{j-i+1}---\left(3\right)$

其中，ω_m+ω_a≤1，v_min为轨迹段中速度最低值，v_max为轨迹段中速度最高值， i和j分别为该轨迹段采样点的下标，对于一条轨迹段多个采样点，其速度都是 不相同的，因此，这里要综合考虑速度的各种因素，以将具有相似速度结构的 轨迹段聚集在一块；

第四步，轨迹段方向

轨迹段方向仅仅考虑始末参考点之间形成的角度，因为尽管道路上两条轨 迹段在每个采样位置的最小移动方向差异较大，但在道路网的约束往往这些采 样点的总体移动方向是相同的，所以，轨迹段的总体移动方向才能表达他们之 间主要方向差别，运动方向角：其中，(x_s，y_s)轨迹段起点，(x_e， y_e)为轨迹段终点；

第五步，轨迹段邻域：

一个聚类主要由时空、速度、方向上相似的轨迹段组成，这些相似轨迹段 称之为轨迹段邻域；

定义3轨迹段L_i的ξ邻域N_x(L_i)：N_x(L_i)＝{L_i危D|d(L_i，L_j)l}；

其中，D为所有轨迹段数据集合，轨迹段领域用以在DBSCAN轨迹密度聚 类中，判断每个轨迹段的当前空间密度，进而将空间密度较大的轨迹段聚为同 一组；

第六步，轨迹分割；城市中，浮动车辆的行动受道路网约束，其轨迹空间 形态不会类似动物路径或风暴路径那样在角度和速度上经常出现随机的剧烈变 化，因此依据角度和速度变化进行轨迹分割的方法不适合城市空间中的轨迹段 划分，而受到交叉路口红灯、交通拥塞、工作、休闲和生活场所的影响，城市 中的移动对象常常在这些位置有较明显的角度或速度差异，因此，通过采样点 在某个时间段内的速度变化来分割轨迹；

定义4断点：假设存在一轨迹段，位于该轨迹段上的任何两点之间的距离 不超过阈值ε，并且这段子轨迹的采样点数s大于阈值E，则将这段子轨迹中的 第[s／2]个点设置为断点，同时将位于该段子轨迹上其余的点删除，这实际上表 示如果某轨迹段在空间上的密度和采用点数量达到一定程度，即可认为该轨迹 段包含了断点；

显然，如果一条轨迹上有t个断点，则该轨迹被分割为t+1个轨迹段；

第七步，轨迹段相似性比较：轨迹段之间的相似性通过轨迹段之间的差异 度获取，该计算包括4方面：空间差异度、时间差异度、方向差异度和速度差 异度，其中，空间差异度与时间差异度采用Hausdorff距离计算得到，方向差异 度和速度差异度直接采用属性差值绝对值表示即可；结合得到一个统一的表达 轨迹段相似性公式：

subDis＝w_s创spatialDis+w_t tempoDis+w_o创OrientDis+w_v velocityDis，

且w_s+w_t+w_o+w_v=1  (4)

其中，spatialDis、tempoDis、OrientDi和seolocityDis分别为轨迹段之间的 空间差异度、时间差异度、方向差异度和速度差异度，轨迹段相似性公式为：

subSIM＝1-tanh(subDis)  (5)

其中，tanh(subDis)为三角函数归一化公式；

第八步，VOC-TC算法：

对轨迹进行分割后，再利用DBSCAN密度算法，采用式(4)的距离公式， 对轨迹段进行聚类，与DBSCAN不同，这里还需考虑轨迹段与原始轨迹的关系， 设聚类簇C中包含的轨迹数目为簇基数n_cb，簇基数n_b与该聚类中轨迹段数目 n_c之比为簇显著度n_cs，给定阈值τ和γ，进行如下定义：

定义5显著簇：C_sig＝{C|C吻O n_cb>t?n_cs g}，其中，O为第一次聚类的结 果集，即簇基数n_b高于τ且簇显著度n_s高于γ聚类称为显著簇；

定义6非显著簇：C_unsig={C|C吻O C□O_sig}，其中，O_sig为显著簇集合，即 显著簇之外的聚类都为非显著簇；

一旦某聚类中簇基数少于τ，则说明该聚类中亦或包含了较多属于同一条轨 迹的轨迹段，亦或仅仅包含了较少的移动对象，同样，如果某聚类中的显著度 小于γ，则说明该聚类中的轨迹数量相对于轨迹段来说过少，这两者均无法反映 全局上的该聚类所覆盖路径的重要性，因此，进行第二次聚类，将第一次聚类 中非显著簇删除，同时将该其中包含的轨迹段归并到离其最距离小于阈值μ且包 含同一条轨迹的聚类中，最终获取那些能反映主题变化的显著簇，非显著簇的 轨迹段归并到其他簇不会改变这些簇中的轨迹数量，因此，从不同的聚类开始 进行顺序显著簇的判断和轨迹段归并，最终会得到相同的聚类形态，一般情况 下，计算每个轨迹段邻域的时间复杂度为O(n²)，本发明采用采用四叉树空间 索引，将其时间复杂度降为O(nlogn)，

双重聚类算法伪代码如表1所示：

表1轨迹时空聚类伪算法

本发明能较好过滤到大部分不重要的聚类，同时扩充了那些具有全局重要 意义的轨迹聚类所涉及的空间范围，在全局空间分异上凸显出重要聚类的影响 范围，而其他类似的轨迹密度聚类方法无法做到这一点。

通过以下实验分析和比较对本发明的使用效果做进一步的说明：

1、实验与分析：

1.1实验数据与运行环境

为了验证本发明提出的聚类算法，开发了轨迹聚类分析系统。轨迹数据存 储在MySQL数据表中，实验的软硬件环境包括：64位的Windows7，Visual  Studio2010，CPU(CORE2DUO2.8GH)，内存8GB。采用武汉市武昌区2010 年2月至4月的出租车数据集作为实验数据，共10835条轨迹，每条轨迹的采 样点包括了经纬度坐标、采样时间。通过计算断点，最终得到52934个轨迹段。

1.2实验分析

1.2.1不同参数下的聚类效果比较

本发明提出的算法涉及13个需要用户预先设定的参数：轨迹段邻域阈值λ 和领域轨迹段数量阈值ξ，轨迹段速度权重值ω_a、ω_m，轨迹段相似性权重ω_v、 ω_t、ω_o、ω_s，断点设置阈值ε、E，聚类簇基数阈值τ和簇显著度阈值γ，归并阈 值μ。本发明着重观察速度、方向对聚类效果的影响，此外，τ、γ和μ作为与以 往轨迹聚类方法不同的参数，对聚类个数和最终聚类形态的影响较大，因此， 经过多次调整后将其他参数固定下来后，观察这5个参数对最终聚类形态的影 响。列出了5组ω_v、ω_o、τ、γ和μ的参数，并在表2-表6显示这5组参数下的 聚类的计算时间和聚类数目。下面对不同参数的影响进行分析(表标题中的“?” 表示对该参数进行调整)。

表2第1组参数(ω_v=？，ω_o=0.25，τ=160，γ＝0.25，μ=0.1)的聚类效果

随着速度权重的提高，越来越多的具有相同路径的轨迹被拆分，形成新的 聚类，如果没有后期对簇基数的控制，则聚类数量将更加多。

表3第2组参数(ω_v＝0.2，ω_o=?，τ＝160，γ=0.25，μ＝0.1)的聚类效果

与速度权重的效果类似，随着方向权重的提高，越来越多的具有相同路径 的轨迹被拆分，形成新的聚类，但其聚类数量较速度权重的少，可见，道路上 车辆间的速度变化差异较方向变化差异更加大。

表4第3组参数(ω_v=0.2，ω_o=0.25，τ＝?，γ=0.25，μ=0.1)的聚类效果

随着聚类簇基数阈值τ的提高，越来越多的包含少数轨迹聚类被删除，其中 的轨迹段一部分作为噪音被过滤掉，一部分融入了周边的显著簇。但其聚类时 间变化不大少，说明在进行过滤和轨迹段合并的过程消耗的时间不多。

表5第4组参数(ω_v＝0.2，ω_o=0.25，τ=160，γ＝?，μ＝0.1)的聚类效果

随着簇显著度阈值γ的提高，大量空间形态过长的聚类被过滤掉，被过滤的 聚类包含的轨迹段一部分作为噪音被删除，一部分融入了周边的“大”聚类。然 而，随着聚类数量的减少，聚类时间逐渐小幅增加，说明在进行轨迹段合并的 过程需有较多合适的邻近类供选择，系统在选取最近邻类时增加了相应的时间 开销。

表6第5组参数(ω_v=0.2，ω_o＝0.25，τ＝160，γ=0.25，μ＝?)的聚类效果

由于聚类簇基数阈值τ决定了最终聚类的个数，因此这里的聚类数目不会随 着归并阈值μ的变化而变化。然而，在μ不断增加时，低于聚类簇基数阈值τ的“小” 聚类中，越来越多的轨迹段被作为噪音过滤掉，当μ达到0.3时，被删除的轨迹 几乎占了轨迹段总数的1／3，可见，加入速度和方向约束后的轨迹段之间的差异 比较大，造成很多同一轨迹上的轨迹段无法聚在同一类中。

1.2.2不同聚类算法效果对比

本发明提出的算法VOC-TC与DBSCAN、OPTICS等都是密度相关的聚类 算法。VOC-TC、DBSCA和OPTICS的参数调优以最大程度体现城市主干要道 为准。从表7中可以看出，相对于其他2种方法，本算法具有较好的运行速度， 且发现的聚类更能体现城市交通特征(图2)，主要有以下原因：①VOC-TC采 用了空间四叉树存储轨迹段并为其近邻增加空间索引，提高了邻接轨迹段的搜 索效率；②VOC-TC以方向和速度特征为依据，容易区分开那些路径相同但移 动属性不同隐蔽轨迹群；③VOC-TC通过两次聚类，删除了大量非显著聚类， 表现了总体上轨迹运动模式和趋势。

表7不同聚类算法之间的效果比较

经过计算后轨迹数据被分为41个类，将结果转换为shp格式，如图2所示， 图中每条线代表200条不区分速度、方向和时间的轨迹，小于200条的也用一 条线段表示。其中，带有颜色的线条为显著轨迹段聚类，灰色轨迹为噪音。在 考虑速度和方向后，原来在同一道路上经过的轨迹段之间由速度和方向的差异 较大，会被聚合到邻近的聚类。由于轨迹段的归并，某些聚类特别长，而某些 聚类类包含了主干道之外旁系轨迹。此外，由于位于枝干道路上移动对象的速 度和方向的相似度较低，大部分的处于主干道之外的轨迹被作为噪音处理，很 多处主干道的非显著聚类，被归并到同一主干道上的显著性聚类中。可见，本 轨迹聚集的空间分布反映了车流在城市中的最为主要的流动状况，从侧面也反 映出了城市主干要道的分布。

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发 明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明 的保护范围之内。