“A” is related to “B” and “C”. How do I show that “B” and “C” might, by this context, be related as well?
Example:
Here are a few headlines about a recent Broadway play:
- David Mamet’s Glengarry Glen Ross, Starring Al Pacino, Opens on Broadway
- Al Pacino in ‘Glengarry Glen Ross’: What did the critics think?
- Al Pacino earns lackluster reviews for Broadway turn
- Theater Review: Glengarry Glen Ross Is Selling Its Stars Hard
- Glengarry Glen Ross; Hey, Who Killed the Klieg Lights?
Problem:
Running a fuzzy-string match over these records will establish some relationships, but not others, even though a human reader could pick them out from context in much larger datasets.
How do I find the relationship that suggests #3 is related to #4? Both of them can be easily connected to #1, but not to each other.
Is there a (Googlable) name for this kind of data or structure? What kind of algorithm am I looking for?
Goal:
Given 1,000 headlines, a system that automatically suggests that these 5 items are all probably about the same thing.
To be honest, it’s been so long since I’ve programmed I’m at a loss how to properly articulate this problem. (I don’t know what I don’t know, if that makes sense).
This is a personal project and I’m writing it in Python. Thanks in advance for any help, advice, and pointers!
4
It’s called cluster analysis, which is basically grouping objects into clusters with similar properties. It’s a huge topic, but that should give you a place to start.
You’re entering the world of Semantics. There are public services that will parse text and pull out the major concepts (a quick search for Semantic API turned up a few) that will parse a free form document and return the major topics encountered including people, places, things, dates, and concepts. Some of the better ones will return in a format known as [RDF]
If you want to build your own system that can do this, the field is Natural Language Processing and that is a very intriguing rabbit hole to dive down.
If at all possible, get the story along with the headline. Headlines can sometimes get “cute” and make only tangential reference to what is being discussed. This works OK with humans (because they have global context), but not so well with NLP.
As mentioned in Karl Bielefeldt’s answer, clustering is a good approach, but the Devil is in the details. You not only have to pick a clustering approach that fits your problem/user space, you also have to figure out what is being clustered.
My background is in Information Retrieval (IR) from the 80’s-90’s, and we focused on similarity searching and centroid-based clustering. Our documents were represented by weighted attribute vectors, which is basically a list of terms and their relative importance in the doc. This approach can work (although better with some collections than others), but it has problems with short-cute headlines, because they lack key vocabulary terms to tie things together. But if you use the whole document, then you get a much richer list of terms (and probably a better sense of importance), and that list of terms will probably make the connection easier to spot (i.e. compute) when you have headlines that are “cute”.
My email is in my profile if you would like to get into vector generation issues, etc.