3-sparse-matrix.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Representation of Data (for Machine Learning)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Machine learning is about creating models from data: for that reason, we'll start by\n",
    "discussing how data can be represented in order to be understood by the computer.  Along\n",
    "with this, we'll build on our matplotlib examples from the previous section and show some\n",
    "examples of how to visualize data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Data in scikit-learn"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Data in scikit-learn, with very few exceptions, is assumed to be stored as a\n",
    "**two-dimensional array**, of size `[n_samples, n_features]`. \n",
    "This array is usually referrred as the **feature matrix**.\n",
    "\n",
    "There is also the **label vector**, of size `n_samples`, containing the list of labels\n",
    "for each samples (_Note_: **ONLY** in the Supervised Learning settings)\n",
    "\n",
    "$$\n",
    "{\\rm feature~matrix:~~~} {\\bf X}~=~\\left[\n",
    "\\begin{matrix}\n",
    "x_{11} & x_{12} & \\cdots & x_{1D}\\\\\n",
    "x_{21} & x_{22} & \\cdots & x_{2D}\\\\\n",
    "x_{31} & x_{32} & \\cdots & x_{3D}\\\\\n",
    "\\vdots & \\vdots & \\ddots & \\vdots\\\\\n",
    "\\vdots & \\vdots & \\ddots & \\vdots\\\\\n",
    "x_{N1} & x_{N2} & \\cdots & x_{ND}\\\\\n",
    "\\end{matrix}\n",
    "\\right]\n",
    "$$\n",
    "\n",
    "$$\n",
    "{\\rm label~vector:~~~} {\\bf y}~=~ [y_1, y_2, y_3, \\cdots y_N]\n",
    "$$\n",
    "\n",
    "Here there are $N$ samples and $D$ features."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "- $N$ (`n_samples`):   The number of samples: each sample is an item to process (e.g. classify).\n",
    "  A sample can be a document, a picture, a sound, a video, an astronomical object,\n",
    "  a row in database or CSV file,\n",
    "  or whatever you can describe with a fixed set of quantitative traits.\n",
    "- $D$ (`n_features`):  The number of features or distinct traits that can be used to describe each\n",
    "  item in a quantitative manner.  Features are generally real-valued, but may be boolean or\n",
    "  discrete-valued in some cases.\n",
    "\n",
    "The number of features must be fixed in advance. \n",
    "\n",
    "However it can be very high dimensional\n",
    "(e.g. millions of features) with most of them being zeros for a given sample. This is a case\n",
    "where `scipy.sparse` matrices can be useful, in that they are\n",
    "much more memory-efficient than numpy arrays.\n",
    "\n",
    "Each sample (data point) is a row in the data array, and each feature is a column."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Scipy Sparse Matrices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Sparse Matrices** are very nice in some situations.  \n",
    "\n",
    "For example, in some machine learning tasks, especially those associated\n",
    "with textual analysis, the data may be mostly zeros.  \n",
    "\n",
    "Storing all these zeros is very inefficient.  \n",
    "\n",
    "We can create and manipulate sparse matrices as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "np.random.seed(42)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0.37454012 0.95071431 0.73199394 0.59865848 0.15601864]\n",
      " [0.15599452 0.05808361 0.86617615 0.60111501 0.70807258]\n",
      " [0.02058449 0.96990985 0.83244264 0.21233911 0.18182497]\n",
      " [0.18340451 0.30424224 0.52475643 0.43194502 0.29122914]\n",
      " [0.61185289 0.13949386 0.29214465 0.36636184 0.45606998]\n",
      " [0.78517596 0.19967378 0.51423444 0.59241457 0.04645041]\n",
      " [0.60754485 0.17052412 0.06505159 0.94888554 0.96563203]\n",
      " [0.80839735 0.30461377 0.09767211 0.68423303 0.44015249]\n",
      " [0.12203823 0.49517691 0.03438852 0.9093204  0.25877998]\n",
      " [0.66252228 0.31171108 0.52006802 0.54671028 0.18485446]]\n"
     ]
    }
   ],
   "source": [
    "# Create a random array with a lot of zeros\n",
    "X = np.random.random((10, 5))\n",
    "print(X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0.         0.95071431 0.73199394 0.         0.        ]\n",
      " [0.         0.         0.86617615 0.         0.70807258]\n",
      " [0.         0.96990985 0.83244264 0.         0.        ]\n",
      " [0.         0.         0.         0.         0.        ]\n",
      " [0.         0.         0.         0.         0.        ]\n",
      " [0.78517596 0.         0.         0.         0.        ]\n",
      " [0.         0.         0.         0.94888554 0.96563203]\n",
      " [0.80839735 0.         0.         0.         0.        ]\n",
      " [0.         0.         0.         0.9093204  0.        ]\n",
      " [0.         0.         0.         0.         0.        ]]\n"
     ]
    }
   ],
   "source": [
    "X[X < 0.7] = 0\n",
    "print(X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  (0, 1)\t0.9507143064099162\n",
      "  (0, 2)\t0.7319939418114051\n",
      "  (1, 2)\t0.8661761457749352\n",
      "  (1, 4)\t0.7080725777960455\n",
      "  (2, 1)\t0.9699098521619943\n",
      "  (2, 2)\t0.8324426408004217\n",
      "  (5, 0)\t0.7851759613930136\n",
      "  (6, 3)\t0.9488855372533332\n",
      "  (6, 4)\t0.9656320330745594\n",
      "  (7, 0)\t0.8083973481164611\n",
      "  (8, 3)\t0.9093204020787821\n"
     ]
    }
   ],
   "source": [
    "from scipy import sparse\n",
    "\n",
    "# turn X into a csr (Compressed-Sparse-Row) matrix\n",
    "X_csr = sparse.csr_matrix(X)\n",
    "print(X_csr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0.         0.95071431 0.73199394 0.         0.        ]\n",
      " [0.         0.         0.86617615 0.         0.70807258]\n",
      " [0.         0.96990985 0.83244264 0.         0.        ]\n",
      " [0.         0.         0.         0.         0.        ]\n",
      " [0.         0.         0.         0.         0.        ]\n",
      " [0.78517596 0.         0.         0.         0.        ]\n",
      " [0.         0.         0.         0.94888554 0.96563203]\n",
      " [0.80839735 0.         0.         0.         0.        ]\n",
      " [0.         0.         0.         0.9093204  0.        ]\n",
      " [0.         0.         0.         0.         0.        ]]\n"
     ]
    }
   ],
   "source": [
    "# convert the sparse matrix to a dense array\n",
    "print(X_csr.toarray())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Sparse matrices support linear algebra:\n",
    "y = np.random.random(X_csr.shape[1])\n",
    "z1 = X_csr.dot(y)\n",
    "z2 = X.dot(y)\n",
    "np.allclose(z1, z2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "* The CSR representation can be very efficient for computations, but it is not as good for adding elements.  \n",
    "\n",
    "* For that, the **LIL** (List-In-List) representation is better:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  (0, 2)\t2.0\n",
      "  (0, 3)\t3.0\n",
      "  (0, 4)\t4.0\n",
      "  (1, 0)\t1.0\n",
      "  (1, 1)\t2.0\n",
      "  (1, 4)\t5.0\n",
      "  (2, 0)\t2.0\n",
      "  (2, 2)\t4.0\n",
      "  (2, 4)\t6.0\n",
      "  (3, 0)\t3.0\n",
      "  (3, 3)\t6.0\n",
      "  (3, 4)\t7.0\n",
      "  (4, 0)\t4.0\n",
      "  (4, 4)\t8.0\n",
      "[[0. 0. 2. 3. 4.]\n",
      " [1. 2. 0. 0. 5.]\n",
      " [2. 0. 4. 0. 6.]\n",
      " [3. 0. 0. 6. 7.]\n",
      " [4. 0. 0. 0. 8.]]\n"
     ]
    }
   ],
   "source": [
    "# Create an empty LIL matrix and add some items\n",
    "X_lil = sparse.lil_matrix((5, 5))\n",
    "\n",
    "for i, j in np.random.randint(0, 5, (15, 2)):\n",
    "    X_lil[i, j] = i + j\n",
    "\n",
    "print(X_lil)\n",
    "print(X_lil.toarray())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "* Often, once an LIL matrix is created, it is useful to convert it to a CSR format \n",
    "    * **Note**: many scikit-learn algorithms require CSR or CSC format"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  (0, 2)\t2.0\n",
      "  (0, 3)\t3.0\n",
      "  (0, 4)\t4.0\n",
      "  (1, 0)\t1.0\n",
      "  (1, 1)\t2.0\n",
      "  (1, 4)\t5.0\n",
      "  (2, 0)\t2.0\n",
      "  (2, 2)\t4.0\n",
      "  (2, 4)\t6.0\n",
      "  (3, 0)\t3.0\n",
      "  (3, 3)\t6.0\n",
      "  (3, 4)\t7.0\n",
      "  (4, 0)\t4.0\n",
      "  (4, 4)\t8.0\n"
     ]
    }
   ],
   "source": [
    "X_csr = X_lil.tocsr()\n",
    "print(X_csr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "There are several other sparse formats that can be useful for various problems:\n",
    "\n",
    "- `CSC` (compressed sparse column)\n",
    "- `BSR` (block sparse row)\n",
    "- `COO` (coordinate)\n",
    "- `DIA` (diagonal)\n",
    "- `DOK` (dictionary of keys)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## CSC - Compressed Sparse Column\n",
    "\n",
    "**Advantages of the CSC format**\n",
    "\n",
    "    * efficient arithmetic operations CSC + CSC, CSC * CSC, etc.\n",
    "    * efficient column slicing\n",
    "    * fast matrix vector products (CSR, BSR may be faster)\n",
    "\n",
    "**Disadvantages of the CSC format**\n",
    "\n",
    "    * slow row slicing operations (consider CSR)\n",
    "    * changes to the sparsity structure are expensive (consider LIL or DOK)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### BSR - Block Sparse Row\n",
    "\n",
    "The Block Compressed Row (`BSR`) format is very similar to the Compressed Sparse Row (`CSR`) format. \n",
    "\n",
    "BSR is appropriate for sparse matrices with *dense sub matrices* like the example below. \n",
    "\n",
    "Block matrices often arise in *vector-valued* finite element discretizations. \n",
    "\n",
    "In such cases, BSR is **considerably more efficient** than CSR and CSC for many sparse arithmetic operations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1, 1, 0, 0, 2, 2],\n",
       "       [1, 1, 0, 0, 2, 2],\n",
       "       [0, 0, 0, 0, 3, 3],\n",
       "       [0, 0, 0, 0, 3, 3],\n",
       "       [4, 4, 5, 5, 6, 6],\n",
       "       [4, 4, 5, 5, 6, 6]])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from scipy.sparse import bsr_matrix\n",
    "\n",
    "indptr = np.array([0, 2, 3, 6])\n",
    "indices = np.array([0, 2, 2, 0, 1, 2])\n",
    "data = np.array([1, 2, 3, 4, 5, 6]).repeat(4).reshape(6, 2, 2)\n",
    "bsr_matrix((data,indices,indptr), shape=(6, 6)).toarray()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## COO - Coordinate Sparse Matrix\n",
    "\n",
    "**Advantages of the CSC format**\n",
    "\n",
    "    * facilitates fast conversion among sparse formats\n",
    "    * permits duplicate entries (see example)\n",
    "    * very fast conversion to and from CSR/CSC formats\n",
    "\n",
    "**Disadvantages of the CSC format**\n",
    "\n",
    "    * does not directly support arithmetic operations and slicing\n",
    "    \n",
    "** Intended Usage**\n",
    "\n",
    "    * COO is a fast format for constructing sparse matrices\n",
    "    * Once a matrix has been constructed, convert to CSR or CSC format for fast arithmetic and matrix vector\n",
    "    operations\n",
    "    * By default when converting to CSR or CSC format, duplicate (i,j) entries will be summed together. \n",
    "    This facilitates efficient construction of finite element matrices and the like.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## DOK - Dictionary of Keys\n",
    "\n",
    "Sparse matrices can be used in arithmetic operations: they support addition, subtraction, multiplication, division, and matrix power.\n",
    "\n",
    "Allows for efficient O(1) access of individual elements. Duplicates are not allowed. Can be efficiently converted to a coo_matrix once constructed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0., 1., 2., 3., 4.],\n",
       "       [0., 2., 3., 4., 5.],\n",
       "       [0., 0., 4., 5., 6.],\n",
       "       [0., 0., 0., 6., 7.],\n",
       "       [0., 0., 0., 0., 8.]], dtype=float32)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from scipy.sparse import dok_matrix\n",
    "S = dok_matrix((5, 5), dtype=np.float32)\n",
    "for i in range(5):\n",
    "    for j in range(i, 5):\n",
    "        S[i,j] = i+j\n",
    "        \n",
    "S.toarray()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The ``scipy.sparse`` submodule also has a lot of functions for sparse matrices\n",
    "including linear algebra, sparse solvers, graph algorithms, and much more."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Exercises"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Ex 1.1\n",
    "\n",
    "Create a big numpy **dense** matrix filled with random numbers in \n",
    "`[0, 1)`.\n",
    "Generate a random number within this range and subsitute all the elements in the matrix **less than** this number with a zero.\n",
    "\n",
    "Save resulting matrix as a `DOK` sparse matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Ex 1.2\n",
    "\n",
    "Repeat the previous exercise, but this time use a `CSR` sparse matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Ex 1.3\n",
    "\n",
    "Transform the previously generated sparse matrix back to a full dense `numpy.array`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Ex 1.4 \n",
    "\n",
    "Generate two sparse Matrix and sum them together, choosing the most appropriate internal representation (i.e. `LIL`, `CSR`, `DOK`...).\n",
    "\n",
    "#### Hint: Oh c'mon.. :)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.7 (WebValley2019)",
   "language": "python",
   "name": "webvalley19"
  },
  "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"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}