{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\n# Agglomerative clustering with and without structure\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\nThere are two advantages of imposing a connectivity. First, clustering\nwith sparse connectivity matrices is faster in general.\n\nSecond, when using a connectivity matrix, single, average and complete\nlinkage are unstable and tend to create a few clusters that grow very\nquickly. Indeed, average and complete linkage fight this percolation behavior\nby considering all the distances between two clusters when merging them (\nwhile single linkage exaggerates the behaviour by considering only the\nshortest distance between clusters). The connectivity graph breaks this\nmechanism for average and complete linkage, making them resemble the more\nbrittle single linkage. This effect is more pronounced for very sparse graphs\n(try decreasing the number of neighbors in kneighbors_graph) and with\ncomplete linkage. In particular, having a very small number of neighbors in\nthe graph, imposes a geometry that is close to that of single linkage,\nwhich is well known to have this percolation instability.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "# Authors: The scikit-learn developers\n# SPDX-License-Identifier: BSD-3-Clause\n\nimport time\n\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 += 0.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\", \"single\")):\n            plt.subplot(1, 4, index + 1)\n            model = AgglomerativeClustering(\n                linkage=linkage, connectivity=connectivity, n_clusters=n_clusters\n            )\n            t0 = time.time()\n            model.fit(X)\n            elapsed_time = time.time() - t0\n            plt.scatter(X[:, 0], X[:, 1], c=model.labels_, cmap=plt.cm.nipy_spectral)\n            plt.title(\n                \"linkage=%s\\n(time %.2fs)\" % (linkage, elapsed_time),\n                fontdict=dict(verticalalignment=\"top\"),\n            )\n            plt.axis(\"equal\")\n            plt.axis(\"off\")\n\n            plt.subplots_adjust(bottom=0, top=0.83, wspace=0, left=0, right=1)\n            plt.suptitle(\n                \"n_cluster=%i, connectivity=%r\"\n                % (n_clusters, connectivity is not None),\n                size=17,\n            )\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.9.21"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}