Developing and Evaluating a Learning String Comparator

• Activity Number: 113
• Type: Topic Contributed
• Date/Time: Monday, August 4, 2003 : 10:30 AM to 12:20 PM
• Sponsor: Section on Survey Research Methods
• Author(s): William E. Yancey*+
• Companies: U.S. Census Bureau
• Keywords: record linkage ; string comparator ; automatic spelling correction ; EM algorithm ; Levenshtein distance ; edit distance

Abstract

Record linkage procedures compare corresponding fields in pairs of file records to estimate the likelihood that the two records both represent the same entity. Even when comparing two matching records, two name fields may differ due to typographical error. In order to allow for minor differences between these fields, a string comparator is used to assign a measure to the similarity between the two strings. A common string comparator measure is Levenshtein distance, which assigns a cost to the string pair that equals the count of the minimum number of insertions, deletions, or substitutions required to convert one string to the other. We examine the effects of modifying this measure by using a cost function that varies according to the characters involved. These cost function values are estimated using a probabilistic interpretation of the costs, then estimating these parameters with a simple EM algorithm applied to training data. One possible advantage to this approach is that the cost function is adaptable to the method of data recording. We compare results using the adaptive cost comparator to the standard Levenshtein distance and the Jaro-Winkler string comparator.