Une généralisation du paradigme de Fellegi-Holt pour la localisation automatique des erreurs 2. Contexte et travaux connexesUne généralisation du paradigme de Fellegi-Holt pour la localisation automatique des erreurs 2. Contexte et travaux connexes

• Précédent
• Suivant

Soit $x=\left(x_1, \dots , x_p\right)\prime \in {ℝ}^p$ un enregistrement de $p$ variables numériques. Supposons que cet enregistrement doive satisfaire à $k$ règles de vérification, se présentant sous la forme du système d’(in)égalités linéaires suivant :

$$Ax+b\odot 0,(2.1)$$

où $A=\left(a_{rj}\right)$ est une matrice $k\times p$ de coefficients et $b=\left(b_1, \dots , b_k\right)\prime$ est un vecteur de constantes. Ici comme ailleurs, $0$ représente un vecteur de zéros de longueur appropriée; de même, $\odot$ représente un vecteur symbolique d’opérateurs de l’ensemble $\left\{\ge ,\le ,=\right\}.$

Pour un enregistrement donné $x$ qui ne satisfait pas à toutes les règles de vérification énoncées en (2.1), le problème de localisation des erreurs fondée sur le paradigme de Fellegi-Holt consiste à trouver la valeur minimale de

$${\displaystyle \sum _{j=1}^p{w}_j{\delta }_j},(2.2)$$

où $w_j>0$ est le poids de confiance de la variable $x_j$ et ${\delta }_j\in \left\{0,1\right\},$ à condition qu’on puisse assurer la cohérence de l’enregistrement original avec les règles de vérification en imputant uniquement les variables $x_j$ pour lesquelles ${\delta }_j=1$ (de Waal et coll. 2011, page 66).

Fellegi et Holt (1976) ont aussi proposé une méthode de résolution du problème de localisation des erreurs ci-dessus fondée sur la production d’un ensemble suffisant de vérifications implicites (voir ci-dessous). Malheureusement, cette méthode exige souvent un très grand nombre de vérifications implicites. Au cours des dernières décennies, divers algorithmes spécialisés ont été élaborés pour le problème de localisation des erreurs, notamment par Schaffer (1987), Garfinkel, Kunnathur et Liepins (1988), Kovar et Whitridge (1990), Ragsdale et McKeown (1996), de Waal (2003), de Waal et Quere (2003), Riera-Ledesma et Salazar-González (2003, 2007), Bruni (2004), ainsi que de Jonge et van der Loo (2014). Les premiers algorithmes visaient principalement à renforcer la méthode originale de Fellegi et Holt (1976) en réduisant le nombre de vérifications implicites requises. Les algorithmes plus récents reposent sur le fait que le problème de localisation des erreurs peut être rédigé sous forme de problème de programmation mixte en nombres entiers, ce qui permet l’application de techniques d’optimisation normalisées. Voir aussi de Waal et Coutinho (2005) ou de Waal et coll. (2011) pour une vue d’ensemble et une comparaison des divers algorithmes de localisation des erreurs.

Les vérifications implicites sont des contraintes qui découlent logiquement des règles de vérification originales (2.1). Dans le contexte qui nous occupe (données numériques, vérifications linéaires), toutes les vérifications implicites pertinentes peuvent être générées par une technique appelée élimination de Fourier-Motzkin (élimination FM; voir Williams 1986). L’élimination FM transforme un système de contraintes linéaires à $p$ variables en un système de contraintes linéaires implicites à au plus $p-1$ variables; ainsi, au moins une des variables originales est éliminée. Pour les détails mathématiques, consultez l’annexe.

L’élimination FM est assortie de la propriété fondamentale suivante : le système de contraintes implicites est satisfait par les valeurs des variables non éliminées si et seulement s’il existe une valeur pour la variable éliminée qui, prise avec les autres valeurs, satisfait au système original de contraintes. Dans la localisation des erreurs en vertu du paradigme de Fellegi-Holt, on peut, en appliquant à répétition cette propriété fondamentale, vérifier si une combinaison particulière de variables peut être imputée pour obtenir un enregistrement cohérent, compte tenu des valeurs originales des autres variables. L’algorithme de localisation des erreurs de de Waal et Quere (2003) illustre bien cette utilisation de l’élimination FM.

Pour conclure cette section, il est intéressant d’examiner brièvement l’interprétation statistique du problème de localisation des erreurs. En fait, Fellegi et Holt (1976) n’ont fourni aucun argument statistique formel pour expliquer leur paradigme de localisation automatique des erreurs. Leur raisonnement était plutôt intuitif :

• « Les données de chaque enregistrement doivent être corrigées afin de satisfaire à toutes les règles de vérification en changeant le moins d’éléments de données (champs) possible. Nous sommes d’avis que cette méthode respecte l’idée de garder telles quelles le plus grand nombre possible des données originales, compte tenu des contraintes des règles de vérification, et donc de modifier le moins de données possible. Parallèlement, si les erreurs sont relativement rares, il semble plus probable que l’on puisse identifier les champs réellement erronés. » (Fellegi et Holt 1976, page 18). [Traduction]

Liepins (1980) ainsi que Liepins, Garfinkel et Kunnathur (1982), en se fondant sur les résultats antérieurs de Naus, Johnson et Montalvo (1972), ont formulé un argument statistique pour minimiser le nombre pondéré de variables imputées. Supposons que les erreurs se produisent selon un processus stochastique, chaque variable $x_j$ étant erronée selon une probabilité $p_j$ qui ne dépend pas de sa valeur réelle et les erreurs étant indépendantes d’une variable à l’autre. Supposons en outre que les poids de confiance sont définis comme suit :

$$w_j=-\log \left(\frac{p_j}{1-p_j}\right).(2.3)$$

On peut alors montrer que la minimisation de l’expression (2.2) correspond approximativement à la maximisation de la vraisemblance de l’enregistrement exempt d’erreur non observé. Soulignons que ces auteurs supposent tacitement qu’une erreur affecte toujours une seule variable à la fois.

D’autres méthodes de localisation des erreurs reposant plus directement sur des modèles statistiques ont été proposées, notamment par Little et Smith (1987) et par Ghosh-Dastidar et Schafer (2006). Ces méthodes ont recours à des techniques de détection des valeurs aberrantes et exigent un modèle explicite pour les données réelles. Malheureusement, elles ne peuvent pas tenir compte de façon directe des règles de vérification comme celle qui est illustrée en (2.1).

• Précédent
• Suivant