Review new book: Practical Data Analysis

Hi all,

I was invited by the Packtpub team to review the book Practical Data Analysis by Hector Cuesta.  I started reading it for the last two weeks and I really enjoyed the topics approach covered by the book.

The book goes through the data science hot topics by presenting several practical examples of data exploration, analysis and even some machine learning techniques. Python as the main platform for the sample codes was a perfect choice, at my opinion. Since Python has becoming more popular at scientific community. 

The book brings several examples in  several science study fields such as stock prices, sentiment analysis on social networks,  biology modelling scenarios, social graphs,  MapReduce, text classification,  data visualisation, etc.  Many novel libraries and tools are presented including Numpy, Scipy, PIL, Python, Pandas, NLTK, IPython, Wakari ( I really liked a dedicated chapter for this excellent tool for scientific python environment on-line),  etc.  It also covers NoSQL databases such as MongoDB and visualisation libraries like D3.js.

I believe the biggest value proposition of this book is that it brings together in one book several tools and how they can be applied on data science. Many tools mentioned lacks further examples or documentation, which this book can assist any data scientist on this task.

However, the reader must not expect learn machine learning and data science in this book.  The theory is  scarce, and I believe it was not the main goal of the author for this book. For anyone looking to learn data science, this is not the right book. It is focused on who desires an extra resource for sample codes and inspirations, it will be a great pick!

The source code is available on Github, but you can explore them better explained inside the book, including illustrations. To sum up, I have to congratulate Hector for his effort writing this book. For the Scientific community, including the Python group, they will really enjoy this book! I really missed more material about scientific stack software installations, since for the beginners it can be really painful.  But in overall, it was well written focused on practical problems! A guide for any scientists.

For me the best chapters were the Chapter 6: Simulation of Stock Prices, the visualisation using D3.js was great, and the last chapter, 14, about On-line Data Analysis with IPython and Wakari. It's the first time I see Wakari covered in a book! Everyone who works with scientific Python today must give a chance some day to experiment this on-line tool! It's awesome!

Congratulations to PacktPub and Hector for the book!

Regards,

Marcel Caraciolo

Graph Based Recommendations using "How-To" Guides Dataset

Hi all,

In this post I'd like to introduce another approach for recommender engines using graph concepts to recommend novel and interesting items. I will build a graph-based how-to tutorials recommender engine using the data available on the website SnapGuide (By the way I am a huge fan and user of this tutorials website), the graph database Neo4J and the graph traversal language Gremlin.

What is SnapGuide ?

Snapguide is a web service for anyone who wants to create and share step-by-step "how to guides".  It is available on the web and IOS app. There you can find several tutorials with easy visual instructions for a wide array of topics including cooking, gardening, crafts, projects, fashion tips and more.  It is free  and anyone is invitide to submit guides in order to share their passions and expertise with the community.  I have extracted from their website for only research purposes the corpus of tutorials likes. Several users may like the tutorial and this signal can be quite useful to recommend similar tutorials based on what other users liked.  Unfortunately I can't provide the dataset for download but the code you can follow below for your own data set.

Snapguide 

Getting Started with Neo4J

To create your own graph with Neo4J you will need to use Java/Groovy to explore it.  I found Bulbflow, it is a open-source Python ORM  for graph databases and supports puggable backends using Blueprints standards.  In this post I used it to connect to Neo4j Servers.  The snippet code below is a simple example of Bulbflow in action by creating some edges and vertexes.

>>> from people import Person, Knows
>>> from bulbs.neo4jserver import Graph
>>> g = Graph()
>>> g.add_proxy("people", Person)
>>> g.add_proxy("knows", Knows)
>>> james = g.people.create(name="James")
>>> julie = g.people.create(name="Julie")
>>> g.knows.create(james, julie)

Generating our tutorials Graph

I decided to define my graph schema in order to map the raw data into a property graph so the traversals required to get recommendations of which tutorials to check could be natural as possible.

SnapGuide Graph Schema

The data will be inserted into the graph database Neo4J  The code belows creates a new Neo4J graph with all the data set.

#-*- coding: utf-8 -*-
from bulbs.neo4jserver import Graph
from nltk.tag.hunpos import HunposTagger
from nltk.tokenize import word_tokenize

ht = HunposTagger('en_wsj.model')

