Estimating the false negatives due to blocking in record linkage
Section 2. Definitions, notations and assumptions

• Previous
• Next

Matched records: In record linkage, like in other automated classification problems, a clear distinction must be made between the nature of the entities to classify (whether two records are actually from the same entity) and the decisions made (whether the records are deemed from the same entity) according to the observations on these entities (the level of agreement between the records). However there is no consensus on the terms used to refer to these key concepts because record linkage is a multidisciplinary field, at the intersection of statistics, epidemiology and computer science. Indeed, in the first paragraph of their abstract, Fellegi and Sunter (1969) writes that “A mathematical model is developed to provide a theoretical framework for a computer-oriented solution to the problem of recognizing those records in two files which represent identical persons, objects or events (said to be matched).” Thus they refer to whether two given records belong to the same entity. In their book, Herzog, Scheuren and Winkler (2007, page 83, last paragraph) use the term “true match” for the same concept. Yet in the computer science literature, the word “matched” has an entirely different meaning. It refers to the classification decision; the best example being given by Christen (2012) in his book entitled “Data matching”. In his book, Newcombe (1988, page 105, second paragraph) also laments the lack of consensus on the meaning of the word “matched” when he writes that “This word is variously used in the literature on record linkage. In this book, however, it is given no special technical meaning and merely implies a pairing of records on the basis of some stated similarity (or dissimilarity).”

In what follows, the term “matched” is used according to the definition given by Fellegi and Sunter (1969) to refer to records from the same entity that may be a person, business, household, etc. It is also applied to a pair with the meaning that the constituent records are matched. Two records are called unmatched if they come from different entities.

Finite population and data sources: For the problem at hand consider a large finite population that comprises of $N$ individuals and a recording process such that records from different individuals are mutually independent with independent recording errors. Let $m$ denote the file size, which is assumed to be a random variable such that $m\le N$ and $m\to \infty$ when $N\to \infty$ (e.g. $m=O(N)).$ Let $V$ denote the set of possible record values in either data source, and let $v_i$ denote record $i$ from the file where $v_i\in V$ by definition. For simplicity $V$ is assumed to be finite even if it is usually very large. To further simplify, assume that the two data sources are actually free of duplicate records and that the register has no undercoverage. In other words, each record from the file corresponds to exactly one record from the same individual in the register. Each record is also assumed complete, i.e. without missing values.

Blocking strategies: When linking two large data sources, blocking is used to eliminate the vast majority of pairs with records from different individuals, while keeping all the other pairs and expanding few computing resources. Yet some pairs with records from the same individual are inevitably lost in the process. Christen (2012, Chapter 4.4) has reviewed a variety of blocking procedures including the simplest strategy, where a pair is selected if the records agree perfectly on a single key. Such a procedure is often assumed in the published literature on the analysis of linked data (Chambers and Kim, 2016; Han and Lahiri, 2018). It selects a subset of pairs based on the union of Cartesian products across disjoint post-strata that are also called blocks. In practice, a refinement of this approach is used where a pair is kept if the records agree perfectly on at least one key among many. As a result, the subset of selected pairs is no longer the union of Cartesian products across disjoint post-strata. In what follows we shall not be concerned with such details but with our ability to accurately estimate the loss resulting from the blocking procedure, when linking a file to a register or census, where both sources have few duplicate records and the register or census has little undercoverage. Perfect examples of such studies are provided by the linkage of tax records to the Canadian Census (Statistics Canada, 2017b) or by a cohort study with mortality records linked to a census (Blakely and Salmond, 2002).

In what follows, it is assumed that the decision to keep a pair only depends on its constituent records. i.e. the blocking decision is equivalent to a mathematical map from $V\times V$ into $\left\{0,1\right\}.$ This includes a large class of blocking procedures, including standard blocking procedures (Christen, 2012, Section 4.4). Yet it excludes blocking strategies that use some form of clustering such as canopy clustering (Christen, 2012, Section 4.8).

Errors: When applying blocking criteria, two kinds of errors may arise including false negatives and false positives. A false negative occurs if a matched pair is rejected by the blocking criteria. A false positive occurs if an unmatched pair is accepted by the blocking criteria. These errors are measured by the false negative rate (FNR) and the false positive rate (FPR), where the former is the proportion of matched pairs that are rejected, and the latter is the proportion of unmatched pairs that are accepted.

When designing the blocking criteria one may minimize the false positive rate while keeping the false negative rate below a threshold (e.g. 1%). Since there are usually many more unmatched pairs than matched pairs in the blocks, this roughly corresponds to minimizing the number of pairs in the blocks while keeping the proportion of lost matched pairs below the said threshold. Of course, the implementation of such a strategy requires the accurate estimation of both error rates. The false positive rate is often much easier to estimate than the false negative rate. Indeed, let $B$ denote the total number of pairs accepted by the blocking criteria. Since the false positive rate isno less than $(B-m)/m(N-1)$ and no more than $B/m(N-1),$ it is well approximated by $B/mN$ if $B>>m.$ This estimator is related to the reduction ratio that is defined as $1-B/mN$ (Christen, 2012, Chapter 7.3). Estimating the false negatives is a much harder problem. Fortunately the concept of neighbour provides valuable insights.

• Previous
• Article main page
• Next