Record linkage
≈ 11 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Record linkage (also known as data matching, data linkage, entity resolution, and many other terms) is the task of finding records in a data set that refer to the same entity across different data sources (e.g., data files, books, websites, and databases). Record linkage is necessary when joining different data sets based on entities that may or may not share a common identifier (e.g., database key, URI, National identification number), which may be due to differences in record shape, storage location, or curator style or preference. A data set that has undergone RL-oriented reconciliation may be referred to as being cross-linked.
Record linkage (also known as data matching, data linkage, entity resolution, and many other terms) is the task of finding records in a data set that refer to the same entity across different data sources (e.g., data files, books, websites, and databases). Record linkage is necessary when joining different data sets based on entities that may or may not share a common identifier (e.g., database key, URI, National identification number), which may be due to differences in record shape, storage location, or curator style or preference. A data set that has undergone RL-oriented reconciliation may be referred to as being cross-linked.
Entity resolution
Entity resolution is an operational intelligence process, typically powered by an entity resolution engine or middleware, whereby organizations can connect disparate data sources with a view to understand possible entity matches and non-obvious relationships across multiple data silos. It analyzes all of the information relating to individuals and/or entities from multiple sources of data, and then applies likelihood and probability scoring to determine which identities are a match and what, if any, non-obvious relationships exist between those identities. Entity resolution engines are typically used to uncover risk, fraud, and conflicts of interest, but are also useful tools for use within customer data integration (CDI) and master data management (MDM) requirements. Typical uses for entity resolution engines include terrorist screening, insurance fraud detection, USA Patriot Act compliance, organized retail crime ring detection and applicant screening. For example, across different data silos – employee records, vendor data, watch lists, etc. – an organization may have several variations of an entity named ABC, which may or may not be the same individual. These entries may, in fact, appear as ABC1, ABC2, or ABC3 within those data sources. By comparing similarities between underlying attributes such as address, date of birth, or social security number, the user can eliminate some possible matches and confirm others as very likely matches. Entity resolution engines then apply rules, based on common sense logic, to identify hidden relationships across the data. In the example above, perhaps ABC1 and ABC2 are not the same individual, but rather two distinct people who share common attributes such as address or phone number.
Data matching
While entity resolution solutions include data matching technology, many data matching offerings do not fit the definition of entity resolution. Here are four factors that distinguish entity resolution from data matching, according to John Talburt, director of the UALR Center for Advanced Research in Entity Resolution and Information Quality: Works with both structured and unstructured records, and it entails the process of extracting references when the sources are unstructured or semi-structured Uses elaborate business rules and concept models to deal with missing, conflicting, and corrupted information Utilizes non-matching, asserted linking (associate) information in addition to direct matching Uncovers non-obvious relationships and association networks (i.e. who's associated with whom) In contrast to data quality products, more powerful identity resolution engines also include a rules engine and workflow process, which apply business intelligence to the resolved identities and their relationships. These advanced technologies make automated decisions and impact business processes in real time, limiting the need for human intervention. \frac{0.90}{0.01}=90, \qquad \frac{0.90}{0.00001}=90{,}000. The Lebowski agreement therefore provides much stronger evidence of a match because it is far less likely to occur by chance. This is an application of Bayes' theorem in odds form. If M denotes the hypothesis that the records match, U that they do not match, and E the observed evidence, then: \frac{P(M\mid E)}{P(U\mid E)} = \frac{P(M)}{P(U)} \frac{P(E\mid M)}{P(E\mid U)}. The odds that the records match before the evidence is considered are the prior odds, written P(M)/P(U) . The odds after considering the evidence are the posterior odds, written P(M\mid E)/P(U\mid E) . The likelihood ratio, P(E\mid M)/P(E\mid U) , describes how the evidence changes the odds. The factors of 90 and 90,000 in the surname example are likelihood ratios. Following Fellegi and Sunter, the m-probability is the probability that an identifier agrees when the records match, m=P(G\mid M) , where G is agreement on that identifier. The u-probability is the probability that it agrees by chance when they do not, u=P(G\mid U) . The likelihood ratio for an agreement is m/u ; for a disagreement, it is (1-m)/(1-u) . The logarithm of this ratio is called a linkage weight. For example, if surnames agree in 90% of matching pairs and 1% of non-matching pairs, disagreement has a likelihood ratio of 0.10/0.99 \approx 0.10 , reducing the odds of a match about tenfold. The u-probability can also be refined for particular values. In the surname example, m=0.90 , while the value-specific u-probabilities are 0.01 for Smith and 0.00001 for Lebowski, so the less common surname provides stronger evidence of a match. Both probabilities can be estimated from known matches or from the data being linked, often using the expectation–maximization algorithm. Approximate string matches can be handled in the same framework. For example, "Smith" and "Smyth" have a Levenshtein edit distance of 1. If an edit distance of exactly 1 occurs in 5% of matching surname pairs but only 0.05% of non-matching pairs, that degree of similarity is 100 times more likely for a match. Its likelihood ratio is therefore 0.05/0.0005=100 , so it multiplies the odds of a match by 100. Other string comparators, such as Jaro–Winkler, can be used in the same way. The prior odds reflect how rare true matches are among the pairs being compared. For example, if two files of 1,000 records each describe the same 1,000 people, then of the 1,000,000 possible record pairs, 1,000 are matches and 999,000 are not, so the prior odds that a randomly chosen pair matches are 1 to 999. Continuing the surname example, agreement on Smith has a likelihood ratio of 90. If the records also agree on birth month, and matching pairs agree on birth month with probability 0.95 while non-matching pairs do so with probability 1/12, the birth-month likelihood ratio is 11.4. Assuming conditional independence (see below), the combined likelihood ratio is 90 \times 11.4 = 1026 . Applying that evidence to the prior odds gives \frac{1}{999} \times 1026 \approx 1.03. Thus the posterior odds are approximately 1.03 to 1, corresponding to a posterior match probability of about 0.51. Although the observed evidence strongly favors a match, it only slightly outweighs the very low prior odds. Had the records instead agreed on Lebowski, the combined likelihood ratio would be 90{,}000 \times 11.4 = 1{,}026{,}000 , giving posterior odds of about 1,027 to 1, a match probability of about 0.999. Multiplying the likelihood ratios in this way assumes that the comparison outcomes are conditionally independent given whether the records match. This is the simplifying assumption used by a naive Bayes classifier. Under this assumption, likelihood ratios can be multiplied, or equivalently their logarithmic weights can be added. However, the assumption may be inaccurate when identifiers are associated—for example, when first and last names are correlated with one another, or when names are associated with birth year. Models that estimate probabilities jointly for combinations of identifiers can relax this assumption. The combined linkage score is then compared with decision thresholds. Record pairs with scores above an upper threshold are classified as matches, those below a lower threshold as non-matches, and those between the thresholds as possible matches that may require manual review. Raising the upper threshold produces fewer false links but misses more true matches; widening the gap between the thresholds reduces both errors at the cost of more manual review.
Machine learning
In recent years, a variety of machine learning techniques have been used in record linkage. Under the conditional independence assumption described above, field-by-field Fellegi–Sunter scoring has the same factorized form as a naive Bayes classifier. When labeled training data is available, other supervised methods can be used, such as a single-layer perceptron, random forests, and SVMs; some studies have reported higher accuracy for such supervised methods.
Human-machine hybrid record linkage
High quality record linkage often requires a human–machine hybrid system to safely manage uncertainty in the ever changing streams of chaotic big data. Recognizing that linkage errors propagate into the linked data and its analysis, interactive record linkage systems have been proposed. Interactive record linkage is defined as people iteratively fine-tuning the results from the automated methods and managing the uncertainty and its propagation to subsequent analyses. The main objectives of interactive record linkage systems is to manually resolve uncertain linkages and validate the results until it is at acceptable levels for the given application. Variations of interactive record linkage that enhance privacy during the human interaction steps have also been proposed. M = \left\{ (a,b); a=b; a \in A; b \in B \right\} and its complement, the set U of pairs representing different entities, is U = \{ (a,b); a \neq b; a \in A; b \in B \} . A vector, \gamma is defined that contains the coded agreements and disagreements on each characteristic: \gamma \left[ \alpha ( a ), \beta ( b ) \right] = \{ \gamma^{1} \left[ \alpha ( a ) , \beta ( b ) \right] ,..., \gamma^{K} \left[ \alpha ( a ), \beta ( b ) \right] \} where K is a subscript for the characteristics (sex, age, marital status, etc.) in the files. The conditional probabilities of observing a specific vector \gamma given (a, b) \in M , (a, b) \in U are defined as m(\gamma) = P \left\{ \gamma \left[ \alpha (a), \beta (b) \right] | (a,b) \in M \right\} = \sum_{(a, b) \in M} P \left\{\gamma\left[ \alpha(a), \beta(b) \right] \right\} \cdot P \left[ (a, b) | M\right] and u(\gamma) = P \left\{ \gamma \left[ \alpha (a), \beta (b) \right] | (a,b) \in U \right\} = \sum_{(a, b) \in U} P \left\{\gamma\left[ \alpha(a), \beta(b) \right] \right\} \cdot P \left[ (a, b) | U\right], respectively. Fellegi and Sunter showed that the optimal decision rule compares the likelihood ratio m(\gamma)/u(\gamma) with an upper and a lower threshold. When the components of \gamma are conditionally independent, this ratio is the product of the single-identifier likelihood ratios described in .
Master data management
Most Master data management (MDM) products use a record linkage process to identify records from different sources representing the same real-world entity. This linkage is used to create a "golden master record" containing the cleaned, reconciled data about the entity. The techniques used in MDM are the same as for record linkage generally. MDM expands this matching not only to create a "golden master record" but also to infer relationships. (i.e. a person has the same/similar surname and same/similar address, this might imply they share a household relationship).
Criticism of existing software implementations
The main reasons cited are: Project costs: costs typically in the hundreds of thousands of dollars Time: lack of enough time to deal with large-scale data cleansing software Security: concerns over sharing information, giving an application access across systems, and effects on legacy systems Scalability: Due to the absence of unique identifiers in records, record linkage is computationally expensive and difficult to scale. Accuracy: Changing business data and capturing all rules for linking is a tough and extensive exercise
Text derived from https://en.wikipedia.org/w/index.php?oldid=1377095359 under CC BY-SA 4.0; modifications have been made.