From Market Baskets to Databases: Association Rule Mining

What do the customers buy? Which products are bought together? With these two short questions the field of association rule (AR) mining makes its appearance. In this field of ML, the original aim was to find associations and correlations between the different items that customers place in their shopping market. More generally, the goal of AR is to find frequent and interesting patterns, associations, correlations, or causal structures among sets of items or elements in large databases and put these relationships in terms of association rules. AR is an important part of the unsupervised learning paradigm, so the algorithm has not the presence of an expert to teach it during the training stage.


Why AR mining may be so important? Many commercial applications generate huge amounts of unlabeled data (just think of Facebook for a moment), so our favorite classifier system will not work in this environment. With AR we can exploit such databases and extract any kind of useful information, and rule-based systems are a well known to us...


Note that there are two main types of ARs: (1) binary or qualitative rules, and (2) quantitative rules. For this article I will use qualitative due to its simplicity.



Association Rule Mining with Apriori

Apriori is the most famous AR miner out there. With this algorithm we can find the most frequent itemsets, that is, those itemsets which appear most often in the database. Its simplicity can be summarized by the following code:


k := 1

generate frequent itemsets (support count >= min support count) of length 1

repeat until no frequent itemsets are found:

k := k + 1

generate itemsets of size k from the k - 1 frequent itemsets

compute the support of each candidate by scanning through the database


But this article is focused on rule generation. How do we obtain the association rules from the previously found frequent itemsets? That is definitely tricky. To obtain the desired rules we have to obtain all the possible combinations (without repetition) from every frequent itemset and check if the confidence of every rule formed has a confidence greater or equal than a minimum threshold, the minimum confidence. Let's see this with the following example: suppose we have the frequent itemset {B,C,D}, where B, C, and D are items obtained from the transaction database. How many rules will this itemset generate? The answer is a maximum of six rules: because we work with qualitative rules, there are (2^k)-2, where k is the size of the set, in our case k = 3. The rules are:

BC => E, BE => C, CE => B, B => CE, C => BE, and E => BC. The idea is the following:


for itemsInAntecedent := 1 to k

first := getFirstItemFromItemset

element := first

do

do

setConsequentItemActive( first )

for j := 1 to itemsInAntecedent

element := getNextElementFromItemset( element )

setConsequentItemActive( element )

endfor

inverseAntecedentFromConsequentInRule

setRuleConfidence

if minConf <= ruleConfidence then

store rule

endif

while first <> lastItemFromItemset and itemsInAntecedent > 1 then

first := getNextElementFromItemset( first )

element := first

while first <> lastItemFromItemset

if itemsInAntecedent = 1 and numElements > 2 then

setConsequentItemActive( lastElement )

setRuleConfidence

if minConf <= ruleConfidence then

store rule

endif

endif

endfor


As it can be appreciated, the algorithm is tricky enough to have a wannabe PhD for a couple of days wondering (from the very scratch) how to obtain the desired rules.


References

R. Agrawal and R. Srikant. Fast Algorithms for Mining Association Rules. Technical report, IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120, Sep 1994.

Comments