# The number of clusters in Hierarchical Clustering

January 22, 2014
By

(This article was first published on Chen-ang Statistics » R, and kindly contributed to R-bloggers)

Cluster analysis is widely applied in data analysis. Obviously hierarchical clustering is the simple and important method to do clustering. In brief, hierarchical clustering methods use the elements of a proximity matrix to generate a tree diagram or dendogram. From the tree diagram, we can draw our own conclusions about the results of clustering. However, when the cluster analysis solution is given,  the question is how to determine the number of clusters k. For some value of k, we want to determine whether the clusters are sufficiently separated so as to illustrate minimal overlap. There is no doubt that we can choose an appropriate threshold value or use scatter diagram to determine that. Furthermore, statistic value is also very useful to determine the value of k. There are some valuable test statistics or pseudo test statistics as follow. In addition, I also provide a corresponding R function to implement.

$R_k^2$ statistic

The $R_k^2$   for k clusters is defined as

$R_k^2=\frac{B_k}{T}=1-\frac{P_k}{T}$

T, P_k means total sum of squares, within cluster sum of squares, respectively. For n clusters, obviously each $P_k=0$  so that  $R^2=1$  . As the number of clusters decreases from n to 1 they should become more widely separated. A large decrease in  $R_k^2$  would represent a distinct join. Actually, we also can use semipartial R^2 statistic to reach our goal.

2 semipartial  $R_k^2$  statistic

The semipartial  $R_k^2$   for k clusters is defined as

$SR_k^2=\frac{B_{KL}^2}{T}=R_{k+1}^2-R_k^2$

$B_{KL}^2$ is equal to $W_M-(W_K+W_L)$ and $W_t$ means the sum of squares in cluster $G_t$ .

3 pseudo  $F_k$ statistic

The pseudo  $F_k$  statistic for k clusters is defined as

pseudo  $F_k=\frac{(T-P_k)/(k-1)}{(P_k)/(n-k)}=1-\frac{B_k(n-k)}{P_k(k-1)}$

If pseudo  $F_k$   decreases with k and reaches a maximum value, the value of k at the maximum or immediately prior to the point may be a candidate for the value of k.

4 pseudo  $t^2$ statistic

The pseudo  $t^2$  is defined as

pseudo  $t^2=\frac{B_{KL}^2}{(W_L+W_K)/(n_K+n_L-2)}$

for joining cluster $G_L$ with $G_K$  each having $n_L$  and $n_K$  elements.

Implementation

As a matter of fact, SAS enables us to get the value of  these statistics easily through the PROC CLUSTER and PROC TREE. However,  it is not convenient to calculate them in R. Last semester, as a teaching assistant of the course of multivariate statistical analysis, the professor gave these assignments(writing R funtions to calculate one of these test statistics) to the students. In order to correct their codes, I also write a R function which can calculate all of these test statistics at the same time. The output of this function is similar with the SAS output. If your want to  view the source code, please click this link.

Further discussion

Besides writing function, a package called NbClust offers a simper and better way to determine the number of clusters. It provides 30 popular indices and also proposes to user a recommended number of clusters. More details could be found from the reference manual of this package.

library(NbClust);
data(USArrests);
NbClust(USArrests,diss="NULL",distance="euclidean",
min.nc=2,max.nc=8,method="ward",index="pseudot2",
alphaBeale=0.1);

Please note that the output is a little different from the SAS output.

Reference

Timm, Neil H. Applied multivariate analysis. Springer, 2002.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...