likes = open('likes.csv')
tutorials = open('tutorials.csv')
users = open('users.csv')

g = Graph()

def filter_nouns(words):
   return [word.lower() for word, cat in words if cat in ['NN', 'NNP', 'NNPS']]

#Loading tutorials and categories
for tutorial in tutorials:
    tutorial = tutorial.strip()
    try:
 ID, title, likes, category = tutorial.split(';')
    except:
 try:
      ID, title, category = tutorial.split(';')
 except:
      t = tutorial.split(';')
      ID, title, category = t[0], t[1].replace('&Yuml', ''), t[-1] 
   
     tut =  g.vertices.create(type='Tutorial', tutorialId=int(ID), title=title)
     keywords = filter_nouns(ht.tag(word_tokenize(tutorial.split(';')[1])))
     keywords.append(category)

     for keyword in keywords:
 resp = g.vertices.index.lookup(category=keyword)
 if resp is None:
      ct = g.vertices.create(type='Category', category = keyword)
 else:
      ct = resp.next()
 g.edges.create(tut,'hasCategory', ct)

#Loading user dataset.

for user in users:
     user = user.strip()
     username = user.split(';')[0]
 
     user = g.vertices.create(type='User', userId=username)

#Loading the likes dataset.
for like in likes:
    like = like.strip()
    item_id, user_id = like.split(';')
    p = g.vertices.index.lookup(tutorialId=int(item_id))
    q =  g.vertices.index.lookup(userId=user_id)
    g.edges.create(q.next(), 'liked', p.next())

There are three input files: tutorials.dat, users.dat and likes.dat. The file tutorials.dat contains the list of  tutorials. Each row has 2 columns: tutorialId, title and category. The file users.dat contains the list of users.  Each row contains the columns:  userID, user name.  Finally  the likes.dat includes the tutorials that a user marked their interest. Each row of the raw file has : userId and movieId.

Given that there are more than 1 million likes, it will take some time to process all the data. An important note before going on. Don't forget to create the vertices indexes,  if you forget your queries it will take ages to proccess.

1. //These indexes are a must, otherwise querying the graph database will take so looong
2. g.createKeyIndex('userId',Vertex.class)
3. g.createKeyIndex('tutorialId',Vertex.class)
4. g.createKeyIndex('category',Vertex.class)
5. g.createKeyIndex('title',Vertex.class)

Before moving on to recommender algorithms, let's make sure the graph is ok.

For instance,  what is the distribution of keywords amongst the tutorials repository ?

1. //Distribution frequency of Categories

   def dist_categories(){

     m = [:]

    g.V.filter{it.getProperty('type')=='Tutorial'}.out('hasCategory').category.groupCount(m).iterate() 

   return m.sort{-it.value}

   }

>>> script = g.scripts.get('dist_categories')
>>> categories = g.gremlin.execute(script, params=None)
>>> sorted(categories.content.items(), key=lambda keyword: -keyword[1])[:10]

[(u'food', 4537), (u'make', 3840), (u'arts-crafts', 1609), (u'cook', 1362), (u'desserts', 1247), (u'beauty', 1108), (u'technology', 943), (u'drinks', 587), (u'home', 508), (u'chicken', 452)]

What about the average number of likes per tutorial ?

1. //Get the average number of likes per tutorial
   def avg_likes(){
   return  
   g.V.filter{it.getProperty('type')=='Tutorial'}.transform{it.in('liked').count()}.mean() 
   }

>>> script = g.scripts.get('avg_likes')
>>>likes = g.gremlin.command(script, params=None)
>>>likes

111.089116326

Trasversing the Tutorials Graph

Now that the data is represented as graph, let's make some queries. Behind the scene what we make are some traversals.  In recommender systems  there are two general typs of recommendation approaches: the collaborative filtering and content-based one.

In collaborative, the liking behavior of users is correlated in order to recommend the favorites of one user to another, in this case let's find the similar user.

I like the tutorials Amanda preferred, what other tutorials does Amanda like that I haven't seen ?

Otherwise, the content-base strategy is based on the features of a recommendable item. So the attributes are analyzed in order to find other similar items with analogous features.

I  like food tutorials, what other food tutorials are there ?

Making Recommendations

Let's begin with collaborative filtering.  I will use some complex traversal queries at our graph.  Let's start with the tutorial: "How to Make Sous Vide Chicken at Home".  Yes,  I love chicken! :)

