Clustering & Déduplication¶

🗺️ Contexte: on ingère de la donnée d’acteurs de l’économie circulaire de plusieurs sources
🔴 Problème: certains acteurs sont en doublon, polluant l’application utilisteur
🟢 Solution: faire un travail pour réduire les doublons et améliorer la cohérence des données
🤔 Comment: voir ci-dessous

⚠️ Limitations connues¶

On ne séparent pas les enfants d’un cluster existant: choix de notre part, pour l’instant on veut uniquement ajouter des nouveaux enfants. Pour changer il faudra CLUSTERING & DEDUP: re-clusteriser les enfants existants. Pour l’instant:
- 🟢 avantage: pas de risque d’endommager des clusters existants
- 🟠 inconvénient: pas d’opportunité de re-clustering les mauvais cluster existants
Pas de re-clustering enfants = pas de contexte enfant: conséquence du dessus, les enfants n’ont pas leur donnée récupérée ni normalisée, ce qui peut poser des problèmes de contexte, donc on à fait https://github.com/incubateur-ademe/quefairedemesobjets/pull/1379 en attendant

📜 Définition¶

📦 Clustering: fait de regrouper des acteurs via leur similarité
1️⃣ Déduplication: convertir un cluster en 1 seul acteur pour ne plus avoir de doublons
🎏 Etat final idéal d’un acteur: on se concentre sur les acteurs statut=ACTIF

Etat 🇫🇷	Code 🇬🇧	Définition	Correspond à une source en particulier	Visible sur la carte
parent(s)	parent(s)	acteur qui a 1 ou plusieurs enfants rattachés à lui	🟠 NON on créé un parent “artificiel” pour que celui-ci vive de manière détachée de ses enfants = plus robuste à travers le temps, pas besoin de changer le parent à chaque fois que les enfants changent	🟢 OUI
enfant(s)	child / children	acteur rattaché à 1 parent (1 est le maximum)	🟢 OUI C’est de cette source que vient l’acteur	🟠 NON C’est le parent qui est affiché
orphelin(s)	orphan(s)	acteur rattaché à 0 parent	🟢 OUI C’est de cette source que vient l’acteur	🟢 OUI

➡️ Transitions d’états: scénarios¶

modèle de changement	Etat avant	Etat après	Scénario	Conséquences dans revision	Conséquences dans displayed
acteur_create_as_parent	Orphelin	Parent	➕ Nouveau parent pour nouveau cluster	➕ Parent à créer ➕ Donnée enrichie au mieux	pareil que révision
acteur_keep_as_parent	Parent	Parent	1️⃣ 1 seul parent existant -> à garder	🟰 Toujours parent du cluster ➕ Donnée enrichie au mieux	pareil que révision
acteur_keep_as_parent	Parent	Parent	🎖️ 2+ parents dans cluster -> celui avec + d'enfants -> à garder	🟰 Toujours parent du cluster ➕ Donnée enrichie au mieux	pareil que révision
acteur_delete_as_parent	Parent	N’existera plus	🔴 2+ parents dans cluster -> non choisi -> à supprimer	🛑 Devrait être automatiquement supprimé suite à la mise à jour de ces enfants (voir PR1247)	🛑 Devrait disparaitre de displayed
acteur_verify_in_revision	Enfant	Enfant	🟰 Pointe déjà vers nouveau parent → rien à faire	Aucune	Aucune
acteur_update_parent_id	Enfant	Enfant	🔀 Pointait vers un parent qui n’a pas été choisi → à pointer vers nouveau parent	🔀 Mettre à jour parent_id pour pointer vers nouveau parent	Aucune
acteur_update_parent_id	Orphelin	Enfant	🔀 à pointer vers un parent	🔀 Mettre à jour parent_id pour pointer vers nouveau parent	🛑 Devrait disparaitre de displayed
	Orphelin	Orphelin	Ne fais toujours pas parti d’un cluster (pas de changement)	Aucune	Aucune

🧪 Algorithme¶

🗓️ Tentatives passées¶

Considération de https://github.com/dedupeio/dedupe: mais en voyant que le comparateur évalue 2 valeurs à la fois = complexité O(n2) au moment du runtime, et sachant nos volumes (~500K acteurs) = peur de s’orentier vers du non-vectorisé. On voit des retours utilisateurs qui vont dans ce sens (temps de matching qui explose en passant d’un échantillon de 1K à 5K).
Tentative vectorisée: tenté de faire du vectorisé de base (ex: TF-IDF pour naturellement dépriorisé le bruit / la redondance) mais n’ayant pas d’infra de compute (ex: startup état = frugale) l’idée a été abandonnée (le risque de créer des modèles qu’on ne pouvait pas gérer via Airflow).

👉🏻 Actuellement¶

Très primitif: avec de la normalisation et du TF-IDF mais qui tourne à une échelle trop réduite pour être vraiment pertinent. Manque de tolérance fuzzy.

💡 Améliorations¶

Continuer la normalisation en amont: car celle-ci fait bénéficier non seulement le clustering, mais la qualité des données sur la carte:
- conversion anciennes -> nouvelles villes: grâce à la BAN
- normalisation des adresses: toujours avec la BAN
- enrichissement des noms au moment du matching pour plus d’embeddings via l”AE
Etendre le scope vectorisé: par exemple à l’échelle d’un département, pour offrir un compromis pertinence vs. taille du modèle
Reconsidérer https://github.com/dedupeio/dedupe: encore une fois sur des sous-ensembles (e.g. ville) pour bénéficier de la librairie (qui offre des choses intéressantes genre distances) sans souffrir trop du O(n2)
Embeddings: à cause des représentations vraiment diverses (ex: centre de collècte des déchets vs. décheteries)
Mappings de conversion pour les cas limités/connus (ex: abbrévation des noms de voies, ex: ESP -> ESPLANADE)
Algo phonétiques pour les typos
Modèles de langues: potentiellement les modèles compact (SLMs) qui offrirait des performances supérieur à tout ce qu’on peut faire au dessus en posant la question simple (« merci de clusteriser ces échantillons »)

🚤 Performance¶

👉🏻 Actuellement¶

Mauvaises mais suffisantes pour métier: qui fait tourner l’algo sur Airflow et fait autre chose en attendant
Raison principale: les boucles et aller-retour successifs pour choisir les parents et leur données
Exemple d’un clustering de 150K acteurs qui prenait ~6 heures

💡 Améliorations¶

Réécrire les tâches en passant par des modèles DBT qui s’occupe de préparer la data = finit les boucles / aller-retour DB via python.

🔀 Schéma¶

        graph TD
   subgraph selection["🔎 <b>selection</b>: statut=ACTIF"]
      direction LR
      parents
      orphans
      children
   end

   subgraph normalization["🧹 <b>normalization</b>"]
	    norma["lower case, no accents etc..."]
   end

   subgraph clustering["📦 <b>clustering</b>"]
		  similar["exact + fuzzy silimarity"]
   end

   subgraph dedup["1️⃣ <b>deduplication</b>"]
		  parents_choose["🥇 Choose new parents"]
		  parents_data["🗄️ Choose parents' data (from non-normalized data)"]
		  parents_choose-->parents_data
		  parents_data-->children_feed["⬅️ Add existing children"]
		  children_feed-->changes_mark["📋 Define changes"]
   end

   subgraph suggestions[" <b>suggestions</b>"]
      propose
	 end

   parents-->|displayed| normalization
   orphans-->|displayed| normalization
   normalization --> clustering
   children-->|revision| children_feed
   clustering-->dedup
   changes_mark-->suggestions