I wrote an article in the May 2014 issue of MSDN Magazine titled “Association Rule Learning”. See http://msdn.microsoft.com/en-us/magazine/dn683798.aspx.
Association Rule Learning (ARL) is a machine learning topic that is not quite as well-known as things such as neural networks and data clustering. The idea of ARL is best explained by an example. Suppose a supermarket has 10,000 total items in stock, numbered 0 through 9999. On a particular day customers buy items such as:
Customer 0 buys items: (0 3 4 11) = Transaction 0 Customer 1 buys items: (1 4 5) = Transaction 1 . . . Customer 9 buys items: (0 6 11) = Transaction 9
The idea of ARL is to extract rules from this data, along the lines of:
IF (0 3) THEN (5) IF (2 4 6) THEN (8 12) etc.
The first rule can be interpreted, “if a customer buys items 0 and 3, then there’s a high probability they also buy item 5.”
ARL has two main steps, both of them quite difficult. The first task is to extract what are called frequent item sets from the source data of all transactions. The idea is to prune down the amount of source data, and eliminate transactions that are so rare they might give misleading information. For example, if there are just three or four transactions that contain both beer and mushrooms, you wouldn’t want to necessarily conclude that people who buy beer are highly likely to buy mushrooms, because your data sample is too limited. Frequent item set extraction is surprisingly difficult.
The second step in ARL is to take frequent item sets and generate rules. This is also much, much trickier than you might expect. The main problem is that even when the frequent item sets have been pruned to a relatively small size, it’s still not possible to generate all possible rules because of combinatorial explosion.