Maximum entropy classification for record linkage
Section 6. Simulation study

• Previous
• Next

6.1   Set-up

To explore the practical feasibility of the unsupervised MEC algorithm for record linkage, we conduct a simulation study based on the data sets listed in Table 6.1, which are disseminated by ESSnet-DI (McLeod, Heasman and Forbes, 2011) and freely available online. Each record in a data set has associated synthetic key variables, which may be distorted by missing values and typos when they are created, in ways that imitate real-life errors (McLeod et al., 2011).

We consider the linkage keys forename, surname, sex, and date of birth (DOB). To model the key variables, we divide DOB into 3 key variables (Day, Month, Year). For text variables such as forename and surname, we divide them into 4 key variables by using the Soundex coding algorithm (Copas and Hilton, 1990, page 290), which reduces a name to a code consisting of the leading letter followed by three digits, e.g. Copas $\equiv$ C120, Hilton $\equiv$ H435. The twelve key variables for record linkage are presented in Table 6.2.

We set up two scenarios to generate linkage files. We use the unique identification variable (PERSON-ID) for sampling, which are available in all the three data sets. We sample $n_A=500$ and $n_B=\text{1,000}$ individuals from PRD and CIS, respectively. Let $p_A$ be the proportion of records in the smaller file (PRD) that are also selected in the larger file (CIS), by which we can vary the degree of overlap, i.e. the set of matched individuals $AB,$ between $A$ and $B.$ We use $p_A=\text{0}\text{.8},\text{0}\text{.5}$ or 0.3 under either scenario.

Scenario-I (Non-informative)

• Sample $n_0=n_B/p_A$ individuals randomly from Census.
• Sample $n_A$ randomly from these $n_0$ as the individuals of PRD, denoted by $A.$
• Sample $n_B$ randomly from these $n_0$ as the individuals of CIS, denoted by $B.$

Under this scenario both ${\delta }_a$ and ${\delta }_b$ are non-informative for the key-variable distribution. For any given $p_A,$ we have $E\left(n_M\right)=n_A{p}_A$ and $\pi =E\left(n_M\right)/n_0,$ where $n_M$ is the random number of matched individuals between the simulated files $A$ and $B.$

Scenario-II (Informative)

• Sample $n_A$ randomly from Census $\cap$ PRD $\cap$ CIS, denoted by $A$ from PRD.
• Sample $n_M=n_A{p}_A$ randomly from $A$ as the matched individuals, denoted by $AB.$
• Sample $n_B-n_M$ randomly from $\text{CIS}\backslash \text{A}$ having $\text{SEX}\text{=}F,$ $\text{YEAR}\le 1970,$ and odd MON, denoted by $B_0.$ Let $B=AB\cup B_0$ be the sampled individuals of CIS.

Under this scenario the key-variable distribution is the same in $A,$ whether or not ${\delta }_a=1,$ but it is different for the records $b\in B_0,$ or ${\delta }_b=0.$ Hence, scenario-II is informative. For any given $p_A,$ we have fixed $n_M=n_A{p}_A$ and $\pi =p_A/n_B.$

6.2   Results: Estimation

For the unsupervised MEC algorithm given in Section 4.1, one can adopt (4.2) or (5.1) for updating ${\theta }_k^{\left(t\right)}.$ Moreover, one can use (4.4) for ${\widehat{\xi }}_k$ directly, or (5.3) for updating ${\xi }_k^{\left(t\right)}$ iteratively. In particular, choosing (5.1) and (4.4) effectively incorporates the procedure of Winkler (1988) and Jaro (1989) for parameter estimation. Note that the MEC approach still differs to that of Jaro (1989), with respect to the formation of the linked set $\widehat{M}.$

Table 6.3 compares the performance of the unsupervised MEC algorithm, using different formulae for ${\theta }_k^{\left(t\right)}$ and ${\xi }_k^{\left(t\right)},$ where the size of $\widehat{M}$ is equal to the corresponding estimate ${\widehat{n}}_M.$ In addition, we include ${\widehat{\theta }}_k=n_M\left(\mathrm{1<mo>;</mo>}k\right)/n_M$ estimated directly from the matched pairs in $M,$ as if $M$ were available for supervised learning, together with (4.4) for ${\widehat{\xi }}_k.$ The true parameters and error rates are given in addition to their estimates.

