# Situation that not well represented by hierarchical clustering

The below text is from statistical learning page 394. I highlighted where i stuck. Please help me to understand this.

The term hierarchical refers to the fact that clusters obtained by cutting the dendrogram at a given height are necessarily nested within the clusters obtained by cutting the dendrogram at any greater height. However, on an arbitrary data set, this assumption of hierarchical structure might be unrealistic.

For instance, suppose that our observations correspond to a group of people with a 50–50 split of males and females, evenly split among Americans, Japanese, and French. We can imagine a scenario in which the best division into two groups might split these people by gender, and the best division into three groups might split them by nationality.(can someone explain it with a dendogram?)

In this case, the true clusters are not nested, in the sense that the best division into three groups does not result from taking the best division into two groups and splitting up one of those groups.(Incomprehensible.Please clarify)

Consequently, this situation could not be well-represented by hierarchical clustering. Due to situations such as this one, hierarchical clustering can sometimes yield worse (i.e. less accurate) results than K-means clustering for a given number of clusters

For instance, suppose that our observations correspond to a group of people with a 50–50 split of males and females, evenly split among Americans, Japanese, and French. We can imagine a scenario in which the best division into two groups might split these people by gender, and the best division into three groups might split them by nationality.(can someone explain it with a dendogram?)

I think that at this point of the text he is not talking about hierarchical clustering so dendrogram would not necessarily makes sense. He talks while being in a broader clustering problem.

In general clustering task, you want to break your sample down into $k$ sub-samples (you may or may not have a prior on $k$) so that it is 'the best' possible clustering results. There are various ways to decide wether or not a cluster is well-defined. The most simple one is to consider that splitting a sample in two is justified if the two resulting clusters are well-enough separated and compact enough, which you can translate as great inter-cluster distance and low intra-cluster distance.

In that situtation, he talks about a case where your population is defined by many variables, two of which are nationality and gender. He then hypothesizes that clustering leading to 2 clusters may be best based on gender and clustering into 3 groups may be best when using nationality. Basically he is just saying that the best way to easily break down your sample in $k$ sub-samples is to use a factor of $k$ levels. Which makes sense as by definition clustering is trying to find such a factor.

In this case, the true clusters are not nested, in the sense that the best division into three groups does not result from taking the best division into two groups and splitting up one of those groups.(Incomprehensible.Please clarify)

Clusters are nested when you can further break down a cluster (end up with a dendrogram). For example, if you have four clusters and then manage to break down one of those clusters into two, you would end up with 5 clusters, two of which are nested in a 6th one (union). Here he says that if you separate your previous sample of people by gender, you would get two clusters. If you now want 3 clusters the best move is to cluster on nationality but doing that you would not take one of your gender cluster and break it down further, you would just use you nationality factor as it is.

In that case, your sample is not structured in a way that allows for nested clusters to be performed efficiently (if you just have those two variables). Meaning, you could break down one of your gender-cluster into two new clusters but that would lead to a worse clustering result than when using nationality.

• if you have four clusters and then manage to break down one of those clusters into two, you would end up with 5 clusters, two of which are nested in a 6th one (union).? Where the 6th one come from . The number of cluster becomes 5 right ? – user110244 Apr 21 '16 at 10:06
• Bad wording on my part. Let's say you have clusters $C_i, i \in [1, 4]$ and you split cluster $C_1$ into $C_{1.1}$ and $C_{1.2}$ you would have 5 clusters $C_{1.1}, C_{1.2}, C_2, C_3, C_4$, two of which, $C_{1.1}$ and $C_{1.2}$, are nested in $C_1$ which is a cluster on its own so a 6th cluster. – Riff Apr 21 '16 at 11:07

The message is that there may be no dendrogram with this properties.

For splitting into two optimal clusters, it needs to look like this:

   +-----+
|     |    Optimum split for 2
+-+-+ +-+-+
| | | | | |
m m m f f f   Gender
a c j a c j   Nationality


In order to be able to do the optimal 3-cluster split, the dendrogram would need to look like this:

  +---+---+
|   |   |    Optimum split for 3
+-+ +-+ +-+
| | | | | |
m f m f m f  Gender
a a c c j j  Nationality


It is not possible for a dendrogram to have both structures at the same time. It can only either contain the optimal 2 cluster split, or the optimal three cluster solution.