2 Background

Sander Scholtus

Previous | Next

2.1  Edits

The problem to be discussed in this article entails, in its most general form, the detection of erroneous and missing values in a record containing both categorical variables $(v_1,\dots ,v_m)$ and numerical variables $(x_1,\dots ,x_p).$ These variables are supposed to satisfy a set of restrictions (edits), each of which can be written in one of the following forms:   

or            

In these expressions, $F_j^k$ is a subset of $D_j,$ the domain of observed values for the categorical variable $v_j,$ and $a_{kj}$ and $b_k$ are known numerical constants. The index $k$ is used to number the edits. Note that $D_j$ is assumed to contain all values of $v_j$ that may be encountered in practice; this includes erroneous values. To simplify matters, we restrict the problem to edits having linear numerical conditions. This class of edits turns out to be sufficiently powerful for most practical applications (cf. De Waal 2005).

A record $(v_1^0,\dots ,v_m^0,x_1^0,\dots ,x_p^0)$ is said to fail an edit if the categorical IF-condition is true (i.e., $v_j^0\in F_j^k$ for all $j=1,\dots ,m),$ but the numerical THEN-condition is false (i.e., either $a_{k1}{x}_1+\cdots +a_{kp}{x}_p+b_k<0$ or $a_{k1}{x}_1+\cdots +a_{kp}{x}_p+b_k\ne 0,$ depending on the form of the edit). Otherwise, we say that the edit is satisfied by that record. It should be noted that an edit is always satisfied by any record for which the categorical IF-condition is false, regardless of the status of the numerical THEN-condition. A record is called consistent if it satisfies every edit.

A categorical variable $v_j$ is said to be involved in an edit if and only if $F_j^k\ne D_j,$ since any edit with $F_j^k=D_j$ is failed or satisfied regardless of the value of $v_j\text{}.$ Similarly, a numerical variable $x_j$ is said to be involved in an edit if and only if $a_{kj}\ne 0.$ We may assume that $F_j^k\ne \varnothing ,$ where $\varnothing$ denotes the empty set. Clearly, a degenerate edit with $F_j^k=\varnothing$ can be discarded with no loss of information, since it is never failed. The same holds for any edit with a numerical THEN-condition that is always true.

Two important special cases of (2.1) and (2.2) are edits that involve only categorical or only numerical variables. A purely categorical edit has the following form:

${\psi }^k:\text{IF }(v_1,\dots ,v_m)\in F_1^k\times \cdots \times F_m^k\text{ THEN }\varnothing .$(2.3)

Edit (2.3) is failed by each record for which the categorical condition is true. A purely numerical edit can be written as:

${\psi }^k:(x_1,\dots ,x_p)\in \{a_{k1}{x}_1+\cdots +a_{kp}{x}_p+b_k\ge 0\}$(2.4)

or

${\psi }^k:(x_1,\dots ,x_p)\in \{a_{k1}{x}_1+\cdots +a_{kp}{x}_p+b_k=0\}.$(2.5)

Edits (2.4) and (2.5) are failed by each record for which the numerical conditions are false.

Edits (1.1) and (1.2) above are examples of purely numerical edits. A simple example of a purely categorical edit is:

IF (Age, Marital Status) $\in$ {"<16�} $\times$ {"Married�} THEN $\varnothing .$

This edit states that persons aged less than 16 years cannot be married. Finally, an example of a mixed edit is:

