群平均聚类的算法复杂度

Question

最近我一直在阅读各种层次聚类算法，例如单链接聚类和组平均聚类。总的来说，这些算法往往不易扩展。大多数层次聚类算法的朴素实现是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）时间 - 假设优先队列是二叉堆。（二叉堆可以让您快速访问最小元素和log N的插入/删除，但无法在O（N）时间内通过值简单地查找元素）。由于我们将为每个行元素扫描优先队列，因此对于每行，我们得到（O（N ^ 3））。

优先队列按距离值排序 - 但是算法要求删除优先队列中与k相应的元素，k是最小元素的距离矩阵中的行索引。同样，没有办法在队列中找到这个元素而不进行O（N）扫描。

所以，我认为我可能是错的，因为其他人都说不是这样。有人能解释一下这个算法为什么不是O（N ^ 3），而实际上是O（N ^ 2 logN）吗？

- Siler

Answer 1

我想您的意思是在堆中更新一个条目需要先找到它，而查找需要花费O(N)的时间。为了解决这个问题，您可以维护一个索引，给出每个项目i在堆中的位置heapPos[i]。每次交换两个项目以恢复堆不变式时，您需要修改heapPos[i]中的两个条目以保持索引正确，但这只是在堆中完成的工作量上的一个恒定因子。

- mcdowella

Answer 2

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

所以我认为您确实可以以O（n ^ 2 log n）实现这些。但是实现仍将使用大量（O（n ^ 2））的内存，任何O（n ^ 2）的内容都不会扩展。如果您拥有O（n ^ 2）内存，则通常会在用尽时间之前用尽内存...

实现这些数据结构非常棘手。如果做得不好，这可能比理论上更糟糕的方法还要慢。例如斐波那契堆。它们在纸面上具有良好的属性，但是具有太高的固定成本无法弥补。

- Has QUIT--Anony-Mousse

Answer 3

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

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

实际上，您只需要半个矩阵。

- Malcolm McLean

---

你应该意识到，0.5 * n^2 仍然属于 O(n^2)。保存矩阵的一半并不能减少渐进复杂度。而且你误用了“reciprocal”。按照你的用法，你是在说 d(x,y) = 1 / d(y,x)，但距离是对称的，而不是相互倒数。 - Has QUIT--Anony-Mousse

这意味着找到互补（更好的词）优先队列条目是O(1)。全局最小值表示两次，它们都必须是其优先队列中的第一个条目。 - Malcolm McLean

以上方法每个条目使用一个优先队列（有很好的原因），否则每次需要丢弃O(n)个条目。 - Has QUIT--Anony-Mousse