组平均聚类的算法复杂度

Question

我最近一直在阅读各种 hierarchical clustering algorithms例如single-linkage clustering和 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) 时间内扫描队列，就无法“更新”优先级队列中的任意值 - 假设优先级队列是二进制堆。 (二叉堆使您可以不断访问 min 元素和 log N 插入/删除，但您不能简单地按值找到一个元素，时间比 O(N) 时间)。由于我们会为每一行元素扫描优先级队列，对于每一行，我们得到 (O(N^3))。

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

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

Answer 1

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