05-Distances-Timeseries.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "hide_input": true,
    "slideshow": {
     "slide_type": "skip"
    },
    "tags": [
     "hide-cell"
    ]
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "%config InlineBackend.figure_format='retina'\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "import seaborn as sns\n",
    "from IPython.display import Image, display_html, display, Math, HTML;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Distances and Timeseries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Today we will start building some tools for making comparisons of data objects, with particular attention to timeseries."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Working with data, we can encounter a wide variety of different data objects:\n",
    "\n",
    "* Records of users\n",
    "* Graphs\n",
    "* Images\n",
    "* Videos\n",
    "* Text (webpages, books)\n",
    "* Strings (DNA sequences)\n",
    "* Timeseries\n",
    "* ...\n",
    "\n",
    "How can we compare them?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Feature space representation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Usually a data object consists of a set of attributes.\n",
    "\n",
    "These are also commonly called __features.__\n",
    "\n",
    "* (\"J. Smith\", 25, \\$ 200,000)\n",
    "* (\"M. Jones\", 47, \\$ 45,000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "If all $d$ dimensions are real-valued then we can visualize each data object as a point in a $d$-dimensional vector space.\n",
    " \n",
    "* `(25, USD 200000)` $\\rightarrow \\begin{bmatrix}25\\\\200000\\end{bmatrix}$.\n",
    "\n",
    "Likewise If all features are binary then we can think of each data object as a binary vector in vector space.\n",
    "\n",
    "The space is called __feature space.__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Vector spaces are such a useful tool that we often use them even for non-numeric data.\n",
    "\n",
    "For example, consider a categorical variable that can be only one of \"house\", \"tree\", \"moon\".\n",
    "\n",
    "For such a variable, we can use a __one-hot__ encoding.  \n",
    "\n",
    "We would encode as follows:\n",
    "   * `house`: $[1, 0, 0]$\n",
    "   * `tree`:  $[0, 1, 0]$\n",
    "   * `moon`:  $[0, 0, 1]$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "So an encoding of `(25, USD 200000, 'house')`\n",
    "\n",
    "could be:\n",
    "\n",
    "$$\\begin{bmatrix}25\\\\200000\\\\1\\\\0\\\\0\\end{bmatrix}.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "We will see many other encodings that take non-numeric data and encode into vectors or matrices.\n",
    "\n",
    "For example, there are vector or matrix encodings for:\n",
    "   * Graphs\n",
    "   * Images\n",
    "   * Text \n",
    "   \n",
    "etc."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Similarity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "We then are naturally interested in how __similar__ or __dissimilar__ two objects are."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "A dissimilarity function takes two objects as input, and returns a large value when the two objects are not very similar."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Often we put restrictions on the dissimilarity function.\n",
    "\n",
    "One of the most common is that it be a __metric.__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "The dissimilarity $d(x, y)$ between two objects $x$ and $y$ is a\n",
    "__metric__ if\n",
    "\n",
    "* $d(i, j) = 0 \\leftrightarrow i == j\\;\\;\\;\\;\\;\\;\\;\\;$ (identity of indiscernables)\n",
    "* $d(i, j) = d(j, i)\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;$ (symmetry)\n",
    "* $d(i, j) \\leq d(i, h)+d(h, j)\\;\\;$ (triangle inequality)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hide_input": false,
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": [
     "hide-input"
    ]
   },
   "source": [
    "<center>\n",
    "    \n",
    "<img src=\"figs/TriangleInequality.png\" alt=\"Figure\" width=\"350px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "By WhiteTimberwolf, Brews ohare (PNG version) - PNG version, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=26047092"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "A metric is also commonly called a __distance__.\n",
    "\n",
    "Sometimes we will use \"distance\" informally, ie, to refer to a dissimilarity function even if we are not sure it is a metric.   \n",
    "\n",
    "We'll try to say \"dissimilarity\" in those cases though."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Why is it important or valuable for a dissimilarity to be a metric?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The additional constraints allow us to reason about and more easily visualize the data.\n",
    "\n",
    "The main way this happens is through the triangle inequality.   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The triangle inequality basically says, if two objects are \"close\" to another object, then they are \"close\" to each other.  \n",
    "\n",
    "This is not always the case for real data, but when it is true, it can really help."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Definitions of distance or dissimilarity functions are usually\n",
    "diferent for real, boolean, categorical, and ordinal\n",
    "variables.\n",
    "\n",
    "Weights may be associated with diferent variables\n",
    "based on applications and data semantics."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Matrix representation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Very often we will manage data conveniently in matrix form.\n",
    "\n",
    "The standard way of doing this is:\n",
    "\n",
    "$$ \\mbox{$m$ data objects}\\left\\{\\begin{array}{c}\\;\\\\\\;\\\\\\;\\\\\\;\\\\\\;\\end{array}\\right.\\;\\;\\overbrace{\\left[\\begin{array}{ccccc}\n",
    "\\begin{array}{c}x_{11}\\\\\\vdots\\\\x_{i1}\\\\\\vdots\\\\x_{m1}\\end{array}&\n",
    "\\begin{array}{c}\\dots\\\\\\ddots\\\\\\dots\\\\\\ddots\\\\\\dots\\end{array}&\n",
    "\\begin{array}{c}x_{1j}\\\\\\vdots\\\\x_{ij}\\\\\\vdots\\\\x_{mj}\\end{array}&\n",
    "\\begin{array}{c}\\dots\\\\\\ddots\\\\\\dots\\\\\\ddots\\\\\\dots\\end{array}&\n",
    "\\begin{array}{c}x_{1n}\\\\\\vdots\\\\x_{in}\\\\\\vdots\\\\x_{mn}\\end{array}\n",
    "\\end{array}\\right]}^{\\mbox{$n$ features}} $$\n",
    "\n",
    "Where we typically use symbols $m$ for number of rows (objects) and $n$ for number of columns (features).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "When we are working with distances, the matrix representation is:\n",
    "\n",
    "$$ \\mbox{$m$ data objects}\\left\\{\\begin{array}{c}\\;\\\\\\;\\\\\\;\\\\\\;\\end{array}\\right.\\;\\;\n",
    "\\overbrace{\\left[\\begin{array}{cccc}\n",
    "\\begin{array}{c}0\\\\d(1,2)\\\\d(1,3)\\\\\\vdots\\\\d(1,m)\\end{array} &\n",
    "\\begin{array}{c}\\;\\\\0\\\\d(2,3)\\\\\\vdots\\\\d(2,m)\\end{array} &\n",
    "\\begin{array}{c}\\;\\\\\\;\\\\\\ddots\\\\\\vdots\\\\\\dots\\end{array} &\n",
    "\\begin{array}{c}\\;\\\\\\;\\\\\\;\\\\\\;\\\\0\\end{array} \\\\\n",
    "\\end{array}\\right]}^{\\mbox{$m$ data objects}} $$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Norms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Assume some function $p(\\mathbf{v})$ which measures the \"size\" of the vector $\\mathbf{v}$.\n",
    "\n",
    "$p()$ is called a __norm__ if:\n",
    "\n",
    "* $p(a\\mathbf{v}) = |a|\\; p(\\mathbf{v})\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;$ (absolute scaling)\n",
    "* $p(\\mathbf{u} + \\mathbf{v}) \\leq p(\\mathbf{u}) + p(\\mathbf{v})\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;$  (subadditivity)\n",
    "* $p(\\mathbf{v}) = 0 \\leftrightarrow \\mathbf{v}$ is the zero vector $\\;\\;\\;\\;$(separates points)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Norms are important for this reason, among others:\n",
    "    \n",
    "__Every norm defines a corresponding metric.__\n",
    "\n",
    "That is, if $p()$ is a norm, then $d(\\mathbf{x}, \\mathbf{y}) = p(\\mathbf{x}-\\mathbf{y})$ is a metric."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Useful Norms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "A general class of norms are called __$\\ell_p$__ norms, where $p \\geq 1.$\n",
    "\n",
    "$$ \\Vert \\mathbf{x} \\Vert_p = \\left(\\sum_{i=1}^d |x_i|^p\\right)^{\\frac{1}{p}} $$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that we use this notation for the $p$-norm of a vector $\\mathbf{x}$:\n",
    "\n",
    "$$ \\Vert \\mathbf{x} \\Vert_p $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The corresponding distance that an $\\ell_p$ norm defines is called the _Minkowski distance._\n",
    "\n",
    "$$ \\Vert \\mathbf{x} - \\mathbf{y} \\Vert_p = \\left(\\sum_{i=1}^d |x_i - y_i|^p\\right)^{\\frac{1}{p}} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "A special -- but very important -- case is the $\\ell_2$ norm.\n",
    "\n",
    "$$ \\Vert \\mathbf{x} \\Vert_2 = \\sqrt{\\sum_{i=1}^d |x_i|^2} $$\n",
    "\n",
    "We've already mentioned it: it is the __Euclidean__ norm.\n",
    "\n",
    "The distance defined by the $\\ell_2$ norm is the same as the Euclidean distance between the vectors.\n",
    "\n",
    "$$ \\Vert \\mathbf{x} - \\mathbf{y} \\Vert_2  = \\sqrt{\\sum_{i=1}^d (x_i - y_i)^2} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Another important special case is the $\\ell_1$ norm.\n",
    "\n",
    "$$ \\Vert \\mathbf{x} \\Vert_1 = \\sum_{i=1}^d |x_i| $$\n",
    "\n",
    "This defines the __Manhattan__ distance, or (for binary vectors), the __Hamming__ distance:\n",
    "\n",
    "$$ \\Vert \\mathbf{x} - \\mathbf{y} \\Vert_1 = \\sum_{i=1} |x_i - y_i| $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<center>\n",
    "    \n",
    "<img src=\"figs/L05-manhattan-distance.png\" alt=\"Figure\" width=\"350px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "If we take the limit of the $\\ell_p$ norm as $p$ gets large we get the $\\ell_\\infty$ norm.  \n",
    "\n",
    "The value of the $\\ell_\\infty$ norm is simply the __largest element__ in a vector.\n",
    "\n",
    "What is the metric that this norm induces?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Another related idea is the $\\ell_0$ \"norm,\" which is not a norm, but is in a sense what we get from the $p$-norm for $p = 0$.\n",
    "\n",
    "Note that this is __not__ a norm, but it gets called that anyway.   \n",
    "\n",
    "This \"norm\" simply counts the number of __nonzero__ elements in a vector.\n",
    "\n",
    "This is called the vector's __sparsity.__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Here is the notion of a \"circle\" under each of three norms.\n",
    "\n",
    "That is, for each norm, the set of vectors having norm 1, or distance 1 from the origin."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hide_input": false,
    "slideshow": {
     "slide_type": "-"
    },
    "tags": [
     "hide-input"
    ]
   },
   "source": [
    "<center>\n",
    "    \n",
    "<img src=\"figs/L5-Vector-Norms.png\" alt=\"Figure\" width=\"150px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a href=\"http://creativecommons.org/licenses/by-sa/3.0/\" title=\"Creative Commons Attribution-Share Alike 3.0\">CC BY-SA 3.0</a>, <a href=\"https://commons.wikimedia.org/w/index.php?curid=678101\">https://commons.wikimedia.org/w/index.php?curid=678101</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Similarity and Dissimilarity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "We've already seen that the inner product of two vectors can be used to compute the __cosine of the angle__ between them:\n",
    "\n",
    "$$ \\cos(\\mathbf{x}, \\mathbf{y}) = \\frac{\\mathbf{x}^T\\mathbf{y}}{\\Vert\\mathbf{x}\\Vert \\Vert\\mathbf{y}\\Vert} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Note that this value is __large__ when $\\mathbf{x} \\approx \\mathbf{y}.$  So it is a __similarity__ function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "We often find that we have a similarity function $s$ and need to convert it to a dissimilarity function $d$.   \n",
    "\n",
    "Two straightforward ways of doing that are:\n",
    "\n",
    "$$d(x,y) = 1\\,/\\,s(x,y)$$\n",
    "\n",
    "or \n",
    "\n",
    "$$d(x,y) = k - s(x,y)$$\n",
    "\n",
    "...for some properly chosen $k$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "For cosine similarity, one often uses:\n",
    "    \n",
    "$$ d(\\mathbf{x}, \\mathbf{y}) = 1 - \\cos(\\mathbf{x}, \\mathbf{y})$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Note however that this is __not a metric!__\n",
    "\n",
    "However if we recover the actual angle beween $\\mathbf{x}$ and $\\mathbf{y}$, that is a metric."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Bit vectors and Sets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "When working with bit vectors, the $\\ell_1$ metric is commonly used and is called the __Hamming__ distance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hide_input": false,
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": [
     "hide-input"
    ]
   },
   "source": [
    "<center>\n",
    "    \n",
    "<img src=\"figs/L5-hamming-1.png\" alt=\"Figure\" width=\"500px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "This has a natural interpretation: \"how well do the two vectors match?\"\n",
    "\n",
    "Or: \"What is the smallest number of bit flips that will convert one vector into the other?\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hide_input": false,
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": [
     "hide-input"
    ]
   },
   "source": [
    "<center>\n",
    "    \n",
    "<img src=\"figs/L5-hamming-2.png\" alt=\"Figure\" width=\"500px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "In other cases, the Hamming distance is not a very appropriate metric.\n",
    "\n",
    "Consider the case in which the bit vector is being used to represent a set.\n",
    "\n",
    "In that case, Hamming distance measures the __size of the set difference.__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "For example, consider two documents.   We will use bit vectors to represent the sets of words in each document.\n",
    "\n",
    "* Case 1: both documents are large, almost identical, but differ in 10 words.\n",
    "* Case 2: both documents are small, disjoint, have 5 words each."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The situation can be represented as this:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hide_input": false,
    "tags": [
     "hide-input"
    ]
   },
   "source": [
    "<center>\n",
    "    \n",
    "<img src=\"figs/L5-jaccard-1.png\" alt=\"Figure\" width=\"500px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "What matters is not just the size of the set difference, but the size of the intersection as well.\n",
    "\n",
    "This leads to the _Jaccard_ similarity:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$$J_{Sim}(\\mathbf{x}, \\mathbf{y}) = \\frac{|\\mathbf{x} \\cap \\mathbf{y}|}{|\\mathbf{x} \\cup \\mathbf{y}|}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "This takes on values from 0 to 1, so a natural dissimilarity metric is $1 - J_{Sim}().$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "In fact, this is a __metric!__:\n",
    "\n",
    "$$J_{Dist}(\\mathbf{x}, \\mathbf{y}) = 1- \\frac{|\\mathbf{x} \\cap \\mathbf{y}|}{|\\mathbf{x} \\cup \\mathbf{y}|}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Consider our two cases:\n",
    "    \n",
    "Case 1: (very large almost identical documents)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hide_input": false,
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": [
     "hide-input"
    ]
   },
   "source": [
    "<center>\n",
    "    \n",
    "<img src=\"figs/L5-jaccard-2.png\" alt=\"Figure\" width=\"500px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Here $J_{Sim}(\\mathbf{x}, \\mathbf{y})$ is almost 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Case 2: (small disjoint documents)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hide_input": false,
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": [
     "hide-input"
    ]
   },
   "source": [
    "<center>\n",
    "    \n",
    "<img src=\"figs/L5-jaccard-3.png\" alt=\"Figure\" width=\"500px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "Here $J_{Sim}(\\mathbf{x}, \\mathbf{y})$ is 0."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Time Series"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "A time series is a sequence of real numbers, representing the measurements of a real variable at (equal) time intervals.\n",
    "\n",
    "* Stock prices\n",
    "* Volume of sales over time\n",
    "* Daily temperature readings\n",
    "\n",
    "A time series database is a large collection of time series."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Similarity of Time Series"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "How should we measure the \"similarity\" of two timeseries?\n",
    "\n",
    "We will assume they are the same length.\n",
    "\n",
    "Examples:\n",
    "\n",
    "* Find companies with similar stock price movements over a time interval\n",
    "* Find similar DNA sequences\n",
    "* Find users with similar credit usage patterns\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Two Problems:\n",
    "\n",
    "1. Defining a meaningful similarity (or distance) function.\n",
    "2. Finding an efficient algorithm to compute it.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Norm-based Similarity Measures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "We could just view each sequence as a vector.\n",
    "\n",
    "Then we could use a $p$-norm, eg $\\ell_1, \\ell_2,$ or $\\ell_p$ to measure similarity."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Advantages:\n",
    "    \n",
    "1. Easy to compute - linear in the length of the time series (O(n)).\n",
    "2. It is a metric.\n",
    "\n",
    "Disadvantage:\n",
    "\n",
    "1. May not be __meaningful!__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hide_input": false,
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": [
     "hide-input"
    ]
   },
   "source": [
    "<center>\n",
    "    \n",
    "<img src=\"figs/L5-ts-euclidean.png\" alt=\"Figure\" width=\"500px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "We may believe that $\\mathbf{ts1}$ and $\\mathbf{ts2}$ are the most \"similar\" pair of timeseries.\n",
    "\n",
    "However, according to Euclidean distance: \n",
    "\n",
    "$$ \\Vert \\mathbf{ts1} - \\mathbf{ts2} \\Vert_2 = 26.9,$$\n",
    "\n",
    "while \n",
    "\n",
    "$$ \\Vert \\mathbf{ts1} - \\mathbf{ts3} \\Vert_2 = 23.2.$$\n",
    "\n",
    "Not good!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Feature Engineering"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "In general, there may be different aspects of a timeseries that are important in different settings.\n",
    "\n",
    "The first step therefore is to ask yourself \"what is important about timeseries in my application?\"\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "This is an example of __feature engineering.__\n",
    "\n",
    "In other words, feature engineering is the art of computing some derived measure from your data object that makes its important properties usable in a subsequent step."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "A reasonable approach may then to be:\n",
    "    \n",
    "* extract the relevant features\n",
    "* use a simple method (eg, a norm) to define similarity over those features.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "In the case above, one might think of using \n",
    "\n",
    "* Fourier coefficients (to capture periodicity)\n",
    "* Histograms\n",
    "* Or something else!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Dynamic Time Warping"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "One case that arises often is something like the following:  \"bump hunting\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hide_input": false,
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": [
     "hide-input"
    ]
   },
   "source": [
    "<center>\n",
    "    \n",
    "<img src=\"figs/L5-DTW-1.png\" alt=\"Figure\" width=\"500px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Both timeseries have the same key characteristics: four bumps.\n",
    "\n",
    "But a one-one match (ala Euclidean distance) will not detect the similarity.\n",
    "\n",
    "(Be sure to think about why Euclidean distance will fail here.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "A solution to this is called __dynamic time warping.__\n",
    "\n",
    "The basic idea is to allow acceleration or deceleration of signals along the time dimension."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Classic applications:\n",
    "    \n",
    "* Speech recognition\n",
    "* Handwriting recognition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Specifically: \n",
    "\n",
    "* Consider $X = x_1, x_2, \\dots, x_n$ and $Y = y_1, y_2, \\dots, y_n$.\n",
    "* We are allowed to extend each sequence by repeating elements to form $X'$ and $Y'$.\n",
    "* We then calculate, eg, Euclidean distance between the extended sequnces $X'$ and $Y'$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "There is a simple way to visualize this algorithm.\n",
    "\n",
    "Consider a matrix $M$ where $M_{ij} = |x_i - y_j|$ (or some other error measure)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hide_input": false,
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": [
     "hide-input"
    ]
   },
   "source": [
    "<center>\n",
    "    \n",
    "<img src=\"figs/L5-DTW-2.png\" alt=\"Figure\" width=\"500px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "$M$ measures the amount of error we get if we match $x_i$ with $y_j$. \n",
    "\n",
    "So we seek a __path through $M$ that minimizes the total error.__\n",
    "\n",
    "We need to start in the lower left and work our way up via a continuous path."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Basic restrictions on path:\n",
    "    \n",
    "* Montonicity\n",
    "    * path should not go down or to the left\n",
    "* Continuity\n",
    "    * No elements may be skipped in sequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "This can be solved via dynamic programming.  However, the algorithm is still quadratic in $n$.\n",
    "\n",
    "Hence, we may choose to put a restriction on the amount that the path can deviate from the diagonal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The basic algorithm looks like this:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "```\n",
    "D[0, 0] = 0\n",
    "for i in range(n):\n",
    "  for j in range(m):\n",
    "    D[i,j] = M[i,j] + \n",
    "             min( D[i-1, j],    # insertion\n",
    "                  D[i, j-1],    # deletion\n",
    "                  D[i-1, j-1] ) # match\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Unfortunately, the algorithm is still quadratic in $n$ -- it is $O(nm)$.\n",
    "\n",
    "Hence, we may choose to put a restriction on the amount that the path can deviate from the diagonal.\n",
    "\n",
    "This is implemented by not allowing the path to pass through locations where $|i - j| > w$.\n",
    "\n",
    "Then the algorithm is $O(nw)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## From Timeseries to Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "A closely related idea concerns strings.\n",
    "\n",
    "The key point is that, like timeseries, strings are __sequences__."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Given two strings, one way to define a 'distance' between them is:\n",
    "* the minimum number of __edit operations__ that are needed to transform one string into the other.\n",
    "\n",
    "Edit operations are insertion, deletion, and substitution of single characters.\n",
    "\n",
    "This is called __edit distance__ or __Levenshtein distance.__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "For example, given strings:\n",
    "\n",
    "``s = VIVALASVEGAS``\n",
    "    \n",
    "and\n",
    "\n",
    "``t = VIVADAVIS``\n",
    "\n",
    "we would like to \n",
    "* compute the edit distance, and\n",
    "* obtain the optimal __alignment__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hide_input": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<center>\n",
    "    \n",
    "<img src=\"figs/viva-las-vegas.png\" alt=\"Drawing\" width=\"500px\">\n",
    "\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "tags": [
     "remove-cell"
    ]
   },
   "source": [
    "Source: http://medicalbioinformaticsgroup.de/downloads/lectures/Algorithmen_und_Datenstrukturen/WS15-16/aldabi_ws15-16_woche6.pdf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "A dynamic programming algorithm can also be used to find this distance, \n",
    "\n",
    "and it is __very similar to dynamic time-warping.__\n",
    "\n",
    "In bioinformatics this algorithm is called __\"Smith-Waterman\" sequence alignment.__"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "celltoolbar": "Slideshow",
  "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.10"
  },
  "rise": {
   "scroll": true,
   "theme": "beige",
   "transition": "fade"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}