群平均聚类算法的复杂性

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)时间内扫描队列，就无法“更新”优先队列中的任意值 - 假设优先队列是二进制堆。 （一个二进制堆让你可以连续访问最小元素和插入/删除，但不能简单地按值查找元素，优于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）内存，您通常会在内存不足时耗尽内存...

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