我知道显然有针对点的聚类算法,但我有一个不同的场景。我有很多光线,它们的起点都在三维的球体上,它们的方向向量都指向球体的内部有些光线指向一个点A,另一些光线指向一个点B,等等,有一些杂音(即光线并不完全相交)。是否有一种聚类算法允许我根据光线指向的点对光线进行聚类我不知道点A、B等的位置,只知道光线的起点和方向向量。
例如,in this picture是一个示例设置,但在2D中,我不知道哪些光线在开始时是红色或蓝色的我如何将光线聚集成红色和蓝色或者,我如何找到它们指向的点的位置?
我想到的一个解决方案是拍摄一对光线,在这两条光线之间找到最接近的点(在2d中,如果延伸光线,这是交点),然后对每一对光线都这样做(所以我得到n(n-1)/2个点,其中n是光线数)。然后,我可以对这些点使用常规的聚类算法。但是,这似乎不起作用——我在原点只得到一个大点,我不知道为什么会这样。
最佳答案
这里有一些尝试,松散地基于https://en.wikipedia.org/wiki/Random_sample_consensus和https://en.wikipedia.org/wiki/K-means_clustering它试图爬山找到一个解决方案,因此您可能需要尝试多次,每次都有不同的随机启动。
我们试图找到点和簇的排列,使每个簇中光线(延伸成直线)到与每个簇相关联的点的平方距离之和最小化。我们知道点到线的距离的平方是二次方(https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line),所以如果你知道哪些线进入哪个簇,你可以找到那个簇的点,这个簇的平方距离之和最小。
如果知道点,但不知道哪些线进入哪个簇,则可以将每条线指定给其点最近的簇。
所以先把线随机分配到簇中。现在找出每个簇的点,使平方距离之和最小化。现在你有了点,把每一条线放在点最近的簇中,进一步减少平方距离的总和。现在,您将不同的线排列成簇,重新计算点,再次减少平方距离之和。很明显,你可以重复这个过程,在每一步减少平方距离之和,直到你收敛到某个局部最小值。
我建议你尝试多次,每次都从不同的随机开始,看看同一个答案是否在最后出现不止一次,在这种情况下,你可能会发现一些接近全局最优值,或者至少是一个非常显著的局部最小值。