Association Rule Problem: Part 3

After spending a couple of weeks working though the imperative code, I decided to approach the problem from a F#/functional point of view.  Going back to the original article, there are several steps that McCaffrey walks through:

  • Get a series of transactions
  • Get the frequent item-sets for the transactions
  • For each item-set, get all possible combinations.  Each combination is broken into an antecedent and consequent
  • Apply the frequency of each antecedent in all transactions
  • If the frequency of the combination is greater than the confidence level, include it in the final set

For the purposes of this article, Step #1 and Step #2 were already done.  My code starts with step #3.  Instead of for..eaching and if..thening my way though the item-sets, I decided to look at how permutations and combinations are done in F#.  Interestingly, one of the first articles on permutations and combinations on Google is from McCaffrey in MSDN from four years ago.  Unfortunately, this article was of limited use because the code is decidedly non-functional so it might as well been written in C# (this was pointed out in the comments).  So going to Stack Overflow, there are plenty of good examples of getting combinations in F# on SO and elsewhere.  After playing with the code samples for a bit (my favorite one was this), it hit me that the ordinal positions are the same for an array of X size.  So going back to McCaffrey’s example, there is only item-sets of 2 and 3 length.  Therefore, I can hard-code the results and leave the actual calculation for another time.

  1. static member GetCombinationsForDouble(itemSet: int[]) =
  2.     let combinations =  new List<int[]*int[]*int[]>()
  3.     combinations.Add(itemSet, [|itemSet.[0]|],[|itemSet.[1]|])
  4.     combinations
  5.  
  6. static member GetCombinationsForTriple(itemSet: int[]) =
  7.     let combinations =  new List<int[]*int[]*int[]>()
  8.     combinations.Add(itemSet, [|itemSet.[0]|],[|itemSet.[1];itemSet.[2]|])
  9.     combinations.Add(itemSet, [|itemSet.[1]|],[|itemSet.[0];itemSet.[2]|])
  10.     combinations.Add(itemSet, [|itemSet.[2]|],[|itemSet.[0];itemSet.[1]|])
  11.     combinations.Add(itemSet, [|itemSet.[0];itemSet.[1]|],[|itemSet.[2]|])
  12.     combinations.Add(itemSet, [|itemSet.[0];itemSet.[2]|],[|itemSet.[1]|])
  13.     combinations.Add(itemSet, [|itemSet.[1];itemSet.[2]|],[|itemSet.[0]|])
  14.     combinations

I used a tuple to represent the antecedent array and consequent array values.  I then spun up a unit test to compare results based on McCaffrey’s detailed example:

  1. [TestMethod]
  2. public void GetValuesForATriple_ReturnsExpectedValue()
  3. {
  4.     var expected = new List<Tuple<int[], int[]>>();
  5.     expected.Add(Tuple.Create<int[], int[]>(new int[1] { 3 }, new int[2] { 4, 7 }));
  6.     expected.Add(Tuple.Create<int[], int[]>(new int[1] { 4 }, new int[2] { 3, 7 }));
  7.     expected.Add(Tuple.Create<int[], int[]>(new int[1] { 7 }, new int[2] { 3, 4 }));
  8.     expected.Add(Tuple.Create<int[], int[]>(new int[2] { 3, 4 }, new int[1] { 7 }));
  9.     expected.Add(Tuple.Create<int[], int[]>(new int[2] { 3, 7 }, new int[1] { 4 }));
  10.     expected.Add(Tuple.Create<int[], int[]>(new int[2] { 4, 7 }, new int[1] { 3 }));
  11.  
  12.     var itemSet = new int[3] { 3,4,7};
  13.     var actual = FS.AssociationRuleProgram2.GetCombinationsForTriple(itemSet);
  14.  
  15.     Assert.AreEqual(expected.Count, actual.Count);
  16. }

A couple of things to note about the unit test:

1) The rules about variable naming and whatnot that apply in business application development quickly fall down when applied to scientific computing.  For example, there is no way that this

