algorithm - 轨迹聚类 : Which Clustering Method?

Question

作为机器学习的新手，我有一组可能长度不同的轨迹。我希望将它们聚类，因为它们中的一些实际上是相同的路径，它们只是由于噪音看起来不同。

此外，并非它们的长度都相同。所以也许虽然轨迹 A 与轨迹 B 不同，但它是轨迹 B 的一部分。我也希望在聚类后呈现这个属性。

我对K-means Clustering知之甚少|和 Fuzzy N-means Clustering . 我该如何在两者之间做出选择？还是应该采用其他方法？

有没有考虑到“归属感”的方法？(例如，在聚类之后，我有 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 Han 和 Kyu-Young Wang 创建的算法，发表在 SIGMOD'07 上。 http://web.engr.illinois.edu/~hanj/pdf/sigmod07_jglee.pdf

这是迄今为止我所见过的最好的轨迹聚类方法，因为:

• 可以发现常见的子轨迹。
• 关注线段而不是点(因此它过滤掉噪音异常值)。
• 它适用于不同长度的轨迹。

基本上是一个两阶段的方法:

1. 第一阶段 - 分区:将轨迹分成多个段，这是使用复杂度为 O(n) 的 MDL 优化完成的，其中 n 是给定轨迹中的点数。这里的输入是一组轨迹，输出是一组段。

   • 复杂度:O(n)，其中 n 是轨迹上的点数
   • 输入:一组轨迹。
   • 输出:D段的集合

2. 第二阶段 - 分组:此阶段使用某种版本的基于密度的聚类(如 DBSCAN)来发现聚类。此阶段的输入是从第一阶段获得的一组段和构成邻域的一些参数以及可以构成一个簇的最小线数。输出是一组集群。聚类是在段上完成的。他们定义了自己的距离度量，由三个部分组成:平行距离、垂直距离和角距离。此阶段的复杂度为 O(n log n)，其中 n 是段数。

   • 复杂度:O(n log n) 其中 n 是集合 D 上的段数
   • 输入:段的集合D，设置邻域阈值的参数E和最小线数的参数MinLns。
   • 输出:Cluster 的集合 C，即段的 Cluster(轨迹聚类)。

最后，他们为每个集群计算了一个代表性轨迹，这就是在每个集群中发现的公共(public)子轨迹。

他们有很酷的例子，这篇论文也有很好的解释。再次重申，这不是我的算法，所以如果您正在进行研究，请不要忘记引用它们。

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