Market Basket Analysis using SQL

Essentially, association rule mining is all about counting. So it fits database environment very well, especially big scalable database. With some "group by"s and "join"s, the job can be easily accomplished using SQL.

Here I use Apriori algorithm to generate all 0-way (i.e., {}=>item B) and 1-way (i.e., item A=>item B) rules. The code first generate frequent itemsets that contains single item and have minimum support count bigger than minsup. And then it will generate all 1-way rules that have frequent itemsets with 2 items with support bigger than minsup, and have confidence bigger than some minconf. Rules bigger than 1 way are more complicated and require going through data iteratively until no more frequent itemsets are generated. The following codes are just meant to show how market basket analysis works and what kind of metrics are available to evaluate the rules.

/* Assuming your transaction data looks like this (order_id, item) pair
order 1, item 1
order 1, item 2
order 1, item 32
order 2, item 3
order 2, item 2
order 2, item 5
order 3, item 3
...
and it's already stored in the database with table name trans_data.
*/

-- Generating 0-way frequent itemsets using minsup=5
CREATE TABLE arule_0w AS
SELECT item, SUM(1) AS cnt
FROM trans_data
GROUP BY item
HAVING SUM(1) > 5
DISTRIBUTED BY (item)
;

-- Generate 1-way frequent itemsets,
CREATE TABLE arule_1w AS
SELECT lhs, rhs, COUNT(1) AS num_lhs_rhs
FROM (
SELECT item_lhs.order_id, lhs, rhs
FROM (SELECT a.order_id, a.item AS lhs
FROM trans_data a
JOIN arule_0w USING(item)
GROUP BY order_id, item) item_lhs
JOIN (SELECT b.order_id, b.item AS rhs
FROM trans_data b
JOIN arule_0w USING(item)
GROUP BY order_id, item) item_rhs
ON (item_lhs.order_id=item_rhs.order_id
AND item_lhs.lhs <> item_rhs.rhs)
) rules
GROUP BY lhs, rhs
HAVING COUNT(1) > 5
DISTRIBUTED BY (lhs, rhs)
;

You might have noticed that trans_data joined with the 0-way itemsets table to filter out items that are not frequent for the 0-way table. This is exactly how Apriori algorithm works, at each iteration, filtering out items are not frequent from previous run. Because as we search deeper in the data, the sets will become smaller and smaller, and if items are not frequent at the previous iteration, they won't be in the later iterations.

All right, the above query shows how to generate 0-way and 1-way itemsets. Next chunk of queries will show how to generate rules from itemsets and measurements that are used to evaluate the rules. Besides support and confidence, there are other measurements too, like cosine, Kappa, Jaccard, Laplace, Gini index, J-measure to name a few (for more details, see sample chapter 6 on "introduction to data mining" book website). Most of the interest measurements are calculated based on the following 2X2 contingency table. f11 is the number of times A and B appear together in the same transaction. f10 is the number of transactions that contains A but not B. The column sum f+1 is the support count for B, and f1+ is the support count for A. N is the total number of transactions.

| B | !B |
----|-----|-----|------
A | f11 | f10 | f1+
!A | f01 | f00 | f0+
----|-----|-----|------
| f+1 | f+0 | N

Next, I show how to generate rules and calculate some of those interest measures in query

