I am building a text categorizer for short sentences. In addition to telling the user "the category of the text you entered is C", I want to be able to explain why I made this decision, in a short and understandable way. For example, I don't want to tell the user "I put your sentence into a complex 3-layered neural network and that's the answer that scored the best"; I want explanations such as "Your sentence contains the words U, V and W, that are characteristic of this category, because of sentences such as X, Y and Z that appeared in the training data".

My question is: what classification algorithms are best suited for such application?

k-nearest-neighbours seems like a good candidate, because I can tell the user "Your sentence has category C because it is similar to sentences X, Y and Z that have the same category. But its performance on text categorization problems is known to be poor. I am looking for a classifie that balances performance with explanation ability.

EDIT: After spending a lot of time looking for such a classifier, I started to build a machine-learning library called limdu, that allows the classifiers to explain their decisions. It is still under development, but, it has already helped me explain to myself and my colleagues why our classifiers fail so often...