*! version 1.3 May 2016

Title

Matchit -- Matches two columns or two datasets based on similar text patterns

Syntax

Data in two columns in the same dataset

matchit varname1 varname2
[, options]

Data in two different datasets (with indexation)

matchit idmaster txtmaster
using filename.dta , idusing(varname) txtusing(varname) [options]

similmethod(simfcn)
String matching method. Default is bigram. Other built-in simfcn are:
ngram, ngram_circ, firstgram, token, cotoken, scotoken, soundex, soundex_nara, soundex_fk, soundex_ext, token_soundex
and nysiis_fk.

score(scrfcn)
Specifies similarity score. Default is jaccard. Other built-in options are simple and minsimple.

weights(wgtfcn)
Weighting transformation. Default is noweights. Built-in options are simple, log and root.

generate(varname)
Specifies the name for the similarity score variable.
Default is similscore.

Two datasets setup:
Required

idmaster Numeric varname from current file (masterfile).
Needs not to uniquely identify observations from masterfile (although recommended).

txtmaster String varname from current file (masterfile) which will be matched to txtusing.

using filename Name (and path) of the Stata file to be matched (usingfile).

idusing(varname) Numeric varname from usingfile.
Needs not to uniquely identify observations from usingfile (although recommended).

txtusing(varname) String varname from usingfile which will be matched to txtmaster.

Advanced

wgtfile(filename)
Allows loading weights from a Stata file, instead of computing it from the current dataset
(and using dataset, in the case of two-dataset setup).
Default is not to load weights.

time
Outputs time stamps during the execution.
To be used for benchmarking purposes.

flag(step)
Controls how often matchit reports back to the output screen.
Only really useful for optimizing indexation by trying different simfcn.
Default is step = 20 (percent).

Only for two datasets syntax:

threshold(num)
Lowest similarity scores to be kept in final results.
Default is num = .5.

override
Ignores unsaved data warning.

diagnose
Reports a preliminary analysis about indexation.
To be used for optimizing indexation by cleaning original data and trying different simfcn.

stopwordsauto
Generates list of stopwords automatically.
It improves indexation speed but ignores potential matches.

swthreshold(grams-per-observation)
Only valid with stopwordsauto.
It sets the threshold of grams per observation to be included in the stopwords list.
Default is grams-per-observation = .2.

Description

matchit provides a similarity score between two different text strings
by performing many different string-based matching techniques.
It returns a new numeric variable (similscore) containing the similarity score, which ranges from 0 to 1.
A similscore of 1 implies a perfect similarity according to the string matching technique chosen
and decreases when the match is less similar.
similscore is a relative measure which can (and often do) change depending on the technique chosen.
For more information on these techniques refer to Raffo & Lhuillery (2009).

These two variables can be from the same dataset or from two different ones.
This latter option makes matchit a convenient tool to join observations
when the string variables are not necessarily exactly the same.
In other terms, it allows for the dataset currently in memory (called the master dataset)
to be matched with filename.dta (called the using dataset)
by means of a fuzzy similarity between string variables of each dataset.
In this case, matchit returns a new dataset containing five variables: two from the master dataset
(idmaster and txtmaster), two from the using dataset (idusing and txtusing)
and the already mentioned similarity score (similscore).

matchit is particularly useful in two cases:
(1) when the two columns/datasets have different patterns for the same string data (e.g. individual or firm names, addresses, etc.); and,
(2) when one of the datasets is considerably large and it was feeded by different sources,
making it not uniformly formatted (e.g. names or addresses in different orders).
Joining data in cases like these may lead to several false negatives when using merge or similar commands.

matchit is intended for overcoming this kind of problems
without engaging into extensive data cleaning or correction efforts.
Take, for instance, a case like (1) where one dataset contains first and last names in separated fields,
while the other one has just a fullname field.
The use of matchit allows to join the two datasets by simply combining the two fields of the first dataset
without caring about the order of first and last names or about missing middle names.
Similarly, a typical example of (2) is a large dataset containing addresses entered as free-text by different people.
Using matchit you can join them with a more standardized source without caring
if the zip or state codes were added systematically or not.

Please, note that matchit is case-sensitive.
It also takes into account all other symbols (as far as Stata does).
While data cleaning is not needed for using matchit,
it often implies an improvement of the similarity scores and,
in consequence, the overall quality of the matching exercise.
However, too much data cleaning might remove relevant information,
inducing a negative effect on quality due to false positives.

matchit requires freqindex to be installed when computing weights.

Options

Options for both syntaxes

