Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.
up vote 4 down vote favorite
2

I am currently looking for some Information Retrieval techniques.

I have a SQL database table containing strings. It has 1000 records, each being a random sentence I picked from random web sites. I need to get the term frequency and represent each string into a vector. I also need to cluster the records, e.g. using k-means.

Does anyone know what is the best way to do this? Are there any tools I can use? I am new to this and looking for a jump off point.

share|improve this question
1  
What is your ultimate goal for the clustering? Are you familiar with basic preprocessing and modeling in IR like TF-IDF weights and vector-space modeling? – cardinal Apr 3 '11 at 19:13
Essentially this is a standard text mining task, thus achievable in many ways; did your teacher suggest any tools? Also, 1k records is still quite a small data (ok, small enough that in this case the computational performance is not a major software selection factor), so will you need to scale up? – mbq♦ Apr 3 '11 at 20:56
Thanks for the quick response guys. My end goal is to create a spam filter for the strings. Basically I have the list of strings (as mentioned), I have manually input a number of what I consider spam strings. I want to be able to cluster the strings based on term freq and from this see that spam has clustered together. Once I get my head around the problem I will probably scale to maybe 10,000 records for my testing but that is still quite a small data set. I have not been recommended any tools so I am searching the web. – Steve Apr 4 '11 at 8:26

2 Answers

up vote 1 down vote

State of the art is to use semantic hashing by Hinton and Salakhutdinov. If you have a look into the paper, there are some really impressive 2D plots of several benchmark datasets.

It is a rather advanced algorithm, however. You train a stack of restricted boltzmann machines with contrastive divergence. In the end your representation of a document will be a bit vector. This can be used to do lookups based on the hamming distance.

Lots of machine learning knowledge goes is required to sucessfully implement this, and as far as I know there is no out of the box. If you want to do this and you have no prior knowledge in neural networks et al, it will take quite some effort.

share|improve this answer
up vote 1 down vote

From your comment you probably don't want to cluster, but rather to categorise (presumably spam vs non-spam). For this you should get familiar with a machine learning toolkit. The tf-idf business may possibly be helpful for pre-processing though.

If you are happy with Java, then Mallet and LingPipe are very straightforward to use. All such toolkits will do the term document matrix construction stuff, but will represent the very sparse data that results much more efficiently and also allow you to apply a variety of classification models. I've also had good luck with BMLR, but that will require that you construct the input data yourself, though it's not particularly tricky.

If you are keen to stay in clustering mode then most databases have a full text search module that allows you identify similar records according to tf-idf or related methods. Dealing with that similarity function directly might be more helpful for subsequent clustering. Better yet, you could just use Lucene which is available in various languages.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.