{
"cells": [
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"%matplotlib inline"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\nAgglomerative clustering with and without structure\n===================================================\n\nThis example shows the effect of imposing a connectivity graph to capture\nlocal structure in the data. The graph is simply the graph of 20 nearest\nneighbors.\n\nTwo consequences of imposing a connectivity can be seen. First clustering\nwith a connectivity matrix is much faster.\n\nSecond, when using a connectivity matrix, average and complete linkage are\nunstable and tend to create a few clusters that grow very quickly. Indeed,\naverage and complete linkage fight this percolation behavior by considering all\nthe distances between two clusters when merging them. The connectivity\ngraph breaks this mechanism. This effect is more pronounced for very\nsparse graphs (try decreasing the number of neighbors in\nkneighbors_graph) and with complete linkage. In particular, having a very\nsmall number of neighbors in the graph, imposes a geometry that is\nclose to that of single linkage, which is well known to have this\npercolation instability.\n\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"# Authors: Gael Varoquaux, Nelle Varoquaux\n# License: BSD 3 clause\n\nimport time\nimport matplotlib.pyplot as plt\nimport numpy as np\n\nfrom sklearn.cluster import AgglomerativeClustering\nfrom sklearn.neighbors import kneighbors_graph\n\n# Generate sample data\nn_samples = 1500\nnp.random.seed(0)\nt = 1.5 * np.pi * (1 + 3 * np.random.rand(1, n_samples))\nx = t * np.cos(t)\ny = t * np.sin(t)\n\n\nX = np.concatenate((x, y))\nX += .7 * np.random.randn(2, n_samples)\nX = X.T\n\n# Create a graph capturing local connectivity. Larger number of neighbors\n# will give more homogeneous clusters to the cost of computation\n# time. A very large number of neighbors gives more evenly distributed\n# cluster sizes, but may not impose the local manifold structure of\n# the data\nknn_graph = kneighbors_graph(X, 30, include_self=False)\n\nfor connectivity in (None, knn_graph):\n for n_clusters in (30, 3):\n plt.figure(figsize=(10, 4))\n for index, linkage in enumerate(('average', 'complete', 'ward')):\n plt.subplot(1, 3, index + 1)\n model = AgglomerativeClustering(linkage=linkage,\n connectivity=connectivity,\n n_clusters=n_clusters)\n t0 = time.time()\n model.fit(X)\n elapsed_time = time.time() - t0\n plt.scatter(X[:, 0], X[:, 1], c=model.labels_,\n cmap=plt.cm.nipy_spectral)\n plt.title('linkage=%s (time %.2fs)' % (linkage, elapsed_time),\n fontdict=dict(verticalalignment='top'))\n plt.axis('equal')\n plt.axis('off')\n\n plt.subplots_adjust(bottom=0, top=.89, wspace=0,\n left=0, right=1)\n plt.suptitle('n_cluster=%i, connectivity=%r' %\n (n_clusters, connectivity is not None), size=17)\n\n\nplt.show()"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.6"
}
},
"nbformat": 4,
"nbformat_minor": 0
}