{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "063e4e3e",
   "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": 1,
     "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": "code",
   "execution_count": 2,
   "id": "370d673f",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "plt.rcParams[\"figure.figsize\"] = (10, 5)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "019ab614",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# A connectivity-based algorithm: Agglomerative clustering\n",
    "\n",
    "## Outline\n",
    "\n",
    "- Algorithm\n",
    "- scikit-learn implementation\n",
    "- Choose K\n",
    "- Linkage"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec775a8c",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Toy data generation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "13f522d1",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 6484 characters]",
      "text/plain": [
       "<Figure size 720x360 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "means = [np.array([1, 1]), np.array([5, 5]), np.array([5, 1])]\n",
    "covariance = np.array([[0.25, 0], [0, 0.25]])\n",
    "n_points = 10\n",
    "\n",
    "data = [\n",
    "    np.random.multivariate_normal(mean=means[i], cov=covariance, size=n_points)\n",
    "    for i in range(3)\n",
    "]\n",
    "all_data = np.r_[data[0], data[1], data[2]]\n",
    "\n",
    "plt.scatter(all_data[:, 0], all_data[:, 1])\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "babc0d81",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Agglomerative clustering algorithm\n",
    "\n",
    "__Objective__: Recursively merges pair of clusters of sample data.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2f77e30b",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## K-means using scikit-learn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "58cc2222",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 11984 characters]",
      "text/plain": [
       "<Figure size 720x360 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "from sklearn.cluster import AgglomerativeClustering\n",
    "\n",
    "ac = AgglomerativeClustering(n_clusters=3)\n",
    "clusters = ac.fit_predict(all_data)\n",
    "\n",
    "plt.scatter(all_data[:, 0], all_data[:, 1], c=clusters)\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1abc56c1",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Visualize dendrogram"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "d52284a0",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Plot Dendrogram\n"
     ]
    },
    {
     "data": {
      "image/png": "[encoded data, 6920 characters]",
      "text/plain": [
       "<Figure size 720x360 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "from scipy.cluster.hierarchy import dendrogram\n",
    "\n",
    "print(\"Plot Dendrogram\")\n",
    "\n",
    "ac = AgglomerativeClustering(n_clusters=3, compute_distances=True)\n",
    "clusters = ac.fit(all_data)\n",
    "\n",
    "children = ac.children_\n",
    "distances = ac.distances_\n",
    "n_observations = np.arange(2, children.shape[0] + 2)\n",
    "\n",
    "linkage_matrix = np.c_[children, distances, n_observations]\n",
    "\n",
    "dendrogram(linkage_matrix, labels=ac.labels_)\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc1f919a",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Choose optimal number of clusters K\n",
    "\n",
    "Plot the height of the different successive merges.\\\n",
    "Find the elbow."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "7676f1a2",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 5772 characters]",
      "text/plain": [
       "<Figure size 720x360 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "x = np.arange(3 * n_points - 1, 0, -1)\n",
    "y = ac.distances_\n",
    "\n",
    "plt.bar(x, y)\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b95a0d2",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Linkage\n",
    "\n",
    "The linkage represent how the similarity between different groups of points is computed.\n",
    "\n",
    "Different linkages in scikit-learn:\n",
    "- __average__: uses the average of the distances of each observation of the two sets.\n",
    "- __complete__: linkage uses the maximum distances between all observations of the two sets.\n",
    "- __single__: uses the minimum of the distances between all observations of the two sets.\n",
    "- __ward__: minimizes the variance of the clusters being merged."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f823699e",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Visualization of the influence of different linkage strategies\n",
    "\n",
    "<img src=\"images/aggloClustering_linkage_comparison.png\" width=\"500px\"/>"
   ]
  }
 ],
 "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
}
