组平均聚类的算法复杂度

Question

我最近一直在阅读各种 hierarchical clustering algorithms such as single-linkage clustering and group average clustering。通常，这些算法的扩展性不好。大多数层次聚类算法的简单实现是 O(N^3)，但单链接聚类可以在 O(N^2) 时间内实现。

还声称可以在O(N^2 logN)时间内实现组平均聚类。这就是我的问题。

我根本不明白这怎么可能。

解释后解释，如：

http://nlp.stanford.edu/IR-book/html/htmledition/time-complexity-of-hac-1.html

http://nlp.stanford.edu/IR-book/completelink.html#averagesection

https://en.wikipedia.org/wiki/UPGMA#Time_complexity

... 声称可以通过使用优先级队列在 O(N^2 logN) 时间内完成组平均层次聚类。但是当我阅读实际解释或伪代码时，在我看来，它总是比 O(N^3).

更好。

本质上，算法如下：

For an input sequence of size N:

Create a distance matrix of NxN #(this is O(N^2) time)
For each row in the distance matrix:
   Create a priority queue (binary heap) of all distances in the row

Then:

For i in 0 to N-1:
  Find the min element among all N priority queues # O(N)
  Let k = the row index of the min element

  For each element e in the kth row:
    Merge the min element with it's nearest neighbor
    Update the corresponding values in the distance matrix
    Update the corresponding value in priority_queue[e]

所以对我来说，最后步似乎使它成为一个 O(N^3) 算法。如果不在 O(N) 时间内扫描队列，就无法 "update" 优先级队列中的任意值 - 假设优先级队列是二进制堆。（二叉堆使您可以持续访问 min 元素和 log N insertion/deletion，但您不能简单地按值找到一个元素，时间比 O(N) 快）。由于我们会为每一行元素扫描优先级队列，对于每一行，我们得到 (O(N^3))。

优先级队列按距离值排序 - 但有问题的算法要求删除优先级队列中对应于k行的元素最小元素的距离矩阵中的索引。同样，如果不进行 O(N) 扫描，就无法在队列中找到该元素。

所以，我想我可能是错的，因为其他人都不这么说。有人能解释一下这个算法是如何不是 O(N^3)，但实际上是 O(N^2 logN) 吗？

Answer 1

我想你是说问题是为了更新堆中的条目你必须找到它，而找到它需要时间 O(N)。你可以做的是维护一个索引，为每个项目 i 提供它在堆中的位置 heapPos[i] 。每次交换两个项目以恢复堆不变性时，您需要修改 heapPos[i] 中的两个条目以保持索引正确，但这只是堆中完成工作的一个常数。

Answer 2

不是，因为距离矩阵是对称的。

如果第 0 行的第一个条目到第 5 列，距离为 1，并且在系统中最低，则第 5 行的第一个条目必须是与第 0 列的互补条目，距离为 1 .

事实上你只需要一个半矩阵。

Answer 3

如果您将位置存储在堆中（这会增加另一个 O(n) 内存），您可以在不扫描的情况下仅在更改的位置上更新堆。这些更新仅限于堆上的两个路径（一个删除，一个更新）并在 O(log n) 中执行。或者，您可以按旧优先级进行二进制搜索，这也可能在 O(log n) 中（但速度较慢，上述方法为 O(1)）。

恕我直言，您确实可以在 O(n^2 log n) 中实现这些。但是该实现仍将使用大量 (O(n^2)) 的内存，O(n^2) 的任何内容都会 而不是 规模。你平时运行在你之前内存不足运行如果你有 O(n^2) 内存...

实现这些数据结构非常棘手。如果做得不好，这最终可能会比理论上更糟糕的方法慢。例如斐波那契堆。它们在纸面上具有不错的性能，但持续成本太高而无法偿还。

组平均聚类的算法复杂度

Algorithmic complexity of group average clustering

algorithm

cluster-analysis

hierarchical-clustering