As expected, the best results are obtained when the parameter ${\theta }_k$ is estimated directly from the matched pairs in $M,$ i.e., ${\widehat{\theta }}_k=n_M\left(\mathrm{1<mo>;</mo>}k\right)/n_M,$ together with (4.4) for ${\widehat{\xi }}_k,$ despite ${\widehat{\xi }}_k$ by (4.4) is not exactly unbiased. Nevertheless, the approximate estimator ${\widehat{\xi }}_k$ can be improved, since the profile-EM estimator given by (5.3) is seen to perform better across all the set-ups, where both are combined with (4.2) for ${\theta }_k^{\left(t\right)}.$ When it comes to the two formulae of ${\theta }_k^{\left(t\right)}$ by (4.2) and (5.1), and the resulting $n_M$ -estimators and the error rates FLR and MMR, we notice the followings.

• Scenario-I: When the size of the matched set $M$ is relatively large at $p_A=0.8,$ there are only small differences in terms of the average and median of the two estimators of $n_M,$ and the difference is just a couple of false links in terms of the linkage errors. Figures 6.1 shows that (4.2) results in a few larger errors of ${\widehat{n}}_M$ than (5.1) over the 200 simulations, when $p_A=0.8$ or $\pi =\mathrm{0.0008.}$ As the size of the matched set $M$ decreases, the averages and medians of the estimators of $n_M$ resulting from (4.2) and (5.3) are closer to the true values than those of the other estimators. Especially when the matched set $M$ is relatively small, where $\pi =0.0003,$ the formula (5.1) results in considerably worse estimation of $n_M$ in every respect. While this is partly due to the use of (4.4) instead of (5.3), most of the difference is down to the choice of ${\theta }_k^{\left(t\right)},$ which can be seen from intermediary comparisons to the results based on (4.2) and (4.4).
• Scenario-II: The use of (4.2) and (5.3) for the unsupervised MEC algorithm performs better than using the other formulae in terms of both estimation of $n_M$ and error rates across the three sizes of the matched set (Figure 6.2). Relatively greater improvement is achieved by using (4.2) and (5.3) for the smaller matched sets.

The results suggest that the unsupervised MEC algorithm tends to be more affected by the size of the matched set under Scenario-I than Scenario-II. Choosing (4.2) and (5.3), however, seems to yield the most robust estimation of $n_M$ and error rates against the small size of the matched set $M,$ regardless the informativeness of key-variable errors. The reason must be the fact that the numerator of ${\theta }_k^{\left(t\right)}$ is calculated in (5.1) over all the pairs in $\Omega$ instead of the MEC set $M^{\left(t\right)},$ which seems more sensitive when the imbalance between $M$ and $U$ is aggravated, while the sizes of $A$ and $B$ remain fixed.

We also include the additional results obtained for $p_A=0.2,0.15,$ and 0.1 in the supplementary material. The estimate ${\widehat{n}}_M$ (or $\widehat{\pi })$ gets worse as $p_A$ (or $\pi )$ reduces, which is consistent with the previous findings of others, for example, Enamorado, Fifield and Imai (2019) showed that a greater degree of overlap between data sets leads to better merging results in terms of the error rates as well as the accuracy of their estimates. The problem is also highlighted by Sadinle (2017). Record linkage in cases of extremely low prevalence of true matches is a problem that needs to be studied more carefully on its own.

6.3   Results: MEC set

Aiming the MEC set $\widehat{M}$ at the estimated size ${\widehat{n}}_M$ is generally not a reasonable approach to record linkage. Record linkage should be guided directly by the associated uncertainty, i.e. the error rates FLR and MMR, based on their estimates (4.5) and (4.6), as described in Section 4.2. Note that this does require the estimation of $n_M$ in addition to $r\left(\gamma \right).$

We have ${\widehat{\text{FLR}}}_{}$ $=$ ${\widehat{\text{MMR}}}_{}$  in Table 6.3, because $\left|\widehat{M}\right|={\widehat{n}}_M$ here. It can be seen that these follow the true FLR more closely than the MMR, especially when ${\widehat{n}}_M$ is estimated using the formulae (4.2) and (5.3). This is hardly surprising. Take e.g. the maximal MEC set $M_1$ that consists of the pairs whose key variables agree completely and uniquely. Provided reasonably rich key variables, as the setting here, one can expect the FLR of $M_1$ to be low, such that even a naïve estimate ${\widehat{\text{FLR}}}_{}$ $=0$  probably does not err much. Meanwhile, the true MMR has a much wider range from one application to another, because the difference between $n_M$ and $\left|M_1\right|$ is determined by the extent of key-variable errors, such that the estimate of MMR depends more critically on that of $n_M.$ The situation is similar for any MEC set beyond $M_1,$ as long as ${\widehat{g}}_{ab}$ remains very high for any $\left(a\mathrm{,}b\right)\in \widehat{M}.$