Great dish by the way!

Which users liked Make Sous Vide Chicken at Home ?

1. //Get the users who liked a tutorial
   def users_liked(tutorial){
      v = g.V.filter{it.getPropery('title') == tutorial}
      return v.inE('liked').outV.userId[0..4]
   }

>>> tuts = g.vertices.index.lookup(title='Make Sous Vide Chicken at Home')
>>> tut = tuts.next()
>>> tut.title 
Make Sous Vide Chicken at Home
>>> tut.tutorialId
11890
>>> tut.type  
Tutorial
>>> script = g.scripts.get('n_users_liked')
>>> users_liked = g.gremlin.command(script, params={'tutorial': 'Make Sous Vide Chicken at Home'})
>>> users_liked
1000

This traversal doesn't provide us useful information, but we could put in action now the collaborative filtering with a extended query:

Which users liked Make Sous Vide Chicken at Home and what other tutorials did they liked most in common to ?

1. //Get the users who liked the tutorial and what other tutorials did they like too ?
   def similar_tutorials(tutorial){
   v = g.V.filter{it.getProperty('title') == tutorial}
   return v.inE('liked').outV.outE('liked').inV.title[0..4]
   }
   
   

>>>> script = g.scripts.get('similar_tutorials')
>>>> similar_tutorials = g.gremlin.execute(script, params={'tutorial': 'Make Sous Vide Chicken at Home'})
>>> similar_tutorials.content

[u'Make Potato Latkes', u'Make Beeswax and Honey Lip Balm', u'Make Sous Vide Chicken at Home', u'Cook the Perfect & Simple Chicken Ramen Soup', u'Make a Simple (But Authentic) Paella on Your BBQ']

What is the query above express ?

It filters all users that liked the tutorial (inE('liked')) and find out what they liked (outV.outE('liked')), fetching the title of those tutorials (inV.title) . It returns the first five items ([0..4])

In recommendations we have to find the most-common purchased or liked itens.  Using Gremlin, we can work on a simple collaborative filtering algorithm by joining several steps together.

1. //Get similar tutorials
   def topMatches(tutorial){
       m = [:]
   v = g.V.filter{it.getProperty('title') == tutorial}
   v.inE('liked').outV.outE('liked').inV.title.groupCount(m).iterate()
       return m.sort{-it.value}[0..9]
   
   }

>>> script = g.scripts.get('topMatches')
>>> topMatches = g.gremlin.execute(script, params={'tutorial': 'Make Sous Vide Chicken at Home'})
>>> sorted(topMatches.content.items(), key=lambda keyword: -keyword[1])[:10]

{u'Make Cake Pops!!': 75, u'Make Sous Vide Chicken at Home': 1000, u'Make Potato Latkes': 124, u'Make Incredible Beef Jerky at Home Easily!': 131, u'Cook the Perfect & Simple Chicken Ramen Soup': 96, u'Make Mint Juleps': 74, u"Solve a 3x3 Rubik's Cube": 89, u'Cook Lamb Shanks Moroccan Style': 74, u'Make Beeswax and Honey Lip Balm': 75, u'Make an Aerium': 74}

This traversal will return a list of tutorials.  But you may notice if you get all matches, ther are many duplicates. It happens because who like  How to Make sous Vide Chicken At Home also like many of the same other tutorials.  The similarity between users in represented at collaborative filtering algorithms.

How many of How to Make sous Vide Chicken At Home highly correlated tutorials are unique ?

1. //Get the number of unique similar tutorials
   def n_similar_unique_tutorials(tutorial){
   v = g.V.filter{it.title == tutorial}
   return v.inE('liked').outV.outE('liked').inV.dedup.count()
   }
   
   //Get the number of similar tutorials
   def n_similar_tutorials(tutorial){
   v = g.V.filter{it.getProperty('title') == tutorial}
   return v.inE('liked').outV.outE('liked').inV.count()
   }

>>> script = g.scripts.get('n_similar_tutorials')
>>> similar_tutorials = g.gremlin.command(script, params={'tutorial': 'Make Sous Vide Chicken at Home'})
>>> similar_tutorials
37323
>>> script = g.scripts.get('n_similar_unique_tutorials')
>>> similar_tutorials = g.gremlin.command(script, params={'tutorial': 'Make Sous Vide Chicken at Home'})
>>> similar_tutorials
8766

