Replies to This Discussion

Permalink Reply by John Gins on January 31, 2010 at 3:58pm

I have done over 30+ Market Basket Analysis jobs in the last 15 years.

There is usually some form of register ID or transaction ID along with store ID and time stamp. Also if the store has a loyalty card program the the Individual or household ID can be very useful.

About ten years ago I decided to write my own code to do this type of analysis. I did this because none of the tools that I found commercially available at the time would scale or could be run in parallel. I also found that most comercial could relied on the 20 year old concept from IBM (Anticedent and Consequent) when a Market Basket does not imply any order.

There are two pillars my code (unix shell script and perl) depend on. The data is sorted so that all the transactions are available and that i am only going to determine item pairs by applying "Yule's Q" in order to selct item pairs that go together with high odds. I will use Graphical techniques, transitive closure, to build unique groups of items, these groups partition the item universe.

If you are a coder you can easily write the pair counting your self as follows
1 limit the number of pair counts so that you do not run out of memory. My code wrote pair counts to disk when the number of pairs I was tracking reached 1M. (i just flushed the memory to disk and freed the memory)
2 inorder to do pair analysis you only need to track three things. The total number of baskets. How many baskets does each item fall into. Given a pair of items (a,b) how many baskets have both items a and b. (Becareful (a,b) = (b,a) I usually order the item numbers so that I am not doing double accounting.) This can be as bad as an (N*(N-1)+N+1) memory problem with N equal to the number of items.
3 if you are required to flush the counts to disk then gather them togeter before determining the ODDS of a pair occuring and applying Yule's Q to the ODDS.

Steps 1 and 2 will take 97% of the analysis time. Steps 3 and the following Transitive closure are very fast because the amount of data is greatly reduced. (If you can effectively divide the data into multiple streams preserving the basket then step 2 can be done in parallel.

I recently tested KXEN's KAR algorith to count pairs. This will work with the correct parameters set. However it will run out of memory, if you are not careful, since it does not cache intermediate counts to disk.