Onze website gebruikt cookies om de site gebruiksvriendelijker te maken.

Gérer les doublons dans une Graph Database

Posted on 19/12/2017 by Vandy Berten

Dans nos blogs précédents (1, 2, 3, 4), nous avons mis en évidence le fait que les structures de graphes étaient très adaptées à la recherche de comportement frauduleux. En étant plongés quotidiennement dans des données issues de diverses bases de données officielles, nous sommes également confrontés en permanence à la présence d'une grande quantité d'information de mauvaise qualité (1, 2). Nous allons voir dans ce blog comment des recherches de fraudes peuvent être réalisées même si les données déclarées sont de mauvaise qualité.

Certaines parties de cet article, plus techniques, seront masquées. Si les détails vous intéressent, il vous suffira de cliquer sur les liens « Cliquer ici pour plus de détails », ou de cliquer ici pour montrer toutes les parties d'un seul coup.

Supposons qu'un organisme public soit responsable de la gestion de la sous-traitance entre entreprises, et que, chaque fois qu'une entreprise fait appel à un sous-traitant, elle doive le déclarer auprès de cet organisme. Les données issues de ces déclarations peuvent alors être vues comme un graphe, dans lequel un nœud représente une entreprise, et une relation entre deux nœuds A et B, le fait que B est un sous-traitant de A. Si A sous-traite auprès de B, et B auprès de C, on notera cela de la façon suivante (en s'inspirant de la notation de Cypher, langage de Neo4j) :

(A)-->(B)-->(C)

Imaginons une loi (un peu simpliste et fantaisiste) disant qu'une entreprise ne peut pas être sa propre sous-traitante, ni directement, ni indirectement. Les structures suivantes seraient donc considérées comme « frauduleuses » :

(A)-->(A)
(A)-->(B)-->(C)-->(A)

Du point de vue de la théorie des graphes, on veut en fait s’assurer qu’il n’y a pas de cycle dans le graphe de description des sous-traitances, graphe étant dirigé, puisque les arcs ont une direction. On parle dès lors de « Graphe Dirigé Acyclique » (DAG). Le schéma ci-dessous montre une structure acceptable, dans laquelle aucune entreprise n’est son propre sous-traitant, même indirectement.

graphic

En Cypher (dont la syntaxe a été brièvement présentée dans notre article précédent), en supposant que les entreprises soient de type « Company », et les relations de type « Subcontractor », on pourra écrire la requête suivante, qui retournera une entreprise, et le cycle dont elle fait partie :

(1)    MATCH p=(a:Company)-[:Subcontractor*]->(a)
       RETURN a, p

Pour des raisons de performances, il sera souvent préférable de limiter la longueur des cycles : (a:Company)-[:Subcontractor*..5]->(a).

Qualité des données

Supposons maintenant que le système de déclaration ne soit pas très contraignant, et que, quand une entreprise déclare une sous-traitance, elle ne soit pas obligée de donner un identifiant officiel de l'entreprise en question (un numéro d'entreprise ou d'employeur attribué par l'état), mais puisse se contenter d'en donner le nom, et éventuellement l'adresse. On peut donc avoir une situation dans laquelle (A) déclare correctement sa sous-traitance vers (B) (c'est-à-dire avec un numéro d'entreprise officiel), idem pour (B) envers (C), mais par contre, (C) déclare sa sous-traitance vers (A) sans en préciser l'identifiant, mais uniquement le nom. On aura dans la base de données associée à la déclaration, deux nœuds, avec les attributs suivants :

  • (A) : ID : 12345, Nom : « Mon Entreprise SA »
  • (A') : ID : <vide>, Nom : « Mon Entreprise SA »

L'organisme récoltant les données n'a ici aucun moyen de s'assurer que les entreprises (A) et (A') sont en fait la même entreprise. Il existe des multitudes de synonymes d'entreprise. On trouve des « Coiffeur Rolland » dans bon nombre de villes, et les boulangeries « La baguette dorée » sont légion.