similmethod(simfcn)
explicitly declares the method to parse the two string variables into Grams.
Default is bigram. Other built-in simfcn are:
ngram, ngram_circ, firstgram, token, cotoken, scotoken, soundex, soundex_nara, soundex_fk, soundex_ext, token_soundex
and nysiis_fk.

similmethod(simfcn,arg)
is the alternative syntax when simfcn requires an argument.
This is the case of ngram and ngram_circ,
which allows computing 1-gram, 2-gram, 3-gram, etc. by passing n as an argument.
For instance, sim(ngram,2) is equivalent to sim(bigram).

Check here for an example of how each built-in simfcn
treats strings.

weights(wgtfcn)
specifies an specific weighting transformation for Grams.
Default is no weights (i.e. each one weights 1).
Built-in options are simple, log and root.
Using weights is particularly recommended for large datasets where some Grams like "Inc", "Jr", "Av"
are frequently found, because if not they increase the false positive matches.

wgtfile(filename)
allows loading Grams' frequencies directly from a Stata file.
matchit applies the weighting transformation (wgtfcn)
selected at weights() after loading them.
Note that no file is loaded nor weights applied
if weights() is not explicitly stated.
If one or more grams are missing in the selected file,
a frequency equal to one is assumed for each of them.
See freqindex (distributed with matchit) to built your own frequency file.

score(scrfcn)
specifies the way to compute the similarity score.
Default is jaccard. Other built-in options are simple and minsimple.

generate(varname)
Specifies the name for the similarity score variable.
Default is similscore.
Please note that, in the case of two datasets, matchit renames variables
in the final dataset if there is any naming conflict.

flag(step)
Controls how often matchit reports back to the output screen.
It affects the percent reported for both matching of columns or datasets
Only really useful for optimizing indexation by trying different simfcn.
Default is step = 20 (percent)

time
Outputs time stamps during the execution.
To be used for benchmarking purposes.

Required Options when matching two datasets

idmaster
is a numeric varname from the current file (masterfile) identifying its observations.
matchit will stop if it is not numeric.
It does not need to uniquely identify observations, although this is recommended.
A practical reason to avoid this suggestion is the case where there are alternative spellings for observations.

txtmaster
is a string varname from the current file (masterfile) which will be matched to the string variable from the usingfile declared in txtusing().
Duplicated values are allowed, although at the cost of losing some computational efficiency.

filename.dta
is the name (and path) of the Stata file to be matched (usingfile).

idusing(varname)
declares the numeric varname from the usingfile identifying its observations.
It does not need to uniquely identify observations, although this is recommended.
A practical reason to avoid this suggestion is the case where there are alternative spellings for observations.

txtusing(varname)
declares the string varname from the usingfile which will be matched to txtmaster.
Duplicated values are allowed, although at the cost of losing some computational efficiency.

Additional options when matching two datasets

threshold(num)
sets the limit of similarity score to keep in the final results.
Final results will have a score greater or equal to num.
Default is .5.
Note that: (1) this value relates to the chosen options for similmethod, weights and
score;
(2) even if 0 is specified, returned results are based on at least one matched term (Gram).

override
makes matchit ignore unsaved data warning. This is to be used with caution as matchit destroys the current data to return the matched combination of masterfile and usingfile.

diagnose
reports a preliminary analysis about indexation.
To be used for optimizing indexation by cleaning original data and trying different simfcn.
First, it reports a list of the top 20 most frequent grams (which depend on the chosen simfcn) from both the Master and Using files.
Grams scoring a higher grams-per-observation ratio will increase the likelihood of more strings being compared,
especially if they score high in both lists.
This list provides a good starting point for identifying grams that are less informative, making them good candidates for removal.
For instance, Inc., Corporation, University, Mr., Ms., Jr., Street, or Avenue
are terms frequently found in datasets which will be of limited use for the matching procedure.
Second, it performs an overall assessment of the matching procedure about to be used, reporting:
(a) total pairs being compared (observations in master file x those in the using file);
(b) a rough estimation of the maximum reduction (in percent) which could be obtained
by the matchit indexation (based on the underlying data and the chosen simfcn); and,
(c) a list of the top 20 grams which have the greatest negative impact to the indexation performance
(max_common_space).
In order to increase the speed of matchit user should reduce the size of (a) or reduce the percent reported in (b).
The latter can be achieved by analyzing the results in (c) and removing those grams with higher scores manually or
by applying the option stopwordsauto.
It is worth noting that values from (b) are estimated and final results may differ.
Typically, they provide an upper bound, implying that final results should be lower
(although in some very particular cases it may actually get better).

