Identification d’adresses avec ElasticSearch

Raya Berova & Benoît Hurpeau (DMRG)

28 novembre 2024

Plan de la présentation

1️⃣ Contexte

2️⃣ Utilisation du référentiel Gaïa

3️⃣ Moteur de recherche ElasticSearch

4️⃣ Algorithme d’identification d’adresses

5️⃣ Performances de l’algorithme d’identification

6️⃣ Discussion

1️⃣ Introduction

Origine du projet

• Besoin d’un référentiel complet, stable, fiable, mis à jour.
• Faciliter la gestion des adresses au sein du SSP.
• Clients : Résil, Géoloc, DMTR…

Gaïa : Référentiel Géographique d’Adresses avec Informations Géolocalisantes.

Parler de l’origine du projet, quand ca a été mis en place, comment, pq…

Une adresse

20 bis avenue de la marne 92049

Géométrie de l’adresse

Exemple: “88 avenue verdier | 92049” reliée à sa parcelle

Le référentiel Gaïa

Autres données disponibles (aspect géométrique des objets) :

• Pour chaque adresse Gaïa : point gps, lien parcelle.
  
• Pour chaque commune Gaïa : polygone.

Identifiants Gaïa

Identifiant unique et stable pour assurer le suivi des objets dans le temps.

Trois niveaux :

• Identifiant adresse
• Identifiant voie
• Identifiant commune

Gestion des scissions et fusions de communes.

Construction du référentiel

Sources fiables :

• Majic : Mise à jour des informations cadastrales.
  
• BAN : Base Adresse Nationale.
  
• RCA : Référentiel Commun d’Adresses.

Au moins une mise à jour par trimestre (avec conservation des identifiants Gaïa).

Une mise à jour :

1. Récupérer la nouvelle base d’une source données.
   
2. Identifier les adresses textuellement :
   

• Les adresses qui sont retrouvées sont alors modifiées si des nouveautés apparaissent.
  
• Les adresses non retrouvées entraînent la création de nouveaux objets Gaïa.
  L’étape d’identification des adresses permet de ne pas écraser les identifiants Gaïa.
  

D’autres données

• Polygones du bâti.
  
• Polygones Parcelles du cadastre.
  
• Polygones QPV, zonages infra, iris.

Pas d’identifiant Gaïa, donc pas de suivi dans le temps de ces objets.

Exemples de géométries

Adresses, parcelles et bâtis :

Quelques métriques sur le référentiel

• Nombre d’adresses ≃ 27 millions.
  
• Nombre de voies ≃ 3 millions.

Plan de la présentation

1️⃣ Contexte

2️⃣ Utilisation du référentiel Gaïa

3️⃣ Moteur de recherche ElasticSearch

4️⃣ Algorithme d’identification d’adresses

5️⃣ Performances de l’algorithme d’identification

6️⃣ Discussion

2️⃣ Utilisation du référentiel Gaïa

Différents besoins au sein du SSP

• Résil :
  • Identification de(s) adresse(s) des individus.
    
  • Regroupement des adresses avec différents identifiants Gaïa mais qui représentent le même lieu.
• Géoloc : identification du référentiel Géoloc et génération de leur nouveau référentiel.
  
• Autres utilisateurs possibles :
  • Identification des adresses sur les certificats de décès.
    
  • Identification des adresses de Sirus.

Besoin d’identification des adresses textuelles

Trouver l’identifiant d’adresse à partir d’un libellé d’adresse plus ou moins correcte.

• Besoin visiblement récurrent au sein du SSP.
  
• Indispensable pour construire et mettre à jour le référentiel.

Il faut donc un moteur de recherche ⚙️.

Plan de la présentation

1️⃣ Contexte

2️⃣ Utilisation du référentiel Gaïa

3️⃣ Moteur de recherche ElasticSearch

4️⃣ Algorithme d’identification d’adresses

5️⃣ Performances de l’algorithme d’identification

6️⃣ Discussion

