Geocoding Inventor Locations

From edegan.com
Revision as of 16:17, 24 August 2009 by imported>Ed
Jump to navigation Jump to search

This page details the various matching techniques used to Geocode inventor locations in the NBER patent data. Geocoding inventor locations entails matching the inventor addresses provided in the patent data to known locations through-out the world and recording their longitude and latitude.

Script Files

The scripts and modules that operationalize these matching techniques can be downloaded as individual scripts or as a bundle with all supporting data files (MatchLocations.tar.gz). Note that the reference data should be placed in a subdirectory by default named "GNS", and source data should be placed in a subdirectory by default named "Source". Both defaults can be changed in the MatchLocations.pl script.

The bundle contains:

Reference Data

The reference data for the locations (which provides the longitude and latitudes) is taken from the (U.S.) National Geospatial-Intelligence Agency's GEOnet Names Server (GNS) which covers the world excluding the U.S. and Antartica.

This project uses ISO3166 two-character country codes to name source and reference files. Available reference data files for countries that have or are being processed include:

The perl module Match::GNS.pm loads, indexes and provides an interface to key variables from this data. The source code is the primary module documentation. The load() method takes and ISO3166 code, and the index methods and most other methods take one of two specific GNS FC codes (e.g. "P" for populated place, and "A" for administrative area).

The Source Files

Per country source files are extracted from the NBER patent data. The problem of identifying countries for some address records will be addressed later. The format of the source file(s) is as follows (XX is an ISO3166 code):

  • XX.txt - Tab delimited plain text with no (intentional) string quotation. Column(s): cty
  • XX_exceptions.txt - Tab delimited plain text with no (intentional) string quotation. Column(s): cty city adm postcode

The cty is used as a primary key in both files. The XX_exceptions.txt provides details on hand identified records, or other records where special care has been taken. This file is not strictly required by the scrips but will be processed if present.

The perl module Match::Patent.pm loads and provides an interface to this source data. The source code is the primary module documentation.

Postal Codes

