In [1]:
%load_ext watermark
In [2]:
%watermark -a "Sebastian Raschka" -d -v
This is a more technical-oriented tutorial that was born out of necessity to plot a heatmap including the dendrograms from a complete linkage clustering. Since I couldn't find any good resource online, I thought that it might be worthwhile sharing it.
Therefore, the theoretical aspects are a little bit brief, but nonetheless, here is a short introduction of what it is all about.
Complete linkage is one implementation of hierarchical agglomerative clustering. The principle of hierarchical agglomerative clustering is to start with a singleton cluster, and clusters are iteratively merged until one single cluster remains. This results in a "cluster tree," which is also called dendrogram. The opposite approach -- starting with one cluster and divide into clusters until only singleton clusters remain -- is called divisive hierarchical clustering.
The algorithm can be summarized via the following pseudocode
1: Compute a distance or similarity matrix.
2: Each data point is represented as a singleton cluster.
3: Repeat
4: Merge two closest clusters (e.g., based on distance between most similar or dissimilar members).
5: Update the distance (or similarity) matrix.
6: Until one single cluster remains.
Complete linkage compares the most dissimilar members between clusters in each iteration. The two clusters which have the most similar dissimilar members are merged into a new cluster.
\begin{equation}
d(C,D) = \max[dist(C_i, D_j)]
\end{equation}
for all $i$ points in cluster $C$ and $j$ points in cluster $D$.
In contrast, the single linkage algorithm compares the two most similar members instead of the most dissimilar ones. \begin{equation} d(C,D) = \min[dist(C_i, D_j)] \end{equation} for all $i$ points in cluster $C$ and $j$ points in cluster $D$.
For more implementations, e.g., centroid, average etc., please see the scipy.cluster.hierarchy.linkage documentation.
(A more detailed article about prototype-based, hierarchical, and density-based clustering is in the planning stage)
First, we generate some random sample data to work with. Like in a typical application, the rows represent different observations (Samples 1-5), and the columns are the different features (X, Y, Z).
In [4]:
import pandas as pd
import numpy as np
import matplotlib.ticker as ticker
np.random.seed(123)
variables = ['A','B','C','X','Y','Z']
labels = ['ID_0','ID_1','ID_2','ID_3','ID_4','ID_5','ID_6',
'ID_7','ID_8','ID_9','ID_10']
X = np.random.random_sample([len(labels),len(variables)])*10
df = pd.DataFrame(X, columns=variables, index=labels)
df
Out[4]:
First, we calculate the pair-wise distances for every row (i.e, between every sample across the different variables). We will use the default euclidean distance measure. The other available distance measures are listed in the scipy.spatial.distance.pdist documentation with a nice and short explanatory paragraph. In addition, we use the squareform function to return a symmetrical matrix of the pair-wise distances.
In [5]:
from scipy.spatial.distance import pdist,squareform
row_dist = pd.DataFrame(squareform(pdist(df, metric='euclidean')), columns=labels, index=labels)
row_dist
Out[5]:
When we apply the complete linkage agglomeration to our clusters, the linkage function returns a so-called linkage matrix.
This linkage matrix consists of several rows where each row consists of 1 merge. The first and second column denote the most dissimilar members in each cluster, and the third row reports the distance between those members. The last column returns the count of members in the clusters.
However, before we call the linkage function, let us take a careful look at its documentation.
Parameters:
y : ndarray
A condensed or redundant distance matrix. A condensed distance matrix is a flat array containing the upper triangular of the distance matrix. This is the form that pdist returns. Alternatively, a collection of m observation vectors in n dimensions may be passed as an m by n array.method : str, optional
The linkage algorithm to use. See the Linkage Methods section below for full descriptions.metric : str, optional
The distance metric to use. See the distance.pdist function for a list of valid distance metrics.Returns:
Z : ndarray
The hierarchical clustering encoded as a linkage matrix.
Thus, we can either pass a condensed distance matrix (upper triangular) from the pdist function, or we can pass the "original" data array and define the 'euclidean' metric as function argument in linkage. However, we shouldn't pass the squareform distance metrics, which would yield incorrect distance values although the overall clustering could be the same.
In [6]:
from scipy.cluster.hierarchy import linkage
row_clusters = linkage(row_dist, method='complete', metric='euclidean')
pd.DataFrame(row_clusters,
columns=['row label 1', 'row label 2', 'distance', 'no. of items in clust.'],
index=['cluster %d' %(i+1) for i in range(row_clusters.shape[0])])
Out[6]:
In [7]:
row_clusters = linkage(pdist(df, metric='euclidean'), method='complete')
pd.DataFrame(row_clusters,
columns=['row label 1', 'row label 2', 'distance', 'no. of items in clust.'],
index=['cluster %d' %(i+1) for i in range(row_clusters.shape[0])])
Out[7]:
In [8]:
row_clusters = linkage(df.values, method='complete', metric='euclidean')
pd.DataFrame(row_clusters,
columns=['row label 1', 'row label 2', 'distance', 'no. of items in clust.'],
index=['cluster %d' %(i+1) for i in range(row_clusters.shape[0])])
Out[8]:
In [9]:
import matplotlib.pyplot as plt
%matplotlib inline
from scipy.cluster.hierarchy import dendrogram
row_dendr = dendrogram(row_clusters, labels=labels)
This section is about the visualization of our hierarchical clustering. Here, we will plot simple heatmaps for each scenario: The original data, the data after row clustering, and eventually the data after we applied row and column clustering.
In [10]:
fig = plt.figure()
ax = fig.add_subplot(111)
cax = ax.matshow(df, interpolation='nearest', cmap='hot_r')
fig.colorbar(cax)
tick_spacing = 1
ax.xaxis.set_major_locator(ticker.MultipleLocator(tick_spacing))
ax.yaxis.set_major_locator(ticker.MultipleLocator(tick_spacing))
ax.set_xticklabels([''] + list(df.columns))
ax.set_yticklabels([''] + list(df.index))
plt.show()
The dendrogram function returns a dictionary with various items which are explained in detail in the scipy documenation here. The dendrogram leave order can then be accessed via the 'leaves' key, e.g.,
In [11]:
row_dendr['leaves']
Out[11]:
Thus, in order to sort the DataFrame according to the clustering, we can simply use the 'leaves' as indices like so:
df.ix[row_dendr['leaves']]
In [13]:
# reorder rows with respect to the clustering
row_dendr = dendrogram(row_clusters, labels=labels, no_plot=True)
df_rowclust = df.ix[row_dendr['leaves']]
# plot
fig = plt.figure()
ax = fig.add_subplot(111)
cax = ax.matshow(df_rowclust,
interpolation='nearest',
cmap='hot_r')
fig.colorbar(cax)
tick_spacing = 1
ax.xaxis.set_major_locator(ticker.MultipleLocator(tick_spacing))
ax.yaxis.set_major_locator(ticker.MultipleLocator(tick_spacing))
ax.set_xticklabels([''] + list(df_rowclust.columns))
ax.set_yticklabels([''] + list(df_rowclust.index))
plt.show()
Now, we can rotate the dendrogram via the by setting the orientation parameter to 'right', but note that
we now have to sort the clustered data in reverse order to match the row labels in the heatmap via
df.ix[row_dendr['leaves'][::-1]]
In [19]:
from scipy.cluster import hierarchy
# makes dendrogram black (1)
hierarchy.set_link_color_palette(['black'])
# plot row dendrogram
fig = plt.figure(figsize=(8,8))
axd = fig.add_axes([0.09,0.1,0.2,0.6])
row_dendr = dendrogram(row_clusters, orientation='left',
color_threshold=np.inf, ) # makes dendrogram black (2))
# reorder data with respect to clustering
df_rowclust = df.ix[row_dendr['leaves'][::-1]]
axd.set_xticks([])
axd.set_yticks([])
# remove axes spines from dendrogram
for i in axd.spines.values():
i.set_visible(False)
# reorder rows with respect to the clustering
df_rowclust = df.ix[row_dendr['leaves'][::-1]]
# plot heatmap
axm = fig.add_axes([0.20, 0.1, 0.6, 0.6]) # x-pos, y-pos, width, height
cax = axm.matshow(df_rowclust, interpolation='nearest', cmap='hot_r')
fig.colorbar(cax)
axm.set_xticklabels([''] + list(df_rowclust.columns))
axm.set_yticklabels([''] + list(df_rowclust.index))
tick_spacing = 1
axm.xaxis.set_major_locator(ticker.MultipleLocator(tick_spacing))
axm.yaxis.set_major_locator(ticker.MultipleLocator(tick_spacing))
plt.show()
Also, we can add a an additional dendrogram for the column clustering at the top. Here, we first sort the indexes after clustering the rows
df_rowclust = df.ix[row_dendr['leaves'][::-1]]
And then we can use the indices from the column clustering to reorder the columns:
df_rowclust.columns = [df_rowclust.columns[col_dendr['leaves']]]
In [21]:
# Compute pairwise distances for columns
col_dists = pdist(df.T, metric='euclidean')
col_clusters = linkage(col_dists, method='complete')
# plot column dendrogram
fig = plt.figure(figsize=(8,8))
axd2 = fig.add_axes([0.38,0.74,0.36,0.10])
col_dendr = dendrogram(col_clusters, orientation='top',
color_threshold=np.inf) # makes dendrogram black)
axd2.set_xticks([])
axd2.set_yticks([])
# plot row dendrogram
axd1 = fig.add_axes([0.09,0.1,0.2,0.6])
row_dendr = dendrogram(row_clusters, orientation='left',
count_sort='ascending',
color_threshold=np.inf) # makes dendrogram black
axd1.set_xticks([])
axd1.set_yticks([])
# remove axes spines from dendrogram
for i,j in zip(axd1.spines.values(), axd2.spines.values()):
i.set_visible(False)
j.set_visible(False)
# reorder columns and rows with respect to the clustering
df_rowclust = df.ix[row_dendr['leaves'][::-1]]
df_rowclust.columns = [df_rowclust.columns[col_dendr['leaves']]]
# plot heatmap
axm = fig.add_axes([0.20,0.1,0.6,0.6])
cax = axm.matshow(df_rowclust, interpolation='nearest', cmap='hot_r')
fig.colorbar(cax)
axm.set_xticklabels([''] + list(df_rowclust.columns))
axm.set_yticklabels([''] + list(df_rowclust.index))
tick_spacing = 1
axm.xaxis.set_major_locator(ticker.MultipleLocator(tick_spacing))
axm.yaxis.set_major_locator(ticker.MultipleLocator(tick_spacing))
plt.show()
It is very important that you always check that the labels on the heatmap and the dendrogram match when you create the first plot! For example, we can provide the labels to the labels parameter of the dendrogram and DON'T set axd.set_yticks([]) to show the labels on the dendrogram to compare them to the heatmap labels.
In [23]:
from scipy.cluster import hierarchy
# makes dendrogram black (1)
hierarchy.set_link_color_palette(['black'])
# plot row dendrogram
fig = plt.figure(figsize=(8,8))
axd = fig.add_axes([0.09,0.1,0.2,0.6])
row_dendr = dendrogram(row_clusters, orientation='left',
labels=labels,
color_threshold=np.inf, ) # makes dendrogram black (2))
axd.set_xticks([])
# uncomment to hide dendrogram labels
#axd.set_yticks([])
# remove axes spines from dendrogram
for i in axd.spines.values():
i.set_visible(False)
# reorder columns and rows with respect to the clustering
df_rowclust = df.ix[row_dendr['leaves'][::-1]]
# plot heatmap
axm = fig.add_axes([0.20,0.1,0.6,0.6]) # x-pos, y-pos, width, height
cax = axm.matshow(df_rowclust, interpolation='nearest', cmap='hot_r')
fig.colorbar(cax)
axm.set_xticklabels([''] + list(df_rowclust.columns))
axm.set_yticklabels([])
tick_spacing = 1
axm.xaxis.set_major_locator(ticker.MultipleLocator(tick_spacing))
axm.yaxis.set_major_locator(ticker.MultipleLocator(tick_spacing))
plt.show()