3️⃣ Moteur de recherche ElasticSearch

Adresses à retrouver dans Gaïa

Exemple d’adresses à retrouver :

Adresse à retrouver	COG	Code Postal	Libellé commune
131, rue du fbg Bannier		45000	Orléans
0033 ave J. Jaurès	92040

Adresses dans Gaïa :

Adresse	COG
131 rue du faubourg bannier	45234
33 avenue jean jaures	92040

C’est pourquoi il faut un moteur de recherche ⚙️.

Un moteur de recherche ⚙️

• Google : recherche par mot clé sur internet.
  
• Moteur de recherche de l’intranet de l’Insee.
  
• Pour la recherche d’adresse :
  • Google Maps.
  • Addok : moteur de recherche de la BAN.

• Quand on pense à moteur de recherche, on pense tout de suite à Google.

• Un moteur de recherche est un outil qui permet de retrouver des informations en effectuant des requêtes dans une base de données. On peut rechercher avec des mots-clés ou des textes similaires à ceux présents dans la base, grâce à des techniques de recherche approximative.

• Il y a des moteurs de recherche partout, par exemple intranet de l’insee, windows pour chercher des applications, l’explorateur de fichiers sur votre ordinateur en local…

• Un moteur ne sert pas qu’à chercher sur internet, c’est tout simplement de la recherche dans une base de données. Mais internet a permis des avancées majeures sur les moteurs, car la recherche sur le web devenait un sujet de plus en plus important. Avec le démultiplication de l’information, difficile de chercher dans une grande bdd et trouver le résultat le plus pertinent.

• Pour avoir le maximum de résultats pertients, il faut non seulement avoir un moteur performant, il faut aussi avoir les bonnes données. C’est en recrutant un étudiant du MIT qui a développé une méthode révolutionnaire pour recenser automatiquement les sites sur le web (auparavant fait manuellement), que google va se démarquer des autres moteurs.

• 1er moteur de recherche Archie 1990. Yahoo 1994, Google 1998, google maps 2004.

• Google maps : api payant, pas la main sur les données.
  

• Google Maps utilise des technologies avancées mais on peut reproduire la logique avec ElasticSearch.
  

• Addok : DINUM.
  

• On va regarder les avantages et les inconvients de d’elastic et d’addok dans la suite.
  

ElasticSearch

• Créé en 2010 par Shay Bannon.
  
• Faire des recherches rapides sur tout type de données.
  
• Moteur ⚙️ utilisable en n’importe quel langage de programmation (requêtes HTTP).

ElasticSearch au sein de l’Insee :

• Pour trier et chercher les recettes de cuisine de sa femme psq il trouvait pas de moteur de recherche adapté.

• 1er moteur Elasticsearch de l’insee : Code statistique Non Signifiant, identifier les individus à partir de ses données d’état civil.

• Résil : prolongement du moteur CSNS, améliorer la qualité du moteur CSNS, en utilisant les informations identifiantes supplémentaires disponibles dans Résil, notamment l’adresse de résidence et les cohabitants.
  

C’est quoi concrètement ElasticSearch ?

• ElasticSearch : logiciel pour l’indexation et la recherche de données.

• Utilisation en pratique avec Python : packages elasticsearch et elasticsearch-dsl.

Pourquoi ElasticSearch pour la recherche textuelle ?

Critères	ElasticSearch	SQL	Addok
Recherche de texte avancée	✅	❌	✅
Personnalisation des recherches	✅	❌	⚠️
Rapidité	✅	✅	✅
Précision	✅	❌	⚠️
Facilité d’implémentation	❌	✅	✅
Maintenance	⚠️	✅	❌

• Addok (DINUM) : code python pour indexer des données d’adresses avec point gps et recherche les adresses avec des requêtes fixées.
  
• Addok est un moteur de recherche open source conçu pour effectuer des tâches de géocodage. Il n’utilise pas Elasticsearch.
  

