Data Wrangling

Slides & Thoughts from Hadoop World NYC

Big data hackers, Apache Hadoop developers, and early adopters from several industries descended on the Roosevelt Hotel this weekend for Hadoop World NYC. I gave a talk on rapid prototyping of data intensive web applications using Hadoop, Hive, Python, and Ruby on Rails. The talk also had a few bits about using R with Hadoop for statistical computing at scale. The sessions were taped, so I’ll update this post with a link to the video when it becomes available.

The slides give a high level overview of how I built the open source trend tracking site trendingtopics.org over a few weeks last June using Amazon EC2 and Cloudera tools. The code for the site is on Github and the raw data it is powered by is available on Amazon Public Data Sets. I’ve also posted a series of tutorials related to trendingtopics on the Cloudera blog over the past few months:

Here are a few resources mentioned in the talk:

Trendingtopics code on github
Wikipedia Page Traffic Statistics Dataset
EMR Forum discussion about using R with Hadoop (scroll down for R code that runs on Twitter data)
David Rosenberg’s R Streaming package on CRAN
How FlightCaster Squeezes Predictions from Flight Data

Conference Highlights

It felt like around half of the attendees of Hadoop World were developers or data hackers I know of via Twitter or the Hadoop mailing lists. This resulted in some decent Twitter coverage via the hadoopworld hash tag. The other half of attendees represented enterprise IT, media companies, government, and financial firms who are either early adopters or interested in using Hadoop.

Some interesting announcements were made in the morning. Amazon added new features for the Elastic MapReduce service, including support for Hive, Cloudera’s Hadoop Distribution, and integration with Karmasphere Studio.

Cloudera’s big news was the launch of Cloudera Desktop, a new web-based unified user interface for users and operators of Hadoop clusters. Note that you can also run the Cloudera Desktop on Amazon EC2. Cloudera announced support for their distribution on Softlayer and Rackspace. They also outlined new features in the latest Hadoop distribution (CDH2), which includes support for HBase and Hadoop 0.20.1.

Vertica announced a partnership with Cloudera, which is an interesting development considering the RDBMS vs. MapReduce debates that took place last year.

I think I actually spent more time talking data with fellow hackers like Joshua Reich and Hillary Mason than I did in the talks, but still managed to catch some good ones by the EHarmony team, Stuart Sierra, Deepak Singh, and several Yahoo people. As a big Python user, it was exciting to hear that Jake Hofman from Yahoo! Research, NY plans on an open source release of a Python based Social Network Library for Hadoop, which he used to generate the Twitter analysis in his talk. A big theme in my talk and others I attended was the use of high level languages on top of Hadoop to accelerate development. Most of the teams I talked to actively use multiple abstractions on top of Hadoop, including Pig, Hive, Clojure, or other languages like Python through Hadoop Streaming.

For further details check out these notes from other attendees:

Amund Tveit has comprehensive notes of the morning and afternoon Hadoop World sessions
The HubSpot team has two posts: Hadoop World 2009 and Hadoop World Impressions
Hillary Mason wrote up some observations on her blog
Deepak Singh, who presented on Hadoop in Bioinformatics, gives his perspective on the conference

How FlightCaster Squeezes Predictions from Flight Data

During the last several years, an increasing number of systems within government and industry have been collecting massive amounts of raw data which often sits untapped in large data warehouses. FlightCaster strikes me as a great example of the next generation of web applications that will leverage that data: bootstrapped startups that apply machine learning and data processing at scale to solve a focused problem people actually care about.

From the site:

“FlightCaster predicts flight delays. We use an advanced algorithm that scours data on every domestic flight for the past 10-years and matches it to real-time conditions. We help you evaluate alternative options and help connect you to the right person to make the change.”

FlightCaster uses data from:

Bureau of Transportation Statistics
FAA Air Traffic Control System Command Center
FlightStats
National Weather Service

I’ve been following the data crunching exploits of Bradford Cross on Twitter, and the launch of FlightCaster seemed like a great opportunity for an “in the trenches” interview on building a machine learning application with Rails & Hadoop. During the interview on FlightCaster, Brad describes some of the challenges of working with flight data, statistical approaches for flight prediction, false negatives in FlightCaster, Clojure, Hadoop & Amazon EC2, YCombinator, and lots more.

Of the 9? people at Flightcaster, how did the roles break down? How did you get started on the problem?

People at YC make fun of us a lot on account of our monolithic team.

We have a core team of 5 founders which breaks down as follows; a CEO, an air travel domain expert, two engineers working on web service, apps, and production issues, and me for research.

I have a secret agent collaborator working with me who has been very helpful with research and scalable compute infrastructure.

We also have a few other engineers doing a mix of stuff. This is a speed thing. We wanted to launch an iPhone app, blackberry app, and website all at the same time. We built it all very fast.

We got started on the problem thanks to Evan Konwiser and his peculiar and endearing obsession with the commercial air travel industry.

Did you have someone on the team with domain expertise who was familiar with the flight or weather data sources?

Absolutely, that is Evan Konwiser. He has been instrumental, and not just for familiarity with the data.

The airline industry is a very idiosyncratic industry. It would be hard to learn a lot of the subtle domain logic via induction alone. Our machine learning approach uses a mix of analytical and inductive learning.

What was the biggest challenge in working with the public flight and weather data? Is there a dataset that isn’t out there right now that might make predicting flight delays easier for you?

The public data set that we use is the “on-time database” published by the FAA. The data set is tricky to get all in one place since the FAA does not provide any decent API to it. The biggest issue is that we make real time predictions, so we needed a historical set of captured real time data, which we had to create ourselves.

Having a more amalgamated real time dataset going back historically for a decade would be a big help. Having more modernized ways of accessing the data would be helpful.

Until then, if anyone wants to buy it, we will sell it to them for a very high price … and to sweeten, they must throw in a few obscure, expensive machine learning books that I have on my Amazon wish list.

I’ve been a big fan of using the combination of Rails, Hadoop, and Amazon EC2 along with a high level language (in your case Clojure). Any tips for people out there thinking of using a similar technology stack? How cost effective is running Hadoop on EC2 for you?