stopwordsauto
generates automatically a list of stopwords based on grams from both master and using files.
The selected stopwords are ignored in the indexation procedure and similarity score calculations.
For instance, a string composed only by grams in the stopwords list will always score zero
regardless to what is compared with.
Similarly, two strings differing only in grams from the stopwords list will score one,
regardless of how many these different grams are.
As such, it could improve indexation speed at the expense of ignoring potential matches and exarcebating similarity scores.

swthreshold(grams-per-observation)
sets the threshold of grams per observation to be included in the stopwords list.
The values are the same than those reported in the grams_per_obs columns from the diagnose option.
Default is grams-per-observation = .2.
Only valid with stopwordsauto.

Examples:

Simple two-columns in one dataset syntax

. matchit mystring1 mystring2

Setting matching method

. matchit mystring1 mystring2, sim(token)

. matchit mystring1 mystring2, sim(ngram,3)

Setting score function

. matchit mystring1 mystring2, s(simple)

. matchit mystring1 mystring2, s(minsimple)

Setting weight function

. matchit mystring1 mystring2, w(log)

Simple two-datasets syntax

. matchit myidvar mytextvar using myusingfile.dta , idu(usingidvar) txtu(usingtextvar)

Diagnosing problems

. matchit myidvar mytextvar using myusingfile.dta, idu(usingidvar) txtu(usingtextvar) di

. matchit myidvar mytextvar using myusingfile.dta, idu(usingidvar) txtu(usingtextvar) di sim(token)

Applying automated stopwords list

. matchit myidvar mytextvar using myusingfile.dta, idu(usingidvar) txtu(usingtextvar) stopw

. matchit myidvar mytextvar using myusingfile.dta, idu(usingidvar) txtu(usingtextvar) stopw swt(.05)

Remarks:

Notes on the different matching algorithms

Matching algorithms can be categorized in three main families: Vectorial decomposition, Phonetic and Edit-distance algorithms.

Vectorial decomposition algorithms (such as N-Gram, Token, etc) basically compares the elements of two strings.
The N-gram algorithm decomposes the text string into elements of N characters (grams) using a moving-window
basis. As depicted as follows, a 3-gram decomposition of Smith, John and Smit, John have nine and eight 3-grams, respectively,
but they share six of them:

Smith, John : Smi mit ith th, h,_  ,_J  _Jo Joh ohn

Smit, John : Smi mit it, t,_  ,_J  _Jo Joh ohn

Similarly, a 3-gram decomposition of John Smith has eight 3-grams and shares five of them with Smith, John
(John Smith : Joh ohn hn  n S  Sm Smi mit ith). This exemplifies how
vectorial decomposition algorithms are particularly suitable when facing permutation problems in the data.

However, vectorial decomposition algorithms do not need to have a moving-window strucutre. For instance,
the token algorithm splits a text string simply by its blank spaces.
In John Smith there are only two elements (or grams): John and Smith.
These match perfectly those grams from Smith John, but only one from either Smith, John or Smit John.

Phonetic algorithms (such as Soundex, Daitch-Mokotoff Soundex, NYSIIS, Double Metaphone, Caverphone, Phonix, Onca,
Fuzzy Soundex, etc) regroup by sound proximity the substrings (phonemes) of a given string.
For instance, the soundex algorithm converts both the strings Smith, John and Smit, John into S532,
but Smith, Peter into S531.

Finally, Edit-distance algorithms (such as Levenshtein, DamerauLevenshtein, Bitap, Hamming, Boyer-Moore, etc)
are based on the simple precept that any text string can be transformed into another by applying a given number of plain operations.
Transforming Smith, John into Smit, John requires one deletion and the reciproque one insertion.
While transforming Smith, John into Smith, Peter requires nine operations (four deletions and five insertions).

As today, matchit performs Vectorial decomposition and phonetic algorithms
but does not perform edit-distance ones as they are not indexable.

Description of available algorithms

Vectorial decomposition

sim(bigram) or sim(ngram, 2): Splits text into grams of 2 moving chars. e.g. "John Smith" splits to Jo oh hn n_ _S Sm mi it th

sim(ngram, n): Splits text into grams of n moving chars. e.g if n=3 "John Smith" splits to Joh ohn hn_ n_S _Sm Smi mit ith

sim(ngram_circ, n): Splits text into grams of n moving chars circularly.
i.e. both "John Smith" and "Smith John" splits to exactly the same grams.
e.g. if n=3 both split to Joh ohn hn_ n_S _Sm Smi mit ith th_ h_J _Jo

