algorithm - 估计两个集群之间的最小距离

Question

我正在为数百万个 50-1000 维点设计一种凝聚式、自下而上的聚类算法。在我的算法的两个部分中，我需要比较两个点簇并决定两个簇之间的分离。 精确 距离是所有点对 P1-P2 的最小欧氏距离，其中 P1 取自簇 C1，P2 取自簇 C2。如果 C1 有 X 个点，C2 有 Y 个点，那么这需要 X*Y 距离测量。

我目前以需要 X+Y 测量的方式估算此距离:

1. 找到簇 C1 的质心 Ctr1。
2. 在簇 C2 中找到最接近 Ctr1 的点 P2。 (Y 比较。)
3. 找到 C1 中最接近 P2 的点 P1。 (X 比较。)
4. 从 P1 到 P2 的距离是集群 C1 和 C2 之间距离的近似度量。它是真实值的上限。

如果簇大致呈球形，则效果很好。我的测试数据是由椭圆高斯簇组成的，所以效果很好。然而，如果簇有奇怪的、折叠的、弯曲的形状，它可能会产生糟糕的结果。我的问题是:

是否有一种算法使用比 X+Y 距离测量更少的距离，并且在平均情况下产生良好的准确性？

或

是否有一种算法(像我的)使用 X+Y 距离测量但提供比我的精度更高的算法？

(我正在用 C# 编写此程序，但可以用伪代码或任何其他语言描述算法。请避免引用 R 或 Matlab 中的专门库函数。具有概率保证的算法，如“95% 机会该距离在最小值的 5% 以内”是可以接受的。)

注意: 我刚刚发现了这个相关问题，它讨论了一个类似的问题，但不一定针对高维度。 Given two (large) sets of points, how can I efficiently find pairs that are nearest to each other?

注意:我刚刚发现这叫做双色最近对问题。

对于上下文，这里是整个聚类算法的概述:

1. 第一步使用空间填充曲线(希尔伯特曲线)将最密集的区域合并为小簇。它会遗漏异常值，并且经常无法合并彼此非常接近的相邻集群。然而，它确实发现了一个特征性的最大链接距离。间隔小于此特征距离的所有点必须聚类在一起。此步骤没有将预定义的簇数作为其目标。

2. 如果集群的最小距离小于最大链接距离，第二遍通过将集群组合在一起来执行单链接凝聚。这不是层次聚类；它是基于分区的。相互之间的最小距离小于此最大链接距离的所有集群将被合并。此步骤没有将预定义的簇数作为其目标。

3. 第三遍执行额外的单链接凝聚，对所有簇间距离进行排序，并且仅组合簇直到簇数等于预定义的目标簇数。它处理一些离群值，倾向于只将离群值与大集群合并。如果有很多异常值(通常是异常值)，这可能无法减少目标的聚类数量。

4. 第四遍将所有剩余的异常值 与最近的大集群相结合，但不会导致大集群与其他大集群合并。 (这可以防止两个相邻的集群由于异常值在它们之间形成一条细链而意外合并。)

Answer 1

您可以使用索引。这是非常经典的解决方案。

空间索引可以帮助您在大约 O(log n) 时间内找到任何点的最近邻居。因此，如果您的集群有 n 和 m 个对象，请选择较小的集群并索引较大的集群，以在 O(n log m) 或 O(m log n) 中找到最接近的对。

一种更简单的启发式方法是多次重复您的想法，从而缩小候选范围。所以你从两个集群中找到了一对好的对象 a，b。然后你丢弃每个集群中必须(通过三角形不等式)更远(使用上限!)的所有对象。然后您重复此操作，但不再次选择相同的 a、b。一旦你的候选集停止改进，就只对剩余的对象进行成对比较。这种方法的最坏情况应该保持为 O(n*m)。