Building layer upon layer of abstraction is a big key. On the jvm, you have to do this, it is the path around the verbosity of Java and the vast abyss of poorly done APIs. You just keep searching until you finally find the folks who have built a sane, high level API on top of the thing you want to use - then you wrap it in a high level language like Clojure. The technical term for this is “wrap the crap.”

In our case, we use Cascading as our step up in abstraction on top of Hadoop.

S3 -> EC2 -> Cloudera -> HDFS -> Hadoop -> Cascading -> Clojure. I’m not sure if those layers are exactly the right order, but you get the point. The key is go keep layering until you encapsulate the plumbing and get to the level of abstraction that lets you focus on solving your problem.

Running Hadoop on EC2 has been very cost effective. The biggest issues have come into play with the disconnect between Hadoop and S3. S3 expects open connections to keep reading, and if they don’t, S3 terminates them. S3 is very much the Arnold of the distributed file system world. So if your Hadoop jobs are compute intensive, and they are buffering in data in a lazy loading fashion, they tend to lose the connection to S3 during long processing phases. We’ve worked around this with some hackery, and we are working with Chris Wensel (of Cascading fame) on a more industrial strength solution to the problem.

There are many existing machine learning and statistical computing packages for R, Python, Java, C++, why did you choose to go with Clojure? What were the pros/cons of that approach? Do you use any of those other tools for prototyping or visualization?

Over the years, I have found that, in practice, the statistical and machine learning code is not the big thing to worry about. That code is fun to write, and often you want to tweak and extend the libraries in ways that they have not been designed for. So we use libraries and frameworks for the basics where we can, but we are OK to implement statistical and machine learning algorithms ourselves. I’m quite experienced with this anyway; all the way down to efficient custom data structures built on arrays.

The bigger problem to worry about is in the title of your site; the data wrangling. Especially pre-processing (filtering, transforming, etc) and the general fault-tolerant distributed compute infrastructure. I worked on this sort of thing during my time at Google, and it is far more complex than it seems. It is easy to grasp the concepts, and get an initial implementation, but the edge cases and last mile issues with respect to the fault tolerance are where you take the hit.

Hadoop is a wonderful solution for distributed computation, and since our code is all purely functional, it is very natural for us.

Clojure is ideal for both the data wrangling, as well as the statistical and machine learning code. Also, Clojure plays nice with everything on the jvm so we wrap and use lots of libs from the java world. Put this together with the distributed compute infrastructure that you get with Hadoop, and it starts to make a lot more sense to build these systems in Clojure on the jvm and use Hadoop than it does to use R, python, etc.

That said, if you just need to do quick and dirty prototypes, or don’t have the need or the option to invest in infrastructure for distributed computing, R and SciPy are probably still the place to turn.

At Google, the research scientists prototype in python and R, and then port to C++ for the real scalable map reduce runs. We prototype and run in production on the same language and platform, and although it is not as fast as Google’s C++ infrastructure, we do have the benefit that Clojure is very high level. For large runs, we parallelize with Hadoop, and we just run smaller tasks locally as if our Hadoop infrastructure were not even there. We are not coupled to it, and yet we don’t need to port code or do anything special to run it in distributed mode.

Can you talk more about how you are using Hadoop for Flightcaster? Are most of the jobs I/O intensive, preprocessing a large volume of historical input data, or are they more often cross-validation or simulation runs? Do you tweak your live models then re-train against all the historical data with Hadoop?

Our jobs are CPU intensive - we do a lot of computation per unit of data, even in our data transformation jobs.

We train and test all our models offline, on captured real time data.

Eventually we would like to move to a more incremental online learning approach, but for now we re-train and re-test against newly captured data and re-deploy new the newly trained model.

Any tips for handling bad data/records in large MapReduce jobs?

We’ve been talking to Chris Wensel and cascading has some really cool stuff for this in the form of “filters” that we are not leveraging yet. We do a lot of filtering and scrubbing of our own during the preprocessing phase, but we will be looking at what cascading can do for us here very soon.

The biggest lesson we have learned about bad data is that we should spend more time up front with visualizing the data and making assertions (or filtering via predicates) to verify that our assumptions about the data hold.

I have had these issues in the past with financial data, but not as bad. Can a flight land before it takes off? Are there 68 hours in a day? These are examples of data that is not malformed or missing, but that violates fundamental properties that you expect to hold true, so they can be trickier to catch.

The big problem with not spending more time on this up front is that these issues are expensive to catch downstream because you will be looking through non-intuitive results of complex analysis jobs and it takes a long time to track down the root of such issues. It is similar to the argument for having good unit tests; it is cheaper to find issues at that level than at the system test level. It is also more sanity-preserving.

You probably can’t say much about your secret sauce or algorithms, but can you discuss some general issues you encounter handling conflicting information sources or incomplete data? Do ensemble approaches or online learning play a role?

As I mentioned in a previous response, we want to get into more of an incremental online learning approach, and I think we will be able to soon. Of course this means certain approaches are in and others are out, but that may be OK in our case.

As of right now, we are using a combination of analytical and inductive learning. We compose individual classifiers that are themselves composed of rich domain logic. This is not an ensemble approach, though we may head in that direction very soon.

What we are doing now is more of a network-of-classifiers approach. It is a bit of a strange beast right now, so we would be remiss to call it a Bayesian network. Maybe we could call it a Cardono network in honor of Jerolomo Cardano. It is a bit of an eccentric network that is ahead of its time but waiting for some formalism to come along and straighten it out.

To a large extent, our current approach is an artifact of how quickly we have built our initial model. We have these rich individual domain specific classifiers that are targeted at different features from different data sources, and the approach we are using to learn the composition of these individual classifiers is an area of active research.

What is your general style for attacking prediction problems? Do you start with a single data source and get the entire pipeline running with a simple model, or you dive in building a more complex model with multiple data sources? How did Flightcaster compare to financial prediction?