Postal codes, known as ZIP codes in the U.S., vary by national jurisdiction and for historical reasons. The following postal codes formats are posted for reference, as are some simple regular expressions that should safely match most variants:

  • United Kingdom (Sourced from Wikipedia): A9 9AA, A99 9AA, A9A 9AA, AA9 9AA, AA99 9AA, AA9A 9AA. Simple Regex: ([A-Z]{1,2}[0-9]{1,2}[A-Z]{0,1}\s[0-9][A-Z]{2,2})
  • France (Sourced from Wikipedia): NNNMM or NNMMM where NN and NNN are numerics indicating the préfectures and sous-préfectures, respectively, and MMM are other numerics. However the following formats also appear frequently in the patent data: F NNNNN, F-NNNNN, F - NNNNN, F- NN NNN, FNNNNN, F-NN NNN, F-NN, FR - NNNNN, FR NNNNN, FR-NNNNN, (NNNNN), (NN), - NNNNN, -NNNNN-, -NN, NN, NN - N-NNNNN, NNNN, NN NNN, NN.NNN, NNN/N, NN., F. NNNNN, F.NNNNN, "FRNN,NNN". French postal codes most often, but not exclusively, occur at the start of the address string. If there are fewer than 5 digits, trailing zeros should be added.
    • Simple Regex: \(?F?R?\.?\s?\d?-?\s?\d{2,3}\.?\s?\/?\d{0,3}-?\)?
  • Belgium (Sourced from Wikipedia): NNNN where N is a numeric. Belgian postcodes are usually placed before the city, and the number of trailing zeros indicates the size of the city. However, the following formats also appear frequently in the patent data: NN NNNN, NNN, NNNN, NNNNN, NNNN-, NNN B-NNNN, NNN B-NNN, NN-NNNN, B-NNNN, NN - B NNNN, NN, N - B - NNNN, "NN, B. NNNN", B - NNNN, B -NNNN, B NNNN, B- NNNN, B--NNNN, B-NNNN, B-NNNN-, BNNNN, BNNNNN, BE - NNNN, BE-NNNN, BF-NNNN.
    • Simple Regex: \d{0,3},?\s?-{0,2}\s?B?[EF]?\.?\s?-{0,2}\s?\d{1,5}-?
  • Germany (Sourced from Wikipedia): Currently (post 1993) German postcal codes consist of five digits: NNMMM where NN indicates the broad area and MMM indicates the sub-area. Prior to 1993 postal codes had four digits NNNN and between 1989 and 1993, O-NNNN (for East, Ost, Germany) and W-NNNN (for West Germany) was used. However, the following formats also appear frequently in the patent data: (NNNN), (D-NNNN), -NNNN, 0-NNNN, 0 - NNNN, 0-NNN, 0NNNN, N CityName NN, NN CityName NN, NNN CityName NN, NNNN CityName NN, NNNN CityName N, NNNN CityName N/BRD, NNNN CityName N/HB, 1-DNNNN, "10,NNNN", BRD-NNNN, N, NN, NNN, NNNN, NNNNN, NN.NNNNN, NN-NNNNN, d-NNNN, NN - NNNNN, NN NNN, D-N, D-NN, D-NNN, D-NNNN, D-NNNNN, D N CityName NN, D NN, D NNNN, D NNNNN, D- NNNN, D- NNNNN, D--NNNNN, D-0-NNNN, D-0NNNN, D-N-NNNNN, D.NNNN, D.NNNNN, D.-NNNNN, D0NNNN, DNNN NN. DNN, DNNN, DNNNN, DNNNNN, DE - NNNN, DE 0NNNN, DE NNNNN, DE-0NNNNN, DE-0-NNNN, DE-NNNN, DE-NNNNN, O-NNNN, W-NNNN, W-NNNN CityName NN, W-NNNNN CityName NN, WNNNN. Where CityName is Berlin, Hamburg, Dusseldorf, Seevetal, etc., and DM, DS and DW appear instead of DE sometimes. Unfortunately this list is not exhaustive. Readers should note that there is a frequent transcription error of O (Ooh) as 0 (Zero).
    • Simple Regex (Doesn't catch everything): \(?(DE|D|1|W|)\.?-?[O0]?(BRD|1|)\s?-?\s?\d{2,5}\)?
  • Spain (Sourced from Wikipedia): Post 1976 Spanish postcodes are five digits of the format NNMMM, where NN indicates the province (01-52) or a reserved code (e.g. 80 for P.O. boxes). In the patent data Spansish postcodes are comparatively well behaved, with the following standard variants appearing: NNNNN, NNN NN, NNNN, NN NNNNN, NN- NNNNN, -NNNNN, NNNNN-, "NN, NNNNN", NNN, NN, N NNNNN-, NN-NN, NN-NN NNNNN, NNNNN-IBI, E-NNNNN, E-NNNN, E - NNNNN, E--NNNNN, ES-NNNNN.
    • Simple Regex: (E|ES|)\d{0,2},?\s?-{0,2}\s?\d{2,5}-?(IBI|)
  • Switzerland (Sourced from Wikipedia): Swiss (and Lictenstein) postcodes are heirarchical four-digit numbers of the form District+Area+Route+PONumber, where districts are numbered West to East (would you expect less from the Swiss?). In the patent data Swiss postcodes are compartvely immaculately behaved with the following formats appearing: NNNN, NNNN-, CH-NNNN, CH - NNNN, CH NNNN, CHNNN, CH- NNNN, CHNNN. Though the "H" may sometimes be lowercase.
    • Simple Regex: (CH|Ch|)\s?-?\s?\d{3,4}-?

The Match::PostalCodes.pm perl module provides a method to extract a postcode from a text string for a given ISO3166 code. The simple regular expressions listed above are not used verbatim, as more sophisticed techniques can be employed on per country basis.

The Matching Process

The matching process is carried out by MatchPatentLocations.pl, which has a standard pod based command line interface. The -co option specifies the ISO3166 country code to be matched.

Glossary of terms:

  • Units - isolated logical units from an address, such as the street number and name, the town, or the region. Postal codes are treated separately.
  • Tokens - Single words or sequences of words separated by a space (note that this is a specific usage)
  • n-grams - character sequences, such as bigrams (two letters from aa to zz), trigrams (aaa-zzz) and so forth
  • Exact Matching - Case insensitive of matching of the entire sequence of both the source and the reference strings
  • LCS - Longest Common Subsequence based matching (See below)
  • Place and administrative area - somewhere identified as a FC=P or FC=A respectively in the GNS data. Unless otherwise specified matches are performed for both place and administrative area separately and in series.

The sequence of processing is as follows (matching only the remaining unmatched locations at each stage):

  1. Load the source files, clean and parse (parsing identifies units)
  2. Load the reference file, build indices
  3. Exact match the exception units of records with exceptions
  4. Exact match the units of well-formatted records
  5. Exact match tokens (1-5 words)
  6. N-gram and LCS match
  7. Reconsile multiple matches

Exact Matching Units

The exact matching of units is performed for both the exception units and units of "well-formatted" records, that is records that have comma seperated logical units. Postcodes are extracted as a logical unit if possible first (to generate the PRS_POSTCODE field). Exact matching is case insensitive and units are trimmed of preceeding and subsequent spaces, but otherwise the match must be exact. Units are matched from the bottom to the top, in order of precedence. That is if the string is Unit1, Unit2, Unit3, Postcode; then Unit3 is matched with precedence over Units 2 and 1, and so forth. However, if multiple matches are made for a "Place" and one match is made for the "Area", then if then preference is given to a Place name that is different from the Area name. This is done as many Areas are also places, and more information from the source string is used in this way. For example if the string were Chelsea, London and both Chelsea and London were recorded in the GNS data as Places, but only London was recorded as a Area, then it would be most sensible to record Place=Chelsea, Area=London, and not Place=London, Area=London. The same 'difference preference' is also applied in the rare cases where there are multiple matches on Area but only one on Place.

Token Matching

Each source string is cleaned of upper-asci code (i.e. reduced to alphanumerics plus spaces), removed of its postcode (to generate PRS_POSTCODE) and then seperated into token arrays on space characters. Thus the string "String1 String2 String3 String4 Postcode" would become: [0]String1 [1]String2 [2]String3 [3]String4

An arbitrary upper token set length limit of 5 is used if the length of the source token array (4 in the example above) is greater than or equal to 5. Then beginning at the upper length limit and decreasing by one after each set of this lenght has been tried, and starting from the right hand-side and moving one unit to the left each time, the token sets are joined with spaces and exact matched against the reference string. This process iterates all length one token sets have been tried and records the matches in the order that they were made. Thus continuing the example above the space-joined source token sets would be, in the order that they are tried:

  1. String1 String2 String3 String4 (token set lenght=4, first and only set)
  2. String2 String3 String4 (token set lenght=3, first set)
  3. String1 String2 String3 (token set lenght=3, second set)
  4. String3 String4 (token set lenght=2, first set)
  5. String2 String3 (token set lenght=2, second set)
  6. String1 String2 (token set lenght=2, third set)
  7. String4 (token set lenght=1, first set)
  8. String3 (token set lenght=1, second set)
  9. String2 (token set lenght=1, third set)
  10. String1 (token set lenght=1, fourth set)

As with the Exact Matching, the 'difference preference' for Areas and Places is invoked.

NGram and LCS Matching

Longest Common Subsequence (LCS) is an abundantly used fuzzy matching technique. The Longest Common Subsequence page on wikipedia provides a very detailed background. However, LCS matching of two datasets is an NP-Hard problem and extremely processor intensive. To avoid long run-times, LCS matching is done on only a small sub-set of strings that have met the NGram criteria detailed below.

NGram are letter token strings. Source and reference strings are transformed to include only characters from one of the following numbered sets:

  1. ABCDEFGHIJKLMNOPQRSTUVWXYZ (i.e. uppercase Latin alphabet)
  2. 0123456789 (i.e. Standard numbers)
  3. " " (i.e. the space character)
  4. Alphanumeric (i.e. 1 and 2 above)
  5. Alphanumeric plus space (1,2,3 above)
  6. Alphabet only plus space(1 and 3 above)

Gramsets of various lengths, currently 2,3 and 4 characters, are used. Reference strings are decomposed into grams and both forward and reverse indexed for speed on large datasets. Source strings are decomposed into grams. Candidate reference strings are found by compiling a list of all reference strings that contain at least one of the source grams (this uses the reverse index). Then each of the candidate reference strings is gram-matched against the source gram to compute a number of scores. Specically gram-matching involves computing:

  • The number of grams in the source string
  • The number of grams in the reference string
  • The number of grams in the source string that appear in the reference string
  • The number of grams in the reference string that appear in the source string
  • The above two numbers as a source percentage and a reference percentage

Then an optional constraint that the first letter of the source and reference strings must match can be employed. If a source and reference pair meets a variety of criteria on the above variables (for example the source string is greater than 10 characters long, the source percentage of grams is greater then 80% and less than 110%, the reference percentage of grams is greater than 90% and less than 105%, and the two strings start with the same letter), then the LCS is computed. An LCS percentage, using the maximum of the lengths of the source and reference strings as a denominator, is also calculated.

The candidate reference string with the highest gram and LCS scores, assuming that these scores meet the decision threshold is then selected as the closest match. If no candidate reference string meets the decision threshold the source string is left unmatched. The decision thresholds are configured in the MatchLocations.pl script, and sets of Ngram/LCS matchings, using different character sets, gram lengths and decision thresholds, are performed sequentially, with the currently unmatched source strings used as input for each round.

Reconciling Multiple Matches

In a small number of cases it is possible that the source string will achieve more than one A (Area) or P (Place) match. For example suppose the string "Glouchester Street Cambridge Cambridgeshire" where considered. This could concievably produce two P matches and one A match with the token matching algorithm detailed above.

To reconsile multiple matches the following process is undertaken:

  • If there are both P and A matches and more than one of either P and/or A matches, then determine the P-A pair with the shortest distance between then using a Haversine formula distance calculation based on the GNS reported longitudes and latitudes. (Note that the Haversine formula is implemented in the Match::GNS.pm module and is the most accurate method over short distances, where other methods, like the great-circle method, suffer from compounded rounding error problems.)
  • If there are multiple P matches but no A matches, take the one that was arrived at first.
  • If there are multiple A matches but no P matches, take the one that was arrived at first.
Retrieved from "http://www.edegan.com/mediawiki/index.php?title=Geocoding_Inventor_Locations&oldid=31595"