Apriori Algorithm and F# Using Elevator Inspection Data

March 18, 2014 1 Comment

Now that I have the elevator dataset in a workable state, I wanted to see what I could see with the data.  I was reading Machine Learning In Action and the authors suggested that an Apriori Algorithm as a way to quantify associations among data points.  I read both Harrington’s code and Wikipedia’s description and I found both the be impenetrable – the former because their code was unreadable and the later because  the mathematical formulas depended on a level of algebra that I don’t have.

Fortunately, I found a C# project on Codeproject that had both an excellent example/introduction and C# code.  I used the examples on the website to formulate my F# implementation.

The first thing I did was create a class that matched the 1st grid in the example

image

  1. namespace ChickenSoftware.ElevatorChicken.Analysis
  2.  
  3. open System.Collections.Generic
  4.  
  5. type Transaction = {TID: string; Items: List<string> }
  6.  
  7. type Apriori(database: List<Transaction>, support: float, confidence: float) =
  8.     member this.Database = database
  9.     member this.Support = support
  10.     member this.Confidence = confidence

Note that because F# is immutable by default, the properties are read-only.  I then created a unit test project that makes sure the constructor works without exceptions.  The data matches the example:

  1. public AprioriTests()
  2. {
  3.     var database = new List<Transaction>();
  4.     database.Add(new Transaction("100", new List<string>() { "A", "C", "D" }));
  5.     database.Add(new Transaction("200", new List<string>() { "B", "C", "E" }));
  6.     database.Add(new Transaction("300", new List<string>() { "A", "B", "C", "E" }));
  7.     database.Add(new Transaction("400", new List<string>() { "B", "E" }));
  8.  
  9.     _apriori = new Apriori(database, .5, .80);
  10.  
  11. }
  12.  
  13. [TestMethod]
  14. public void ConstructorUsingValidArguments_ReturnsExpected()
  15. {
  16.     Assert.IsNotNull(_apriori);
  17. }

I then need a function to count up all of the items in the Itemsets.  I refused to use loops, so I first started using Seq.Fold, but I was having zero luck because I was trying to fold a Seq of List.  I then started experimenting with other functions when I found Seq.Collect – which was perfect.  So I created a function like this:

  1. member this.GetC1() =
  2.     database
  3.  
  4. member this.GetL1() =
  5.     let numberOfTransactions = this.GetC1().Count
  6.  
  7.     this.GetC1()
  8.         |> Seq.collect(fun d -> d.Items)
  9.         |> Seq.countBy(fun i -> i)
  10.         |> Seq.map(fun (t,i) -> t, i, float i/ float numberOfTransactions)
  11.         |> Seq.filter(fun (t,i,p) -> p >= support)
  12.         |> Seq.map(fun (t,i,p) -> t,i)
  13.         |> Seq.sort
  14.         |> Seq.toList

Note that the numberOfTransactions is for the database, not the individual items in the List<Item>.  And the results match the example:

imageimage

So this is great.  My next stop was to build a list of pair combinations of the remaining values

image

The trick is that is not a Cartesian join of the original sets – it is only the surviving sets that are needed.  My first attempt looked like:

  1. let C1 = database
  2.  
  3. let L1 = C1
  4.         |> Seq.map(fun t -> t.Items)
  5.         |> Seq.collect(fun i -> i)
  6.         |> Seq.countBy(fun i -> i)
  7.         |> Seq.map(fun (t,i) -> t, i, float i/ float numberOftransactions)
  8.         |> Seq.filter(fun (t,i,p) -> p >= support)
  9.         |> Seq.toArray
  11. let C2A = L1
  12.             |> Seq.map(fun (x,y,z) -> x)
  13.             |> Seq.toArray
  14. let C2B = L1
  15.             |> Seq.map(fun (x,y,z) -> x)
  16.             |> Seq.toArray
  17. let C2 = C2A |> Seq.collect(fun x -> C2B |> Seq.map(fun y -> x+y))
  18. C2   

With the output like this:

image