There are 37323 paths from Make Sous Vide Chicken at Home to other tutorials and only  8766 of those tutorials are unique. Using this information we can use these duplications to build a ranking mechanism to build recommendations.

Which tutorials are most highly co-rated with How to Make Soous Vide Chicken ?

>>> script = g.scripts.get('topMatches')
>>> topMatches = g.gremlin.execute(script, params={'tutorial': 'Make Sous Vide Chicken at Home'})
>>> sorted(topMatches.content.items(), key=lambda keyword: -keyword[1])[:10]

[(u'Make Sous Vide Chicken at Home', 1000), (u'Make Incredible Beef Jerky at Home Easily!', 131), (u'Make Potato Latkes', 124), (u'Cook the Perfect & Simple Chicken Ramen Soup', 96), (u"Solve a 3x3 Rubik's Cube", 89), (u'Make Cake Pops!!', 75), (u'Make Beeswax and Honey Lip Balm', 75), (u'Make Mint Juleps', 74), (u'Cook Lamb Shanks Moroccan Style', 74), (u'Make an Aerium', 74)]

So we have the top similar tutorials. It means, people who like  Make Sous Vide Chicken at Home, also like Make Sous Viden Chicken at Home, oops! Let's remove these reflexive paths, by filtering out the Sous Viden Chicken.

1. //Get similar tutorials
   def topUniqueMatches(tutorial){
       m = [:]
       v = g.V.filter{it.getProperty('title') == tutorial}
       possible_tutorials = v.inE('liked').outV.outE('liked').inV
       possible_tutorials.hasNot('title',tutorial).title.groupCount(m).iterate()
       return m.sort{-it.value}[0..9]
   }
   
   
   

>>>> script = g.scripts.get('topUniqueMatches')
>>>> topMatches = g.gremlin.execute(script, params={'tutorial': 'Make Sous Vide Chicken at Home'})
>>> topMatches.content

[(u'Make Incredible Beef Jerky at Home Easily!', 131), (u'Make Potato Latkes', 124), (u'Cook the Perfect & Simple Chicken Ramen Soup', 96), (u"Solve a 3x3 Rubik's Cube", 89), (u'Make Cake Pops!!', 75), (u'Make Beeswax and Honey Lip Balm', 75), (u'Make Mint Juleps', 74), (u'Cook Lamb Shanks Moroccan Style', 74), (u'Make an Aerium', 74), (u'Make a Leather iPhone Flip Wallet', 73)]

The recommendation above starts from a particular tutorial (i.e. Make Sous Vide Chicken), not from a particular user. This collaborative filtering method is called item-based filtering.   

Given an tutorial that a user likes, who else like this tutorial, and from those what other tutorials do they like that are not already liked by the initial user.

And the recommendation for a particular user ?  That comes the user-based filtering.

Which tutorials that similar users liked are recommended given a specified user  ?

1. def userRecommendations(user){
     m = [:]
     v = g.V.filter{it.getProperty('userId') == user}
    v.out('liked').aggregate(x).in('liked').dedup.out('liked').except(x).title.groupCount(m).iterate()
     return m.sort{-it.value}[0..9]
   }
   

>>>> script = g.scripts.get('topRecommendations')
>>>> recommendations = g.gremlin.execute(script, params={'user': 'emma-rushin'})
>>> recommendations.content

[(u'Create a Real Fisheye Picture With Your iPhone', 1156), (u'Make a DIY Galaxy Print Tshirt', 933), (u'Make a Macro Lens for Free!', 932), (u'Make Glass Marble Magnets With Any Image', 932), (u'Make DIY Nail Decals', 932), (u'Make a Five Strand Braid', 929), (u'Create a Pendant Lamp From Coffee Filters', 928), (u'Make Avocado Toast', 926), (u'Make Instagram Magnets for Less Than $10', 923), (u'Make a Recycled Magazine Tree (Christmas Tree)', 923)]

Emma Rushin will really like art and crafts suggestions! :D

Ok, we have interesting recommendations, but if I desire to make another styles of chicken like Chicken Ramen Soup for my dinner, I probably do not want some tutorial of How to Solve a Rubik Cube 3x3.  To adapt to this situation, it is possible to mix collaborative filtering and content-based recommendation into a traversal so it would recommend similar chicken and food tutorials based on similar keywords.

