Sunday 26 November 2017

Big data query system

HDFS was born on 2006 to fix the distributed storage/computing problem and then came spark riding on cheap hardware in 2012 to fix distributed processing problem in disruptive style.

One problem space that has seen lot of innovative tools is  "How to build information system" for huge data, cheap hardware has enabled to build fast analytics system by using in-Memory techniques.
Data is growing every moment and it is becoming very challenging to all analytics tools to keep-up with it, some system use Column stores, special index like Bitmap index etc to build responsive system.

One more technique called Summarization is also used in many system to solve this problem, in this blog i will discuss some ideas around Summarization and tradeoff of using this technique.

Definition of summarization as per vocabulary.com is

To summarize means to sum up the main points of something — a summarization is this kind of summing up. Elementary school book reports are big on summarization.

When you're a trial lawyer, the last part of the argument you make before the court is called a summation. It included a summarization of the points you have made in the trial so far, but it goes one step further, to push this summarization toward a conclusion you hope the judge or jury will accept.    

This picture explains it, you take something big and make it small by retaining important attributes.

One more technique is Sampling that also helps in reducing size of something that is unmanageable to manageable, but it trade-offs accuracy for this and may system can tolerate some percentage of error.

Sampling is also used to to validate some tests or assumption, so sampling allows to consumer information using limited resource.

Summarization and Sampling can used together to build some fast information system.


One of the simple summary approach is build group the data into different set and each record/row should be just in one set.

Lets take a toy data set to build groups.


yearsexNametype_of_course
1993MaleM1Humanities & Social Sciences
1993MaleM2Mass Communication
1993MaleM3Accountancy
1993MaleM4Business & Administration
1993MaleM5Law
1994MaleM6Education
1994MaleM7Applied Arts
1994MaleM8Humanities & Social Sciences
1994FemaleF1Education
1994FemaleF2Applied Arts
1994FemaleF3Humanities & Social Sciences
1994MaleM9Law


This data is for what type of course people study, it can split into couple of groups using year,sex,type of course.

1993,Male,Humanities & Social Science
1994,Female,Education
1994,Male,Law
1993,Male,Law

Grouping convert huge data set to small set and then sampling can be done based on these groups to pick up items from this group.

One of the way is to take random sample but it has limitation  that some group will be missed and sample data will be not representative to original dataset and it will be impossible to answer many query.

We need smart sampler and stats guru have already figured it out, it is called Stratified Sampling

This sampling involves
 - Create Strata, this is nothing but create groups.




yearsextype_of_courseno_of_graduates
1994MalesHumanities & Social Sciences512
1994MalesBusiness & Administration413
1994FemalesInformation Technology196
1994FemalesArchitecture & Building182
1994FemalesEngineering Sciences227
Total1530


- Decided sample size

Lets take 5% of sample that comes to 77 (5% of 1530)

- Compute contribution of each group


yearsextype_of_courseno_of_graduatesContribution
1994MalesHumanities & Social Sciences51233.46405229
1994MalesBusiness & Administration41326.99346405
1994FemalesInformation Technology19612.81045752
1994FemalesArchitecture & Building18211.89542484
1994FemalesEngineering Sciences22714.83660131
Total1530
- Select sample records

77 records are required and break of 77 will be based weight of individual group


yearsextype_of_courseno_of_graduatesContributionSample Size ( 77)
1994MalesHumanities & Social Sciences51233.4640522925.6
1994MalesBusiness & Administration41326.9934640520.65
1994FemalesInformation Technology19612.810457529.8
1994FemalesArchitecture & Building18211.895424849.1
1994FemalesEngineering Sciences22714.8366013111.35
Number of records selected are based on weight of group and this gives data from each group.

By this approach 1530 records got reduced to 77 , lets try to answer some of query using this sample data, we also try to estimate what it will look at 100% and calculate error.

100 % estimate = 1%  * 100

1% = Sample Answer/Sample %


QuestionActual Answer5% Sample100% ( Estimated)Error
No of people graduated in 199415307715400.006535947712
Males graduated in 1994925469200.005405405405
All Females605306000.00826446281
Engineering Sciences student227112200.03083700441


Look at the error column, worst answer has 3% error and with this small error query can be answer in milli second vs seconds.

I used singapore open data graduates-from-university-first-degree-courses-by-type-of-course to build app that answer query based on sampling.

Code is available @ github

Machine Learning 101

Data science is trending these days, everybody wants to become data scientist because it is cutting edge and has high paying jobs.

I am also starting to learn this coooool stuff and best way to learn is write some code and get the feel of it.
I will start blog post series how to approach machine learning problem without getting lost in jargons and complex mathematical formulas.

Some of problem suited for ML are
 - Email classification ( Spam Vs Ham)
 - Books/Hotel/Food etc review classification
 - Sentiment analysis of brand or product.

In each of the above problem output is some kind of label(spam,ham, positive, negative etc)
These type of problem are classification problem, lets look at diagram to understand this.


Email is problem instance.
Classifier is the process that know rules to classify
Spam/Ham is the output. If there is only 2 output then it is called binary classifier.

Lets zoom in "Classifier", it is rule engine that know all the business rules to do the work.
Rules can be static or dynamic, in some case static rules are fine but for many problem rules keeps on changing and it becomes overhead to keep rules up to date.

This is where ML comes in picture, system learns new rules by it self.

How does system learns ?
You have to train the system and after that training system identifies the patterns, this type of ML is called Supervised learning

Each Supervised learning has Training phase before it starts making predication.

Think training phase as practice, it contains both questions and answers.

Once training phase is done then classifier is ready for use on new questions without answer.

There is one more phase called "Test", it is used to check how good classifier is, if it is not good then it means training data was not good.

Now lets try to do some sentiment analysis using imdb reviews


ReviewType
Wasted two hoursNegative
A bit predictableNegative
The story itself is just predictable and lazyNegative
Buy it, play it, enjoy it, love itPositive
It deserves strong lovePositive

In learning phase model takes above data and works out pattern for positive and negative comments.
You must be thinking how model knows about pattern.

One way to look at the problem is using probability of word being in positive comment vs negative comment and then take the one that is greater.

Lets look at example to understand this.

"Wasted" and "predictable" only appears only in -ve, so if any comment that contains these word they have high chance of being -ve comment.

"Love"  comes only in the +ve .

So algorithm is very simple.

 - Split sentence in words
 - POS Score = (Compute +ve score of words & multiply them)
 - NEG Score = (Compute -ve score of words & multiply them)
 - Result = Max(Pos Score,Neg Score)


Before scores are compared we have to multiply with overall probability of positive or negative comments.

In our toy example

Total Reviews5
Pos Comment2
Neg Comment3
Pos Probability( 2/5)0.4
Neg Probability( 3/5)0.6
 
POS ScorePos(words in sentence) * Overall Pos(i.e 0.4)
Neg ScoreNeg(words in sentence) * Overall Neg(i.e 0.6)

You don't have to code this algorithm, it is already implemented in Naive Bayes classifier.
Although this classifier has 'Naive' in name but it is not really naive, it gives very good result with around close to 80% accuracy and it is used in many production system.

All language/framework like python,spark,R has implementation for this classifier. 

I have implemented this classifier in python/spark using Sentiment Labelled Sentences data from UCI ML repo.

This sample data contains reviews from imdb,yelp & amazon.

Code is available @ github