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

Post a Comment

Popular posts from this blog

A conceptual machine for cloning a human driver

-
Image
If anything else, a Machine Learning practitioner has to get a global view and think on how far our conceptual machines can go. This is a little tale of my recent experience with Deep Learning. To start with, say that I am enrolled in the Udacity’s nanodegree inSelf Driving Car Engineer . Here we are learning the techniques needed for building a car controller capable of driving at the human level. The interesting part of the course (to be read as where one truly learns) is in the so called projects: these are nothing but assignments in which the student has to solve a challenging task, mainly by using Convolutional Neural Networks (convnets), the most well-known Deep Learning models. So far, the most mind-blowing task and the focus of this entry is project 3, were we have to record our driving behavior in a car simulator and let a convnet to clone it and successfully generalize the act of driving. It is remarkable that a convnet learns to control the car from raw color images jointly
Read more

Data Streams and VFML

-
We live in a technological world crowded of information. Every device we can think of can give us a bunch of such data, usually in the form of a flow or stream of information in, more or less, real time . In this particular situation classical knowledge discovery mechanisms (like our loved C4.5, a decision tree developed by Quinlan) are completely unable of extract a correct model of the situation. But, what is so special with flows of data? Following the words of Gama and Rodriques: a data stream is an ordered sequence of instances that can be read only once or a small number of times using limited computing and storage capabilities. These sources of data are characterized by being open-ended, following at high speed, and generated by non-stationary distributions in dynamic environments . So, to properly handle this kind of knowledge the learning algorithm has to learn on line and process massive amounts of data increasing the challenges to be faced. Let's hold one's breath w
Read more

Data Analytics Plus Big Data: A Win-win Strategy

-
We live in a dynamic world where new technologies arise, dominate for a brief blink of an eye and then fall to oblivion rapidly. A part from the academia domain, it is interesting to check what are the current trends in the industry. Or even better: see the whole picture without discriminating. In this regard, a nice analytics tool is found in Google Trends, which allow us to track our terms of interest. The following chart shows the search interest for Machine Learning and Data Analytics . In a similar scale I depicted the search interest for Data Analytics and Big Data . As it is clearly noticeable, knowing both disciplines can open many doors in the industry. Finally, as top and also rising queries, Hadoop is the most popular term.
Read more