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

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%范围内"是可以接受的."

注意:我刚刚发现了这个相关的问题,它讨论了类似的问题,但不一定是针对高维度的问题.给定两个(大)点集,我如何有效地找到彼此最近的对？

注意:我刚刚发现这被称为双色最近对问题.

对于上下文,以下是整体聚类算法的概述:

1. 第一次通过使用空间填充曲线(希尔伯特曲线)将最密集的区域合并成小的簇.它错过了异常值,并且经常无法合并彼此非常接近的相邻聚类.但是,它确实发现了一个特征性的最大连杆距离.所有以小于此特征距离分隔的点必须聚集在一起.此步骤没有预定义数量的集群作为其目标.

2. 如果它们的最小距离小于最大连杆距离,则第二次通过通过将簇组合在一起来执行单连杆聚集.这不是层次聚类; 它是基于分区的.将组合彼此的最小距离小于该最大连杆距离的所有簇.此步骤没有预定义数量的集群作为其目标.

3. 第三遍执行额外的单链接聚集,对所有簇间距离进行排序,并且仅组合簇,直到簇的数量等于预定义的目标簇数.它处理一些异常值,更喜欢只合并具有大簇的异常值.如果存在许多异常值(通常是异常值),则可能无法减少到目标的簇数.

4. 第四遍将所有剩余的异常值与最近的大型集群组合在一起,但不会导致大型集群与其他大型集群合并.(这可以防止两个相邻的簇意外地合并,因为它们的异常值在它们之间形成一条细链.)

Answer 1

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

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

我将尝试实施它，看看它是否有效。

更新 - 经过进一步研究，很明显，运行时间与 3^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) 成正比。