{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "private_outputs": true, "provenance": [] }, "kernelspec": { "name": "python3", "display_name": "Python 3" }, "accelerator": "GPU", "gpuClass": "standard" }, "cells": [ { "cell_type": "markdown", "metadata": { "id": "tlPTnIRCowvr" }, "source": [ "# Aprendizaje Automático para Datos en Grafos - Laboratorio 3\n", "## Introducción a modelos generativos, representation learning y detección de comunidades.\n", "\n", "En este laboratorio trataremos de ganar cierta intuición de algunos modelos clásicos para grafos no dirigidos y sin pesos. En particular el **Erdös-Rényi** (ER), **Stochastic Block Models** (SBM) y el más general **Random Dot Product Graph** (RDPG). Este último es lo que se denomina un modelo de *posiciones latentes*, donde cada nodo $i=1,\\ldots,n$ tendrá asociado un cierto vector $\\mathbf{x}_i\\in\\mathbb{R}^d$ y la probabilidad de que un par de nodos $i$ y $j$ estén conectados es una cierta función $\\kappa(\\mathbf{x}_i,\\mathbf{x}_j)$. En el caso particular del RDPG, esta función es el producto interno $\\langle\\mathbf{x}_i,\\mathbf{x}_j\\rangle$.\n", "\n", "Lo anterior es un caso particular de **embeddings de nodos**. Es decir, cada nodo se representa con un vector de dimensión $d\\ll n$, a partir de los cuales, en cierto sentido, se puede \"recuperar\" el grafo. Para ser más precisos, en un RDPG si $\\mathbf{X}\\in\\mathbb{R}^{n\\times d}$ son los vectores fila $\\mathbf{x}_i^\\top$ apilados, entonces se cumple que, entre todas las matrices de rango $d$ semi-definidas positivas, $\\mathbf{X}\\mathbf{X}^T$ minimiza $||\\mathbf{A}-\\mathbf{X}\\mathbf{X}^T||^2_F$ (siendo $\\mathbf{A}$ la matriz de adyacencia del grafo). Observar que la matriz $\\mathbf{X}\\mathbf{X}^T$ contiene en la entrada $(i,j)$ el producto interno entre las posiciones latentes de los nodos $i$ y $j$. Lo que se busca con la minimización entonces es encontrar estas posiciones latentes, de forma que las conexiones observadas en $\\mathbf{A}$ sean bien aproximadas por los productos internos correspondientes.\n", "\n", "Si cada nodo queda representado con un vector, entonces es natural realizar clustering a partir de esta representación. En particular, usaremos el modelo RDPG para **detectar comunidades** en un grafo. Además de networkx, usaremos **graspologic**, una biblioteca específica para RDPG (https://microsoft.github.io/graspologic/latest/index.html)." ] }, { "cell_type": "code", "metadata": { "id": "nUf3lCGjonWp" }, "source": [ "# Instalo graspologic\n", "!pip install graspologic" ], "execution_count": null, "outputs": [] }, { "cell_type": "code", "metadata": { "id": "ST0-W-kzz1_V" }, "source": [ "# importamos algunas bibliotecas que vamos a usar\n", "import networkx as nx\n", "import graspologic as gp\n", "import matplotlib.pyplot as plt\n", "import seaborn as sns\n", "import pandas as pd\n", "import numpy as np\n", "from sklearn.manifold import TSNE\n", "\n" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "1cOmfDZU2Kja" }, "source": [ "## Grafos Erdös-Rényi\n", "\n", "Los grafos aleatorios ER son quizá lo más sencillos de especificar. Cada par de nodos está conectado con una cierta probabilidad $p$, independiente para todos los pares de nodos.\n", "\n", "La siguiente celda genera un ER con cierta cantidad de nodos `n` y probabilidad de conexión `p` y dibuja el grafo resultante.\n", "1. Verifique que a partir de cierto valor de $p$ (que a su vez dependerá de $n$) el grafo es conexo." ] }, { "cell_type": "code", "metadata": { "id": "f9lm6j8t3Q8D" }, "source": [ "n = 200\n", "p = 0.05\n", "\n", "# genero el grafo\n", "G_er = nx.generators.random_graphs.erdos_renyi_graph(n=n,p=p)\n", "\n", "# lo dibujo\n", "plt.figure(figsize=(20,10))\n", "nx.draw_networkx(G_er)\n", "plt.show()\n", "# y también ploteo su matriz de adyacencia\n", "sns.heatmap(nx.to_numpy_array(G_er), cmap='Greys')\n", "plt.title('Matriz de adyacencia de G_er')" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "u2NrgapBciTP" }, "source": [ "## Grafos Stochastic Block Model\n", "\n", "Aunque es un objeto matemáticamente muy interesante (con efectos de transición de fase como el que vimos recién) está claro que el modelo ER es un tanto básico y no incluye varias de las características de grafos \"reales\". En particular, en lo que respecta a este laboratorio, no se forman comunidades entre nodos.\n", "\n", "El modelo más clásico para incluir estos fenómenos es el SBM y sus variantes. En su formulación más sencilla cada nodo pertenece a una de $C$ comunidades y la existencia de una arista entre un par de nodos es un evento independiente del resto de las aristas y de probabilidad $\\mathbf{Q}_{c_i,c_j}$ (donde $\\mathbf{Q}\\in\\mathbb{R}^{C\\times C}$ es una cierta matriz de probabilidad y $c_i$,$c_j$ son las comunidades de los nodos $i$,$j$ respectivamente).\n", "\n", "La siguiente celda genera un grafo con un par de comunidades. Entre nodos de la misma comunidad la conexión es bastante fuerte, y la conectividad es bastante baja entre nodos de distintas comunidades. Jugue un poco con los dos parámetros disponibles: `n` y `Q`.\n", "\n", "2. Usando dos comunidades para simplificar la visualización ¿qué diferencia cualitativa hay entre el caso que `Q` tenga todos los valores propios positivos y cuando algunos valores propios son negativos?\n", "3. En particular, use los siguientes parámetros `n=[45, 5, 45, 5]` y $Q = \\left( \\begin{smallmatrix}0.05 & 0.9 & 0 & 0\\\\ 0.9 & 0.8& 0 & 0.5 \\\\ 0 & 0& 0.05 & 0.9 \\\\ 0& 0.5& 0.9 & 0.9\\end{smallmatrix}\\right)$. ¿Cuántas comunidades hay?" ] }, { "cell_type": "code", "metadata": { "id": "pHP8SYF5fhOq" }, "source": [ "n = [50, 50]\n", "# atención que Q tiene que ser simétrico en este caso que vamos a generar grafos simétricos\n", "Q = [[0.4, 0.05],\n", " [0.05, 0.3]]\n", "\n", "# calculo e imprimo los valores propios para chequear y no hacer macanas...\n", "w = np.linalg.eigvals(Q)\n", "print(\"Valores propios de Q: \"+str(w))\n", "\n", "# y hago lo mismo que en la celda anterior.\n", "G_sbm = nx.stochastic_block_model(sizes=n, p=Q)\n", "\n", "plt.figure(figsize=(20,10))\n", "nx.draw_networkx(G_sbm)\n", "plt.show()\n", "sns.heatmap(nx.to_numpy_array(G_sbm), cmap='Greys')\n", "plt.title('Matriz de adyacencia de G_sbm')" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "MIJXk4MlpwOv" }, "source": [ "## Grafos Random Dot-Product Graph: definición\n", "\n", "El modelo RDPG (y sus variantes) es relativamente nuevo y como veremos es una generalización del SBM (y por lo tanto del ER). De todas formas, sigue siendo un modelo donde la existencia de cada arista es independiente del resto. Definamos entonces la matriz $\\mathbf{P}\\in\\mathbb{R}^{n\\times n}$, donde la entrada $\\mathbf{P}_{i,j}$ indica la probabilidad de la existencia de una arista entre los nodos $i,j$ (donde ignoraremos la diagonal). Como comentamos en la introducción, cada nodo $i=1,\\ldots,n$ tendrá asociado un vector $\\mathbf{x}_i\\in\\mathbb{R}^d$ y la probabilidad de que un par de nodos $i$ y $j$ estén conectados es el producto interno $\\langle\\mathbf{x}_i,\\mathbf{x}_j\\rangle$. De forma compacta, si $\\mathbf{X}\\in\\mathbb{R}^{n\\times d}$ son los vectores fila $\\mathbf{x}_i^\\top$ apilados, entonces $\\mathbf{P}=\\mathbf{X}\\mathbf{X}^\\top$.\n", "\n", "4. ¿Cómo se puede generar un grafo ER con probabilidad $p$ a partir de un RDPG? Dicho de otra forma, ¿cuánto valdrían los $\\mathbf{x}_i$ para un grafo ER de parámetro $p$?\n", "5. ¿Y un grafo SBM? ¿Cómo haría detección de comunidades usando el modelo RDPG?\n", "6. ¿Se puede generar cualquier grafo SBM? Por ejemplo, ¿el de la pregunta 3? Pruebe que bajo el modelo RDPG $\\mathbf{P}$ debe ser semidefinida positiva, algo que no cumple la $\\mathbf{P}$ de la pregunta 3. El siguiente artículo discute este problema y su (relativamente sencilla) solución: https://arxiv.org/abs/1709.05506." ] }, { "cell_type": "markdown", "metadata": { "id": "csa6Tx_kyGmP" }, "source": [ "## Grafos Random Dot-Product Graph: inferencia\n", "\n", "La aplicación que nos interesa en este caso es detectar comunidades dentro de un grafo. Por lo tanto, dado un grafo $G$ y su matriz de adyacencia $\\mathbf{A}$, nos enfocamos ahora en cómo estimar la matriz $\\mathbf{X}$. Dado que $\\mathbb{E}[\\mathbf{A}]=\\mathbf{P}=\\mathbf{X}\\mathbf{X}^\\top$, intuitivamente tiene sentido hallar la mejor aproximación de rango $d$ de la matriz $\\mathbf{A}$.\n", "\n", "Por lo tanto, la estimación $\\hat{\\mathbf{X}}$ se hallaría resolviendo\n", "> $$\\hat{\\mathbf{X}}=\\underset{\\mathbf{X}: \\text{ rango} (\\mathbf{X}\\mathbf{X}^\\top)=d}{\\mathrm{argmin}}||\\mathbf{A}-\\mathbf{X}\\mathbf{X}^\\top||^2_F.$$\n", "\n", "La solución de este problema es relativamente sencilla. Dado que $\\mathbf{A}$ es simétrica y real, tiene una descomposición espectral de la forma $\\mathbf{A}=\\mathbf{Q}\\boldsymbol{\\Lambda}\\mathbf{Q}^\\top$. La mejor aproximación de rango $d$ de la matriz $\\mathbf{A}$ se puede encontrar ordenando los valores propios por magnitud y usando solo los $d$ mayores. Sea $\\hat{\\mathbf{Q}}$ y $\\hat{\\mathbf{\\Lambda}}$ el correspondiente \"recorte\":\n", "> $$\\mathbf{A} \\approx \\hat{\\mathbf{Q}}\\hat{\\boldsymbol\\Lambda}\\hat{\\mathbf{Q}}^\\top=\\hat{\\mathbf{Q}}\\sqrt{\\hat{\\boldsymbol\\Lambda}}\\sqrt{\\hat{\\boldsymbol\\Lambda}}\\hat{\\mathbf{Q}}^\\top=\\hat{\\mathbf{Q}}\\sqrt{\\hat{\\boldsymbol\\Lambda}}\\left(\\hat{\\mathbf{Q}}\\sqrt{\\hat{\\boldsymbol\\Lambda}}\\right)^\\top=\\hat{\\mathbf{X}}\\hat{\\mathbf{X}}^\\top.$$\n", "\n", "La expresión anterior explicita la necesidad de que los $d$ mayores (en valor absoluto) valores propios de $\\mathbf{A}$ sean positivos.\n", "\n", "### Usando `graspologic` y ganando intuición con grafos ER.\n", "\n", "Para hallar esta descomposición (y en particular estimar $d$) vamos a usar la biblioteca `graspologic`. La siguiente celda usa el grafo `G_er` generado antes y estima la matriz de las posiciones latentes.\n", "\n", "7. ¿Cómo cambia la precisión de las estimaciones de los $\\mathbf{x}_i$ a medida que varía $p$ y $n$?\n", "8. ¿Y la del producto $\\hat{\\mathbf{X}}\\hat{\\mathbf{X}}^\\top$?\n", "9. La celda también grafica los valores propios de la matriz de adyacencia ordenados por su valor absoluto. ¿Cómo estimaría $d$ a partir de esta gráfica?\n", "\n", "En vez de usar el parámetro `n_components` en el constructor `gp.embed.AdjacencySpectralEmbed`, use el parámetro `n_elbows=1`. Lea la documentación de la función y verifique que se obtiene lo esperado." ] }, { "cell_type": "code", "metadata": { "id": "2yPIHQcL46Vs" }, "source": [ "#####################################\n", "# algunos ejemplos usando grafos ER\n", "#####################################\n", "\n", "# repito el código de generación del grafo por comodidad en las pruebas\n", "n = 200\n", "p = 0.05\n", "G_er = nx.generators.random_graphs.erdos_renyi_graph(n=n,p=p)\n", "\n", "# armo el objeto que estimará el embedding con dimensión d=1 (porque ya sé)\n", "ase = gp.embed.AdjacencySpectralEmbed(n_components=1)\n", "\n", "Xhat = ase.fit_transform(G_er)\n", "\n", "plt.figure()\n", "sns.histplot(Xhat, bins=15)\n", "plt.title('Histograma de los valores del X estimado')\n", "plt.figure()\n", "sns.heatmap(Xhat@Xhat.T, cmap='Greys')\n", "plt.title('El producto XX^T')\n", "plt.figure()\n", "\n", "# calculo los valores propios de A y los ordeno por magnitud (y en caso de empate, por signo).\n", "w = np.linalg.eigvals(nx.to_numpy_array(G_er))\n", "wabs = np.array(list(zip(-np.abs(w), -np.sign(np.real(w)))), dtype=[('abs', 'f4'), ('sign', 'i4')])\n", "w = w[np.argsort(wabs,order=['abs','sign'])]\n", "plt.plot(w,'x-', color='blue')\n", "plt.plot(np.abs(w),'x-', color='red')\n", "plt.title('(Valor absoluto de los) valores propios de la matriz A\\n Ordenados por magnitud')\n", "plt.grid()\n", "\n" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "--p2As8yETpy" }, "source": [ "### Ganando intuición usando grafos SBM\n", "\n", "La siguiente celda repite los experimentos anteriores pero para un grafo SBM. En este caso la dimensión del embedding será mayor a 1, por lo que se graficarán los puntos correspondientes a las dos primeras dimensiones en vez del histograma. Verifique que su repuesta a la pregunta 5 debería funcionar.\n", "\n", "10. Dados dos nodos $i,j$, ¿qué representa el ángulo entre $\\mathbf{x}_i$ y $\\mathbf{x}_j$ respecto a su probabilidad de conexión?\n", "11. ¿Y la magnitud de $\\mathbf{x}_i$?" ] }, { "cell_type": "code", "metadata": { "id": "MFyVrzINE3IK" }, "source": [ "#####################################\n", "# algunos ejemplos usando grafos SBM\n", "#####################################\n", "\n", "# repito el código de generación del grafo por comodidad en las pruebas\n", "n = [100, 100]\n", "Q = [[0.8, 0.05],\n", " [0.05, 0.3]]\n", "G_sbm = nx.stochastic_block_model(sizes=n, p=Q)\n", "\n", "# armo el objeto que estimará el embedding con dimensión n_elbows=2 (valor por defecto)\n", "ase = gp.embed.AdjacencySpectralEmbed(n_elbows=2)\n", "\n", "Xhat = ase.fit_transform(G_sbm)\n", "\n", "plt.figure()\n", "fig, ax = plt.subplots(subplot_kw={'projection': 'polar'})\n", "complejo = Xhat[:,0]+1j*Xhat[:,1]\n", "ax.scatter(np.angle(complejo),np.abs(complejo))\n", "plt.title('Gráfica polar de los valores del X estimado')\n", "plt.figure()\n", "sns.heatmap(Xhat@Xhat.T, cmap='Greys')\n", "plt.title('El producto XX^T')\n", "plt.figure()\n", "\n", "# calculo los valores propios de A y los ordeno por magnitud (y en caso de empate, por signo).\n", "w = np.linalg.eigvals(nx.to_numpy_array(G_sbm))\n", "wabs = np.array(list(zip(-np.abs(w), -np.sign(np.real(w)))), dtype=[('abs', 'f4'), ('sign', 'i4')])\n", "w = w[np.argsort(wabs,order=['abs','sign'])]\n", "plt.plot(w,'x-', color='blue')\n", "plt.plot(np.abs(w),'x-', color='red')\n", "plt.title('(Valor absoluto de los) valores propios de la matriz A\\n Ordenados por magnitud')\n", "plt.grid()" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "sNSj2-WvJUS1" }, "source": [ "## Clustering usando RDPG\n", "\n", "Finalmente podemos hacer detección de comunidades. Como ya contestó en la pregunta 5, debería ser tan fácil como usar algún algoritmo de clustering en los vectores $\\mathbf{x}_i$. Al menos en el caso SBM debería funcionar. Sobre cuál algoritmo de clustering usar, el esquema clásico es usar k-means. Sin embargo, las formas obtenidas en los ejemplos anteriores le debería dar la pauta de que k-means puede equivocarse al agrupar y sería mejor usar una técnica como Gaussian Mixture Model (GMM), donde cada cluster tiene forma de elipse.\n", "\n", "Afortunadamente para nosotros, la biblioteca `graspologic` tiene métodos para estimar automáticamente los hiperparámetros del método GMM. La celda de abajo usa la biblioteca para el grafo SBM generado antes, y colorea los nodos en función de la comunidad estimada. Juegue con los parámetros y los grafos usados.\n", "\n", "12. ¿Para qué parámetros es particularmente difícil de detectar las comunidades?" ] }, { "cell_type": "code", "metadata": { "id": "Eud0aG23Kgr1" }, "source": [ "#####################################\n", "# algunos ejemplos usando grafos SBM\n", "#####################################\n", "\n", "# repito el código de generación del grafo por comodidad en las pruebas.\n", "# Sería interesante ver qué pasa con el grafo de la pregunta 3\n", "n = [100, 100]\n", "Q = [[0.8, 0.05],\n", " [0.05, 0.3]]\n", "G_sbm = nx.stochastic_block_model(sizes=n, p=Q)\n", "ase = gp.embed.AdjacencySpectralEmbed(n_elbows=2)\n", "Xhat = ase.fit_transform(G_sbm)\n", "\n", "# el algoritmo de clustering será entonces GMM\n", "# se puede probar cambiar el máximo y mínimo número de clusters a ver qué pasa.\n", "cluster_algo = gp.cluster.AutoGMMCluster(min_components=2, max_components=5)\n", "clusters_hat = cluster_algo.fit_predict(Xhat)\n", "print(print(\"Número de clusters: \"+str(np.max(clusters_hat)-np.min(clusters_hat)+1)))\n", "\n", "# ahora dibujo el grafo como siempre, pero cambiando el color de los nodos en función de la comunidad estimada\n", "plt.figure(figsize=(20,10))\n", "posfijas_layout = nx.spring_layout(G_sbm)\n", "nx.draw_networkx(G_sbm,posfijas_layout,node_color=clusters_hat)\n", "\n", "fig, ax = plt.subplots(subplot_kw={'projection': 'polar'},figsize=(10,10))\n", "complejo = Xhat[:,0]+1j*Xhat[:,1]\n", "ax.scatter(np.angle(complejo),np.abs(complejo), c=clusters_hat)\n", "plt.title('Gráfica polar de los valores del X estimado')\n", "plt.figure()\n" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "zbWerHiTN9eN" }, "source": [ "### Detectando comunidades en un ejemplo real\n", "\n", "Ahora sí, un grafo real. Vamos a considerar los partidos jugados entre las selecciones de fútbol durante un año. Cada nodo del vector será una selección y habrá una arista cuando esos dos equipos jugaron al menos una vez en el año en cuestión. Primero vamos a armar el grafo (naturalmente usando `pandas`) y después calcular el embedding. El año se elige como variable." ] }, { "cell_type": "code", "source": [ "# Cambio codificación a UTF-8 porque si no Colab da error\n", "# Ver: https://github.com/googlecolab/colabtools/issues/3409\n", "import locale\n", "locale.getpreferredencoding = lambda: \"UTF-8\"" ], "metadata": { "id": "ropX5Zoa5LmO" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "metadata": { "id": "rGDfycC8N9I_" }, "source": [ "# Bajamos los archivos necesarios. Lo dejo en una celda aparte para no repetir la bajada cada vez.\n", "!wget -O AllMatches.csv https://www.fing.edu.uy/owncloud/index.php/s/V2tk4MxZxAvNidx/download\n", "!wget -O codigos_paises_corregido.csv https://www.fing.edu.uy/owncloud/index.php/s/gb7SIbuUzVOgQJj/download\n", "!wget -O world.jpg https://www.fing.edu.uy/owncloud/index.php/s/ABbYDE4nR4T3qvx/download\n", "\n", "df_matches = pd.read_csv('AllMatches.csv')\n", "df_matches['anio'] = pd.to_datetime(df_matches.Date,format='%m/%d/%Y').dt.year\n", "df_matches.head()" ], "execution_count": null, "outputs": [] }, { "cell_type": "code", "metadata": { "id": "HSjIPEJ0Qd9d" }, "source": [ "anio = 2015\n", "df_matches_recortado = df_matches[df_matches.anio==anio]\n", "\n", "# voy a contar cuántos partidos hubo entre las selecciones, sin importar dónde se jugó ni quién fue local.\n", "ordered_matches = pd.DataFrame(df_matches_recortado[['HomeTeam','AwayTeam']].apply(lambda x: sorted([x['HomeTeam'],x['AwayTeam']]),axis=1).tolist())\n", "ordered_matches.columns = ['team1','team2']\n", "num_matchs = ordered_matches.groupby(['team1','team2']).size().reset_index()\n", "num_matchs.columns = ['team1','team2','weight']\n", "\n", "# voy a armar dos versiones del grafo: uno con pesos (la cantidad de partidos) y otro sin\n", "G_sin_pesos = nx.from_pandas_edgelist(num_matchs,source='team1',target='team2',create_using=nx.Graph())\n", "G_con_pesos = nx.from_pandas_edgelist(num_matchs,source='team1',target='team2',edge_attr='weight',create_using=nx.Graph())\n", "\n", "# me quedo con la componente conexa. No tiene sentido detectar comunidades en un grafo disconexo.\n", "G_sin_pesos = gp.utils.largest_connected_component(G_sin_pesos)\n", "G_con_pesos = gp.utils.largest_connected_component(G_con_pesos)\n", "\n", "# hago el embedding\n", "ase = gp.embed.AdjacencySpectralEmbed(n_elbows = 2)\n", "# CUIDADO: lo mejor es pasarle un array al embedder de graspologic.\n", "# Sino el orden de los nodos a veces no se respeta.\n", "Xhat_con_pesos = ase.fit_transform(nx.to_numpy_array(G_con_pesos))\n", "Xhat_sin_pesos = ase.fit_transform(nx.to_numpy_array(G_sin_pesos))\n", "\n", "# calculo los valores propios de A y los ordeno por magnitud (y en caso de empate, por signo).\n", "w = np.linalg.eigvals(nx.to_numpy_array(G_con_pesos))\n", "wabs = np.array(list(zip(-np.abs(w), -np.sign(np.real(w)))), dtype=[('abs', 'f4'), ('sign', 'i4')])\n", "w = w[np.argsort(wabs,order=['abs','sign'])]\n", "plt.plot(w,'x-', color='blue')\n", "plt.plot(np.abs(w),'x-', color='red')\n", "plt.title('(Valor absoluto de los) valores propios de la matriz con pesos\\n Ordenados por magnitud')\n", "plt.grid()\n", "\n", "w = np.linalg.eigvals(nx.to_numpy_array(G_sin_pesos))\n", "wabs = np.array(list(zip(-np.abs(w), -np.sign(np.real(w)))), dtype=[('abs', 'f4'), ('sign', 'i4')])\n", "w = w[np.argsort(wabs,order=['abs','sign'])]\n", "plt.figure()\n", "plt.plot(w,'x-', color='blue')\n", "plt.plot(np.abs(w),'x-', color='red')\n", "plt.title('(Valor absoluto de los) valores propios de la matriz sin pesos\\n Ordenados por magnitud')\n", "plt.grid()\n", "\n", "print(\"Dimensiones elegidas (con pesos): \"+str(Xhat_con_pesos.shape[1]))\n", "print(\"Dimensiones elegidas (sin pesos): \"+str(Xhat_sin_pesos.shape[1]))\n" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "DR-LeL4nOpok" }, "source": [ "Ahora vamos a calcular el clustering de las selecciones. Para hacernos una idea de qué esperar, y como no podemos dibujar un vector de dimensión>3, vamos a usar el método [T-distributed stochastic neighbor embedding](https://en.wikipedia.org/wiki/T-distributed_stochastic_neighbor_embedding) (TSNE) para reducir su dimensión y plotear los $\\hat{\\mathbf{x}}_i$ en el plano. La idea es obtener una visualización donde vectores similares están cerca.\n", "\n", "13. De la visualización debería estar claro que el grafo con pesos se podrá agrupar más \"fácilmente\". ¿Porqué cree que sucede esto?" ] }, { "cell_type": "code", "metadata": { "id": "rqykwr-8OpEt" }, "source": [ "Xtsne_con = TSNE(n_components=2).fit_transform(Xhat_con_pesos)\n", "plt.figure()\n", "plt.scatter(Xtsne_con[:, 0],Xtsne_con[:, 1], s=40);\n", "plt.grid()\n", "plt.title('TSNE para el embedding del grafo con pesos')\n", "\n", "Xtsne_sin = TSNE(n_components=2).fit_transform(Xhat_sin_pesos)\n", "plt.figure()\n", "plt.scatter(Xtsne_sin[:, 0],Xtsne_sin[:, 1], s=40);\n", "plt.grid()\n", "plt.title('TSNE para el embedding del grafo sin pesos')\n", "\n" ], "execution_count": null, "outputs": [] }, { "cell_type": "code", "metadata": { "id": "920xnI0IQtv_" }, "source": [ "###############################################\n", "# Ahora sí, a calcular y dibujar el clustering!\n", "###############################################\n", "cluster_algo = gp.cluster.AutoGMMCluster(min_components=1, max_components=6)\n", "\n", "clusters_hat_con_pesos = cluster_algo.fit_predict(Xhat_con_pesos)\n", "clusters_hat_sin_pesos = cluster_algo.fit_predict(Xhat_sin_pesos)\n", "\n", "# empecemos dibujando el grafo con los colores de cada comunidad detectada en los nodos y el TSNE para ver si cierra con lo anterior\n", "plt.figure(figsize=(20,10))\n", "nx.draw_networkx(G_con_pesos,node_color=clusters_hat_con_pesos, with_labels=True)\n", "plt.title('Clustering para el grafo con pesos')\n", "plt.figure()\n", "plt.scatter(Xtsne_con[:, 0],Xtsne_con[:, 1], c=clusters_hat_con_pesos, s=40, cmap='viridis');\n", "plt.grid()\n", "plt.title('TSNE para el embedding del grafo con pesos')\n", "\n", "plt.figure(figsize=(20,10))\n", "nx.draw_networkx(G_sin_pesos,node_color=clusters_hat_sin_pesos, with_labels=True)\n", "plt.title('Clustering para el grafo sin pesos')\n", "plt.figure()\n", "plt.scatter(Xtsne_sin[:, 0],Xtsne_sin[:, 1], c=clusters_hat_sin_pesos, s=40, cmap='viridis');\n", "plt.grid()\n", "plt.title('TSNE para el embedding del grafo sin pesos')\n" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "_GmQBgboYnLl" }, "source": [ "### Finalmente, algo más vistoso para dibujar el grafo: en un mapa!\n", "\n", "Siéntase libre de probar distintos años y tratar de explicar las comunidades detectadas por el algoritmo, tanto en el grafo con o sin pesos.\n" ] }, { "cell_type": "code", "metadata": { "id": "CwdwH8ONVUg2" }, "source": [ "codigos = pd.read_csv('codigos_paises_corregido.csv')\n", "# la tabla tiene las coordenadas de las capitales de los países.\n", "xrange = (np.min(codigos.Capitallongitude),np.max(codigos.Capitallongitude))\n", "yrange = (np.min(codigos.Capitallatitude),np.max(codigos.Capitallatitude))\n", "\n", "# en el mapa que voy a usar, algunos países de oceanía están con una longitud distinta de mi tabla. Los corrijo:\n", "codigos.loc[codigos.Capitallongitude<-170,'Capitallongitude']=codigos.loc[codigos.Capitallongitude<-170,'Capitallongitude'] + 170+189\n", "\n", "# para fijar las posiciones de los nodos en un grafo, necesito armar un diccionario\n", "# con key el nombre del nodo (en este caso el pais), y valor un array de dos elementos.\n", "posix = codigos.set_index('Countryname')[['Capitallongitude','Capitallatitude']]\n", "posix['arrays'] = list(posix.values)\n", "posfijas = posix['arrays'].to_dict()\n", "\n", "plt.figure(figsize=(20,20))\n", "img = plt.imread(\"world.jpg\")\n", "plt.imshow(img, extent=[xrange[0]+3, xrange[1]+15, yrange[0]-38, yrange[1]+30])\n", "nx.draw_networkx_nodes(G_con_pesos,posfijas,node_color=clusters_hat_con_pesos)\n", "nx.draw_networkx_edges(G_con_pesos,posfijas,edge_color='grey')\n", "plt.title('Clustering para el grafo con pesos')\n", "\n", "plt.figure(figsize=(20,20))\n", "img = plt.imread(\"world.jpg\")\n", "plt.imshow(img, extent=[xrange[0]+3, xrange[1]+15, yrange[0]-38, yrange[1]+30])\n", "nx.draw_networkx_nodes(G_sin_pesos,posfijas,node_color=clusters_hat_sin_pesos)\n", "nx.draw_networkx_edges(G_sin_pesos,posfijas,edge_color='grey')\n", "plt.title('Clustering para el grafo sin pesos')" ], "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [], "metadata": { "id": "g2mgxmKNKgf7" }, "execution_count": null, "outputs": [] } ] }