Show Sidebar Hide Sidebar

Agglomerative clustering with and without structure in Scikit-learn

This example shows the effect of imposing a connectivity graph to capture local structure in the data. The graph is simply the graph of 20 nearest neighbors.

Two consequences of imposing a connectivity can be seen. First clustering with a connectivity matrix is much faster.

Second, when using a connectivity matrix, average and complete linkage are unstable and tend to create a few clusters that grow very quickly. Indeed, average and complete linkage fight this percolation behavior by considering all the distances between two clusters when merging them. The connectivity graph breaks this mechanism. This effect is more pronounced for very sparse graphs (try decreasing the number of neighbors in kneighbors_graph) and with complete linkage. In particular, having a very small number of neighbors in the graph, imposes a geometry that is close to that of single linkage, which is well known to have this percolation instability.

New to Plotly?

Plotly's Python library is free and open source! Get started by downloading the client and reading the primer.
You can set up Plotly to work in online or offline mode, or in jupyter notebooks.
We also have a quick-reference cheatsheet (new!) to help you get started!

Version

In [1]:
import sklearn
sklearn.__version__
Out[1]:
'0.18'

Imports

This tutorial imports AgglomerativeClustering and kneighbors_graph.

In [2]:
import plotly.plotly as py
import plotly.graph_objs as go
from plotly import tools

import time
import matplotlib.pyplot as plt
import numpy as np

from sklearn.cluster import AgglomerativeClustering
from sklearn.neighbors import kneighbors_graph

Calculations

Generate sample data

In [3]:
n_samples = 1500
np.random.seed(0)
t = 1.5 * np.pi * (1 + 3 * np.random.rand(1, n_samples))
x = t * np.cos(t)
y = t * np.sin(t)


X = np.concatenate((x, y))
X += .7 * np.random.randn(2, n_samples)
X = X.T

Plot Results

Create a graph capturing local connectivity. Larger number of neighbors will give more homogeneous clusters to the cost of computation time. A very large number of neighbors gives more evenly distributed cluster sizes, but may not impose the local manifold structure of the data.

In [4]:
knn_graph = kneighbors_graph(X, 30, include_self=False)
In [5]:
fig = tools.make_subplots(rows=4, cols=3,
                          print_grid=False,
                          subplot_titles=('linkage=Average(time=0.22s)',
                                          
                                          'n_cluster=30, connectivity=False<br>'+
                                          'linkage=Complete(time=0.06s)',
                                          
                                          'linkage=Ward(time=0.07s)',
                                          
                                          'linkage=Average(time=0.22s)',
                                          
                                          'n_cluster=3, connectivity=False<br>'+
                                          'linkage=Complete(time=0.06s)',
                                          
                                          'linkage=Ward(time=0.07s)',
                                          
                                          'linkage=Average(time=0.22s)',
                                          
                                          'n_cluster=30, connectivity=True<br>'+
                                          'linkage=Complete(time=0.06s)',
                                          
                                          'linkage=Ward(time=0.07s)',
                                          
                                          'linkage=Average(time=0.22s)',
                                          
                                          'n_cluster=3, connectivity=True<br>'+
                                          'linkage=Complete(time=0.06s)',
                                          
                                          'linkage=Ward(time=0.07s)'))

def matplotlib_to_plotly(cmap, pl_entries):
    h = 1.0/(pl_entries-1)
    pl_colorscale = []
    
    for k in range(pl_entries):
        C = map(np.uint8, np.array(cmap(k*h)[:3])*255)
        pl_colorscale.append([k*h, 'rgb'+str((C[0], C[1], C[2]))])
        
    return pl_colorscale
In [6]:
l = 0
row = 1
colors = matplotlib_to_plotly(plt.cm.spectral, 13)

for connectivity in (None, knn_graph):
    for n_clusters in (30, 3):
        for index, linkage in enumerate(('average', 'complete', 'ward')):
            
            model = AgglomerativeClustering(linkage=linkage,
                                            connectivity=connectivity,
                                            n_clusters=n_clusters)
            
            t0 = time.time()
            model.fit(X)
            elapsed_time = time.time() - t0
            
            trace = go.Scattergl(x=X[:, 0], y=X[:, 1],
                               mode='markers', 
                               showlegend=False,
                               marker=dict(color=X[:, 1],
                                           colorscale=colors,
                                           line=dict(color='black', width=1)
                                    ))
            fig.append_trace(trace, row, index+1)
            l=l+1
        row = row+1
        
fig['layout'].update(height=1000,)

for i in map(str,range(1,13)):
    y = 'yaxis'+i
    x = 'xaxis'+i
    fig['layout'][y].update(showticklabels=False, ticks='',
                            showgrid=False, zeroline=False)
    fig['layout'][x].update(showticklabels=False, ticks='',
                           showgrid=False, zeroline=False)
py.iplot(fig)
Out[6]:

License

Authors:

       Gael Varoquaux, 
       Nelle Varoquaux

License:

       BSD 3 clause
Still need help?
Contact Us

For guaranteed 24 hour response turnarounds, upgrade to a Developer Support Plan.