Introduction to Hierarchical Clustering
Hierarchical clustering groups data over a variety of scales
by creating a cluster tree or dendrogram. The
tree is not a single set of clusters, but rather a multilevel hierarchy,
where clusters at one level are joined as clusters at the next level.
This allows you to decide the level or scale of clustering that is
most appropriate for your application. The function
clusterdata supports agglomerative clustering
and performs all of the necessary steps for you. It incorporates the
cluster functions, which
you can use separately for more detailed analysis. The
dendrogram function plots the cluster tree.
To perform agglomerative hierarchical cluster analysis on a data set using Statistics and Machine Learning Toolbox™ functions, follow this procedure:
Find the similarity or dissimilarity between every pair of objects in the data set. In this step, you calculate the distance between objects using the
pdistfunction supports many different ways to compute this measurement. See Similarity Measures for more information.
Group the objects into a binary, hierarchical cluster tree. In this step, you link pairs of objects that are in close proximity using the
linkagefunction uses the distance information generated in step 1 to determine the proximity of objects to each other. As objects are paired into binary clusters, the newly formed clusters are grouped into larger clusters until a hierarchical tree is formed. See Linkages for more information.
Determine where to cut the hierarchical tree into clusters. In this step, you use the
clusterfunction to prune branches off the bottom of the hierarchical tree, and assign all the objects below each cut to a single cluster. This creates a partition of the data. The
clusterfunction can create these clusters by detecting natural groupings in the hierarchical tree or by cutting off the hierarchical tree at an arbitrary point.
The following sections provide more information about each of these steps.
all of the necessary steps for you. You do not need to execute the
cluster functions separately.
You use the
to calculate the distance between every pair of objects in a data
set. For a data set made up of m objects, there
are m*(m –
1)/2 pairs in the data set. The result of this
computation is commonly known as a distance or dissimilarity matrix.
There are many ways to calculate this distance information.
By default, the
pdist function calculates the Euclidean
distance between objects; however, you can specify one of several
other options. See
You can optionally normalize the values in the data set before
calculating the distance information. In a real world data set, variables
can be measured against different scales. For example, one variable
can measure Intelligence Quotient (IQ) test scores and another variable
can measure head circumference. These discrepancies can distort the
proximity calculations. Using the
you can convert all the values in the data set to use the same proportional
zscore for more information.
For example, consider a data set,
up of five objects where each object is a set of x,y coordinates.
Object 1: 1, 2
Object 2: 2.5, 4.5
Object 3: 2, 2
Object 4: 4, 1.5
Object 5: 4, 2.5
You can define this data set as a matrix
rng("default") % For reproducibility X = [1 2; 2.5 4.5; 2 2; 4 1.5; ... 4 2.5];
and pass it to
calculates the distance between object 1 and object 2, object 1 and object 3,
and so on until the distances between all the pairs have been calculated.
The following figure plots these objects in a graph. The Euclidean
distance between object 2 and object 3 is shown to illustrate one
interpretation of distance.
pdist function returns
this distance information in a vector,
where each element contains the distance between a pair of objects.
Y = pdist(X)
Y = Columns 1 through 6 2.9155 1.0000 3.0414 3.0414 2.5495 3.3541 Columns 7 through 10 2.5000 2.0616 2.0616 1.0000
To make it easier to see the relationship between the distance
information generated by
pdist and the objects
in the original data set, you can reformat the distance vector into
a matrix using the
In this matrix, element i,j corresponds to the
distance between object i and
object j in the original data
set. In the following example, element 1,1 represents the distance
between object 1 and itself (which is zero). Element
1,2 represents the distance between object 1 and
object 2, and so on.
ans = 0 2.9155 1.0000 3.0414 3.0414 2.9155 0 2.5495 3.3541 2.5000 1.0000 2.5495 0 2.0616 2.0616 3.0414 3.3541 2.0616 0 1.0000 3.0414 2.5000 2.0616 1.0000 0
Once the proximity between objects in the data set has been
computed, you can determine how objects in the data set should be
grouped into clusters, using the
linkage function takes the distance information
pdist and links
pairs of objects that are close together into binary clusters (clusters
made up of two objects). The
linkage function then
links these newly formed clusters to each other and to other objects
to create bigger clusters until all the objects in the original data
set are linked together in a hierarchical tree.
For example, given the distance vector
pdist from the sample data set of x-
and y-coordinates, the
generates a hierarchical cluster tree, returning the linkage information
in a matrix,
Z = linkage(Y)
Z = 4.0000 5.0000 1.0000 1.0000 3.0000 1.0000 6.0000 7.0000 2.0616 2.0000 8.0000 2.5000
In this output, each row identifies a link between objects or
clusters. The first two columns identify the objects that have been
linked. The third column contains the distance between these objects.
For the sample data set of x- and y-coordinates,
linkage function begins by grouping objects 4 and 5, which have the closest proximity
(distance value = 1.0000). The
continues by grouping objects 1 and 3,
which also have a distance value of 1.0000.
The third row indicates that the
grouped objects 6 and 7. If the
original sample data set contained only five objects, what are objects 6 and 7? Object 6 is
the newly formed binary cluster created by the grouping of objects 4 and 5. When the
groups two objects into a new cluster, it must assign the cluster
a unique index value, starting with the value m +
1, where m is the number of objects in the original
data set. (Values 1 through m are
already used by the original data set.) Similarly, object 7
is the cluster formed by grouping objects 1 and 3.
linkage uses distances to determine the order
in which it clusters objects. The distance vector
the distances between the original objects 1 through 5. But linkage
must also be able to determine distances involving clusters that it
creates, such as objects 6 and 7. By default,
a method known as single linkage. However, there are a number of different
methods available. See the
page for more information.
As the final cluster, the
grouped object 8, the newly formed cluster made up
of objects 6 and 7, with object 2 from the original data set. The following figure graphically
illustrates the way
linkage groups the objects
into a hierarchy of clusters.
The hierarchical, binary cluster tree created by the
is most easily understood when viewed graphically. The function
dendrogram plots the tree as follows.
In the figure, the numbers along the horizontal axis represent
the indices of the objects in the original data set. The links between
objects are represented as upside-down U-shaped lines. The height
of the U indicates the distance between the objects. For example,
the link representing the cluster containing objects 1 and 3 has a
height of 1. The link representing the cluster that groups object
2 together with objects 1, 3, 4, and 5, (which are already clustered
as object 8) has a height of 2.5. The height represents the distance
between objects 2 and 8. For more information about creating a dendrogram
diagram, see the
Verify the Cluster Tree
After linking the objects in a data set into a hierarchical cluster tree, you might want to verify that the distances (that is, heights) in the tree reflect the original distances accurately. In addition, you might want to investigate natural divisions that exist among links between objects. Statistics and Machine Learning Toolbox functions are available for both of these tasks, as described in the following sections.
In a hierarchical cluster tree, any two objects in the original
data set are eventually linked together at some level. The height
of the link represents the distance between the two clusters that
contain those two objects. This height is known as the cophenetic
distance between the two objects. One way to measure how
well the cluster tree generated by the
reflects your data is to compare the cophenetic distances with the
original distance data generated by the
If the clustering is valid, the linking of objects in the cluster
tree should have a strong correlation with the distances between objects
in the distance vector. The
compares these two sets of values and computes their correlation,
returning a value called the cophenetic correlation coefficient.
The closer the value of the cophenetic correlation coefficient is
to 1, the more accurately the clustering solution reflects your data.
You can use the cophenetic correlation coefficient to compare
the results of clustering the same data set using different distance
calculation methods or clustering algorithms. For example, you can
cophenet function to evaluate the clusters
created for the sample data set.
c = cophenet(Z,Y)
c = 0.8615
Z is the matrix output by the
Y is the distance vector output
pdist again on the same data set,
this time specifying the city block metric. After running the
on this new
pdist output using the average linkage
cophenet to evaluate the clustering
Y = pdist(X,"cityblock"); Z = linkage(Y,"average"); c = cophenet(Z,Y)
c = 0.9047
The cophenetic correlation coefficient shows that using a different distance and linkage method creates a tree that represents the original distances slightly better.
One way to determine the natural cluster divisions in a data set is to compare the height of each link in a cluster tree with the heights of neighboring links below it in the tree.
A link that is approximately the same height as the links below it indicates that there are no distinct divisions between the objects joined at this level of the hierarchy. These links are said to exhibit a high level of consistency, because the distance between the objects being joined is approximately the same as the distances between the objects they contain.
On the other hand, a link whose height differs noticeably from the height of the links below it indicates that the objects joined at this level in the cluster tree are much farther apart from each other than their components were when they were joined. This link is said to be inconsistent with the links below it.
In cluster analysis, inconsistent links can indicate the border
of a natural division in a data set. The
uses a quantitative measure of inconsistency to determine where to
partition your data set into clusters.
The following dendrogram illustrates inconsistent links. Note how the objects in the dendrogram fall into two groups that are connected by links at a much higher level in the tree. These links are inconsistent when compared with the links below them in the hierarchy.
The relative consistency of each link in a hierarchical cluster tree can be quantified and expressed as the inconsistency coefficient. This value compares the height of a link in a cluster hierarchy with the average height of links below it. Links that join distinct clusters have a high inconsistency coefficient; links that join indistinct clusters have a low inconsistency coefficient.
To generate a listing of the inconsistency coefficient for each
link in the cluster tree, use the
By default, the
inconsistent function compares
each link in the cluster hierarchy with adjacent links that are less
than two levels below it in the cluster hierarchy. This is called
the depth of the comparison. You can also specify
other depths. The objects at the bottom of the cluster tree, called
leaf nodes, that have no further objects below them, have an inconsistency
coefficient of zero. Clusters that join two leaves also have a zero
For example, you can use the
to calculate the inconsistency values for the links created by the
linkage function in Linkages.
First, recompute the distance and linkage values using the default settings.
Y = pdist(X); Z = linkage(Y);
inconsistent to calculate the inconsistency
I = inconsistent(Z)
I = 1.0000 0 1.0000 0 1.0000 0 1.0000 0 1.3539 0.6129 3.0000 1.1547 2.2808 0.3100 2.0000 0.7071
inconsistent function returns data about
the links in an (m-1)-by-4 matrix, whose columns
are described in the following table.
Mean of the heights of all the links included in the calculation
Standard deviation of all the links included in the calculation
Number of links included in the calculation
In the sample output, the first row represents the link between
objects 4 and 5. This cluster is
assigned the index 6 by the
Because both 4 and 5 are leaf nodes,
the inconsistency coefficient for the cluster is zero. The second
row represents the link between objects 1 and 3, both of which are also leaf nodes. This cluster is
assigned the index 7 by the linkage function.
The third row evaluates the link that connects these two clusters,
objects 6 and 7. (This new cluster
is assigned index 8 in the
Column 3 indicates that three links are considered in the calculation:
the link itself and the two links directly below it in the hierarchy.
Column 1 represents the mean of the heights of these links. The
uses the height information output by the
to calculate the mean. Column 2 represents the standard deviation
between the links. The last column contains the inconsistency value
for these links, 1.1547. It is the difference between the current
link height and the mean, normalized by the standard deviation.
(2.0616 - 1.3539) / 0.6129
ans = 1.1547
The following figure illustrates the links and heights included in this calculation.
In the preceding figure, the lower limit on the y-axis
is set to
0 to show the heights of the links. To
set the lower limit to
Properties from the Edit menu,
click the Y Axis tab, and enter
the field immediately to the right of Y Limits.
Row 4 in the output matrix describes the link between object 8 and object 2. Column 3 indicates that two links are included in this calculation: the link itself and the link directly below it in the hierarchy. The inconsistency coefficient for this link is 0.7071.
The following figure illustrates the links and heights included in this calculation.
After you create the hierarchical tree of binary clusters, you
can prune the tree to partition your data into clusters using the
cluster function. The
lets you create clusters in two ways, as discussed in the following
Find Natural Divisions in Data
The hierarchical cluster tree may naturally divide the data
into distinct, well-separated clusters. This can be particularly evident
in a dendrogram diagram created from data where groups of objects
are densely packed in certain areas and not in others. The inconsistency
coefficient of the links in the cluster tree can identify these divisions
where the similarities between objects change abruptly. (See Verify the Cluster Tree for more
information about the inconsistency coefficient.) You can use this
value to determine where the
creates cluster boundaries.
For example, if you use the
to group the sample data set into clusters, specifying an inconsistency
coefficient threshold of
1.2 as the value of the
cluster function groups all the objects in
the sample data set into one cluster. In this case, none of the links
in the cluster hierarchy had an inconsistency coefficient greater
T = cluster(Z,"cutoff",1.2)
T = 1 1 1 1 1
cluster function outputs a vector,
T, that is the same size as the original
data set. Each element in this vector contains the number of the cluster
into which the corresponding object from the original data set was
If you lower the inconsistency coefficient threshold to
cluster function divides the sample data set
into three separate clusters.
T = cluster(Z,"cutoff",0.8)
T = 1 2 1 3 3
This output indicates that objects 1 and 3 are in one cluster, objects 4 and 5 are in another cluster, and object 2 is in its own cluster.
When clusters are formed in this way, the cutoff value is applied
to the inconsistency coefficient. These clusters may, but do not necessarily,
correspond to a horizontal slice across the dendrogram at a certain
height. If you want clusters corresponding to a horizontal slice of
the dendrogram, you can either use the
to specify that the cutoff should be based on distance rather than
inconsistency, or you can specify the number of clusters directly
as described in the following section.
Specify Arbitrary Clusters
Instead of letting the
create clusters determined by the natural divisions in the data set,
you can specify the number of clusters you want created.
For example, you can specify that you want the
to partition the sample data set into two clusters. In this case,
cluster function creates one cluster containing
objects 1, 3, 4, and 5 and another
cluster containing object 2.
T = cluster(Z,"maxclust",2)
T = 2 1 2 2 2
To help you visualize how the
cluster function determines these clusters,
the following figure shows the dendrogram of the hierarchical cluster tree. The
horizontal dashed line intersects two lines of the dendrogram, corresponding to
2. These two lines
partition the objects into two clusters: the objects below the left-hand line,
namely 1, 3, 4, and 5, belong to one cluster, while the object below the
right-hand line, namely 2, belongs to the other cluster.
On the other hand, if you set
cluster function groups objects 4 and 5 in one cluster, objects 1
and 3 in a second cluster, and object 2 in a third cluster. The
following command illustrates this.
T = cluster(Z,"maxclust",3)
T = 1 3 1 2 2
This time, the
cluster function cuts off
the hierarchy at a lower point, corresponding to the horizontal line
that intersects three lines of the dendrogram in the following figure.