simple-time-space-clustering.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this notebook we propose a method to efficiently cluster time-space data using the existing DBSCAN implementation in [scikit-learn](http://scikit-learn.org/). Before taking this approach, we considered two other approaches to time-space clustering. The first was to use an [existing implementation](https://github.com/eubr-bigsea/py-st-dbscan) of [ST-DBSCAN](http://www.sciencedirect.com/science/article/pii/S0169023X06000218). This implementation uses [COMPSS](https://www.bsc.es/research-and-development/software-and-apps/software-list/comp-superscalar/) for distributed computing, which may be nontrivial to quickly deploy. The second approach that we considered was to implement a custom time-space metric in python which we could pass into the scikit-learn DBSCAN implementation. However, we were concerned that this approach would not scale very well to large data sets compared to metrics predefined (and optimized) in scikit-learn.\n",
    "\n",
    "Our approach is to precompute a sparse spatial distance matrix where a given pairwise distance is only included if the time-distance is smaller than a given threshold. That is, for pairs of data points, we do the following:\n",
    "\n",
    "1. If the time distance is smaller than a given threshold value, and\n",
    "2. If the space distance is smaller than a second given threshold, then\n",
    "3. Include the space distance in the sparse pairwise distance matrix\n",
    "\n",
    "One way to think of this approach is that we are defining a time-space metric in which the time component only takes two values: smaller-than-epsilon and infinity.\n",
    "\n",
    "If the input data set is sorted by timestamp, then computing this distance matrix can be very efficient because you only ever need to compare pairs of points that are physically near each other in the data. In fact, it may be possible to modify this approach to apply and record a custom time-space metric (i.e., to try the second approach that we rejected for scaling badly when directly supplied to the DBSCAN implementation).\n",
    "\n",
    "Compared to ST-DBSCAN, this approach incorporates the time-distance in a very crude way and we expect the results will reflect that."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Import dependencies\n",
    "\n",
    "import collections\n",
    "import csv\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import os\n",
    "import scipy as sp\n",
    "\n",
    "from datetime import datetime, timedelta\n",
    "from sklearn.cluster import DBSCAN\n",
    "from sklearn.neighbors import DistanceMetric"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Define the function used to compute the sparse distance matrix\n",
    "\n",
    "\"\"\"Return the index of the first element x in a collection such that pred(x) is True.\"\"\"\n",
    "def find(coll, pred):\n",
    "    for i, x in enumerate(coll):\n",
    "        if pred(x):\n",
    "            return i\n",
    "    raise ValueError\n",
    "\n",
    "\"\"\"Drop the first n elements from the left end of deq.\"\"\"\n",
    "def dropn(deq, n):\n",
    "    for _ in range(n):\n",
    "        deq.popleft()\n",
    "\n",
    "\"\"\"\n",
    "Create a sparse distance matrix of distances between points in the data set. Currently this \n",
    "function hardcodes certain things that we might want to make into parameters, such as the \n",
    "distance metric and the formatof the input CSV. In order to work correctly, this function \n",
    "requires that the input data is sorted byincreasing timestamp values.\n",
    "\n",
    "infile - path to input CSV file. The data in this file should be sorted by timestamp.\n",
    "outfile - path where the output CSV file will be saved\n",
    "time_threshold - only record distances where the time difference is smaller than this timedelta\n",
    "space_threshold - only record distances if the space distance is smaller than this number\n",
    "\"\"\"\n",
    "def write_sparse_distance_matrix(infile, outfile, time_threshold, space_threshold):\n",
    "    \n",
    "    # We can make these parameters if we need to\n",
    "    dist = DistanceMetric.get_metric(\"haversine\")\n",
    "    date_format = \"%m/%d/%Y %H:%M\"\n",
    "    \n",
    "    def go(rr, wr):\n",
    "        left_index = 0\n",
    "        right_index = 0\n",
    "        \n",
    "        time_window = collections.deque()  # timestamp\n",
    "        space_window = collections.deque() # [lat, long]\n",
    "        \n",
    "        for row in rr:\n",
    "            lat, long, current_ts = row['lat'], row['lon'], row['date'] \n",
    "            current_coords = [lat, long]\n",
    "            current_ts = datetime.strptime(current_ts, date_format)\n",
    "            \n",
    "            try:\n",
    "                number_to_drop = find(time_window, lambda ts: current_ts - ts <= time_threshold)\n",
    "                left_index += number_to_drop\n",
    "                dropn(time_window, number_to_drop)\n",
    "                dropn(space_window, number_to_drop)\n",
    "            except ValueError:\n",
    "                left_index += len(time_window)\n",
    "                time_window.clear()\n",
    "                space_window.clear()\n",
    "            \n",
    "            if len(space_window) > 0:\n",
    "                distances = dist.pairwise(space_window, [current_coords])\n",
    "                for i, d in enumerate(np.nditer(distances)):\n",
    "                    if d <= space_threshold:\n",
    "                        wr.writerow({\n",
    "                                \"x\": left_index + i,\n",
    "                                \"y\": right_index,\n",
    "                                \"distance\": d\n",
    "                            })\n",
    "                        wr.writerow({\n",
    "                                \"x\": right_index,\n",
    "                                \"y\": left_index + i,\n",
    "                                \"distance\": d\n",
    "                            })\n",
    "            \n",
    "            right_index += 1\n",
    "            time_window.append(current_ts)\n",
    "            space_window.append(current_coords)\n",
    "        \n",
    "    with open(infile) as f, open(outfile, 'w') as outf:\n",
    "        rr = csv.DictReader(f)\n",
    "        wr = csv.DictWriter(outf, fieldnames=[\"x\", \"y\", \"distance\"])\n",
    "        wr.writeheader()\n",
    "        go(rr, wr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Set the input and output locations\n",
    "\n",
    "working_directory = \"/path/to/data\"\n",
    "infile = os.path.join(working_directory, \"input_data_sorted_by_timestamp.csv\")\n",
    "outfile = os.path.join(working_directory, \"sparse_distance_matrix.csv\")\n",
    "\n",
    "# Set the threshold parameters for the distance calculation\n",
    "# The space threshold should be the same value used as a parameter in DBSCAN below\n",
    "\n",
    "time_threshold = timedelta(minutes=60)\n",
    "space_threshold = 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Write the sparse matrix into a CSV file\n",
    "\n",
    "write_sparse_distance_matrix(infile, outfile, time_threshold, space_threshold)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Load the sparse distance matrix and compute clusters using DBSCAN\n",
    "\n",
    "df = pd.read_csv(outfile)\n",
    "distances = sp.sparse.csr_matrix((df[\"distance\"], (df[\"x\"], df[\"y\"])))\n",
    "\n",
    "model = DBSCAN(metric=\"precomputed\", eps=space_threshold)\n",
    "fit = model.fit(distances)"
   ]
  }
 ],
 "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}