I like to let simpler cases drive out a lot of the demand for infrastructure early on. As you suggest, I tend to start by getting something working end-to-end with a simple model and a single data source. Then you can start to evolve faster, join in other data sources, and try more deeply theoretical ideas; all on top of a quality infrastructure.

That said, some infrastructure is not required until you get to more complex models, so it is always an evolutionary process where model drives infrastructure.

I made a lot of mistakes early in my career in building trading models where I let me theories get too far ahead of what I could really test in practice. That is not a good place to be. Unfortunately, this is an easy mistake to make.

Flightcaster has been very different from my work in investing in a number of ways. FlightCaster makes predictions by turning the probability distribution estimation problem into a k-way classification problem.

This is a simpler problem than designing holistic investment strategies.

In investing, you have to answer many questions. Selecting the point at which buying and selling occurs is akin to predictive problems in other domains. However, this only answers the question of when to buy or sell.

You also have to decide what to buy or sell - which is called portfolio selection. You also have to decide how much to buy or sell - which is called portfolio allocation. There are also the topics that I like to call risk and exposure accommodation.

The latter subjects of portfolio selection, portfolio allocation, and risk and exposure accommodation are arguably more important than the former subject of timing or predicting entry and exit points. Parameter sensitivity analysis tends to show that return and risk-return metrics are less sensitive to variability in the entry-exit approach as compared with portfolio selection, portfolio allocation, and risk accommodation approaches.

These aspects of financial modeling make it significantly more difficult, and they also seem to largely account for the repeated demise of many so-called “quantitative trading” operations.

Can you say anything about decision points and false alarm rates in travel delay prediction? It seems like there is a big penalty (risk) if somebody misses a flight based on a bad prediction, but a minor annoyance if the flight is delayed and you don’t predict it correctly. Will you guys publish some ROC curves at some point?

There are always two key metrics in learning - in IR they are called precision and recall. We seem to be at somewhere around 85% precision and 60% recall. So discovering more delays is where we need to focus, and our false positive delay predictions are not the big issue for us right now.

We compute confusion matrices, and use them to derive precision, recall, and our false positive and false negative rates.

When you turn numerical probability distribution estimation into k-way classification, one side effect is that not all false positives are equal. If we way you will be delayed by over an hour, but you are delayed by 45 minutes, that not bad at all. But if we say you will be delayed by over an hour and you are on time, that is much worse. So there is a distance aspect to false positives.

We don’t see a lot of bad false positives now, that is, we don’t appear to tell people they will experience a long delay when in fact they will be on time. The bigger issue seems to be our recall - there are a lot of delays that we are just not able to detect yet. Alternatively stated, we have a problem with false negatives in the on time class.

We also have a strong temporal element to all this. How do these numbers change as we get closer or further away from your departure time? We’re working on this analysis right now, and we do hope to publish a lot of useful metrics soon.

How was it working with YCombinator?

YCombinator is amazing. The people are all great; both YC founders and the people they invest in. The exposure we have gotten from being part of the program is itself worth the equity stake they take in the company. YC has put together a really fascinating business model. I would like to be an investor in YC.

Trevor Blackwell is a YC founder, friend, and maker of fine quality luxury robots. Actually, his big new thing is telepresence robots. Check out the bots at anybots.com.

Trevor is the one who lured me into working with the Flightcaster team. I hadn’t met Paul Graham and his Wife Jessica before YC - they totally rock!

It has been an amazing experience and I would encourage anyone to apply; especially if you want to build something that solves a real problem.

Wikipedia Page Traffic Statistics Dataset

I’ve published a Wikipedia Page Traffic Data Set containing a 320 GB sample of the data used to power trendingtopics.org (I’ll talk about Trending Topics more in a upcoming post). The EBS snapshot includes 7 months of hourly page traffic statistics for over 8 Million Wikipedia articles (~ 1 TB uncompressed) along with the associated Wikipedia content, linkgraph, & metadata. The english Wikipedia subset contains ~2.5 Million articles.

It only takes a couple of minutes to sign up for an Amazon EC2 account and set up access to the data as an EBS volume from the Amazon Management Console.

If you want to work entirely from the command line, you will need to complete the steps in the Getting Started Guide. When you are set up to use EC2, launch a small EC2 Ubuntu instance from your local machine:

    $ ec2-run-instances ami-5394733a -k gsg-keypair -z us-east-1a

Once it is running and you have the instance id, create and attach an EBS Volume using the public snapshot snap-753dfc1c (make sure the volume is created in the same availability zone as the ec2 instance)

    $ ec2-create-volume --snapshot snap-753dfc1c -z us-east-1a
    $ ec2-attach-volume vol-ec06ea85 -i i-df396cb6 -d /dev/sdf

Next, ssh into the instance and mount the volume

    $ ssh root@ec2-12-xx-xx-xx.z-1.compute-1.amazonaws.com
    root@domU-12-xx-xx-xx-75-81:/mnt# mkdir /mnt/wikidata
    root@domU-12-xx-xx-xx-75-81:/mnt# mount /dev/sdf /mnt/wikidata

See the README files in each subdirectory for more details on these datasets…

Wikistats

The good stuff is sitting in 5000 files in /mnt/wikidata/wikistats/pagecounts/

    /mnt/wikidata/wikistats/pagecounts# ls -l | wc -l
    5068
    /mnt/wikidata/wikistats/pagecounts# ls -lh |head
    total 260G
    -rw-r--r-- 1 root root  49M 2009-02-26 13:34 pagecounts-20081001-000000.gz
    -rw-r--r-- 1 root root  46M 2009-02-26 13:34 pagecounts-20081001-010000.gz
    -rw-r--r-- 1 root root  47M 2009-02-26 13:34 pagecounts-20081001-020000.gz
    -rw-r--r-- 1 root root  44M 2009-02-26 13:34 pagecounts-20081001-030000.gz
    -rw-r--r-- 1 root root  45M 2009-02-26 13:34 pagecounts-20081001-040000.gz
    -rw-r--r-- 1 root root  47M 2009-02-26 13:35 pagecounts-20081001-050001.gz
    -rw-r--r-- 1 root root  45M 2009-02-26 13:35 pagecounts-20081001-060000.gz
    -rw-r--r-- 1 root root  50M 2009-02-26 13:35 pagecounts-20081001-070000.gz
    -rw-r--r-- 1 root root  51M 2009-02-26 13:35 pagecounts-20081001-080000.gz

