Duplicata de correspondance floue dans Java

Question

J'ai un List<String[]> d'enregistrements clients en Java (à partir d'une base de données). Je sais de regarder manuellement les données que 25% + sont des doublons.

Les doublons sont loin d'être exacts. Parfois, ils ont des zips différents, mais le même nom et l'adresse. D'autres fois l'adresse est complètement manquante, etc ...

Après une journée de recherche; Je suis toujours perplexe quant à la façon même de commencer à attaquer ce problème?

Quels sont les termes que je devrais googler pour décrire cette zone (à partir d'une résolution dans la perspective Java)? Et je ne pense pas qu'il y ait fuzzymatch.jar là-bas qui rend tout simplement facile?

Answer 1

J'ai déjà réalisé des systèmes similaires pour l'appariement d'informations de lieux et de personnes. Ce sont des objets complexes avec de nombreuses fonctionnalités et de déterminer si deux objets différents décrivent le même endroit ou la personne est difficile. Le moyen de le faire est de le réduire à l'essentiel.

Voici un certain nombre de choses que vous pouvez faire:

0) Si cela est un OneOff, charger les données dans openrefine et arranger les choses de manière interactive. Maximum cela résout votre problème, minimum il vous montrera où vos correspondances possibles sont.

1) il existe plusieurs façons de comparer les chaînes. Fondamentalement, ils diffèrent dans la façon dont ils sont fiables dans la production de correspondances négatives et fausses. Une correspondance négative est quand elle correspond quand elle ne devrait pas avoir. Une correspondance positive est quand il devrait correspondre et fait. Les chaînes égales ne produiront pas de correspondances négatives mais manqueront beaucoup de correspondances potentielles en raison de légères variations. Levenstein avec un petit facteur est un peu mieux. Les Ngrams produisent beaucoup de matches, mais beaucoup d'entre eux seront faux. Il y a quelques autres algorithmes, regardez par exemple. le code openrefine pour trouver différentes façons de comparer et de grouper des chaînes. Lucene implémente beaucoup de ces choses dans son framework d'analyseur mais c'est un peu une bête à travailler si vous n'êtes pas très familier avec son design.

2) Séparer le processus de comparaison des éléments du processus de décision d'une correspondance. Ce que j'ai fait dans le passé était de qualifier mes comparaisons, en utilisant une simple note numérique, par ex. ce champ correspondait exactement (100) mais ce champ était une correspondance partielle (75) et ce champ ne correspondait pas du tout. Le vecteur résultant de comparaisons qualifiées, par ex. (100, 75,0,25) peut être comparé à un vecteur de référence qui définit vos critères de correspondance parfaits ou partiels. Par exemple, si le prénom, le nom de famille et la correspondance de rue correspondent, les deux enregistrements sont identiques, quel que soit le reste des champs. Ou si les numéros de téléphone et les noms de famille correspondent, c'est aussi un match valide. Vous pouvez encoder des correspondances parfaites en tant que vecteur, puis simplement les comparer avec vos vecteurs de comparaison pour déterminer s'il s'agit d'une correspondance, d'une correspondance ou d'une correspondance partielle. C'est en quelque sorte une version manuelle de ce que fait l'apprentissage automatique qui consiste à extraire des vecteurs de caractéristiques et à construire ensuite un modèle de probabilité dont les vecteurs signifient quoi à partir des données de référence. Le faire manuellement, peut travailler pour des problèmes simples.

3) Construire un ensemble de données de référence avec des cas de test que vous savez correspondre ou ne pas correspondre et évaluer votre algorithme par rapport à cet ensemble de référence. De cette façon, vous saurez quand vous améliorez les choses ou si vous aggravez les choses lorsque vous modifiez, par ex. le facteur qui va dans Levinstein ou quoi que ce soit.

Answer 2

La réponse de Jilles est géniale et vient de l'expérience. J'ai également dû travailler sur le nettoyage de grandes tables désordonnées et malheureusement je ne savais pas grand-chose de mes options à ce moment-là (j'ai fini par utiliser Excel et beaucoup de filtres automatiques). J'aurais aimé connaître OpenRefine.

Mais si vous en arrivez au point où vous devez écrire du code personnalisé pour cela, je voudrais faire une suggestion sur la façon dont: Les colonnes sont toujours les mêmes, n'est-ce pas? Par exemple, la première chaîne est toujours la clé, la seconde est le prénom, le sixième est le code postal, dixième est le numéro de télécopie, etc.

En supposant qu'il n'y a pas un nombre déraisonnable de champs, je commencerais par un type d'enregistrement personnalisé qui a chaque champ de DB comme membre plutôt que comme une position dans un tableau. Quelque chose comme

class CustomerRow { 
    public final String id; 
    public final String firstName; 
    // ... 

    public CustomerRow(String[] data) { 
     id = data[0]; 
     // ... 
} 

Vous pourriez également inclure un code de validation dans le constructeur, si vous saviez qu'il y ait des valeurs de déchets que vous voulez toujours filtrer.

(Notez que vous faites essentiellement ce que l'ORM ferait automatiquement, mais commencer avec un serait probablement plus de travail que simplement écrire le type d'enregistrement.) Puis

vous feriez mettre en œuvre certaines Comparator<CustomerRow> s qui ne regardez que des champs particuliers, ou définissez l'égalité en termes flous (là où les algorithmes de distance d'édition seraient utiles), ou faites des tris spéciaux.

Java utilise un tri stable pour les objets, donc trier par ex. nom, puis adresse, puis touchez, vous feriez chaque type, mais choisissez vos comparateurs dans l'ordre inverse.

Aussi, si vous avez accès à la base de données actuelle, et qu'il s'agit d'une véritable base de données relationnelle, je vous recommande de faire certaines de vos recherches en tant que requêtes si possible. Et si vous avez besoin d'aller et venir entre vos objets Java et la base de données, l'utilisation d'un ORM peut s'avérer être une bonne option.