Wenming's Big Data and Big Compute Blog

Data Science in a Box using IPython: Scipy and Scikit-Learn (3/4)

HPC Trekker — Wed, 17 Apr 2013 22:43:25 GMT

In the first two blogs of this series, we installed the IPython notebook using the minimum requirement.

Creating a Linux VM on Windows Azure (1/4)

Installing IPython notebook (2/4)

The third blog post will walk you through some of the common packages used for Data Science.

SciPy/NumPy packages are usually mentioned together. At this point, we have not installed SciPy, SciPy includes a collection of numerical packages, that includes Linear solvers that we used in a previous post. Enter the Big Data Matrix: analyzing meanings and relations of everything (2/2).

To install the package type: sudo apt-get install python-scipy

Scikit Learn is a fantastic python-based machine learning package, it includes algorithms for both supervised and unsupervised learning. Moreover, it includes support for sample datasets, data import tools, and model evaluation.

Scikit Learn is included with your Ubuntu distribution, but the default is about 2 versions behind. The best way to install Scikit Learn is to use PIP.

type: pip install scikit-learn

The installation process includes building many of the packages from scratch; much of the code base is written in C. Check the installation for errors. You can verify by checking new files in /usr/local/lib/python2.7/dist-packages for sklearn.

Getting samples

It is easy to find samples and run them in IPython Notebook. You can easily get them from various websites and even tutorials. To save you time, I’ve make a small collection at: https://github.com/wenming/BigDataSamples

Get the package by typing: wget https://github.com/wenming/BigDataSamples/archive/master.zip

On your Ubuntu box, you might have to install unzip by typing: sudo apt-get install unzip

Unzip master.zip; then copy content from BigDataSamples-master/ipythonMLsamples into your Ipython dir. A sample command may look like:

