{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "f3218f39",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "<style>\n",
       ".output_png {\n",
       "    display: table-cell;\n",
       "    text-align: center;\n",
       "    vertical-align: middle;\n",
       "}\n",
       "</style>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.core.display import HTML\n",
    "\n",
    "HTML(\n",
    "    \"\"\"\n",
    "<style>\n",
    ".output_png {\n",
    "    display: table-cell;\n",
    "    text-align: center;\n",
    "    vertical-align: middle;\n",
    "}\n",
    "</style>\n",
    "\"\"\"\n",
    ")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d92ea1e",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Introduction to clustering\n",
    "\n",
    "## Outline\n",
    "\n",
    "- What is clustering?\n",
    "- Why is it used?\n",
    "- How to evaluate it?\n",
    "- How to choose a clustering algorithm?\n",
    "\n",
    "_Question: What do you know about machine learning / data science?_"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8c3562e9",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## What is clustering?\n",
    "\n",
    "__Wikipedia__: \"Cluster analysis is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense) to each other than to those in other groups (clusters).\"\n",
    "\n",
    "### Example 1: How would you group objects in the following example?\n",
    "<br>\n",
    "<center><img src=\"images/example_lego_in.png\" width=\"500px\"/></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13f28171",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "3628e5cd",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## What is clustering?\n",
    "\n",
    "__Wikipedia__: \"Cluster analysis is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense) to each other than to those in other groups (clusters).\"\n",
    "\n",
    "### Example 1: Classification based on shape and color features\n",
    "<br>\n",
    "\n",
    "<center><img src=\"images/example_lego_out.png\" width=\"700px\"/></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5284963b",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## What is clustering?\n",
    "\n",
    "### Clustering is Unsupervised Classification\n",
    "\n",
    "A clustering problem is defined by a set of data points on which we don't know the labels, but that we want to group together in a smart way."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5afb7fd9",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## What is clustering?\n",
    "\n",
    "### Toy data generation\n",
    "\n",
    "Let's generate an unsupervised dataset in 2D, composed of three natural clusters coming from different multivariate Gaussian distributions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "07379552",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import seaborn as sns\n",
    "from sklearn.datasets import make_blobs, make_moons\n",
    "\n",
    "plt.rcParams[\"figure.figsize\"] = (8, 8)\n",
    "sns.set_theme()\n",
    "sns.set_context(\"talk\")\n",
    "\n",
    "n_points = 100\n",
    "data, labels = make_blobs(\n",
    "    n_samples=n_points, n_features=2, centers=3, cluster_std=1, center_box=[-10, 10]\n",
    ")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a08cb2a",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## What is clustering?\n",
    "\n",
    "### Clustering problem\n",
    "\n",
    "A set of unlabeled data points"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "382785f6",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 25868 characters]",
      "text/plain": [
       "<Figure size 576x576 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "sns.scatterplot(x=data[:, 0], y=data[:, 1])\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "44fe3c81",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## What is clustering?\n",
    "\n",
    "### Objective of clustering\n",
    "\n",
    "The objective of a clustering algorithm is to retrieve the intrinsic clusters in the unsupervised data. In other words, which data point come from which distribution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "44f55473",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 41532 characters]",
      "text/plain": [
       "<Figure size 576x576 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "sns.scatterplot(x=data[:, 0], y=data[:, 1], hue=labels, palette=\"tab10\")\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2e139f0b",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Features used for clustering\n",
    "\n",
    "### Example 2: How would you group objects in the following example?\n",
    "<br>\n",
    "<center><img src=\"images/example_tools_in.png\" width=\"500px\"/><center>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c1565bcd",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Feature used for clustering\n",
    "\n",
    "\n",
    "### Example 2: Classification based on semantic features\n",
    "<br>\n",
    "\n",
    "<center><img src=\"images/example_tools_out.jpg\" width=\"700px\"/></center>\n",
    "\n",
    "Why not classifying objects based on their size/weight/color? Such classifications could also be useful for different applications.\n",
    "\n",
    "$\\rightarrow$ __The choice of the characteristics, as well as the distance metrics used to compute clustering is paramount and can change drastically the results. These choices are application dependant.__"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c9ff2a1e",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "## Take-home messages\n",
    "\n",
    "* The classification resulting from clustering depends on the __features__ used to represent entities."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f52c1c55",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Why do we use clustering?\n",
    "\n",
    "### Unsupervised robotic sorting\n",
    "[video1](https://www.youtube.com/watch?v=NpZIwY3H-gE)\n",
    "\n",
    "[video2](https://www.youtube.com/watch?v=korkcYs1EHM)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6be005a3",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Why do we use clustering?\n",
    "\n",
    "### Recommender systems\n",
    "\n",
    "<br>\n",
    "\n",
    "<center><img src=\"images/clustering_recommender.png\" width=\"900px\"/></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3503f8d9",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Why do we use clustering?\n",
    "\n",
    "### Image segmentation: Tumor identification\n",
    "\n",
    "<br>\n",
    "\n",
    "<center><img src=\"images/tumor.jpg\" width=\"700px\"/></center>\n",
    "\n",
    "_source: https://www.mathworks.com/matlabcentral/fileexchange/27022-image-segmentation-using-fuzzy-c-means-with-two-image-inputs_"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8b022889",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Why do we use clustering?\n",
    "\n",
    "### Image segmentation: Ecological studies\n",
    "\n",
    "<br>\n",
    "\n",
    "<center><img src=\"images/forest_segmentation.png\" width=\"900px\"/></center>\n",
    "\n",
    "_source: https://www.kdnuggets.com/2019/08/introduction-image-segmentation-k-means-clustering.html_"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dbebfe62",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Why do we use clustering?\n",
    "\n",
    "### Epidemiology: Covid contaminations prediction\n",
    "    \n",
    "> Pereira, I. G., Guerin, J. M., Silva Júnior, A. G., Garcia, G. S., Piscitelli, P., Miani, A., ... & Gonçalves, L. M. G. (2020). _Forecasting Covid-19 dynamics in Brazil: a data driven approach._ International Journal of Environmental Research and Public Health, 17(14), 5115."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ebfa4500",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## How do we evaluate clustering results?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "727d66f4",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Internal metric:\n",
    "\n",
    "- Silhouette coefficient\n",
    "- Davies–Bouldin index\n",
    "- Dunn Index"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2df07841",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Example internal metric: Silhouette coefficient\n",
    "\n",
    "For a point $x_i$, which is associated to cluster $C(i)$, we note $a(i)$ the mean distance between $x_i$ and other points in $C(i)$:\\\n",
    "$$a(i)=\\frac{1}{|C(i)|-1} \\sum_{j \\in C(i), j \\neq i} d(x_i, x_j)$$\\\n",
    "and we note $b(i)$ the mean distance between $x_i$ and the points of the closest other cluster:\\\n",
    "$$b(i)=\\min_{k \\neq C(i)} \\frac{1}{|C_k|}\\sum_{j\\in C_k} d(x_i, x_j)$$\n",
    "Then, the silhouette for point $x_i$ is:\n",
    "$$s(i) = \\frac{b(i)-a(i)}{max(a(i), b(i))}$$\n",
    "And the silhouette for the entire dataset is\n",
    "$$S = \\frac{1}{K} \\sum_{k=1}^K \\frac{1}{|C_k|} \\sum_{i \\in C_k} s(i)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "db712288",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Visualize silhouette: correct clusters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "205e9450",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 41532 characters]",
      "text/plain": [
       "<Figure size 576x576 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from sklearn.metrics import silhouette_score\n",
    "\n",
    "sns.scatterplot(x=data[:, 0], y=data[:, 1], hue=labels, palette=\"tab10\")\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6e34f696",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Visualize silhouette: random clusters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "33081e44",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 41692 characters]",
      "text/plain": [
       "<Figure size 576x576 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "random_clusters = np.random.randint(0, 3, n_points)\n",
    "\n",
    "sns.scatterplot(x=data[:, 0], y=data[:, 1], hue=random_clusters, palette=\"tab10\")\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "71dafea5",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Visualize silhouette: only two clusters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "197f0652",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 39976 characters]",
      "text/plain": [
       "<Figure size 576x576 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from sklearn.cluster import KMeans\n",
    "\n",
    "twogroups_clusters = KMeans(2).fit_predict(data)\n",
    "\n",
    "sns.scatterplot(x=data[:, 0], y=data[:, 1], hue=twogroups_clusters, palette=\"tab10\")\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fcf0235a",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Visualize silhouette: many clusters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "fe519d51",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 2  6 13 12 13  7  1  7 11  7  7 18  6 15  7  0  3  4  8  9 12 11  7 13\n",
      "  4 10  1 12  9  0  9 16  0  1  2  4 12 12 12  7 10 16  8 15 12  4  4 12\n",
      " 15  8  1  2 10  9  6  5 13  0  6  7  5  3 14  1  7 17  6 14  7  2  7 19\n",
      "  8  2 15  9 12 14  5  1 18  3  8  5  2 16 17  7 10 18 19 13  3 11  6 18\n",
      " 11 14  3 10]\n"
     ]
    },
    {
     "data": {
      "image/png": "[encoded data, 39304 characters]",
      "text/plain": [
       "<Figure size 576x576 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "many_clusters = KMeans(20).fit_predict(data)\n",
    "print(many_clusters)\n",
    "\n",
    "sns.scatterplot(x=data[:, 0], y=data[:, 1], hue=many_clusters, palette=\"tab10\")\n",
    "plt.legend(\"\")\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15330967",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Compare Silhouette scores"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "8b41194d",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Silhouette true labels:      0.8474469113729575\n",
      "Silhouette random clusters:  -0.04685894742512662\n",
      "Silhouette two clusters:     0.5806310922637636\n",
      "Silhouette many clusters:    0.44519330790414796\n"
     ]
    }
   ],
   "source": [
    "print(\"Silhouette true labels:     \", silhouette_score(data, labels))\n",
    "print(\"Silhouette random clusters: \", silhouette_score(data, random_clusters))\n",
    "print(\"Silhouette two clusters:    \", silhouette_score(data, twogroups_clusters))\n",
    "print(\"Silhouette many clusters:   \", silhouette_score(data, many_clusters))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a97921ee",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### External metrics\n",
    "\n",
    "- Purity\n",
    "- Clustering accuracy\n",
    "- Folkes-Mallows index\n",
    "- Normalized Mutual Information"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21c511f8",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Example external metric\n",
    "\n",
    "$\\to$ Need for specific clustering metrics when ground truth is known\n",
    "\n",
    "#### Example: Purity\n",
    "Let's call $\\mathcal{C}$ the clusters found, and $\\mathcal{D}$ the ground truth classes:\n",
    "\n",
    "$$purity = \\frac{1}{N} \\sum_{k \\in \\mathcal{C}} \\max_{d \\in D} |k \\cap d|$$\n",
    "\n",
    "_Issue: more clusters $\\to$ Decreasing purity_"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "222307f8",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Choosing a clustering algorithm\n",
    "\n",
    "#### Different families of clustering algorithms\n",
    "\n",
    "- Partitioning-based\n",
    "- Connectivity-based\n",
    "- Density-based"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "64f4880a",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Partitioning-based\n",
    "\n",
    "#### Pros\n",
    "- Can conduct inference on new data points\n",
    "- Usually fast\n",
    "\n",
    "#### Cons\n",
    "- Number of clusters required\n",
    "- No outlier detection\n",
    "- Need access to point values\n",
    "\n",
    "__Example:__ K-means"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "41392ab9",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 43908 characters]",
      "text/plain": [
       "<Figure size 576x576 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2.184988   6.51544932] 0\n",
      "[ 6.12525812 -4.12924726] 0\n"
     ]
    }
   ],
   "source": [
    "clustering_algo = KMeans(3)  # Number of clusters required\n",
    "clusters = clustering_algo.fit_predict(data)\n",
    "\n",
    "new_x = np.random.uniform(-10, 10, (2, 2))  # Can conduct inference on new points\n",
    "\n",
    "sns.scatterplot(x=data[:, 0], y=data[:, 1], hue=clusters, palette=\"tab10\")\n",
    "plt.scatter(new_x[:, 0], new_x[:, 1], marker=\"X\", c=\"r\")\n",
    "plt.show()  # No outlier detection\n",
    "\n",
    "print(new_x[0, :], clustering_algo.predict(new_x)[0])\n",
    "print(new_x[1, :], clustering_algo.predict(new_x)[1])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d7ceaa6b",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Connectivity-based\n",
    "\n",
    "#### Pros\n",
    "- Does not need access to data points values (only distances)\n",
    "- Can handle non linearly separated clusters\n",
    "\n",
    "#### Cons\n",
    "- Number of clusters required\n",
    "- No outlier detection\n",
    "- Usually slow\n",
    "- Cannot conduct inference\n",
    "\n",
    "__Example:__ Hierarchical clustering"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "662b7e06",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 104256 characters]",
      "text/plain": [
       "<Figure size 576x576 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "data, labels = make_moons(n_samples=500, noise=0.05)\n",
    "sns.scatterplot(x=data[:, 0], y=data[:, 1], hue=labels, palette=\"tab10\")\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "161afdfd",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 104516 characters]",
      "text/plain": [
       "<Figure size 576x576 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "clusters_partitioning = KMeans(2).fit_predict(data)\n",
    "sns.scatterplot(x=data[:, 0], y=data[:, 1], hue=clusters_partitioning, palette=\"tab10\")\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "ea478879",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 104256 characters]",
      "text/plain": [
       "<Figure size 576x576 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from sklearn.cluster import AgglomerativeClustering\n",
    "\n",
    "clusters_connectivity = AgglomerativeClustering(2, linkage=\"single\").fit_predict(data)\n",
    "sns.scatterplot(x=data[:, 0], y=data[:, 1], hue=clusters_connectivity, palette=\"tab10\")\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a70c1f25",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Density-based\n",
    "\n",
    "#### Pros\n",
    "- Does not need access to data points values\n",
    "- Can handle non linearly separable clusters\n",
    "- Does not need number of clusters\n",
    "- Can handle outliers\n",
    "\n",
    "#### Cons\n",
    "- Usually slow\n",
    "- Cannot be used for inference\n",
    "\n",
    "__Example:__ DBSCAN"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "5259f58c",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 94128 characters]",
      "text/plain": [
       "<Figure size 576x576 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "noise = np.random.uniform(-1.5, 1.5, (50, 2))\n",
    "data_noise = np.r_[data, noise]\n",
    "\n",
    "clusters_connectivity = AgglomerativeClustering(2, linkage=\"single\").fit_predict(\n",
    "    data_noise\n",
    ")\n",
    "sns.scatterplot(\n",
    "    x=data_noise[:, 0], y=data_noise[:, 1], hue=clusters_connectivity, palette=\"tab10\"\n",
    ")\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "4c7927fd",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 92848 characters]",
      "text/plain": [
       "<Figure size 576x576 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from sklearn.cluster import DBSCAN\n",
    "\n",
    "clusters_density = DBSCAN(eps=0.2).fit_predict(\n",
    "    data_noise\n",
    ")  # Does not need number of clusters\n",
    "sns.scatterplot(\n",
    "    x=data_noise[:, 0], y=data_noise[:, 1], hue=clusters_density, palette=\"tab10\"\n",
    ")\n",
    "plt.show()  # Can handle outliers\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6b17e3dc",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7d75e468",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
