Record linkage is an important problem to be solved in all contexts in which data integration is to be performed under the hypothesis of data sources that can exhibit errors. In this paper we formulate the record linkage problem as a multiobjective optimization problem and we propose an algorithm for solving it based on evolutionary computation. This computational paradigm has a stochastic, adaptive and intrinsically parallel nature that makes it particularly suitable for a peer-to-peer integration context. Experiments on real datasets proved the effectiveness and efficiency of this novel approach.
Peer data management systems (PDMSs) are distributed data management systems where peers interact according to a peer-to-peer paradigm. Differently from traditional data integration systems, no centralized global schema is present, but each peer maps its own schema to schemas of other peers on a local basis. These systems are characterized by large scale, high dinamicity and openness.
Query answering in these systems is realized by exploiting peer mappings that describe the semantic relationships between the schemas of pairs (or small sets of) peers. In order to specify such mappings, it is important to join the different sources on identifying attributes. In real integration scenarios, such attributes may be affected by errors, that is joins cannot be performed in an exact way, but some approximation must be introduced.
In order to implement approximate joins for the purpose of integrating data, a record linkage activity must be performed. Given two (or more records) record linkage (RL) has the purpose of comparing them on some common attributes and deciding if they are a match or not, on the basis of the result of such a comparison. The record linkage problem has been studied since more than five decades, but Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
Copyright 2008 ACM X-XXXXX-XX-X/XX/XX ...$5.00. in the context of peer data management systems, it presents new research challenges.
More specifically, record linkage techniques can be
classified into: probabilistic, knowledge-based and empirical
[
In knowledge-based techniques (e.g., [
Empirical techniques (see e.g., [
To overcome these limitations, we propose to solve the record linkage in a PDMS setting by using a completely novel approach, based on evolutionary computation. Evolutionary algorithms have all the features desired for this specific setting: they are stochastic, adaptive and intrinsically parallel search algorithms. Indeed, the stochastic feature and the intrinsic parallelism can help to face problems deriving from large scale; adaptiveness is very important for the dinamicity and openness of PDMSs.
More specifically, in this paper, we first formulate the record linkage problem as a multiobjective optimization problem. Then, we extend an evolutionary algorithm named NSGA-II, used for solving multiobjective optimization problems, in order to solve our problem. We experimentally show that our algorithm has good performance, both in terms of effectiveness and efficiency.
The rest of the paper is organized as follows. After some background definitions, provided in Section 2, Section 3 describes two formulations of the record linkage problem. Then, in Section 4, we describe the details of the proposed algorithm. Finally, we present our experimental results in Section 5 and we draw some conclusions in Section 7. The related work is presented in Section 6.
Before presenting the details of our algorithm we provide
some background definitions. In general, multiobjective
optimization problems can be defined in the following way [
M in/M ax fm(x)
m = 1, 2, ..., M gj > 0 j = 0, ..., J hk = 0 k = 1, ..., K xiL 6 xi 6 xi
U i = 1, ..., n.
(1) (2) (3) (4)
Where f is the function to optimize, (2) and (3) represent constraints to be satisfied and (4) is the interval of values that xi can assume.
The differences between multiobjective optimization problems and the single-objective ones are: • M objectives instead of a single one; • beside the n-dimensional space of the admissible solutions (which is also present in single-objective optimization problems), there is a further M-dimensional space whose coordinates correspond to the M objectives of the problem; • generation of a set of solutions.
In a multiobjective optimization scenario a different definition of optimum is needed. In the following we introduce the notion of Pareto optimum that is the one mainly adopted in these cases.
Definition - Pareto Optimality A solution x ∈ Ω is Pareto optimal in Ω if and only if there is no y ∈ Ω : v = F (y) = f1(y), f2(y), ..., fk(y) dominates u = F (x) = f1(x), f2(x), ..., fk(x).
To state if a solution x is better than a solution y we refer to the following definition:
Definition - Pareto Dominance A vector u = (u1, ..., uk) dominates a vector v = (v1, ..., vk) (u v) if and only if ∀i ∈ {1, .., k} ui 6 vi and ∃i ∈ {1, .., k} ui < vi. With this ordering relation between the solutions an optimal set will be defined in the following way: Definition - Pareto Optimal Set Let us consider an optimization problem where F (x) is the function to be optimized, the Pareto Optimal Set P is: P = {x ∈ Ω | ∄y ∈ Ω F (y) F (x)}.
For each decision variable belonging to the Pareto Optimal Set there is a correspondent vector in the space of the objective function as stated by the following definition:
Definition - Pareto Front Let us consider an optimization problem with an objective function F (x) and a Pareto Optimal Set P, the Pareto Front F is defined as: F = {u = F (x) | x ∈ P}.
Multiobjective optimization problems can be solved with
evolutionary algorithms [
Definition - Evolutionary Algorithm An evolutionary algorithm is defined as an 8-tuple EA = (I, Φ, Ω, μ, λ, s, ι, Ψ) where: • I = Ax × As is the space of the individuals with Ax e
As arbitrary sets. • Φ : I 7−→ R denotes the fitness function which assigns real values to the individuals. • Ω = {ωΘi, ..., ωΘz | ωΘi : Iλ 7→ Iλ} ∪ {ωΘ0 : Iμ 7→ Iλ} is a set of probabilistic genetic operators ωΘi, each one controlled by specific parameters contained in Θi ⊂ R. λ is the number of son-individuals and μ is the number of father-individuals. • sΘi : (Iλ ∪ Iμ+λ) 7→ Iμ denotes the selection operator that can change the number of individuals from λ to μ + λ where λ = μ is allowed. A further set of parameters Θs can be used by the selection operator. • Finally ι : Iμ 7→ {true, f alse} is an ending condition for the evolutionary algorithm and the transition function Ψ : Iμ 7→ Iμ describes the transformation process of a population P into the next one by applying the genetic operators and the selection: – Ψ = s ◦ ωΘ1 ◦ ... ◦ ωΘj ◦ ωΘ0 – Ψ(P) = sΘi(Q S ωΘi1 (...(ωΘij (ωΘ0(P)))...)) – {i1, ..., ij} ⊆ {1, ...z}
Q ∈ {∅, P} 3.
Let us consider two files, say A and B, of dimension n and m respectively. Without loss of generality we assume that n 6 m.
In our work we formulate the RL problem as a multiobjective optimization problem, according to two distinct formulations, detailed in the following.
m n max X X F (yiA, yjB) · xij i=1 j=1 m X xij 6 1 j=1 n X xij 6 1 i=1 Variables xij are equal to 1 when record j of file B has been assigned/matched to record i of file A and 0 otherwise.
The function F (yiA, yjB) calculates the distances between
fields of record i of file A and fields of record j of file B and
it is composed by the functions f1(yiA1, yjB1), ..., fn(yiAn, yjBn).
These functions can be chosen among a set of comparison
functions between strings such as Edit Distance, Jaro and
others [
Constraints (6) and (7) assure that the match is one to one. Specifically, a record of the file A can be matched with at most one record of the file B and viceversa.
The goal is to maximize the total values for comparison functions.
Let us suppose to run a RL procedure between table 1 and table 2, shown in the following. As a first step we focus on the common attributes of file A and file B thus obtaining files A’ and B’ shown in tables 3 e 4.
The problem formulation for this input is:
Notice that for both Surname and Address we have chosen the edit distance as comparison function.
An optimal solution for this case is obtained with the following assignment of the variables:
x11 = 1 x22 = 1 x33 = 1 ∀ij (1 ≤ i ≤ 3 ∧ 1 ≤ j ≤ 4 ∧ i 6= j) → xij = 0.
Formulation I does not take into account any threshold value when comparing different record fields on the basis of similarity functions. However, this is a common input to several record linkage procedures; therefore, we include these thresholds in a second problem formulation, detailed in the following.
m n max X X(F (yiA, yjB) · xij) · tij i=1 j=1 (12) The objective of this problem formulation is the maximization of the global similarity values of those match that satisfy the condition F (yiA, yjB) > V and xij = 1 where V is a vector of similarity thresholds that a match must exceed or at least be equal in order to be considered a true match. For this second formulation of the problem we developed an algorithm that uses a specific mutation genetic operator in order to focus the search. The genes of the individual of the population that is submitted to mutation are changed in a selective way. The mutated genes are those that correspond to matches that do not satisfy the condition F (yiA, yjB) > V and xij = 1 .
In this section we describe the algorithm we propose for record linkage, called EARL (Evolutionary Algorithm for Record Linkage). The aim of the algorithm is to generate a matching of records where the total distance between each attribute selected for the match is maximized, according to the given problem formulations.
The algorithm is composed by the phases shown in Figure 1, which are described in the following. 4.1
The parameters that are input to EARL are: • The dimension of the initial population, the number of generations and a parameter, named x, which is a negative integer that supports the creation of individuals (as better detailed in the following). All these parameters are set on the basis of the results we have obtained from tests on real datasets, detailed in Section 5. • Matching attributes, that is those attributes of the input files that will be actually compared for taking the EARL
In the following, we will indicate as donor file, the file which has the highest number of records; instead, we will indicate as receiving file the other one. The donor and receiving files are read in two multidimensional arrays, with a number of rows equal to the records of each file and a number of columns equal to the number of attributes selected for the match. The first population is generated in a random way starting from the files which are input to the record linkage procedure. Let m be the dimension of the donor file and n be the dimension of the receiving file. Each individual of the initial population, say v, is represented by an array of objects with dimension n. Each object is a vector of k values corresponding to values of the comparison function function for each attribute in case of a match, it is vector of zero otherwise. The following pseudocode shows how each individual is created. for i =1 to n z =randomGen(x,m) if z <0 else if z =q>0
The function randomGen generates a random value between x and m, where x is a parameter set in dependence of the value of m (see Section 5); the idea is to select randomly the index of the record of the donor file to match (or not) with the current index of the record of the receiving file. The variable z has a negative value in the case of a decision of not assigning a match for the corresponding records which have been compared; it has a positive value otherwise.
In order to satisfy the RL one-to-one constraint, when creating the new individual a preventive check is performed to avoid the creation of inadmissible solutions. 2. Evaluation of the individuals for each objective 3. Assignment of a rank to each individual in function of a ranking based on the Pareto dominance principle 4. Generation of individuals from P1 in order to obtain a population P1′ of size 2N (a) Extraction of individuals from P1 with a selection (b) Crossover and mutation of the extracted individuals 5. f or i = 1 to g
For each individual of population Pi′ with i > 1 (a) According to the Pareto dominance principle, assignment of a rank to each individual and conforming partition of the population into nondominated fronts Fk (b) Creation of a new population Pi+1 of size N from Pi′ for j = 0 to j < k Fj.size < N − Pi+1.size sorting the solutions of Fj by the so-called
crowding distance 1
Pi+1 = Pi+1 ∪ Fj (c) If N − Pi+1.size > 0 sorting of the solutions of Fj according to the
crowding distance adding of the first N − Pi+1.size of FJ to Pi+1 (d) Creation of Pi′+1 through selection, crossover and mutation on Pi+1
The algorithm creates a population of individuals, it sorts each individual according to its level of non-domination then it applies the evolutionary operators to the population. The favorite individuals for the new population are those with the best rank and with the best crowding distance (elitism).
The algorithm NSGA-II is initialized in the following way: • N is the initial population where each individual represents a linkage between the receiving file and the donor file; • g is the number of generations; 1The crowding distance is computed for each objective i in the following way: • sorting of the solutions according to the objective i; • computation of the distance of the individual s as the difference between the values of fi assumed by the previous and by the next individual of s, this value is normalized with the difference that the first and the last individuals assume for objective i; • he crowding distance of individual s will be the sum of these distances obtained for each objective i. • the function to be optimized is:
n F (v) = X[vi1, . . . , vik] = [v1, . . . , vk] i=1 (16) where v1 denotes (a value for) the global similarity between the strings of the field that corresponds to the first matching attribute of the record of the receiving file and of the donor file of the individual v.
• the genetic operators defined in the following section.
In this section we describe the genetic operators used in EARL. The selection operator is binary tournament, as typically used in NSGA-II.
The binary tournament genetic operator selects the individuals of the population in the following way: 1. a sorted array whose length is equal to the dimension of the population is created, each field of the array contains an integer that represents an individual of the population, the array can contain the same elements; 2. it takes the individual i and the individual i + 1, selected between the followings: • the individual with the best rank; • the individual with the best crowding distance,
when having the same rank; • the individual is randomly selected, when having
the same rank and the same crowding distance.
The crossover and mutation operators have been newly defined in order to fit our specific problem.
Our crossover operator takes as input two individuals and returns two individuals built with the best genes of the starting individuals. To perform this kind of crossover the genes of the starting individuals are compared one by one, if there exists a gene that dominates (according to the Pareto Dominance principle) the other, this gene is selected to create the new individual, otherwise, if none of the individuals dominate another one, the choice will be random.
Our mutation operator changes those genes that correspond to values of the similarity function that will probably lead to false-matching. Specifically the similarity functions assume values between 0 and 1 and if the value computed between any two attributes of two records is 0 then with a high probability the two records don’t represent the same entity.
The genes of the individual submitted to mutation are changed in part according to the described mutation operator and in part randomly. The described mutation is mainly performed in the first generations and becomes less frequent in the next generations when the ratio between nongood genes and the total genes is less significant. On the other hand the random mutation, that is always applied to the same part of the population during all the generations, avoids the risk of a too premature convergence and the risk of falling into local maxima of the function.
In order to satisfy the RL one-to-one constraint, when creating the new individual a repairing action is performed. 1 7 5 0 a no uf imn ibtiea rl po fo ipn udlaiv tiido un ls
This section describes a set of experiments performed with the objective of testing the effectiveness and efficiency of EARL.
We have used real data sets about personal data related to Rome citizens, owned by an Italian public administration. Specifically, we have run experiments on two datasets that were populated by different processes, each of size of about 8000 records. On these datasets, in the following dataset A and dataset B, a record linkage activity had already been performed in the context of a project lasted several months and involving both deterministic and probabilistic procedures. A significant human intervention was also necessary in order to decide the status of matching of records. We used these already available results as a benchmark for evaluating the effectiveness of EARL.
As far as the technological platform, we ran experiments
on a PC with CPU of 2 Ghz and RAM of 1 GB, with OSX
operating system. EARL was developed in Java. A tool
called jmetal [
In order to better study the behavior of EARL, we extracted 3 subsets of data from datasets A and B, respectively of sizes 300, 600, and 1000.
First of all we studied how to set up the dimension of the initial population.
Figure 2 shows how the number of true matches increases with the dimension of the initial population for the two problem formulations we have provided. Specifically, algorithm EARL 1 corresponds to the first problem formulation: the curve consistently grows up with number of individuals. Algorithm EARL 2 corresponds to the second problem formulation, in which thresholds on the matching attributes have all been fixed to 0.8. As it is shown, the EARL 2 curve is constant when varying the number of individuals of the initial population, which is a quite interesting finding. In order to understand the effect on the time behavior of this result, we have studied the execution times, when varying the number of individuals of the population. In Figure 3, we report the execution time for the dataset of 1000 records: obviously the time increases with the dimension of the initial population, though quite slowly, confirming the substantial independence of the EARL 2 algorithm from the dimension of the initial population.
A second set of experiments was made in order to consider how to fix the number of generations. Such experiments (that we do not report for lack of space) allowed to study the number of evaluations, defined as the product between the number of individuals and the number of generations. The experiments showed: • A few number of generations was necessary for the convergence of EARL 1. 2 • how to fix the number of generations of EARL 2, in dependence of the behavior of the number of evaluations when varying the dimensions of the input datasets.
A third set of experiments allowed us to choose a value for the x parameter (see Section 4). We have observed that the parameter has an impact on how fast the algorithm converges, and hence on effectiveness and efficiency. More specifically, high values of x leads to a low effectiveness, remaining constant the number of generations and the dimension of the population. Hence, a rule of thumb for the choice of x is to consider quite low values, between 2% and 5% of the dataset with the highest dimension.
Finally, in Figure 4, we report the effectiveness performance of EARL 1 and EARL 2 that must be compared to the real performance figures we had for our benchmark data. The number of true matches is reported for EARL 1, EARL 2 and the real data. We can notice that: • the performance of EARL 1 are quite good for datasets of 300, 600 and 1000 records, while become dramatically low for the 8000 record data set. This is mainly due to the fact that for such data set it was not possible, due to memory limitations of the experimental environment, to increase the number of individuals of the initial population in order to have better performance. • the performance of EARL 2 (which are independent on the number of individuals of the initial population) are instead very good, even when compared with exact methods for record linkage, being the percentage of the true matches always higher than 80% of the real true matches with peaks of more than the 90%.
In synthesis, algorithm EARL 1 is really independent on the data, and does not need to fix parameters like threshold values that require an accurate analysis of the data at hand. 2Actually we verified that the behavior of EARL 1 can lead to a premature convergence to local maxima independent on the number of generations. On the other hand it can have performance that are not acceptable (but can be refined by appropriate tuning some parameters). Algorithm EARL 2 exhibits very good performance but threshold values must be fixed for the matching attributes.
Finally, we ran an experiment with the objective to test the time efficiency of the two algorithms (EARL 1 and EARL 2 of course have the same time performance, implementing the same computational steps). In Figure 5, we show the time necessary for the execution versus the dimensions of the input datasets, to which we added a 20000 record datasets, obtained synthetically from the 8000 record one. We can observe that the such performance are really good: for the maximum size datasets, that is 20000 records each, the time is of slightly more than one hour.
In this section, we briefly review some works of the area of multiobjective optimization through evolutionary algorithms.
In 1985 Schaffer [
As far as we know, genetic algorithms haven’t been used
expressly for the RL process, but some of the approaches
proposed for database merging provided a useful
contribution to such a usage. In [
In this paper we have presented an original formulation of the record linkage problem as a multiobjective optimization problem, and we have proposed an evolutionary algorithm, EARL, for solving it. The context in which we see the major application of this algorithm is the one of peer-to-peer management systems. In its current implementation, EARL has the following advantages if used in this context: • first, it is a one-shot algorithm. Specifically, record linkage is typically implemented as a process with different algorithms for each of its phases, such as a search space reduction phase which involves sorting algorithms, a phase where the appropriate comparison functions must be chosen, a decision phase with related algorithms, etc. Instead, EARL is a single algorithm that can be easily run even in complex contexts like PDMSs. • Second, as it is based on an evolutionary paradigm, it depends just on data, that is EARL automatically adapts to data at hand with limited human knowledge required.
However, it still needs an accurate design in order to be deployed on a P2P platform. We plan to address the issues regarding such design in the future. These issues include: • the integration of the algorithm within the query answering process; • the design of distributed mechanisms for enacting the algorithm in a peer to peer context; • the physical distributed implementation of the algorithm. datasets where each record from one of the files is matched with a record from the second file that generally does not represent the same unit, but does represent a similar unit.