Better text documents clustering than tf/idf and cosine similarity?

18
votes

I'm trying to cluster the Twitter stream. I want to put each tweet to a cluster that talk about the same topic. I tried to cluster the stream using an online clustering algorithm with tf/idf and cosine similarity but I found that the results are quite bad.

The main disadvantages of using tf/idf is that it clusters documents that are keyword similar so it's only good to identify near identical documents. For example consider the following sentences:

1- The website Stackoverflow is a nice place. 2- Stackoverflow is a website.

The prevoiuse two sentences will likely by clustered together with a reasonable threshold value since they share a lot of keywords. But now consider the following two sentences:

1- The website Stackoverflow is a nice place. 2- I visit Stackoverflow regularly.

Now by using tf/idf the clustering algorithm will fail miserably because they only share one keyword even tho they both talk about the same topic.

My question: is there better techniques to cluster documents?

3
machine-learningdata-miningcluster-analysistext-mining
@ThomasJungblut well, TF-IDF is supposed to be a weighting scheme that puts more weight on relevant keywords already. If figure the problem is that tweets are just so tiny text fragments, you can't expect similarity to work very well on them beyond "near identity". Most tweets aren't even complete sentences, so NLP will likely also fail. – Has QUIT--Anony-Mousse
One thing to watch with LSI / LDA / NMF etc. is topic drift. Training a model on a known dataset will yield good results if your pipeline isn't done correctly. If you then apply your model to a totally unseen dataset you may see significant drop in performance due to fitting the original training data. Because Twitter text is so short the representation will need a bit of fiddling with as there may not be enough text to train a model properly. – Steve
@steve are there any solutions to this? – Jack Twain
@guckogucko does the user it comes from have any impact? – Steve
@steve what do you mean? – Jack Twain

3 Answers

10
votes

In my experience, cosine similarity on latent semantic analysis (LSA/LSI) vectors works a lot better than raw tf-idf for text clustering, though I admit I haven't tried it on Twitter data. In particular, it tends to take care of the sparsity problem that you're encountering, where the documents just don't contain enough common terms.

Topic models such as LDA might work even better.

7
votes

As mentioned in other comments and answers. Using LDA can give good tweet->topic weights.

If these weights are insufficient clustering for your needs you could look at clustering these topic distributions using a clustering algorithm.

While it is training set dependent LDA could easily bundle tweets with stackoverflow, stack-overflow and stack overflow into the same topic. However "my stack of boxes is about to overflow" might instead go into another topic about boxes.

Another example: A tweet with the word Apple could go into a number of different topics (the company, the fruit, New York and others). LDA would look at the other words in the tweet to determine the applicable topics.

  1. "Steve Jobs was the CEO at Apple" is clearly about the company
  2. "I'm eating the most delicious apple" is clearly about the fruit
  3. "I'm going to the big apple when I travel to the USA" is most likely about visiting New York
2
votes

Long answer:

TfxIdf is currently one of the most famous search method. What you need are some preprocessing from Natural Langage Processing (NLP). There is a lot of resources that can help you for english (for example the lib 'nltk' in python).

You must use the NLP analysis both on your querys (questions) and on yours documents before indexing.

The point is : while tfxidf (or tfxidf^2 like in lucene) is good, you should use it on annotated resource with meta-linguistics information. That can be hard and require extensive knowledge about your core search engine, grammar analysis (syntax) and the domain of document.

Short answer : The better technique is to use TFxIDF with light grammar NLP annotations, and both re-write query and indexing.