Appropriate algorithm for string (not document) classification?

Question

I am trying to classify a large-ish number of small strings (millions) into about 10 disjunct categories. Examples of classes and strings for each class include:

email: "foo@bar.com"
phone: "55", "22334455"
personName: "John", "Q.", "Public"
organizationName: "Reuters", "IBM"
date: "Dec.", "22.10.2010"
nameAndEmail: "Larsonlarson@gmail.com" (a last name has been concatenated with an email address.)
phoneAndEmail: "55larson@gmail.com" (part of a phone number has been concatenated with an emal address)
separator: ",", "and", "or"
other: stuff that does not fit in other categories.

Carrying out classification via a set of heuristics seems tedious, so I have been experimenting with an SVM. I'm not able to get more than about 80% accuracy without doing a lot of work manually encoding features like "has an ampersand", "is uppercase", "is mostly numeric", "has a colon in the middle", etc., which sort of defeats the purpose.

I'm wondering whether part of the challenge with using an SVM is that the "salient features" of a given string, like the '@' character, are not in a fixed position in the string, so it will not get the same feature index for each string.

Does anyone have suggestions for a more appropriate approach to this task, or can anyone recommend further reading?

Answer 1

You might find it useful to treat n-grams of characters as your feature space. Then you could represent a string as a bag of substrings. With N = 4 or greater, you would capture things like ".com" in emails, "##.#" in dates, etc.

It might also help to encode all single digits as one reserved number-only-character.

An easy way to to this might be to create all the n-gram substrings for each string in your dataset, then simply treat that list of words as a document. Then you could use term frequency or tf-idf vectors in your supervised step.

For example to create the substring uni-, bi-, and tri-grams for "whatever@gmail.com":

a = "whatever@gmail.com" 
b = set([a[x:x+y] for y in range(0,4) for x in range(0,len(a))]) 

set(['', 'co', 've', 'ai', 'eve', 'r@', 'at', '.co', 'gm', 'ev', 'tev', 'er', '@gm', 'ver', '@g', 'r@g', 'ail', 'il.', 'gma', '.', 'te', 'hat', '@', 'wha', 'om', 'wh', 'er@', 'mai', 'ma', 'ha', 'l.c', 'a', 'c', 'ate', 'e', 'g', 'i', 'h', '.c', 'm', 'l', 'o', 'l.', 'r', 't', 'w', 'v', 'com', 'il'])

Answer 2

One can copy the 'bag of words' model for documents, though it becomes a 'bag of characters' model. (jamesmf extends this to n-grams, which will be more useful.)

But if you want a feature to be salient to the algorithm, you need to give the algorithm access to that feature. You don't need to tell it what classes that feature is relevant for--just whether or not the feature is present. For example, the length of the string, number of digits in the string, and number of capital letters in the string are probably very useful for differentiating several of the classes you described, but will not be part of the feature vector unless you put them there. But all you need to do is identify them, assign them numbers, and then let the SVM take care of deciding how relevant they are.

Similarly, having a binary variable for whether or not the last four characters are .com (or whether .com appears in the string if it's not always at the end) in the feature vector will convey the same amount of helpful information without also giving the algorithm a bunch of worthless information--there may be other 4-grams that are important, but it seems unlikely to me that it's worth the cost of considering all 4-grams and 3-grams in order to get the known features of .com, .net, .org, and so on.

Answer 3

For a first pass why not use regex?
There are examples of regex for email
You could use regex for email with a digit before @
(and you cannot conclude 55 is a phone number)
From there you would just need to decide if it has a name
And you could use regex to extract the component before the @

Regex for date

Regex for phone number

I use regex to extract date and email from documents
It is fast and as accurate as the regex
Every regex is accurate it just may not pick up some edge cases
You expand the regex or pick those up via the algorithm

If you also want to also classify invalid email at least you have valid email to compare to