I was running out of Saturday morning so I went over to stack overflow and got a couple of responses.  I was on the right track with the concat, but I didn’t think about the List.Filter(), which would prune my list.  With this in mind, I copied Mark’s code and got what I was looking for

  1. member this.GetC2() =
  2.     let l1Itemset = this.GetL1()
  3.                     |> Seq.map(fun (i,s) -> i)
  4.  
  5.     let itemset =
  6.         l1Itemset
  7.             |> Seq.map(fun x -> l1Itemset |> Seq.map(fun y -> (x,y)))
  8.             |> Seq.concat
  9.             |> Seq.filter(fun (x,y) -> x < y)
  10.             |> Seq.sort
  11.             |> Seq.toList         
  12.     
  13.     let listContainsItem(l:List<string>, a,b) =
  14.             l.Contains(a) && l.Contains(b)
  15.     
  16.     let someFunctionINeedToRename(l1:List<string>, l2)=
  17.             l2 |> Seq.map(fun (x,y) -> listContainsItem(l1,x,y))
  18.  
  19.     let itemsetMatches = this.GetC1()
  20.                             |> Seq.map(fun t -> t.Items)
  21.                             |> Seq.map(fun i -> someFunctionINeedToRename(i,itemset))
  22.  
  23.     let itemSupport = itemsetMatches
  24.                             |> Seq.map(Seq.map(fun i -> if i then 1 else 0))
  25.                             |> Seq.reduce(Seq.map2(+))
  26.  
  27.     itemSupport
  28.         |> Seq.zip(itemset)
  29.         |> Seq.toList

So now I have C2 filling correctly:

image

 

Taking the results, I needed to get L2.

image

That was much simpler that getting C2 –> here is the code:

  1. member this.GetL2() =
  2.     let numberOfTransactions = this.GetC1().Count
  3.     
  4.     this.GetC2()
  5.             |> Seq.map(fun (i,n) -> i,n,float n/float numberOfTransactions)
  6.             |> Seq.filter(fun (i,n,p) -> p >= support)
  7.             |> Seq.map(fun (t,i,p) -> t,i)
  8.             |> Seq.sort
  9.             |> Seq.toList    

And when I run it – it matches this example exactly:

image

Finally, I added in a C# and L3.  This code is identical to the C2/L2 code with one exception: mapping a triple and not a tuple:  The C2 code maps like this

  1. let itemset =
  2.     l1Itemset
  3.         |> Seq.map(fun x -> l1Itemset |> Seq.map(fun y -> (x,y)))
  4.         |> Seq.concat
  5.         |> Seq.filter(fun (x,y) -> x < y)
  6.         |> Seq.sort
  7.         |> Seq.toList     

and the C3 code looks like this (took me 15 minutes to figure out line 3 below):

  1. let itemset =
  2.     l2Itemset
  3.         |> Seq.map(fun x -> l2Itemset |> Seq.map(fun y-> l2Itemset |> Seq.map(fun z->(fst x,fst y,snd z))))
  4.         |> Seq.concat
  5.         |> Seq.collect(fun d -> d)
  6.         |> Seq.filter(fun (x,y,z) -> x < y && y < z)
  7.         |> Seq.distinct
  8.         |> Seq.sort
  9.         |> Seq.toList    

With the C3 and L3 matching the example also:

image

image

 

I was now ready to put in the elevator data into the analysis.  I think I am getting better at F# because I did the mapping, filtering, and transformation of the data from the server without looking at any other material and it look only 15 minutes.

  1. type public ElevatorBuilder() =
  2.     let connectionString = ConfigurationManager.ConnectionStrings.["localData2"].ConnectionString;
  3.  
  4.     member public this.GetElevatorTransactions() =
  5.         let transactions = this.GetElevators()
  6.                               |> Seq.map(fun e ->this.ConvertElevatorToTransaction(e))
  7.         let transactionsList = new System.Collections.Generic.List<Transaction>(transactions)
  8.         transactionsList
  9.  
  10.     member public this.ConvertElevatorToTransaction(i: string, t:string, c:string, s:string) =
  11.         let items = new System.Collections.Generic.List<String>()
  12.         items.Add(t)
  13.         items.Add(c)
  14.         items.Add(s)
  15.         let transaction = {TID=i; Items=items}
  16.         transaction
  17.  
  18.     member public this.GetElevators () =
  19.         SqlConnection.GetDataContext(connectionString).ElevatorData201402
  20.             |> Seq.map(fun e -> e.ID, e.EquipType,e.Capacity,e.Speed)
  21.             |> Seq.filter(fun (i,et,c,s) -> not(String.IsNullOrEmpty(et)))
  22.             |> Seq.filter(fun (i,et,c,s) -> c.HasValue)
  23.             |> Seq.filter(fun (i,et,c,s) -> s.HasValue)
  24.             |> Seq.map(fun (i,t,c,s) -> i, this.CatagorizeEquipmentType(t),c,s)
  25.             |> Seq.map(fun (i,t,c,s) -> i,t,this.CatagorizeCapacity(c.Value),s)
  26.             |> Seq.map(fun (i,t,c,s) -> i,t,c,this.CatagorizeSpeed(s.Value))
  27.             |> Seq.map(fun (i,t,c,s) -> i.ToString(),t,c,s)