List<Tuple<int[], int[]>> expected = new List<Tuple<int[], int[]>>();

is more readable that this

var expected = new List<Tuple<int[], int[]>>();

In fact, it is less readable.  The use of complex data structures and algorithms force a different set of naming conventions.  Applying Fx-Cop or other framework naming conventions to scientific programming is as useful as applying scientific naming conventions to framework development.  If it is a screw, use a screwdriver.  If it is a nail, user a hammer…

2) I don’t have a good way of comparing the results of a tuple of paired arrays for equivalence – there is certainly nothing out of the box in Microsoft.VisualStudio.TestTools.UnitTesting.  I toyed (briefly) with creating a method to compare equivalence in arrays but I did not in the interest of time.  That would be a welcome additional to the testing namespace.

Sure enough, running the unit test using McCaffrey’s data all run green.

With step 3 knocked out, I now needed to determine the frequency of the antecedent in the transactions list.  This step is better broken down into a couple of sub-steps.  I used McCaffrey’s detailed example of 3,4,7 as proof of correctness in my unit tests:

image

I need a way of taking the antecedent of 3, and comparing it to all transactions (which are arrays) to see how often it appears.  As an additional layer of complexity, that 3 is not an int, it is an array (all be it an array of one).  I could not find a equivalent question on StackOverflow (meaning I probably am asking the wrong question), so I went ahead of made a mental model where I would map the TryFindIndex function against each item of subset and see if that value is in the original set.  The result is a tuple with the original value and the ordinal position in the set.  The key thing is that if the item was not found, it returns “None”.  So I just have to filter on that flag and if the result of the filter is greater than 1, I know that something was not found and the functional can return false

image


In code, it pretty much looks like the way I just described it:

  1. static member SetContainsSubset(set: int[], subset: int[]) =
  2.     let notIncluded = subset
  3.                         |> Seq.map(fun i -> i, set |> Seq.tryFindIndex(fun j -> j = i))
  4.                         |> Seq.filter(fun (i,j) -> j = None )
  5.                         |> Seq.toArray
  6.     if notIncluded.Length > 0 then false else true

And I generated my unit tests out of the example too: 

  1. [TestMethod]
  2. public void SetContainsSubsetUsingMatched_ReturnsTrue()
  3. {
  4.     var set = new int[4] { 1, 3, 4, 7 };
  5.     var subset = new int[3] { 3, 4, 7 };
  6.  
  7.     Boolean expected = true;
  8.     Boolean actual = FS.AssociationRuleProgram2.SetContainsSubset(set, subset);
  9.  
  10.     Assert.AreEqual(expected, actual);
  11. }
  12.  
  13. [TestMethod]
  14. public void SetContainsSubsetUsingUnMatched_ReturnsFalse()
  15. {
  16.     var set = new int[3] { 1, 4, 7 };
  17.     var subset = new int[3] { 3, 4, 7 };
  18.  
  19.     Boolean expected = false;
  20.     Boolean actual = FS.AssociationRuleProgram2.SetContainsSubset(set, subset);
  21.  
  22.     Assert.AreEqual(expected, actual);
  23.  
  24. }

With this supporting function ready, I can then apply it to an array and see how many trues I get.  That is the Count value in Figure 2 of the article.  Seq.Map fits this task perfectly. 

  1. static member ItemSetCountInTransactions(itemSet: int[], transactions: List<int[]>) =
  2.     transactions
  3.         |> Seq.map(fun (t) -> t, AssociationRuleProgram2.SetContainsSubset(t,itemSet))
  4.         |> Seq.filter(fun (t,f) -> f = true)
  5.         |> Seq.length

