最近我一直在阅读各种层次聚类算法,例如单链接聚类和组平均聚类。总的来说,这些算法往往不易扩展。大多数层次聚类算法的朴素实现是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)吗?