This directory contains hourly Wikipedia article traffic logs covering the 7 month period from October 01 2008 to April 30 2009, this data is regularly logged from the wikipedia squid proxy by Domas Mituzas.

Each log file is named with the date and time of collection: pagecounts-20090430-230000.gz

Each line has 4 fields:

projectcode, pagename, pageviews, bytes

    en Barack_Obama 997 123091092
    en Barack_Obama%27s_first_100_days 8 850127
    en Barack_Obama,_Jr 1 144103
    en Barack_Obama,_Sr. 37 938821
    en Barack_Obama_%22HOPE%22_poster 4 81005
    en Barack_Obama_%22Hope%22_poster 5 102081

Wikilinks (1.1G)

Contains a wikipedia linkgraph dataset provided by Henry Haselgrove.

These files contain all links between proper english language Wikipedia pages, that is pages in “namespace 0″. This includes disambiguation pages and redirect pages.

In links-simple-sorted.txt, there is one line for each page that has links from it. The format of the lines is ready for processing by Hadoop:

    from1: to11 to12 to13 ...
    from2: to21 to22 to23 ...
    ...

where from1 is an integer labelling a page that has links from it, and to11 to12 to13 … are integers labelling all the pages that the page links to. To find the page title that corresponds to integer n, just look up the n-th line in the file titles-sorted.txt.

Wikidump (29G)

Contains the raw Wikipedia dumps from March along with some processed versions of the data. One of the useful files I created provides a direct lookup table for wikipedia article redirects in page_lookup_redirects.txt, which can be useful for name standardization and search:

Here is a sample query run when the file is loaded into MySQL:

   mysql> select redirect_title, true_title from page_lookups
               where page_id = 534366;
   +------------------------------------------------+--------------+
   | redirect_title                                 | true_title   |
   +------------------------------------------------+--------------+
   | Barack_Obama                                   | Barack Obama |
   | Barak_Obama                                    | Barack Obama |
   | 44th_President_of_the_United_States            | Barack Obama |
   | Barach_Obama                                   | Barack Obama |
   | Senator_Barack_Obama                           | Barack Obama | 
                          .....                           .....         

   | Rocco_Bama                                     | Barack Obama |
   | Barack_Obama's                                 | Barack Obama | 
   | B._Obama                                       | Barack Obama |
   +------------------------------------------------+--------------+
   110 rows in set (11.15 sec)

The raw wikipedia dump file latest-pages-articles.xml was also post-processed using xml2sql to produce a set of tab delimited text files for use with Hadoop and other tools :

692M page.txt
115M redirect.txt
987M revision.txt
17G text.txt

the corresponding namespace0 files were created by limiting page.txt and redirect.txt as follows:

# grep '^[0-9]*       0       ' page.txt > page_namespace0.txt
# grep '^[0-9]*        0       ' redirect.txt > redirect_namespace0.txt

Quick Visualization of irs.gov Search Queries

Here is a quick visualization I did in honor of April 15th to investigate what people looking for on tax day…

This “query tree” shows the most frequent searches starting with the term “irs”. Each branch in the tree represents a query where the words are sized according to frequency of occurrence. I like how you can see at a glance what the most popular tax forms are by following the “irs tax form …” branch. Apparently form 8868, Application for Extension of Time To File, is in high demand.

It was created by uploading search queries from AOL users leading to clicks on irs.gov during Spring 2006 to Concentrate, which generated the query tree. This image is a snapshot of an interactive flash visualization in Concentrate, where the focus term was “irs”. Looking at query patterns like this can help you get an idea of what people are looking for and how to better organize your site so they can find it quickly.

The interactive flash visualization was developed by Chris Gemignani using Flare with some input from Zach Gemignani and myself and inspiration from the Many Eyes WordTree.

The raw data is from the released AOL Search data sample, and consists of the subset of unique queries leading to clicks on irs.gov from March to May 2006. The IRS queries used to make the visualization can be downloaded here: irs.gov.queries.csv (191K)

Here are the top 10 queries in the file:

Query	Searches
irs	4787
irs.gov	2282
www.irs.gov	1975
internal revenue service	1154
irs forms	608
tax forms	361
irs tax forms	196
internal revenue	158
taxes	142
wheres my refund	139
federal tax forms	125
irs refunds	106

Amazon Elastic MapReduce: A Web Service API for Hadoop

AWS just launched a new service called Amazon Elastic MapReduce that provides the same kind of developer friendly API used for Amazon EC2 or S3 for running Hadoop jobs in the Cloud. You submit a job request and number of instances to the API (pointing to input data and code on S3), and AWS spins up a private Hadoop cluster on EC2, submits your job, and reports back on status through the API. You can cancel or modify jobs using the API, and can even add additional steps to a running job.

I was part of the private beta and wrote a short code sample that shows how to run Python streaming jobs using the service: Finding Similar Items with Amazon Elastic MapReduce, Python, and Hadoop Streaming. As part of the code example, I also pulled together a cleaned up version of the AudioScrobbler dataset for use in music recommendations (it is about 1/4 the size of the Netflix Prize data). The code sample basically implements a Python streaming version of the Pairwise Similarity algorithm found in this paper by Tamer Elsayed, Jimmy Lin, and Douglas Oard and applies it to Netflix Prize ratings and Audioscrobbler playlist data.

The base EC2 images underlying the service are running Hadoop 18.3 on Debian and include NumPy, SciPy, R, BeautifulSoup, and other preinstalled packages useful for Streaming Hadoop jobs. You can use the distributed cache to install other packages like nltk at runtime.

My initial impression is that this will evolve into a powerful tool for people who want to run adhoc mapreduce jobs, prototype MapReduce code on EC2, or interface with on-demand clusters from within their apps. Hopefully we’ll see a MapReduce code/task sharing facility at some point similar to the EC2 pubic AMI system.

