光线的聚类算法 [英] Clustering algorithm for rays

问题描述

我知道显然有针对点的聚类算法，但是我有不同的情况.我有很多射线，所有射线的起点都在3D球体上，并且方向矢量向内指向球体.有些光线指向A点，有些光线指向B点，依此类推，但有一些噪音(即，光线彼此之间并不完全相交).是否有一种聚类算法，可以让我根据射线指向的点对射线进行聚类?我不知道点A，B等的位置，仅知道射线的起点和方向矢量.

I know that there are clustering algorithms for points obviously, but I have a different scenario. I have many rays, all whose start points are on a sphere in 3D, and whose direction vectors point inwards into the sphere. Some of the rays are pointing towards a point A, others are pointing towards a point B, etc, with some noise(ie the rays don't perfectly intersect each other). Is there a clustering algorithm that will allow me to cluster the rays based on which point they are pointing towards? I don't know the locations of points A, B, etc, only the start points and direction vectors of the rays.

例如，此图片中的 是示例设置，但在2D模式下，我不知道一开始是红色还是蓝色.我如何将光线聚集成红色和蓝色?或者，我如何找到他们指向的点的位置?

For example, in this picture is a sample setup, but in 2D, and I don't know which rays are red or blue at the start. How would I cluster the rays into red and blue? Or, how would I find the locations of the points they're pointing towards?

我想到的一个解决方案是获取射线对，找到这两条射线之间的最接近点(在2D中，如果延伸射线，则是相交点)，然后对每对射线都这样做(所以我d获得n(n-1)/2点，其中n是射线数).然后，我可以在这些点上使用常规的聚类算法.但是，这似乎不起作用-我在原点只得到一大分，我不知道为什么会这样.

One solution I thought of was taking pairs of rays, finding the closest point between those two rays(in 2D this is the point of intersection if you extend the rays), and doing this for every pair of rays(so I'd get n(n-1)/2 points, where n is the number of rays). Then, I could use the regular clustering algorithm on those points. But, that's not seeming to work - I'm getting just one big lump of points at the origin, I don't know why that's happening.

推荐答案

这里是尝试的内容，大致基于">://en.wikipedia.org/wiki/K-means_clustering .它会尝试爬升至解决方案，因此您可能要尝试使用不同的随机开始多次尝试.

Here is something to try, loosely based on https://en.wikipedia.org/wiki/Random_sample_consensus and https://en.wikipedia.org/wiki/K-means_clustering. It attempts to hill-climb to a solution, so you might want to try it a number of times with different random starts.

我们尝试找到点和簇的排列，以使从每个簇中的光线(延伸为线)到与每个簇相关的点的平方距离的平方和最小.我们知道从点到直线的距离的平方是二次方( https://en. wikipedia.org/wiki/Distance_from_a_point_to_a_line )，因此，如果您知道哪条线进入哪个聚类，则可以找到该聚类的点，从而将其平方距离的总和最小化.

We try and find the arrangements of points and clusters that minimizes the sum of squared distances from the rays in each cluster (extended to become lines) to the point associated with each cluster. We know that the square of the distance from a point to a line is a quadratic (https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line) so if you know which lines go into which cluster, you can find the point for that cluster which minimizes the sum of squared distances for it.

如果您知道点，但不知道哪些线进入哪个簇，则可以将每条线分配给点最接近点的簇.

If you know the points, but not which lines go in which clusters, you can assign each line to the cluster whose point is closest to it.

因此，首先将线随机分配到簇中.现在找到每个聚类的点，该点将平方距离的总和最小化.现在您有了点，将每条线放入点最接近的群集中，进一步减小了平方距离的总和.现在，您将线的排列方式改为了不同的簇，重新计算了点，再次减小了平方距离的总和.显然，您可以重复此过程，减少每一步的平方和，直到收敛到某个局部最小值为止.

So start with a random assignment of lines into clusters. Now find the point for each cluster which minimizes the sum of squared distances. Now you have points, put each line into the cluster whose point is closest, further reducing the sum of squared distances. Now you have a different arrangement of lines into clusters, recalculate the points, reducing the sum of squared distances again. Clearly you can repeat this process, reducing the sum of squared distances at each step, until you converge to some local minimum.

我建议您尝试多次，每次都从不同的随机起点开始，并查看同一答案是否在结束时出现多次，在这种情况下，您可能会发现一个接近整体的问题.最佳，或者至少是非常突出的局部最小值.

I suggest that you try this a number of times, starting from different random starts each time, and look to see if the same answer appears more than once at the end, in which case you might be finding something close to a global optimum, or at least a very prominent local minimum.

这篇关于光线的聚类算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！