Une généralisation du paradigme de Fellegi-Holt pour la localisation automatique des erreurs 8. ConclusionUne généralisation du paradigme de Fellegi-Holt pour la localisation automatique des erreurs 8. Conclusion

• Précédent
• Suivant

Le présent article propose une nouvelle formulation du problème de localisation des erreurs dans le contexte de la vérification automatique. On suggère de trouver le nombre minimal (pondéré) d’opérations de vérification nécessaires pour assurer la cohérence d’un enregistrement observé avec les règles de vérification. Le nouveau problème de localisation des erreurs peut être considéré comme une généralisation du problème proposé dans l’article fondamental de Fellegi et Holt (1976), parce que l’opération qui impute une nouvelle valeur à une seule variable à la fois constitue un important cas particulier d’une opération de vérification.

L’objectif principal était de mettre au point la théorie mathématique sur laquelle repose le nouveau problème de localisation des erreurs. Il ressort que l’élimination FM, une technique utilisée par le passé pour résoudre le problème de localisation des erreurs fondé sur le paradigme de Fellegi-Holt, peut aussi être appliquée dans le contexte du nouveau problème (voir la section 5). Néanmoins, la résolution du problème de localisation des erreurs demeure une tâche difficile du point de vue du calcul, du moins pour les quantités de variables, de règles de vérification et d’opérations de vérification qui entrent en jeu dans les applications pratiques au sein des instituts de statistique. Un algorithme de localisation des erreurs possible est proposé à la section 6. D’autres algorithmes plus efficients pourraient et devraient probablement être mis au point. Comme pour l’élimination FM, il pourrait être possible d’adapter d’autres idées mises en œuvre pour résoudre le problème fondé sur le paradigme de Fellegi-Holt au problème général étudié ici.

Le présent article ne porte que sur les données numériques et les règles de vérification linéaires. Le paradigme original de Fellegi-Holt a aussi été appliqué à des données catégoriques et mixtes. Plusieurs auteurs, dont Bruni (2004) et de Jonge et van der Loo (2014), ont montré qu’une grande catégorie de règles de vérification s’appliquant à des données mixtes peuvent être reformulées en fonction de données numériques et de règles de vérification linéaires, sous réserve de la restriction supplémentaire que certaines variables doivent avoir une valeur entière. En principe, cela signifie que les résultats présentés dans l’article pourraient aussi s’appliquer à des données mixtes. Pour tenir compte du fait que certaines variables ont une valeur entière, on pourrait utiliser l’élargissement de l’élimination FM aux nombres entiers proposé par Pugh (1992); voir aussi de Waal et coll. (2011) pour en savoir davantage à propos de cette technique d’élimination élargie dans le contexte de la localisation des erreurs fondée sur le paradigme de Fellegi-Holt. Il reste à déterminer si les calculs nécessaires en vertu de cette approche sont réalisables.

La remarque n° 4 de la section 4 laisse entrevoir une analogie entre la localisation des erreurs dans les microdonnées statistiques et le domaine de l’appariement approximatif de chaînes. Dans l’appariement approximatif de chaînes, des chaînes de caractères sont comparées en vertu de l’hypothèse qu’elles pourraient avoir été partiellement corrompues (Navarro 2001). Diverses fonctions de distance ont été proposées pour cette tâche. La distance de Hamming, qui correspond au nombre de positions où deux chaînes diffèrent, peut être considérée comme analogue à la fonction cible fondée sur le paradigme de Fellegi-Holt (2.2). Le problème généralisé de localisation des erreurs défini dans le présent article peut quant à lui être considéré comme la contrepartie de l’utilisation de la distance de Levenshtein, ou « distance d’édition », pour l’appariement approximatif de chaînes. Il pourrait être intéressant d’explorer plus avant cette analogie. Plus particulièrement, des algorithmes efficients ont été mis au point pour calculer les distances d’édition entre deux chaînes; il pourrait être possible d’appliquer certaines idées sous-jacentes au problème généralisé de localisation des erreurs.

Le nouvel algorithme de localisation des erreurs a été appliqué avec succès à un petit ensemble synthétique de données (section 7). Globalement, les résultats de l’étude par simulations indiquent que la nouvelle méthode de localisation des erreurs pourrait améliorer considérablement la qualité de la vérification automatique par rapport à la méthode actuellement mise en œuvre. Il faut toutefois disposer d’information suffisante pour déterminer toutes $–$ ou à tout le moins la majorité $–$ des opérations de vérification pertinentes pour une application particulière. Les gains possibles en termes de qualité de la localisation des erreurs doivent aussi être pondérés dans la pratique par rapport aux exigences supérieures de calcul du problème généralisé de localisation des erreurs.

