dm.cs.tu-dortmund.de/en/mlbits/cluster-hac-acceleration/
Accelerating Hierarchical Clustering – Lecture Notes
O}(n^2)\) time and memory.
finding the minimum distance / maximum similarity: \(\mathcal{O}(n^2)\cdot i\)
updating the matrix: \(\mathcal{O}(n)\cdot i\) (with Lance-Williams) or \(\mathcal{O}(n^2)\cdot [...] \) time and \(\mathcal{O}(n^2)\) memory!
Better algorithms can run in guaranteed \(O(n^2)\) time [ Defa77 ; Sibs73 ] for special cases, with priority queues we get \(O(n^2 \log n)\)
[ DaEd84 ; Epps98 ; [...] ; Müll11 ; Murt83 ] ,
\(O(n^2)\) for reducible linkages [ Murt83 ] , or usually \(n^2\) time with caching [ Ande73 ] .
Instead of agglomerative (bottom-up), we can also begin with one cluster, and divide …