Statistical classification of text

I'm a programmer without statistical background, and I'm currently looking at different classification methods for a large number of different documents that I want to classify into pre-defined categories. I've been reading about kNN, SVM and NN. However, I have some trouble getting started. What resources do you recommend? I do know single variable and multi variable calculus quite well, so my math should be strong enough. I also own Bishop's book on Neural Networks, but it has proven to be a bit dense as an introduction.

-

I recommend these books - they are highly rated on Amazon too:

"Text Mining" by Weiss

"Text Mining Application Programming", by Konchady

For software, I recommend RapidMiner (with the text plugin), free and open-source.

This is my "text mining process":

* collect the documents (usually a web crawl)
o [sample if too large]
o timestamp
o strip out markup
* tokenize: break into characters, words, n-grams, or sliding windows
* stemming (aka lemmatization)
o [include synonyms]
o see porter or snowflake algorithm
o pronouns and articles are usually bad predictors
* remove stopwords
* feature vectorization
o binary (appears or doesn’t)
o word count
o relative frequency: tf-idf
o information gain, chi square
o [have a minimum value for inclusion]
* weighting
o weight words at top of document higher?


Then you can start the work of classifying them. kNN, SVM, or Naive Bayes as appropriate.

You can see my series of text mining videos here

-
This is a great answer! I'll look into your book suggestions, and the description of your process is also great. I especially like the suggestions for feature vectorizations. – Emil H Jul 19 '10 at 23:34
(If anyone would like to elaborate even further on the vectorization part, that'd be great.) – Emil H Jul 19 '10 at 23:35

Neural network may be to slow for a large number of documents (also this is now pretty much obsolete).
And you may also check Random Forest among classifiers; it is quite fast, scales nice and does not need complex tuning.

-
Random Forest seems very interesting. Thanks. :) – Emil H Jul 19 '10 at 23:32
+1 for Random Forests. Definitely a good classifier to try 1st, as they don't overfit. – Zach Mar 3 '11 at 17:23

A great introductory text covering the topics you mentioned is Introduction to Information Retrieval, which is available online in full text for free.

-
I actually scanned that at work yesterday. It's an interesting read - I wish I had more time to absorb the material in it, but I had to get what I needed and move on. – Thomas Owens Jul 22 '10 at 0:39
agreed, that is an excellent book. It pretty much explains how Google works :) – Neil McGuigan Jul 25 '10 at 18:41

Firstly I can recommend you the book Foundations of statistical natural language processing by Manning and Schütze.

The methods I would use are word-frequency distributions and ngram language models. The first works very well when you want to classify on topic and your topics are specific and expert (having keywords). Ngram modelling is the best way when you want to classify writing styles etc.

-

If you're coming from the programming side, one option is to use the Natural Language Toolkit (NLTK) for Python. There's an O'Reilly book, available freely, which might be a less dense and more practical introduction to building classifiers for documents among other things.

If you're interested in beefing up on the statistical side, Roger Levy's book in progress, Probabilistic Models in Study of Language, might not be bad to peruse. It's written for cogsci/compsci grad students starting out with statistical NLP techniques.

-

Naive Bayes is usually the starting point for text classification, here's an article from Dr. Dobbs on how to implement one. It's also often the ending point for text classification because it's so efficient and parallelizes well, SpamAssassin and POPFile use it.

-

Here is a link to a book that comes with Windows software, that is the seminal introduction to the Optimal Data Analysis (ODA) paradigm (see the review on this page): http://www.apa.org/pubs/books/4316000.aspx

"Optimal" specifically means "classify with maximum accuracy".

Here is a link to an article that discusses a popular multivariable, non-linear, exact ODA method, called hierarchically-optimal classification tree analysis: http://optimalprediction.com/files/pdf/V1A16.pdf

-