Étape 1 : pouvoir comparer l’adresse recherchée avec les données Gaïa.

Filtres

• Normaliser le texte pour la comparaison.
  
• Pour les données du référentiel ET pour les adresses recherchées.

Filtres implémentés

• Lowercase
  
• Asciifolding
  
• Ponctuation
  
• Séparation des nombres et lettres (ex : 1er → 1 er)
  
• Suppression des “0” devant les nombres (ex : 0033 → 33)
  
• Prise en compte des synonymes (ex : ave = avenue, st = saint)

Étape 2 : définir un score pour évaluer la pertinence.

Base de données classique

Exemple

idVoie	nom de voie
A	du general leclerc
B	du general charles de gaulle
C	du point du jour
D	verdier
E	des cours

Nous allons faire un focus sur uniquement le “nom de voie” pour simplifier la compréhension de la théorie du moteur.

Recherche par mot

Pour chaque nom de voie du référentiel, compter le nombre de mots qui sont retrouvés dans l’adresse recherchée : les matchs 🎯.

Exemple : score avec tokenizer “mot” de “45 avenue du general charles de gaulle”

idVoie	nom de voie	score
A	du general leclerc	2
B	du general charles de gaulle	5
C	du point du jour	2
D	verdier	0
E	des cours	0

• Un match c’est chercher si une sous chaine du nom de voie, ici un mot, est incluse dans l’adresse recherchée.
  
• Recherche par groupes de caractères également possible, abordée dans la suite.
  

Score avec tokenizer “mot”

Tokenizer = façon de découper le texte recherché et ciblé.

Pour retourner la voie la plus pertinente, on construit un score pour chaque voie : \[ score_{voie} = \sum_{\text{∀m} \in \text{M}} {nb\_occurrence}_m \]

m = mot.
M = ensemble des mots de l’adresse recherchée.

Dans une grande base de données, c’est extrêmement long.

Pour palier à ces temps de traitement qui explosent, on peut utiliser un nouvel outil qui permet de réorganiser nos bases de données : l’index inversé.

Étape 3 : utiliser un index inversé. Mais qu’est ce donc ?

Index inversé mot

Exemple

idVoie	nom de voie
A	du general leclerc
B	du general charles de gaulle
C	du point du jour
D	verdier
E	des cours

mot	occurrences
general	{“A”: 1, “B”: 1}
jour	{“C”: 1}
du	{“A”: 1, “B”: 1, “C”: 2}
cours	{“E”: 1}
…	…

Comptage direct ⚡ des occurrences de chaque mot de la base par idVoie.

• Faire un index inversé par mot, c’est récupérer tous les mots des noms de voie dans le référentiel et on les aplati dans une colonne.
  
• Il y a autant de lignes qu’il y a de mots différents dans les noms de voie du référentiel. Les mots les plus fréquents seront ceux qui ont le plus d’occurences.
  
• Nous obtenons directement le comptage de chaque mot par idVoie.
  
• L’index inversé est fait en amont des recherches.
  

Étape 4 : prendre en compte les variations textuelles.

Fuzziness

Contourner les petites fautes d’orthographes : fuzziness.

Pour matcher 🎯 deux mots avec une fuzziness de niveau 1 = corriger l’un des mots :

• Ajout d’une lettre. Ex: “verdiier”
  
• Suppression d’une lettre. Ex: “verdie”
  
• Remplacement d’une lettre. Ex: “verfier”
  
• Échanger deux lettres de place. Ex: “evrdier”

Il est possible de comparer deux textes, deux n-grams ou n’importe quel autre groupe de caractères.

La fuzziness n’est pas un tokenizer, une facon de decouper, c’est plutot une option qu’on rajoute pour matcher des sous chaine, peu importe le decoupage.

Une autre façon de découper : les n-grams

Prendre en compte les correspondances partielles : chaque mot est découpé en sous-chaînes de n caractères consécutifs.

Exemple de découpage en 3-grams de caractères du texte “avenue verdier” :
ave, ven, enu, nue, ver, erd, rdi, die, ier