La cycle ci-dessus devient alors une chaîne (non fermée) : (A)-->(B)-->(C)-->(A') , et la recherche évoquée plus haut ne permet plus de détecter le comportement frauduleux.

L'approche classique

Une approche classique de ce problème consiste à utiliser des outils de « Data Quality » (comme l’outil open-source OpenRefine, ou le logiciel commercial Trillium aux fonctionnalités beaucoup plus avancées), pour, en fonction de critères définis, fusionner certains enregistrements de la base de données. On peut par exemple décider que si on trouve deux enregistrements avec exactement le même nom d’entreprise, se trouvant dans la même rue, on les fusionne en considérant qu’il s’agit de la même entreprise. On peut par ailleurs décider que si les deux noms sont similaires, mais ont la même adresse, alors on les fusionne également.

Les outils, en particulier les suites professionnelles comme Trillium, permettent de définir finement le degré de proximité que l'on acceptera entre deux dénominations ou adresses (ou, plus généralement, toute information) pour les considérer comme « identiques » (on ne va pas uniquement considérer des chaînes de caractères exactement identiques). Par ailleurs, nous n'évoquons ici que la problématique de la détection de (présomption de) doublons : le domaine de la « Data Quality » s'intéresse à bien d'autres aspects : incohérence de données, comparaison entre différentes sources, profilage des données, standardisation...

Notons qu’on va souvent effectuer cette fusion non pas dans les données de production, mais dans une copie servant à faire des analyses et des recherches de fraude.

Mais cette approche, très efficace dans de nombreuses situations, a principalement deux limites :

  • Elle permet de fusionner des informations tabulaires plates (une entreprise avec un nom, une adresse, éventuellement une catégorie d’entreprise, le nom du gérant, voire des dates de création ou autres événements), mais est plus complexe pour des structures plus élaborées. On s’en sort encore sans trop de dommages si on considère que chaque entreprise peut avoir plusieurs adresses (correspondant à plusieurs implantations, ou à l’historique du siège principal), mais si l’on veut considérer, en l’absence d’adresse, les travailleurs communs aux « deux » entreprises, ou les administrateurs (ou autres client, fournisseur…), cette approche relativement statique n’est plus tenable.
  • Elle impose de choisir, avant l’analyse des données, les critères de fusion. Or il s’avère parfois utile de faire ce choix plus tard dans l’analyse, soit parce que, en fonction de l’analyse, on veut être plus ou moins stricte sur la façon de faire cette fusion, soit parce que, dans une analyse particulière, on veut identifier un schéma passant par plusieurs « chemin de duplicatas », n’ayant pas tous le même degré de certitude.

Nous proposons dès lors une approche qui combine à la fois les possibilités offertes par les bases de données orientées graphes (« Graph Databases ») et les outils de gestion de qualité de données (« Data Quality tools »).

Une autre approche

L’approche que nous décrivons ici permet de traiter les doublons d’entreprises, mais une approche très similaire pourra être utile pour détecter les doublons de personnes, ou de toute autre entité.

La première étape de notre approche consistera à identifier les entreprises dont le nom est identique, ou similaire (selon un niveau d'exigence que l'on peut définir). Dans cette première étape, on ne considère que le nom de l’entreprise, et pas les autres attributs (adresses, travailleurs…)

 

Après ces étapes de nettoyage, toutes les entreprises (ou plus précisément tous les enregistrements d’entreprise) dont le nom est considéré comme identique ou presque, seront regroupées (mais pas fusionnés). Dans notre base de données, on créera alors un nœud d’un nouveau type (nous avions déjà implicitement un type de nœud « Company »), que nous appellerons « Denomination_group »

graphic

Gestion des adresses

En parallèle avec cette gestion de dénomination, il s’agira également de traiter les adresses dont on dispose pour une entreprise. Il peut s’agir d’une seule adresse, mais également de plusieurs adresses par entreprise, soit parce que celle-ci dispose de plusieurs sites, soit parce que l’on dispose de l’historique des adresses.

 

Une fois les adresses normalisées, on va considérer dans notre base de données un nœud par rue, et un lien (avec en attribut le numéro de la boite) entre une entreprise et la rue où celle-ci a un siège.
Nous pourrions éventuellement considérer un nœud par adresse (et non par rue), mais cela fera exploser le nombre de nœuds, et donnera plus de souplesse par la suite, comme nous le verrons plus loin.

grphic

Autres liens

On peut imaginer qu’un organisme dispose d’autres informations. Par exemple, un système dans lequel les entreprises doivent déclarer leurs travailleurs, et où le contrôle au niveau de l’entreprise est faible (ce qui est typiquement le cas des travailleurs « détachés », ayant leur employeur dans un pays A, mais travaillant – généralement temporairement – dans un pays B. Ils doivent alors être déclarés dans le pays B, mais qui peut alors difficilement imposer un système d’identification standardisé).
Dans de tels cas, on pourrait utiliser les travailleurs comme entités supplémentaires. On peut aussi se servir des administrateurs ou des gérants si l’on dispose de ce type d’information.

Combiner noms et adresses

Considérons maintenant plusieurs enregistrements dans notre base de données de sous-traitance. Nous supposons que « Ma Société » a déménagé, on trouve donc des données à deux adresses différentes :

  ID national Dénomination Adresse
1   Ma société S.A Avenue Fonsny 20
2   MA SOCIETE Boulevard Industriel 25
3 1234 Ma Société Avenue Fonsny 20
4 1234 Ma Société Boulevard Industriel 25

On aura dans notre base de données graphes trois nœuds « Company » : (-, « Ma société S.A »), (-, « MA SOCIETE »), et (1234, « Ma Société »), et deux rues : « Avenue Fonsny » et « Boulevard Industriel » (nous supposons que les adresses ont été normalisées au préalable), comme on peut le voir dans la figure ci-dessus.

Les versions nettoyées des trois sociétés donnent la même chaîne de caractères, et seront regroupées autour d’un nœud « Denomination_group », comme le montre le schéma ci-dessus.

On pourra maintenant rechercher un cycle entre deux compagnies A1 et A2, avec de forts soupçons de doublons.

(2)    MATCH
      (A1:Company)-[:Subcontractor*]->(A2:Company),
      (A1)-->(:Denomination_group)<--(A2),
      (A1)-->(:Street)<--(A2)
      RETURN …

La première ligne indique donc qu’il y a un chemin de sous-traitance entre A1 et A2 ; la seconde que A1 et A2 portent le même nom (après nettoyage, ou éventuellement après application d’un algorithme tel que la distance de Levenshtein), et la troisième que A1 et A2 sont renseignées dans la même rue.

graphic

Dans le schéma ci-dessus, la requête (1) plus haut aurait retourné la chaîne

(C1)-->(C2)-->(C3)-->(C1).

La requête (2) retournera quant à elle

(C10)-->(C3)-->(C1)-->(C2)-->(C9),

avec D1 comme nœud « Denomination_group » et S1 comme « Street », A1 et A2 correspondant respectivement à C10 et C9.

 

On peut aussi imaginer que l’on va considérer comme fortement suspect deux entreprises de même nom, ayant un même sous-traitant (sans considérer les adresses, qui pourraient être souvent manquantes) :

(3)     MATCH
       (A1:Company)-[:Subcontractor*]->(A2:Company),
       (A1)-->(: Denomination_group)<--(A2),
       (A1)- [:Subcontractor]->(B:Company)<- [:Subcontractor]-(A2)
        RETURN …

Cette requête retournera alors

(C6)-->(C1)-->(C2)-->(C3)-->(C4),

C5 correspondant à B, et D3 au « Denomination_group ».

 

Technique hybrides

Plutôt que de gérer la totalité des doublons dans la base de données graphes, en se servant uniquement des Data Quality tools pour corriger les adresses et détecter les homonymes d'entreprises, on peut aussi considérer une technique hybride. On peut par exemple considérer une première phase, basée sur un Data Quality tool, de fusion de tous les enregistrements qui constituent à coup sûr un doublon (ou avec un niveau de certitude choisi) : par exemple, exactement la même dénomination, exactement la même adresse (les outils avancés permettent bien sûr de faire des choses bien plus complexes que ceci, gérant des dénominations similaires plutôt qu'exactes). Nous avons par exemple dans une base de données que nous exploitons plus de 1000 fois la même entreprise décrite, avec le même nom et la même adresse (mais où le numéro d'entreprise n'a pas été déclaré).

