估计两个集群之间的最小距离
Estimate the minimum Distance between two Clusters
我正在为数百万个 50-1000 维点设计一种凝聚的、自下而上的聚类算法。在我的算法的两个部分中，我需要比较两个点簇并决定两个簇之间的分离。 exact 距离是所有点对 P1-P2 的最小欧氏距离，其中 P1 取自集群 C1，P2 取自集群 C2。如果 C1 有 X 个点，C2 有 Y 个点，那么这需要 X*Y 距离测量。
我目前以需要 X+Y 测量的方式估算此距离：
- 找到簇 C1 的质心 Ctr1。
- 在聚类C2中找到距离Ctr1最近的点P2。 （Y 比较。）
- 找到C1中距离P2最近的点P1。 （X 比较。）
- 从 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?
注意：我刚刚发现这叫做双色最近对问题。
对于上下文，这里是整个聚类算法的概述：
第一遍使用 space 填充曲线（希尔伯特曲线）将最密集的区域合并为小簇。它会遗漏异常值，并且经常无法合并彼此非常接近的相邻集群。然而，它确实发现了一个特征最大链接距离。间隔小于此特征距离的所有点必须聚类在一起。此步骤没有将预定义的簇数作为其目标。
第二遍执行单链接聚集，如果它们的最小距离小于最大链接距离[，则将它们组合在一起。 =62=]。这不是层次聚类；它是基于分区的。相互之间的最小距离小于此最大链接距离的所有集群将被合并。此步骤没有将预定义的簇数作为其目标。
第三遍执行额外的单链接聚集，对所有簇间距离进行排序，并且仅组合簇直到簇数等于预定义的目标数集群。它处理一些离群值，更喜欢只合并具有大集群的离群值。如果有很多离群值（通常是），这可能无法减少目标的聚类数量。
第四遍将所有剩余的异常值与最近的大集群合并，但不会导致大集群与其他大集群合并。 （这可以防止两个相邻的集群由于异常值在它们之间形成细链而意外合并。）
您可以使用 索引。这是非常经典的解决方案。
空间索引可以帮助您在大约 O(log n) 时间内找到任何点的最近邻居。因此，如果您的集群有 n 和 m 个对象，请选择较小的集群并索引较大的集群，以在 O(n log m) 或 O(m log n) 中找到最接近的对。
一种更简单的启发式方法是多次重复您的想法，从而缩小您的候选人集。所以你从两个集群中找到了一对好的对象 a，b。然后你丢弃每个集群中必须（通过三角形不等式）更远（使用上限！）的所有对象。
然后你重复这个，但是 而不是 再次选择相同的 a，b。一旦你的候选集停止改进，就只对剩余的对象进行成对比较。这种方法的最坏情况应该保持为 O(n*m).
我发现一篇论文描述了线性时间、随机、epsilon-approximate 最近双色点问题的算法：
http://www.cs.umd.edu/~samir/grant/cp.pdf
我会尝试实现它，看看它是否有效。
更新 - 经过进一步研究，很明显运行时间与 3^D 成正比，其中 D 是维数。这是无法接受的。在尝试了其他几种方法后，我想到了以下方法。
- 使用有效但不完整的方法将粗略聚类为 K 个簇。此方法将正确地聚类一些点，但会产生太多聚类。这些小集群仍有待进一步整合以形成更大的集群。该方法将确定被认为在同一簇中的点之间的上限距离 DMAX。
- 按希尔伯特曲线顺序对点进行排序。
- 丢弃紧接在同一集群中的邻居之前和之后的所有点。通常，这些是集群的内部点，而不是表面点。
- 对于每个点 P1，向前搜索，但不超过同一簇中的下一个点。
- 计算从聚类 C1 的点 P1 到聚类 C2 的每个访问点 P2 的距离，如果该距离小于 C1 和 C2 中的点之间测量的任何先前距离，则记录该距离。
- 但是，如果 P1 已经与 C2 中的某个点进行了比较，请不要再次这样做。只对P1和C2中的任意一点进行单次比较
- 所有的比较完成后，最多会记录K(K-1)个距离，很多因为比DMAX大而被丢弃。这些是估计的最近点距离。
- 如果集群比 DMAX 更近，则在集群之间执行合并。
很难想象 Hilbert 曲线是如何在簇之间摆动的，所以我估计这种寻找最接近对的方法的效率是它与 K^2 成正比。然而，我的测试表明它更接近 K。它可能在 K*log(K) 左右。需要进一步研究。
至于准确性：
- 将每个点与其他每个点进行比较是 100% 准确的。
- 使用我的问题中概述的质心方法的距离大约过高 0.1%。
- 使用此方法发现距离最多高 10%，平均高 5%。然而，真正最近的集群几乎总是出现在第一到第三最近的集群中，所以从质量上讲它是好的。使用这种方法最终的聚类结果非常好。我最终的聚类算法似乎与 DNK 或 DNK*Log(K) 成正比。
我正在为数百万个 50-1000 维点设计一种凝聚的、自下而上的聚类算法。在我的算法的两个部分中，我需要比较两个点簇并决定两个簇之间的分离。 exact 距离是所有点对 P1-P2 的最小欧氏距离，其中 P1 取自集群 C1，P2 取自集群 C2。如果 C1 有 X 个点，C2 有 Y 个点，那么这需要 X*Y 距离测量。
我目前以需要 X+Y 测量的方式估算此距离：
- 找到簇 C1 的质心 Ctr1。
- 在聚类C2中找到距离Ctr1最近的点P2。 （Y 比较。）
- 找到C1中距离P2最近的点P1。 （X 比较。）
- 从 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?
注意：我刚刚发现这叫做双色最近对问题。
对于上下文，这里是整个聚类算法的概述：
第一遍使用 space 填充曲线（希尔伯特曲线）将最密集的区域合并为小簇。它会遗漏异常值，并且经常无法合并彼此非常接近的相邻集群。然而，它确实发现了一个特征最大链接距离。间隔小于此特征距离的所有点必须聚类在一起。此步骤没有将预定义的簇数作为其目标。
第二遍执行单链接聚集，如果它们的最小距离小于最大链接距离[，则将它们组合在一起。 =62=]。这不是层次聚类；它是基于分区的。相互之间的最小距离小于此最大链接距离的所有集群将被合并。此步骤没有将预定义的簇数作为其目标。
第三遍执行额外的单链接聚集，对所有簇间距离进行排序，并且仅组合簇直到簇数等于预定义的目标数集群。它处理一些离群值，更喜欢只合并具有大集群的离群值。如果有很多离群值（通常是），这可能无法减少目标的聚类数量。
第四遍将所有剩余的异常值与最近的大集群合并，但不会导致大集群与其他大集群合并。 （这可以防止两个相邻的集群由于异常值在它们之间形成细链而意外合并。）
您可以使用 索引。这是非常经典的解决方案。
空间索引可以帮助您在大约 O(log n) 时间内找到任何点的最近邻居。因此，如果您的集群有 n 和 m 个对象，请选择较小的集群并索引较大的集群，以在 O(n log m) 或 O(m log n) 中找到最接近的对。
一种更简单的启发式方法是多次重复您的想法，从而缩小您的候选人集。所以你从两个集群中找到了一对好的对象 a，b。然后你丢弃每个集群中必须（通过三角形不等式）更远（使用上限！）的所有对象。 然后你重复这个，但是 而不是 再次选择相同的 a，b。一旦你的候选集停止改进，就只对剩余的对象进行成对比较。这种方法的最坏情况应该保持为 O(n*m).
我发现一篇论文描述了线性时间、随机、epsilon-approximate 最近双色点问题的算法：
http://www.cs.umd.edu/~samir/grant/cp.pdf
我会尝试实现它，看看它是否有效。
更新 - 经过进一步研究，很明显运行时间与 3^D 成正比，其中 D 是维数。这是无法接受的。在尝试了其他几种方法后，我想到了以下方法。
- 使用有效但不完整的方法将粗略聚类为 K 个簇。此方法将正确地聚类一些点，但会产生太多聚类。这些小集群仍有待进一步整合以形成更大的集群。该方法将确定被认为在同一簇中的点之间的上限距离 DMAX。
- 按希尔伯特曲线顺序对点进行排序。
- 丢弃紧接在同一集群中的邻居之前和之后的所有点。通常，这些是集群的内部点，而不是表面点。
- 对于每个点 P1，向前搜索，但不超过同一簇中的下一个点。
- 计算从聚类 C1 的点 P1 到聚类 C2 的每个访问点 P2 的距离，如果该距离小于 C1 和 C2 中的点之间测量的任何先前距离，则记录该距离。
- 但是，如果 P1 已经与 C2 中的某个点进行了比较，请不要再次这样做。只对P1和C2中的任意一点进行单次比较
- 所有的比较完成后，最多会记录K(K-1)个距离，很多因为比DMAX大而被丢弃。这些是估计的最近点距离。
- 如果集群比 DMAX 更近，则在集群之间执行合并。
很难想象 Hilbert 曲线是如何在簇之间摆动的，所以我估计这种寻找最接近对的方法的效率是它与 K^2 成正比。然而，我的测试表明它更接近 K。它可能在 K*log(K) 左右。需要进一步研究。
至于准确性：
- 将每个点与其他每个点进行比较是 100% 准确的。
- 使用我的问题中概述的质心方法的距离大约过高 0.1%。
- 使用此方法发现距离最多高 10%，平均高 5%。然而，真正最近的集群几乎总是出现在第一到第三最近的集群中，所以从质量上讲它是好的。使用这种方法最终的聚类结果非常好。我最终的聚类算法似乎与 DNK 或 DNK*Log(K) 成正比。