# Using n-grams to find data that does not 'belong'

Recently I posted a question over in CS.SE dealing with methods of classifying data. Essentially the problem is that I have a collection of strings (100's of thousands). Most of these strings are the same "type"-- in my initial case they are street addresses. However, there are a few strings in this collection that don't belong (city names, zip codes, or even completely unrelated nonsense like a number e.g. '53231232'). My goal is to identify these strings that don't belong.

One suggestion on CS.SE was to use n-gram analysis. For addresses especially this seemed like it could work, considering addresses tend to follow similar patterns (start with a number, end in St/Rd etc.). Just to get me started I counted bi-gram frequencies from my collection of strings. So I ended up with something like this (first 5 rows sorted by frequency descending):

ST #          104958
STREET #      89884
RD #          83532
AVE #         82628
ROAD #        65682


There were a total of 1.5 million distinct bigrams, and about 7.6 million total. My problem now is that I want to pull each string and evaluate it against these results. For example if I take "1 Microsoft Way" I can compare the frequencies of each bigram:

# 1               7409
1 Microsoft       1
Microsoft Way     1
Way #             16363


While '1 Microsoft' and 'Microsoft Way' may only appear once, '# 1' and 'Way #' appear a relatively large number of times and thus I would hope this is classified as an address.

Similarly, if a zip code is examined: 98052

# 98052     1
98052 #     1


There's nothing to suggest this is an address and I'd hope it would be classified as 'not an address'.

My problem is how can I "combine" the frequencies I've found for individual addresses into a meaningful statistic? I've though about computing z-scores for each bi-gram in the sample address, but this still leaves me with 1 z-score per bi-gram and I don't know how I would combine these. I've though about maybe finding the average z-score but I'm pretty sure that has no statistical basis. I'm also not sure how the fact that the original corpus contains the erroneous data influences what statistical tests I can and cannot use (if it does at all).

Essentially what I want to do is have a probability that "1 Microsoft Way" is an address based on the bigrams it contains and the frequency of those bigrams in the larger corpus. So say, "1 Microsoft Way" gets a .90. At the same time, I'd hope "98052" gets a very low probability, say .01.

Can anyone suggest any statistical tests or other methodologies that will allow me to achieve this?

-
In the answer to your original question, it looks like the poster was recommending an n-gram analysis using letters as the units, not words. I suspect that's the way to go as well. –  Marius Aug 8 '12 at 2:09
@Marius, thanks I had planned to take a number of samples (uni-/bi-/tri-grams by word and character) to see which gives me the best distribution, but even if I were to go by character instead of word, the original problem still stands. –  Andrew Aug 8 '12 at 2:17
@Andrew To train a classifier you need to label examples beforehand manually. Given this and the fact that addresses as you said tend to follow predefined patterns, why not using regular expressions instead ? –  steffen Aug 8 '12 at 7:12
add comment