notebooks-spanish/20-clustering_jerarquico_y_basado_densidades.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbpresent": {
     "id": "2de13356-e9ae-466c-89d1-50618945c658"
    }
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import numpy as np\n",
    "from matplotlib import pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "4a9d75ee-def8-451e-836f-707a63d8ea90"
    }
   },
   "source": [
    "# Aprendizaje no supervisado: algoritmos de clustering jerárquicos y basados en densidades"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "2e676319-4de0-4ee0-84ec-f525353b5195"
    }
   },
   "source": [
    "En el cuaderno número 8, introdujimos uno de los algoritmos de agrupamiento más básicos y utilizados, el K-means. Una de las ventajas del K-means es que es extremadamente fácil de implementar y que es muy eficiente computacionalmente si lo comparamos a otros algoritmos de agrupamiento. Sin embargo, ya vimos que una de las debilidades de K-Means es que solo trabaja bien si los datos a agrupar se distribuyen en formas esféricas. Además, tenemos que decidir un número de grupos, *k*, *a priori*, lo que puede ser un problema si no tenemos conocimiento previo acerca de cuántos grupos esperamos obtener."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "7f44eab5-590f-4228-acdb-4fd1d187a441"
    }
   },
   "source": [
    "En este cuaderno, vamos a ver dos formas alternativas de hacer agrupamiento, agrupamiento jerárquico y agrupamiento basado en densidades. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "a9b317b4-49cb-47e0-8f69-5f6ad2491370"
    }
   },
   "source": [
    "# Agrupamiento jerárquico"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "d70d19aa-a949-4942-89c0-8c4911bbc733"
    }
   },
   "source": [
    "Una característica importante del agrupamiento jerárquico es que podemos visualizar los resultados como un dendograma, un diagrama de árbol. Utilizando la visualización, podemos entonces decidir el umbral de profundidad a partir del cual vamos a cortar el árbol para conseguir un agrupamiento. En otras palabras, no tenemos que decidir el número de grupos sin tener ninguna información. \n",
    "\n",
    "### Agrupamiento aglomerativo y divisivo\n",
    "\n",
    "Además, podemos distinguir dos formas principales de clustering jerárquico: divisivo y aglomerativo. En el clustering aglomerativo, empezamos con un único patrón por clúster y vamos agrupando clusters (uniendo aquellos que están más cercanos), siguiendo una estrategia *bottom-up* para construir el dendograma. En el clustering divisivo, sin embargo, empezamos incluyendo todos los puntos en un único grupo y luego vamos dividiendo ese grupo en subgrupos más pequeños, siguiendo una estrategia *top-down*.\n",
    "\n",
    "Nosotros nos centraremos en el clustering aglomerativo."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "d448e9d1-f80d-4bf4-a322-9af800ce359c"
    }
   },
   "source": [
    "### Enlace simple y completo\n",
    "\n",
    "Ahora, la pregunta es cómo vamos a medir la distancia entre ejemplo. Una forma habitual es usar la distancia Euclídea, que es lo que hace el algoritmo K-Means."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "045c17ed-c253-4b84-813b-0f3f2c4eee3a"
    }
   },
   "source": [
    "Sin embargo, el algoritmo jerárquico requiere medir la distancia entre grupos de puntos, es decir, saber la distancia entre un clúster (agrupación de puntos) y otro. Dos formas de hacer esto es usar el enlace simple y el enlace completo.\n",
    "\n",
    "En el enlace simple, tomamos el par de puntos más similar (basándonos en distancia Euclídea, por ejemplo) de todos los puntos que pertenecen a los dos grupos. En el enlace competo, tomamos el par de puntos más lejano.\n",
    "![](figures/clustering-linkage.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "b6cc173c-044c-4a59-8a51-ec81eb2a1098"
    }
   },
   "source": [
    "Para ver como funciona el clustering aglomerativo, vamos a cargar el dataset Iris (pretendiendo que no conocemos las etiquetas reales y queremos encontrar las espacies):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "b552a94c-9dc1-4c76-9d9b-90a47cd7811a"
    }
   },
   "outputs": [],
   "source": [
    "from sklearn import datasets\n",
    "\n",
    "iris = datasets.load_iris()\n",
    "X = iris.data[:, [2, 3]]\n",
    "y = iris.target\n",
    "n_samples, n_features = X.shape\n",
    "\n",
    "plt.scatter(X[:, 0], X[:, 1], c=y);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "473764d4-3610-43e8-94a0-d62731dd5a1c"
    }
   },
   "source": [
    "Ahora vamos haciendo una exploración basada en clustering, visualizando el dendograma utilizando las funciones `linkage` (que hace clustering jerárquico) y `dendrogram` (que dibuja el dendograma) de SciPy:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "d7f4a0e0-5b4f-4e08-9c77-fd1b1d13c877"
    }
   },
   "outputs": [],
   "source": [
    "from scipy.cluster.hierarchy import linkage\n",
    "from scipy.cluster.hierarchy import dendrogram\n",
    "\n",
    "clusters = linkage(X, \n",
    "                   metric='euclidean',\n",
    "                   method='complete')\n",
    "\n",
    "dendr = dendrogram(clusters)\n",
    "\n",
    "plt.ylabel('Distancia Euclídea');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "68cb3270-9d4b-450f-9372-58989fe93a3d"
    }
   },
   "source": [
    "Alternativamente, podemos usar el `AgglomerativeClustering` de scikit-learn y dividr el dataset en 3 clases. ¿Puedes adivinar qué tres clases encontraremos?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "4746ea9e-3206-4e5a-bf06-8e2cd49c48d1"
    }
   },
   "outputs": [],
   "source": [
    "from sklearn.cluster import AgglomerativeClustering\n",
    "\n",
    "ac = AgglomerativeClustering(n_clusters=3,\n",
    "                             affinity='euclidean',\n",
    "                             linkage='complete')\n",
    "\n",
    "prediction = ac.fit_predict(X)\n",
    "print('Etiquetas de clase: %s\\n' % prediction)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "a4e419ac-a735-442e-96bd-b90e60691f97"
    }
   },
   "outputs": [],
   "source": [
    "plt.scatter(X[:, 0], X[:, 1], c=prediction);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "63c6aeb6-3b8f-40f4-b1a8-b5e2526beaa5"
    }
   },
   "source": [
    "# Clustering basado en densidades - DBSCAN"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "688a6a37-3a28-40c8-81ba-f5c92f6d7aa8"
    }
   },
   "source": [
    "Otra forma útil de agrupamiento es la conocida como *Density-based Spatial Clustering of Applications with Noise* (DBSCAN). En esencia, podríamos pensar que DBSCAN es un algoritmo que divide el dataset en subgrupos, buscando regiones densas de puntos.\n",
    "\n",
    "En DBSCAN, hay tres tipos de puntos:\n",
    "\n",
    "- Puntos núcleo: puntos que tienen un mínimo número de puntos (MinPts) contenidos en una hiperesfera de radio epsilon.\n",
    "- Puntos fronterizos: puntos que no son puntos núcleo, ya que no tienen suficientes puntos en su vecindario, pero si que pertenecen al vecindario de radio epsilon de algún punto núcleo.\n",
    "- Puntos de ruido: todos los puntos que no pertenecen a ninguna de las categorías anteriores.\n",
    "\n",
    "![](figures/dbscan.png)\n",
    "\n",
    "Una ventaja de DBSCAN es que no tenemos que especificar el número de clusters a priori. Sin embargo, requiere que establezcamos dos hiper-parámetros adicionales que son ``MinPts`` y el radio ``epsilon``."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "98acb13b-bbf6-412e-a7eb-cc096c34dca1"
    }
   },
   "outputs": [],
   "source": [
    "from sklearn.datasets import make_moons\n",
    "X, y = make_moons(n_samples=400,\n",
    "                  noise=0.1,\n",
    "                  random_state=1)\n",
    "plt.scatter(X[:,0], X[:,1])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "86c183f7-0889-443c-b989-219a2c9a1aad"
    }
   },
   "outputs": [],
   "source": [
    "from sklearn.cluster import DBSCAN\n",
    "\n",
    "db = DBSCAN(eps=0.2,\n",
    "            min_samples=10,\n",
    "            metric='euclidean')\n",
    "prediction = db.fit_predict(X)\n",
    "\n",
    "print(\"Etiquetas predichas:\\n\", prediction)\n",
    "\n",
    "plt.scatter(X[:, 0], X[:, 1], c=prediction);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "6881939d-0bfe-4768-9342-1fc68a0b8dbc"
    }
   },
   "source": [
    "<div class=\"alert alert-success\">\n",
    "    <b>EJERCICIO</b>:\n",
    "     <ul>\n",
    "      <li>\n",
    "      Usando el siguiente conjunto sintético, dos círculos concéntricos, experimenta los resultados obtenidos con los algoritmos de clustering que hemos considerado hasta el momento: `KMeans`, `AgglomerativeClustering` y `DBSCAN`.\n",
    "\n",
    "¿Qué algoritmo reproduce o descubre mejor la estructura oculta (suponiendo que no conocemos `y`)?\n",
    "\n",
    "¿Puedes razonar por qué este algoritmo funciona mientras que los otros dos fallan?\n",
    "      </li>\n",
    "    </ul>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "nbpresent": {
     "id": "4ad922fc-9e38-4d1d-b0ed-b0654c1c483a"
    }
   },
   "outputs": [],
   "source": [
    "from sklearn.datasets import make_circles\n",
    "\n",
    "X, y = make_circles(n_samples=1500, \n",
    "                    factor=.4, \n",
    "                    noise=.05)\n",
    "\n",
    "plt.scatter(X[:, 0], X[:, 1], c=y);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}