help with data matching

[Target]

looking for some helpful suggestions regarding a task I'm currently trying to complete at work

I have 2 sets of data that I'm trying to match.  The common fields are address details, however they are all free text and there are no common conventions in use.  To compound the issue we can also toss in random abbreviations (still no common conventions), a limited field length (some entries don't have spaces), random pieces of extraneous info, and poor data quality(HA!).  I've been bashing my head against this for a while now without success and have come to the conclusion that I'm going to have to tackle it line by line, though I'm still holding out hope that there might be a better way

the data is clearly potentially sensitive so I can't really supply much in the way of examples, but any idea's?

[wraith808]

US only?

[Target]

the data is AU (whats the 'only' part?)

[wraith808]

there are different considerations when you have a localized area for the addresses vs. international and local, so I was clarifying if the information was international or not.

[mouser]

You could think of the process in terms of two stages
1. Assign a score to every given pair of items (one from each datafile), where the score represents the likelyhood that they are matching entries (refer to same user).
2. Now for each item in dataset A you can identify its most likely (or top few) potential matches, and let a human make the final judgement.

Doesn't seem like its ever going to be possible to do this without human intervention at some point, but you could probably do a pretty good job of identifying good candidates and keeping false positives to a small number.

Now as for scoring algorithm,  i'm thinking the best approach would probably be to treat each entry as a single string, and use an existing algorithm that finds longest substrings in common.  something like that.

[Target]

so basically I'm just going to have to slog my way through it - luckily it's only small (4.5K records)

[4wd]

You could possibly make it a little quicker, depends on how localised the addresses are, by doing a RegEx match for postcode.  Put all addresses of the same postcode into separate smaller files.

[wraith808]

so basically I'm just going to have to slog my way through it - luckily it's only small (4.5K records)

RegEx could really help with this- other than the street address.  Also, remember it doesn't have to be either/or.  You can use a programmatic method to narrow it down to possible matches that you have to look at, and do that part manually.

And I think that's exactly what 4wd said above, but I'm going to post this anyway because maybe I'm wrong. 

[Target]

I can pull the postcodes easily, and likewise derive corresponding suburbs.  Trouble is their data doesn't necessarily match my data (and in many cases is just plain wrong)

which brings me back to the street address.  I'd be interested in how I might go about building some sort of regex tool, but given the variables I'm not sure how I would even go about it

[wraith808]

I can pull the postcodes easily, and likewise derive corresponding suburbs.  Trouble is their data doesn't necessarily match my data (and in many cases is just plain wrong)

which brings me back to the street address.  I'd be interested in how I might go about building some sort of regex tool, but given the variables I'm not sure how I would even go about it

Well, I don't know much about AU street addresses.  Which is one of the reasons I quieted down once you clarified.  Can you expound?

Until then, some general resources:

As you said this was for a company, there are several services if you have a budget for this that would probably cost less than paying you to reinvent the wheel.

A good example: https://smartystreets.com/features

I use RegExBuddy to help me build.  There's also a good library: http://www.regxlib.com/DisplayPatterns.aspx?cattabindex=6&categoryId=7&AspxAutoDetectCookieSupport=1

A good start (but this is US Based)

Code: (text)

\d{1,5}\s\w.\s(\b\w*\b\s){1,2}\w*\.

(need to get mouser to add regex to the code highlighting)

This bit of RegEx allows 1-5 digits for the house number, a space, a character followed by a period (for N. or S.), 1-2 words for the street name, finished with an abbreviation (like st. or rd.).  This by no means solves your problem... it's just meant as a start.

You can also use text matching to brute force the text matches... and use the DICE coefficient to set a threshold for human intervention.  For more on that, visit: https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Dice%27s_coefficient. ; There are implementation examples in several languages.

A better and more practical explanation: http://www.tsjensen.com/blog/post/2011/05/27/Four+Functions+For+Finding+Fuzzy+String+Matches+In+C+Extensions.aspx

[4wd]

And I think that's exactly what 4wd said above, but I'm going to post this anyway because maybe I'm wrong. 

Not wrong 

I think some pseudo-examples would help with us working out possible RegEx.

[Target]

this should be reasonably safe (what could possibly go wrong?)

the attached lists a bunch of entries that I've already matched - it's by no means complete, but it's a start

note that it's actually in CSV format so you can just change the xtn

[4wd]

See what you mean, the postcode is about the only thing that matches reasonably consistently and even that fails in two of the examples you've got.

[Target]

gotta love the value we place on data integrity

[Stoic Joker]

If it's something you'll need to do frequently, or just multiple times...automate.

If it's something you need to do once, it's probably safer and easier to just suffer through it.

When we switch business applications a few years ago, it was my lot in life to sort out the mess that was our data for export/import. We had a list of 5,000 clients that was in in much the same state as you describe. Some people used address field 1, some people used address field 2, some people abbreviated, some did not ... It was a complete GD train wreck.

But in retrospect, it wasn't that hard to sort out in Excel once I started playing with the sort order and using replace X in column only. Because if you sort by the column you're working on all of the errors of a given type tend to get grouped by the sorting process, so they're easier to address it one shot.

Just a thought.