Data Mining: Text Mining, Visualization and Social Media

Factual's Crosswalk API

Factual, which is mining the web for knowledge using a variety of web mining methods, has released an API in the local space which aims to expose, for a specific local entity (e.g. a restaurant) the places on the web that it is mentioned. For example, you might find for a restaurant its homepage, its listing on Yelp, its listing on UrbanSpoon, etc.

This mapping between entities and mentions is potentially a powerful utility. Given all these mentions, if some of the data changes (e.g. via a user update on a Yelp page) then the central knowledge base information for that entity can be updated.

You can try out the system at this demo site.

There are many challenges in this enterprise. Perhaps most importantly, there is the central issue of matching records. While there are obvious scale and performance concerns (do you really want to match 10 million Yelp entities against 10 million Yelp entities?) the key problem is, when comparing two records determining not if they are identical statements but if they are statements about the same real world entity. This is a challenge because the 'truth' about that entity may change - phone numbers change, addresses change and even names change. This can be particularly troubling with high density chain brands like Starbucks.

Browsing through the data on Factual's demo site, I came across many cases where this matching was overly aggresive (what we call over matches - statements about multiple real world entities being conflated onto a single entity).

For example, this entity:

Wild Ginger Thai Cuisine

124 Washington St
Norwell, MA 02061 US
(781) 347-4687

Is linked to the following:

http://www.yelp.com/biz/wild-ginger-norwell (correct)

but also has links to

http://www.insiderpages.com/b/3715376667/siam-cuisine-hanover

Siam Cuisine

370 Columbia RdHanover, MA 02339

781-826-1115

http://www.dexknows.com/business_profiles/the_make_and_take_kitchen-l801392119/

The Make & Take Kitchen

(781) 659-2440

433 Washington St, Norwell, MA 02061

http://www.insiderpages.com/b/5952045094/maung-thai-restaurant-hingham

Maung Thai Restaurant

74 North StHingham, MA 02043

781-740-1218

http://www.dexknows.com/business_profiles/mcdonald_s-l804749993/

McDonald's

57 Washington St, Norwell, MA 02061

(781) 878-8068

Similarly, his entity:

Wild Ginger China Bistro

3694 Burbank Rd

Wooster, OH 44691 US
(330) 345-6388

is linked to 

http://local.yahoo.com/info-15692932-pizza-hut-wooster

Pizza Hut

1831 Beall Ave, Wooster, OH 44691

(330) 262-6202

The fundamental problem here is that a number of these sites, while they have a 'main' entity on their page, also mention other entities (e.g. for recommending alternatives to the user). However, these recommendations are not guaranteed to be stable (you may get different recommendations at any time). This fundamental problem illustrates why document analysis (understanding the layout of the document and consequently what the document is 'about' through the position of mentions of entities) is key if one wants to accurately mine the web for knowledge of this sort.

  

Unrest in the Middle East, Social Media, Text Mining and Trending Topics

In the early 2000s, after the collapse of WhizBang!Labs, I joined Intelliseek as part of the group of researchers who formed the ARC. In a fit of hacking and inspiration, we created a simple blog tracking site called BlogPulse. We actually launched the site without informing our bosses, which led to some interesting dialgoue.

Back in those days, blogs were thin on the ground (I remember first hearing of them from an early advocate - Fernando Pereira). Instead of crawlling RSS feeds, we simply crawled the front page of the blog and did a diff on the content to extract the new material. We then took that content and ran it through some simple but (generally) elegant keyword and phrase extraction technology to determine, on a daily cadence, the hot topics that people were spending their attention on.

The internet archive's first capture of the site is dated Apirl 8th, 2003. Keyphrase from that day were as follows:

On that date, we  crawled 31, 926 blogs, which contained  12, 954 new entries.