Note that in the current release of Elastic MapReduce, input data is copied down from S3 at the start of the job and your cluster shuts itself down upon completion by default (you can override this with the API). Mounting data directly from EBS volumes isn’t supported yet, but I wouldn’t be surprised to see that soon given the potential for integrating with Amazon Public Datasets. Running Dumbo jobs isn’t supported yet since it requires a Hadoop patch for 18.3, but it should be possible when AWS moves to Hadoop 0.21 (which will also bring in a number of other important Hadoop features that are missing in 18.3).

For maintaining a permanent cluster in-house or even a semi-permanent cluster on EC2 with a large amount of data, I would recommend using the Cloudera distribution for Hadoop (it is a one-liner to start an EC2 Hadoop cluster from the command line). I would often bounce between running jobs on my Cloudera EC2 cluster and Elastic MapReduce during development of the code example. If you are getting started with Hadoop, the Cloudera training videos are a great place to get up to speed.

So what can you do with Elastic MapReduce? Here are a few initial ideas:

Offload background processing from your Rails or Django app to Hadoop by sending the ElasticMapReduce API job requests pointing to data stored on S3: convert PDFs, classify spam, deduplicate records, batch geocoding, etc.
Process large amounts of retail sales and inventory transaction data for sales forecasting and optimization
Use the AddJobFlowSteps method in the API to run iterative machine learning algorithms using MapReduce on a remote Hadoop cluster and shut it down when your results converge to an answer

I’ll post more on this later today - including a detailed explanation of using Netflix Prize data in the code example and some next steps for using Elastic MapReduce.

Updated List of Datasets & Video Lectures

New Datasets

It’s spring cleaning time at Data Wrangling. I’ve bookmarked 230 new datasets since publishing my first dataset linkdump in January 2008, so at the request of @mrflip, I’ve appended them to the original post along with a json dump of the tagged links. Flip and the other Infochimps will be pulling anything they might have missed into the infochimps.org dataset repository.

You can check out the new list of datasets at the same url:
“Some Datasets Available on the Web”

Around 85 of these datasets can be redistributed publicly: http://delicious.com/pskomoroch/redistributable+dataset. The rest are mostly free for academic use, but the license conditions vary. Some appear to adhere to the terms on http://opendefinition.org/

New Video Courses

In addition to the datasets, my bookmarks included 20 new video courses since the original video lecture post was published in April, 2008. These are mostly graduate and advanced undergraduate courses in Physics, Mathematics, and Computer Science. Among these are full video courses in Parallel programming, Loop Quantum Gravity, Machine Learning, Financial Markets, and other fun subjects.

The new videos have been added to the post:
“Hidden Video Courses in Math, Science, and Engineering”

Videos of Talks & Seminars

As an added bonus, here is a completely unorganized list of interesting programming, machine learning, and visualization talks which caught my eye in 2008:

Search map: interactive visualization of search query clusters

Last month, our team at Juice launched a Django web analytics app called Concentrate that ingests search queries from sources like Google Analytics or Hitwise, then enhances this raw data by discovering common query patterns, generating segmented reports, and offering visual interfaces for data exploration. Jeff Barr wrote about the technology stack we used to build the app itself a couple of weeks ago at the AWS blog. I’ll provide some more detail on that topic later this week. This post will give a basic description of Concentrate’s pattern discovery algorithm and show it in action.

The following mashup provides a visual interface for exploring search patterns used by readers of the Data Wrangling blog by combining output from concentrateme.com with the Google AJAX search API. Each bubble in the visualization below represents a search query typed into Google during the last 2 months that led to clicks on on this site (~2000 unique queries, ~3400 searches). The size of each bubble represents the number of visitors referred by that particular query, and the bubbles are colorized by the query cluster based on phrase pattern structure (’python [x]’, [x] video’, etc). The search results below the chart are highlighted in yellow if they lead to datawrangling.com pages, which allows you to see at a glance where the site ranks for each query.

Search map of queries leading to clicks on datawrangling.com

Click to open the query browser in a new window, then mouse over a query bubble and click to update the search results.

Search query referrals from Google depend on a number of factors; including what content you have, how well it ranks in Google, and how often people actually search for it. I’m not the most prolific blogger, so the topical coverage seen in the chart is somewhat sparse. Some alternate views which can offer additional insight include sizing the bubbles by engagement metrics like average time on site instead of visit count. You can download the raw data here if you want to experiment further: datawrangling_dec_jan.csv

Pattern discovery in Concentrate grew out of discussions I had with clients about current pain points in web analytics. A common theme seemed to be that they had large amounts of internal and competitive search referral data, but found managing and deriving insights from the data to be difficult using existing tools. My first instinct was to give them a summary view and trend reports by clustering queries based on topic using methods like NMF (I’ll be doing a few posts on topic classification later this month), but it turned out that the use cases they described were better served by another approach which automatically discovered common text patterns in the data and segmented queries based on phrase structure.

What I’m calling “patterns” are really regular expression templates for searches that share a similar structure. For instance, the pattern “jobs in [x]” represents searches for jobs in some location. The “[x]” is a wildcard that can stand for one or more words. These wildcards are often variants of a similar concepts like locations, brands, or celebrity names. As it turned out, a number of web analytics teams I talked to were spending a lot of time mining this kind of information manually from their search data in an effort to get a picture of their search traffic.

Clustering searches based on phrase similarity is a problem that people have looked at before in fields like question answering. Several interesting papers are referenced in my delicious clustering tag if you want to dig deeper. I think the novel part in Concentrate is that it combines a custom distance metric with an iterative algorithm that alternates between clustering queries and extracting common patterns within those clusters in a scalable fashion. Since the algorithm is part of a commercial service I can’t go into much more detail about how this all works, but hopefully you get the general idea of how this kind of pattern discovery can be useful.

The original idea for the interactive query scatter plot was inspired by a Netflix Prize data visualization at A Beautiful WWW. A similar analysis was run by Mark Reid using book borrowing data at Inductio ex Machina.