And the subsequent unit test also runs green

  1. [TestMethod]
  2. public void CountItemSetInTransactions_ReturnsExpected()
  3. {
  4.     List<int[]> transactions = new List<int[]>();
  5.     transactions.Add(new int[] { 0, 3, 4, 11 });
  6.     transactions.Add(new int[] { 1, 4, 5 });
  7.     transactions.Add(new int[] { 3, 4, 6, 7 });
  8.     transactions.Add(new int[] { 3, 4, 6, 7 });
  9.     transactions.Add(new int[] { 0, 5 });
  10.     transactions.Add(new int[] { 3, 5, 9 });
  11.     transactions.Add(new int[] { 2, 3, 4, 7 });
  12.     transactions.Add(new int[] { 2, 5, 8 });
  13.     transactions.Add(new int[] { 0, 1, 2, 5, 10 });
  14.     transactions.Add(new int[] { 2, 3, 5, 6, 7, 9 });
  15.  
  16.     var itemSet = new int[1] { 3 };
  17.  
  18.     Int32 expected = 6;
  19.     Int32 actual = FS.AssociationRuleProgram2.ItemSetCountInTransactions(itemSet, transactions);
  20.  
  21.     Assert.AreEqual(expected, actual);
  22.  
  23. }

So with this in place, I am ready for the next column, the confidence column.  McCaffrey used the numerator of 3 which is shown here:

image

So I assume that this count is the number of times 3,4,7 show up in the the transaction set.  If so, the supporting function ItemSetCountInTransactions can also be used.  I created a unit test and it ran green

  1. [TestMethod]
  2. public void CountItemSetInTransactionsUsing347_ReturnsThree()
  3. {
  4.     List<int[]> transactions = new List<int[]>();
  5.     transactions.Add(new int[] { 0, 3, 4, 11 });
  6.     transactions.Add(new int[] { 1, 4, 5 });
  7.     transactions.Add(new int[] { 3, 4, 6, 7 });
  8.     transactions.Add(new int[] { 3, 4, 6, 7 });
  9.     transactions.Add(new int[] { 0, 5 });
  10.     transactions.Add(new int[] { 3, 5, 9 });
  11.     transactions.Add(new int[] { 2, 3, 4, 7 });
  12.     transactions.Add(new int[] { 2, 5, 8 });
  13.     transactions.Add(new int[] { 0, 1, 2, 5, 10 });
  14.     transactions.Add(new int[] { 2, 3, 5, 6, 7, 9 });
  15.  
  16.     var itemSet = new int[3] { 3,4,7 };
  17.  
  18.     Int32 expected = 3;
  19.     Int32 actual = FS.AssociationRuleProgram2.ItemSetCountInTransactions(itemSet, transactions);
  20.  
  21.     Assert.AreEqual(expected, actual);
  22.  
  23. }

So the last piece was to put it together in the GetHighConfRules method.  I did not change the signature

  1. static member GetHighConfRules(frequentItemSets: List<int[]>, transactions: List<int[]>, minConfidencePct:float) =
  2.     let returnValue = new List<Rule>()
  3.     let combinations = frequentItemSets |> Seq.collect (fun (a) -> AssociationRuleProgram2.GetCombinations(a))
  4.     combinations
  5.         |> Seq.map(fun (i,a,c ) -> i,a,c,AssociationRuleProgram2.ItemSetCountInTransactions(i,transactions))
  6.         |> Seq.map(fun (i,a,c,fisc) -> a,c,fisc,AssociationRuleProgram2.ItemSetCountInTransactions(a,transactions))
  7.         |> Seq.map(fun (a,c,fisc,cc) -> a,c,float fisc/float cc)
  8.         |> Seq.filter(fun (a,c,cp) -> cp > minConfidencePct)
  9.         |> Seq.iter(fun (a,c,cp) -> returnValue.Add(new Rule(a,c,cp)))
  10.     returnValue

 

Note that I did add a helper function to get Combinations based on the length of the array

  1. static member GetCombinations(itemSet: int[]) =
  2.     if itemSet.Length = 2 then AssociationRuleProgram2.GetCombinationsForDouble(itemSet)
  3.     else AssociationRuleProgram2.GetCombinationsForTriple(itemSet)

And when I run that from the console:

image