cp /home/azureuser/samples/BigDataSamples-master/ipythonMLsamples/* /home/azureuser/.ipython/

Check to make sure the files have been copied.

Running the samples

Go back to the website for IPython, log in, and the files listed should show up in the root directory. Click on K-Means clustering on the handwritten digits data.

Click on the Play button to run the machine learning sample.

The code uses the K-means algorithm with 3 different types of initialization, then plots the results.

The code for making the color scattered plot.

Additional samples to explore

These samples are also includes, feel free to explore them on your own.

A demo of K-Means clustering on the handwritten digits data
A demo of structured Ward hierarchical clustering on Lena image
Faces dataset decompositions
Gaussian Processes regression
Manifold learning
Non-linear SVM
Hand writing recognition using SVM
Hierarchical clustering-structured vs unstructured ward
demo2 of the K Means clustering algorithm
Weighted SVM
Visualizing the stock market structure

Conclusion

IPython Notebook gives us a quick and easy way to share compute resources through the web-based IPython notebook interface. Scikit-Learn, NumPy, and Scipy all simply work out of the box for IPython notebook. The simple, yet powerful combination lets users focus on learning and getting the data analysis done.

In the next blog, we will introduce additional packages in Python that can be used for Data analysis including scaling out using clustering.

Data Science in a Box using IPython: Installing IPython notebook (2/4)

HPC Trekker — Tue, 09 Apr 2013 21:45:41 GMT

In the previous blog, we demonstrated how to create a Windows Azure Linux VM in detail. We will continue the installation process for the IPython notebook and related packages.

Python 2.7 or 3.3

One of the discussions that happened at the Python in Finance conference is which version of Python you should use? My personally opinion is that unless you have a special need, you should stick with Python 2.7. 2.7 comes as the default on most of the latest Linux distros. Until 3.3 becomes the default Python interpreter on your OS, it is better to use 2.7.

The Basics of package management for Python

There are several ways you can get Python packages installed. The easiest is probably by running the OS default installer, but sometimes it may not have the latest version in the version of Linux you are running. For Ubuntu, apt-get is the installer for the OS. apt-get will install your packages in /usr/lib/python/dist-packages.

Another option is to use easy_install. Easy install is part of Python, not part of the Ubuntu OS. We need to have python-setuptools package installed using apt-get first, before being able to use it. If you use easy_install, all your packages will end up in /usr/local/lib/python/site-packages instead.

type sudo apt-get install python-setuptools

PIP is another tool for installing and managing python packages, it is recommended over easy_install. For our purposes, we simply will use which ever of these tools that can install our packages easily and correctly.

type sudo apt-get install python-pip, this might take a few minutes as pip has many dependency packages that it must install.

`Installing IPython, Tornado web server, Matplotlib and other packages`

`Matplotlib is a popular 2D plotting library, it is one of IPython notebook’s component. As you interact with the Notebook, plots are generated on the server using matplotlib and sent for displaying in your web browser.`

To install, type: sudo apt-get install python-matplotlib

IPython notebook is browser based, it uses the Tornado webserver. The Python-based Tornado webserver supports web sockets for interactive and efficient communication between the webserver and the browser.

To install, type: sudo apt-get install python-tornado

Upon completion, we will now install Python itself. The IPython team recommends installing through easy_install to get the latest package from their website.

sudo easy_install http://github.com/ipython/ipython/tarball/master

This should install version 1.0 dev version of IPython.

We also need to install a package called Pyzmq, Zero MQ is a very fast networking package that IPython uses for its clustered configuration. IPython is capable of interactively controlling a cluster of machines and run massively parallel Big Compute and Big Data applications.

Type: sudo apt-get install python-zmq

Finally, Jinja2, is a fast, modern and designer friendly templating language for Python is is now required for IPython notebook.

Type: sudo apt-get install python-jinja2

Configuring IPython notebook

Type: ipython profile create nbserver to create a profile. The command generates a default in your home directory under .ipython/profile_nbserver/ipython_config.py Note that any directory starts with a “.” is a hidden directory in Linux. You must type ls –al to see it.

The .ipython directory is shown below in blue.

Once we’ve created a profile, the next step is to create an SSL certificate and generate a password to protect the notebook webpage.

Type: cd ~\.ipython\profile_nbserver to switch into the profile we just created.

Then, type: openssl req -x509 -nodes -days 365 -newkey rsa:1024 -keyout mycert.pem -out mycert.pem to create a certificate. Below is a sample session we used to create the certificate.

Since this is a self-signed certificate, the notebook your browser will give you a security warning. For long-term production use, you will want to use a properly signed certificate associated with your organization. Since certificate management is beyond the scope of this demo, we will stick to a self-signed certificate for now.

The next step is to create a password to protect your notebook.

Type: python -c "import IPython;print IPython.lib.passwd()" # password generation

Next, we will edit the profile's configuration file, the ipython_notebook_config.py file in the profile directory you are in. This file has a number of fields and by default all are commented out. You can open this file with any text editor of your liking, and you should ensure that it has at least the following content, you may use either the Unix vi editor or nano which would be easier for beginners.

Make sure you make a copy of the sha1:c70c9b9671ef:43cf678c8dcae580fb87b2d18055abd084d0e2ad string you got from the python password generator line above.

Type: nano ipython_config.py

This will go into the editor, copy the appropriate line into your editor. Note # is the comment sign for Python.

c = get_config()
   
 # This starts plotting support always with matplotlib
 c.IPKernelApp.pylab = 'inline'

 # You must give the path to the certificate file.

 # If using a Linux VM:
 c.NotebookApp.certfile = u'/home/azureuser/.ipython/profile_nbserver/mycert.pem'

 # Create your own password as indicated above
 c.NotebookApp.password = u'sha1:c70c9b9671ef:43cf678c8dcae580fb87b2d18055abd084d0e2ad' #use your own
  
 # Network and browser details. We use a fixed port (9999) so it matches
 # our Windows Azure setup, where we've allowed traffic on that port

 c.NotebookApp.ip = '*'
 c.NotebookApp.port = 8888
 c.NotebookApp.open_browser = False

Press control –X to exit nano and press Y to save the file.

Configure the Windows Azure Virtual Machines Firewall

This was done in Post 1 of this blog series.  Please see Create your first Linux Virtual Machine section of the blog.

Run the IPython Notebook

At this point we are ready to start the IPython Notebook. To do this, navigate to the directory you want to store notebooks in and start the IPython Notebook Server:

Type: ipython notebook --profile=nbserver

You should now be able to access your IPython Notebook at the address https://[Your Chosen Name Here].cloudapp.net.

In our case it is: https://ipythonvm.cloudapp.net

Type in the Password you set when you ran the python -c "import IPython;print IPython.lib.passwd()" command.

Once logged in, you should see an empty directory. Click on “New NoteBook” to start.

To reward your hard work, we’ll have IPython notebook plot a few donuts for us. You can copy and paste the code from: http://matplotlib.org/examples/api/donut_demo.html Please your cursor to the end of the last line, Press shift + Enter to run the code right after the last line. If all goes well, you should see a set of 4 chocolate donuts almost instantly.

Conclusion

In the second part of this blog series, we showed you the minimum steps to install the IPython notebook inside a Windows Azure VM running Linux Ubuntu 12.10. In the next blog, we’ll take a look at a few popular, common packages for machine learning, data analysis, and scientific Computing. If you have questions, please contact me at @wenmingye on twitter.

Data Science in a Box using IPython: Creating a Linux VM on Windows Azure (1/4)

HPC Trekker — Tue, 09 Apr 2013 17:22:54 GMT

I just returned from the Python in Finance Conference in New York, I would like to thank Bank of America and Andrew Shepped organizing the event. It was not difficult to see the popularity of Python in the financial community; the event was quickly sold out with over 400 attendees. I gave a 35 minute talk on Python and Windows Azure, and was pleasantly surprised by the amount of interests from the audience and there after. The purpose of this tutorial series is to help you to get IPython notebook installed and start playing with machine learning, and other data science packages in Python.

IPython: Convenience leads to mainstream popularity

One Python package that really stood out at the conference was the IPython notebook. Almost every single presenter mentioned the greatness of IPython notebook. It is a web based Python environment that makes sharing Python code/projects that much easier. IPython was developed by my former colleagues from Tech-X corp and alumni, Brian Granger and Fernando Perez from the CU Boulder Physics dept. Over the years, I have collaborated, and helped to fund some of the work for the project to get IPython running smoothly, especially on Windows HPC Server and on Windows Azure cluster. It is good to see these investments have paid off and benefited the Python community greatly. Most recently, Microsoft External Research has made a sizable donation to the IPython foundation to further support the community, the announcement was made at PyCon this year.

Due to high demand from recent conferences, we’ll do a walk through of the installation process with more details for those who are new to either IPython or Windows Azure. The original instructions can be found on the official site of Windows Azure.

Windows Azure free trial sign up

Windows Azure is Microsoft’s Cloud platform, we support both Windows, and Linux VMs. The free trial gives you 3 months free with 750 core hours each month, 70 GB free storage and so on. The Sign up process is quick and completely risk free, your credit card will NOT be charged until you specifically instructing Azure to do so. You will need a liveID.

Login and sign up for the Virtual Machine Preview Feature

Since Windows Azure Virtual Machines or our IaaS (infrastructure as a service) is still in preview, you will need to log in through the portal and then enable the preview feature at: https://account.windowsazure.com/PreviewFeatures

Click on Try it now to enable the preview feature. You will get queued for approval. This process may take a few minutes to a day depending on availability. For us, it became available instantly by going back to and refresh the Windows Azure dashboard.

Upon signing up for the VM preview feature, Virtual Machines menu item appears in the dashboard.

Create your first Linux Virtual Machine

IPython works really well for both Windows and Linux instances. In this tutorial, I would like to take this opportunity to show majority of the readers here who are Windows users how to get up and running on Linux. As I believe that a good developer should be tools and platform agnostic.

Click on +NEW, then select Compute and Virtual Machine

Use the QUICK CREATE option. Fill out the fields with DNS Name, this is the name of your machine. I picked Ubuntu 12.10, this is a preferred VM on the IPython development team. You may want to pick a smaller VM size for the trial, as it may run out much quicker with the Extra large. Pick a Secure Password. It is also recommended that you pick a data center closer to where you are. Click on Create A virtual Machine. A Virtual machine along with a storage account will be automatically created for you.

To understand how IaaS Virtual Machines work, please take a look at the diagram below. Windows Azure virtual machines are much more advanced than simple machine hosting. When we normally buy a server box, we use its disks for keeping the OS and data, but if the disk dies it will have to be replaced. If the server dies, we will have to get a new server. In Windows Azure Virtual machine, a user no longer have to worry about such hardware failures or down time. In case there’s hardware failures on the physical host that hosts your VM, your VM can be moved onto a different host. In order to do this, the VM does not use local physical hard drive, but instead it uses virtual drives sitting on Windows Azure Storage remotely. Windows Azure Storage keeps 3 copies of your Image in case of physical drive failures on Windows Azure storage itself. Such architecture gives us flexibility, reliability and great service level for preventing down time. You can also attach multiple drives to the VM depending on its size. For an extra large instance, we can attach up to 16 drives at 1TB each. You can read more about Windows virtual machines here.

It only takes a few minutes to provision a Windows Azure Virtual Machine. IPythonVM’s status is now running.

Configuring your VM for log in

SSH details or the default way of logging into a Linux machine are at the bottom of the Dashboard page. In case you want to change the port to its default 22 instead of randomly selected port 50390 listed here, you will need to do that on the End points Tab at the top of the page.

Click on Edit the endpoint at the bottom and change the public port to 22 from 50390. This may take a few seconds for the changes to reflect.

To expose the IPython notebook webserver, we need to add an additional end point. We will be running the web server internally at port 8888, and expose it at 443 as the public end point.

Click on Add Endpoint

Port 443 has been created for the IPython VM.

Log into Your Windows Azure Linux VM

Download Putty or your favorite SSH client to login. Use the full hostname displayed on the dashboard for your VM.

Accept the remote SSH key, then type in your user name and password to login. By default it is azureuser and the passwd you created.

Security Updates and patches

Linux machines that are not secure are the primary attack targets on the internet, is is advised that you immediately and frequently update your VM with security patches. The commands are simple:

sudo apt-get update // note that sudo allows you to run command as the super user (root), you will need to type in your own password.
sudo apt-get upgrade // once in a while you may want to upgrade your packages too.
adduser allows you to add additional users.

update command results above.

upgrade may ask user input, and will take a while to complete.

Conclusion

This is the first in a blog series that shows you how to turn a Windows Azure VM into a powerful IPython-based machine learning in a box solution. If you have questions please contact me via @wenmingye on twitter. In the next tutorial we are ready to get all the Python packages installed.

Enter the Big Data Matrix: analyzing meanings and relations of everything (2/2)

HPC Trekker — Mon, 08 Apr 2013 02:00:00 GMT

Running the Python example step by step:

We explained the basic idea behind LSA or latent semantic analysis in the first part of this blog.

We built a matrix by word counting for each document. The set of document vectors are then sorted by words they appear in.
Then we applied SVD (single value decomposition) on the document and took a smaller number of Eigen values to shrink the three newly decomposed matrices. We keep these three smaller matrices as the basis for our data model.
Any new documents can be computed by a formula rather than having to run SVD again.
We can then use the new matrix to compute the similarities of word vectors.

In the second part of this tutorial, we’ll go through a simple example with real code.

This is the original corpus.

Word count gives us a matrix composed by Matrix[ row of words, column document]

Compute SVD using NumPy

Let’s run the actual code, you can find the Python code here in github. A matlab script is also available.

First, start the PyLab console Window. If you have not downloaded Enthought Python Distribution, please get it from the download link.

from numpy import *

from numpy.linalg import svd

The SVD solver is part of the NumPy package.

The next step is to enter the word matrix that represent all the sentences and word occurrences in them.

A = array ([( 1., 0., 0., 1., 0., 0., 0., 0., 0.),
       ( 1., 0., 1., 0., 0., 0., 0., 0., 0.),
       ( 1., 1., 0., 0., 0., 0., 0., 0., 0.),
       ( 0., 1., 1., 0., 1., 0., 0., 0., 0.),
       ( 0., 1., 1., 2., 0., 0., 0., 0., 0.),
       ( 0., 1., 0., 0., 1., 0., 0., 0., 0.),
       ( 0., 1., 0., 0., 1., 0., 0., 0., 0.),
       ( 0., 0., 1., 1., 0., 0., 0., 0., 0.),
       ( 0., 1., 0., 0., 0., 0., 0., 0., 1.),
       ( 0., 0., 0., 0., 0., 1., 1., 1., 0.),
       ( 0., 0., 0., 0., 0., 0., 1., 1., 1.),
       ( 0., 0., 0., 0., 0., 0., 0., 1., 1.)])

Now run apply SVD to decompose the matrix into 3:

U,sigma,V = svd(A) // Numpy built in function.

Results of the decomposition, you get 3 Matrices, U, sigma (W Matrix), V. Let me explain each one of them.

The U Matrix

These values are basically a coefficient times the original vector, you are looking at the U matrix.

The sigma Matrix (W matrix)

Or the one that contains all the Eigen values on its diagonal, we will be pick to use perhaps 2 of these Eigen values for our work. Why 2? That is purely by experimentation. In general you should pick about 300 in a really large matrix, and 2-3 in a really small matrix like this one. Your job as the data scientist is to play with the model and find the optimal number of Eigen value for this particular dataset.

The V Transposed Matrix

This is the word matrix, or the Vt matrix.

Dimension Reduction

As discussed earlier, the next step is to do a dimension reduction. In our case, we pick n=2. We are trying to compute the 3 new matrices in this step. U matrix should have 2 columns, W(Sigma) matrix should have 2x2, and the Vt matrix should have 2 rows.

In the code, we will make a new matrix and copy over 2 Eigen values.

Sigma = zeros_like(A) # A temp matrix A filled with 0. Same as Sigma = A.copy().fill(0)

n = min(A.shape) # should return 9, since the original A matrix is 12 x 9, the shorter dimension is 9 which is N.
Sigma[:n,:n] = diag(sigma) # Fill the matrix with Eigen values in diagonal.

U2=U[:,:2] take 2 columns of the decomposed U matrix.
S2=Sigma[:2,:2] ## take 2 Eigen values for the new W Matrix. (N xN) in the middle.

V=transpose(V)
V2=V[:,:2] # take two rows of V(transposed); The matrix to the right.

Multiply them back,

A2=dot(U2,dot(S2,transpose(V2))

The New Matrix ready for computing meaning of words

This is the New Matrix that we now can use to compute the relations. Notice we are comparing the word vectors using the Cosine function.

print "relation between human and user: ", dot(A2[0,:],A2[ 3,:])/linalg.norm(A2[0,:])/linalg.norm(A2[ 3,:]) # human is close to user (row 0, row 3)
print "relation between human and minor: ", dot(A2[0,:],A2[11,:])/linalg.norm(A2[0,:])/linalg.norm(A2[11,:]) #minors in this context has nothing to do with human. (row 0, row 11)

Human and minor = similar at 0.8878; human minors = –0.275 (not similar).

print "relation between tree and graph: ", dot(A2[9,:],A2[10,:])/linalg.norm(A2[9,:])/linalg.norm(A2[10,:]) #(row 9, row 10)

Conclusion

This example shows you how advanced math models can be applied to text to figure out the relations between words. The same technique can be applied to just about anything that can be turned into a feature vector. Data scientists can fine tune these models to discover interesting things, and ask new questions that normal BI can not help answer. SVD is very useful in big data computation and predictive analysis, you will encounter it often in data analysis.

Questions or comments? follow me on twitter @wenmingye

Enter the Big Data Matrix: analyzing meanings and relations of everything (1/2)

HPC Trekker — Sun, 07 Apr 2013 23:58:00 GMT

Data Science is compute and labor intensive

In the previous blogs, we showed you how to find a dataset, clean it and run simple mapReduce, sort on the dataset. It was meant to give you a flavor of what data science is all about, and I also wanted to expose Big Data’s rather labor intensive nature. It does take some processing power and thinking to work on even just 10 Gigabytes of data. Now you can imagine why it takes a large team at large web 2.0 companies to deal with terabytes of data. To maintain good service levels on those live services, it takes some serious processing and man power. Back to our word count examples, one of the most common questions I get is that what exactly do people do after the word count is done, and why would you do word count in the first place. There are two parts of this blog, first explains how things work in detail, the second blog goes through an example.

Meaning of word count

Word count is the foundation of (NLP) or natural language processing, which is fundamental to applications such as speech recognition, search engines, machine translation, and just about any applications that needs to derive meaning from human input. By counting words and putting that into a mathematical model, you can derive the meaning of a sentence based on the words appear in it, at the same time, the context which words appear also determine the meaning of words. The simplest example is a word cloud.

We will go through a relatively complex example, even if you do not understand the mathematics behind it, please follow along to understand how words of English are turned into a mathematical model, and how relationships can be derived between words based on your model. These mathematical techniques can be applied to just about anything that can be turned into such a model, that includes your Facebook post behaviors, your online purchases, and even your travel patterns.

Python: the Data Modeling Language

If you are working with mathematical models and scientific computing, you are likely to encounter tools such as R, Python, Matlab, SAS, etc. Python is becoming more popular by the day due to its user base and the availability of packages. Another important reason we are using Python here is the fact that most data scientists use Python to get a “feel” for their data, any one of them will tell you that they use “Scripting” to “feel” their data, and that is here to stay. We’ll have a discussion on how Python and Hadoop fit together in a later blog. In a short sentence is that you need to use the right tool for the right job. Hadoop is an amazing and proven tool for scaling out data analysis at Peta-scale, while Python is great for prototyping and analytics for small amounts of data. In production, big data scientists may port, or modify their Python code to run on Hadoop.

It should take you just a couple of day and perhaps even a few hours to get acquainted with it. For this example, we encourage you to install Python with a few numerical packages. Luckily for Windows users, you can simply download EPD from Enthought, our friends in Austin with batteries included. Their distribution provides scientists with a set of tools including over 100 libraries to perform data analysis and visualization. Some of the most common ones include: SciPy and NumPy and matplotlib. Link to the binary download.

Once you have it installed, run a simple test with PyLab. If both import statements ran fine, you have it installed correctly, and those are the packages we need.

Semantic Matrix Model

The basic idea of this example is that the meaning of a document is determined by the words that appear in it, and the meaning of a word is determined by the documents in which it appears. Consider the following piece of text, each sentence consists of an array of words, and the words themselves appear in multiple sentences. Within different context (sentences), words may have different meanings. In this case, the word “tree” in m2 refers to a computer science tree. Graph and Trees are very much the same thing in sentence m2. You’ll also notice that while minors are human in our every day context, the word minor appears in m3 has nothing to do with the word human, while the word “user” refers to human in these sentences. Will a a mathematical model, or a semantic matrix analysis be able to tell them apart? Let us explore.

The first step is, you guessed it, word count. In the semantic matrix below, you can find a word count for each of the words. “User” appears in sentence c2, c3 and c5 1 time each, and we mark all the other context (sentences) that it didn’t appear in as 0. The Word system appeared in c4, 2 times. As you can see, we are simply counting up all the words for each of the sentences and each of the words. In the case of the entire internet, this could become a really really large Matrix. Perhaps, many billions of documents vs. millions of words. The concept of word counting is also known as N-Gram, in the case of counting just 1 word, we call it the 1-Gram, while we could also count 2-grams…. Ngrams. A couple of examples of 2-grams above are “response time”, and “human system.” Then, we will end up with even larger matrix. There are tools in Python that let’s you deal with this such as the NLTK.

The import thing to note here is that we turned the original corpus into a matrix, each document into a document vector, and each word into a word vector. You can do the same with just anything you want to compare relationships with, that was also explained in the “meaning of word count” section above.

To express these vectors in equations:

The meaning of a sentence is equal to adding together of meaning of all the words times a coefficient, or a linear combination of meaning of words. The coefficients are something we need to solve for in this matrix to determine their actual values, these are the a[i, j]. The word & document vectors themselves don’t get changed, but we are trying to find the coefficients.

SVD: Single Value decomposition

Single value decomposition is widely used technique in working with matrix transformation. It is the basis of a number of vector-based methods like Latent Semantic Analysis (LSA) and Principal Component Analysis (PCA), Independent Analysis (ICA). When you work with big data, you will encounter these methods rather frequently especially PCA. In recent context, SVD is used in advanced recommendation engines among other practical uses. By transforming the matrix in different ways using SVD, it allows us to look at meaning of words from different angles, or tuning the nobs to reveal different properties of the matrix.

Let’s go through the process of running SVD on a matrix. If you would like to know more details, consult your linear algebra book. Basically a matrix can be decomposed into 3 matrices. A is the original matrix, and U and V are the new basis. Same vectors, but diff coefficient. U, rows are document vectors but now with diff coefficient. W (the NxN matrix in the middle), only has diagonal Eigen values. V: columns of VT(transposed) are word vectors, since it is transposed.

You do need a sparse matrix solver to do a SOLVE, that is a topic that people have been working on for 50 years in HPC. There are efficient math solver libraries that you can use to compute these 3 matrices. You can find these solvers from Petsc, Trilinos, Python, or Matlab. Your best bet is the Numpy, SciPy library in Python that you just installed. There are also higher level tools that you can use such as the NLTK, natural language processing tool kit’s clustering algorithm API. We will have a lecture on using NLPTK with Hadoop in the future. Another package on Hadoop is the Mahout Machine learning package, it also has a SVD solver that you can use.

Dimension reduction: Smaller matrix but retain the most important part

As we mentioned earlier, the matrix can get rather large when you go to the internet scale. Perhaps SVD isn’t really the right solution, but for modest amounts of Data, SVD can easily handle the computation of a few hundred million cells in a large sparse matrix. Even so, we will need to do a dimension reduction by shrinking the size of the matrix. Eigen values are in decreasing order in the W matrix. We don’t have to keep all of them. We can keep a much smaller N, and it’s a good approximation of the original matrix. In language applications keeping about 300 for documents in the “millions.“

In other words, you are reducing the dimensionality by many orders of magnitude. Visually it is represented by a skinnier U matrix that’s as tall as the original one & flatter Vt Matrix that is as wide as the original one. As we recall from matrix multiplication, when you multiply them together, you still get the M x N dimension back! Now, that is Math Magic by approximation.

SVD only needs to be done once

If you are adding new documents, there are no need to redo this entire process again. That the red dots on the right side of the equation (U matrix’s last row) can be calculated easily by using the Au vector or the last row of the original matrix, AKA the added new document.

Uu = Au * V * W inverse

Au = new document and it is a vector. V, the smaller matrix, and W (inverse).

Distances and Relations

As we recall,

Dot products: They are simply a projected value from 1 vector onto the other; imagine you have two pencils at an angle to each other, the similarity can be computed by projecting a shadow from first pencil onto the second one.

Cosine: normalized dot product, you don’t care about the length, just the direction.

Euclidean distance: compute distance for all the points and add them together,

In any case, we are looking for distance/similarity of vectors, we can calculate meaning of words by comparing their vectors in the new Matrix. The calculation examples will continue into the second half of this blog.

One note is that Euclidean distance and the angle (the inverse-cosine) are metrics. The dot product and the cosine are NOT metrics. A metric should be zero when the distance is zero, it should always be non-negative, and it should obey the triangle inequality, so that the distance A-to-B + B-to-C is always greater or equal to the distance A-to-C (meaning that a roundabout path cannot be shorter than the direct route). That's not true for cosines; cosines will tell you that some roundabout routes are shorter than the direct one.

Conclusion

SVD is one of the more advanced topics and you may not have fully understood it in this blog without a math background. However, the things to remember here are:

1. Data that we collect can be turned into a mathematical model.

2. Documents, or individual behavior data can be turned into a feature vector.

3. These vectors can be magically transformed, factorized to reveal important characters of the matrix and the relations between the various feature vectors.

The example using Python will be through through in detail in the 2nd part of this blog, we will demonstrate to you mathematically that how this computer model can understand that USER = HUMAN.

New Breakthrough in Big Data Technologies: the NullSQL Paradigm shift

HPC Trekker — Mon, 01 Apr 2013 07:32:00 GMT

Mammoth the NullSQL tool

Most of us by now understand the properties of big data. Many of us are already working with big data tools, or NoSQL tools such as Hadoop. I've spent a bit of my spare time in the last 2 months working on prototypes of a new set of tools that can help the big data industry accelerate their progress of handling large amounts of data. The first version, code named Mammoth will be to get the new distribute file system fully implemented and tested. The NullFS, or the Null File System contains a name node which keeps track of a set of Data nodes in a cluster formation.

Each of these data nodes contain a data storage device that is write-only, the write only device has the advantage of being to hold any amounts of data you write onto it. This device is the equivalent of achieving quantum computing in big Compute. It is the underlying breakthrough for the NullSQL paradigm. I have tested my implementation with over 1Exabyte of real data including live data from my inbox. The results are promising. In a cluster of 16 nodes, I was able to process more than 1Exabyte of data in minutes.

The Architecture of Mammoth is similar to Hadoop, it is portable, distributed, fault tolerant, and scalable. More importantly, it does satisfy all 3 aspects of the CAP theorem, Concurrency, Availability, and Partition tolerance. It has two layers, the NullFS Layer, and the MapRemove layer. The MapRemove layer will optimally copy data to the right device that is free. We've fully implemented the device drivers for both Windows and Unix: /dev/null (UNIX) and NUL(Windows). The Job tracker and task tracker can optimally handle batch processing jobs as well as jobs submitted by different users.

Here’s an example for a simple MapRemove job, each data node will run the Map process and write results to /dev/null and send leftover data to the global NullContext, and the Remove process simply checks to make sure that there are no more bits left to be processed. This simple programming pattern allows constant scaling. big O(16 ) ，with constant scaling, you will never need a cluster larger than 16 nodes, as the processing time stays the same regardless how many nodes you use beyond 16, or how much data you need to process.

NullSQL

Mammoth will be available on 2/29 of next year, but pre-alpha versions are already available. the NullSQL paradigm with NullFS and MapRemove allow users to store any amounts of data, write-only for less than 16 compute node cluster with constant speed. I believe it will soon be a valuable tool for many organizations that need to store their data write-only economically. It also opens up new opportunities for cloud companies to provide this as a security storage service, as write-only is inherently secure.

Conclusion

Happy 4/1. @wenmingye

Make another small step, with the JavaScript Console Pig in HDInsight

HPC Trekker — Mon, 01 Apr 2013 06:06:00 GMT

Our previous blog, MapReduce on 27,000 books using multiple storage accounts and HDInsight showed you how to run the Java version of the MapReduce code against the Gutenberg dataset we uploaded to the blog storage. We also explained how you can add multiple storage accounts and access them from your HDInsight cluster. In this blog, we’ll take a smaller step and show you how this works with the JavaScript example, and see if it can operate on a real dataset.

The JavaScript Console gives you simpler syntax, and a convenient web interface. You can do quick tasks such as running a query, and check on your data without having to RDP into your HDInsight cluster head node. It is for convenience only; not meant for complex workflow. The JavaScript has a few features built in, that includes being able to use the HDFS commands such as ls, mkdir, copy files, etc. Moreover, it allows you to invoke pig commands.

Let's go through the process of running the PIG Script with the entire Gutenberg collection, we first uploaded the MapReduce word count file, WordCount.js [link] by typing fs.put() it brings up dialog box for you to upload the WordCount.js file.

Next, you can verify that the WordCount.js file has been uploaded properly by typing #cat /user/admin/WordCount.js. As you noticed, HDFS commands that normally looks like: hdfs dfs –ls has been abstracted to #ls.

We then ran a Pig command to kick off a set of map reduce operations. The JavaScript below is compiled into Pig Latin Java and then executed.

pig.from("asv://textfiles@gutenbergstore.blob.core.windows.net/").mapReduce("/user/admin/WordCount.js", "word, count:long").orderBy("count DESC").take(10).to("DaVinciTop10")

Load files from ASV storage, notice the format, asv://container@storageAccoutURL.
Run MapReduce on the dataset using WordCount.js, results are in the format of, words, and count key value pair.
Sort the key value dictionary by descending count value.
Copy top 10 of the values to the DaVinciTop10 directory in the default HDFS.

This process may take 10s of minutes to complete, since the dataset is rather large.

The View Log link provides detailed progress logs.

You can check the progress by RDP into the HeadNode, it will give you more detailed progress than the “View Log” link on the JavaScript Console.

Click on The Reduce link in the Table above to check on the Reduce Job, notice there shuffle and sort processes. Shuffle basically is the process where the reducer is fed with output with all the mappers output that it needs to process.

Click into the Counters link, there are significant amount of data being read and written in this process. The nice thing about Map Reduce jobs is that you can speed up the process by adding more compute resources. The mapping phase can be significantly speed up by running more processes in parallel.

When everything finishes, the summary page tells us that the pig script was really about 5 different jobs, 07 – 11. for learning purposes, I’ve posted my results at: https://github.com/wenming/BigDataSamples/blob/master/gutenberg/results.txt

The JavaScript Console also provides you with simple graph functions.

file = fs.read("DaVinciTop10")

data = parse(file.data, "word, count:long")

graph.bar(data)

graph.pie(data)

When we compare the entire Gutenberg collection with just the Davinci.txt file, there’s a significant difference, with our new data we can certainly estimate the occurrences of these top words in the English language more accurately than just looking through 1 book.

Conclusion

More data always gives us more confidence, that’s why big data processing is so important. When it comes to processing large amounts of data, parallel big data processing tools such as HDInsight (Hadoop) can deliver results faster than running them on single workstations. Map Reduce is like the assembly language of Big Data, Higher level languages such as PIG Latin can be decomposed into a series of map reduce jobs for us.

MapReduce on 27,000 books using multiple storage accounts and HDInsight

HPC Trekker — Sun, 31 Mar 2013 04:36:00 GMT

In our previous blog, Preparing and uploading datasets for HDInsight, we showed you some of the important utilities that are used on the Unix platform for data processing. That includes Gnu Parallel, Find, Split, and AzCopy for uploading large amounts of data reliably. In this blog, we’ll use an HDInsight cluster to operate on the Data we have uploaded. Just to review, here’s what we have done so far:

Map Reduce

Map reduce is the programming pattern for HDInsight, or Hadoop. It has two functions, Map and Reduce. Map takes the code to each of the nodes that contains the data to run computation in parallel, while reduced summarizes results from map functions to do a global reduction.

In the case of this word count example In JavaScript, the mapping function below, simply splits words from a text document into an array of words, then it writes it to a global context. The map function takes three parameters, key, value, and a global context object. Keys in this case are individual files, while the value is the actual content of the documents. The Map function is called on every compute node in parallel. As you noticed, it writes a key-value pair out to the global context: the word being the key and the value being 1 since it counted 1. Obviously the output from the mapper could contain many duplicate keys (words).

// Map Reduce function in JavaScript
var map = function (key, value, context) {
    var words = value.split(/[^a-zA-Z]/);
    for (var i = 0; i < words.length; i++) {
        if (words[i] !== "")
            context.write(words[i].toLowerCase(), 1);
    }
}};

The reduce function also takes key, values, context parameters and is called when the Map function completes. In this case, it takes output from all the mappers, and sums up all the values for a particular key. In the end you get word:count key value pair. This gives you a good feel of how map reduce works.

var reduce = function (key, values, context) {
    var sum = 0;
    while (values.hasNext()) {
        sum += parseInt(values.next());
    }
    context.write(key, sum);
};

To run map reduce against the dataset we have uploaded, we have to add the blob container in the cluster’s configuration page, if you are trying to learn how to create a new cluster. Please take a look at this video: Creating your first HDInsight cluster and run samples

HDInsight’s Default Storage Account: Windows Azure Blob Storage

The diagram below explains the difference between HDFS, or the distributed file system natively to Hadoop, and the Azure blob storage. Our engineering team had to do extra work to make the Azure blob storage system work with Hadoop.

The original HDFS uses of many local disks on the cluster, while azure blob storage is a remote storage system to all the compute nodes in the cluster. For beginners, all you have to know is that the HDInsight team has abstracted both systems for you through the HDFS tool. And you should use the Azure blob storage as a default, since when you tear down the cluster, all your files will still persist in the remote storage system.

On the other hand, when you tear down a cluster, the content you store on HDFS contained on the cluster will disappear with it. So, only store temp data that you don’t mind losing in HDFS. Or before you tear down the cluster, you should copy them to your blob storage account.

You can explicitly reference hdfs (local) by using hdfs:// while asv:/// to reference files in the blob storage system. (default).

Adding Additional Azure Blob Storage container to your HDInsight Cluster

On the head node of the HDInsight cluster in C:\apps\dist\hadoop-1.1.0-SNAPSHOT\conf\core-sites.html, you need to add:

<property>
<name>fs.azure.account.key.[account_name].blob.core.windows.net</name>
<value>[account-key]</value>
</property>

For example, in my account, I simply copied the default property and added the new name/key pair.

In the RDP session, using the Hadoop commandline console, we can verify the new storage can be accessed.

In the JavaScript Console, it works just the same.

Deploy and Run word count against the second storage

In the samples page in the HDInsight Console.

Deploy the Word Count sample.

Modify Parameter 1 to: asv://textfiles@gutenbergstore.blob.core.windows.net/ asv:///DaVinciAllTopWords

Navigate all the way back to the main page and click on Job History, find the job that you just started running.

You may also check more detailed progress in the RDP session, recall that we have 40 files, and there are 16 mappers total (16 cores) running in parallel. The current status is: 16 complete, 16 running 8 pending.

The job completed within about 10 minutes, and the results are stored in DaVinciAllTopWords directory.

The results is about 256mb

Conclusion

We showed you how to configure additional ASV storage on your HDInsight Cluster to run Map Reduce Jobs against. This concludes our 3 part blog Set.

Preparing and uploading datasets for HDInsight

HPC Trekker — Sun, 31 Mar 2013 01:04:40 GMT

In the previous blog http://blogs.msdn.com/b/hpctrekker/archive/2013/03/30/finding-and-pre-processing-datasets-for-use-with-hdinsight.aspx we went over how to get English only documents from the Gutenberg DVD. We showed you the Cygwin Unix emulation environment and also some simple Python code. The script takes about 15 minutes to run. Async or some simple task scheduling would probably have saved us some time in copying about 25,000 files. We will continue to explore some of the Unix utilities that are useful for data processing.

After the Script finished running, we go into the zips directory and did a count on total number of files:

Some of these files are in zip format and some are text files. We could simply upload these files to HDInsight, but in general it is a bad idea to send lots of small files for Hadoop to process. The best way to do this is to combine all the text files into a smaller set of larger files. To do this, we need to unzip these files first, and then combine them into similar sized chunks in 250mb in size. 64MB – 256 MB are common block sizes for Hadoop file systems.

Installing and using Gnu Parallel

As we saw earlier, it was painfully slow to process 25000 files in serial execution. Parallelism in this case might help when it comes to unzipping the files, as long as the extraction process is CPU bound. GNU Parallel is a set of Perl Scripts that can help you do simple task based parallelism. Download them from: ftp://ftp.gnu.org/gnu/parallel/ You might want to get a more recent version from 2013.

Building gnu Parallel is like any raw Unix packages. You need to Unpack, configure and then run Make. Please make sure these utilities are installed under Cygwin. If not, you can simply re-run setup.exe from http://cygwin.com/ . You should get “make”, “wget”, as well. Unfortunately, gnu parallel is not part of the cygwin pre-built packages.

Open gnu parallel with WinRAR and press control+C, copy the directory and paste it into a temp location. In this case, e:\temp

In the Cygwin Shell, navigate to the parallel package directory, and type ./configure;make

Finally, make install, by default, most raw Unix source packages will install everything in /usr/local/

You can verify this by typing which parallel, it will show you that parallel is in /usr/local/bin (binary).

When we have large amount of files(26808 total), unzip *.zip would not even work properly.

Instead, we can list the files and pipe it to work with gnu parallel. but first, let’s run chmod 555 *.zip to make sure we can read the zip files for unzip.

Then the command: ls *.zip |parallel unzip

Well have other chances to use parallel in the future for processing files. By default, gnu parallel will use number of cores the CPU contains to spawn the sanme number of processes, in this case 4 parallel processes or tasks. How well gnu parallel speeds up the processing depends on the actual workload, if this is disk bound work, then multiple processes won’t help, but if it is CPU bound work, then it would. The best way to find out is to run a benchmark test with and without gnu parallel. You can find more examples here http://en.wikipedia.org/wiki/GNU_parallel

The Unix “Find” Command

The Unix find command is extremely powerful, you can use it in conjunction with GNU Parallel. In this step of the tutorial, we will need to combine the 27000 text files we just extracted and prepare them as 250MB blocks to upload to Windows Azure Blob Storage. Some of these text files are in the root directory, some are in sub dirs. The easiest way is to combine all text files into one giant file, and then split it up. With “find”, we can accomplish this by a single command:

find ./ –name “*.txt” –exec cat {} >> giant_file.txt \;

Note that {} is the argument list, and >> means “append”

The text file is about 10GB in size.

The Unix Split Command

We often need to split a larger file into smaller chunks, split is a very useful command for data files. You can split by number of lines, or simply by total number of chunks. In our case, we need to split the 10GB file into 40 files to get approximately 250MB each.

mkdir split_files; cd split_files create a directory that we keep the split files separately, and cd into it.

In split_files directory, type split –n 40 ./giant_file.txt to start the process.

A list of files with auto-generated file names appear in the split_files directory. The next step is to upload these files to the Blob Storage.

The Windows Azure AZCopy Utility

Download the Windows Azure Blob copy utility from Github, then copy it to c:\cygwin\usr\local\bin

The AZcopy utility can copy files to/from blob storage, you can learn more about it at: http://blogs.msdn.com/b/windowsazurestorage/archive/2012/12/03/azcopy-uploading-downloading-files-for-windows-azure-blobs.aspx Or you can get help by typing AzCopy /?

In our case, we are copy files to a blob container we created on Azure blob storage account. To do so, you need to create an new storage account, it is recommended that you do that in the east data center, or the data center which your HDInsight cluster will be created.

I recommend turning off Geo replication to keep cost low.

You can add/remote container by selecting the containers tab in Gutenbergstore storage account.

We will be using this command to upload all the files to blob storage: (please note you should replace your own keys with /destKey switch) The storage account keys are at the bottom tool bar, “manage keys".

wenmingy@LPA-MSFT /cygdrive/e/temp/INDEXES/zips/split_files
$ AzCopy ./ https://gutenbergstore.blob.core.windows.net/textfiles/ /destKey:yourKey

Note ./ means currently directory, destination is the URL for the blob container.

The AzCopy Utility can perform at excellent transfer speed using the default configuration. We sustained 18Mbps over our wifi network. AzCopy uses 8 threads/core as its default number for transfer.

Once done, you should find the files in Blob storage by inspecting the container using Azure Storage Explorer.

Conclusion

In this part of the tutorial, we learned how to use a few useful Unix tools including Gnu Parallel, Find, Split, and the AzCopy command to efficiently deal with large files using the Cygwin environment. It should also give you a flavor of what Data scientists do on a daily basis when it comes to dealing with data files. We have not touched on how to use HDInsight to do some of these tasks in Parallel. In the next blog, we will cover Map Reduce in detail on doing word count on the Gutenberg files we just uploaded.

Finding and pre-processing datasets for use with HDInsight

HPC Trekker — Sat, 30 Mar 2013 22:02:29 GMT

Free datasets

There are many difficult aspects associated with Big Data, getting a good, clean, well tagged dataset is the first barrier. After all, you can not really do much data processing without data! Many companies are yet to realize and discover the value of their data. For those of you who want to play with HDInsight, the good news is that there are plenty of free datasets on the internet, here are some examples:

The Million Song Dataset: A freely available collection of audio features and metadata for a million contemporary popular music tracks. You can get up to a few Terabytes worth. This is a very interesting dataset for a recommendation engine. I have a simple tutorial to walk you through on WindowsAzure.com at http://www.windowsazure.com/en-us/manage/services/hdinsight/recommendation-engine-using-mahout/ Example

Freebase: A community-curated database of well-known people, places, and things http://www.freebase.com/ Freebase stores its data in a graph structure to describe relationships among different topics and objects. APIs are provided for running MQL queries against the graph dataset. Free base is very useful when it comes to data mash up: make looking up facts in the Freebase being part of your big data processing.

Data.Gov: One of my favorite places to find data is Data.gov, it contains datasets ranging from census, to earth quake, to economics data.

Wikipedia and its sub projects: http://en.wikipedia.org/wiki/Wikipedia:Database_download You can download the entire wikipedia if you wanted to. I am personally guilty of downloading 100s of gigabytes from wikipedia for parsing projects a few years ago.

These are just a few examples of free datasets you can get from the internet.

DataMarket: Microsoft has its own data market on Windows Azure, you can access them through Odata, I have written a hands on lab on how to get data into HDInsight here: https://github.com/WindowsAzure-TrainingKit/HOL-WindowsAzureHDInsight/blob/master/HOL.md Example

An example: Getting the Gutenberg free books dataset

If we want to get a large dataset that’s well structured for a simple word count example, where would we go about finding such datasets? We might want to craw the web, or search our own computer for text documents, but that can be quiet involved. Luckily, Gutenberg.com has a huge collection of free books. The largest and latest dataset can be download, here’s the link to one of their DVD ISO images that contain much of the archive: ftp://snowy.arsc.alaska.edu/mirrors/gutenberg-iso I recommend the ISO image pgdvd042010.iso, it is about 8 GB. Once you download the ISO, take a look inside. If you have older versions of Windows OS, you might want to use winRAR to peak inside, windows 8 mounts it for you as a drive automatically.

The ISO contains a web interface INDEX.HTML, and many books in various formats. Some books have images so they are in HTML or RTF formats, some are simply text without any illustrations. There are also books in different languages, and encoded in various formats. As you can see it becomes a big job to even prepare this modest dataset. In our case, we would like to get all the English text files, for that we will have to use the meta data from the index pages as much as we can. Click on the DVD and open the INDEX.HTML page by right click and Open With Internet explorer.

Now feel free to browse the index pages. You will soon discover that the pages actually contain good clue on if the book if English or not.

Click on Browse by title:

HTML Page for each individual files.

The best way to get all the English text is to write a simple crawler and copy all the English documents into a directory for further processing. The code is relatively straight forward, and I spent a couple of hours writing this in Python. You are welcome to use your favorite language. For those of you who are not familiar with the Python programming language, it is one of the most popular scripting languages for data processing. The Syntax is simple but may not be as intuitive to C, C# developers. Full source available on github: https://github.com/wenming/BigDataSamples/blob/master/gutenberg/gutenbergcrawl.py

First section of the code:

We need an HTML Parser(HTMLParser, htmlentitydefs), a crawler or http client (urllib), and commands for copying files. Please note we are using Python 2.7, not 3.0. Python 2.7 is still the most popular at this time.

Let’s look at the main function first: make a directory called zips, this is where all the final ZIP files will go if they qualify as English text.

Then, get a list of title pages a-z, other. These HTML index pages reside in the INDEXES directory, for each of these files, we unleash our crawler by running the function called: get_english_only_urls(). The TITLES_*HTML pages contain information about each of the books and their language, and location of the book’s property html file that contains the actual book’s text file URL location.

The next step is to open each of the TITILES*.HTML find the urls for each of the book’s HTML page, and then process them one by one. Notice TitleFilesHTMLParser is called here.

The title page parser is called, it only adds books with (English) tags next to it for processing.

Now parse each HTML page for the individual books. Notice we are calling BookPropertyHTMLParser() on each of the HTML pages (per book).

The BookPropertyHTMLParser simply finds the <a href=”…..*.zip> tags and copy the right zip files over the file to the zips directory. The code is a stub for future modification in case image, html, and pdf files need to be processed.

Running the sample:

Extract the ISO content into a temp directory, on Windows 8 you can simply control +A copy and paste into a temp directory. Other versions, you can use WinRAR for the extraction.

Install Cygwin: http://cygwin.org/ Make sure Python 2.7 is installed, also make sure Unzip is installed. It certainly helps to learn some basic Unix commands if you are dealing with lots of text files, and raw data files.

Get the code: https://raw.github.com/wenming/BigDataSamples/master/gutenberg/gutenbergcrawl.py, put the file in the root/INDEXES directory of Gutenberg files.

Open the Cygwin terminal and change directory to where you extracted your files, in my case I stored the data in E:\temp in Cygwin, you’ll see your drive in a special format: /cygdrive/e/temp/INDEXES (unix style directory).

cd e: to change Drive letters in the cygwin command window.

Another note is that your python script will need execute permission. In Unix shell, you can change it by setting the permission bits in the format of read,write, execute. (rwx). We wanted this file to be rwx, bits are set to be 111 for yourself, and r-x only 101 for group and world. Thus it is really: 111 (you/user) 101(group) 101(everyone). That translates into 755, thus the chmod 755 command.

Now, we are simply going to run the gutenbergcrawl.py by executing ./gutenbergcrawl.py Why the ./ in front? That is to specify that you want to run the command from the current directory. By default, bash shells don’t pick up the ./ directory for security reasons; you may accidentally run a script that you don’t intend to.

Conclusion

In this tutorial, we showed you how to find datasets on the internet for demos and examples. We went through a detailed example of pre-processing Gutenberg datasets. In this example, we used Cygwin, which is a Unix emulation environment for Windows, and we showed you some simple Python code for parsing HTML pages to extract meta data. This gives you a flavor of what data scientists do when it comes to getting and pre-processing datasets.

In later blogs, we will explore how we can use this dataset to run word count on HDInsight.