8 Conclusion

Sander Scholtus

Previous

In this article, we proposed a new formulation of the error localisation problem which can take the distinction between hard and soft edits into account. In addition, we showed that a modified version of the branch-and-bound algorithm of De Waal and Quere (2003) can be used to solve this new error localisation problem. It was suggested that this new algorithm can be used to increase the quality of automatic editing. This suggestion was confirmed by the empirical results reported in Section 7, although it should be stressed that these results were obtained with data containing synthetic errors. An application is currently being investigated of the new error localisation algorithm to realistic data.

It remains an open problem how the costs of soft edit failures may best be modelled, i.e., how the term $D_{\text{soft}}$ in (3.1) should be defined. The different results with approaches C and D in Section 7 demonstrate that the quality of automatic error localisation may be improved by a suitable choice of failure weights. It will be interesting to see to what extent the quality of automatic editing may be improved further by experimenting with different combinations of failure weights $s_k,$ confidence weights $w_j,$ and the balancing parameter $\lambda$ in (3.1).

Other forms of $D_{\text{soft}}$ than (3.2) could also be considered, including forms that depend on the sizes of the soft edit failures. As mentioned in Section 3, it is intuitively appealing to take the amounts by which soft edits are failed into account in the error localisation problem, so that larger soft edit failures yield higher values of $D_{\text{soft}}.$ One interesting choice for $D_{\text{soft}}$ could be the Mahalanobis distance of soft edit failures, as suggested by Hedlin (2003) in a different context. It should be noted that the algorithm from Section 6 may be used to solve the error localisation problem for all choices of $D_{\text{soft}}$ that can be expressed as (reasonably well-behaved) functions of $z_1,\dots ,z_{K_S}.$ One simply uses the appropriate expression for $D_{\text{soft}}$ as the target function in problem (5.1). On the other hand, if $D_{\text{soft}}$ depends explicitly on the sizes of the soft edit failures, then we have to resort to a more complex approach. In particular, the information provided by Theorems 1 and 2 is no longer sufficient, because we now need to know not only which soft edits will be failed after imputation but also the amounts by which they will be failed. An approach for solving the error localisation problem in this more complicated situation can be found in Scholtus (2011).

In summary, it remains to be seen how the theoretical results outlined in this article should be applied to obtain the best results in practice. Nevertheless, given that subject-matter experts use the conceptual difference between hard and soft edits during manual editing, it seems evident that the new error localisation algorithm has the potential to increase the quality of automatic editing.

Acknowledgements

The views expressed in this article are those of the author and do not necessarily reflect the policies of Statistics Netherlands. The author would like to thank: Jeroen Pannekoek and Ton de Waal for their many helpful suggestions; Edwin de Jonge and Mark van der Loo for programming the branch-and-bound algorithm in R; Sevinç Göksen for collecting the evaluation results presented in Section 7; and finally the Associate Editor and two anonymous referees for their constructive comments.

Appendix A Proofs

A.1  Proof of Theorem 1

In order to prove Theorem 1, it is convenient to prove first an auxiliary lemma. Suppose that ${\Psi }_q$ is obtained from ${\Psi }_{q-1}$ by eliminating $x_g.$ We define, for each edit ${\psi }_q^k,$ the index set $A_q^k$ of the edit(s) in ${\Psi }_{q-1}$ from which it has been derived. That is to say, we define $A_q^k:=\{l\}$ if ${\psi }_q^k$ is obtained by copying the edit ${\psi }_{q-1}^l,$ and we define $A_q^k:=\{s,t\}$ if ${\psi }_q^k$ is obtained by eliminating a variable from the pair of edits $({\psi }_{q-1}^s,{\psi }_{q-1}^t).$

Lemma 1. Consider the situation of Theorem 1 for $q\ge 1,$ and suppose that $x_g$ has been eliminated to obtain ${\Psi }_q$ from ${\Psi }_{q-1}.$ Let $A$ be a representing set of the index sets $A_q^k$ belonging to all ${\psi }_q^k\in {\Psi }_q^{(2)}.$ Then there exists a value for $x_g$ that, together with the original values of the variables that are involved in ${\Psi }_q,$ satisfies all edits in ${\Psi }_{q-1}$ except those in $A.$

