2

我正在使用层次聚类来尝试可视化已扁平化为二维的大量数据。我想要做的是创建一个可视化，允许我通过将集群渲染为其组成点的凸包来查看层次结构中不同高度的数据。这个问题最难的部分是我需要一种算法，当我向上移动时，它可以有效地合并对集群的凸包。我已经看到了很多用于在 O(n log n) 时间内计算点的凸包的算法，但在这种情况下，利用问题的子结构似乎会更有效，但我不完全确定如何。

编辑：

有关更多信息，数据结构是一个数组，它从聚类的原始点开始，然后说明哪些点/聚类被组合以形成下一个聚类。所以它有点像树/指针结构，但包含在一个大数组中。重要的部分是，查看任何超级集群的两个组成集群是有效的，但获取属于集群的所有点的集合并不高效。所以任何合理的算法都必须自下而上地工作。

所以假设我们在某个地方的层次结构的中间，并且预先计算的层次结构表明集群 A 和 B 被合并以产生集群 C。我们是从下往上的，所以我们已经计算了簇 A 和 B 中的点，因此我们只需将它们组合起来即可生成簇 C 的凸包。簇 A 的凸包实际上可以是一个点、一对或一个完整的多边形。集群 B 也是如此。因此，有几种情况应该如何合并这些以形成集群 C 的凸包，但我敢打赌，有一个聪明的解决方案可能会将单例和对以与多边形相同的方式处理。

最明显的解决方案是使用集群 A 和 B 的凸包的组合点集来计算凸包。但我需要在 100k 点的层次结构上执行此操作，所以我想知道是否有更有效的组合 A 和 B 的凸包的方法。

编辑2：

         /----5
    1---/    / \
   / \      / B 8
  2 A 3  C 6   /
   \ /      \ /
    4--------7

好的，所以我尝试用 ASCII 码来说明我的意思。簇A的凸包是1-2-3-4，B的凸包是5-6-7-8，C的凸包是1-2-4-7-8-5。据推测，集群 A 和 B 在它们的外壳内包含额外的点，但这些显然不可能成为 C 外壳的一部分，因此问题在于确定在何处“拼接”集群 A 和 B 的外壳以形成C 的船体，基于点的坐标。这是整个过程的归纳步骤。（最终 C 将与集群 D 组合，依此类推，直到算法以最顶层的集群结束，该集群将所有点的凸包作为其凸包）。

4

2 回答 2

3

There are at least two convex hull merge algorithms that I'm aware of -- rotating calipers of Toussaint (section 5 of the paper) and the bridging algorithm of Preparata and Hong (see section 3 of the paper). Both of these algorithms take time linear in h = h1 + h2, where h1 and h2 are the number of hull vertices in the first and second convex hulls respectively.

于 2012-10-21T11:21:38.707 回答
2

有多种方法可让您在添加新点时“更新”凸包。此外，一些凸包和 Delaunay 三角剖分的方法已经很好地由内而外地工作，这应该很好地发挥作用。看看 s-hull 算法。

但是，由于您在谈论层次聚类，因此在涉及复杂性时，凸包可能是您最不关心的问题。

层次聚类不能很好地扩展到大型数据集，因为算法通常O(n^3)是自然的（使它们成为您发现仍在实践中使用的最慢的聚类算法之一）。因此，考虑到您的聚类更昂贵，另外计算多个凸包应该不会产生太大的影响。您可能只需要一个快速、增量的O(n log n)凸包算法实现。

于 2012-10-19T21:52:30.053 回答