15

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

此外，并非所有的长度都相同。所以也许虽然轨迹 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)。演示文稿由我控制。

4

4 回答 4

13

可能有点晚了，但我也在解决同样的问题。我建议您看一下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）来发现聚类。此阶段的输入是从第一阶段获得的一组线段以及构成邻域的一些参数以及可以构成集群的最小线数。输出是一组集群。聚类是在段上完成的。他们定义了自己的距离度量，由 3 个组件组成：平行距离、垂直距离和角距离。该阶段的复杂度为 O(n log n)，其中 n 是段数。

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

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

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

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

于 2015-03-17T05:21:09.917 回答
9

每个聚类算法都需要一个度量。您需要定义样本之间的距离。在您的情况下，简单的欧几里得距离不是一个好主意，特别是如果轨迹可以有不同的长度。

如果您定义一个指标，那么您可以使用任何允许自定义指标的聚类算法。可能您事先不知道正确的集群数量，那么层次聚类是一个不错的选择。K-means 不允许自定义指标，但有一些 K-means 的修改（如 K-medoids）

困难的部分是定义两个轨迹（时间序列）之间的距离。常用的方法是 DTW（动态时间规整）。为了提高性能，您可以通过更少量的点（许多算法）来近似您的轨迹。

于 2013-09-16T07:42:38.010 回答
7

两者都行不通。因为这里的正确意思是什么？

查看基于距离的聚类方法，例如层次聚类（对于小型数据集，但您可能没有数千条轨迹）和 DBSCAN。

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

诸如动​​态时间规整 (DTW) 距离之类的距离函数可以适应这一点。

于 2013-09-16T07:41:11.387 回答
0

这是一个很好的概念，并且有可能用于实时应用。在我看来，可以采用任何聚类但需要选择适当的相异性度量，稍后需要考虑计算复杂度。论文 ( http://link.springer.com/chapter/10.1007/978-81-8489-203-1_15 ) 使用了 Hausdorff 并提出了降低复杂性的技术，论文 ( http://www.cit.iit.bas .bg/CIT_2015/v-15-2/4-5-TCMVS%20A-edited-md-Gotovop.pdf ) 描述了“基于多视图相似性的轨迹聚类技术”的使用

于 2016-03-29T04:13:21.373 回答