Working through a clustering problem

Question

Say I've got a program that monitors a news feed and as I'm monitoring it I'd like to discover when a bunch of stories come out with a particular keyword in the title. Ideally I want to know when there are an unusual number of stories clustered around one another.

I'm entirely new to statistical analysis and I'm wondering how you would approach this problem. How do you select what variables to consider? What characteristics of the problem affect your choice of an algorithm? Then, what algorithm do you choose and why?

Thanks, and if the problem needs clarification please let me know.

Answer 1

You can try Latent Semantic Analysis, which basically provides a way to represent in a reduced space your news feeds and any term (in your case, keyword appearing in the title). As it relies on Singular Value Decomposition, I suppose you may then be able to check if there exists a particular association between those two attributes. I know this is used to find documents matching a specific set of criteria, as in information retrieval, or to construct a tree reflecting terms similarity (like a dictionary) based on a large corpus (which here plays the role of the concept space).

See for a gentle introduction An Introduction to Latent Semantic Analysis, by Landauer et al.

Moreover, there is an R package that implements this technique, namely lsa.

Answer 2

The traditional solution to this problem is to use the vector representation for the news stories and then cluster the vectors. The vectors are arrays where each entry represents a word or word class. The value associated to each word will be the tf-idf weight. This value goes up the more frequent the word in the document and down the more frequent the word is in the whole collection of documents.

You may think of the titles as the documents, but sticking to just the title for news stories may be a bit risky for clustering similar stories. The problem is that by using word counts you are discarding all information on the order of the words. Longer texts compensate for that loss information by distinguishing documents by the vocabulary used (articles mentioning finance, money, ... are closer to each other than those mentioning ergodic, Poincare).

If you want to stick to titles, one idea is to think of word pairs as the words you use in the vector representation. So for the title The eagle has landed, you would think of the eagle, eagle has, has landed. as the “words.”

To discover when a cluster has become much bigger or different from the others you will need to develop a decision procedure.

Answer 3

This problem you are asking about is known as text mining!

There are a few things you need to consider. For example in your question you mentioned using keywords in titles. One may ask "why not the text in the article rather than just the title?" which brings me to the first consideration: What data do you limit yourself to?

Secondly, as the previous answer suggests, using frequencies is a great start. To take the analysis further you may start looking at what words occur frequently together! For example, the word 'happy' may occur very frequently... however if always accompanied by a 'not' your conclusions would be very different!

There is a very nice Australian piece of software I have used in the past called Leximancer. I would advise anybody interested in text mining to have a look at their site and the examples they have... from memory one of which analysed speeches by 2 U.S. presidential candidates. It makes for some very interesting reading!

Answer 4

I would start with a frequency distribution. Collect for a big corpus the word-frequencies and select smartly the words that are keywords (not misspellings, with a very low frequency, and not stop words like "and", "or")

Then when you have a number of new feeds, compare their distribution with the distribution that you build from your training data. Look to the big differences in frequencies and select so the important keywords of that moment.