Now let's play with content-based recommendation! 

Which tutorials are most highly correlated with Sous Vide Chicken that share the same category of food?

1. //Top recommendations mixing content + collaborative sharing all categories.
   def topRecommendations(tutorial){
     m = [:]
     x = [] as Set
    v = g.V.filter{it.getProperty('title') == tutorial}
    tuts =v.out('hasCategory').aggregate(x).back(2).inE('liked').outV.outE('liked').inV
   tuts.hasNot('title',tutorial).out('hasCategory').retain(x).back(2).title.groupCount(m).iterate()
     return m.sort{-it.value}[0..9]
   }

>>>> script = g.scripts.get('topRecommendations')
>>>> recommendations = g.gremlin.execute(script, params={'tutorial': 'Make Sous Vide Chicken at Home'})
>>> topMatches.content

[(u'Make Incredible Beef Jerky at Home Easily!', 131), (u'Make Potato Latkes', 124), (u'Cook the Perfect & Simple Chicken Ramen Soup', 96), (u'Make Cake Pops!!', 75), (u'Make Beeswax and Honey Lip Balm', 75), (u'Make Mint Juleps', 74), (u'Cook Lamb Shanks Moroccan Style', 74), (u'Cook an Egg in a Basket', 72), (u'Make Banana Fritters', 72), (u'Prepare Chicken With Peppers and Gorgonzola Cheese', 71)]

This rank makes sense, but it still has a flaw.  The tutorial like Make mint Juleps may not be interesting for me. How about only considering those tutorials that share the same keyword 'chicken' with Vide Chicken  ?

Which tutorials are most highly co-rated with Vide Chicken that share the same keyword 'chicken' with  Vide Chicken?

1. //Top recommendations mixing content + collaborative sharing the chicken category.

   def topRecommendations(tutorial){

    m = [:]

    v = g.V.filter{it.getProperty('title') == tutorial}

   
    v.inE('liked').outV.outE('liked').inV.hasNot('title',tutorial).out('hasCategory').
    has('category' ,'chicken').back(2).title.groupCount(m).iterate()
   
   

    return m.sort{-it.value}[0..9]

   }

>>>> script = g.scripts.get('topRecommendations')
>>>> recommendations = g.gremlin.execute(script, params={'tutorial': 'Make Sous Vide Chicken at Home'})
>>> topMatches.content
{u'Make a Whole Chicken With Veggies in the Crockpot': 28, u'Bake Crispy Chicken With Doritos': 30, u'Cook Chicken Rollatini With Zucchini & Mozzarella': 28, u'Make Beer Can Chicken': 23, u'Roast a Chicken': 54, u'Cook the Perfect & Simple Chicken Ramen Soup': 96, u'Pesto Chicken Roll-Ups Recipe': 31, u'Cook Chicken in Roasting Bag': 23, u'Make Chicken Enchiladas': 29, u'Prepare Chicken With Peppers and Gorgonzola Cheese': 71}

Conclusions

In this post I presented one strategy for recommending items using graph concepts. What I explored here is the flexibility of the property graph data structure and the notion of derived and inferred relationships. This strategy could be further explored to use other features available at your dataset (I will be sure that SnapGuide has more rich information to use such as Age, sex and the category taxonomy).  I am working on a book for recommender systems and I will explain with more details about graph based recommendations, so stay tunned at my blog!

The performance ?  Ok, I didn't test in order to compare with the current solutions nowadays.  What I can say is that Neo4J can theoretically hold billions entities (vertices + edges) and the Gremlin makes possible advanced queries. I will perform some tests, but based on what I studied, depending on the complexity of the the graph structure, runtimes vary. 

I also would like to thank Marko Rodriguez with his help at the Grenlim-Users community with his post to inspire me to take a further look into Neo4J + Grenlim! It amazed me! :)

Regards,

Marcel Caraciolo

Machine learning and Data Mining - Association Analysis with Python

Hi all,

Recently I've been working with recommender systems and association analysis.  This last one, specially, is one of the most used machine learning algorithms to extract from large datasets hidden relationships. 

