Hierarchical Clustering Algorithm

From GM-RKB
Jump to navigation Jump to search

A Hierarchical Clustering Algorithm is a clustering algorithm that can be implemented into a hierarchical clustering system (to solve a hierarchical clustering task).



References

2019

2016

2014

  • (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/hierarchical_clustering Retrieved:2014-11-21.
    • In data mining, hierarchical clustering (also called hierarchical cluster analysis or HCA) is a method of cluster analysis which seeks to build a hierarchy of clusters. Strategies for hierarchical clustering generally fall into two types[1]:
      • Agglomerative: This is a "bottom up" approach: each observation starts in its own cluster, and pairs of clusters are merged as one moves up the hierarchy.
      • Divisive: This is a "top down" approach: all observations start in one cluster, and splits are performed recursively as one moves down the hierarchy.
In general, the merges and splits are determined in a greedy manner. The results of hierarchical clustering are usually presented in a dendrogram.

In the general case, the complexity of agglomerative clustering is [math]\displaystyle{ O(n^3) }[/math], which makes them too slow for large data sets. Divisive clustering with an exhaustive search is [math]\displaystyle{ O(2^n) }[/math], which is even worse. However, for some special cases, optimal efficient agglomerative methods (of complexity [math]\displaystyle{ O(n^2) }[/math]) are known: SLINK[2] for single-linkage and CLINK[3] for complete-linkage clustering.

  1. Rokach, Lior, and Oded Maimon. “Clustering methods." Data mining and knowledge discovery handbook. Springer US, 2005. 321-352.
  2. D. Defays (1977). "An efficient algorithm for a complete-link method". The Computer Journal. British Computer Society. 20 (4): 364–366. doi:10.1093/comjnl/20.4.364.

2008

  1. In this chapter, we only consider hierarchies that are binary trees like the one shown in Figure 17.1 - but hierarchical clustering can be easily extended to other types of trees.