examples/Networks/Hotspots on a network.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Hotspots on a network\n",
    "\n",
    "A class of algorithms which are based on the classical (prospective / retrospective) hotspotting techniques where a grid is replaced by edges on a network/graph.\n",
    "\n",
    "\n",
    "## Sources\n",
    "\n",
    "1. Rosser et al. \"Predictive Crime Mapping: Arbitrary Grids or Street Networks?\" Journal of Quantitative Criminology 33 (2017) 569--594 [10.1007/s10940-016-9321-x](https://link.springer.com/article/10.1007/s10940-016-9321-x)\n",
    "2. Okabe et al. \"A kernel density estimation method for networks, its computational method and a GIS‐based tool\" International Journal of Geographical Information Science 23 (2009) 7--32  [10.1080/13658810802475491](http://www.tandfonline.com/doi/abs/10.1080/13658810802475491)\n",
    "\n",
    "\n",
    "## Algorithm\n",
    "\n",
    "We follow (1), which itself uses (2) for the KDE method.\n",
    "\n",
    "- We need geometry giving the street network we'll work on.\n",
    "  - For the moment, we use freely available data from the [OS Open Road](https://www.ordnancesurvey.co.uk/business-and-government/products/os-open-roads.html) for the UK, and [TIGER/Line](https://www.census.gov/geo/maps-data/data/tiger-line.html) for the USA.\n",
    "  - For us, a \"network\" or \"graph\" is a collection of vertices in the plane, with edges connecting (some of) the vertices, as straight lines.  Informally, the \"network\" is the subset of the plane formed by the union of all the edges.  Curved streets can be approximated by adding further vertices.  This usage correlates with the above geometry sources.\n",
    "- All events need to be assigned to the network.  Following (1) we simply orthogonally project each event to the network (this is equivalent as assigning each event to the closest point on the network).\n",
    "- We then \"simply\" change the grid-based hotspotting technique to work on the network, using (2).  We give details below.\n",
    "\n",
    "The resulting \"hotspot\" is actually a \"risk\" estimate for each point on the network, where a higher risk corresponds to the belief that future events are more likely.  As usual, we generate an actual \"hotspot(s)\" by chosing a \"coverage level\", say 10%, and then selecting the 10% of the network which is most risky, where we use the natural length of edges in the network to decide what \"10%\" means.\n",
    "\n",
    "We might naturally want to compare such a prediction with a grid-based prediction.  To do this, (1) suggests (although they don't quite use these words) generating a network prediction from a grid prediction.  We do this by giving edge network point the \"risk\" of the grid cell it occurs in.  Once this is done, we can then compare network predictions directly.  (For example, to generate 10% coverage, we work from most risky to least risky grid cell, adding all the network which intersects with that cell, until we have selected 10% of the network by length.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## KDE on a network\n",
    "\n",
    "We follow (2); the summary in (1) is very clear.  Let $s'$ be an event on the network.  We seek to derive a formula for the (space-like) kernel induced at a point $s$.  As a base, we start with a one-dimensional kernel function $f:\\mathbb R\\rightarrow [0,\\infty)$.  We assume that $f$ is symmetric, $f(-t) = f(t)$, and it should be normalised, $\\int_{\\mathbb R} f(t) \\ dt = 1$.  (Source (2) gives further conditions, but these are details, and will be satisfied by our kernels.)  We always suppose our kernels have a finite \"support\", a value $t_\\max$ such that $f(t)=0$ for any $|t|>t_\\max$.\n",
    "\n",
    "We consider all paths in the network from $s'$ to $s$, ignoring any \"cyclic\" paths.  This is not entirely specified in (1), so we use this algorithm:\n",
    "- We perform a [Breadth-first search](https://en.wikipedia.org/wiki/Breadth-first_search) starting at $s'$ and considering all possible vertices adjacent to $s'$, forming a set of possible paths.  For each possible path, we consider the adjacent vertices to the end vertex, forming a new set of possible paths.  We continue, discarding paths where:\n",
    "  - We form a cycle, by visiting a vertex we have visited before.  We ignore such paths.\n",
    "  - We get to $s$.  We consider such paths.\n",
    "  - The length of the path is greater than the support of the base kernel $f$.\n",
    "- This gives us a finite set of possible paths, $P$.\n",
    "- For each path $p\\in P$ we will visit vertices $v_1, \\cdots, v_{m(p)}$ between $s'$ and $s$.  For each $i$ let $n_i$ be the order of the vertex $v_i$, that is, the number of neighbours which $v_i$ has.\n",
    "- Let $l(p)$ be the length of that path.\n",
    "- Our network kernel estimate is then\n",
    "$$ k_{s'}^{(p)}(s) = \\sum_{P} \\frac{f(l(p))}{(n_1-1)\\cdots(n_{m(p)}-1)} $$\n",
    "- This corresponds to \"splitting\" the kernel at each vertex by the number of possible paths out of that vertex.  See (2) for further details.\n",
    "- The final kernel estimate is obtained by summing over all events $s'$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Which kernels to use\n",
    "\n",
    "(1) considers a \"prospective\" hotspotting technique, which takes account of time.  We consider forming a prediction at time $t$.  Consider events which occur at time $t_i$ for $i=1,\\cdots,n$, and which occur at a place $s_i$ on the network.  We combine a time and space kernel.\n",
    "\n",
    "- The time kernel is\n",
    "$$ g(t) = \\frac{1}{h_T} \\exp\\Big( -\\frac{t}{h_T} \\Big). $$\n",
    "That is, exponential decay, with a \"bandwidth\" $h_T$.\n",
    "- The space kernel uses a base kernel which is linear decay:\n",
    "$$ f(s) = \\begin{cases} \\frac{h_S - s}{h_S^2} &: 0 \\leq s \\leq h_S,\\\\ 0 &: |s| > h_S. \\end{cases} $$\n",
    "Here $h_S$ is the \"spatial bandwidth\" or \"support\" as above.\n",
    "\n",
    "Thus the final network \"risk\" estimate is at time $t$ and network location $s$,\n",
    "$$ \\lambda(s,t) = \\sum_{t_i<t} \\frac{1}{h_T} \\exp\\Big( -\\frac{t-t_i}{h_T} \\Big)\n",
    "\\Big( \\sum_i \\sum_{p:s_i\\rightarrow s, l(p) \\leq h_S} \\frac{h_S - l(p)}{h_S^2(n_1-1)\\cdots(n_{m(p)}-1)}\\Big) $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Efficiency\n",
    "\n",
    "We are interested in an estimate of the risk at a fixed time $t$.  Source (1) suggests sampling $\\lambda(s) = \\lambda(s,t)$ at various points $s$ across the network; (1) suggests every 30 metres.  We make some comments on how to improve this, and towards efficient computation:\n",
    "\n",
    "- If we are only sampling at points, then we may as well actually just deem every edge in the network to have a risk which is constant across that edge.  If an edge is too long, then it can simply be split into parts by adding addition vertices.\n",
    "- Thus, we will assign, say, the risk at the _centre_ of each edge to the whole edge.\n",
    "- To correctly normalise, we should multiply this point risk by the length of the edge.  An alternative, if the form of the spacial kernel is analytically tractable, is to integrate it over the edge.\n",
    "- It is more efficient to work over each event at time $t_i<t$ in turn, performing the \"walk\" across the network from that point, adding to the risk of each edge as we encounter it.\n",
    "\n",
    "To find all paths between a point in the middle of an edge between vertices $u_1, u_2$ and a point in the middle of an edge between vertices $u_3, u_4$, we can proceed as follows:\n",
    "- Decide we will first move to vertex $u_1$, and will finally move to vertex $u_3$.\n",
    "- Find all such paths, ignoring any path which uses the edges between $u_1, u_2$ and $u_3, u_4$, to avoid circular paths.\n",
    "- Do the for paths $u_1 \\rightarrow u_4$, then $u_2\\rightarrow u_3$ and finally $u_2\\rightarrow u_4$.\n",
    "\n",
    "Finally, once we have summed all the \"risks\" for each edge, we should normalise and divide by the length of the edge.\n",
    "- This assigns to each edge the average/expected risk.\n",
    "- We can then e.g. take the top 10% of edges to form network \"hotspots\"\n",
    "- (Or apply some more involved hotspot generation algorithm)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Approximation\n",
    "\n",
    "The above procedure is very slow if the \"spatial bandwidth\" of the kernel becomes large (and in practical situations, it is large).  We have implemented a caching scheme which:\n",
    "- Uses a lot of memory.  For the South side of Chicago, we need a 12GB machine.\n",
    "- Is only of benefit if the same network and events collection will be tested for multiple kernels (for example) or across multiple days.\n",
    "\n",
    "An alternative scheme, as explored more in the `Geometry reduction` notebook, is to approximate the sum over all paths by:\n",
    "- Simply compute the shortest path.  \n",
    "- But continue to take account of node degree.\n",
    "- We can use a variation of Dijkstra's algorithm to do this.\n",
    "- This seems to lead to a reasonably good approximation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Comparison to grid based methods\n",
    "\n",
    "We again follow (1).  Given a grid prediction, we can intersect the grid with the network, and assign the risk of each grid cell to every network part which intersects that cell.\n",
    "\n",
    "- As (1) notes, this typically leads to a slightly artificial intersection of the grid and network\n",
    "- It seems likely that the better performance of the network hotspot to the grid hotspot found in (1) is mostly due to the \"over coverage\" from this intersection procedure.  It would be interesting to make this conjecture precise and to test it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Examples\n",
    "\n",
    "For networks, it is hard(er) to produce toy examples.  So instead of giving examples here, we give examples using real data from Chicago.\n",
    "\n",
    "- See the folder \"Case study Chicago\"\n",
    "- The notebook \"Input data\" describes how we produced the data we need as input\n",
    "- The notebook \"Hotspotting\" shows how to produce a hotspot map on a network\n",
    "- The notebook \"Grid to network hotspotting\" shows how to move from a grid prediction to a network prediction\n",
    "- The notebook \"Cross-Validation\" shows a replication of the work of Rosser et al, but for Chicago, on choosing optimal bandwidths\n",
    "- The notebook \"Cross-Validation grid\" does the same for gird based predictions with the Chicago data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}