Proof (of Lemma 1). By construction, $A$ contains all indices of failed edits from ${\Psi }_{q-1}$ which do not involve $x_g.$ Hence, the only way for the lemma to be false would be if there existed two edits that involve $x_g,$ say ${\psi }_{q-1}^s$ and ${\psi }_{q-1}^t,$ with $s\notin A$ and $t\notin A,$ so that it is not possible to find a value for $x_g$ that satisfies both edits simultaneously. In this case, an implied edit in ${\Psi }_q$ is generated by eliminating $x_g$ from ${\psi }_{q-1}^s$ and ${\psi }_{q-1}^t.$ Moreover, by the fundamental property given at the end of Section 2.3, this implied edit must be failed by the original values of the other variables, i.e., the implied edit must be an element of ${\Psi }_q^{(2)}.$ But this would contradict the assumption that $A$ is a representing set of $A_q^k$ for all ${\psi }_q^k\in {\Psi }_q^{(2)}.$ Hence, it is impossible to find such a pair of edits, and the lemma follows.

The proof of Theorem 1 now proceeds by induction on the number of treated variables $q.$ For $q=0,$ the statement is trivial. For $q=1,$ the theorem follows as a special case of Lemma 1; note that $B_1^k\equiv A_1^k.$ We suppose therefore that the statement has been proved for all $q\in \{0,1,\dots ,Q-1\},$ and we consider the case $q=Q,$ with $Q\ge 2.$

If ${\Psi }_Q$ is obtained from ${\Psi }_{Q-1}$ by fixing a variable to its original value, and $B$ is a representing set of the sets $B_Q^k$ for the failed edits from ${\Psi }_Q,$ then by construction $B$ is also a representing set of the sets $B_{Q-1}^k$ for the failed edits from ${\Psi }_{Q-1}.$ Thus, in this case, the statement for $q=Q$ follows immediately from the induction hypothesis.

Hence, we are left with the case that ${\Psi }_Q$ is obtained from ${\Psi }_{Q-1}$ by eliminating a variable, say $x_g.$ We define, for each ${\psi }_Q^k\in {\Psi }_Q^{(2)},$ the index set $A_Q^k$ of the edit(s) from ${\Psi }_{Q-1}$ from which ${\psi }_Q^k$ is derived, as above. Next, we use $B$ to construct a set $A,$ by applying the following procedure to each ${\psi }_Q^k\in {\Psi }_Q^{(2)}:$

It is easy to see that this procedure produces a representing set $A$ of the index sets $A_Q^k$ for all ${\psi }_Q^k\in {\Psi }_Q^{(2)}.$

According to Lemma 1, there exists a value for $x_g$ which, together with the original values of the $p-q$ variables that have not been treated, satisfies the edits in ${\Psi }_{Q-1}$ except those in $A.$ That is to say, ${\Psi }_{Q-1}$ can be partitioned similarly to ${\Psi }_Q$ as ${\Psi }_{Q-1}={\Psi }_{Q-1}^{(1)}\cup {\Psi }_{Q-1}^{(2)},$ where ${\Psi }_{Q-1}^{(2)}$ contains the edits with indices in $A.$ Moreover, it is not difficult to see that the above procedure implies that $B$ is a representing set of the index sets $B_{Q-1}^k$ for all ${\psi }_{Q-1}^k\in {\Psi }_{Q-1}^{(2)}.$ Hence, the induction hypothesis establishes that, given the original values of the variables that have not been eliminated and given the chosen value for $x_g,$ there exist values for the other eliminated variables that satisfy all the original edits except those in $B.$ This shows that the statement holds for $q=Q$ and completes the proof of Theorem 1.

A.2  Proof of Theorem 2