CREATE TABLE arule_1w_with_measure AS
SELECT a.*
, (power(exp_lhs_rhs - num_lhs_rhs, 2)/exp_lhs_rhs + power(exp_lhs_no_rhs - num_lhs_no_rhs, 2)/exp_lhs_no_rhs + power(exp_no_lhs_rhs - num_no_lhs_rhs,2)/exp_no_lhs_rhs + power(exp_no_lhs_no_rhs - num_no_lhs_no_rhs, 2)/exp_no_lhs_no_rhs) as Chi_Square
, (num_lhs_rhs+1)/(num_lhs+2) as Laplace
, (num_lhs*num_no_rhs)/(num_basket * num_lhs_no_rhs) as Conviction
, (num_lhs_rhs/num_lhs - num_rhs/num_basket) as Added_Value
, (num_lhs_rhs/num_lhs - num_rhs/num_basket) /(1-num_rhs/num_basket) as Certainty_Factor
, (num_lhs_rhs/num_basket * ln((num_basket*num_lhs_rhs)/(num_lhs*num_rhs)) + num_lhs_no_rhs/num_basket * ln((num_basket*num_lhs_no_rhs)/(num_lhs*num_no_rhs))) as J_Measure
, num_lhs/num_basket*(power(num_lhs_rhs, 2)+power(num_lhs_no_rhs, 2))/power(num_lhs, 2)-power(num_rhs/num_basket, 2) + num_no_lhs/num_basket *(power(num_no_lhs_rhs,2) + power(num_no_lhs_no_rhs, 2))/power(num_no_lhs, 2) - power(num_no_rhs/num_basket, 2) as Gini_Index
, num_lhs_rhs/(num_lhs+num_rhs-num_lhs_rhs) as Jaccard
, (num_lhs_rhs/num_basket - num_rhs*num_lhs/power(num_basket, 2)) as Shapiro
, num_lhs_rhs/sqrt(num_lhs*num_rhs) as Cosine
, (num_lhs_rhs*num_basket-num_lhs*num_rhs)/sqrt(num_lhs*num_rhs*num_no_lhs*num_no_rhs) as Correlation
, num_lhs_rhs*num_no_lhs_no_rhs/(num_lhs_no_rhs*num_no_lhs_rhs) as Odds_Ratio
FROM (SELECT lhs_rhs.lhs||' => '|| lhs_rhs.rhs as rules
, lhs_rhs.lhs
, lhs_rhs.rhs
, num_lhs_rhs*1.0 as num_lhs_rhs
, num_basket*1.0 as num_basket
, num_lhs*1.0 as num_lhs
, num_rhs*1.0 as num_rhs
, (num_basket - num_lhs)*1.0 as num_no_lhs
, (num_basket - num_rhs)*1.0 as num_no_rhs
, (num_lhs - num_lhs_rhs)*1.0 as num_lhs_no_rhs
, (num_rhs - num_lhs_rhs)*1.0 as num_no_lhs_rhs
, (num_basket - num_lhs - num_rhs + num_lhs_rhs)*1.0 as num_no_lhs_no_rhs
, num_lhs * num_rhs * 1.0 /num_basket as exp_lhs_rhs
, num_lhs * (1.0 * num_basket - num_rhs) * 1.0 /num_basket as exp_lhs_no_rhs
, (1.0 * num_basket - num_lhs) * num_rhs /num_basket as exp_no_lhs_rhs
, (1.0 * num_basket - num_lhs) * (1.0 * num_basket - num_rhs) /num_basket as exp_no_lhs_no_rhs
, num_lhs_rhs * 1.0 /num_basket as support
, num_lhs_rhs * 1.0 /num_lhs as confidence
, num_lhs_rhs * num_basket * 1.0/(num_lhs * num_rhs) as lift
FROM arule_1w as lhs_rhs
JOIN (SELECT item as lhs
, count(1) as num_lhs
FROM trans_data
GROUP BY lhs) sum_lhs
ON lhs_rhs.lhs=sum_lhs.lhs
JOIN (SELECT item as rhs
, COUNT(1) as num_rhs
FROM trans_data
GROUP BY rhs) sum_rhs
ON lhs_rhs.rhs=sum_rhs.rhs
CROSS JOIN (SELECT COUNT(1) as num_basket
FROM (SELECT order_id FROM trans_data GROUP BY order_id) foo) total
) a
WHERE lift > 1 -- only the good rules
AND confidence > .0001
DISTRIBUTED BY (lhs, rhs)
;

Notice the where clause at the end insures that we only generate rules with confidence bigger than a threshold of .0001 and lift > 1, meaning positively related rules. One trick I used is to multiply 1.0 to integer counts, so later on when you calculate those measure, the SQL won't complain about over floating of integers.

Association Rule Mining (Market Basket Analysis)

