[2011 08]Astrath Une Methode de purification de la liste électorale

Méthode de purification de la liste des
électeurs.

1. Problématique
1.1.

Présentation des données

Nous disposons essentiellement de deux bases de données, la base des CIN qu’on nommera 1 et la base du
registre des décès qu’on nommera 2
Les entrées de 1
ID

N°CIN

Prénom

26787 02412581

‫ف‬

‫إ‬

Nom

‫ـ ي‬

‫ا‬

Date de
naissance

Prénom du
père

05.02.1982

‫ا ـ دي‬

Prénom de
la mère

‫ز ـ‬

Date d’émission

08.09.2004

Et d’autres données moins pertinentes comme l’adresse.
Les entrées de 2
ID

Prénom

78431

‫ف‬

‫إ‬

Nom

‫ـ ي‬

‫ا‬

Date de naissance

Prénom du père

05.02.1982

‫ا ـ دي‬

Prénom de la
mère

‫ز ـ‬

Date du décès

11.05.2009

Les données de la date de naissance et de décès sont peu fiables dans 2

1.2.

L’objectif

Nous nous proposons de purifier la base de données des CIN pour construire une nouvelle base contenant la liste
des électeurs. L’opération doit :
•
•
•
•
•

Eliminer les doublons
Eliminer les personnes décédées selon le registre des décès.
Eviter au maximum les fausses détections (mauvaise reconnaissance d’une personne de 1 dans 2)
Maximiser la reconnaissance des entrées invalides dans 1
A priori il y a environ 4 millions entrées dans 2 à vérifier. Il faut donc que chaque itération dure un
maximum de 100
pour un temps de calcul total de 4,6
.

Astrath | 19.08.2011 | Une méthode de la purification des listes des électeurs |

1

2. Procédure
2.1.

Eliminer les doublons

Sur la base de comparaison de la date de naissance, puis le prénom, puis le nom. La classification de la base de
données selon ces critères selon cet ordre devrait permettre l’exécution de cette tâche en
+ O(N.logN)

2.2.

Le traitement des données invalides

Le but est de vérifier pour chaque
dans 1, s’il existe
considéré comme entrée invalide de 1 et sera donc éliminé.

dans 2 tel que

~

. S’il en existe un,

sera