Si un mot est inférieur à la taille n, il n’aura pas de découpage en n-grams → pas présent dans l’index inversé n-gram.

Index inversé 3-grams

Exemple

idVoie	nom de voie
A	du general leclerc
B	du general charles de gaulle
C	du point du jour
D	verdier
E	des cours

3-gram	occurrences
gen	{“A”: 1, “B”: 1}
cha	{“B”: 1}
our	{“C”: 1, “E”: 1}
oin	{“C”: 1}
…	…

• Il y a autant de lignes qu’il ya de trigrams différents dans les noms de voie du référentiel.
  
• Si un mot est inférieur à la taille n=3, il ne sera pas pris en compte. Par exemple : du général de gaules, “du” et “de” n’apparaîtront pas dans l’index et donc ne seront pas pris en compte dans les matchs trigrams.
  

Score avec tokenizer “n-grams”

Score pour chaque voie : \[ score_{voie} = \sum_{\text{∀ngram} \in \text{N}} {nb\_occurrence}_{ngram} \]

N = ensemble des n-grams de l’adresse recherchée.

Limites des n-grams

\[ \downarrow \text{taille n-grams} \Rightarrow \text{taille index inversé} \uparrow \Rightarrow \text{temps de recherche} \uparrow \]

• Limitation à n∈{3,4,5} pour notre cas.
  
• Tests effectués pour choisir ces valeurs, en fonction de la précision et la rapidité des requêtes.

Donc avec tous ces éléments, on peut commencer à construire un score de plus en plus efficient pour trouver la voie la plus pertiente.

Score global

Le score global va donc combiner la somme des matchs 🎯 au niveau :

• mot avec fuzziness.
  
• n-grams.
  
• mais également texte entier sans découpage !

Il est possible de donner plus ou moins d’importance à ces différents niveaux de matchs 🎯.

• On va chercher le nom de voie tel quel, sans découpage, au sein de l’adresse recherchée.

• C’est pourquoi on va introduire la notion de boost.
  

Boost 🚀

• Chaque occurrence est multipliée par un facteur, appelé boost 🚀, qui dépend du niveau de match 🎯.
  
• Personnalisation des boosts 🚀 pour être adapté aux données recherchées.

Avec tous ces outils la, on peut faire une recherche !

Faire des recherches 🔍

Requête 🔍 pour retrouver la voie :

À chaque match 🎯, le score va ⇡ en fonction du boost 🚀 associé.

Variable	Tokenizer	Fuzzi 1	Boost 🚀
Nom de voie	Mot	✅	15
Type de voie	Mot	✅	5
Nom de voie	3 à 5-grams	❌	1

Ex boost 200 : “3 rue du genral de gaulle” ⊃ “du general de gaulle”

• Requete gaia pour retrouver la voie.
  
• Ici, on introduit le type de voie qui n’a pas été vu précédement, pour ne pas compliquer la compréhension de la théorie du moteur, mais la logique reste la meme que pour le nom de voie.
  
• Attention, pas de fuzzi sur les ngrams car on juge que les sous chaines sont déjà assez petites, c’est contre productif pour la rapidité et la précision des recherches d’ajouter de la fuzzi.
  
• Il faut noter qu’on match à chaque sous-chaine, par exemple à chaque 3-grams de verdier dans 88 avenue verdier.
  
• Les ngrams c’est notre dernier recours, on va retourner comme voie plus pertinente les match sur nom de voie complet et sur token mais ngrams c’est notre roue de secours.
  

Retour sur le score global

\[ score_{voie} = \sum_{\text{∀n} \in \text{N}} \sum_{\text{∀t} \in \text{n}} boost_{n}*{nb\_occurrence}_{t} \]

N = ensemble des niveaux (niveau chaîne complète fuzzi, niveau mot fuzzi…).
n = niveau.
t = token, sous-chaîne (un mot, un 3-grams…).

