talleres_inov_docente/2-02-aprendizaje_no_supervisado_agrupamiento.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Aprendizaje no supervisado parte 2 - agrupamiento"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El agrupamiento (*clustering*) consiste en formar grupos de ejemplos similares de acuerdo a alguna medida de semejanza prefijada o disimilitud (distancia), como la distancia Euclídea.\n",
    "\n",
    "<img width=\"60%\" src='figures/clustering.png'/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En esta sección, exploraremos la tarea básica de agrupamiento en algunas bases de datos sintéticas y del mundo real.\n",
    "\n",
    "Estas son algunas aplicaciones bastante comunes de los algoritmos de *clustering*:\n",
    "\n",
    "- Compresión para reducción de datos.\n",
    "- Resumir los datos como un paso de preprocesamiento para los sistemas de recomendación.\n",
    "- Agrupar noticias *web* relacionadas (p.ej. Google News) y resultados de búsquedas *web*.\n",
    "- Realizar perfiles de clientes en estrategias de marketing."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vamos a empezar creando un dataset sintético simple de dos dimensiones:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from sklearn.datasets import make_blobs\n",
    "\n",
    "X, y = make_blobs(random_state=42)\n",
    "X.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "plt.scatter(X[:, 0], X[:, 1]);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En el _scatter_ anterior, podemos ver tres grupos separados de datos y nos gustaría recuperarlos utilizando agrupamiento (algo así como \"descubrir\" las etiquetas de clase, que ya damos por sentadas en la tarea de clasificación).\n",
    "\n",
    "Incluso si los grupos son obvios en los datos, es difícil encontrarlos cuando estos datos están en un espacio de alta dimensionalidad, que no podemos visualizar en un único histograma o scatterplot."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ahora utilizaremos uno de los algoritmos de *clustering* más simples, K-means. Este es un algoritmo iterativo que busca aquellos tres centroides (centro de cada uno de los *clusters*) tales que la distancia desde cada punto a su centroide sea mínima.\n",
    "La implementación estándar de K-means utiliza la distancia Euclídea, por lo que debemos estar seguros de que todas nuestras variables están en la misma escala, especialmente para datasets reales. Para ello podemos aplicar la estandarización que vimos en el cuaderno anterior.\n",
    "<br/>\n",
    "<div class=\"alert alert-success\">\n",
    "    <b>Pregunta</b>:\n",
    "     <ul>\n",
    "      <li>\n",
    "      ¿Qué salida esperarías obtener con un algoritmo de *clustering*?\n",
    "      </li>\n",
    "    </ul>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sklearn.cluster import KMeans\n",
    "\n",
    "kmeans = KMeans(n_clusters=3, random_state=42)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Podemos obtener las etiquetas de los datos o llamando al método ``fit`` y después accediendo al atributo ``labels_`` del estimador KMeans, o llamando a ``fit_predict`` (que aplica los dos pasos seguidos). En cualquier caso, el resultado contiene el identificador del grupo al que asignamos cada punto."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "labels = kmeans.fit_predict(X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "labels"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print('¿Hemos acertado en todas las etiquetas?', np.all(y == labels))\n",
    "print('¿En cuantas hemos fallado?', np.sum(y != labels))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vamos a visualizar lo que hemos obtenido"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "plt.scatter(X[:, 0], X[:, 1], c=labels);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comparando con las etiquetas reales:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "plt.scatter(X[:, 0], X[:, 1], c=y);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Examinando el resultado de forma gráfica, está claro que podríamos estar satisfechos con los resultados obtenidos, pero, en general, nos gustaría tener una evaluación cuantitativa. ¿Qué tal comparar nuestras etiquetas aprendidas con las etiquetas reales?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from sklearn.metrics import confusion_matrix, accuracy_score\n",
    "\n",
    "print('Porcentaje de precisión:', accuracy_score(y, labels))\n",
    "print(confusion_matrix(y, labels))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "np.mean(y == labels)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-success\">\n",
    "    <b>EJERCICIO</b>:\n",
    "     <ul>\n",
    "      <li>\n",
    "      Después de mirar el array `y` real, el scatterplot y las etiquetas aprendidas, ¿sabes por que la precisión es 0.0 cuando debería ser 1.0 y como arreglarlo?\n",
    "      </li>\n",
    "    </ul>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Incluso si conseguimos los mismos grupos, los identificadores asignados son arbitrarios y no podemos recuperar los reales. Por tanto, tendremos que usar otro mecanismo de asignación de rendimiento, como el ``adjusted_rand_score``, el cuál es invariante a cualquier permutación de las etiquetas:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from sklearn.metrics import adjusted_rand_score\n",
    "\n",
    "adjusted_rand_score(y, labels)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Una de las desventajas del K-means es que tenemos que especificar el número de *clusters*, cosa que a menudo no conocemos *a priori*. Por ejemplo, veamos que pasa si ponemos k=2 para el dataset sintético anterior:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "kmeans = KMeans(n_clusters=2, random_state=42)\n",
    "labels = kmeans.fit_predict(X)\n",
    "plt.scatter(X[:, 0], X[:, 1], c=labels);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "kmeans.cluster_centers_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### El método del codo (*Elbow method*)\n",
    "\n",
    "El método del codo es una regla general para encontrar el número óptimo de *clusters*. Para ello, analizamos la dispersión de los *clusters* (también llamada inercia o SSE, suma de las distancias de cada punto a su centroide más cercano) para distintos valores de k:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "distortions = []\n",
    "for i in range(1, 11):\n",
    "    km = KMeans(n_clusters=i, \n",
    "                random_state=0)\n",
    "    km.fit(X)\n",
    "    distortions.append(km.inertia_)\n",
    "\n",
    "plt.plot(range(1, 11), distortions, marker='o')\n",
    "plt.xlabel(u'Número de grupos')\n",
    "plt.ylabel(u'Distorsión')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Después, tomamos el valor que lleva al pico del codo. Como podemos ver, ese valor será k=3 para este caso, lo que tiene sentido dado el conocimiento que tenemos del dataset."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**El agrupamiento siempre viene con suposiciones**: Un algoritmo de agrupamiento encuentra grupos haciendo suposiciones acerca de cómo deberían agruparse los ejemplos. Cada algoritmo hace suposiciones distintas y la calidad e interpretabilidad de nuestros resultados dependerá de si estas suposiciones son correctas para nuestro objetivo. Para el K-means, el modelo subyacente supone que todos los grupos tienen la misma varianza, esférica (si usamos distancia Euclídea).\n",
    "\n",
    "**En general, no hay ninguna garantía de que la estructura encontrada por un algoritmo de *clustering* sea aquello en lo que estás interesado**.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Fácilmente, podemos crear un dataset que tenga grupos no isotrópicos (distinta varianza en cada dimensión), caso en el que KMeans fallará:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "plt.figure(figsize=(12, 12))\n",
    "\n",
    "n_samples = 1500\n",
    "random_state = 170\n",
    "X, y = make_blobs(n_samples=n_samples, random_state=random_state)\n",
    "\n",
    "# Número de clusters incorrecto\n",
    "y_pred = KMeans(n_clusters=2, random_state=random_state).fit_predict(X)\n",
    "\n",
    "plt.subplot(221)\n",
    "plt.scatter(X[:, 0], X[:, 1], c=y_pred)\n",
    "plt.title(u\"Número de clusters incorrecto\")\n",
    "\n",
    "# Datos distribuidos de forma anisotrópica\n",
    "transformation = [[0.60834549, -0.63667341], [-0.40887718, 0.85253229]]\n",
    "X_aniso = np.dot(X, transformation)\n",
    "y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_aniso)\n",
    "\n",
    "plt.subplot(222)\n",
    "plt.scatter(X_aniso[:, 0], X_aniso[:, 1], c=y_pred)\n",
    "plt.title(u\"Clusters con distribución anisotrópica\")\n",
    "\n",
    "# Distinta varianza\n",
    "X_varied, y_varied = make_blobs(n_samples=n_samples,\n",
    "                                cluster_std=[1.0, 2.5, 0.5],\n",
    "                                random_state=random_state)\n",
    "y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_varied)\n",
    "\n",
    "plt.subplot(223)\n",
    "plt.scatter(X_varied[:, 0], X_varied[:, 1], c=y_pred)\n",
    "plt.title(\"Distinta varianza\")\n",
    "\n",
    "# Clusters de distinto tamaño\n",
    "X_filtered = np.vstack((X[y == 0][:500], X[y == 1][:100], X[y == 2][:10]))\n",
    "y_pred = KMeans(n_clusters=3,\n",
    "                random_state=random_state).fit_predict(X_filtered)\n",
    "\n",
    "plt.subplot(224)\n",
    "plt.scatter(X_filtered[:, 0], X_filtered[:, 1], c=y_pred)\n",
    "plt.title(u\"Distinto tamaño\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algunos métodos importantes de agrupamiento"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A continuación, algunos de los algoritmos de agrupamiento más importantes: \n",
    "\n",
    "- `sklearn.cluster.KMeans`: <br/>\n",
    "    El más simple aunque más efectivo algoritmo de agrupamiento. Hay que proporcionarle el número de grupos y asume que los datos están normalizados.\n",
    "- `sklearn.cluster.MeanShift`: <br/>\n",
    "    Puede encontrar *mejores* clusters que KMeans pero no es escalable para muchos ejemplos.\n",
    "- `sklearn.cluster.DBSCAN`: <br/>\n",
    "    Puede detectar grupos con formas irregulares, basándose en densidades, es decir, las regiones dispersas del espacio de entrada tienen más posibilidades de convertirse en fronteras entre *clusters*. También permite detectar *outliers* (datos que no pertenecen a ningún grupo).\n",
    "- `sklearn.cluster.AffinityPropagation`: <br/>\n",
    "    Algoritmo de agrupamiento basado en paso de mensajes entre puntos.\n",
    "- `sklearn.cluster.SpectralClustering`: <br/>\n",
    "    KMeans aplicado a la proyección de un grafo Laplaciano normalizado: encuentra cortes de mínimo coste del grafo normalizado cuando la matriz de afinidad se interpreta como la matriz de adyacencia de un grafo.\n",
    "- `sklearn.cluster.Ward`: <br/>\n",
    "    Implementa clustering jerárquico basado en el algoritmo de Ward, una aproximación que minimiza la varianza intra-cluster. En cada paso, minimiza la suma de diferencias cuadradas internas de todos los puntos de todos los grupos (criterio de inercia).\n",
    "\n",
    "Entre estos, el algoritmo de Ward, el SpectralClustering, el DBSCAN y el método de propagación de afinidad pueden trabajar también con matrices de similitud precomputadas."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"figures/cluster_comparison.png\" width=\"900\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-success\">\n",
    "    <b>EJERCICIO: agrupamiento de dígitos</b>:\n",
    "     <ul>\n",
    "      <li>\n",
    "      Aplica agrupamiento K-means a los datos de los dígitos, buscando 10 dígitos. Visualiza los centros como imágenes (es decir, redimensiona cada uno a 8x8 y usa ``plt.imshow``). ¿Te parece que los grupos estén relacionados con algunos dígitos particulares? ¿Qué valores de ``adjusted_rand_score`` obtienes?\n",
    "      </li>\n",
    "      <li>\n",
    "      Visualiza los dígitos proyectados como se hizo en el ejemplo anterior pero, esta vez, utiliza las etiquetas que proporciona KMeans como colores. ¿Qué observas?\n",
    "      </li>\n",
    "    </ul>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sklearn.datasets import load_digits\n",
    "digits = load_digits()\n",
    "# ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Agrupamiento aplicado a imágenes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Los algoritmos de agrupamiento se usan a menudo en el campo de procesamiento de imágenes. Algunas aplicaciones pueden ser: \n",
    " - **Compresión de información**. Una imagen RGB estańdar tiene 8 bits por píxel, lo que nos da un tamaño en memoria de 24 bits por píxel. Con esto podemos representar 16.777.216 colores distintos. Sin embargo, estos colores pueden simplificarse utilizando los centroides de los *clusters* resultantes del proceso de agrupamiento. Formalmente esto se denomina *cuantization de información*. \n",
    " - **Segmentación de la imagen**. En aplicaciones de identificación de objetos en imágenes se suele utilizar el agrupamiento para simplificar la tarea de reconocimiento, reduciendo el número de colores y realzando la diferencia entre ellos. \n",
    " - **Representación de imágenes en dispositivos sencillos**. Aunque cada día las pantallas de dispositivos que permiten representación de colores reales están muy extendidas, existen muchos casos en que la pantalla del dispositivo sólo permite representar una cantidad reducid de profundidad de bits por pixels. En estos casos se utiliza el agrupamiento para *simplificar* la imagen.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejemplo de cuantización de información"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# -*- coding: utf-8 -*-\n",
    "\"\"\"\n",
    "==================================\n",
    "Color Quantization using K-Means\n",
    "==================================\n",
    "\n",
    "Performs a pixel-wise Vector Quantization (VQ) of an image of the summer palace\n",
    "(China), reducing the number of colors required to show the image from 96,615\n",
    "unique colors to 64, while preserving the overall appearance quality.\n",
    "\n",
    "In this example, pixels are represented in a 3D-space and K-means is used to\n",
    "find 64 color clusters. In the image processing literature, the codebook\n",
    "obtained from K-means (the cluster centers) is called the color palette. Using\n",
    "a single byte, up to 256 colors can be addressed, whereas an RGB encoding\n",
    "requires 3 bytes per pixel. The GIF file format, for example, uses such a\n",
    "palette.\n",
    "\n",
    "For comparison, a quantized image using a random codebook (colors picked up\n",
    "randomly) is also shown.\n",
    "\"\"\"\n",
    "# Authors: Robert Layton <robertlayton@gmail.com>\n",
    "#          Olivier Grisel <olivier.grisel@ensta.org>\n",
    "#          Mathieu Blondel <mathieu@mblondel.org>\n",
    "#\n",
    "# License: BSD 3 clause\n",
    "\n",
    "print(__doc__)\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from sklearn.cluster import KMeans\n",
    "from sklearn.metrics import pairwise_distances_argmin\n",
    "from sklearn.datasets import load_sample_image\n",
    "from sklearn.utils import shuffle\n",
    "from time import time\n",
    "\n",
    "n_colors = 64\n",
    "\n",
    "# Load the Summer Palace photo\n",
    "china = load_sample_image(\"china.jpg\")\n",
    "\n",
    "# Convert to floats instead of the default 8 bits integer coding. Dividing by\n",
    "# 255 is important so that plt.imshow behaves works well on float data (need to\n",
    "# be in the range [0-1])\n",
    "china = np.array(china, dtype=np.float64) / 255\n",
    "\n",
    "# Load Image and transform to a 2D numpy array.\n",
    "w, h, d = original_shape = tuple(china.shape)\n",
    "assert d == 3\n",
    "image_array = np.reshape(china, (w * h, d))\n",
    "\n",
    "print(\"Fitting model on a small sub-sample of the data\")\n",
    "t0 = time()\n",
    "image_array_sample = shuffle(image_array, random_state=0)[:1000]\n",
    "kmeans = KMeans(n_clusters=n_colors, random_state=0).fit(image_array_sample)\n",
    "print(\"done in %0.3fs.\" % (time() - t0))\n",
    "\n",
    "# Get labels for all points\n",
    "print(\"Predicting color indices on the full image (k-means)\")\n",
    "t0 = time()\n",
    "labels = kmeans.predict(image_array)\n",
    "print(\"done in %0.3fs.\" % (time() - t0))\n",
    "\n",
    "\n",
    "codebook_random = shuffle(image_array, random_state=0)[:n_colors + 1]\n",
    "print(\"Predicting color indices on the full image (random)\")\n",
    "t0 = time()\n",
    "labels_random = pairwise_distances_argmin(codebook_random,\n",
    "                                          image_array,\n",
    "                                          axis=0)\n",
    "print(\"done in %0.3fs.\" % (time() - t0))\n",
    "\n",
    "\n",
    "def recreate_image(codebook, labels, w, h):\n",
    "    \"\"\"Recreate the (compressed) image from the code book & labels\"\"\"\n",
    "    d = codebook.shape[1]\n",
    "    image = np.zeros((w, h, d))\n",
    "    label_idx = 0\n",
    "    for i in range(w):\n",
    "        for j in range(h):\n",
    "            image[i][j] = codebook[labels[label_idx]]\n",
    "            label_idx += 1\n",
    "    return image\n",
    "\n",
    "# Display all results, alongside original image\n",
    "plt.figure(1)\n",
    "plt.clf()\n",
    "ax = plt.axes([0, 0, 1, 1])\n",
    "plt.axis('off')\n",
    "plt.title('Original image (96,615 colors)')\n",
    "plt.imshow(china)\n",
    "\n",
    "plt.figure(2)\n",
    "plt.clf()\n",
    "ax = plt.axes([0, 0, 1, 1])\n",
    "plt.axis('off')\n",
    "plt.title('Quantized image (64 colors, K-Means)')\n",
    "plt.imshow(recreate_image(kmeans.cluster_centers_, labels, w, h))\n",
    "\n",
    "plt.figure(3)\n",
    "plt.clf()\n",
    "ax = plt.axes([0, 0, 1, 1])\n",
    "plt.axis('off')\n",
    "plt.title('Quantized image (64 colors, Random)')\n",
    "plt.imshow(recreate_image(codebook_random, labels_random, w, h))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "celltoolbar": "Raw Cell Format",
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}