Plus l’on est tolérant avec l’équivalence, plus on risque de reconnaître des correspondances entre 1 et 2 mais
plus on augmente la probabilité de fausse détection.
Le but est d’estimer le seuil de décision qui nous donne une probabilité de fausse détection quasi-nulle.
Discussion de la méthode actuelle : Soundex
Il s’agit d’une méthode clairement inappropriée avec notre cas. Soundex est une méthode qui compare des
chaines contenant des mots arabes écrites avec l’alphabet latin. Il est évident que soundex se doit donc d’intégrer un
outil de construction grammaticale lui permettant de prendre la décision selon sa modélisation de cette grammaire.
En effet, Soundex aurait été utile si la base de données n’était pas arabisée. Il aurait pu identifié dans ce cas la
similitude entre
et
, mais il s’avère aussi qu’il peut générer de fausses détections de
correspondance s’il s’agit de deux noms de familles différents :
‫ هـ‬/
‫ـ‬
En effet, le codage phonétique Soundex est insensible aux voyelles. Et déjà qu’il part avec le handicape de
l’erreur de la translitération (le H qui peut désigner la lettre «‫ » هـ‬ou « ‫» ح‬, il s’avère qu’il est très réducteur (il code
l’alphabet arabe qui comporte plus de 70 phonèmes (8bits) sur 3bits ce qui représente une erreur de modélisation
énorme que l’on ne peut se permettre car elle va générer énormément de mauvaises détections de correspondance.
La distance de Damerau-Levenshtein
Pour comparer deux chaînes, on calcule la distance de Damerau-Levenshtein qui représente le nombre minimum
d'opérations nécessaires pour transformer la première chaîne à la deuxième.
int DamerauLevenshteinDistance(char str1[1..lenStr1], char str2[1..lenStr2])
declare int d[0..lenStr1, 0..lenStr2]
declare int i, j, cost
//initialisation
for i from 0 to lenStr1
for j from 0 to lenStr2

d[i, 0] := i
d[0, j] := j

for i from 1 to lenStr1
for j from 1 to lenStr2
if str1[i] = str2[j] then cost := 0
else cost := 1
d[i, j] := minimum(
d[i-1, j ] + 1,
// suppression
d[i , j-1] + 1,
// insertion
d[i-1, j-1] + cost
// substitution
)
if(i > 1 and j > 1 and str1[i] = str2[j-1] and str1[i-1] = str2[j]) then
d[i, j] := minimum( d[i, j], d[i-2, j-2] + cost ) // transposition
return d[lenStr1, lenStr2]

Astrath | 19.08.2011 | Une méthode de la purification des listes des électeurs | Procédure

2

Prise de décision
,

On exprime la ressemblance entre les deux chaines par

!"# $%&'(

,%&'(

) *

Dans la prise de décision on compare 1. , et 2. , - . si la ressemblance entre les deux chaines est
supérieure à un seuil ./01'&2 que l’on fixera élevé au début pour minimiser les fausse détections (80% par exemple),
on compare les noms de famille, puis si les deux noms de familles sont semblables (à un seuil moins important, 70%
par exemple), on teste le prénom du père (seuil à 80%), puis le prénom de la mère (seuil à 80%). Si les
ressemblances est supérieure au seuil, on pourra considérer que les deux entrée 1 et 2 sont identiques1
Itérations
Etant donné que l’interaction entre les deux bases de données est 2 3 1 il est possible de diviser la liste 1
en sous-listes 14 afin de distribuer la tâche en fournissant à chaque machine 54 les listes 14 et les 2.
Il est préférable de classer la base 2 par prénom.
Il serait utile pour des raisons de contrôle humain de quantifier la probabilité qu’une entrée
6 1 puisse
6 2. Ceci se fait en associant un barème pour chaque test de ressemblance effectué
avoir une correspondance
lors des itérations.
On notera la probabilité de vraissemblance d’une entrée
7

,

à une entrée

par

∑: 9: .; <=,: ,<>,:
∑: 9:

(1)

Je propose le barème suivant :
?

$1, 3, 5, 9*

(2)

Le choix s’explique par le fait que les premiers coefficients sont disqualifiant, mais peu discriminatoire. On peut
facilement avoir deux prénoms différents. Mais une fois identique, on peut un peu plus difficilement avoir le même
nom de famille, si cette condition est satisfaite, on discriminera selon le prénom du père. Dans le calcul de
vraisemblance, il est plus pertinent de considérer les effets discriminatoires.
La probabilité de qu’une entrée

6 1 puisse avoir une correspondance
C

| 2

max 7

H: 6I

6 2 s’exprime donc

, J4

On créera ainsi une colonne supplémentaire de métadonnées contenant la probabilité qu’une entrée de la table
des CIN puisse correspondre à une personne décédée selon le registre des décès. Ces données peuvent s’avérer
utiles ultérieurement, notamment lors du check up manuel pour les valeurs limites.

2.3.

Vitesse de calcul

Elle est proportionnelle au nombre de machines participant au calcul. La complexité des itérations est de
1 K 2 ce qui reste considérable mais la simplicité de la factorisation permet de dépasser facilement ce
problème.

1

Le programme se chargera de logger toutes les interventions qui ont mené à la suppression d’une entrée de 1

Astrath | 19.08.2011 | Une méthode de la purification des listes des électeurs | Procédure

3

3. Affinement du la méthode
Il serait judicieux de tester le programme avant le déployer sur un échantillon de 1 pour déterminer les seuils
permettant d’améliorer la prise de décisions (des seuils trop hauts vont causer des non-détections, des seuils trop
bas causeront des fausses détections). Le seuil doit être calibré juste au dessus de la valeur qui permet l’apparition
de la première erreur de reconnaissance de correspondances d’entrées.
La valeur limite théorique de la probabilité C pour une entrée sans correspondant dans 2 en utilisant le
barème donné dans (2) est celle correspondante au cas d’une entrée qui a été discriminée à cause du nom de la
mère.
CLMN

α P ? P ?Q P ?R .R
α P ? P ?Q P ?R

1S

1 S SR ?R
α P ? P ?Q P ?R

1 P 3 P 5 P 7.2
1P3P5P9

90%

La borne inférieure d’un cas à la limite de détection est de
C"#W

α S P ? . P ?Q .Q P ?R .R
α P ? P ?Q P ?R

0.8 P 2.1 P 4.0 P 7.2
1P3P5P9

78.3%

Cette bande de probabilité $CY'Z , C[\/ * est à vérifier manuellement. Toute entrée ayant pour valeur de
probabilité de correspondance dans cet intervalle est susceptible d’être un cas de non-détection. Baisser les seuils a
pour effet d’élargir cette bande des deux bornes.

Astrath | 19.08.2011 | Une méthode de la purification des listes des électeurs | Affinement du la
méthode

4