%load_ext watermark

%watermark -a "Sebastian Raschka" -d -v

"""
Explanation: [<- back to pattern_classification]
End of explanation
"""


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

"""
Explanation: Hierarchical Agglomerative Clustering - Complete Linkage Clustering
- A quick Python tutorial
<br>
<br>
Sections

Generating some Sample Data
Pair-wise Distance Matrix, Rows
Apply Clustering - Complete Linkage
Heatmaps
Heatmap of the Original Data
Heatmap after Row-Clustering
Heatmap plus Row-Dendrogram
Adding a Column Dendrogram


Important Warning About Adding Dendrograms

<br>
<br>
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
<hr>

1: Compute a distance or similarity matrix.
2: Each data point is represented as a singleton cluster.
3: Repeat
4:  &nbsp;&nbsp;&nbsp;&nbsp;   Merge two closest clusters (e.g., based on distance between most similar or dissimilar members).
5:  &nbsp;&nbsp;&nbsp;&nbsp;   Update the distance (or similarity) matrix.
6: Until one single cluster remains.  
<hr>

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)
<br>
<br>
Generating some Sample Data
[back to top]
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).
End of explanation
"""


from scipy.spatial.distance import pdist,squareform

row_dist = pd.DataFrame(squareform(pdist(df, metric='euclidean')), columns=labels, index=labels)
row_dist

"""
Explanation: <br>
<br>
Pair-wise Distance Matrix, Rows
[back to top]
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.
End of explanation
"""


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])])

"""
Explanation: <br>
<br>
Apply Clustering - Complete Linkage
[back to top]
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. 
a) Squareform distance matrix (wrong)
End of explanation
"""


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])])

"""
Explanation: b) Condensed distance matrix (correct)
End of explanation
"""


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])])

import matplotlib.pyplot as plt
%matplotlib inline
from scipy.cluster.hierarchy import dendrogram

row_dendr = dendrogram(row_clusters, labels=labels)

"""
Explanation: c) Input sample matrix (correct)
End of explanation
"""


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()

"""
Explanation: <br>
<br>
Heatmaps
[back to top]
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.
<br>
<br>
Heatmap of the Original Data
[back to top]
End of explanation
"""


row_dendr['leaves']

"""
Explanation: <br>
<br>
Heatmap after Row-Clustering
[back to top]
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.,
End of explanation
"""


# 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()

"""
Explanation: 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']]
End of explanation
"""


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()

"""
Explanation: <br>
<br>
Heatmap plus Row-Dendrogram
[back to top]
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]]
End of explanation
"""


# 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()

"""
Explanation: <br>
<br>
Adding a Column Dendrogram
[back to top]
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']]]
End of explanation
"""


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()

"""
Explanation: <br>
<br>
Important Warning About Adding Dendrograms
[back to top]
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.
End of explanation
"""


