轨迹集群：哪种聚类方法？ [英] Trajectory Clustering: Which Clustering Method?
问题描述
作为机器学习一个新手，我有一组轨迹，可能是不同长度的。我想集群他们，因为他们中的一些是其实是相同的路径，然后他们只是 SEEM不同由于噪声。
As a newbie in Machine Learning, I have a set of trajectories that may be of different lengths. I wish to cluster them, because some of them are actually the same path and they just SEEM different due to the noise.
此外，不可以所有这些都是在相同的长度。因此，也许虽然轨迹A是不一样的轨迹B，但它的的一部分轨迹B.我想为 present这个属性集群后也是如此。
In addition, not all of them are of the same lengths. So maybe although Trajectory A is not the same as Trajectory B, yet it is part of Trajectory B. I wish to present this property after the clustering as well.
我有的只有一点点知识的K-means聚类和模糊的N-均值聚类。 如何我可以选择它们两者之间？或者我应该采取其他的方法呢？
的任何方法，它采用了belongness考虑？
（如后集群，我有3个集群 A，B和C 。一个特别的轨迹X 属于集群A ，并缩短轨迹是，虽然没有在集群 A ，被确定为轨迹乙部分。）
Any method that takes the "belongness" into consideration?
(e.g. After the clustering, I have 3 clusters A, B and C. One particular trajectory X belongs to cluster A. And a shorter trajectory Y, although is not clustered in A, is identified as part of trajectory B.)
===================更新======================
上述轨迹是行人的轨迹。他们可以psented一系列（X，Y）点或一系列的步骤向量（长度方向）。在presentation形式是我的控制之下。
The aforementioned trajectories are the pedestrians' trajectories. They can be either presented as a series of (x, y) points or a series of step vectors (length, direction). The presentation form is under my control.
推荐答案
这可能晚了一点，但我也努力了同样的问题。 我建议你看一看由宰吉尔李，韩家炜和圭青年王某，发表了关于SIGMOD'07创建 TRACLUS ，一种算法。 http://web.engr.illinois.edu/~hanj/pdf/sigmod07_jglee .PDF
It might be a little late but I am also working on the same problem. I suggest you take a look at TRACLUS, an algorithm created by Jae-Gil Lee, Jiawei Han and Kyu-Young Wang, published on SIGMOD’07. http://web.engr.illinois.edu/~hanj/pdf/sigmod07_jglee.pdf
这是迄今为止我所看到的集群轨迹的最好的方法，因为：
This is so far the best approach I have seen for clustering trajectories because:
- 可以发现共同的子轨道
- 重在段，而不是点（因此它的过滤掉噪音异常值）。
- 在它工作过的轨迹不同长度
- Can discover common sub-trajectories.
- Focuses on Segments instead of points (so it filters out noise-outliers).
- It works over trajectories of different length.
基本上是一个2阶段方式：
Basically is a 2 phase approach:
-
第一阶段 - 分区：分割轨迹成段，这是使用MDL优化为O（n）的复杂性，其中n是点的数量在给定的轨迹进行。这里的输入是一组轨迹和输出是一组段的
Phase one - Partition: Divide trajectories into segments, this is done using MDL Optimization with complexity of O(n) where n is the numbers of points in a given trajectory. Here the input is a set of trajectories and output is a set of segments.
- 复杂度：O（n），其中n是一个轨道 点数
- 输入：轨迹组
- 输出：集合D段
第二阶段 - 群：这个阶段发现使用某些版本的基于密度的聚类像DBSCAN集群。输入在这个阶段是一组从第一阶段得到的段和什么构成的邻域，并且可以构成一个簇的行的最小量的一些参数。输出是一组集群。集群做了细分。他们定义自己的距离度量由3部分组成：平行距离，垂直距离和角度的距离。这相具有为O（n log n）的，其中n是区段的数目的复杂性。
Phase two - Group: This phase discovers the clusters using some version of density-based clustering like in DBSCAN. Input in this phase is the set of segments obtained from phase one and some parameters of what constitutes a neighborhood and the minimum amount of lines that can constitute a cluster. Output is a set of clusters. Clustering is done over segments. They define their own distance measure made of 3 components: Parallel distance, perpendicular distance and angular distance. This phase has a complexity of O(n log n) where n is the number of segments.
- 复杂度：O（N日志N），其中n是集D 段数
- 输入：设置段研发，参数ê，设置社区treshold和参数MinLns这是行的最低限度的数量 。
- 输出：设置集群C，这是段（轨迹集群）的集群
最后，他们计算出每个集群中的重presentative轨迹，这不是别的，一个在每个集群发现常见的子轨道
Finally they calculate a for each cluster a representative trajectory, which is nothing else that a discovered common sub-trajectory in each cluster.
他们有pretty的酷实例和纸是很好的解释。再次，这是不是我的算法，所以不要忘记说说他们，如果你正在做研究。
They have pretty cool examples and the paper is very well explained. Once again this is not my algorithm, so don't forget to cite them if you are doing research.
PS：我做了基于自己的工作，只是为了教育目的一些幻灯片： 的http://www.slideshare.net/ivansanchez1988/trajectory-clustering-traclus-algorithm
PS: I made some slides based on their work, just for educational purposes: http://www.slideshare.net/ivansanchez1988/trajectory-clustering-traclus-algorithm
这篇关于轨迹集群：哪种聚类方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