To prove Theorem 2, we start again with an auxiliary lemma. Analogous to the numerical case, when ${\Psi }_q$ is obtained from ${\Psi }_{q-1}$ by eliminating $v_g,$ we define the index set $A_q^k$ of edits in ${\Psi }_{q-1}$ from which the edit ${\psi }_q^k\in {\Psi }_q$ is derived. To be precise, we define $A_q^k:=\{l\}$ if ${\psi }_q^k$ is obtained by copying the edit ${\psi }_{q-1}^l,$ and we define $A_q^k:=T$ if ${\psi }_q^k$ is obtained by eliminating a variable from the set of edits ${\psi }_{q-1}^t(t\in T).$

Lemma 2. Consider the situation of Theorem 2 for $q\ge 1,$ and suppose that $v_g$ has been eliminated to obtain ${\Psi }_q$ from ${\Psi }_{q-1}.$ Let $A$ be a representing set of the index sets $A_q^k$ belonging to all ${\psi }_q^k\in {\Psi }_q^{(2)}.$ Then there exists a value for $v_g$ that, together with the original values of the variables that are involved in ${\Psi }_q,$ satisfies all edits in ${\Psi }_{q-1}$ except those in $A.$

Proof (of Lemma 2). By construction, $A$ contains all indices of failed edits from ${\Psi }_{q-1}$ which do not involve $v_g.$ Hence, the only way for the lemma to be false would be if there existed edits that involve $v_g,$ say ${\psi }_{q-1}^{t_1},\dots ,{\psi }_{q-1}^{t_r},$ with $A\cap \{t_1,\dots ,t_r\}=\varnothing ,$ so that it is not possible to find a value for $v_g$ that satisfies these edits simultaneously, given the values of the other variables. Clearly, this could only happen if $F_g^{t_1}\cup \cdots \cup F_g^{t_r}=D_g,$ since otherwise any value for $v_g$ outside $F_g^{t_1}\cup \cdots \cup F_g^{t_r}$ would work. We may assume without loss of generality that $T^{\prime }=\{t_1,\dots ,t_r\}$ is a minimal set having this property. Furthermore, it must hold in this case that for all variables involved in ${\Psi }_q,$ the original value of $v_j$ is contained in all sets $F_j^{t_1},\dots ,F_j^{t_r}.$ In other words, $T^{\prime }$ must satisfy properties (2.8) and (2.9). This means that $T^{\prime }$ would generate an implied edit in ${\Psi }_q$ which, by the fundamental property given at the end of Section 2.3, must be failed by the original values of the remaining variables. However, this would contradict the assumption that $A$ is a representing set of $A_q^k$ for all ${\psi }_q^k\in {\Psi }_q^{(2)}.$ This completes the proof of Lemma 2.

The proof of Theorem 2 is now completely analogous to that of Theorem 1, with Lemma 2 taking the role of Lemma 1.

References

Bankier, M., Lachance, M. and Poirier, P. (2000). 2001 Canadian Census Minimum Change Donor Imputation Methodology. Working Paper, UN/ECE Work Session on Statistical Data Editing, Cardiff.

Bankier, M., and Crowe, S. (2009). Enhancements to the 2011 Canadian Census E&I System. Working Paper, UN/ECE Work Session on Statistical Data Editing, Neuchâtel.

Boskovitz, A., Goré, R. and Wong, P. (2005). Data Editing and Logic. Working Paper, UN/ECE Work Session on Statistical Data Editing, Ottawa.

Bruni, R. (2004). Discrete models for data imputation. Discrete Applied Mathematics, 144, 59-69.

Bruni, R. (2005). Error correction for massive datasets. Optimization Methods and Software, 20, 297-316.

Casado Valero, C., Del Castillo Cuervo-Arango, F., Mateo Ayerra, J. and De Santos Ballesteros, A. (1996). Quantitative Data Editing: Quadratic Programming Method. Presented at the COMPSTAT 1996 Conference, Barcelona.

De Jonge, E., and Van der Loo, M. (2011). Manipulation of Linear Edits and Error Localization with the Editrules Package. Discussion Paper 201120, Statistics Netherlands, The Hague.