Les SSE constituent un candidat parfait pour l’application de cette nouvelle méthode dans la pratique. Toutefois, des recherches plus poussées sont nécessaires avant que la méthode puisse être utilisée dans un contexte de production courante. Pour appliquer la méthode dans un contexte particulier, il faut d’abord préciser les opérations de vérification pertinentes. Idéalement, chaque opération de vérification doit correspondre à une combinaison de modifications aux données que les vérificateurs humains considèrent comme une correction d’une erreur en particulier. De plus, un ensemble approprié de poids $w_g$ doit être déterminé pour ces opérations de vérification. Pour ce faire, il faut disposer d’information sur les fréquences relatives des types de modification les plus courants durant la vérification manuelle. Ces deux aspects pourraient être déterminés à partir des données historiques avant et après la vérification manuelle, des instructions de vérification et des autres sources de référence utilisées par les vérificateurs, ainsi qu’à partir d’entrevues avec des vérificateurs et des superviseurs des opérations de vérification.

Sur un plan plus fondamental, il faut encore répondre à la question de la démarcation entre les méthodes de correction déductives et la vérification automatique en vertu du nouveau problème de localisation des erreurs. En principe, bon nombre de types d’erreur connus pourraient être résolus soit par des règles de correction automatique, soit par la localisation des erreurs au moyen d’opérations de vérification. Chaque méthode présente ses propres avantages et inconvénients (Scholtus 2014). Il est probable qu’un compromis entre les deux donnera les meilleurs résultats, certaines erreurs étant traitées de façon déductive et d’autres, au moyen d’opérations de vérification. La meilleure façon d’établir un tel compromis dans la pratique demeure toutefois difficile à déterminer.

En fin de compte, la nouvelle méthode proposée dans l’article vise à accroître l’utilité de la vérification automatique dans la pratique. Les résultats obtenus à ce jour sont prometteurs.

Remerciements

Les opinions exprimées dans le présent article sont celles de l’auteur et ne reflètent pas forcément les politiques de Statistics Netherlands. L’auteur tient à remercier Jeroen Pannekoek, Ton de Waal et Mark van der Loo pour leurs commentaires à propos des premières versions de l’article, ainsi que le rédacteur en chef adjoint et deux évaluateurs anonymes.

Annexe

Élimination de Fourier-Motzkin

Soit un système de contraintes linéaires (2.1) et $x_f,$ la variable à éliminer. Supposons d’abord que $x_f$ ne participe qu’à des inégalités. Pour faciliter l’explication, supposons que les règles de vérification sont normalisées de sorte que toutes les inégalités utilisent l’opérateur $\ge .$ La méthode d’élimination FM considère toutes les paires $\left(r,s\right)$ d’inégalités pour lesquelles les coefficients de $x_f$ ont des signes opposés, c’est-à-dire $a_{rf}{a}_{sf}<0.$ Supposons, sans perte de généralité, que $a_{rf}<0$ et $a_{sf}>0.$ À partir de la paire originale de règles de vérification, on dérive la contrainte implicite suivante :

$${\displaystyle \sum _{j=1}^p{a}_j^{*}{x}_j+b^{*}\ge 0},(\text{A}\text{.1})$$

où $a_j^{*}=a_{sf}{a}_{rj}-a_{rf}{a}_{sj}$ et $b^{*}=a_{sf}{b}_r-a_{rf}{b}_s.$ Soulignons que $a_f^{*}=0,$ de sorte que $x_f$ ne participe pas à (A.1). Une inégalité de la forme (A.1) est dérivée de chacune des paires $\left(r,s\right)$ susmentionnées. La totalité du système de contraintes résultant de l’élimination FM est maintenant composée de ces contraintes dérivées, ainsi que de toutes les contraintes originales dans lesquelles $x_f$ n’intervient pas.

S’il y a des égalités linéaires où intervient $x_f,$ on pourrait appliquer la technique ci-dessus après avoir remplacé chaque égalité linéaire par deux inégalités linéaires équivalentes. de Waal et Quere (2003) ont proposé une autre solution plus efficiente pour ce cas. Supposons que la $r^{\text{e}}$ contrainte en (2.1) soit une égalité dans laquelle intervient $x_f.$ On peut réécrire cette contrainte comme suit :

$$x_f=\frac{-1}{a_{rf}}\left(b_r+{\displaystyle {\sum }_{j\ne f}{a}_{rj}{x}_j}\right).(\text{A}\text{.2})$$

En remplaçant $x_f$ par le terme de droite de l’équation (A.2) pour toutes les autres contraintes, on obtient de nouveau un système implicite de contraintes dans lesquelles $x_f$ n’intervient pas et qui peuvent être réécrites comme en (2.1).

Pour consulter une preuve que l’élimination FM possède la propriété fondamentale énoncée à la section 2, voir entre autres de Waal et coll. (2011, pages 69-70).

Bibliographie

Agrawal, R., et Srikant, R. (1994). Fast Algorithms for Mining Association Rules. Rapport technique, IBM Almaden Research Center, San José, Californie.

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

