
.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "auto_examples/cluster/plot_agglomerative_clustering.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_auto_examples_cluster_plot_agglomerative_clustering.py>`
        to download the full example code or to run this example in your browser via Binder

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_auto_examples_cluster_plot_agglomerative_clustering.py:


Agglomerative clustering with and without structure
===================================================

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.

There are two advantages of imposing a connectivity. First, clustering
with sparse connectivity matrices is faster in general.

Second, when using a connectivity matrix, single, 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 (
while single linkage exaggerates the behaviour by considering only the
shortest distance between clusters). The connectivity graph breaks this
mechanism for average and complete linkage, making them resemble the more
brittle single linkage. 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.

.. GENERATED FROM PYTHON SOURCE LINES 26-85



.. rst-class:: sphx-glr-horizontal


    *

      .. image-sg:: /auto_examples/cluster/images/sphx_glr_plot_agglomerative_clustering_001.png
         :alt: n_cluster=30, connectivity=False, linkage=average (time 0.02s), linkage=complete (time 0.02s), linkage=ward (time 0.02s), linkage=single (time 0.01s)
         :srcset: /auto_examples/cluster/images/sphx_glr_plot_agglomerative_clustering_001.png
         :class: sphx-glr-multi-img

    *

      .. image-sg:: /auto_examples/cluster/images/sphx_glr_plot_agglomerative_clustering_002.png
         :alt: n_cluster=3, connectivity=False, linkage=average (time 0.02s), linkage=complete (time 0.02s), linkage=ward (time 0.02s), linkage=single (time 0.01s)
         :srcset: /auto_examples/cluster/images/sphx_glr_plot_agglomerative_clustering_002.png
         :class: sphx-glr-multi-img

    *

      .. image-sg:: /auto_examples/cluster/images/sphx_glr_plot_agglomerative_clustering_003.png
         :alt: n_cluster=30, connectivity=True, linkage=average (time 0.07s), linkage=complete (time 0.07s), linkage=ward (time 0.08s), linkage=single (time 0.02s)
         :srcset: /auto_examples/cluster/images/sphx_glr_plot_agglomerative_clustering_003.png
         :class: sphx-glr-multi-img

    *

      .. image-sg:: /auto_examples/cluster/images/sphx_glr_plot_agglomerative_clustering_004.png
         :alt: n_cluster=3, connectivity=True, linkage=average (time 0.07s), linkage=complete (time 0.07s), linkage=ward (time 0.08s), linkage=single (time 0.02s)
         :srcset: /auto_examples/cluster/images/sphx_glr_plot_agglomerative_clustering_004.png
         :class: sphx-glr-multi-img





.. code-block:: default


    # Authors: Gael Varoquaux, Nelle Varoquaux
    # License: BSD 3 clause

    import time

    import matplotlib.pyplot as plt
    import numpy as np

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

    # Generate sample data
    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 += 0.7 * np.random.randn(2, n_samples)
    X = X.T

    # 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
    knn_graph = kneighbors_graph(X, 30, include_self=False)

    for connectivity in (None, knn_graph):
        for n_clusters in (30, 3):
            plt.figure(figsize=(10, 4))
            for index, linkage in enumerate(("average", "complete", "ward", "single")):
                plt.subplot(1, 4, index + 1)
                model = AgglomerativeClustering(
                    linkage=linkage, connectivity=connectivity, n_clusters=n_clusters
                )
                t0 = time.time()
                model.fit(X)
                elapsed_time = time.time() - t0
                plt.scatter(X[:, 0], X[:, 1], c=model.labels_, cmap=plt.cm.nipy_spectral)
                plt.title(
                    "linkage=%s\n(time %.2fs)" % (linkage, elapsed_time),
                    fontdict=dict(verticalalignment="top"),
                )
                plt.axis("equal")
                plt.axis("off")

                plt.subplots_adjust(bottom=0, top=0.83, wspace=0, left=0, right=1)
                plt.suptitle(
                    "n_cluster=%i, connectivity=%r"
                    % (n_clusters, connectivity is not None),
                    size=17,
                )


    plt.show()


.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 1.230 seconds)


.. _sphx_glr_download_auto_examples_cluster_plot_agglomerative_clustering.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example


    .. container:: binder-badge

      .. image:: images/binder_badge_logo.svg
        :target: https://mybinder.org/v2/gh/scikit-learn/scikit-learn/1.3.X?urlpath=lab/tree/notebooks/auto_examples/cluster/plot_agglomerative_clustering.ipynb
        :alt: Launch binder
        :width: 150 px



    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_agglomerative_clustering.py <plot_agglomerative_clustering.py>`

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_agglomerative_clustering.ipynb <plot_agglomerative_clustering.ipynb>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_
