17
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ In this answer I touched some of potentially problematic facets of hierarchical agglomerative cluster analysis. The main "drawback" is that it is noniterative, single-pass greedy algorithm. With a greedy algorithm, you optimize the current step's task, which - for most HC methods - does not necessarily guarantee the best partition at a distant future step. The main advantage of HC is that it is flexible with respect to the choice of proximity measure to use. @Mic has already given a good answer below, so I'm just echoing. $\endgroup$ – ttnphns Nov 27 '15 at 13:32
11
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Can you give few more examples of data having hierarchical structure? Didn't follow the financial market example. $\endgroup$ – GeorgeOfTheRF Nov 27 '15 at 13:16
  • $\begingroup$ Sure. cf. arxiv.org/pdf/cond-mat/9802256.pdf or simply Figure 7 in arxiv.org/pdf/1506.00976.pdf which depicts a correlation matrix which has a (noisy) hierarchical correlation block structure: you can notice blocks on the main diagonal, which are divided into more blocks, each one divided into even more blocks. It corresponds roughly to a subdivision in regions (Europe, US, Asia ex-Japan, Japan), then each region divided by the asset quality (say high quality vs. junk), then divided by the big industrial sectors (retail, industry, media), further subdiv into (aerospace, auto...) $\endgroup$ – mic Nov 27 '15 at 13:37
  • 3
    $\begingroup$ +1. However, should use hierarchical clustering when underlying data has a hierarchical structure... and you want to recover the hierarchy Not necessarily. In most cases rather on the contrary. The hierarhy of HC is rather a story of the algo than a structure of the data. Still, this question is ultimately philosophical/logical, not so statistical. $\endgroup$ – ttnphns Nov 27 '15 at 13:40
  • $\begingroup$ Ward is not space-conserving, i.e. at each merging step it will distort the metric space. Can you write more about it? This is not very much clear. $\endgroup$ – ttnphns Nov 27 '15 at 13:41
  • $\begingroup$ Ward is space-dilating, whereas Single Linkage is space-conserving like k-means. Did you want to say space-contracting for single linkage? $\endgroup$ – ttnphns Nov 27 '15 at 13:46
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Does Hierarchical fail like k means when clusters are 1)non spherical 2) have different radius 3) have different density? $\endgroup$ – GeorgeOfTheRF Nov 28 '15 at 3:09
  • 2
    $\begingroup$ Both can work, and both can fail. That is why things like dendrograms are useful. Never trust a clustering result to be "correct", ever. $\endgroup$ – Anony-Mousse Nov 28 '15 at 13:02
  • $\begingroup$ Hierarchical clustering may give locally optimise clusters as it is based on greedy approach but K means gives globally optimised clusters. I have also experienced that explanation of hierarchical clustering is relatively easy to business people compare to K means. $\endgroup$ – Arpit Sisodia Sep 9 '17 at 10:13
7
$\begingroup$

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:

enter image description here

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.

$\endgroup$
  • $\begingroup$ This is an interesting way of thinking about hierarchical clustering. I find it strongly reminiscent of clustering by nonparametric density estimation (pdf), which is implemented in R in the pdfCluster package. (I discuss it here.) $\endgroup$ – gung Nov 28 '15 at 4:12
  • $\begingroup$ HDBSCAN* uses a similar approach. $\endgroup$ – Anony-Mousse Nov 28 '15 at 13:04
3
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ I suppose "problem" in your last paragraph would be seen positively as an asset. K-means, however, is based implicitly on euclidean distance only. $\endgroup$ – ttnphns Nov 27 '15 at 14:02
  • $\begingroup$ Many possible choices can be a problem as well as an asset, indeed :) Thanks for the comment on k-means, I'll improve that paragraph. $\endgroup$ – Jacek Podlewski Nov 27 '15 at 14:10
  • $\begingroup$ @ttnphns Actually, " $k$-means " can be used with any Bregman divergences jmlr.org/papers/volume6/banerjee05b/banerjee05b.pdf ; I mean this is the case when considering that $k$-means is what results when considering the limiting case of Gaussian mixture models (from soft to hard), then by replacing Gaussian by another member of the exponential family, you replace the Euclidean distance by another Bregman divergence associated with the member of the family you picked. You end up with a similar algorithm scheme that aims to find a maximum likelihood with an expectation-maximization. $\endgroup$ – mic Nov 27 '15 at 14:21
  • $\begingroup$ I believe the original question was made with regard to "classical' K-means and not a slightest intention to delve into Bregman divergences. Nice remark though, I'll check out this paper more thoroughly for sure. $\endgroup$ – Jacek Podlewski Nov 27 '15 at 14:37
  • $\begingroup$ @mic nobody uses Bregman divergences beyond variations of Euclidean distance... it is a tiny tiny class only. But people would like to use e.g. Manhattan distance, Gower etc. which are not Bregman divergences for all I know. $\endgroup$ – Anony-Mousse Nov 28 '15 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.