路线(旅行路径)聚类机学习算法

Question

我有一系列的线数据(2-3个连接点).什么是最好的机器学习算法，我可以用它来分类直线到它们的位置相似性？(下图)

最好是python库，如本工具包-学习。

​

​

编辑：我尝试过DBSCAN，但是我面临的问题是如果有两条线相交，有时DBSCAN会把它们看作一个组，尽管它们完全是在不同的方向上。

到目前为止，我找到了一个解决方案：

GeoPath聚类算法

这里的想法是将旅行非常相似的地理路径聚成一组。

步骤：

1-基于斜率的群集线

2-从步骤1开始，在每个簇内，找到线的中心点，并使用k均值算法将它们聚为较小的组。

3-从第2步开始，计算每条线和组线在规定长度阈值范围内的长度。

结果将是具有相似坡度、彼此相近、旅行距离相近的一小群直线。

这里是可视化的屏幕截图:黄线都是线，红色是一簇路径一起旅行。

​

​

​

​

​

Answer 1

我将抛出一个答案，因为我认为当前的答案是incomplete...and，我也认为“简单启发式”的评论为时过早。我认为，如果按点进行聚类，就会得到与图表所描述的结果不同的结果。因为星系团将接近终点，你就不会得到你漂亮的椭圆。

因此，如果您的数据的行为确实类似于您如何显示它。我会尝试将每一组2/3点转化为一个更长的点列表，这些点基本上是跟踪直线的。(你需要测试密度有多大)

然后在结果上运行HDBSCAN --请参阅视频( https://www.youtube.com/watch?v=AgPQ76RIi6A )--以获得集群。我相信"pip install hdbscan“会安装它。

现在，在测试一个新样本时，首先将其分解为多个(N)点，并将它们与hdbscan模型相匹配。我认为，如果你对N点采取多数投票的方式，你就会得到“线”所属的最佳整体集群。

所以，虽然我有点同意“简单启发式”的评论，但如果你想让整个事情自动化的话，这就不那么简单了。一旦您观看了视频，您可能会确信，HDBSCAN，由于其基于密度的算法，将适合这个问题(如果您决定从每个样本创建多个点)。

最后，我要说的是，我确信有一些行交模型已经完成了这个before...and，确实存在启发式和规则来完成这项工作。很可能，它们在计算上也更经济。我的答案只是一些有机的使用滑雪板，因为你requested...and，我甚至还没有测试过它！如果我站在你的立场上我就会这么做。

编辑

我四处打探，你可以试试几个线相似性度量。Frechet和Hausdorff距离测度

Frechet：http://arxiv.org/pdf/1307.6628.pdf Hausdorff：python中曲线的距离矩阵用于python示例。

如果您生成所有成对相似点，然后根据相似性和/或将它们分组到N个桶中，那么您就可以将这些垃圾箱称为“集群”(不是指集群！)。对于每个新行，生成所有相似之处，并查看它属于哪个bin。我修改了我最初的评论，可能在计算上不那么密集.你很幸运你的台词只有2到3分！

Answer 2

您要解决的问题称为集群。有关sklearn中的集群算法的概述，请参阅http://scikit-learn.org/stable/modules/clustering.html#clustering。

编辑2:当我第一次看到你的帖子时， KMeans突然出现在我的脑海中，但是根据评论中的反馈，它看起来不太合适。您可能想尝试一下sklearn的DBSCAN。

您可以添加的一个潜在的转换或额外特性是在每一组点上拟合一条直线，然后使用(斜率，截距)对。您还可以使用每一行的质心。