• Formule mathématique du score pour retrouver la voie la plus pertiente dans Gaïa.

• Maintenant, on est capable de retrouver la voie la plus pertinente, mais qu’est ce qu’il en est de l’adresse ? Regardons l’algorithme d’identification d’adresse de Gaïa.
  

Plan de la présentation

1️⃣ Contexte

2️⃣ Utilisation du référentiel Gaïa

3️⃣ Moteur de recherche ElasticSearch

4️⃣ Algorithme d’identification d’adresses

5️⃣ Performances de l’algorithme d’identification

6️⃣ Discussion

4️⃣ Algorithme d’identification d’adresses

Algorithme d’identification d’adresses

• Prends en entrée un libellé d’adresse et un COG, ou à défaut, un code postal + libellé commune.
  
• Retourne :
  • le(s) identifiant(s) Gaïa retrouvé(s).
    
  • une indicatrice sur la qualité de l’identification (0 à 10).
    
  • un ratio qui mesure l’écart entre la 1ère et la 2ème voie la plus pertinente retournées par Elastic (0 à 1).

Schéma algorithme d’identification

• Entre chaque requête Elastic, il y a des étapes de validation du résultat ES qui sont font en aval.
  
• Identification adresse stricte : une recherche l’adresse comme un appariement direct avec notre référentiel Gaïa, tout en passant via le moteur ElasticSearch pour avoir les filtres et les synonymes montrés précédemment.
  
• En moyenne, sur une base de données d’adresses non normalisées, il y a 30% des adresses qui passent à la première étape de l’identification. Cette identification stricte permet donc d’accélerer le processus, car ca prend 6 fois moins de temps de faire une recherche stricte plutot qu’une recherhce floue.
  
• Comme les bases de données qui alimentent notre référentiel sont plutôt normalisées, cela accélère d’autant plus notre processus d’identification.
  
• ensuite voie floue puis simplement numéro et indice de répétition, pas besoin de faire autant d’ingénieurie que pour retrouver la voie ici.
  
• La validation de la voie retrouvée va être présentée juste après, et d’ailleurs l’indicatrice qualité va dépendre de la validation de la voie.
  

Indicatrice qualité

• Dépend du pourcentage de 3-grams de la voie du référentiel ⊂ l’adresse recherchée.
• Calcul non réalisable avec Elastic, donc effectué post requête.

Voie qualifiée de	Pourcentage de 3-grams
sûre	≥ 65%
peu douteuse	35% ≤ x < 65%
douteuse	10% ≤ x < 35%
non retrouvée	< 10%

Exemple : 80% des 3-grams de “verdier” dans “88 avenue verdie”.

• Le trigram “ier” n’est jamais matché
  

• verdier : 5 trigrams
  

• 4 trigrams retrouvés dans 88 avenue verdier
  

• 4*100/5 = 80

• Ces valeurs n’ont pas été choisies aux hasard, elles ont été calculées grâce au jeu de test que nous allons vous présenter ensuite. Et nous avons regardé la courbe Précision-Rappel.

• Précision = Vrais positifs/ positifs (vp + fp)

• Rappel = Vrais positifs / Bons prédits (vp + vn)

Valeurs de l’indicatrice qualité

Valeur	idGaïa maximum retrouvé
6 à 10	idAdresse
3 à 5	idVoie
2	idCommune
0 à 1	Aucun

Distance entre la 1ère et la 2ème voie la plus pertinente

\[ \text{ratio} = 1 - \frac{R_2}{R_1} \]

R1 = score Elastic de la 1ère voie la plus pertinente (voie retournée).
R2 = score Elastic de la 2ème voie la plus pertinente.

Ratio → 1 ⇔ le résultat retourné est loin de la 2ème proposition.

Maintenant qu’on a en tete l’algorithme d’identification d’adresse de Gaia, quelles sont ses performances concrètement ?

Plan de la présentation

1️⃣ Contexte

2️⃣ Utilisation du référentiel Gaïa

