
.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "auto_examples/cluster/plot_ward_structured_vs_unstructured.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_ward_structured_vs_unstructured.py>`
        to download the full example code.

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

.. _sphx_glr_auto_examples_cluster_plot_ward_structured_vs_unstructured.py:


===========================================================
Hierarchical clustering: structured vs unstructured ward
===========================================================

Example builds a swiss roll dataset and runs
hierarchical clustering on their position.

For more information, see :ref:`hierarchical_clustering`.

In a first step, the hierarchical clustering is performed without connectivity
constraints on the structure and is solely based on distance, whereas in
a second step the clustering is restricted to the k-Nearest Neighbors
graph: it's a hierarchical clustering with structure prior.

Some of the clusters learned without connectivity constraints do not
respect the structure of the swiss roll and extend across different folds of
the manifolds. On the opposite, when opposing connectivity constraints,
the clusters form a nice parcellation of the swiss roll.

.. GENERATED FROM PYTHON SOURCE LINES 22-35

.. code-block:: Python


    # Authors : Vincent Michel, 2010
    #           Alexandre Gramfort, 2010
    #           Gael Varoquaux, 2010
    # License: BSD 3 clause

    import time as time

    # The following import is required
    # for 3D projection to work with matplotlib < 3.2
    import mpl_toolkits.mplot3d  # noqa: F401
    import numpy as np








.. GENERATED FROM PYTHON SOURCE LINES 36-40

Generate data
-------------

We start by generating the Swiss Roll dataset.

.. GENERATED FROM PYTHON SOURCE LINES 40-48

.. code-block:: Python

    from sklearn.datasets import make_swiss_roll

    n_samples = 1500
    noise = 0.05
    X, _ = make_swiss_roll(n_samples, noise=noise)
    # Make it thinner
    X[:, 1] *= 0.5








.. GENERATED FROM PYTHON SOURCE LINES 49-54

Compute clustering
------------------

We perform AgglomerativeClustering which comes under Hierarchical Clustering
without any connectivity constraints.

.. GENERATED FROM PYTHON SOURCE LINES 54-65

.. code-block:: Python


    from sklearn.cluster import AgglomerativeClustering

    print("Compute unstructured hierarchical clustering...")
    st = time.time()
    ward = AgglomerativeClustering(n_clusters=6, linkage="ward").fit(X)
    elapsed_time = time.time() - st
    label = ward.labels_
    print(f"Elapsed time: {elapsed_time:.2f}s")
    print(f"Number of points: {label.size}")





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    Compute unstructured hierarchical clustering...
    Elapsed time: 0.03s
    Number of points: 1500




.. GENERATED FROM PYTHON SOURCE LINES 66-69

Plot result
-----------
Plotting the unstructured hierarchical clusters.

.. GENERATED FROM PYTHON SOURCE LINES 69-86

.. code-block:: Python


    import matplotlib.pyplot as plt

    fig1 = plt.figure()
    ax1 = fig1.add_subplot(111, projection="3d", elev=7, azim=-80)
    ax1.set_position([0, 0, 0.95, 1])
    for l in np.unique(label):
        ax1.scatter(
            X[label == l, 0],
            X[label == l, 1],
            X[label == l, 2],
            color=plt.cm.jet(float(l) / np.max(label + 1)),
            s=20,
            edgecolor="k",
        )
    _ = fig1.suptitle(f"Without connectivity constraints (time {elapsed_time:.2f}s)")




.. image-sg:: /auto_examples/cluster/images/sphx_glr_plot_ward_structured_vs_unstructured_001.png
   :alt: Without connectivity constraints (time 0.03s)
   :srcset: /auto_examples/cluster/images/sphx_glr_plot_ward_structured_vs_unstructured_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 87-89

We are defining k-Nearest Neighbors with 10 neighbors
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 89-94

.. code-block:: Python


    from sklearn.neighbors import kneighbors_graph

    connectivity = kneighbors_graph(X, n_neighbors=10, include_self=False)








.. GENERATED FROM PYTHON SOURCE LINES 95-99

Compute clustering
------------------

We perform AgglomerativeClustering again with connectivity constraints.

.. GENERATED FROM PYTHON SOURCE LINES 99-110

.. code-block:: Python


    print("Compute structured hierarchical clustering...")
    st = time.time()
    ward = AgglomerativeClustering(
        n_clusters=6, connectivity=connectivity, linkage="ward"
    ).fit(X)
    elapsed_time = time.time() - st
    label = ward.labels_
    print(f"Elapsed time: {elapsed_time:.2f}s")
    print(f"Number of points: {label.size}")





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    Compute structured hierarchical clustering...
    Elapsed time: 0.06s
    Number of points: 1500




.. GENERATED FROM PYTHON SOURCE LINES 111-115

Plot result
-----------

Plotting the structured hierarchical clusters.

.. GENERATED FROM PYTHON SOURCE LINES 115-131

.. code-block:: Python


    fig2 = plt.figure()
    ax2 = fig2.add_subplot(121, projection="3d", elev=7, azim=-80)
    ax2.set_position([0, 0, 0.95, 1])
    for l in np.unique(label):
        ax2.scatter(
            X[label == l, 0],
            X[label == l, 1],
            X[label == l, 2],
            color=plt.cm.jet(float(l) / np.max(label + 1)),
            s=20,
            edgecolor="k",
        )
    fig2.suptitle(f"With connectivity constraints (time {elapsed_time:.2f}s)")

    plt.show()



.. image-sg:: /auto_examples/cluster/images/sphx_glr_plot_ward_structured_vs_unstructured_002.png
   :alt: With connectivity constraints (time 0.06s)
   :srcset: /auto_examples/cluster/images/sphx_glr_plot_ward_structured_vs_unstructured_002.png
   :class: sphx-glr-single-img






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

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


.. _sphx_glr_download_auto_examples_cluster_plot_ward_structured_vs_unstructured.py:

.. only:: html

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

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

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

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

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

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_ward_structured_vs_unstructured.zip <plot_ward_structured_vs_unstructured.zip>`


.. only:: html

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

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