tutorials/03_graph_from_features.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [NTDS'19] tutorial 3: build a graph from features\n",
    "[ntds'19]: https://github.com/mdeff/ntds_2019\n",
    "\n",
    "[Benjamin Ricaud](https://people.epfl.ch/benjamin.ricaud), [EPFL LTS2](https://lts2.epfl.ch).\n",
    "\n",
    "* Dataset: [Iris](https://archive.ics.uci.edu/ml/datasets/Iris)\n",
    "* Tools: [pandas](https://pandas.pydata.org), [numpy](http://www.numpy.org), [scipy](https://www.scipy.org), [matplotlib](https://matplotlib.org), [networkx](https://networkx.github.io), [gephi](https://gephi.org/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tools"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By convention, the first lines of code are always about importing the packages we'll use."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "from scipy.spatial.distance import pdist, squareform\n",
    "from matplotlib import pyplot as plt\n",
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tutorials on pandas can be found at:\n",
    "* <https://pandas.pydata.org/pandas-docs/stable/10min.html>\n",
    "* <https://pandas.pydata.org/pandas-docs/stable/tutorials.html>\n",
    "\n",
    "Tutorials on numpy can be found at:\n",
    "* <https://docs.scipy.org/doc/numpy/user/quickstart.html>\n",
    "* <http://www.scipy-lectures.org/intro/numpy/index.html>\n",
    "* <http://www.scipy-lectures.org/advanced/advanced_numpy/index.html>\n",
    "\n",
    "A tutorial on networkx can be found at:\n",
    "* <https://networkx.github.io/documentation/stable/tutorial.html>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following line is a [magic command](https://ipython.readthedocs.io/en/stable/interactive/magics.html). It enables plotting inside the notebook."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "# %matplotlib notebook"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Import and explore the data\n",
    "\n",
    "We will play with the famous Iris dataset. This dataset can be found in many places on the net and was first released at <https://archive.ics.uci.edu/ml/index.php>. For example it is stored on [Kaggle](https://www.kaggle.com/uciml/iris/), with many demos and Jupyter notebooks you can test (have a look at the \"kernels\" tab).\n",
    "\n",
    "![Iris Par Za — Travail personnel, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=144395](https://upload.wikimedia.org/wikipedia/commons/thumb/2/27/Iris_germanica_002.jpg/251px-Iris_germanica_002.jpg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "iris = pd.read_csv('data/iris.csv')\n",
    "iris.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The description of the entries is given here:\n",
    "https://www.kaggle.com/uciml/iris/home"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "iris['Species'].unique()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "iris.describe()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Build a graph from the features\n",
    "\n",
    "We are going to build a graph from these data. The idea is to represent iris samples (rows of the table) as nodes, with connections depending on their physical similarity.\n",
    "\n",
    "The main question is how to define the notion of similarity between the flowers. For that, we need to introduce a measure of similarity. It should use the properties of the flowers and provide a positive real value for each pair of samples. \n",
    "\n",
    "*Remark:* The value should increase with the similarity.\n",
    "\n",
    "Let us separate the data into two parts: physical properties and labels."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "features = iris.loc[:, ['SepalLengthCm', 'SepalWidthCm', 'PetalLengthCm', 'PetalWidthCm']]\n",
    "species = iris.loc[:, 'Species']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "features.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "species.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Similarity, distance and edge weight"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can define many similarity measures. One of the most intuitive and perhaps the easiest to program relies on the notion of distance. If a distance between samples is defined, we can compute the weight accordingly: if the distance is short, which means the nodes are similar, we want a strong connection between them (large weight)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Different distances\n",
    "The cosine distance is a good candidate for high-dimensional data. It is defined as follows:\n",
    "$$d(u,v) = 1 - \\frac{u \\cdot v} {\\|u\\|_2 \\|v\\|_2},$$\n",
    "where $u$ and $v$ are two feature vectors.\n",
    " \n",
    "The distance is proportional to the angle formed by the two vectors (0 if colinear, 1 if orthogonal, 2 if opposed direction).\n",
    "\n",
    "Alternatives are the [$p$-norms](https://en.wikipedia.org/wiki/Norm_%28mathematics%29#p-norm) (or $\\ell_p$-norms), defined as\n",
    "$$d(u,v) = \\|u - v\\|_p,$$\n",
    "of which the Euclidean distance is a special case with $p=2$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `pdist` function from `scipy` computes the pairwise distance. By default it is the Euclidian distance. `features.values` is a numpy array extracted from the Pandas dataframe. Very handy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#from scipy.spatial.distance import pdist, squareform\n",
    "pdist?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "distances = pdist(features.values, metric='euclidean')\n",
    "# other metrics: 'cosine', 'cityblock', 'minkowski'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we have a distance, we can compute the weights."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Distance to weights\n",
    "A common function used to turn distances into edge weights is the Gaussian function:\n",
    "$$\\mathbf{W}(u,v) = \\exp \\left( \\frac{-d^2(u, v)}{\\sigma^2} \\right),$$\n",
    "where $\\sigma$ is the parameter which controls the width of the Gaussian.\n",
    "  \n",
    "The function giving the weights should be positive and monotonically decreasing with respect to the distance. It should take its maximum value when the distance is zero, and tend to zero when the distance increases. Note that distances are non-negative by definition. So any funtion $f : \\mathbb{R}^+ \\rightarrow [0,C]$ that verifies $f(0)=C$ and $\\lim_{x \\rightarrow +\\infty}f(x)=0$ and is *strictly* decreasing should be adapted. The choice of the function depends on the data.\n",
    "\n",
    "Some examples:\n",
    "* A simple linear function $\\mathbf{W}(u,v) = \\frac{d_{max} - d(u, v)}{d_{max} - d_{min}}$. As the cosine distance is bounded by $[0,2]$, a suitable linear function for it would be $\\mathbf{W}(u,v) = 1 - d(u,v)/2$.\n",
    "* A triangular kernel: a straight line between the points $(0,1)$ and $(t_0,0)$, and equal to 0 after this point.\n",
    "* The logistic kernel $\\left(e^{d(u,v)} + 2 + e^{-d(u,v)} \\right)^{-1}$.\n",
    "* An inverse function $(\\epsilon+d(u,v))^{-n}$, with $n \\in \\mathbb{N}^{+*}$ and $\\epsilon \\in \\mathbb{R}^+$.\n",
    "* You can find some more [here](https://en.wikipedia.org/wiki/Kernel_%28statistics%29).\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let us use the Gaussian function\n",
    "kernel_width = distances.mean()\n",
    "weights_list = np.exp(-distances**2 / kernel_width**2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Turn the list of weights into a matrix.\n",
    "weight_matrix = squareform(weights_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Find the nodes with highest degree and display their respective entry in the `iris` dataframe. Do they belong to the same iris species?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sometimes, you may need to compute additional features before processing them with some machine learning or some other data processing step. With Pandas, it is as simple as that:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Compute a new column using the existing ones.\n",
    "features['SepalLengthSquared'] = features['SepalLengthCm']**2\n",
    "features.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Coming back to the weight matrix, we have obtained a full matrix but we may not need all the connections (reducing the number of connections saves some space and computations!). We can sparsify the graph by removing the values (edges) below some fixed threshold. Let us see what kind of threshold we could use:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.hist(weights_list)\n",
    "plt.title('Distribution of weights')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let us choose a threshold of 0.6.\n",
    "# Too high, we will have disconnected components\n",
    "# Too low, the graph will have too many connections\n",
    "weight_matrix[weight_matrix < 0.6] = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Plot the number of edges with respect to the threshold, for threshold values between 0 and 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Remark:* The distances presented here do not work well for categorical data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graph visualization\n",
    "\n",
    "To conclude, let us visualize the graph. We will use the python module networkx."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# A simple command to create the graph from the adjacency matrix.\n",
    "graph = nx.from_numpy_array(weight_matrix)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us try some direct visualizations using networkx."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let us add some colors\n",
    "colors = species.values\n",
    "colors[colors == 'Iris-setosa'] = 0\n",
    "colors[colors == 'Iris-versicolor'] = 1\n",
    "colors[colors == 'Iris-virginica'] = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw_spectral(graph, node_color=colors)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Oh! It seems to be separated in 3 parts! Are they related to the 3 different species of iris?\n",
    "\n",
    "Let us try another [layout algorithm](https://en.wikipedia.org/wiki/Graph_drawing#Layout_methods), where the edges are modeled as springs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw_spring(graph, node_color=colors)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Save the graph to disk in the `gexf` format, readable by gephi and other tools that manipulate graphs. You may now explore the graph using gephi and compare the visualizations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.write_gexf(graph, 'iris.gexf')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 1:**\n",
    "Modify the experiment such that the distance is computed using normalized features, i.e., all features (columns of `features`) having the same mean and variance.\n",
    "This avoids having some features with too much importance in the computation of distance.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 2 (advanced):**\n",
    "Construct the graph of k-nearest neighbors (choose $k=4$).\n",
    "You may read the [kNN section of scikit-learn](https://scikit-learn.org/stable/modules/neighbors.html) and use this python module."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code here."
   ]
  }
 ],
 "metadata": {
  "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}