Association rule mining is a well researched classical data mining technique. It's designed to find hidden pattern or relationship in large data set, pattern referring to co-appearance of high frequency different items given the existence of some item. Particularly, it's well suited for analyzing commercial transaction data. In that scenario (where it's usually called "market basket analysis"), the presence of items can be expressed using a binary variable taking value from {0,1}. For example, the transaction data at the checkout counters (each customer holding a basket of one or more items), shows that customer who buys A also purchases B. By examining huge amount of transaction data, interesting relationships/rules could be revealed, like people buy diaper also buy wipes (this is a trivial rule, not very interesting), or people buy diaper also buy beer (well, this is a lot more interesting than the previous rule). Rules like this can be very helpful for cross-marketing, catalog design, shelf organizing, products recommendation at the place-order page etc. Of course, besides this kind of consumer preference analysis, association rule mining works for other types of problems too, e.g., human resource management (employees who said positive things about initiative A also frequently complain about issue B), and the history of language.

Because association rule mining does not require users to provide a whole lot prior information and it deals with single values, words or items, it's well suited for data or text mining in large databases. In next posts, I will demonstrate how to do market basket analysis using SQL and R.

The rules can be denoted as A => B, meaning A implies B. The most commonly used measurements for association rule mining is support and confidence, where support =count(A & B together)/ count(total transactions) (joint probability for A and B), confidence =count(A & B together)/count(A) (conditional probability of B given A) and count(A) counts the number of transaction for event A. A lot of algorithms use support and confidence to prune the uninteresting less confident rules. For example, the well-known Apriori algorithm rapidly processes data based on preferred "threshold" values.

Here Professor Kumar showed some sample chapters for his book "Introduction to Data Mining", including the chapter for association rule mining.

Convert R "xtabs" object to a dataframe

Lately, I used R's "xtabs" command to generate a 2 dimension contingency table. Then I tried to merge the result with a dataframe object I created earlier. However "merge" function does not like the miss-match input types, meaning I have to transform the xtabs result to a dataframe. The challenges are (1) the regular as.data.frame did not work. I have to use as.data.frame.matrix (2) the column's naming convention is not the ones I'd like it to be. So I write a little R function to accomplish the task of converting xtabs objects to dataframes.

# define x
x <- data.frame(id=c(123,123), model=c(2,3), value=c(2.73,0.36))

# > x
# id model value
# 1 123 2 2.73
# 2 123 3 0.36

# create 2 dimension xtab variable
aa <- xtabs(value~id+model, data=x)

xtabs_2_dataframe <- function(aa){
# figure out column names that are originally used in the xtabs call
nm_tmp <- attributes(dimnames(aa))$names
if(length(nm_tmp) != 2){
# this function only handles 2 dimension xtabs object
cat('Error: the input xtabs object has to have at most 2 dimensions!\n')
#return(NULL)
} else {
bb <- as.data.frame.matrix(aa)

# playing aroun d
colnames(bb) <- paste(nm_tmp[2], colnames(aa), sep='_')
bb$newcol <- dimnames(bb)[[1]]
colnames(bb)[ncol(bb)] <- nm_tmp[1]
rownames(bb) <- NULL

cc=data.frame(bb[, ncol(bb)], bb[, 1:(ncol(bb)-1) ], stringsAsFactors = F)
colnames(cc)[1]=nm_tmp[1]
return(cc)
} }

# > xtabs_2_dataframe(aa)
# id model_2 model_3
# 1 123 2.73 0.36
# > str(xtabs_2_dataframe(aa))
# 'data.frame': 1 obs. of 3 variables:
# $ id : chr "123"
# $ model_2: num 2.73
# $ model_3: num 0.36


Of course, you may ask why not use cast function in reshape package? Well, I tried that and got a list object. So if I want a data frame, I have to process that too, for example using do.call(cbind,...) and assign the proper column names.

# > cast(x, id~model+value)
# id 2_2.73 3_0.36
# 1 123 2.73 0.36
# > str(y<-cast(x, id~model+value))
# List of 3
# $ id : num 123
# $ 2_2.73: num 2.73
# $ 3_0.36: num 0.36
# - attr(*, "row.names")= int 1
# - attr(*, "idvars")= chr "id"
# - attr(*, "rdimnames")=List of 2
# ..$ :'data.frame': 1 obs. of 1 variable:
# .. ..$ id: num 123
# ..$ :'data.frame': 2 obs. of 2 variables:
# .. ..$ model: num [1:2] 2 3
# .. ..$ value: num [1:2] 2.73 0.36

Thinking about self-join? Well, think again!

This week, the greenplum people came on-site and talked about a few tricks that I am very new to. The ones I have most feeling about are

(1) about function overloading

So PostgreSQL allows you to have functions with exact names but different inputs or outputs, even different number of inputs. This is called function overloading. It's a feature in various programming languages like C, Java etc. And since Greenplum is written in C, it has this feature by birth. And this is exactly WHY you have to specify the inputs when deleting a function in greenplum!

I know, this could be very annoying! So they should really have a switch, so you can choose whatever options you want, either follow the overloading rule or not. So if you refuse to follow overloading and you try to name a new function the same as an existing one, greenplum will throw an error on you. C language has the overloading thing. That's fine. But greenplum could have given user options.

(2) about "STRICT"

When writing user defined functions, by adding "STRICT" option at the end, you are telling PostgreSQL to return a null automatically when someone inputs a null to the function. The function will not even try to run with null inputs, it will return null immediately. This could be a nice option to speed things up.

(3) about windowing function

Windowing function is not new concept to me. But the instructor's comment about all self-join could be replaced by windowing function is quite new. It's kind of surprising to me. Of course, I believe it's not hard, just takes time to get used to, particularly when one has been so familiar with table self-joins.

Windowing function allows user to access a set of rows associated with the current row. It can perform various calculations, like sum, rank, average, max/min etc. PostgreSql has a very good tutorial on windowing functions. There are two things I like particularly, running totals and naming windows.

So now the running total revenue calculation of campaigns is

SELECT campaign_id
, revenue
, SUM(revenue) OVER (w) as running_total
, SUM(revenue) OVER() AS overall_total
,(SUM(revenue) OVER (w)) / (SUM(revenue) OVER()) AS pct
FROM rev_table
WINDOW w AS (ORDER BY revenue DESC)

Very nice and clean, right?

Last but not least, first_value, last_value or nth_value could be extremely useful sometime, for example, I'd like to know that's the last campaign a user have clicked on in the past week.

SELECT enc_email
, FIRST_VALUE(campaign_id) OVER(PARTITION BY enc_email ORDER BY click_date DESC) AS last_campaign
FROM user_history
LIMIT 1;

The "limit 1" at the end is very important. Without it, the end result will has as many rows as the original table filling with exact same rows.

Extracting "gems" from web pages using BeautifulSoup and Python - extracting II

**** step 4 ****
extract the business address (suppose tt=results[0]).
The address itself is closed to a tag called "address", for example

<address>
3002 W 47th Ave <br/>Kansas City, MO 64103 <br/>
</address>

Since I want the address and zip code separate, I used

# address
>> address_tmp=tt.find('address')
>> address_tmp=BeautifulSoup(re.sub('(<.*?/>)',' ',str(address_tmp))).text
>> address=address_tmp.rstrip('1234567890 ')
>> zipcode=re.search(r'\d+$',address_tmp).group()

The first line is saying "find the tag with name address". Because of the
stuff in the middle of the string, I have to use regular expression to replace them with a single space. Then I change the string back to BeautifulSoup object and finally get the text between the "address" tages.

u'3002 W 47th Ave Kansas City, KS 66103'

The third line tends to trim off zipcode and any space after the state abbreviation. On the contrary, the fourth line utilizes regular expression to extract the zipcodes (which are few digits at the end of the string).

There is one thing that needs to pay attention is to use "?" to make the search non-greedy, meaning as long as the search find the pattern, it will return it. see here Google Python Class for more details.

**** step 5 ****
Oops, did I forget to get the business name first? All right, if you realize the name part is heading in a div tag with it's attributes called "itemheading", you will get the entire piece and the name part easily through

>> name_rank=tt.find('div', attrs={'class':'itemheading'}).text
>> name_rank
u"1.\n \tOklahoma Joe's BBQ & Catering"
>> names=name_rank.lstrip('1234567890. ').replace('\n \t', '')
>> names
"Oklahoma Joe's BBQ & Catering"

Very similar to the address part, the new piece added is the replace function operated on strings to remove '\n \t'.

**** step 6 ****
Next, I'd like to know the category or categories for those restaurants. Those are stored in the text of 'a' tags with class label of "category". The 2nd line below join all category labels using ',' to make them one string. And the 3rd line removes '\n' from the string.

# multiple categories so
>> cats=tt.findAll('a',attrs={'class':'category'})
>> category=','.join([x.text for x in cats])
>> category=str(category).replace('\n', '')
>> category
u'Barbeque'


**** step 7 ****
Similar idea applies to get number of reviews and rating as following

# reviews '217 reviews', have to parse the number part using regular expression
>> review_tmp=tt.find('a',attrs={'class':'reviews'}).text
>> rev_count=re.search(r'^\d+', review_tmp).group()
>> rev_count
u'217'
# rating scale
>> rating_tmp=tt.find('div',attrs={'class':'rating'})
>> rating=re.search(r'^\w+\.*\w*',rating_tmp('img')[0]['title']).group()
>> rating
u'4.5'



After all these 7 steps, I write them into a csv file through

out = open('some.csv','a') # append and write
TWriter = csv.writer(out, delimiter='|', quoting=csv.QUOTE_MINIMAL)
TWriter.writerow([ranks, names, category, address, zipcode, rev_count,rating])
out.close()

Extracting "gems" from web pages using BeautifulSoup and Python - extracting I

The web crawling piece I talked previously seems a little bit easier. So I will start from there. There are actually two pieces involved: first one is to crawl the website and download its related webpages, second is to extract information out of the saved html pages.

I will start from the 2nd half of work and show step by step how I work with the sample webpages from yelp.com and process them in Python using BeautifulSoup.

Ok, let's get started. First of all, give you an idea of what does yelp.com look like. Below is a small screen shot on the restaurant search result for Kansas City metro area. What I really want to extract from this page is: the business unit name, address, zip, category, number of reviews and rating.



This is a typical search result from yelp website, which includes something totally unrelated with what we need (like the sponsor ads for "The Well"), then the stuff we care, and finally stuff totally irrelevant again. Not that bad, right? But when you look at the underneath html codes, you will see this



Really messy!!! How can you clearly see the stuff you want, let along extract anything them from such a html page? Here is when you should have thought about using BeautifulSoup, which is a terrific, flexible HTML/XML parser for Python.

Now, it's time to get hands dirty with some python codes.
**** step 1 ****
inside python (under windows), load the modules that will be used

import re # regular expression module
import os # operation system module
import csv
from BeautifulSoup import BeautifulSoup

**** step 2 ****
point python the html file I saved and open it of course

os.chdir('C:\\Documents and Settings\\v\\Desktop\\playground\\yelp data')
f=open('rest3.htm','r')

**** step 3 ****
create a soup object and extract the business units

soup=BeautifulSoup(f)
results=soup.findAll('div', attrs={'class':'businessresult clearfix'})

After the "BeautifulSoup" command applied to file f, the output "soup" becomes a soup object (basically just a text file). Observing the original html pages, you will find yelp organize the search result using a div with class="businessresult clearfix". So the second line is really saying give me all the div sections which has class="businessresult clearfix". In this case, "results" is a list of 40 text stings, each one contains the information we want about a single restaurant. Next I will loop through each element in the list ("for tt in results:") and extract "gems" one by one.

Extracting "gems" from web pages using BeautifulSoup and Python - BI part

Lately, I am trying to find a way to answer this question: what's the best local restaurants or spas? So we are trying to figure out which local businesses will worth the most to go after.

Ok, that could be a supervised or unsupervised learning problem. If I can find some data that indicates brand awareness, and use some metrics as predictors, then it's a supervised problem. Well, if I cannot find the indicator kind of response, then I have to figure out another way to sort of build that index using whatever predictive metrics I can find online and for free.

The first thing came to my mind was yelp.com, which is a relatively comprehensive rating website on local businesses. Naturally what I want to do is to crawl that website and get some useful information out, like location of business (in order to calculate distance of that business to a particular user), number of ratings (one indicator of brand awareness), rating itself (brand quality), etc.

Secondly, I want to see if I can get some twitter data. If I happened to know the ip of the twitter user, I can figure out his/her location and just see how many tweets a local business can have. Similarly, google analytics might be helpful too, but I am not sure.