IF Age $\in$ {"<12�} THEN Income = 0.

According to this edit, persons aged less than 12 years do not have a positive income.

2.2  The error localisation problem

For a given record $(v_1^0,\dots ,v_m^0,x_1^0,\dots ,x_p^0)$ and a collection of edits, it is straightforward to verify which values in the record are missing and whether any of the edits are failed. However, given that some of the edits are failed, solving the error localisation problem is much less straightforward. On the one hand, most edits involve more than one variable, and on the other hand, most variables are involved in more than one edit.

In order to solve the error localisation problem automatically, one has to adopt a formal strategy for finding erroneous values. The most commonly-used strategy is based on the paradigm of Fellegi and Holt (1976): make the record consistent by changing the smallest possible number of original values. Other strategies have also been proposed; for instance, Little and Smith (1987) suggested a criterion based on outlier detection (without edits) and Casado Valero, Del Castillo Cuervo-Arango, Mateo Ayerra and De Santos Ballesteros (1996) formulated error localisation as a quadratic minimisation problem. We shall restrict attention to the Fellegi-Holt paradigm here, because of its frequent use in official statistics.

The original Fellegi-Holt paradigm is easily generalised to allow a distinction between a priori suspicious and less suspicious variables. To this end, one associates a confidence weight to each variable. According to the generalised Fellegi-Holt paradigm, one should search for a subset of the variables which (i) can be imputed in such a way that the imputed record satisfies all edits, and (ii) minimises the following target function:

$D_{\text{FH}}={\displaystyle \sum _{j=1}^m{w}_j^C{y}_j^C}+{\displaystyle \sum _{j=1}^p{w}_j^N{y}_j^N}.$(2.6)

Here, $w_j^C$ and $w_j^N$ denote the confidence weights of the categorical and numerical variables, respectively. The binary target variables $y_j^C$ and $y_j^N$ describe the structure of the solution: $y_j^C=1$ if $v_j$ is to be imputed and $y_j^C=0$ otherwise, and similarly $y_j^N=1$ if $x_j$ is to be imputed and $y_j^N=0$ otherwise. Since variables with missing values have to be imputed with certainty, we set $y_j^C=1$ or $y_j^N=1$ when $v_j^0$ or $x_j^0$ is missing.

Fellegi and Holt (1976) also presented a method for solving the error localisation problem under this paradigm. This method first derives a well-defined set of logically implied edits from the original set of edits, to obtain a so-called complete set of edits. Next, the error localisation problem may be formulated as a straightforward set-covering problem for any record (Fellegi and Holt 1976; Boskovitz, Goré and Wong 2005). Unfortunately, especially for numerical data the complete set of edits can be extremely large in practice, so the method of Fellegi and Holt is not always computationally feasible.

Many alternative algorithms have been developed for error localisation according to the Fellegi-Holt paradigm. Besides improvements on Fellegi and Holt's original method (Garfinkel, Kunnathur and Liepins 1986; Winkler 1995), the list includes formulations based on vertex generation (Sande 1978; Kovar and Whitridge 1990; Todaro 1999; De Waal 2003a), cutting planes (Garfinkel et al. 1986; Garfinkel, Kunnathur and Liepins 1988; Ragsdale and McKeown 1996), and mixed integer (Schaffer 1987; Riera-Ledesma and Salazar-González 2003) and integer programming (Bruni 2004 and 2005); see also De Waal et al. (2011) for an overview. Here, we shall focus on a branch-and-bound algorithm due to De Waal and Quere (2003) which, in contrast to some of the above approaches, can handle a mix of categorical and numerical data. This algorithm has been implemented in the software package SLICE at Statistics Netherlands and has been found to be computationally feasible in practice.

2.3  The branch-and-bound algorithm of SLICE

A detailed description of the error localisation algorithm implemented in SLICE can be found in De Waal and Quere (2003), De Waal (2003b), and De Waal et al. (2011). Here, we only mention those aspects of the algorithm that we shall need later. For a general introduction to branch-and-bound algorithms, see e.g., Nemhauser and Wolsey (1988).

For each record, the SLICE algorithm sets up a binary tree, as illustrated in Figure 2.1. In the root node of the tree, we start with the original set of edits and we select one of the variables. From the root node, two branches are added to the tree. In the first branch, the original value of the selected variable in the record is assumed to be correct, and in the second branch this value is assumed to be erroneous. Both assumptions correspond with a transformation of the set of edits, to be outlined below, after which the selected variable is no longer involved in the edits: the selected variable has been treated. Next, one of the remaining variables is selected and the operation is repeated.

Figure 2.1 Illustration of the branch-and-bound algorithm as a binary tree

Once all variables have been treated, the algorithm reaches an end node of the tree. It is seen that, together, the end nodes of the binary tree enumerate all possible choices of erroneous subsets of variables. The transformed set of edits corresponding to an end node does not involve any variables, so it must either be empty or consist of elementary relations such as "1 ≥ 0� (a tautology) and "$–$1 ≥ 0� (a self-contradicting statement). As will be discussed below, it is possible to satisfy the original edits by only imputing the variables that have been considered erroneous in the branch leading to an end node, if and only if the transformed set of edits for that end node contains no self-contradicting statements. Using this property, all feasible solutions to the error localisation problem may be identified. Moreover, since we are only interested in feasible solutions that minimise target function (2.6), a branch of the tree may be pruned as soon as we find that it only leads to end nodes corresponding with infeasible or suboptimal solutions.

We will now outline the transformations of the set of edits that occur, depending on whether a variable is assumed to be correct or erroneous. A variable that is assumed to be correct is removed from the edits by simply substituting the original value from the record in the edits. This is called fixing a variable to its original value. A variable that is assumed to be erroneous is removed from the edits by a more complex operation, called eliminating a variable from the edits. Numerical variables and categorical variables are eliminated by two different but equivalent methods.

To eliminate a numerical variable, say $x_g,$ from a set of edits having the general forms (2.1) and (2.2), we generate logically implied edits by considering all pairs of edits ${\psi }^s$ and ${\psi }^t$ that involve $x_g.$ We first check whether $F_j^s\cap F_j^t\ne \varnothing$ for all $j=1,\dots ,m;$ if any of these intersections yields the empty set, then the pair ${\psi }^s$ and ${\psi }^t$ does not generate an implied edit. If the numerical THEN-condition of one of the edits, say ${\psi }^s,$ is an equality, then this equality may be solved for $x_g.$ By substituting the resulting expression for $x_g$ in the THEN-condition of ${\psi }^t,$ we obtain the numerical THEN-condition of the implied edit. The categorical IF-condition of the implied edit is found by taking the non-empty intersections $F_j^{\ast }=F_j^s\cap F_j^t$ for $j=1,\dots ,m.$

If the numerical THEN-conditions of ${\psi }^s$ and ${\psi }^t$ are both inequalities, the algorithm uses a technique called Fourier-Motzkin elimination (see e.g., Williams 1986) to generate an implied edit. A pair of edits is relevant for this elimination method only if the coefficients of $x_g$ have opposite signs, so we may assume without loss of generality that $a_{sg}<0$ and $a_{tg}>0.$ The implied edit generated from ${\psi }^s$ and ${\psi }^t$ may then be written as (cf. De Waal and Quere 2003):

with $a_j^{\ast }=a_{tg}{a}_{sj}-a_{sg}{a}_{tj},b^{*}=a_{tg}{b}_s-a_{sg}{b}_t,$  and $F_j^{\ast }=F_j^s\cap F_j^t$ as above. This edit does not involve $x_g,$ since $a_g^{\ast }=0.$ In this manner, implied edits are generated by considering all pairs of edits that involve $x_g.$ These edits are added to the set of original edits that do not involve $x_g,$ to find the transformed set of edits obtained by eliminating $x_g.$

For the elimination of categorical variables, De Waal and Quere (2003) make the simplifying assumption that these variables are only selected when all numerical variables have been treated. This assumption implies that categorical variables are always eliminated from purely categorical edits of the form (2.3). To eliminate a categorical variable, say $v_g,$ from a set of edits of the form (2.3), a technique is used that was first described by Fellegi and Holt (1976).

Consider all minimal sets of edits $T$ with the following properties:

$F_g^{\ast }(T)={\displaystyle \underset{k\in T}{\cup }{F}_g^k}=D_g$(2.8)

and

$F_j^{\ast }(T)={\displaystyle \underset{k\in T}{\cap }{F}_j^k\ne \varnothing }\text{,}$ for $j=1,\dots ,g-1,g+1,\dots ,m.$(2.9)

Here, by "minimal� we mean that property (2.8) does not hold for any set $T^{\prime }\subset T.$ Each of these minimal sets $T$ generates an implied edit:

$\begin{array}{ll}{\psi }^{\ast }:\hfill & \text{IF }(v_1,\dots ,v_m)\hfill \end{array}\in F_1^{\ast }(T)\times \cdots \times F_m^{\ast }(T)$ THEN $\varnothing ,$(2.10)

which does not involve $v_g$ because of property (2.8). These implied edits are added to the set of original edits that do not involve $v_g,$ to find the transformed set of edits obtained by eliminating $v_g.$

It should be clear that the computational work of the algorithm lies mainly in the elimination steps. In particular, it is known that the number of implied edits under Fourier-Motzkin elimination may be exponential in the number of eliminated variables (Schrijver 1986).

A fundamental property of both elimination techniques, for numerical and categorical variables, is exhibited by the following result. Consider a system of implied edits ${\Psi }_1$ obtained by eliminating $x_g$ or $v_g$ from a system of edits ${\Psi }_0.$ Then the original values of the untreated variables satisfy all edits in ${\Psi }_1,$ if and only if there exists a value for $x_g$ or $v_g$ that, together with these original values, satisfies all edits in ${\Psi }_0.$ For a proof, see Theorem 8.1 in De Waal (2003b) or Theorem 4.3 in De Waal et al. (2011). The above-mentioned correspondence between end nodes without self-contradicting elementary relations and feasible solutions to the error localisation problem follows from a repeated application of this fundamental property.

Previous | Next