How can I group strings by common themes?

Question

I am attempting to group, for example, strings about programming with other strings about programming, strings about physics with other strings about physics, etc., for a wide range of topics. Despite the glaring theoretical linguistic aspect of the problem, I am looking to actually do this using programming/software.

The rundown: Given a large number of strings, how would I go about grouping them by semantic theme?

The particular application: I have ~200k trivia questions that I would like to categorize into common groupings (cars, computers, politics, Canada, food, Barack Obama, etc.).

What I've looked into: Wikipedia has a list of natural language processing toolkits (assuming that what I'm trying to do is actually called NLP) so I have looked at a few but none seem to do anything similar to my needs.

Notes: It has been pointed out that doing this requires additional knowledge (e.g. a Porsche being a car, C++ being a programming language). I assume then that training data is needed, but if I have only the list of questions and answers, how can I generate training data? And then how do I use training data?

More notes: If the current formatting of my Q&As help (although it looks like JSON, it's basically a raw text file):

// row 1: is metadata
// row 2: is a very specific kind of "category"
// row 3: is the question
// row 4: is the answer
{
  15343
  A MUSICAL PASTICHE
  Of classical music's "three B's", he was the one born in Hamburg in 1833
  Johannes Brahms
}

But before someone points out that there already exists a category, note that there are ~200k questions and answers like this, and basically as many "categories". I am trying to group these into broader groups like the ones listed above. Also, this formatting can be changed for all the questions very easily, I do it programmatically.

And more notes: I don't actually know how many categories I'll need (at least 10-20), because I haven't read through all of the questions myself. I was partially expecting to have the finite number determined somehow during categorizing. In any case, I can always manually create a number of categories.

Answer 1

You are trying to solve two problems here.

Problem 1: Categorize questions strings in the proper category.

Problem 2: Create proper categories.

The first problem could be done by so-called supervised algorithms, many classifiers can give very good accuracy and performance. However, problem 2, creating categories out of thin air (tons of data), is much more tricky. This is an unsupervised problem, given lots of data the computer autonomically decides categories given some criteria. Ideally, these criteria and the algorithm should neatly organize your data into clusters. These could then be labeled. However, as this is a much more difficult task, I'd say that there is no acceptable drop-in solution here that will give a good result without a lot of tuning effort which would most likely require experts.

So, I'm afraid there's no magic button here just yet. What you can do however, is to help the machine out a bit. For instance, you can decide on the category set. When you have decided on categories, you can create training data. In this setup, the training data is just question and correct category pairs.

The more training data the better. However, as the task still is to something automatically, it doesn't make sense at first start doing things manually. Now why would you want to have training data? Accuracy evaluation. If you want good results, it is vital that you can perform some sort of evaluation on how good a setup is doing. And the only way do to that somewhat systematically is to manually label up some questiosn yourself. Otherwise you're in the blind.

Then, some new questions do arise. First: How much training data do I need? "It depends". Without having seen your data or categories I'm not sure i'd even take a guess; but I can take a "ballpark estimate" and say about 500 questions. Note that I could be off by an order of magnitude.

Does this really mean that you'd have to tag 500 questions by hand? Yes and no. It is possible to use intermediate results and some cleverness to "bootstrap" classifiers. It is still manual work though, and when you think on it 500 questions will not take that long to tag. Being clever here can quickly give worse results than being industrious.

When you have training data in a sufficient amount, take 75% of it and create a classifier using your favourite tool (e.g those mentioned here or whatnot). Now, let the classifier try to label the held out 25% of the data and meausre the resulting accuracry. If the result is good, then pop champagne. If not then make more training data or try another classifier.

TL;DR

To sum, here's how I would have done it.

0) Use a supervised learner.
1) Create a category set yourself. 
2) Label manually about 500 questions
3) Use 75% of those to train a classifier.
4) Check performance.
5) If good then cheers else goto 2.

Answer 2

This is a fairly standard problem in NLP, and the magic Google words you're looking for are "topic modeling". Although your strings are quite short, you may have some success with Latent Dirichlet Allocation, or a similar method. There's a nice blog post by Edwin Chen here, which lays out the general idea behind the algorithm. The details of implementation are covered in this note by Yi Wang.

If you're looking for an off-the-shelf solution, I recommend trying out the topicmodels package for R, as this provides a reasonably nice interface to both LDA and a more sophisticated Correlated Topic Model. There's also a good list of implementations maintained by David Mimno here.