So this is pretty close.  McCaffrey allows for inversion of the numbers in the array (3:4 is not the same as 4:3) and I do not – but his supporting detail does not show that so I am not sure what is the correct answer.  In any event, this is pretty good.  The F# code can be refactored so that all combinations can be sent from an array.  In the mean time, here is all 43 lines of the program. 

  1. open System
  2. open System.Collections.Generic
  3.  
  4. type AssociationRuleProgram2 =
  5.  
  6.     static member GetHighConfRules(frequentItemSets: List<int[]>, transactions: List<int[]>, minConfidencePct:float) =
  7.         let returnValue = new List<Rule>()
  8.         let combinations = frequentItemSets |> Seq.collect (fun (a) -> AssociationRuleProgram2.GetCombinations(a))
  9.         combinations
  10.             |> Seq.map(fun (i,a,c ) -> i,a,c,AssociationRuleProgram2.ItemSetCountInTransactions(i,transactions))
  11.             |> Seq.map(fun (i,a,c,fisc) -> a,c,fisc,AssociationRuleProgram2.ItemSetCountInTransactions(a,transactions))
  12.             |> Seq.map(fun (a,c,fisc,cc) -> a,c,float fisc/float cc)
  13.             |> Seq.filter(fun (a,c,cp) -> cp > minConfidencePct)
  14.             |> Seq.iter(fun (a,c,cp) -> returnValue.Add(new Rule(a,c,cp)))
  15.         returnValue
  16.  
  17.     static member ItemSetCountInTransactions(itemSet: int[], transactions: List<int[]>) =
  18.         transactions
  19.             |> Seq.map(fun (t) -> t, AssociationRuleProgram2.SetContainsSubset(t,itemSet))
  20.             |> Seq.filter(fun (t,f) -> f = true)
  21.             |> Seq.length
  22.  
  23.     static member SetContainsSubset(set: int[], subset: int[]) =
  24.         let notIncluded = subset
  25.                             |> Seq.map(fun i -> i, set |> Seq.tryFindIndex(fun j -> j = i))
  26.                             |> Seq.filter(fun (i,j) -> j = None )
  27.                             |> Seq.toArray
  28.         if notIncluded.Length > 0 then false else true
  29.  
  30.     static member GetCombinations(itemSet: int[]) =
  31.         if itemSet.Length = 2 then AssociationRuleProgram2.GetCombinationsForDouble(itemSet)
  32.         else AssociationRuleProgram2.GetCombinationsForTriple(itemSet)
  33.  
  34.     static member GetCombinationsForDouble(itemSet: int[]) =
  35.         let combinations =  new List<int[]*int[]*int[]>()
  36.         combinations.Add(itemSet, [|itemSet.[0]|],[|itemSet.[1]|])
  37.         combinations
  38.  
  39.     static member GetCombinationsForTriple(itemSet: int[]) =
  40.         let combinations =  new List<int[]*int[]*int[]>()
  41.         combinations.Add(itemSet, [|itemSet.[0]|],[|itemSet.[1];itemSet.[2]|])
  42.         combinations.Add(itemSet, [|itemSet.[1]|],[|itemSet.[0];itemSet.[2]|])
  43.         combinations.Add(itemSet, [|itemSet.[2]|],[|itemSet.[0];itemSet.[1]|])
  44.         combinations.Add(itemSet, [|itemSet.[0];itemSet.[1]|],[|itemSet.[2]|])
  45.         combinations.Add(itemSet, [|itemSet.[0];itemSet.[2]|],[|itemSet.[1]|])
  46.         combinations.Add(itemSet, [|itemSet.[1];itemSet.[2]|],[|itemSet.[0]|])
  47.         combinations

Note how the code in the GetHighConfRules function matches almost one for one to the bullet points at the beginning of the post.  F# is a language where the code follows how you think, not the other way around.  Also note how the 43 lines of code compares to 136 lines of code in the C# example –> less noise, more signal.

 

Advertisements

One Response to Association Rule Problem: Part 3

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

Leave a Reply

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

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: