How can I cluster short messages [Tweets] based on topic ? [Topic Based Clustering]

I am planning an application which will make clusters of short messages/tweets based on topics. The number of topics will be limited like Sports [ 开发者_JAVA技巧NBA, NFL, Cricket, Soccer ], Entertainment [ movies, music ] and so on...

I can think of two approaches to this

• Ask users to tag questions like Stackoverflow does. Users can select tags from a predefined list of tags. Then on server side I will cluster them based on tags. Pros:- Simple design. Less complexity in code. Cons:- Choices for users will be restricted. Clusters will not be dynamic. If a new event occurs, the predefined tags will miss it.
• Take the message, delete the stopwords [ predefined in a dictionary ], apply some clustering algorithm on the stemmed message to make a cluster and depending on its popularity display the cluster. The cluster will be displayed till the time it remains popular [ many messages/minute].New messages will be skimmed and assigned to corresponding clusters. Pros:- Dynamic clustering based on the popularity of the event/accident. Cons:- Increased complexity. More server resources required.

I would like to know whether there are any other approaches to this problem. Or are there any ways of improving the above mentioned methods?

Also suggest some good clustering algorithms.I think "K-Nearest Clustering" algorithm is apt for this situation.

Check out Carrot2, this tool extracts the tags from the text and clusters. You can download it from here and check the algorithms implemented (Lingo, mainly) here.

Hope this help you.

Use Bayesian classification. Train the filter with some predefined corpus, and (optionally) provide a way for users to further refine it by flagging things that were incorrectly categorized.

Here's some examples of using the Bayesian classifier in NLTK.

I am also doing a similar kind of thing. I think hashtags are a good way if you are talking specifically about twitter. You could also perform some classification but it should be enriched with some external knowledge base like Wikipedia etc. Anyways, if your solution is better, please post it here