To generate the scatter plot, I tied my hands a bit and only allowed myself to use the CSV files downloaded from Concentrate as an input to the mashup (an API may be on the horizon). I made similar plots to aid in development and debugging of the clustering & pattern extraction algorithms, but this version is nice because you don’t need any extra information to generate it yourself. I computed inter-query distance for all pairs of query strings in the file using a string edit distance metric based on a combination of the queries and the phrase patterns labels discovered by Concentrate (also in the CSV).

The scatter plot layout was generated by running multidimensional scaling (MDS) on the resulting full distance matrix. The MDS approach consisted of applying the SVD function built into NumPy to the distance matrix to find the first two basis vectors, which were then used as X-Y coordinates. To produce the actual scatterplot html imagemap I used Matplotlib and smattering of Python code from the following links:

Bio and Geo Informatics: pylab matplotlib imagemap

This was just intended as a quick one-off example, but if anyone out there wants to generate the same visualization using another site’s search traffic, feel free to contact me. If you have Google Analytics on your site, you can sign up for a free Concentrate account and email me a CSV report containing your pattern clusters. If you want to find out more about how you can apply search patterns for web analytics applications, check out these posts from the Juice blog:

Conversation with Eric Siegel on Predictive Analytics World

The Predictive Analytics World Conference is taking place Feb 18-19, 2009 in San Francisco, CA and seems to have an interesting lineup of speakers (including one of the winners of this years Netflix Progress Prize). I’m going to be in the bay area during the week of Feb 15th, so I’m planning on checking out some of the talks. Data Wrangling readers can register using this code: datawranglingpaw09 and get 15% off the conference registration fee. Drop me a line if you are attending and want to meet up.

It also might be worth stopping by if you are an R user, as Mike E. Driscoll at Data Evolution mentioned:

The Bay Area R UseRs group is doing a free, co-located event on Wed evening of the conference — so if you’re interested in mingling with some PAW folks as well as some R users — you can sign up at: http://ia.meetup.com/67/calendar/9573566/

The organizers of the conference are coordinating a nice media blitz across several machine learning blogs; check out the post by Brendan O’Connor and John Langford’s interview at Machine Learning (Theory). I thought I would join in the fun by interviewing Eric about a few topics related to the conference, mostly focusing on customer modeling and machine learning in the business world.

Read on for the transcript of our email interview:

Eric Siegel, Ph.D., is the conference chair of Predictive Analytics World, coming to San Francicso Feb 18-19 - the event for predictive analytics professionals, managers and commercial practitioners. This conference delivers case studies, expertise and resources in order to strengthen the business impact delivered by predictive analytics.

Pete: Can you give readers an overview of your background?

Eric: I’ve been in data mining for 16 years and commercially applying predictive analytics with Prediction Impact since 2003. As a professor at Columbia University, I taught graduate courses in predictive modeling (referred to as “machine learning” at universities), and have continued to lead training seminars in predictive analytics as part of my consulting career.

There appear to be a few talks on the schedule related to the Netflix Prize. During the first year of the competition I found it surprising how effective ensemble approaches turned out to be, with multiple teams often pooling a number of algorithms together to improve accuracy. Are you seeing similar ensemble methods used in practice more often now?

Netflix is addressed during at least three session of PAW, including a presentation by the current Netflix leader (and winner of the 2008 Progress Prize).

I do see ensemble models as key to many successful deployments of predictive analytics, both internally (my firm, Prediction Impact) and otherwise. In fact, the Netflix leader uses a “mini-” ensemble, combining two competing methods with a meta-model, which turned out to be key to their success. The only reason team “BellKor in BigChaos” did well enough to qualify for the 2008 Progress Prize was by combining the two approaches developed by the separate teams “BigChaos” and “BellKor”, who had operated completely separately and developed different methods (in Austria and the U.S., respectively). The method to combine models is called “meta-learning” or “ensemble models”. The “meta-model” learned which of the two methods were better at which kinds of cases, and weights their outputs accordingly.

Ensembles are also covered at PAW-09 outside of the Netflix leader’s session. John Elder, who published a very interesting article (now a book chapter), “The Generalization Paradox of Ensembles”, will speak on the topic during his workshop, “The Best and the Worst of Predictive Analytics: Predictive Modeling Methods and Common Data Mining Mistakes”. Dr. Elder is also speaking on case studies during a regular conference session. And Dean Abbott’s session covers a case study of his work for the NRA employing ensemble models.

Peter Norvig gave a talk a couple of years ago, “Theorizing from Data: Avoiding the Capital Mistake”, which discussed how relatively simple statistical approaches could outperform more complex algorithms given large enough datasets. Use of the Mapreduce approach is often pointed to as a key factor enabling companies like Google and Yahoo to tackle problems like this. Lately, I’m hearing more interest from enterprise clients about using Hadoop and cloud computing to analyze large internal datasets in a similar manner. Do you think this kind of large scale parallel data mining will see increased adoption in traditional enterprises? Or will this approach be limited to a handful of large organizations?

Well, even with simple models, there can be a benefit to parallelizing the learning process. On the other hand, even with a million training cases, one reasonably modern desktop can be enough. Even if most organizations don’t need to go parallel, this is one of those “raise the floor by raising the ceiling” kind of situations - it’s important to keep this moving and push to new heights.

By the way, the advantage of simpler approaches relates to the article by Dr. Elder I mentioned above. An ensemble is by definition a more complex model, yet it is less inclined to succumb to the central risk of higher complexity: overadapting/overfitting to the data.

In the past, I worked with offline retailers on predictive modeling of price elasticity and promotional effectiveness. Back then, we were often limited to analysis of historical price and sales POS data, without the capability to conduct live A/B testing in physical store locations. Over the last few years, sites like Amazon and Google have taken advantage of live A/B testing for price and advertising optimization on the web. In your experience, is this experimental approach to decision making becoming more common in traditional enterprises or is it still limited to the web?