BlogPulse went on to innovate with what at the time was possibly the most popular time series presentation of search results (I don't believe we were the first, but we were copied, in at least one case with an exact replica of our HTML showing up on a competitors site).

Time series of topics, keywords extraction and trending, they are both still with us and going from strength to strength. Of course, the media has changed, though I find acclamations of the death of blogs to be generally exaggerated.

It is interesting to note that unrest in the middle east is still a key focal point of all media. It is ironic that as the frequency at which we live our lives, and the frequency with which we produce, consume and mine social content continues to increase, the big picture topics are constant: free speach, british troops, american troops, rubber bullets, ...

Stocks, Google Correlate and Being Careful With Data

Paul Kedrosky (whose opinion and blog I greatly enjoy) posted yesterday about the correlation between Microsoft stock prices and searches on Google for "google interview questions". These time series are correlated at r=0.6361.

To replicate his experiment you can do the following steps:

1. Visit Google Finance and get the MSFT stock data up.
2. Visit the 'historical prices" link and edit the date range so that it includes a good chunk of data (say 10 years).
3. Click the update button to update the data on the page (note that the graph won't update - some sort of bug).
4. Click on the download option on the right hand side (this is not available for all data on Google Finance, btw). 
5. Once the data is downloaded, upload it to Google Documents as a spreadsheet and delete all but the first column (dates) and the second last column (closing price). Note that you might see a server error when deleting columns, just ignore it and keep going.
6. Now download the results and open the data in a text editor and delete the first line.
7. Next, upload this data to Google Correlate.

I did this for a couple of other stocks : Google and IBM. For IBM, the correlated terms are as shown below:

While there are various views on what value of r for Pearson's statistic constitute good or strong correlations, it is clear from the above that these terms are more correlated with IBM's stock than the terms Paul showed for Microsoft's and, importantly, that they bear no intuitive reasoning - what explains the relationship between 'mi novio' (my boyfriend) and IBM?

You can see the relationship between the top correlated term and the stock below:

 

 

 

Zanran - A Search Engine for Graphs

I've been having fun with a new search engine for graphs call Zanran. Zanran crawls the web and classifies content in a number of formats including PDF, excel, html and image. Resources that it classifies as either graphical presentations of data (time series, pie charts, bar graphs, etc) or tabular data it indexes. When you search over this data set, the results are charts and tables containing data relating to your query.

The site, like any sensible engineering endeavour, is very focused in terms of scenario. There is a simple search / response interaction similar to a web search engine.

One can interact with the search results by hovering over the icon on the left (which also indicates the type of the result document, be it PDF, excel, etc.). This action brings up an overlay which includes the page or other document element containing the data.

Of all the data engines out there, including d8taplex, Infochimps, DataMarket and timetric, Zanran possibly has the most data. A search for 'temperature' brought up over a million hits.

However, as it has opted for the same interaction paradigm as a search engine, it is forced to optimize for relevance as its core competency in connecting users to data (other models might include browsing by categories, browsing by source, or even browsing by the shape of the data as done by Eiodosearch). This is where the site has some real challenges. The site also suffers from some failures. Searches for 'per' and 'for' provide a server side error of some sort (possibly due to a high hit count?).

At anyrate, I see Zanran as being somewhat aligned with the philosophy behind d8taplex in terms of data sources - the wild web, rather than being limited to open data. However, it is focused on a different user scenario (get the user to a source with the data rather than get the data to the user for interaction).

 

Data Wrangler - for Wrangling Data

Data Wrangler is a cross between a wrapper creation system and a table understanding system from Stanford Visualization Group. Take a look at the video.

Wrangler Demo Video from Stanford Visualization Group on Vimeo.

HT : Eytan

Analyzing a Week of Foursquare Data

The Wall Street Journal has created an animated presentation of a week of Foursquare checkins focused on New York. The analytic covers other regions with top checkin events, gender differences and a comparison between New York and the Bay Area.

What is Data?

Of all the concepts that are thrown about in the web/data mining space, data, information, knowledge and content seem to be the most important, but also the most overloaded and slippery. In many situations, this isn't too much of a problem, but when dealing with the creation of large scale systems that are intended to derive one (e.g. knowledge) from the other (e.g. data) it becomes vital to get some idea of where the boundaries are.

The definition in Wikipedia for data is a reasonable start, but, for me, not firm enough:

The term data means groups of information that represent the qualitative or quantitative attributes of a variable or set of variables. Data (plural of datum, which is seldom used) are typically the results of measurements and can be the basis of graphs, images, or observations of a set of variables. Data are often viewed as the lowest level of abstraction from which information and knowledge are derived. Raw data refers to a collection of numbers, characters, images or other outputs from devices that collect information to convert physical quantities into symbols, that are unprocessed.

I need a bit more.

To me data must include

• a representation: the set of symbols used to capture the data
• an intention: the reason for capturing the data
• an object concept: the thing about which it is data of
• a semantics: a set of 'rules' for interpreting the representation

If you think of a sequence of numbers representing a sample of frequencies recorded from a microphone pointed at a song bird. We might represent those frequencies as numbers. The numbers have to be represented as symbols and those symbols have to be known to map to frequencies of sound waves in a certain unit of measure. The object concept is the sound wave and the intention is to capture the song to determine (for example) the characteristics of the song.

I believe this is all important in a definition as I look at data from the perspective of archiving and discovery. If I come across a document with numbers written on it, is that data?

Of course, the interesting thing about capturing these details of data is that they can then be layered to arbitrary representations. Electrons to binary, binary to digital, digital to unicode, unicode to xml, etc.

End of Year Data: Facebook Currently Leads

Like me, John Battelle was underwhelmed by offerings from Twitter summarizing a year of tweets.

Nah. After reviewing them, it's clear that Twitter's first trends release is, well, a bit predictable. But I am sure there is really interesting data locked behind that rather obvious facade....we just can't see it. Yet.

John has similar things to say about YouTube’s offering:

Everyone's doing it! YouTube's most watched came out this morning. Again, nothing that eye opening. Wish they'd dig deeper.

Facebook, on the other hand, while not quite showing the same sort of data, is not afraid to dig deeper. The data teams post includes:

• Proportion of Minorities on Facebook in the U.S.
• Ethnic Breakdown of Facebook Users in the U.S. Named ‘LEE”
• Facebook U.S. Population by Ethnicity
• Relative Saturation of Ethnicities on Facebook in the U.S.

All of these are trended over time :-)

Clearly, the intended audiences are different, but hats off (again) to the Facebook data team.

For those of you who’d like to see trending over topics, here’s a sample from BlogPulse:

 

Who cares about the pandemic, some guy left his flies open!

In Search of the Alphram Niche

The launch of Alphram has resulted in many posts regarding its relationship to Google, and its ability to deliver whatever it is meant to deliver. Certainly, I see it as being a different beast from traditional search, and I regard the initial period of its release as a time in which users will be looking for the systems natural niche. This search will basically be the search for the intersection of expectations and execution.

In our discussions last night following the opening tutorials for ICWSM the topic of the carbon footprint of our conference came up. It occurred to me that this would be a perfect Alphram style query – what is the carbon cost of a flight from Seattle to San Jose? Better yet, compare this with the same journey by train. Given my understanding of the system and having viewed the screencast, my expectation was that this would be where the system could deliver.

Unfortunately, no such luck. I can get it to say something about the distance (seattle san jose) and about the time via plane (seattle san jose airplane), about carbon emissions in general (carbon emissions). Seattle carbon reveals that there is a town in Mexico called carbon (why would that be preferred to the chemical interpretation?).

Is this an extensibility issue (how will Alphram extend its capabilities to estimate some derived cost of a quantity – e.g. the carbon emissions of a flight of a certain duration)? Or a query interpretation problem (it can do it, but I can’t get the query right)?

Interestingly, the obvious search on Google didn’t get a good result but doing the same on Live Search produced a perfect first result.

Zoetrope: That is the Web that Was

Update: Here’s the video

Eytan et al have been working on Zoetrope for a while, but here is a new article/video that shows of how far they’ve come. Zoetrope is a combination of a browser and a web archive that allows the user to manipulate the temporal point of view of a web page (or parts of a web page).

The Internet contains vast amounts of information, much of it unorganized. But what you see online at any given moment is just a snapshot of the Web as a whole -- many pages change rapidly or disappear completely, and the old data gets lost forever.

"Your browser is really just a window into the Web as it exists today," said Eytan Adar, University of Washington computer science and engineering doctoral student. "When you search for something online, you're only getting today's results."

Now, Adar and his colleagues at UW and Adobe Systems Inc. are grabbing hold of the fleeting Web and storing historical sites that users can easily search using an intuitive application called Zoetrope.

"There are so many ways of finding and manipulating and visualizing data on what we call 'the today Web' that it's kind of amazing that there's no way to do anything similar to the ephemeral Web," said Dan Weld, a UW computer science and engineering professor who also worked on the application. One service, the Internet Archive, has been capturing old versions of Web sites for years, but the records for the stored sites are inconsistent, Weld said. More importantly, there's no easy way to search the archive.

(Note to UW – make your videos trivially embedable).