How to understand the drawbacks of Hierarchical Clustering?

Question

Can someone explain the pros and cons of Hierarchical Clustering?

1. Does Hierarchical Clustering have the same drawbacks as K means?
2. What are the advantages of Hierarchical Clustering over K means?
3. When should we use K means over Hierarchical Clustering & vice versa?

Answers to this post explains the drawbacks of k means very well. How to understand the drawbacks of K-means

Answer 1

Whereas $k$-means tries to optimize a global goal (variance of the clusters) and achieves a local optimum, agglomerative hierarchical clustering aims at finding the best step at each cluster fusion (greedy algorithm) which is done exactly but resulting in a potentially suboptimal solution.

One should use hierarchical clustering when underlying data has a hierarchical structure (like the correlations in financial markets) and you want to recover the hierarchy. You can still apply $k$-means to do that, but you may end up with partitions (from the coarsest one (all data points in a cluster) to the finest one (each data point is a cluster)) that are not nested and thus not a proper hierarchy.

If you want to dig into finer properties of clustering, you may not want to oppose flat clustering such as $k$-means to hierarchical clustering such as the Single, Average, Complete Linkages. For instance, all these clustering are space-conserving, i.e. when you are building clusters you do not distort the space, whereas a hierarchical clustering such as Ward is not space-conserving, i.e. at each merging step it will distort the metric space.

To conclude, the drawbacks of the hierarchical clustering algorithms can be very different from one to another. Some may share similar properties to $k$-means: Ward aims at optimizing variance, but Single Linkage not. But they can also have different properties: Ward is space-dilating, whereas Single Linkage is space-conserving like $k$-means.

-- edit to precise the space-conserving and space-dilating properties

Space-conserving: $$D_{ij} \in \left[ \min_{x \in C_i, y \in C_j} d(x,y), \max_{x \in C_i, y \in C_j} d(x,y) \right]$$ where $D_{ij}$ is the distance between clusters $C_i$ and $C_j$ you want to merge, and $d$ is the distance between datapoints.

Space-dilating: $$D(C_i \cup C_j, C_k) \geq \max(D_{ik}, D_{jk}),$$ i.e. by merging $C_i$ and $C_j$ the algorithm will push further away the cluster $C_k$.

Answer 2

Scalability

$k$ means is the clear winner here. $O(n\cdot k\cdot d\cdot i)$ is much better than the $O(n^3 d)$ (in a few cases $O(n^2 d)$) scalability of hierarchical clustering because usually both $k$ and $i$ and $d$ are small (unfortunately, $i$ tends to grow with $n$, so $O(n)$ does not usually hold). Also, memory consumption is linear, as opposed to quadratic (usually, linear special cases exist).

Flexibility

$k$-means is extremely limited in applicability. It is essentially limited to Euclidean distances (including Euclidean in kernel spaces, and Bregman divergences, but these are quite exotic and nobody actually uses them with $k$-means). Even worse, $k$-means only works on numerical data (which should actually be continuous and dense to be a good fit for $k$-means).

Hierarchical clustering is the clear winner here. It does not even require a distance - any measure can be used, including similarity functions simply by preferring high values to low values. Categorial data? sure just use e.g. Jaccard. Strings? Try Levenshtein distance. Time series? sure. Mixed type data? Gower distance. There are millions of data sets where you can use hierarchical clustering, but where you cannot use $k$-means.

Model

No winner here. $k$-means scores high because it yields a great data reduction. Centroids are easy to understand and use. Hierarchical clustering, on the other hand, produces a dendrogram. A dendrogram can also be very very useful in understanding your data set.

Answer 3

I just wanted to add to the other answers a bit about how, in some sense, there is a strong theoretical reason to prefer certain hierarchical clustering methods.

A common assumption in cluster analysis is that the data are sampled from some underlying probability density $f$ that we don't have access to. But suppose we had access to it. How would we define the clusters of $f$?

A very natural and intuitive approach is to say that the clusters of $f$ are the regions of high density. For example, consider the two-peaked density below:

By drawing a line across the graph we induce a set of clusters. For instance, if we draw a line at $\lambda_1$, we get the two clusters shown. But if we draw the line at $\lambda_3$, we get a single cluster.