Table 6.4 shows the performance of the MEC set using the bisection procedure described in Section 4.2, across the same set-ups as in Table 6.3. We use only (4.2) for ${\theta }_k^{\left(t\right)}$ and (5.3) for ${\xi }_k^{\left(t\right)}$ to obtain the corresponding ${\widehat{n}}_M.$ We let the target FLR be $\psi =0.05$ or 0.03, where the latter is clearly lower than the true FLR of $\widehat{M}$  that is of the size ${\widehat{n}}_M$  (Table 6.3), especially when the prevalence is relatively low (at $\pi =0.0003)$  under either scenario. The resulting true (FLR, MMR) and their estimates are given in Table 6.4.

It can be seen that the MEC algorithm guided by the FLR yields the MEC set $\widehat{M},$ whose size $\left|\widehat{M}\right|$ is close to the true $n_M$ across all the set-ups. Indeed, under Scenario-I, the mean of $\left|\widehat{M}\right|$ is closer to $n_M$ than the mean (or median) of ${\widehat{n}}_M$ over all the simulations, which results directly from parameter estimation, especially when the match set is relatively small (at $\pi =0.0003)$ and the performance of ${\widehat{n}}_M$ is most sensitive. In other words, the fact that $\left|\widehat{M}\right|$ differs to the estimate ${\widehat{n}}_M$ is not necessarily a cause of concern for the MEC algorithm guided by targeting the FLR.

To estimate the MMR by (4.6), one can either use $\left|\widehat{M}\right|$ as the estimate of $n_M,$ or one can use ${\widehat{n}}_M$ from parameter estimation based on (4.2) and (5.3). In the former case, one would obtain ${\widehat{\text{MMR}}}_{}$ $=$ ${\widehat{\text{FLR}}}_{}$ . While this ${\widehat{\text{MMR}}}_{}$  is not unreasonable in absolute terms since $\left|\widehat{M}\right|$ is close to $n_M$ here, as can be seen from comparing the mean of ${\widehat{\text{FLR}}}_{}$  with that of the true MMR in Table 6.4, it has a drawback a priori, in that it decreases as the target FLR decreases, although one is likely to miss out on more true matches when more links are excluded from the MEC set $\widehat{M}.$ Using ${\widehat{n}}_M$ from parameter estimation directly makes sense in this respect, since the true $n_M$ must remain the same, regardless the target FLR. However, the estimator ${\widehat{\text{MMR}}}_{}$  could then become less reliable given relatively low prevalence $\pi ,$ where ${\widehat{n}}_M$ could be sensitive in such situations.

In short, the estimation of FLR tends to be more reliable than that of MMR, especially if the prevalence $\pi$ is relatively low in its theoretical range $0<\pi \le \min \left(n_A\mathrm{,}{n}_B\right)/n.$ The following recommendations for unsupervised record linkage seem warranted. 

• When forming the MEC set $\widehat{M}$ according to the uncertainty of linkage, it is more robust to rely on the FLR, estimated by (4.5).
• The estimate of MMR given by (4.6), derived from the parameter estimate ${\widehat{n}}_M$ based on (4.2) and (5.3) provides an additional uncertainty measure. However, one should be aware that this measure can be sensitive when the prevalence $\pi$ is relatively low.
• Between two target values of the FLR, $\psi <\psi \prime ,$ more attention can be given to the estimate of additional missing matches in $\widehat{M}\left(\psi \right)$ compared to $\widehat{M}\left(\psi \prime \right),$ given by

$${\displaystyle \sum _{\left(a\mathrm{,}b\right)\in \widehat{M}\left(\psi \prime \right)}{\widehat{g}}_{ab}}-{\displaystyle \sum _{\left(a\mathrm{,}b\right)\in \widehat{M}\left(\psi \right)}{\widehat{g}}_{ab}}={\displaystyle \sum _{\left(a\mathrm{,}b\right)\in \widehat{M}\left(\psi \prime \right)\backslash \widehat{M}\left(\psi \right)}{\widehat{g}}_{ab}}\mathrm{<mi>\; </mi>.}$$

• Previous
• Article main page
• Next