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

Question

作为机器学习的新手,我有一组可能有不同长度的轨迹.我希望将它们聚类,因为它们中的一些实际上是相同的路径,并且由于噪声它们只是SEEM不同.

此外,并非所有长度都相同.因此,虽然轨迹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

到目前为止,这是我看到的聚类轨迹的最佳方法,因为:

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

第一阶段 - 分区:将轨迹划分为段,这是使用复杂度为O(n)的MDL优化完成的,其中n是给定轨迹中的点数.这里输入是一组轨迹,输出是一组段.
- 复杂度:O(n)其中n是轨迹上的点数
- 输入:轨迹集.
- 输出:设置段的D
第二阶段 - 组:此阶段使用某些版本的基于密度的聚类(如DBSCAN)发现聚类.此阶段的输入是从第一阶段获得的一组分段和构成邻域的一些参数以及可构成一个集群的最小行数.输出是一组集群.群集是通过分段完成的.它们定义了由3个分量组成的自己的距离测量:平行距离,垂直距离和角距离.该阶段具有O(n log n)的复杂度,其中n是段的数量.
- 复杂度:O(n log n)其中n是集合D上的段数
- 输入:设置段D,参数E设置邻域阈值,参数MinLns设置为最小行数.
- 输出:设置群集C,即群集群集(群集的轨迹).

最后,他们为每个群集计算一个代表性轨迹,这是每个群集中发现的共同子轨迹的其他内容.

他们有非常酷的例子,这篇论文得到了很好的解释.再一次,这不是我的算法,所以如果你正在做研究,不要忘记引用它们.

Answer 2

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

如果定义度量标准,则可以使用允许自定义度量标准的任何群集算法.可能您事先并不知道正确的簇数,然后层次聚类是一个不错的选择.K-means不允许自定义度量,但有K-means的修改(如K-medoids)

困难的部分是定义两个轨迹之间的距离(时间序列).常见的方法是DTW(动态时间扭曲).为了提高性能,您可以通过较少的点(许多算法)来近似您的轨迹.

-1:如果定义自定义指标,则无法使用K-means.K-means仅为eucliean度量定义良好.K-medoids或核化k-means可以克服这种限制,但代价是额外的计算资源. (2认同)
@Anony Mousse对于明确区分*metric*和*difimilarity*有一个很好的观点.这也可以是聚类方法usind伪内核(不引起内核度量)的情况以及基于某些模型/分布拟合的聚类,其中我们不关心数据之间*distance*的任何概念,我们更倾向于测量来自某些参数化模型的概率(这不仅仅是输入空间中的一个点). (2认同)

Answer 3

两者都不会起作用.因为这里的意思是什么？

看看基于距离的聚类方法,例如层次聚类(对于小数据集,但您可能没有数千个轨迹)和DBSCAN.

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

距离的功能,如动态时间规整(DTW)距离可容纳这一点.