You know, I know of few to no public case studies of offline (non-web) businesses employing online/realtime learning. Generally, it isn’t worth the integration requirements and increased analytical challenges - companies usually just refresh the predictive model periodically with the usual offline process of learning/modeling over updated data.

Earlier this month, the O’Reilly Money:Tech Conference was postponed in light of the financial crisis. Have you seen much fallout in the predictive analytics community from the economic downturn?

It is hard to generalize. People are more risk adverse in employing a technology to which they may be new, but, at the same time, there’s more attention on improving efficiency with better decisions or more precisely targeted marketing. My keynote at PAW-09 is entitled, “Five Ways to Lower Costs with Predictive Analytics”. And I would say my consulting colleagues and I are as busy as usual.

You may think conferences are another thing, since attendance/travel are often the first costs cut. Well, I’ve got a bias, but my opinion that predictive analytics is too important to circumvent is founded: registration for PAW-09 has surpassed the goals we set last spring. I credit in large part predictive analytics’ increase in buzz and attention; it’s starting to get its due.

What problem areas appear to be most in demand by enterprise customers right now? Credit scoring, recommendation systems, predictive text mining?

Credit scoring is established - an application of predictive analytics that has crossed the chasm and achieved wide adoption. It is fairly specialized, almost a field unto itself. Product recommendations is certainly on it’s way up, as vendors rendor it more accessible to companies that aren’t an Amazon or Netflix. Augmenting predictive analytics with text mining has great potential, but I haven’t seen enough case studies to get a feel of how pervasive it’s become - at least not yet.

Human resource applications, including human capital retention, are an up-and-coming contrast to marketing applications — predict which employee will quit rather than the more standard prediction of which customer will defect.

Beyond those, I consider the following the remaining hot areas (all represented by named case studies at PAW-09, by the way):

Marketing and CRM (both offline and online)
- Response modeling
- Customer retention with churn modeling
Online marketing optimization
- Behavior-based advertising
- Email targeting
- Website content optimization
Insurance pricing

Amazon Web Services Public Datasets

Amazon announced their Hosted Public Data Sets service today, and I expect it to be a game changer. Finding and using datasets on the web just got a lot easier. Similar to how developers can share Amazon Machine Images on EC2, you can now freely share large datasets in the cloud using Amazon EBS snapshots.

A few months ago, Jeff Bar stopped by Juice to talk with our team about how we are using Amazon EC2 and SQS to scale our data mining efforts. One of the issues I brought up was the potential cost and hassle of shuffling large datasets on and off AWS. Jeff discussed his concept of using Amazon as a kind of data & application ecosystem, where various companies, researchers, and data providers interact on AWS and take advantage of the transfer efficiencies of staying within the Amazon infrastructure and using data and APIs locally.

This seems to be a part of that vision, and I’m looking forward to unleashing Hadoop on whatever data flows into the system.

From the AWS Public Data site:

Select public data sets are hosted on Amazon EC2 for free as Amazon Elastic Block Store (Amazon EBS) snapshots. Amazon EC2 customers can access this data by creating their own personal Amazon EBS volumes, using the public data set snapshots as a starting point. They can then access, modify and perform computation on these volumes directly using their Amazon EC2 instances and just pay for the compute and storage resources that they use. If available, researchers can also use pre-configured Amazon Machine Images (AMIs) with tools like Inquiry by BioTeam to perform their analysis. To get started using the Public Data Sets on AWS, simply perform these three easy steps:

1. Sign up for an Amazon EC2 account.

2. Launch an Amazon EC2 instance.

3. Create an Amazon EBS volume using the Snapshot ID listed in the catalog above for your chosen snapshot.

…If you have a public domain or non-proprietary data set that you think is useful and interesting to the AWS community, please submit a request below and the AWS team will review your submission and get back to you. Typically the data sets in the repository are between 1 GB to 1 TB in size (based on the Amazon EBS volume limit), but we can work with you to host larger data sets as well. You must have the right to make the data freely available.

Hidden Video Courses in Math, Science, and Engineering

Over the last few years, a large number of open courseware directories and video lecture aggregators have popped up on the web. These sites often include introductory courses and research seminars, but it can be difficult to find full courses covering advanced topics. For budgetary and copyright reasons, most upper level and smaller attendance courses are not recorded, or are only offered online for a fee. Many schools provide access-restricted videos of advanced courses to current students, but do not make them available to the wider community. To help remedy this, I have pulled together a big list of advanced courses with publicly available video lectures in math, physics, finance, and computer science that seem to have slipped through the cracks and included them in this post (scroll down to skip to the links).

What motivated me to pull this together? Like many people who are working full time while taking grad courses, blogging, or burning the midnight oil on a startup, I looked up after a couple of years to find I had gained a bunch of weight and was no longer in the best shape of my life. I had too much to do, and couldn’t tear myself away from coding every day for a couple of hours at the gym. In addition to my gym problem, I had just moved to DC and missed the huge number of courses available in the Boston area. It is difficult to find advanced math and physics courses that fit into a full time work schedule. Being a geek, my first instinct was to look for a technical solution to non-technical problems.

The approach I came up with was to load an Archos video player with video lectures from the web (an iphone would probably work just as well). After 3 months of watching machine learning lectures while on the elliptical machine, I had lost 30 lbs and learned a few things at the same time. The motivation problems for self-study using open courseware videos are a lot like those with working out: you really intend to do something to improve yourself, but you never seem to find the time. Somehow putting the two together and forcing myself to get things done appealed to the part of my brain which seeks extreme efficiency.

Most video players now come with wifi built in, so if you have wireless access at your gym you should be ready to go. If you need to download the videos, then depending on the copyright of the author you can use mplayer or other linux utilities to rip the stream and encode it appropriately. Check out my del.icio.us video streaming links for details.
There was a lot of buzz last week about the pace of technology causing bloggers to sacrifice health for work, but this might be a way for technology to actually help improve the situation. You can force yourself to watch some video lectures and get back in shape at the same time…

Enough motivation, on with the links:

Links to Advanced Courses with Complete Video Lectures:

