Traffic Stop Disposition: Classification Using F# and KNN

I have already looked at the summary statistics of the traffic stop data I received from the town here.  My next stop was to try and do a machine learning exercise with the data.  One of the more interesting questions I want to answer is what factors into weather a person gets a warning or a ticket (called disposition)?  Of all of the factors that may be involved, the dataset that I have is fairly limited:

Using dispositionId as the result variable, there is StopDateTime and Location (Latitude/Longitude).  Fortunately, DateTime can be decomposed into several input variables.  For this exercise, I wanted to use the following:

• TimeOfDay
• DayOfWeek
• DayOfMonth
• MonthOfYear
• Location (Latitude:Longitude)

And the resulting variable being disposition.  To make it easier for analysis, I limited the analysis set to finalDisposition as either “verbal warning” or “citation”  I decided to do a K-Nearest Neighbor because it is regarded as an easy machine learning algorithm to learn and the question does seem to be a classification problem.

My first step was to decide weather to write or borrow the KNN algorithm.  After looking at what kind of code would be needed to write my own and then looking at some other libraries, I decided to use Accord.Net.

My next first step was to get the data via the web service I spun up here.

1. namespace ChickenSoftware.RoadAlert.Analysis
2.  
3. open FSharp.Data
4. open Microsoft.FSharp.Data.TypeProviders
5. open Accord.MachineLearning
6.  
7. type roadAlert2 = JsonProvider<"http://chickensoftware.com/roadalert/api/trafficstopsearch/Sample&quot;>
8. type MachineLearningEngine =
9.     static member RoadAlertDoc = roadAlert2.Load("http://chickensoftware.com/roadalert/api/trafficstopsearch&quot;)

My next first step was to filter the data to only verbal warnings (7) or citations (15). 

1.   static member BaseDataSet =
2.       MachineLearningEngine.RoadAlertDoc
3.             |> Seq.filter(funx -> x.DispositionId = 7 || x.DispositionId = 15)
4.           |> Seq.map(fun x -> x.Id, x.StopDateTime, x.Latitude, x.Longitude, x.DispositionId)
5.           |> Seq.map(fun (a,b,c,d,e) -> a, b, System.Math.Round(c,3), System.Math.Round(d,3), e)
6.           |> Seq.map(fun (a,b,c,d,e) -> a, b, c.ToString() + ":" + d.ToString(), e)
7.           |> Seq.map(fun (a,b,c,d) -> a,b,c, match d with
8.                                               |7 -> 0
9.                                               |15 -> 1
10.                                               |_ -> 1)
11.           |> Seq.map(fun (a,b,c,d) -> a, b.Hour, b.DayOfWeek.GetHashCode(), b.Day, b.Month, c, d)
12.           |> Seq.toList

You will notice that I had to transform the dispositionIds from 7 and 15 to 1 and 0.  The reason why is that the KNN method in Accord.Net assumes that the values match the index position in the array.  I had to dig into the source code of Accord.Net to figure that one out.

My next step was to divide the dataset in half: one half being the training sample and the other the validation sample:

1. static member TrainingSample =
2.     let midNumber = MachineLearningEngine.NumberOfRecords/ 2
3.     MachineLearningEngine.BaseDataSet
4.         |> Seq.filter(fun (a,b,c,d,e,f,g) -> a < midNumber)
5.         |> Seq.toList
6.  
7. static member ValidationSample =
8.     let midNumber = MachineLearningEngine.NumberOfRecords/ 2
9.     MachineLearningEngine.BaseDataSet
10.         |> Seq.filter(fun (a,b,c,d,e,f,g) -> a > midNumber)
11.         |> Seq.toList

The next step was to actually run the KKN.  Before I could do that though, I had to create the distance function.  Since this was my 1st time, I dropped the geocoordinates and focused only on the time of day derivatives.

1. static member RunKNN inputs outputs input =
2.     let distanceFunction (a:int,b:int,c:int,d:int) (e:int,f:int,g:int,h:int) =  
3.       let b1 = b * 4
4.       let f1 = f * 4
5.       let d1 = d * 2
6.       let h1 = h * 2
7.       float((pown(a-e) 2) + (pown(b1-f1) 2) + (pown(c-g) 2) + (pown(d1-h1) 2))
8.  
9.     let distanceDelegate =
10.           System.Func<(int * int * int * int),(int * int * int * int),float>(distanceFunction)
11.     
12.     let knn = new KNearestNeighbors<int*int*int*int>(10,2,inputs,outputs,distanceDelegate)
13.     knn.Compute(input)

You will notice I  tried to normalize the values so that they all had the same basis.  They are not exact, but they are close.  You will also notice that I had to create a delegate from for the distanceFunction (thanks to Mimo on SO).  This is because Accord.NET was written in C# with C# consumers in mind and F# has a couple of places where the interfaces are not as seemless as one would hope.

In any event, once the KKN function was written, I wrote a function that to the validation sample, made a guess via KKN, and then reported the result:

1. static member GetValidationsViaKKN  =
2.     let inputs = MachineLearningEngine.TrainingInputClass
3.     let outputs = MachineLearningEngine.TrainingOutputClass
4.     let validations = MachineLearningEngine.ValidationClass
5.  
6.     validations
7.         |> Seq.map(fun (a,b,c,d,e) -> e, MachineLearningEngine.RunKNN inputs outputs (a,b,c,d))
8.         |> Seq.toList
9.  
10. static member GetSuccessPercentageOfValidations =
11.     let validations = MachineLearningEngine.GetValidationsViaKKN
12.     let matches = validations
13.                     |> Seq.map(fun (a,b) -> match (a=b) with
14.                                                 | true -> 1
15.                                                 | false -> 0)
16.  
17.     let recordCount =  validations |> Seq.length
18.     let numberCorrect = matches |> Seq.sum
19.     let successPercentage = double(numberCorrect) / double(recordCount)
20.     recordCount, numberCorrect, successPercentage

I then hopped over to my UI console app and looked that the success percentage.

 

1. private static void GetSuccessPercentageOfValidations()
2. {
3.     var output = MachineLearningEngine.GetSuccessPercentageOfValidations;
4.     Console.WriteLine(output.Item1.ToString() + ":" + output.Item2.ToString() + ":" + output.Item3.ToString());
5. }

So there are 12,837 records in the validation sample and the classifier guessed the correct disposition 9,001 times – a success percentage of 70%

So it looks like there is something there.  However, it is not clear that this is a good classifier without further tests – specifically seeing if the how to most common case results when pushing though the classifier.  Also, I would assume to make this a true ‘machine learning’ algorithm I would have to feed the results back to the distance function to see if I can alter it to get the success percentage higher.

One quick note about methodology – I used unit tests pretty extensively to understand how the KKN works.  I created a series of tests with some sample data to see who the function reacted. 

1. [TestMethod]
2. public void TestKKN_ReturnsExpected()
3. {
4.  
5.     Tuple<int, int, int, int>[] inputs = {
6.         new Tuple<int, int, int, int>(1, 0, 15, 1),
7.         new Tuple<int,int,int,int>(1,0,11,1)};
8.     int[] outputs = { 1, 1 };
9.  
10.     var input = new Tuple<int, int, int, int>(1, 1, 1, 1);
11.  
12.     var output = MachineLearningEngine.RunKNN(inputs, outputs, input);
13.  
14. }

This was a big help to get me up and running (walking, really..)…