Chen, B., Thibaudeau, Y. et Winkler, W.E. (2003). A Comparison Study of ACS If-Then-Else, NIM, DISCRETE Edit and Imputation Systems Using ACS Data. Document de travail N^o 7, UN/ECE Work Session on Statistical Data Editing, Madrid.

de Jonge, E., et van der Loo, M. (2014). Error Localization as a Mixed Integer Problem with the Editrules Package. Document de discussion 2014-07, Statistics Netherlands, La Haye. Disponible au : http://www.cbs.nl.

de Waal, T. (2003). Résolution du problème de localisation des erreurs par la génération de sommets. Techniques d’enquête, 29, 1, 81-90.

de Waal, T., et Coutinho, W. (2005). Automatic editing for business surveys: An assessment for selected algorithms. Revue Internationale de Statistique, 73, 73-102.

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

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

EDIMBUS (2007). Recommended Practices for Editing and Imputation in Cross-Sectional Business Surveys. Manuel préparé par ISTAT, Statistics Netherlands, et SFSO.

Fellegi, I.P., et 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. et Liepins, G.E. (1988). Error localization for erroneous data: Continuous data, linear constraints. SIAM Journal on Scientific and Statistical Computing, 9, 922-931.

Ghosh-Dastidar, B., et Schafer, J.L. (2006). Outlier detection and editing procedures for continuous multivariate data. Journal of Official Statistics, 22, 487-506.

Giles, P. (1988). A model for generalized edit and imputation of survey data. The Canadian Journal of Statistics, 16, 57-73.

Granquist, L. (1995). Improving the traditional editing process. Dans Business Survey Methods, (Éds., B.G. Cox, D.A. Binder, B.N. Chinnappa, A. Christianson, M.J. Colledge et P.S. Kott), John Wiley & Sons, Inc., 385-401.

Granquist, L. (1997). The new view on editing. Revue Internationale de Statistique, 65, 381-387.

Granquist, L., et Kovar, J. (1997). Editing of survey data: How much is enough? Dans Survey Measurement and Process Quality, (Éds., L.E. Lyberg, P. Biemer, M. Collins, E.D. de Leeuw, C. Dippo, N. Schwartz et D. Trewin), John Wiley & Sons, Inc., 415-435.

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.

Hidiroglou, M.A., et Berthelot, J.-M. (1986). Contrôle statistique et imputation dans les enquêtes-entreprises périodiques. Techniques d’enquête, 12, 1, 79-89.

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

Kruskal, J.B. (1983). An overview of sequence comparison. Dans Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, (Éds., D. Sankoff et J.B. Kruskal), Addison-Wesley, 1-44.

Lawrence, D., et McKenzie, R. (2000). The general application of significance editing. Journal of Official Statistics, 16, 243-253.

Liepins, G.E. (1980). A Rigorous, Systematic Approach to Automatic Data Editing and its Statistical Basis. Rapport ORNL/TM-7126, Oak Ridge National Laboratory.

Liepins, G.E., Garfinkel, R.S. et Kunnathur, A.S. (1982). Error localization for erroneous data: A survey. TIMS/Studies in the Management Sciences, 19, 205-219.

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

Naus, J.I., Johnson, T.G. et Montalvo, R. (1972). A probabilistic model for identifying errors in data editing. Journal of the American Statistical Association, 67, 943-950.

Navarro, G. (2001). A guided tour to approximate string matching. ACM Computing Surveys, 33, 31-88.

Pannekoek, J., Scholtus, S. et van der Loo, M. (2013). Automated and manual data editing: A view on process design and methodology. Journal of Official Statistics, 29, 511-537.

Pugh, W. (1992). The omega test: A fast and practical integer programming algorithm for data dependence analysis. Communications of the ACM, 35, 102-114.

R Development Core Team (2015). R: A Language and Environment for Statistical Computing. Vienne, Autriche : R Foundation for Statistical Computing. URL: http://www.R-project.org/.

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

Riera-Ledesma, J., et Salazar-González, J.J. (2003). New Algorithms for the Editing and Imputation Problem. Document de travail N^o 5, UN/ECE Work Session on Statistical Data Editing, Madrid.

Riera-Ledesma, J., et Salazar-González, J.J. (2007). A branch-and-cut algorithm for the continuous error localization problem in data cleaning. Computers & Operations Research, 34, 2790-2804.

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). Algorithms for correcting sign errors and rounding errors in business survey data. Journal of Official Statistics, 27, 467-490.

Scholtus, S. (2014). Error Localisation using General Edit Operations. Document de discussion 2014-14, Statistics Netherlands, La Haye. Disponible au : http://www.cbs.nl.

Tempelman, D.C.G. (2007). Imputation of Restricted Data. Thèse de doctorat, University of Groningen. Disponible au : http://www.cbs.nl.

van der Loo, M., et de Jonge, E. (2012). Automatic Data Editing with Open Source R. Document de travail N^o 33, UN/ECE Work Session on Statistical Data Editing, Oslo.

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

• Précédent
• Suivant