The famous example related to the study of association analysis is the history of the baby diapers and beers. This history reports that a certain grocery store in the Midwest of the United States increased their beers sells by putting them near where the stippers were placed. In fact, what happened is that the association rules  pointed out that men bought diapers and beers on Thursdays. So the store could have profited by placing those products together, which would increase the sales.

Association analysis is the task of finding interesting relationships in large data sets. There hidden relationships are then expressed as a collection of association rules and frequent item sets.  Frequent item sets are simply a collection of items that frequently occur together.  And association rules suggest a strong relationship that exists between two items.  Let's  illustrate these two concepts with an example.

A list of transactions from a grocery store is shown in the figure above. Frequent items are a list of items that commonly appear together.  One example is {wine, diapers, soy milk}.  From the data set we can also find an association rule such as diapers -> wine.  This means that if someone buys diapers, there is a good chance they will buy wine. With the frequent item sets and association rules retailers have a much better understanding of their customers.  Although common examples of association rulea are from the retail industry, it can be applied to a number of other categories, such as web site traffic, medicine, etc.

How do we define these so called relationships ? Who defines what is interesting ?  When we are looking for frequent item sets or association rules, we must look two parameters that defines its relevance.  The support of an itemset, which is defined as the percentage of the data set which containts this itemset. From the figure above the support of {soy milk} is 4/5. The support of {soy milk, diapers } is 3/5 because of the five transactions, three contained both soy milk and diapers. Support applies  to an itemset, so we can define a minimum support and only get the itemsets that meet that minimum support. And the cofidence which is defined for an association rule like diapers->wine. The confidence for this rule is defined as support({ diapers, wine})/ support(diapers).  From the figure above, support of {diapers, wine} is 3/5. The support for diapers is 4/5, so the confidence for diapers -> wine  is: 3/4 = 0.75.  That means in 75% of the items in our data set containing diapers our rule is correct.

The support and confidence are ways we can quantify the success of our association analysis. Let's assume we wanted to find all sets of items with a support greater than 0.8. How would we do that ?  We could generate a list of every combination of items then go and count how frequent that occurs. But this is extremely slow when we have thousands of items for sale. In the next section, we will analyze the Apriori principle which address this problem and reduces the number of calculations we need to do to learn association rules.

To sum up, one example of rule extracted from associatio analysis:

"If the client bought the product A1 and the product A4, so he also bought the product A6 in 74% of the cases. This rule applies on 20% of the studied cases."

The first parameter is the support, that is, the percentage of cases that the product A1 appears in the frequent item sets.  In the rule above, the value 20% points the support, which reports that the rule is applied on 20% of the studied cases.  The second parameter is the confidence, which tells the percentage of occurrences of the rule.  So the value 74% represents the confidence,  where in the 20% of the rules where products A1 and A4 are found, 74% of them we also can find the product A6.

Apriori Algorithm

Let's assume that we are running a market store with a very limited selection. We are interested in finding out which items were purchased together. We have only four items: item0, item1, item2 and item3. What are all the possible combinations that can be purchased ? We can have one item, say item0 alone, or two items, or threee items, or all of the items together. If someone purchased two of item0 and four of item2, we don't care. We are concerned only that they purchased one or more of an item.

A diagram showing all possible combinations of the items is shown in the figure above.  To make easier to interpret, we only use the item number such as 0 instead of item0.  The first set is a big Ø, which means the null set or a set containing no items. Lines connecting item sets indicate that two or more sets can be combined to form a larger set.

Remember that our goal is to find sets of items that are purchased together frequently. The support of a set counted the percentage of transactions that contained that set. How do we calculate this support for a given set, say {0,3}? Well. we go through every transaction and ask, ”Did this transaction contain 0 and 3?” If the transaction did contain both those items, we increment the total. After scanning all of our data, we divide the total by the number of transactions and we have our support. This result is for only one set: {0,3}. We will have to do this many times to get the support for every possible set. We can count the sets in Figure below and see that for four items, we have to go over the data 15 times. This number gets large quickly. A data set that contains N possible items can generate 2N-1 possible itemsets. Stores selling 10,000 or more items are not uncommon. Even a store selling 100 items can generate 1.26*1030 possible itemsets. This would take a very, very long time to compute on a modern computer.

