# How to perform Cleaning of a very large set of addresses

I have a dataset where I have a large number of addresses. The problem lies in the fact that many addresses although they are same but haven't been noted down in the same manner. So I want to find these addresses which are similar and clean my data from the duplicate data.

Is there any standard approach or algorithms that can help me? How should I go about this problem?

I guess you are in a situation that different fields of an address are mixed together. Try break the address text into Shingles and then try Locality-sensitive Hashing

Prof. Jeff Ullman's Text Book may help you put together all the techniques you need, starts with Section 3.2

1. Eliminate exact duplicates
2. Do fuzzy matching of addresses to get a score of near match.
3. Retain only one of the matched address and discard the rest
• I'm not sure if you've tried this but "fuzzy" matching can be very difficult with addresses and is certainly not as simple as you mention. For instance, "321 NW First ST" has a lot of very poor matches that are only and edit distance of 1 away: 320, 322, 323, 324, 325, 326, 327, 328, 329, 121, 221, 421, 521, 621, 721, 821, 921, 021, 301, 311, 331, 341, 351, 361, 371, 381, 391. Also N, NE, SW, W are all within an edit distance and 1 of the pre-direction NW. Also first-->1st is far in edit distance but is semantically similar as are abbreviations of suffixes, etc Jun 29 '16 at 22:57

You can apply clustering algorithms such as KNN or Spherical KMeans. You might need to vectorize the text in addresses before applying the algorithms.

• Breakdown by zipcode or city
• Create feature vectors of remaining address section (except zipcode/city/State)
• Apply clustering algorithm

I am not quite sure how important the address field is, but I would even try regular expressions here.