De Waal, T. (2003a). Solving the error localization problem by means of vertex generation. Survey Methodology, 29, 1, 71-79.

De Waal, T. (2003b). Processing of Erroneous and Unsafe Data. PhD Thesis, Erasmus University, Rotterdam.

De Waal, T. (2005). SLICE 1.5: a Software Framework for Automatic Edit and Imputation. Working Paper, UN/ECE Work Session on Statistical Data Editing, Ottawa.

De Waal, T., Pannekoek, J. and Scholtus, S. (2011). Handbook of Statistical Data Editing and Imputation. New Jersey: John Wiley & Sons, Inc.

De Waal, T., and Quere, R. (2003). A fast and simple algorithm for automatic editing of mixed data. Journal of Official Statistics, 19, 383-402.

Fellegi, I.P., and Holt, D. (1976). A systematic approach to automatic edit and imputation. Journal of the American Statistical Association, 71, 17-35.

Garfinkel, R.S., Kunnathur, A.S. and Liepins, G.E. (1986). Optimal imputation of erroneous data: Categorical data, general edits. Operations Research, 34, 744-751.

Garfinkel, R.S., Kunnathur, A.S. and Liepins, G.E. (1988). Error localization for erroneous data: Continuous data, linear constraints. SIAM Journal on Scientific and Statistical Computing, 9, 922-931.

Hedlin, D. (2003). Score functions to reduce business survey editing at the U.K. Office for National Statistics. Journal of Official Statistics, 19, 177-199.

Kovar, J., and Whitridge, P. (1990). Generalized edit and imputation system; Overview and applications. Revista Brasileira de Estadistica, 51, 85-100.

Little, R.J.A., and Smith, P.J. (1987). Editing and imputation of quantitative survey data. Journal of the American Statistical Association, 82, 58-68.

Magnus, J.R., Van Tongeren, J.W. and De Vos, A.F. (2000). National accounts estimation using indicator ratios. Review of Income and Wealth, 46, 329-350.

Mirsky, L. (1971). Transversal Theory. New York: Academic Press, Inc.

Nemhauser, G.L., and Wolsey, L.A. (1988). Integer and Combinatorial Optimization. New York: John Wiley & Sons, Inc.

Pannekoek, J., and De Waal, T. (2005). Automatic edit and imputation for business surveys: The Dutch contribution to the EUREDIT project. Journal of Official Statistics, 21, 257-286.

Ragsdale, C.T., and McKeown, P.G. (1996). On solving the continuous data editing problem. Computers & Operations Research, 23, 263-273.

Riera-Ledesma, J., and Salazar-González, J.J. (2003). New Algorithms for the Editing and Imputation Problem. Working Paper, UN/ECE Work Session on Statistical Data Editing, Madrid.

Sande, G. (1978). An Algorithm for the Fields to Impute Problems of Numerical and Coded Data. Technical Report, Statistics Canada.

Schaffer, J. (1987). Procedure for solving the data-editing problem with both continuous and discrete data types. Naval Research Logistics, 34, 879-890.

Scholtus, S. (2011). Automatic Editing with Soft Edits. Discussion Paper 201130, Statistics Netherlands, The Hague.

Schrijver, A. (1986). Theory of Linear and Integer Programming. New York: John Wiley & Sons, Inc.

Todaro, T.A. (1999). Overview and Evaluation of the AGGIES Automated Edit and Imputation System. Working Paper, UN/ECE Work Session on Statistical Data Editing, Rome.

Van der Loo, M., and De Jonge, E. (2011). Manipulation of Categorical Data Edits and Error Localization with the Editrules Package. Discussion Paper 201129, Statistics Netherlands, The Hague.

Williams, H.P. (1986). Fourier's method of linear programming and its dual. The American Mathematical Monthly, 93, 681-695.

Winkler, W.E. (1995). Editing Discrete Data. Working Paper, UN/ECE Work Session on Statistical Data Editing, Athens.

Previous