估计两个聚类之间的最小距离

Question

我正在设计一个自底向上的聚类算法，用于数百万个50-1000维点。在我的算法的两个部分中，我需要比较两个点簇并决定它们之间的分离度。"精确距离"是所有点P1-P2对中取最小欧几里得距离，其中P1来自簇C1，P2来自簇C2。如果C1有X个点，C2有Y个点，则需要进行X*Y次距离测量。

目前我以一种需要X+Y次测量的方式估计这个距离：

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

如果簇大致球形，则这种方法效果非常好。我的测试数据由椭圆高斯簇组成，因此它非常有效。但是，如果簇具有奇怪、折叠、弯曲的形状，则可能会产生较差的结果。我的问题是：

是否有一种算法可以使用少于X+Y的距离测量，在平均情况下产生良好的准确度？

或者

是否有一种算法（像我的算法一样）使用X+Y的距离测量，但提供比我的算法更好的准确度？

（我正在使用C#进行编程，但伪代码或任何其他语言的算法描述都可以。请避免引用来自R或Matlab的专门库函数。具有概率保证的算法，如“距离在最小值的5％内的95％机会”是可接受的。）

注意：我刚发现了这个相关问题，它讨论了类似的问题，但不一定针对高维度。 给定两组（大）点，如何有效地找到彼此最近的对？

注意：我刚发现这被称为二色最近对问题。

为了背景，这里是整体聚类算法的概述：

1. 第一次遍历使用空间填充曲线（Hilbert Curve）将最密集的区域合并为小群集。它会忽略离群值，并且通常无法合并非常接近的相邻群集。但是，它确实发现了一个特征的最大链接距离。所有距离小于此特征距离的点必须聚类在一起。此步骤没有预定义的目标聚类数。

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

3. 第三次遍历执行额外的单链接凝聚，对所有群集之间的距离进行排序，并仅在群集数量等于预定义的目标聚类数时才合并群集。它处理一些离群值，更喜欢仅将离群值与大型群集合并。如果有许多离群值（通常如此），则可能无法将聚类数减少到目标。

4. 第四次遍历将所有剩余的离群值与最近的大型群集组合，但不会导致大型群集与其他大型群集合并。（这可以防止由于其离群值在它们之间形成细链而意外合并两个相邻的群集。）

- Paul Chernoch

---

你尝试过类似这样的东西吗？ - Borbag

不！知道问题的“名称”会有所帮助！谢谢！我会阅读这篇文章。 - Paul Chernoch

你能尝试降低维度吗？或者所有的维度都大致同等重要吗？ - kfx

你必须按照它们的维度使用吗？还是可以对其进行主成分分析，并仅保留重要的部分？ - Borbag

我从未执行过PCA。它看起来很有趣，但数学很可怕。不过，我确实执行了一些简单的数据降维，比如去除冗余的维度或那些具有成对的1-1映射的维度。 - Paul Chernoch

Answer 1

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

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

更简单的启发式方法是多次迭代您的想法，缩小候选集合。所以你从两个聚类中找到一对好的对象a、b。然后丢弃每个聚类中必须（通过三角不等式）相距更远（使用上限！）的所有对象。然后重复此操作，但不再次选择相同的 a，b。一旦您的候选集合停止改进，请仅对剩余对象进行成对比较。该方法的最坏情况应该仍为O(n*m)。

- Has QUIT--Anony-Mousse

---

在20个或以上的维度上，距离 不再可靠。这就是索引失败的原因。请参见维数灾难；它关乎距离过于相似。希尔伯特曲线通常也会在5个维度左右崩溃。因为要分裂每个维度仅一次，并且有非空分区，您需要2^d个对象。如果要获得漂亮的曲线，则需要至少2^{4d}个对象。您有2^80个对象吗？ - Has QUIT--Anony-Mousse

关于Anony在“维度灾难”评论中提到的问题，您的数据是否真的沿着所有这些维度具有方差？PCA或SVD表示了什么？ - nicholas

@nicholas - 对于我的真实世界数据，我会删除冗余的维度（这将把我的问题从40,000个维度减少到950个维度）。在这950个维度中，我确实有有意义的差异。（我的领域是使用UPS或Fedex的邮编到邮编交货时间。） - Paul Chernoch

@PaulChernoch R树永远不会出现空分区。你可能在想四叉树？ - Has QUIT--Anony-Mousse

是的。但是为什么不直接将实际交货时间作为距离呢？ - Has QUIT--Anony-Mousse

Answer 2

我找到了一篇论文，描述了一个用于最近的双色点问题的线性时间、随机化、epsilon-近似算法。

http://www.cs.umd.edu/~samir/grant/cp.pdf

我将尝试实现它并查看其是否有效。

更新 - 经过进一步研究，显然运行时间与维度数D成比例，其中D是维度数。这是不可接受的。在尝试了几种其他方法后，我找到了以下解决方案。

1. 使用高效但不完整的方法对K个簇进行粗略聚类。该方法将正确地聚类一些点，但会产生太多的簇。这些小簇需要进一步合并形成更大的簇。该方法将确定被视为同一簇中的点之间的上限距离DMAX。
2. 按希尔伯特曲线顺序排序点。
3. 立即丢弃所有紧邻同一簇中的邻居的前后点。往往这些是簇的内部点，而不是表面点。
4. 对于每个点P1，向前搜索，但不超过来自同一簇的下一个点。
5. 计算从簇C1中的点P1到访问的每个簇C2中的点P2的距离，并记录距离，如果它比先前在C1和C2之间测量的任何距离都要小。
6. 然而，如果P1已经与C2中的某个点进行了比较，则不要再次进行比较。只在P1和C2中的任何一个点之间进行单次比较。
7. 完成所有比较后，最多会记录K（K-1）个距离，并且许多距离因大于DMAX而被丢弃。这些是估计的最接近点距离。
8. 如果它们比DMAX更近，则在簇之间执行合并。

很难想象希尔伯特曲线在聚类之间蜿蜒前进的方式，因此我对于这种寻找最近对的方法效率的估计是与K^2成正比的。然而，我的测试表明它更接近于K，可能在K*log(K)左右。需要进一步研究。

至于准确性：

• 将每个点与其他每个点进行比较是100%准确的。
• 使用我在问题中概述的质心方法会导致距离高出约0.1%。
• 使用这种方法找到的距离最多会高出10%，平均高出5%。然而，真正的最近聚类几乎总是出现在前三个最近的聚类中，因此从定性上讲，这是好的。使用这种方法得到的最终聚类结果非常好。我的最终聚类算法似乎与DNK或DNK*Log(K)成正比。

- Paul Chernoch