Data Mining: Text Mining, Visualization and Social Media

How Hard is the Local Search Problem?

[this post is a work in progress]

If I take a look at Google's local search results for a moderately populated road in my neighborhood I can see a considerable number of errors.

Varsity (E) is positioned in the wrong block; Bernu's (F) is in the wrong location and it is actually closed; Himalayan Kitchen (I - not shown) is long gone and has been replaced by another unlisted restaurant, etc.

Similarly, the results on Bing have problems:

Somethings of the results are an improvement over Google: Varsity (8) is in the right location. On the other hand, Hot Dish (4) is in the right location, but it closed and the location was then occupied by Himalayan Kitchen, ...

The local search problem has two key components: data curation (creating and maintaining a set of high quality statements about what the world looks like) and relevance (returning those statements in a manner that satisfies a user need. The first part of the problem is a key enabler to success, but how hard is it?

There are many problems which involve bringing together various data sources (which might be automatically or manually created) and synthesizing an improved set of statements intended to denote something about the real world. The way in which we judge the results of such a process is to take the final database, sample it, and test it against what the world looks like.

In the local search space, this might mean testing to see if the phone number in a local listing is indeed that associated with a business of the given name and at the given location.

But do we quantify this challenge? We might perform the above evaluation and find out that 98% of the phone numbers are correctly associated. Is that good? Expected? Poor?

 There are many factors at play. Some are to do with the nature of the real world entity in question:

1. The number of real world entities that we are attempting to describe (certainly if our goal was to describe a single restaurant then it would be easier than, say, 1 million).
2. The complexity of the real world entities that we are attempting to describe (for example, if we have to include just the phone number that would be easier than phone, address, website, chef, year of incorporation, etc.)
3. The legal nature of the entity (entities that are defined legally are probably easier to describe than those which are not due to stricter requirements governing their appearance and disappearance).
4. The dynamic nature of the entities (for example, businesses appear and disappear rapidly making it hard to maintain a 'fresh' database).

Others are to do with the manner in which the entity interacts with people and other real world entities. These interactions often result in data sets being generated as a by-product. The quality of these data sets is determined by their original application which may not have the same requirements as their opportunistic application in the local search space.

1. How does the entity interact with people?
2. How does the entity interact with other entities (for example, other businesses or government organizations)
3. The privacy associated with the entity (people in many countries have some legal documentation, but that documentation is not necessarily in the public domain).

Finally, there are issues relating to computation made over available explicit and implicit data sets that denote or are otherwise related to or influence by the real world entity.

1. How can we infer or derive required properties (for example, how hard is it to determine the specific geographic location of something given an address?)
2. How does variance in descriptive titles (think: business names) relate to algorithmically inferring that these titles are intended to denote the same real world entity (e.g. Fred's Diner, Fred's Cafe, Fred's Restaurant)

 Any data set we have access to can be characterized in terms of:

1. How much of the model it covers (e.g. name, phone and address but not web site)
2. How many of the entities it covers (e.g. all restaurants, all businesses, just Seattle restaurants, etc.)
3. How much noise is in the data (at the time the statements were made, how accurate were they)
4. The latency in the data (or, how much of the world has changed since these statements were made)
5. Is the information direct (statements of the exact for of the desired ultimate data set) or indirect (statements that can be used in whole or in part to derive the desired statements, in which case the accuracy of an algorithm for doing so must be determined)

Finally, across all data sets we can determine

1. Correlation or other dependencies. If we discover two sets of statements about the world but find that they are from the same source (or were originally and have since diverged) then their combined value is less than if we find independent sets of statements that can be used for mutual corroboration.

Visualizing Jane Austen Part 2

A better way to do this is to format with the columns indicating the chapters (rather than arbitrary flow based layout).

Pride and Prejudice, Collins

Emma, Churchill

Sense and Sensibility, Willoughby

Visualizing Jane Austen

A simple experiment - render a book in a summary form and highlight specific terms by changing the color of the paragraph.

Here is Jane Austen's Pride and Prejudice with the term Collins highlighted.

And here is Emma with the term Churchill highlighted.

Finally, here is Willoughby from Sense and Sensibility.

Note that this form of rendering has an artificial clustering of colours when highlighted paragraphs happen to be adjacent across columns.

Focus on GDP

I've put together an example of a focus page on d8taplex aimed at bringing together different data sets under one topic or narative. Still a work in progress.

Visualization of Google Plus Graph

I took a sample of the Google Plus graph and loaded it up in to the excellent Gephi graph rendering package. Due to the simple manner in which I crawled the data, this doesn't represent a true breadth-first crawl of the graph (rather it captures the random set of in and out links that appear on a user's profile page). However, what is interesting is that there is a clear tightly connected component that is distinguished from a more dilute area. I suspect, without any real investigation, that this is the core area of Google employees and some of their immediate connections as well as alpha users. This is complete conjecture, though.

In capturing this data, I also observed the complete in and out degree of each node. The top ten that I came across where (in order): Mark Zuckerberg, Vic Gundotra, Robert Scoble, Tom Anderson, Matt Cutts, Markus Persson, Pete Cashmore, Thomas Hawk, Evan Williams and Om Malik with links ranging from 456k to 33k.

Finally, I noticed that 48% of users haven't yet posted.

Google's Slipping Product Quality?

When I'm signed in to Google and issue a regular web search, this is what I visually see:

What's with the black background, exclamation sign, unreadable text, etc? Are things going pear-shaped as Google focuses on more products? The actual search results are great, but the experience is horrible.

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.

  

Pragmatic Philosophical Technology for Text Mining: Categories

Modeling the world is a key part of text mining. Modeling is an activity that comes after someone makes a statement like this :  'there are restaurants in the world, let's mine some web data and find out where they all are!" This is because someone else will ask "what is a restaurant?"

If we step back a little, we might think about the value of generalization in language, which is clearly linked to what we often call 'meaning'. When I say "there is a restaurant on 3rd at 5th, let's meet there" I am assuming that the things in the world that you use the word "restaurant" to describe are reasonably similar to the set that I would denote with the same term. This remarkable assumption - that we will behave in similar ways in the future in a manner determined by an act of language - is pretty much what holds the whole idea of language together.

The idea of assigning categories to things (or things to categories) can be analyzed at a number of levels.

Firstly, we might think of some natural, or objective quality of the objects in question and determine that if something has this quality, then it is in the category. This is what biologists have been doing for quite some time.

Secondly, especially in the case of various ownable things, we might consider the manner in which the owner describes it (this is a sushi bar, damn it!).

Thirdly, we might consider how people refer to the object (Japanese fast food!).

Finally, we might consider how people (or other agents) interact with the thing in a non-linguistic manner.

All of these come with various caveats. That being said, the difference between the first and all the others is the difference between objectivity and subjectivity. Someone int he UK might refer to an establishment selling a limited range of fried food for immediate consumption (but not on the premises) as a "chippie" whereas the same place in the US might be called a "fish and chip shop". These names don't necessarily change the nature of the thing in question. With the other options, we have to consider the subjective nature of the audience. This leads to a set of categories which differentiate both the space of things and the space of speakers (and even the space of contexts in which people are communicating).

The next challenge when trying to put things in buckets is specialization. We might feel that concepts like restaurant and plumber are pretty straightforward (we know what to expect when we engage with such businesses). In addition, we might have some idea of what a loung is. But what is a "Thai Restaurant and Lounge"? Is this a restaurant that is also a lounge? Or is this a restaurant that has a relationaship with another entity which is called a lounge? Is a "bar & grill" the same as a "grill & bar"? Is it a bar with a grill or is it an atomic concept in which the nature of the bar experience is altered by the intimate relationship with the grill?

The value of categories is that they help us project assumptions onto concepts about which we know almost nothing. If you tell me that your mum runs a business that is fine, but if you tell me she runs a restaurant, I will be around for some discounted food.

Ultimately, the things we can do with entities are defined by a matrix of properties. Categories are really a projection from this matrix. This is how I know how to interact with a taco truck, a kaiten sushi bar and a french restaurant the same for some things (paying for goods) and differently for others (sitting down at a table, at a bar or not at all). This matrix of fine grained facets can be used to project onto a model of convenient concepts (e.g. concept_134 for which I use the word 'restaurant' to denote, among others). There are many different terms we may use to indicate these concepts and we may do so imprecisely (it is more efficient to use a category we are all familiar even for an object that has a 2% variance in the details of some of the common facets).

World History Timeline

This visualization of world history, with time and location as the major axes, is one of the simplest but best I've seen. By rendering empires in space and time, the relationships between some of the major social and cultural forces to shape the modern world are made clear and intuitive. With every history book, or historical novel I read, I ask myself - why don't they provide this map?

Get it here. Or you can get it in the physical world from Metskers.

BuzzData - Initial Thoughts

I've been tracking BuzzData for a while (see posts on data engines). It is now open for business.

Firstly, what is BuzzData? Functionally, it supports the following features:

• creating identity: a user has a profile, etc. with all the normal social capabilities between objects in the BuzzData universe (following people, following data)
• uploading data: as per other data markets, BuzzData permits the uploading of data files
• associating objects with data: these can be visualizations (note that it doesn't provide its own visualization technology) or articles (discovered online, relating to the data set in question)
• searching for data sets: the usual keyword interaction

This set of functionality supports an ecosystem intended to snowball value on to data sets. Users follow datasets, users currate the data (e.g. I find a visualization of a data set and share it). I can comment on data sets, etc. Like any ecological system, one has to figure one of two strategies. You either have to provide value to individual users independent of the design ecosystem (this was exactly the clever part of delicious. It was useful to the user for bookmarking even without all the social effects of discovery and sharing) or you have to ensure there is not a cold start issue (in the case of BuzzData, this would mean that the site was already rich with data sets).

Independent of what the use-cases, persona or other design intentions of the site are, I'm not sure that BuzzData has yet solved the initial conditions in either of the two ways described above. It doesn't have the data coverage of other sites like timetric, ZanRan or d8taplex, yet it doesn't provide data tools such as visualization or statistical analytics or manipulation. However, perhaps this points to the intended value proposition of the site - bringing social to data. It is the user base that provides both of these (or will if things turn out right). That being the case, the data priming challenge is perhaps where the company needs to focus.

Overall, I like the design principles and implementation of the site. True, there are some beta (and alpha) level bugs (I'm having trouble loading up a small data set right now), but that is not exceptional in the highly iterative web application world.

It is going to be very interesting to see how the site grows and evolves as a consequence. Is it a commercial version of IBM's Many Eyes? A twist on DataMarket or InfoChimps? A reimplentation of Swivels (the YouTube of data)?