3️⃣ Moteur de recherche ElasticSearch

4️⃣ Algorithme d’identification d’adresses

5️⃣ Performances de l’algorithme d’identification

6️⃣ Discussion

5️⃣ Performances de l’algorithme d’identification

Constitution d’un jeu de test

• Idée : avoir des adresses avec des variations textuelles et leur idGaïaAdresse associé (vérité).
  
• Le jeu de test est une suite d’appariements de sources de données :
  • PASRAU : Prélèvement À la Source sur les Revenus AUtres.
    
  • TSSAL : Base tous salariés, issue de la déclaration sociale nominative.
    
  • Fidéli : FIchiers DÉmographiques sur les Logements et les Individus.

Schéma appariements jeu de test

• PASRAU : Ce sont des données administratives générées par le prélèvement à la source sur les retraites et d’autres revenus (mais pas les salaires).
• Adresses du PASRAU et Tous Salariés (TTSAL) avec le CSNS de l’individu connu pour chaque adresse.
  
• Grâce aux CSNS des individus Fidéli 2022, obtention de l’identifiant Majic de ces adresses.
• Avec l’identifiant Majic des adresses, conservé dans le référentiel Gaïa, on retrouve l’idGaïaAdresse.
  
• Validation post-appariements des paires adresse non normalisée (PASRAU, TSSAL)) + idGaïaAdresse.
  

Maintenant qu’on a le jeu de test, on peut evaluer l’algo.

Évaluation de l’algorithme d’identification

Pour 100 000 adresses issues du jeu de test sur tout le territoire français :

	Adresse trouvée	Voie trouvée	Commune trouvée/rien trouvé
Pourcentage	86,0%	99,5%	0,5%
Précision	0.94	0.94	x

Appariement direct avec filtres entre adresses à retrouver et référentiel Gaïa : 30% d’identification à l’adresse.

• Précision = Vrais positifs/ positifs (vp + fp)

• A titre de comparaison, un appariement direct entre les adresses à retrouver et le référentiel Gaïa donnerait 30% d’identification à condition que les filtres présentés précédemment soient appliqués.

• Le reste des adresses doivent être retrouvées avec du flou, ce qui est très long dans une bdd standard.

• Donc ce qui justifie l’utilisation d’un moteur en terme de précision mais aussi en terme de performances temporelles, notamment grace à l’index inversé.

Rapidité de l’algorithme

• 500 adresses en 2 secondes.
  
• Identification de gros paquets d’adresses : 1 million d’adresses en 50 minutes.
• Démonstration en direct du moteur ⚙️ ElasticSearch développé en Python.

{ “adresseComplete”: “48 rue fontaine”, “depcom”: ““,”codePostal”: “14530”, “libelleCommune”: “luc s/mer” }

Plan de la présentation

1️⃣ Contexte

2️⃣ Utilisation du référentiel Gaïa

3️⃣ Moteur de recherche ElasticSearch

4️⃣ Algorithme d’identification d’adresses

5️⃣ Performances de l’algorithme d’identification

6️⃣ Discussion

6️⃣ Discussion

Limites

• Compétences requises pour le développement et la maintenance du moteur ElasticSearch.
  
• Moteur créé par l’EPS en Python, réécrit en Java par l’EPI.
  
• Les travaux ont été effectués sur un référentiel contenant des erreurs/doublons → entrave les métriques qualité.

Bibliographie

1. Chaudhuri, S., et al. (2003). Robust and efficient fuzzy match for online data cleaning : lien.

2. Kathare, N., et al. (2022). A Comprehensive Study of Elastic Search. Journal of Research in Science and Engineering, 4(11) : lien.

3. Wikipedia. (n.d.). Elasticsearch : lien.

Merci au SSPlab : Julien Pramil, Lino Galiana, Olivier Meslin, Marie-Pierre Joubert et Tom Seimandi

Merci à Heidi Koumarianos et à Manon Evain

Et enfin, merci pour votre attention !