samedi 20 septembre 2008

Matching Déterministe versus Matching Probabiliste

Détection de doublons, appariement, comparaison, mise en correspondance, rapprochement ou encore calcul de similarité... Autant de termes en usage dans le monde francophone pour nommer ce processus clef au cœur des mécanismes de dédoublonnage de données (ou de déduplication, de factorisation ou encore de stockage d'instance unique). Faisons simple : j'utiliserai ici le terme anglophone plus générique de matching.

Le principe du matching est simple : déterminer si 2 représentations (ou avatars) correspondent ou non à une même réalité. Et lorsque la comparaison de représentations n'est pas aussi évidente, on a recourt à des procédés plus ou moins élaborés de matching, dont 2 approches sont abordées dans cet article. Le problème ne date pas d'hier, mais la problématique de doublons dans les solutions MDM - c'est à dire de doublons dans des référentiels de données d'entreprise, devant mettre à disposition des données de qualité et rapidement accessibles à l'ensemble des applications de l'entreprise - amène des contraintes de rapidité de traitement (parceque accès temps-réel - SOA) et de volumétrie qu'il est nécessaire de prendre en compte pour le choix de la méthode la plus efficace.

Matching Déterministe vs Matching Probabiliste
L'univers du matching est régi par 2 grandes écoles : les fervants adeptes du déterminisme, et les aficionados du probabilisme. Le choix d'une méthode de matching a des répercussions bien plus pragmatiques sur la qualité des données de l'entreprise.

Tentons déjà de dégrossir un peu ce que sont ces 2 approches :
Pour commencer, les deux approches partagent le même objectif : déterminer si 2 avatars représentent ou non la même réalité physique - autrement dit à identifier des doublons dans un ensemble de données.

Ensuite, les 2 approches - matching Déterministe et matching Probabiliste - utilisent toutes deux des processus déterministes (avec un petit 'd') pour évaluer la similarité de deux avatars : et par déterministe on entend le procédé qui, à partir d'un même ensemble de paramètres, produit toujours le même résultat - de l'ordre de la prédiction, donc.

Enfin, les deux approches manipulent plusieurs algorithmes pour évaluer la similarité de 2 données élémentaires : on distinguera alors la comparaison stricte de valeur, qui évalue l'égalité de valeur, des logiques floues (fuzzy logic), outillées par des algorithmes complexes de calculs de "distances" entre expressions, permettent de détecter des données "proches", comme les inversions de lettres, etc.

Alors vient LA question : Puisque tout semble les rapprocher, pourquoi avoir attribué des noms distincts à ces 2 approches ?

Pour résumer cette différence, disons que les démarches de matching Probabilistes non seulement en compte les données à comparer, mais également des informations plus générale sur le contexte dans lequel s'effectue cette comparaison, comme l'état actuel de l'espace de recherche. Ces informations de contexte sont généralement des mesures statistiques - par exemple l'ensemble des valeurs de noms de famille actuellement présent dans la base référentielle de personnes - desquelles sont déduites des probabilités qui vont influencer les résultats de la comparaison déterministe

En comparant 2 enregistrements champ par champ, les 2 démarches sont capables de déterminer une probabilité de doublonnage de 2 enregistrements, c'est à dire leur similarité (à ne pas confondre avec la notion de "matching probabiliste"). Le matching probabiliste ne s'arrête pas à cette simple comparaison, et prend en compte les statistiques de l'ensemble de valeurs existentes pour pondérer l'importance données à certains champs pour différencier 2 enregistrements. 

Matching déterministe
Au delà de la simplicité de conception des algorithmes de matching déterministes, ce type de méthode souffre (selon Scott Schumacher) de plusieurs défauts qu'il décrit ainsi :
  • Moins efficaces et moins fidèles que les méthodes probabilistes, puisque non prise en compte des données existantes,
  • Applicable uniquement sur de faibles volumétries (moins de 2M d'enregistrements) , avec peu d'attributs à comparer, et là où la non détection de doublons a peu de conséquences,
  • Lourds à implémenter à mesure que les règles de matching se complexifient, et que le nombre d'attributs pris en compte augmente. La prise en compte d'un nouvel attribut nécessite la révision de l'ensemble des règles déjà existantes, en plus des nouvelles règles à implémenter, avec des impacts sur les développements et sur les performances;
  • Les méthodes déterministes n'ont plus l'avantage de la rapidité d'exécution vis-à-vis des méthodes probabilistes.
Matching probabiliste
Les avantages du matching probabiliste face au matching déterministe semblent évidents, puisque l'efficacité de la méthode probabiliste réside dans la prise en compte de données statistiques sur l'espace de recherche au moment de la comparaison. La fraîcheur de ces statistiques est donc un caractère important de cette efficacité, afin que ces informations représentent au mieux l'état du contenu du référentiel. Dans le cas du temps réel, il n'est pas pensable de régénérer ces statistiques à chaque nouvelle entrée dans le référentiel : un compromis pourra être trouvé en ne les régénérant que périodiquement - en fonction des volumes et des fréquences de mise à jour considérés.

Les détracteurs du probabiliste lui reproche son côté .. non déterministe : les limites du matching probabiliste semblent atteintes en cas de mécontentement de la manière dont 2 enregistrements sont rapproché, ou bien lorsqu'il faudra justifier les raisons qui ont menées à ce rapprochement, par exemple dans le cadre d'un audit.
Le matching déterministe permet en ce sens plus de transparence; et lorsque 2 enregistrements ne sont pas rapprochés, il suffit d'écrire la règle adéquate.
Plus évasif, le matching probabiliste peine à justifier ses raisons, de par la difficulté de conserver la trace des statistiques utilisées par le matching. C'est ici que les fonctionnalités d'audit et d'historisation des outils MDM ont leur importance : l'audit permet de conserver la trace des fusions opérées pour procéder à un éventuel retour arrière, l'historisation permet quant à elle de reconstituer - non sans effort d'investigation - l'état de l'espace de recherche (les données) et donc des statistiques considérées à un instant précis.

Quel vainqueur ?
La solution réside en un usage intelligent des 2 méthodes. Par exemple, pour des raisons de performances, un matching déterministe est essentiel pour réduire l'espace de recherche sur lequel se basera un matching probabiliste pour affiner les résultats.

Et comme le confirme David Loshin, que ce soit matching déterministe ou matching probabiliste, le plus important réside dans la maîtrise de la compréhension de la démarche, et dans la capacité des utilisateurs à faire évoluer et vivre l'algorithme, pour le rendre plus efficace dans le temps et apporter la valeur ajoutée escomptée.

Dans un prochain article, j'aborderai les limites auxquelles ces approches font face, et les méthodes pour y remédier dans le contexte du MDM.


Liens :

mercredi 10 septembre 2008

MDM Alliance Group (MAG) : Modèles de données prêts à l'emploi

Le MDM Alliance Group (ou MAG pour les intimes) vient de publier des modèles de données UML préconstruits et prêts à l'emploi ("afin d'éviter de réinventer la roue") sur les domaines des Tiers (Party), Adresses, Ressources Humaines, Classification et Période (le tout sous licence Creative Commons Attribution-Share Alike 2.0 France).

L'alliance, qui se veut fédératrice des méthodes et initiatives MDM, en profite d'ailleurs pour publier son guide de modélisation dans la langue de Shakespeare.

Liens :

lundi 1 septembre 2008

Dossier 01 Informatique : "Référentiel de donnees - Master Data Management : l'âge de raison"

Cette semaine dans les kiosques, l'hebdomadaire 01 Informatique (N°1959, du 28/08/2008) consacre un dossier pragmatique sur les référentiels de données, en abordant les dimensions liées à l'architecture, l'organisation, l'intégration, les éditeurs de solutions, et les perspectives du marché.

Dans cette dernière thématique, Franck Régnier (responsable de l'offre MDM chez Logica Management Consulting) offre des éléments de réponse quant à la tournure que prend le marché du MDM en France : place prépondérante du MDM dans les projets de refonte du SI, croissance de dimension organisationnelle, convergence des pratiques MDM et de celles de l'EIM, et bouleversements à venir du côté des marchés des éditeurs et des intégrateurs de solutions MDM.

Up : Retrouvez désormais le dossier en ligne sur le site de 01 Informatique