向量场k-Means:通过多向量场拟合对轨迹数据聚类(Vector Field k-Means: Clustering Trajectories by Fitting Multiple Vector Fields)

运动是这个世界的本质,而运动轨迹则是描述运动的重要方式之一。轨迹数据被人们研究了数百年,研究的对象从战争中的行军路线,船舶航行路线,到鸟类迁徙路线,以及如今GPS技术普及之后的出租车、自行车行驶路线等等。面对轨迹数据,一种常见的做法是对轨迹数据进行聚类,将相似的轨迹数据聚到一起,便于研究者发现内在的模式。来自纽约大学与AT&T实验室的学者Nivan Ferreira等人在今年的EuroVis上提出了一种新颖的基于向量场拟合的向量场k-Means算法。

hurricane_cluster
图1:图中展示了对1412条飓风行进轨迹进行向量场k-Means聚类的结果。在4个聚类中,a, d类方向均为西南——东北,但a中飓风速度要快于d中飓风。b类为东南——西北方向移动的飓风,而c类则在此移动基础上又明显的方向改变。

在向量场k-Means算法中,每一条轨迹对应于传统k-Means算法种的“数据点”,向量场对应于传统k-Means算法的“中心点”。该聚类算法寻找的解包含两个部分:一是k个平滑的向量场X_j,二是分配函数Φ,将每条轨迹指派给某个向量场,使得向量场能最大限度拟合所涵盖的轨迹。实际操作中,整个二维区域首先被划分为均匀网格,并进而划分为三角网格。用于表示速度大小及方向的向量场定义在这个离散的网格上,对于非网格点,可以通过重心坐标系插值来得到该点的速度。同时,一条轨迹也被三角网格划分为多个片断,在假设片断内匀速运动的前提下,我们衡量这条轨迹与向量场的拟合程度。

能量方程

图2:向量场k-Means问题对应的能量方程,其中第一项限制向量场需要平滑,第二项限制向量场需要与所涵盖的轨迹尽量吻合。

对于向量场k-Means问题,我们可以用图2的能量方程来描述这个最优化问题。其中第一项限制向量场需要平滑,第二项限制向量场需要与所涵盖的轨迹尽量吻合,λ因子用于平衡两项的权重。
这个最优化问题可以通过经典的EM算法来求解。初始时,将每条轨迹按某种策略分配给某个聚类。之后,算法迭代地重复以下两个阶段:先固定分配函数,求出拟合轨迹数据最好的向量场;然后固定向量场,重新分配各条轨迹。这两个步骤交替进行,直至结果令人满意时止。

对合成轨迹数据聚类

图3:作者首先将其算法应用于合成数据,用于验证算法正确性。这个数据包含2000条轨迹,其中每1000条轨迹各自形成了一个环状模式。向量场k-Means算法通过若干次迭代之后,能够完全将两个类别区分开,得到满意的结果。

图3是作者采用的一个合成数据,包含2000条轨迹,其中每1000条轨迹各自形成了一个环。向量k-Means算法通过若干次迭代之后,能够完全将两个类别区分开,得到满意的结果。而同时其它针对轨迹数据的聚类算法却不能得到好的结果。

图1是作者针对1412条飓风行进轨迹数据进行聚类的结果。在4个分类中,a, d类方向均为西南——东北,但a中飓风速度要快于d中飓风。b类为东南——西北方向移动的飓风,而c类则在此移动基础上又明显的方向改变。

总起来看,这篇文章最大的创新点就是将轨迹数据拟合至向量场模型,这种方法相比于已有方法能够很好的发掘数据隐含的运动模型。而对于用向量场来表示聚类的结果,文中给出的可视化方法也十分直观。

评论关闭。