轨迹聚类:哪种聚类方法？

Question

作为机器学习的新手，我有一套不同长度的轨迹。我希望对它们进行聚类，因为它们中的一些是，实际上是相同的路径，而由于噪声的影响，它们的看起来与不同。

此外，，而不是，它们的长度都是相同的。所以，虽然轨迹A和轨迹B不一样，但它是轨迹B的部分。我希望在聚类之后也能给出这个性质。

我对K-means Clustering和Fuzzy N-means Clustering只有一点点的了解。，我怎样才能在他们两人之间作出选择呢？或者我应该采用其他方法？

任何考虑"belongness“的方法？(例如，在集群之后，我有3个集群A, B and C。一个特定的trajectory X属于cluster A。并且一个较短的trajectory Y (虽然不是聚集在A中)被识别为trajectory B的一部分。)

===================更新======================

前面提到的轨迹是行人的轨迹。它们既可以表示为一系列(x, y)点，也可以表示为一系列阶跃向量(length, direction)。演示表在我的控制之下。

Answer 1

现在可能有点晚了，但我也在处理同样的问题。我建议你看一看TRACLUS，这是由Jae-Gil Lee，Jiawei和Kyu创建的算法，发表在SIGMOD‘07上。jglee.pdf

到目前为止，这是我看到的最好的聚类轨迹方法，因为：

• 可以发现常见的sub-trajectories.
• 专注于段而不是点(因此过滤掉了噪声异常值)。
• 它工作在不同长度的轨迹上。

基本上是两个阶段的方法：

1. 第一阶段-划分:将轨迹分割成分段，这是使用具有O(n)复杂性的MDL优化完成的，其中n是给定轨迹中的点数。在这里，输入是一组轨迹，输出是一组分段。

- Complexity: O(n) where n is number of points on a trajectory
- Input: Set of trajectories.
- Output: Set D of segments

​

1. 第二阶段-组:这个阶段使用一些基于密度的集群来发现集群，比如在DBSCAN中。这一阶段的输入是从第一阶段获得的一组片段，以及构成一个邻域的一些参数，以及组成一个簇的最小线数。输出是一组集群。聚类是在段上完成的。它们定义了由平行距离、垂直距离和角距离三个分量组成的距离测量方法。这个阶段的复杂度为O( n )，其中n是段数。

- Complexity: O(n log n) where n is number of segments on set D
- Input: Set D of segments, parameter E that sets neighborhood treshold and parameter MinLns that is the minimun number of lines.
- Output: Set C of Cluster, that is a Cluster of segments (trajectories clustered).

​

最后，他们为每个集群计算一个有代表性的轨迹，这不是在每个集群中发现的共同子轨道。

他们有相当酷的例子，这篇论文解释得很好。再说一次，这不是我的算法，所以如果你在做研究，别忘了引用它们。

PS:我根据他们的工作制作了一些幻灯片，只是为了教育目的：http://www.slideshare.net/ivansanchez1988/trajectory-clustering-traclus-algorithm

Answer 2

每个聚类算法都需要一个度量。你需要定义样品之间的距离。在你的例子中，简单的欧几里得距离不是一个好主意，特别是如果轨道可以有不同的长度。

如果定义了度量，则可以使用允许自定义度量的任何群集算法。您可能事先不知道正确的集群数量，那么分层聚类是一个很好的选择。K-表示不允许自定义度量，但对K-表示进行了修改(比如K-medoid)。

最困难的部分是定义两个轨道之间的距离(时间序列)。常用的方法是DTW (动态时间翘曲)。为了提高性能，你可以用更小的点来近似你的轨迹(很多算法都是这样的)。

Answer 3

这两样都没用。因为，这里的是什么意思？

看看基于距离的集群方法，例如分层聚类(对于小数据集而言，但您可能没有数千条轨迹)和DBSCAN。

然后，您只需要选择一个适当的距离函数，例如允许时间和空间分辨率的轨迹差异。

距离函数，如动态时间翘曲(DTW)距离可以容纳这一点。