Coffee shop location prediction, Vancouver

Overview

Where should a coffee shop open in Vancouver, given it should sit near a rapid transit station, have no Starbucks nearby, and stand in an area of low crime. Published as an article by the client.

The data

Fourteen years of Vancouver crime history, 530,653 records, filtered and reprocessed. Twenty-three rapid transit stations across three lines. Twenty-four Starbucks locations, ten of them near transit stations. Crime was classified into three categories used throughout: theft, break and enter, and mischief.

Method

1. Take crime history for the past two years
2. Locate every transit station and every Starbucks
3. Find stations with no Starbucks inside a set radius. Six qualified
4. Filter crime near those stations, narrowing over 110,000 records to roughly 44,000
5. Generate a grid of candidate coordinates around each station
6. Score each candidate against nearby crime and rank the results

Complexities tackled

The obvious approach does not run at all. One candidate coordinate per square metre gives a million candidates per square kilometre. Across six stations that is six million candidates, each compared against roughly 7,000 thefts, 19,000 break-ins and 17,000 mischiefs. That is an estimated 432.4 billion operations, which on ordinary hardware means many hours and sometimes days. The analysis was not going to finish, which is a design problem rather than a hardware one.

Two optimisations, and only the pair is enough. Coarsening the grid to one coordinate per ten square metres cuts candidates from a million to about ten thousand per square kilometre, which brings the estimate down to several billions and is still too slow on its own. The second change was spatial deduplication of the crime data: drop duplicate coordinates and merge those within about a metre of each other. That reduced the comparison set to 816 thefts, 2,654 break-ins and 8,234 mischiefs. Together they turned the job into 48.9 million comparisons for thefts, 159.2 million for break-ins and 494 million for mischiefs.

Knowing which precision is worth losing. Both optimisations trade accuracy for time. Merging crimes a metre apart and rounding candidate positions to ten metres does not change where a coffee shop should go, because the answer is a street corner and not a coordinate. Recognising which precision the question actually needs is the difference between an analysis that ships and one that runs overnight and gets cancelled.

Output

Six final coordinates passing every constraint, ranked by distance to the nearest transit station. Constraint by constraint: 122,000 candidates survived having no theft within a kilometre, 8,000 survived no break-in within 200 metres, and 6,000 survived no mischief within 200 metres.

Stack

Python, Pandas, Matplotlib, open government data.