轨迹聚类

Question

我有大量的时间和地点数据（经纬度）。

我想从这些数据中找到k个轨迹的聚类。请问有什么好的方法吗？

谢谢。

编辑：

我应该如何为我的数据（经纬度 + 时间）生成特征，以便使用k均值聚类或层次聚类呢？

编辑：

希望这样能更清楚一些。

这是我的数据的一个例子：

Trajectory 1:

lat1,lon1 at time1
lat2,lon2 at time2
...
lat55,lon55 at time55

Trajectory 2:

lat343,lon343 at time343
lat344,lon344 at time344
...
lat376,lon376 at time376

还有更多的轨迹。

假设我有200条这样的轨迹，我想把它们分成2组。我该怎么做呢？

我应该使用k均值聚类或层次聚类，还是应该考虑其他方法呢？

编辑：

我的目标是将这些轨迹分类为k个聚类，代表k个不同的方向。

简单来说，我只是想把轨迹分成不同方向的组。我不太关心它们之间的距离相似性。

所以说，最后我想找到这样的结果：

Direction 1:
Trajectory 4
Trajectory 5
Trajectory 7

Direction 2:
Trajectory 44
Trajectory 2
Trajectory 27

...

Direction 10:
Trajectory 17
Trajectory 8

注意：这些轨迹的形状大多是线条（不是直线），有些是环形的。
注意：经纬度数据非常局限于一个区域，所以我可以使用平面地球的近似。

这些方向是比较粗略的。我该如何计算轨迹之间的相似性，以便进行聚类呢？

编辑：

这是一个插图（尽我所能）：

我想把轨迹分成这样的方向。

Answer 1

动态时间规整（DTW）是一种用来衡量相似度的方法，通常用于时间序列数据（这正是你所拥有的）。你可以把这些DTW相似度作为输入，放到一些基于相似度的聚类算法中去。

对于你的数据集，我建议只提取方向的序列，因为如果把距离也考虑进去，可能会出现问题，比如路径以不同的速度行进，或者样本是在不均匀的时间间隔内采集的。

Answer 2

你描述的问题听起来像是可以用一个角度来表示所有的轨迹，这个角度是相对于赤道的。接下来就是要把这些轨迹分段；这其实不是在进行聚类，具体可以参考一下这个链接。在你的情况下，这些值是循环的，所以我们是在一个圆上进行分段（使用度数/角度），而不是在一条直线上。当然，如果这正好描述了你的问题，那也为可视化提供了一个很好的方法。

Answer 3

K-means算法的设计目的是为了最小化方差。

当你把它应用到时间序列数据时，如果你总是离赤道很近，并且远离180度经线，你会遇到一些错误。因为地球大致是一个球面，而不是一个无限的欧几里得空间。

不如试试基于距离或密度的聚类算法，这些算法可以使用大圆距离。比如，层次聚类可能比K-means更合适。

大圆距离就是指两个点之间的距离。所以接下来你需要做的就是弄清楚如何将这些距离和时间因素结合起来，形成一个合适的相似度度量，用于你的轨迹。这很依赖于具体的使用场景，没有一个通用的解决方案可以分享给你。你的相似度函数越好，聚类结果就会越好！