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?
