羣平均聚類算法的複雜性

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）內存，您通常會在內存不足時耗盡內存...

實現這些數據結構非常棘手。如果做得不好，這可能最終會比理論上更糟糕的方法慢。例如斐波那契堆。他們在紙上擁有不錯的性能，但其成本太高，無法付清。