To reduce the time needed to compute this value, researchers identified something called the Apriori principle. The Apriori principle helps us reduce the number of possible interesting itemsets. The Apriori principle is: if an itemset is frequent, then all of its subsets are frequent. In Figure below this means that if {0,1} is frequent then {0} and {1} have to be frequent. This rule as it is doesn’t really help us, but if we turn it inside out it will help us. The rule turned around reads: if an itemset is infrequent then its supersets are also infrequent, as shown in Figure  below.

As you can observe, the shaded itemset {2,3} is known to be infrequent. From this knowledge, we know that itemsets {0,2,3}, {1,2,3}, and {0,1,2,3} are also infrequent. This tells us that once we have computed the support of {2,3}, we don’t have to compute the support of {0,2,3}, {1,2,3}, and {0,1,2,3} because we know they won’t meet our requirements. Using this principle, we can halt the exponential growth of itemsets and in a reasonable amount of time compute a list of frequent item sets.

Finding frequent item sets

Now let's go through the Apriori algorithm.  We first need to find the frequent itemsets, then we can find association rules. The Apriori algorithm needs a minimum support level as an input and a data set. The algorithm will generate a list of all candidate itemsets with one item. The transaction data set will then be scanned to see which sets meet the minimum support level. Sets that do not meet the minimum support level will get tossed out. The remaining sets are then combined to make itemsets with two elements. Again, the transaction data set will be scanned and itemsets not meeting the minimum support level will get tossed. This procedure is repeated until all sets are tossed out.

We will use Python with Scipy and Numpy to implement the algorithm. The pseudocode for the Apriori Algorithm would look like this:

While the number of items in the set is greater than 0:

               Create a list of candidate itemsets of length k 

              Scan the dataset to see if each itemset is frequent

             Keep frequent itemsets to create itemsets of length k+1

The code in Python is shown below:

The source is docummented so  you can easily understand all the rules generation process.

Let's see in action ?!

First, we created our first candidate item set C1. C1 contains a list of all items in frozenset. After we created D, which is just a dataset in the form of list of sets (set is a list of unique elements).  With everything in set form we removed items that didn't meet our minimum support. So in our example 0.5 was the minimum support level chosen.  The result is represented by the list L1 and support_data. These four items that make our list L1 are the sets that occur in at least 50% of all transactions. Item 4 didn't make the minimum support level, so it's not a part of L1. By removing it, we have removed more work we needed to do when wen find the list of two-item-sets. Remember our pruned tree above?!

Two more functions now were used: apriori() and aprioriGen(). In apriori() given a data set and a support level, it will generate a list of candidate itemsets. AprioriGen() is responsible for generate the next list of candidate itemsets and scanD throw out itemsets that don't meet the minimum support levels. See the result of aprioriGen() it generates six unique two-item-sets.  If we run it with our apriori function we will check that L contains some lists of frequent itemsets that met a minimum support of 0.5.  The variable support_data is just a dictionary with the support values of our itemsets.  We don't care about those values now, but it will be useful in the next section.   We have now which items occur in 50% of all transactions and we can begin to draw conclusions from this.  In the next section we will generate association rules to try to get an if-then understanding of the data.

Mining association rules from frequent item sets

We just saw how we can find frequent itemsets with Apriori Algorithm. Now we have to find the association rules. To find them, we first start with a frequent itemset.  The set of items is unique, but we can check if there is anything else we can get out of these items. One item or one set of items can imply another item. From the example above, if we have a frequent itemset: {soy milk lettuce}, one example of an association rule is: soy milk -> lettuce.  This means if someone purchases soy and milk, then there is a statistically significant chance that he will purchase lettuce. Of course this is not always true, that is, just because soy milk -> lettuce is statistically significant, it does not mean that lettuce -> soy milk will be statistically significant.

We showed the support level as one measurement for quantifying the frequency of an itemset. We also have one for association rules. This measurement is called the confidence. The confidence for a rule P-> H is defined as: support (P|H)/support(P).  Remember that the | symbol is the set union. P|H means all the items in set P or in set H.  We already have the support values for all frequent itemsets provided in apriori function, remember ?  Now, to calculate the confidence, all we have todo is call up those support values and do one divide.

From one frequent itemset, how many association rules can we have ?  If you see the figure below, it shows all the different possible associations rules from the itemset {0, 1, 2, 3}. To find relevant rulese, we simply generate a list of possible rules, then test the confidence of each rule. If the confidence does not meet our minimum requirement, then we throw out the rule.