sim(token): Splits text into tokens (see mata tokens). e.g. "John Smith" splits to John Smith

sim(firstgram, n): Keeps only the first n chars of each token.
e.g. if n=3 "John Smith" splits to Joh Smi

sim(cotoken): Splits text into pairs of colocated tokens.
Better for establishing similarity scores between long texts.
Use with stopwordsauto recommended.

sim(scotoken): Splits text into single tokens and pairs of colocated tokens.
Better for establishing similarity scores between long texts.
Use with stopwordsauto recommended.

Phonetic algorithms

sim(soundex): Recodes text using the soundex algorithm (see mata soundex).
e.g. "John Smith" recodes to J525

sim(soundex_nara): Recodes text using the soundex NARA algorithm (see mata soundex_nara).
e.g. "John Smith" recodes to J525

sim(soundex_fk): Recodes text using the soundex algorithm but keeping the full key
(i.e. more than 4 digits allowed but ignore trailing zeros).
e.g. recodes to J5253

sim(nysiis_fk): Recodes text using the NYSIIS algorithm but keeping the full key
(i.e. more than 6 digits allowed).
e.g. "John Smith" recodes to JANSNAT

Hybrids

sim(soundex_ext): Splits full soundex full key into grams of increasing size.
e.g. "John Smith" recodes and splits to J5 J52 J525 J5253

sim(token_soundex) or sim(tokenwrap, "soundex"): applies soundex algorithm to each token.
e.g. "John Smith" recodes and splits to J500 S530

sim(tokenwrap, "soundex_nara"): applies soundex NARA algorithm to each token.
e.g. "John Smith" recodes and splits to J500 S530

sim(tokenwrap, "soundex_fk"): applies soundex full key to each token.
e.g. "Johnatan Smithsonian" recodes and splits to J535 S532255

sim(tokenwrap, "soundex_ext"): applies soundex full key to each token and them into grams of increasing size.
e.g. "Johnatan Smithsonian" recodes and splits to J5 J53 J535 S5 S53 S532 S5322 S53225 S532255

sim(tokenwrap, "nysiis_fk"): applies NYSIIS full key to each token
e.g. "John Smith" recodes and splits to JAN SNAT

Each algorithm has its own merits.
For example, phonetic based algorithms are more efficient at managing similar sounds based on misspellings.
The Edit distance algorithm family manages typing or spelling errors effectively.
The N-gram algorithms work effectively on misspellings as well as large string permutations.
Several rankings of matching algorithms are already available in the literature on name matching
(See Pfeifer et al., 1996; Zobel and Dart, 1995; Phua et al., 2007).
Even though a clear hierarchy is hard to achieve for several reasons,
Phonex or 2-gram are found to be better performers than 3-gram, 4-gram, or Damerau-Levenshtein algorithms
(Pfeifer et al., 1996; Phua et al., 2007; Christen, 2006).
According to the surveyed literature, hybrid matching algorithms have even better results
(e.g. Zobel and Dart, 1995; Pfeifer et al., 1996; Hodge and Austin, 2003; Phua et al., 2007).

Notes on the different weighting options

The different algorithms can be customized to improve their performance.
For example, a weighting procedure can be added to the Edit transformations
or to the N-grams and Token vector elements in order to give more relevance to
less likely pieces of information in a text string.
In N-gram or Token algorithms, some grams - e.g. street or road - may provide less useful
information than rare ones simply because they are too common.

The typical approach is just to weight grams according to their inverse number of occurrences
in the data.
Hence, based on the frequency of each gram (f),
matchit can compute weights in the following ways:

simple = 1/f

root = 1/sqrt(f)

log = 1/log(f)

As aparent from the formulas, all these assign less importance to those more frequent grams.
The main difference is how fast they "punish" high frequencies,
where simple does it faster than root, which does it faster than log.
However, in practice, there are more differences between using or not weights
than among the three computation strategies.
Note that matchit computes the weights based on frequencies found in both string variables,
regardless if they are found in the same or in two different datasets
(i.e. the masterfile and the usingfile).

Notes on the different scoring options

Text similarity is typically computed using variations of the Jaccard index, which basically means the intersection
between the two strings over the union of them.
Taking m as the amount of grams matched and s1 and s2 as the amount of grams
in the first and second string, respectively, matchit computes three scoring variations:

jaccard = m/sqrt(s1*s2)

simple = 2*m/(s1+s2)

minsimple = m/min(s1,s2)