See http://del.icio.us/pskomoroch/video+lectures to find updated links for complete courses…this list is mostly composed of courses I hadn’t seen in other directories, but includes links to some of the better Berkeley, Stanford, and MIT videos as well.

Update (02/10/09): I’ve bookmarked 20 new video courses since the original post was published on April 09, 2008. The new video links have been added to the sections below and are in bold type.

Physics

Loop Quantum Gravity « Cosmic Posts

Prof. Michael D. Spivak Pathway Lectures

PIRSA - Perimeter Institute Recorded Seminar Archive

MIT OpenCourseWare - 6.002 Circuits and Electronics, Spring 2007

Personal and Historical Perspectives of Hans Bethe

Harvard Physics: Quantum Field Theory by Sidney Coleman - 50 videos
University of New Mexico: Physics 524 Quantum Field Theory II -27 videos
University of New Mexico: Physics 521 Quantum Mechanics - 32 videos
UCSD Quantum Physics 130A, 130B, 130C ~ 25 videos each
University of South Carolina PHYS 729 - Applied Group Theory - 22 Videos, The Foundations of Theoretical Physics Using Lie Groups & Algebras
Florida Atlantic University: PHY 6938 General Relativity — Fall 2007 - 28 videos
Brookhaven National Laboratory Streaming Video: Cosmology for Beginners -5 videos
MIT OpenCourseWare | Physics | Video Lectures - Physics I: Classical Mechanics, 8.02 E & M, 8.03 Vibrations and Waves, 8.224 GR & Astrophysics
Oregon State University - Physics 464/564, Computational Physics - 23 videos, based on “A Survey of Computational Physics”, Landau, Paez, Bordeianu
Cambridge University Video - Thermodynamics and Phase Diagrams with Harry Bhadeshia - 7 videos
University of New Mexico: Prof. Ivan H. Deutsch, Short Course in Quantum Information 8 videos
The Vega Science Trust - Astrophysical Chemistry by Harry Kroto - 8 videos
CERN: Introduction to String Theory - W. Lerche - 4 videos
CERN: String Theory - Johnson, C. (University of Southern California) - 5 videos
CERN: String Theory for Pedestrians - Zwiebach, B. (MIT) 3 videos, author of “A First Course in String Theory”
CERN Short Courses in Particle Physics - Accelerators, Detectors, Bubble Chambers, Feynman Diagrams, etc.

Mathematics

MIT OpenCourseWare - 18.02 Multivariable Calculus, Fall 2007

National Programme on Technology Enhanced Learning(NPTel)- Chaos, Fractals & Dynamic Systems

Stanford EE364a: Optimization Lecture Videos
Stanford EE263: Linear Dynamical Systems Lecture Videos
MIT Courseware: Godel, Escher, Bach: A Mental Space Odyssey
Constraint Programming Summer School 2007
University of Colorado at Colorado Springs UCCS - Mathematics Video Courses - Requires free registration.. lots of courses
UCCS Math 432 Modern Analysis II | Spring 2008
UCCS Math 311 Number Theory | Spring 2008
UCCS Math 535 Applied Functional Analysis | Spring 2006
Texas A&M University - Math 614 Dynamical Systems and Chaos
MIT OpenCourseWare | Mathematics | Video Lectures- 18.03 Differential Equations, 18.06 Linear Algebra, 18.085 Computational Science and Engineering I, 18.086 Mathematical Methods for Engineers II
Calculus in 20 Minutes Part 1 Part 2 - funny and educational.

Computer Science & Engineering

HLRS - Organization - Parallel Computing - Parallel Programming Workshop ONLINE

ClusterMonkey - MPI-Tube: Learn MPI the Internet Way

Machine Learning

Video Lectures: Stanford Natural Language Processing - Christopher Manning

Machine Learning (Stanford CS 229) Course Videos- Andrew Ng (also on iTunesU)

Yuri Lifshits - course "Algorithms for the Internet" (3 short courses in Russian)

SUNY Buffalo - Machine Learning (CSE574)

U Alaska: CS A405 - Artificial Intelligence

Stanford Machine Learning CS229 (Fall 07) 20 lectures - thanks to Max Khesin + on iTunes, course page
UC Berkeley Machine Learning Workshop 11 lectures
CS 281A / Stat 241A: Statistical Learning Theory
U Washington Machine Learning Videos
University of Freiburg - Advanced AI Techniques - Reinforcement Learning, NLP, Bayesian Networks

Neuroscience & Biology

Finance and Econometrics

Game Theory — Open Yale Courses

Financial Markets — Open Yale Courses

U Oregon Economics Video Lectures - E421 Econometrics, E470 Monetary Theory & Policy, and more

University of Toronto ACT 460 / STA2502 - Stochastic Methods for Actuarial Science - S. Jaimungal, Department of Statistics and Mathematical Finance Program
Economics 421 - Econometrics- Mark Thoma: Department of Economics, University of Oregon
Course Video Lectures: Latent Variable Analysis Professor Bengt Muthén of the UCLA Graduate School of Education & Information Studies
INFO 747 - Social and Economic Data - Cornell Record Linkage Course Lecture Videos Prof. John M. Abowd
UC Berkeley Webcasts: Econometrics 244 - Discrete Choice Methods with Simulation

Seminars, Talks, and Conference Videos:

See http://del.icio.us/pskomoroch/talk+video for more links…

Physics

Mathematics

Computer Science & Engineering

Machine Learning

Neuroscience & Biology

Finance and Economics

Open Courseware Directories and Other Video Lecture Roundup Posts

Berkeley Course Webcasts
MIT OpenCourseWare Videos
Open Yale Courses
VideoLectures - exchange ideas & share knowledge
Free Science and Video Lectures Online!
Lecturefox: free university lectures - computer science, mathematics, physics
Business Intelligence, Data Mining & Machine Learning: Machine Learning OnLine Lectures - Machine Learning OnLine Lectures
Yet Another Machine Learning Blog » Machine learning videos [Pierre Dangauthier]
obousquet - ML Videos - Online videos of talks or lectures about Machine Learning related topics