Hierarchical clustering: Difference between revisions

Revision as of 07:23, 11 November 2024

Revision as of 04:32, 19 April 2025

Line 13:

== Complexity ==

The standard algorithm for '''hierarchical agglomerative clustering''' (HAC) has a [[time complexity]] of <math>\mathcal{O}(n^3)</math> and requires <math>\Omega(n^2)</math> memory, which makes it too slow for even medium data sets. However, for some special cases, optimal efficient agglomerative methods (of complexity <math>\mathcal{O}(n^2)</math>) are known: '''SLINK'''<!--boldface per WP:R#PLA--><ref name="SLINK">{{cite journal | author=R. Sibson | title=SLINK: an optimally efficient algorithm for the single-link cluster method | journal=The Computer Journal | volume=16 | issue=1 | pages=30–34 | year=1973 | publisher=British Computer Society | url=http://www.cs.gsu.edu/~wkim/index_files/papers/sibson.pdf | doi=10.1093/comjnl/16.1.30| doi-access=free }}</ref> for [[Single-linkage clustering|single-linkage]] and CLINK<ref name="CLINK">{{cite journal | author=D. Defays | title=An efficient algorithm for a complete-link method | journal=The Computer Journal | volume=20 | issue=4 | pages=364–6 | year=1977 | publisher=British Computer Society | doi=10.1093/comjnl/20.4.364| doi-access= }}</ref> for [[complete-linkage clustering]]. With a [[heap (data structure)|heap]], the runtime of the general case can be reduced to <math>\mathcal{O}(n^2 \log n)</math>, an improvement on the aforementioned bound of <math>\mathcal{O}(n^3)</math>, at the cost of further increasing the memory requirements. In many cases, the memory overheads of this approach are too large to make it practically usable. Methods exist which use [[quadtree]]s that demonstrate <math>\mathcal{O}(n^2)</math> total running time with <math>\mathcal{O}(n)</math> space.<ref name=":2">{{Cite journal |last=Eppstein |first=David |date=2001-12-31 |title=Fast hierarchical clustering and other applications of dynamic closest pairs |url=https://dl.acm.org/doi/10.1145/351827.351829 |journal=ACM Journal of Experimental Algorithmics |volume=5 |pages=1–es |doi=10.1145/351827.351829 |issn=1084-6654|arxiv=cs/9912014 }}</ref>

Divisive clustering with an exhaustive search is <math>\mathcal{O}(2^n)</math>, but it is common to use faster heuristics to choose splits, such as [[k-means clustering|''k''-means]].

Line 76:

- \min_{m\in B} \sum_{y\in B} d(m,y)</math>

|-

|Medoid linkage<ref>{{Cite conference |last1=Miyamoto |first1=Sadaaki |last2=Kaizu |first2=Yousuke |last3=Endo |first3=Yasunori |date=2016 |title=Hierarchical and Non-Hierarchical Medoid Clustering Using Asymmetric Similarity Measures |url=https://ieeexplore.ieee.org/document/7801678 |conference=2016 Joint 8th International Conference on Soft Computing and Intelligent Systems (SCIS) and 17th International Symposium on Advanced Intelligent Systems (ISIS) |pages=400–403 |doi=10.1109/SCIS-ISIS.2016.0091}}</ref><ref name=":3">{{Cite conference |date=2016 |title=Visual Clutter Reduction through Hierarchy-based Projection of High-dimensional Labeled Data| conference=Graphics Interface |url=https://graphicsinterface.org/wp-content/uploads/gi2016-14.pdf | first1=Dominik|last1=Herr|first2=Qi|last2=Han|first3=Steffen|last3=Lohmann| first4=Thomas |last4=Ertl |access-date=2022-11-04 |website=Graphics Interface |language=en-CA |doi=10.20380/gi2016.14}}</ref>

|<math>d(m_A, m_B)</math> where <math>m_A</math>, <math>m_B</math> are the medoids of the previous clusters

|-

Line 140:

The dendrogram of DIANA can be constructed by letting the splinter group <math>C_\textrm{new}</math> be a child of the hollowed-out cluster <math>C_*</math> each time. This constructs a tree with <math>C_0</math> as its root and <math>n</math> unique single-object clusters as its leaves.

== Limitations ==

# '''Time Complexity''': Hierarchical clustering, especially in its basic agglomerative form, has a high time complexity of  O(n³). This becomes a significant bottleneck for large datasets, limiting its scalability <ref name="CLINK" />.   

# '''Scalability''': Due to the time and space complexity, hierarchical clustering algorithms struggle to handle very large datasets efficiently <ref name=":2" />.   

# '''Sensitivity to Noise and Outliers''': Hierarchical clustering methods can be sensitive to noise and outliers in the data, which can lead to the formation of inaccurate or misleading cluster hierarchies <ref name="SLINK" />.   

# '''Difficulty with High-Dimensional Data''': In high-dimensional spaces, hierarchical clustering can face challenges due to the curse of dimensionality, where data points become sparse, and distance measures become less meaningful. This can result in poorly defined clusters <ref name=":3" />.   

# '''Inability to Handle Non-Convex Shapes and Varying Densities''': Traditional hierarchical clustering methods, like many other clustering algorithms, often assume that clusters are convex and have similar densities. They may struggle to accurately identify clusters with non-convex shapes or varying densities <ref>{{Cite journal |last=Wani |first=Aasim Ayaz |date=2024-08-29 |title=Comprehensive analysis of clustering algorithms: exploring limitations and innovative solutions |url=https://peerj.com/articles/cs-2286 |journal=PeerJ Computer Science |language=en |volume=10 |pages=e2286 |doi=10.7717/peerj-cs.2286 |issn=2376-5992 |pmc=11419652 |pmid=39314716}}</ref>. 

== Software ==