All these should range between 0 and 1, reflecting none to perfect similarity
(always relative to the similarity function chosen).
As apparent from the formulas, all these are exactly the same if s1 and s2 are equal.
In simple terms, the major difference among these is how they treat the dissimilar part of the longer string.
Jaccard and simple basically take a geometric and arimethic mean, respectively;
while minsimple considers only the shorter string.
If one of the two sources has unuseful information in the string
- e.g. address information embedded in the company name field -
minsimple might be preferred at the expense of increasing the false positive results.

In the case of using any weighting (or stopwords) option ,
the previous formulas still hold but m, s1 and s2 are weighted
(or ignored) instead of just counts of grams.

Some useful tips when using matchit with two the datasets:

1) While matchit replicates the most standard use of merge command
(i.e. intersection _merge == 3),
it does it less efficiently when there is no risk of false negatives.

2) After using matchit, the resulting dataset can be easily merged with
either the master or using datasets using the merge or joinby commands.

. matchit myidvar mytextvar using myusingfile.dta
, idu(usingidvar) txtu(usingtextvar)

. merge m:1 myidvar using mymasterfile.dta

. merge m:1 usingidvar using myusingfile.dta

3)It does not matter in substance which file is used as master or using file.
It just matters in the order of the columns in the resulting dataset.
The computational time is likely to differ, but these differences are not found substantive (within 5%).

4)Observations in the resulting dataset are not sorted.
This can be easily done by making use of sorting commands such as
sort or gsort after running matchit.
Often, it is useful to sort the resulting dataset from the higher similarity score
to the lower one in order to manually establish the best threshold to keep.

. matchit myidvar mytextvar using myusingfile.dta
, idu(usingidvar) txtu(usingtextvar)

. gsort -similscore

5)You can customize matchit by adding your own similarity, weighting or scoring functions
and benefit from its indexing and other features.
All these are coded in Mata as functions with relatively simple structure and naming conventions, which are described as follows:

Similarity functions just receive a string scalar, parses it into grams and return them in an associative array.
Optionally, you can have an argument passed to the custom function (like simf_ngram or simf_tokenwrap do),
which has to be passed after the string and it is used only within your function.
The naming convention is to have simf_ before the name of your function.

Weighting functions just receive a numeric scalar with the gram frequency
and return a numeric scalar transformation of it.
The naming convention is to have weight_ before the name of your function.

Scoring functions receive three numeric scalars and return a single numeric scalar transformation of them.
The three numeric scalars are passed in the following order:
First, the amount of grams matched;
second, the amount of grams from the string in the master file (or first column);
and, third, the amount of grams from the string in the using file (or second column).
The naming convention is to have score_ before the name of your function.

Author

Julio D. Raffo

References

Christen, P., 2006.
A comparison of personal name matching: techniques and practical issues.
Proceedings of the Workshop on Mining Complex Data (MCD).
IEEE International Conference on Data Mining (ICDM), Hong Kong, December.

Hodge, V.J., Austin, J., 2003.
A comparison of standard spell checking algorithms and a novel binary neural approach.
IEEE Transactions on Knowledge and Data Engineering 15 (5), 10731081.

Pfeifer, U., Poersch, T., Fuhr, N., 1996.
Retrieval effectiveness of proper name search methods.
Information Processing & Management 32 (6), 667679.

Phua, C., Lee, V., Smith-Miles, K., 2007.
The personal name problem and a recommended data mining solution.
Encyclopedia of Data Warehousing and Mining, 2nd ed. IDEA Group Publishing.

Raffo, J., & Lhuillery, S. (2009).
How to play the Names Game: Patent retrieval comparing different heuristics.
Research Policy, 38(10), 16171627. doi:10.1016/j.respol.2009.08.001

Zobel, J., Dart, P., 1995.
Finding approximate matches in large lexicons.
SoftwarePractice and Experience 25 (3), 331345.

Examples for "John Smith":

----------------------------------------------------------------
# token_ ngram_ ngram_
grams bigram token soundex soundex ngram,1 ngram,3 circ,2 circ,3
----------------------------------------------------------------
1 Jo John J525 J500 J Joh Jo Joh
2 oh Smith S530 o ohn oh ohn
3 hn h hn_ hn hn_
4 n_ n n_S n_ n_S
5 _S _ _Sm _S _Sm
6 Sm S Smi Sm Smi
7 mi m mit mi mit
8 it i ith it ith
9 th t th th_
10 h h_ h_J
11 _J _Jo
----------------------------------------------------------------
Notes: "_" = a blank space.
ngram, 2 is equivalent to bigram.