如今移动物体的轨迹数据在多个领域被广泛的收集，如动物生态学，运动以及航空。移动物体的相似轨迹的聚类是运动分析中的重要技术。可以使用距离函数基于轨迹点或段的属性来评估轨迹之间的相似性。属性可能包括空间位置，时间和其他数据属性。有这样的需求，需要分析轨迹的某些部分，即具有特定属性的点和段。根据分析焦点，需要对轨迹的相关部分进行聚类。在整个分析过程中，焦点可能会改变，轨迹的不同部分可能会变得相关。这篇文章[1]提出一个分析工作流程，其中使用交互式过滤工具将相关标志附加到轨迹点，聚类是使用忽略不相关元素的距离函数完成的，并且汇总了所得到的聚类进一步分析。
该工作有三个主要的工作流程，分别为过滤，聚类和汇总分析。其主要贡献为支持对轨迹相关部分进行聚类Relevance-aware density-based clustering(RACAT)，而不是针对整个轨迹数据聚类。首先所针对的数据就是一般的轨迹类型。首先是一系列的轨迹集合Tr={tr1, tr2,…,trk},表示有K条轨迹。每条轨迹由一系列点构成tri=<p1, p2,…,pl>。l为每条轨迹的长度。每个点由一系列时间，位置和一些移动物体的属性构成。表示为<t, l, {a}>。
第一步为过滤操作。通过可视支持的交互性过滤，选择出感兴趣的轨迹的相关部分。过滤操作针对的是轨迹的一系列点。过滤条件可以是轨迹的任何组成部分<t, l, {a}>。根据时间，位置和移动物体的相关属性过滤出的轨迹点就是用户感兴趣的轨迹的相关部分。这一步操作的输出是针对轨迹的一系列标示M(Tr)={m1, m2,…,mk}, 一个标示是针对一条轨迹的所有点的标记mi=<r1, r2,…,rl>; 其中0<rj<1, 当rj为1的时候，点pj被称为激活点，反之称为非激活点。过滤操作确定有三个任务。一是用户可以单独看到轨迹的相关部分，来确定他们只包含相关部分。二是用户可以单独看到轨迹的非激活部分，来检查他们是否不包含激活部分。三是可以在非激活轨迹的上下文中观察激活部分。针对任务作者实现了三种设计，如图1所示，过滤相关的渲染，激活部分用实线更粗的表示，非激活部分用虚线或点线表示。如图2所示布尔值的可视化，用颜色表示是否为轨迹的激活部分。图3表示激活部分和非激活部分展示不同程度的细节。
图1 过滤后轨迹渲染
图2 布尔值用颜色区分
第二步为聚类(RACAT)操作。针对所过滤出来的轨迹相关部分进行聚类。使用基于特定轨迹距离函数的密度聚类算法。其中距离函数根据第一步过滤输出的相关标记，为D(tr1, m1, tr2, m2)->R, R≥0。对于给定的一对轨迹 tr1, tr2，和与他们对应的相关标记m1, m2 ，输出为一个非负的实数代表两条轨迹之间的距离。在此基础上，聚类函数确定聚类轨迹的分组，未能聚类的轨迹被称为噪音。聚类操作的输出为轨迹的聚类标志， Li={C1, C2,…,Cm, noise}, 其中Cm为聚类结果。
聚类采用渐进式聚类的方法，基于密度的聚类涉及两个参数，邻域半径NR和一个对象成为聚类核心对象的最小邻居数NN。更改这两个参数来渐进式的聚类。首先使用较大的NN和较小的NR来确定最密集的群集。然后聚类操作迭代地应用在之前的聚类结果。在每个步骤中，通过增加NR或减少NN来放宽参数设置，从而形成较好的聚类结果。渐进式还体现在如果聚类结果存在某部分聚类效果不够好，可以单独针对这部分进行重新聚类。形成一个好的聚类效果需要进行多次尝试，通过对聚类的可视表达来人为判断聚类效果，或者通过统计聚类轨迹的距离总和来判断。如图3是使用不同颜色来标记航线的不同聚类。
图3 航线聚类结果
第三步为汇总分析。针对轨迹聚类结果创造出可视表达。主要目的是为每个聚类创造出中心轨迹。首先是对聚类中所有轨迹的点创造分组，然后找出每组的代表点，一般代表点可以选择为分组中的均值点或中位数点。最后需要对代表点进行排列，组成中心轨迹。如图4是对聚类中心轨迹的可视化结果，更便于观察和分析。在确定轨迹点的分组时，如果轨迹是同时运动的，可以根据不同的时间间隔来确定分组。如果轨迹不是同时运动的。作者提出了一个基于二分和重组优化的算法来确定聚类轨迹点的分组。
图4 聚类中心轨迹的可视表达
使用案例揭露影响航空线路选择的因素。其中一个因素是航行费，飞机飞过不同领域的上空需要缴纳不同额度的航行费用。如图所示，不同区域颜色越深代表飞过此领域需要缴纳的航行费用越高，因此在选择航空线路的时候需要尽量降低航行费用。在过滤掉受航道影响较大的起飞和降落的轨迹部分后，对主要的飞行航线进行聚类和汇总分析，形成如下图5所示的九条主要的轨迹聚类，其中轨迹的宽度代表在此区域需要缴纳的航行费用。从图中可以发现除了蓝色轨迹经过航行费用较高的深色区域LS，其余轨迹都选择绕开LS。其中绿色航线2偏离了其余轨迹选择了经过LO和LH来避开更贵的区域。
图5 航班费对航线选择影响
参考文献：
[1] Andrienko G, Andrienko N, Fuchs G, et al. Clustering Trajectories by Relevant Parts for Air Traffic Analysis[J]. IEEE Transactions on Visualization and Computer Graphics, 2017.
评论关闭。