Les données ainsi « compactées » pourront alors être intégrées dans une base de données graphe, dans laquelle on recherchera des structures de doublons plus complexes (en se servant également d'autres informations, comme les travailleurs ou mandataires communs, ou plus généralement le voisinage), ou plus faible.

On pourrait aussi utiliser les techniques décrites ci-dessus pour fusionner, directement dans la base de données graphe, tous les nœuds considérés comme des doublons. Cela permettra de simplifier les requêtes par la suite, tout en permettant de garder une certaine souplesse : on fusionnera uniquement les cas « sûrs » (selon des critères que l'on devra définir), et laissera la possibilité de considérer des doublons moins certains dans les requêtes.

Conclusion

Notre expérience dans la lutte contre la fraude nous a montré ces dernières années qu'il est primordial de tenir compte de la qualité des données sur lesquelles on travaille. Mais elle nous a aussi montré que, dans le cadre d'un travail de « datamining », traiter la totalité de la problématique de qualité en amont, dans une phase de pré-traitement, n'est pas toujours optimal. Le degré de certitude exigé peut varier d'une analyse à l'autre et une certaine souplesse peut être nécessaire dans des phases plus avancées.

Néanmoins, en aucun cas il ne sera envisageable de se passer des outils de Data Quality :

  • Nous n'évoquons ici que l'aspect « détection de (présomption de) doublons » ; les outils de Data Quality ont de nombreuses autres fonctionnalités indispensables.
  • Notre approche suppose que l'on est capable de déterminer que deux dénominations d'entreprises sont « considérées comme identiques », même s'il y a des différentes orthographiques ou syntaxiques. Si l'on veut pour ce faire utiliser des méthodes plus avancées que des simples distances de Levenshtein, l'utilisation d'outil adapté sera nécessaire.
  • Nous supposons également que nous sommes capable d'identifier que deux adresses sont identiques, ce qui est bien plus complexe que de vérifier la similitude entre deux chaînes de caractères. Pour cette tâche, l'utilisation d'outils disposant de base de connaissance sera indispensable.

L'approche que nous proposons ici permet de combiner, pour la problématique du dédoublonnage et dans le cadre d'une analyse effectuée sur une base de données graphe, travail partiel de Data Quality en pré-traitement et analyse métier tenant compte des résultats obtenus. L'idée générale sera d'appliquer le principe de « Keep the power where it belongs » : combiner de façon optimale un outil de Data Quality (pour la comparaison de contenus textuels) et Graph Database (pour l'exploitation des relations).

En appliquant cette méthodologie sur des cas concrets, de multiples cas problématiques ont pu être trouvés et soumis à divers services d'inspection, que des analyses plus classiques n'avaient jusqu'ici pas permis de déceler.

Bron: Smals Research