Usually we don't this. Imagine the number of rules if we have a itemset of 10 items, it would be huge. As we did with Apriori Algorithm we can also reduce the number of rules that we need to test. If the rule does not meet the minimum confidence requirement, then subsets of that rule also will not meet the minimum. So assuming that the rule 0,1,2 -> 3 does not meet the minimum confidence, so any rules where is subset of 0,1,2 ->3 will also not meet the minimum confidence.

By creating a list of sets with one item on the right hand size, testing them and merging the remaining rulese, we can create a list of rules of two items and do this recursively. Let's see the code below:

Let's see in action:

As you may seen in the fist call, it gives us three rules: {1} -> {3} , {5} -> {2} and {2} -> {5}. It is interesting to see the rules with 2 and 5 can be flipped around, but not the rule with 1 and 3. If we lower the confidencer threshold to 0.5, we may see more rules.  Let's go now to a real-life dataset and see how it does work.

Courses  at Atepassar.com

It's time to see these tools on a real life dataset. What can we use ?  I love educational data, so let's see an example using the Atepassar social network data. Atepassar is a popular social-learning environment where people can organzie the studies for public exams in order to get a civil job. I work there as Chief Scientist!

The data set provided can give us some interesting insights about the profiles of the users who buys on-line courses at Atepassar. So we will use the apriori() and generateRules() functions to find interesting information in the transactions.

So let's get started.  First I will create a transaction database and then generate the list of frequent itemsets and association rules.

Collect Dataset from Atepassar.

So let's get started.  First I will create a transaction database and then generate the list of frequent itemsets and association rules.

I have encoded some information related to our transactions, for example, the client's user profile such as state, gender and degree. I also extracted the bought courses and the category of the course such as 'national', 'regional', 'state' or 'local'.

This give us important hypothesis to test like "Male people buy more preparation courses for national exams?", "People from Sao Paulo tends to buy more for state exams ?" or even if male people graduated buys courses for 'local' exams ?"  Those are some examples of explanations that we may get with association analysis.

After loading my dataset we can see inside each transaction:

Let's see one of them in order to explain it:

So one transaction is composed by a woman who bought a preparation course for a national exam (Brazilian exam) and lives at Distrito Federal (DF).

Now,  let's use our Apriori algorithm. But first let's make a list of all the transactions. We will throw out the keys, which are the usernames. We are not interested in that.  What we are interested is the items and associations among them.  Now let's going to mine the frequent itemsets and association rules.

Applying the Apriori algorithm developed earlier,  and use support settings of 5%, we may see several of frequent itemsets. 

Now let's try to generate the association rules. We begin with minimum confidence of 70%.  

If we increase the confidence even more, we don't see any rules at all. That means lots of distinct transactions or  small amount of data unfortunately.

I will be with confidence of 70%. So we have the following rules:

What can we say about those insights ? Do you remember the support level of 5% ? That means that the rules above show up in at least 5% of all transactions. To sum up,  we are going to see these association rules in at least 5% of the transactions, and in the case of  DF --> Nacional, this rule is right 83,8% of the time.  People from Brasilia really purchase for better positions in the government,  or even get the best salaries! 

Conclusions

In this post I presented one of the most traditional tools in data mining to find interesting relationships in a large set of data.  We saw that there are two ways we can quantify the relationships: using frequent itemsets, which shows items that commonly appear in the data together. And the second one are the association rules which imply an if -> t hen relationship between items.

But wait,  before start using it at your dataset, I have to give sou some warnings.  Finding different combinations of items can be a very consuming task and expensive in terms of computer proccessing.  So you will need more intelligent approaches to find frequent itemsets in a small amount time.  Apriori is one approach that tries to reduce the number of sets that are chacked against the dataset. With Support measure and Confidence we can combine both to generate association rules.

The main problem of Apriori Algorithm is it requires to scan over the dataset each time we increase the length of our frequent itemsets. Imagine with a huge dataset, it can slow down the speed of finding frequent itemsets.  Alternative techniques for this issue is the FP-Growth algorithm, for example. It only needs to go over the dataset twice, which can led to a better performance.

The code in Python is shown here.

I hope you enjoyed this article, the first of 2013!

Regards,


Marcel Caraciolo