The longest part was aggregating the free-form text of the Equipment Type field (here is partial snip, you get the idea…)

  1. member public this.CatagorizeEquipmentType(et: string) =
  2.     match et.Trim() with
  3.         | "OTIS" -> "OTIS"
  4.         | "OTIS (1-2)" -> "OTIS"
  5.         | "OTIS (2-1)" -> "OTIS"
  6.         | "OTIS hydro" -> "OTIS"
  7.         | "OTIS, HYD" -> "OTIS"
  8.         | "OTIS/ ASHEVILLE " -> "OTIS"
  9.         | "OTIS/ MOUNTAIN " -> "OTIS"
  10.         | "OTIS/#1" -> "OTIS"
  11.         | "OTIS/#19 " -> "OTIS"

Assigning categories for speed and capacity was a snap using F#

  1. member public this.CatagorizeCapacity(c: int) =
  2.     let lowerBound = (c/25 * 25) + 1
  3.     let upperBound = lowerBound + 24
  4.     lowerBound.ToString() + "-" + upperBound.ToString()        
  5.  
  6. member public this.CatagorizeSpeed(s: int) =
  7.     let lowerBound = (s/50 * 50) + 1
  8.     let upperBound = lowerBound + 49
  9.     lowerBound.ToString() + "-" + upperBound.ToString()    

With this in hand, I created a Console app that takes the 27K records and pushes them though the apriori algorithm:

  1. private static void RunElevatorAnalysis()
  2. {
  3.     Stopwatch stopwatch = new Stopwatch();
  4.     stopwatch.Start();
  5.     ElevatorBuilder builder = new ElevatorBuilder();
  6.     var transactions = builder.GetElevatorTransactions();
  7.     stopwatch.Stop();
  8.     Console.WriteLine("Building " + transactions.Count + " transactions took: " + stopwatch.Elapsed.TotalSeconds);
  9.     var apriori = new Apriori(transactions, .1, .75);
  10.     var c2 = apriori.GetC2();
  11.     stopwatch.Reset();
  12.     stopwatch.Start();
  13.     var l1 = apriori.GetL1();
  14.     Console.WriteLine("Getting L1 took: " + stopwatch.Elapsed.TotalSeconds);
  15.     var l2 = apriori.GetL2();
  16.     Console.WriteLine("Getting L2 took: " + stopwatch.Elapsed.TotalSeconds);
  17.     var l3 = apriori.GetL3();
  18.     Console.WriteLine("Getting L3 took: " + stopwatch.Elapsed.TotalSeconds);
  19.     stopwatch.Stop();
  20.     Console.WriteLine("–L1");
  21.     foreach (var t in l1)
  22.     {
  23.         Console.WriteLine(t.Item1 + ":" + t.Item2);
  24.     }
  25.     Console.WriteLine("–L2");
  26.     foreach (var t in l2)
  27.     {
  28.         Console.WriteLine(t.Item1 + ":" + t.Item2);
  29.     }
  30.     Console.WriteLine("–L3");
  31.     foreach (var t in l3)
  32.     {
  33.         Console.WriteLine(t.Item1 + ":" + t.Item2);
  34.     }
  35. }

I then made an offering to the F# Gods and hit F5:

image

Doh!  The gods were not pleased.  I then went back to my initial filtering function and added a Seq.Take(25000) and the results:

image

So there a couple of things to draw from this exercise.

1) Apriori Algorithm is the wrong classification technique for this dataset.  I had to bring the support way down (10%) to even get any readings.  Also, there is too much dispersion of the values.  This kind of algorithm is much better with N number of a smaller set of data values versus a fixed number of large values.

2) Even so, how cool is this?  Compare the files just to make the C#/OO work versus with F#

imageimage

And the Total LOC is 539 for C# versus 120 for F# – and the F# can be optimized using a better way to create search and itemsets.  Hard-coding each level was a hack I did to get thing working and give me an understanding of how AA works.  I bet this can be consolidated to well under 75 lines without sacrificing readability

3) I think the StackOverflow exception is because I am doing a Cartesian join and then paring the result.  Using one of the other techniques suggested on SO will give much better results.

I any event, what a fun project!  I can’t wait to optimize this and perhaps throw a different algorithm at the dataset in the coming weeks.

 

 

 

Filed under Analytics, F#, Open Data

One Response to Apriori Algorithm and F# Using Elevator Inspection Data

  1. Pingback: F# Weekly #12, 2014 | Sergey Tihon's Blog

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

%d bloggers like this: