35

I've run into a number of use cases where I need to normalize company names in a database before running automated and manual matching. We've usually ended up writing a specific script with endless subtleties for each application, but I'm curious if anyone knows of more general (free) solutions, or frameworks for normalizing (or maybe even stemming) company names.

As a crude example, I'd want these 4 strings to all be matched:

ACME, Inc.
Acme, Inc
Acme Inc
ACME INCORPORATED

But also maybe some more challenging cases like:

Wal Mart
Walmart
Wal*mart
Wal-Mart Stores, Inc.

I've seen some applications use string edit distances, but I haven't had great results with that, maybe it would need to be combined with some rules for dealing with common abbreviations in various languages.

Some partial solutions I'm aware of:

OpenCorporates has a matching service/plugin for OpenRefine (formerly google-refine)

OpenCalais does some entity recognition in free text.

  • OpenRefine in combination with OpenCorporates sounds promising! Have you tried it? What are the problems with that solution? – Patrick Hoefler May 9 '13 at 10:32
  • I tried OpenRefine a few years a ago when it was part of Freebase and matching to their company entity lists. I feel like is a partial solution to the closely related problem of matching a set of company names to a set of known entities. However, at the time I tested it, it could only use string distance matching metrics, so it didn't do a good job with "inc" and "incorporated". And I'm looking for library code because I'm assuming any solution will require some tweaking for best performance on any specific use case. – skyebend May 9 '13 at 14:51
  • As Chris Taggart mentions below, the premise of your question, normalize THEN match, may not be a good one. A good reconciliation service should deal with (and probably would prefer) your original data. – Tom Morris Jul 4 '13 at 17:45
  • @TomMorris, thanks for the suggestion. In many of the use-cases which initially prompted my question, we don't have access to a known authoritative list of entities to reconcile against. – skyebend Jul 15 '13 at 17:51
20

[Note: I'm the co-founder of OpenCorporates, which along with our reconciliation service for OpenRefine, has been kindly mentioned by several of the answers, but I've tried to cover some of the general issues here, using our experience, rather than suggesting we've got all the answers]

This is a really difficult problem because in general it requires more than just string algorithms, and also because of the underlying question of what you are matching.

So first, what will you be matching the normalised strings to? If you're matching them to companies (legal entities), OpenRefine is really great for that as long as it's for jurisdictions that we have in OpenCorporates (we have about 30 of the US states, for example), or it's matching the names against entries in Wikipedia, using Freebase. I'm not sure of the matching algorithms that Freebase use, but we do all the usual things such as you've got with your ACME examples.

With the Walmart examples, it's rather more difficult. In part this is because sometimes these normalisations would lose information that is helpful in matching to entities. Take the hyphenation issue for example, and say you were searching for Wal-Mart Limited. If you search OpenCorporates on the web interface (which is pretty liberal in what it returns, and for the sake of this example, let's say we're limiting to companies in the UK, and this is what you get:

  • CREDITS INVESTMENTS LTD (United Kingdom, 16 Feb 2007- )
  • DOS-MART (UK) LIMITED (United Kingdom, 18 Feb 1999- )
  • GEORGE SOURCING SERVICES UK LIMITED (United Kingdom, 2 Jun 2000- )
  • WAL MART LIMITED (United Kingdom, 5 Jan 1999-17 Sep 2002)
  • WAL-MART LIMITED (United Kingdom, 12 Apr 2006-31 Mar 2009)
  • WAL-MART LN (UK) LIMITED (United Kingdom, 3 Feb 2000- )
  • WAL-MART STORES (UK) LIMITED (United Kingdom, 26 Apr 1999- )
  • WAL-MART STORES LIMITED (United Kingdom, 18 Mar 1994-10 Jul 2001)

Look at the fourth and fifth entries and you can see the problem. One has a hyphen, one doesn't. It's also worth looking at the first three entries, and these were returned because their previous names matched Wal-mart. There are also lots of other cases where normalisation brings false positives.

So although we do some normalisation, we also score against the non-normalised search term in our reconciliation API. We also are increasingly using other attributes of the companies, scoring current companies higher than dissolved companies (company names are often used by unrelated companies over time), unless a date is supplied in which case we return the company that was called that name at the given date.

Finally there's the question of what do you want to match? With Walmart, maybe it's 'obvious', but in general it isn't, even with something like "Tesco", the world's second biggest retailer (after Walmart), which could match several unrelated entities around the world, including the US.

That's why when we're matching a dataset using OpenRefine and OpenCorporates we do a first pass, limiting to a jurisdiction, passing dates in where we can, and then automatically reconciling to those entities which have a high score and where there's just one high scoring result returned by the API (there's some cool filtering in Google Refine to do this), and then progressively go down the scores, sometimes using the ability to do live reconciliations, to match the ones with no match, or with ambiguous results.

Because we use the service internally we're constantly finding 'edge cases' (that aren't so edgy), and improving the matching. People who've used it and the proprietary DBs reckon OC is very good. However, we can see there's massive of room for improvement. We're now doing more normalisation for non-US/UK company forms (e.g. GmbH and SA/SARL), and playing around with transliteration, and when we launch company hierarchies, there's obviously potential for assuming that by Walmart/Wal-mart you mean the company at the 'top' of the Walmart tree.

Hope this helps. Chris

12

OpenRefine has come a long way in the recent years. It has become quite flexible, there are many plugins available, and even though there's no programmatic "batch mode", the community is already talking about adding one (see the last entry at the OpenRefine FAQ).

It might be beneficial to look into OpenRefine (in combination with OpenCorporates) once more – and I'm sure the community here at Open Data SE will be happy to help with any arising questions :)

9

Sunlight Labs has the name-cleaver library, which does some of this, though it's more geared towards display than matching. It does help with capitalization, though, and stripping "Inc," "Assoc," etc., from the ends of entity names. Beyond that, like others have said, Refine is slick, especially when combined with custom reconciliation functions, of which Open Corporates has one, and Sunlight may at some point release another.

Editing to add: if you want to do fuzzy matching programmatically rather than via a UI, you can apply some of the same techniques Refine does by hand, like Levenshtein edit distance, which would allow you to group organizations whose names are similarly spelled. There are several implementations of these kinds of algorithms floating around.

Editing again for disclosure: I'm a Sunlight employee.

6

If you have (or want to create) a specific list you want to normalize against you may want to look at "Nomenklatura": http://nomenklatura.okfnlabs.org/

This allows you to upload your own authoratative list and then do matching using a Refine compatible API or via the user interface. Your list can also be expanded through the web interface.

The idea is to combine automatic and manual matching to ensure good outputs.

6

I worked on the creation of a very large (300 million) company authority file for a major publisher and have been involved in proper noun resolution for a number of years. The solution involves two parts: extraction of probable company names and then resolving those names to a standardized "canonical" name. The extraction portion depends upon the source material. Trade journals will refer to a company in one manner, often dropping Inc. or Co, while the national business press refers to the same company in a different manner, often using the standard enforced by the editor. Further, consumer generated content such as blogs et al can be expected to have misspellings and bad format. Thus, to find even the candidate names, one needs three different models. In order to resolve ambiguities, company location and product/service type should also be extracted from the content.

The resolution piece needs to begin with an authority file. One can start with the companies on the stock exchanges and then add to this private company lists from say D&B or similar. The authority file should also have address and industrial classification code so that ambiguities may be resolved. Before candidates are matched to the authority file, certain normalization needs to be done on company suffixes and prefixes, spaces and punctuation so that the differences measured by string edit distance focus primarily on the the company name. Nonetheless, ambiguities will be found and this is where product and location come into play.

2

If you have your data in RDF (or are able to export it to RDF), you can use linking engines like Silk or LIMES to merge different company names belonging to the same legal entities.

Silk, in particular, has a lot of comparison metrics and common transformations, from which token-wise string similarity metrics might be what you're looking for when handling the kinds of names you have in examples.

1

Adding to Andrew's response, I'd add that I recently read @chasedavis using shingles and Jaccard similarity to find matches within hashed buckets of possible matches. It's not too different an approach from Levenshtein, but might be somewhat more resistant to some classes of name variation.

  • 3
    Could you provide a link? – fgregg May 21 '13 at 22:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.