To make this more precise, suppose we have an arbitrary $\lambda > 0$. What are the clusters of $f$ at level $\lambda$? They are the connected component of the superlevel set $\{x : f(x) \geq \lambda \}$.

Now instead of picking an arbitrary $\lambda$ we might consider all $\lambda$, such that the set of "true" clusters of $f$ are all connected components of any superlevel set of $f$. The key is that this collection of clusters has hierarchical structure.

Let me make that more precise. Suppose $f$ is supported on $\mathcal X$. Now let $C_1$ be a connected component of $\{ x : f(x) \geq \lambda_1 \}$, and $C_2$ be a connected component of $\{ x : f(x) \geq \lambda_2 \}$. In other words, $C_1$ is a cluster at level $\lambda_1$, and $C_2$ is a cluster at level $\lambda_2$. Then if $\lambda_2 < \lambda_1$, then either $C_1 \subset C_2$, or $C_1 \cap C_2 = \emptyset$. This nesting relationship holds for any pair of clusters in our collection, so what we have is in fact a hierarchy of clusters. We call this the cluster tree.

So now I have some data sampled from a density. Can I cluster this data in a way that recovers the cluster tree? In particular, we'd like a method to be consistent in the sense that as we gather more and more data, our empirical estimate of the cluster tree grows closer and closer to the true cluster tree.

Hartigan was the first to ask such questions, and in doing so he defined precisely what it would mean for a hierarchical clustering method to consistently estimate the cluster tree. His definition was as follows: Let $A$ and $B$ be true disjoint clusters of $f$ as defined above -- that is, they are connected components of some superlevel sets. Now draw a set of $n$ samples iid from $f$, and call this set $X_n$. We apply a hierarchical clustering method to the data $X_n$, and we get back a collection of empirical clusters. Let $A_n$ be the smallest empirical cluster containing all of $A \cap X_n$, and let $B_n$ be the smallest containing all of $B \cap X_n$. Then our clustering method is said to be Hartigan consistent if $\Pr(A_n \cap B_n) = \emptyset \to 1$ as $n \to \infty$ for any pair of disjoint clusters $A$ and $B$.

Essentially, Hartigan consistency says that our clustering method should adequately separate regions of high density. Hartigan investigated whether single linkage clustering might be consistent, and found that it is not consistent in dimensions > 1. The problem of finding a general, consistent method for estimating the cluster tree was open until just a few years ago, when Chaudhuri and Dasgupta introduced robust single linkage, which is provably consistent. I'd suggest reading about their method, as it is quite elegant, in my opinion.

So, to address your questions, there is a sense in which hierarchical cluster is the "right" thing to do when attempting to recover the structure of a density. However, note the scare-quotes around "right"... Ultimately density-based clustering methods tend to perform poorly in high dimensions due to the curse of dimensionality, and so even though a definition of clustering based on clusters being regions of high probability is quite clean and intuitive, it often is ignored in favor of methods which perform better in practice. That isn't to say robust single linkage isn't practical -- it actually works quite well on problems in lower dimensions.

Lastly, I'll say that Hartigan consistency is in some sense not in accordance with our intuition of convergence. The problem is that Hartigan consistency allows a clustering method to greatly over-segment clusters such that an algorithm may be Hartigan consistent, yet produce clusterings which are very different than the true cluster tree. We have produced work this year on an alternative notion of convergence which addresses these issues. The work appeared in "Beyond Hartigan Consistency: Merge distortion metric for hierarchical clustering" in COLT 2015.

Answer 4

An additional practical advantage in hierarchical clustering is the possibility of visualising results using dendrogram. If you don't know in advance what number of clusters you're looking for (as is often the case...), you can the dendrogram plot can help you choose $k$ with no need to create separate clusterings. Dedrogram can also give a great insight into data structure, help identify outliers etc. Hierarchical clustering is also deterministic, whereas k-means with random initialization can give you different results when run several times on the same data. In k-means, you also can choose different methods for updating cluster means (although the Hartigan-Wong approach is by far the most common), which is no issue with hierarchical method.

EDIT thanks to ttnphns: One feature that hierarchical clustering shares with many other algorithms is the need to choose a distance measure. This is often highly dependent on the particular application and goals. This might be seen as an additional complication (another parameter to select...), but also as an asset - more possibilities. On the contrary, classical K-means algorithm specifically uses Euclidean distance.