Duncan spent last weekend (including Monday) doing some sort of Math Modeling Competition at which they used dating service algorithms to predict the likely next locations of serial crime
( Read more... )
In Facebook, Duncan McGregor commented on my note:
"For those of you more interested in technical details our method worked as follows.
Each region of a city is assigned a vector based on zoning information (i.e. commercial, residential, red light, etc.)
Between each adjacent area of the city place an edge and assign it weight of the average time between regions.
Each crime location was also assigned a vector of a different size corresponding to victim characteristics (i.e. commuting, prostitution, exercising, etc.).
Using a matrix-vector product we transformed victim characteristics into zoning information (i.e. prostitution maps to red light, exercising maps to public and residential...).
Each transformed victim vector was added to the location vector at the scene of the crime. A profile of the criminal was created by summing all the victim vectors and location of crime vectors. This summation was subject to a digital filter that can be adjusted based on how much the criminal's pattern is expected to change.
For example a very mutable criminal will have the following profile vector:
let P(n) be the pattern after victim n
let t(n) be the time of crime n let K = t(n) be the total time of the crime spree.
V(n) = transformed victim vector of crime n L(n) = location vector of crime n
P(n)= P(n-1)*8^-(( K - t(n-1))/K) + V(n) + L(n)
To account for a less mutable killer use an exponent closer to 0.
We then use Dijkstra's algorithm starting at the three most recent crime locations to find the closest locations.
We then take the dot product of each location in the subsection of the city with the profile vector and assign patrols based on the highest dot product values (this is the part we took from dating sites).
If we pick the closest 15% of the city and assign patrols at the highest 10 locations (assuming a 10x10 grid for the city) our model predicts the location of the next killer 50% of the time. This is decent compared to randomly assigning patrol to 10% of the city, which works 10% of the time."
Algorithm copyright (c)2010 Duncan McGregor and partner, of course.
"For those of you more interested in technical details our method worked as follows.
Each region of a city is assigned a vector based on zoning information (i.e. commercial, residential, red light, etc.)
Between each adjacent area of the city place an edge and assign it weight of the average time between regions.
Each crime location was also assigned a vector of a different size corresponding to victim characteristics (i.e. commuting, prostitution, exercising, etc.).
Using a matrix-vector product we transformed victim characteristics into zoning information (i.e. prostitution maps to red light, exercising maps to public and residential...).
Each transformed victim vector was added to the location vector at the scene of the crime. A profile of the criminal was created by summing all the victim vectors and location of crime vectors. This summation was subject to a digital filter that can be adjusted based on how much the criminal's pattern is expected to change.
For example a very mutable criminal will have the following profile vector:
let P(n) be the pattern after victim n
let t(n) be the time of crime n
let K = t(n) be the total time of the crime spree.
V(n) = transformed victim vector of crime n
L(n) = location vector of crime n
P(n)= P(n-1)*8^-(( K - t(n-1))/K) + V(n) + L(n)
To account for a less mutable killer use an exponent closer to 0.
We then use Dijkstra's algorithm starting at the three most recent crime locations to find the closest locations.
We then take the dot product of each location in the subsection of the city with the profile vector and assign patrols based on the highest dot product values (this is the part we took from dating sites).
If we pick the closest 15% of the city and assign patrols at the highest 10 locations (assuming a 10x10 grid for the city) our model predicts the location of the next killer 50% of the time. This is decent compared to randomly assigning patrol to 10% of the city, which works 10% of the time."
Algorithm copyright (c)2010 Duncan McGregor and partner, of course.
Reply
Leave a comment