Ce n’est probablement pas nouveau pour vous que les donnĂ©es soient considĂ©rĂ©es comme de “l’or des temps modernes”. Bien que tout le monde soit conscient de l’importance des donnĂ©es, de nombreuses entreprises ne sont pas axĂ©es sur les donnĂ©es ou ne peuvent pas utiliser leurs donnĂ©es. Les raisons varient, mais c’est souvent parce que les donnĂ©es ne sont pas bien stockĂ©es, structurĂ©es ou mĂŞme consultables pour ĂŞtre utilisĂ©es.
Bien que les donnĂ©es puissent ĂŞtre stockĂ©es, les entreprises peuvent les stocker plus d’une fois ou de manière inexacte en raison d’une erreur humaine. Cela conduit bien sĂ»r Ă une mauvaise qualitĂ© des donnĂ©es, ce qui peut nuire gravement aux organisations. En fait, on dit que des donnĂ©es inexactes font perdre en moyenne 15 millions de dollars par annĂ©e aux entreprises.
Pour relever les dĂ©fis liĂ©s aux donnĂ©es, les entreprises peuvent utiliser des solutions automatisĂ©es capables de faire correspondre les donnĂ©es de deux sources de donnĂ©es diffĂ©rentes. Avec une telle solution, les donnĂ©es en double et les inexactitudes peuvent ĂŞtre facilement Ă©liminĂ©es. C’est lĂ que le Fuzzy Matching (aussi appelĂ©e correspondance floue) entre en jeu.
Pour comprendre ce concept technique, nous prendrons le temps d’expliquer ce qu’il est, pourquoi il est nĂ©cessaire pour les organisations modernes et comment il peut ĂŞtre mis en Ĺ“uvre.
Allons-y !
Qu’est-ce que Fuzzy Matching?
Fuzzy Matching (FM) aussi appelĂ©e correspondance de noms en logique floue ou correspondance approximative de chaĂ®nes, est une technique qui aide les utilisateurs Ă comparer et Ă trouver une correspondance approximative entre deux sections de donnĂ©es diffĂ©rentes ou mĂŞme une ligne de texte. Cette technique est souvent rendue possible par des technologies telles que l’intelligence artificielle (IA) et l’apprentissage machine (ML).
Techniquement, Fuzzy Matching est utilisĂ©e comme algorithme de correspondance de chaĂ®nes (algorithme qui recherche une chaĂ®ne dans ​​’autre chaĂ®ne) avec des règles prĂ©dĂ©terminĂ©es pour trouver des chaĂ®nes, des mots ou des entrĂ©es en double qui sont les plus proches les uns des autres. Avec l’utilisation de Fuzzy Matching, il est possible de trouver des noms, des mots ou des chaĂ®nes qui sont abrĂ©gĂ©s, raccourcis ou mal orthographiĂ©s, par exemple.
Supposons que vous souhaitiez trouver “numĂ©ro de facture” sur un document, mais que le mot est mal orthographiĂ© “numĂ©ro de factur” ou est abrĂ©gĂ© en “no de facture”. Dans cette situation, vous n’obtiendriez pas une correspondance exacte lors de la recherche du “numĂ©ro de facture”, donc vous ne pouvez pas trouver ce que vous cherchez.
Avec un algorithme de Fuzzy Matching, ce n’est pas un problème, car l’algorithme peut toujours trouver une correspondance approximative avec le mot mal orthographiĂ© ou raccourci en fournissant un score de correspondance de 0 Ă 100% basĂ© sur les “corrections d’Ă©dition”. Une correction d’Ă©dition est une correction que l’algorithme FM doit effectuer en fonction de la logique pour ajuster une certaine chaĂ®ne afin que cette chaĂ®ne corresponde Ă une autre chaĂ®ne.
Corrections d’édition de Fuzzy Matching
En gĂ©nĂ©ral, les algorithmes FM utilisent les corrections d’Ă©dition suivantes :
- Insertion – ajout d’une lettre pour complĂ©ter le mot (p. ex. “factur” devient “facture“)
- Suppression – suppression d’une lettre d’un mot (par exemple, “Facturee” devient “Facture”)
- Substitution – Ă©change d’une lettre pour corriger un mot (par exemple, “pacture” devient “facture”)
- Transposition – Ă©change de lettres pour corriger un mot (par exemple, “afcture” devient “facture”)
Chaque correction qui doit ĂŞtre effectuĂ©e attribuera une “distance d’Ă©dition” de 1. Les distances d’Ă©dition influencent le score de correspondance mentionnĂ© prĂ©cĂ©demment. Par exemple, si vous avez une chaĂ®ne de 11 caractères et que vous devez effectuer 2 corrections, le score de correspondance final est Ă©gal Ă 81,81 %.
Calcul : 100%- 2 / 11= 81,81%
En plus de ces corrections, FM peut être utilisé pour corriger les ponctuations, les mots supplémentaires et les espaces manquants dans les chaînes ou les textes.
Pour mieux comprendre le fonctionnement de Fuzzy Matching et le calcul des distances d’Ă©dition, la section suivante est consacrĂ©e Ă l’explication dĂ©taillĂ©e des diffĂ©rents algorithmes de Fuzzy Matching.
Fuzzy Matching Algorithmes
Fuzzy Matching fait partie de la catĂ©gorie des mĂ©thodes qui n’ont pas un algorithme spĂ©cifique qui couvre tous les scĂ©narios et cas d’utilisation. Par consĂ©quent, nous allons couvrir certains des algorithmes de Fuzzy Matching les plus couramment utilisĂ©s et fiables pour trouver des correspondances de donnĂ©es approximatives:
- Distance de Levenshtein (LD)
- Distance de Hamming (HD)
- Damerau-Levenshtein
Levenshtein Distance
La distance de Levenshtein (LD) est une technique de Fuzzy Matching qui prend en compte deux chaĂ®nes lors de la comparaison et de la recherche d’une correspondance. Plus la valeur de Levenshtein Distance est Ă©levĂ©e, plus les deux chaĂ®nes ou “termes” sont loin d’ĂŞtre identiques.
Alors comment obtenir la valeur de la distance Levenshtein ? Le LD entre les deux chaĂ®nes est Ă©gal au nombre d’Ă©ditions nĂ©cessaires pour convertir une chaĂ®ne en l’autre. Pour l’ID, l’insertion, la suppression et la substitution d’un seul caractère s’appliquent en tant qu’opĂ©rations d’Ă©dition.
Supposons que vous voulez mesurer le LD entre “numĂ©ro de facture” et “nmĂ©ro de factur”. La distance entre les deux termes est “1 x u” et “1 x e”, ce qui Ă©quivaudrait Ă une distance de 2. Pourquoi ? Parce qu’il faudrait ajouter ces deux caractères pour qu’ils correspondent exactement. Voir les exemples ci-dessous.
Levenshtein Distance Exemple
- Numéo de facture→ Numéro de facture (insertion de “r”) – Distance: 1
- NumĂ©ro de actre → NumĂ©ro de facture (insertion de “f” & “u”) – Distance: 2
- Numéro de fre → Numéro de facture (insertion de “a,c,t,u”) – Distance: 4
Hamming Distance
La distance de Hamming (HD) n’est pas trop diffĂ©rente de la Levenshtein. La distance de Hamming est souvent utilisĂ©e pour calculer la distance entre deux chaĂ®nes textuelles de longueur Ă©gale.
La mĂ©thode HD est basĂ©e sur la table ASCII (American Standard Code for Information Interchange). Pour calculer le score de distance, l’algorithme de distance de Hamming utilise la table pour dĂ©terminer le code binaire associĂ© Ă chaque lettre dans les chaĂ®nes.
Exemple de distance de Hamming
Prenons les chaĂ®nes textuelles suivantes “number” (numĂ©ro) et “lumber” comme exemple. Lorsque nous essayons de dĂ©terminer le HD entre les chaĂ®nes, la distance n’est pas 1 comme ce serait le cas avec l’algorithme de Levenshtein. Au lieu de cela, ce serait 10. En effet, la table ASCII montre un code binaire de (1001110) pour la lettre N et (1001100) pour la lettre L.
Exemple de calcul:
D = N – L = 1001110 – 1001100 = 10
Damerau-Levenshtein
Le Damerau-Levenshtein mesure Ă©galement la distance entre deux mots en mesurant les changements requis pour ajuster un mot dans l’autre. Ces modifications dĂ©pendent du nombre d’opĂ©rations telles que les insertions, les suppressions ou les substitutions d’un seul caractère ou la transposition de deux caractères adjacents.
C’est lĂ que la distance de Damerau-Levenshtein diffère de la distance de Levenshtein normale, car elle inclut des transpositions en plus des opĂ©rations d’Ă©dition d’un seul caractère pour trouver une correspondance approximative (Fuzzy Match).
Damerau-Levenshtein Exemple
Chaîne 1: Facture
Chaîne 2: Facutr
Operation 1: transposition -> Échanger des caractères “u” and “t”
Operation 2: insérer “e” à la fin de la chaîne 2
Comme deux opĂ©rations Ă©taient nĂ©cessaires pour rendre les deux chaĂ®nes identiques, la distance est Ă©gale Ă 2. En d’autres termes, chaque opĂ©ration telle que l’insertion, la suppression, la transposition, etc, compte comme une distance de “1”. Cependant, avec la distance Levenshtein, vous devez effectuer trois corrections d’Ă©dition, ce qui Ă©quivaut Ă la distance de 3.
Il est clair que tous les algorithmes de Fuzzy Matching mentionnĂ©s ci-dessus diffèrent les uns des autres dans la façon dont la distance d’Ă©dition est calculĂ©e. C’est la raison pour laquelle il n’y a pas d’algorithme FM adaptĂ© Ă tous. Cependant, la distance de Levenshtein est l’algorithme FM le plus couramment utilisĂ© dans la gestion des donnĂ©es et la science des donnĂ©es, parmi les trois qui ont Ă©tĂ© prĂ©sentĂ©s.
Fuzzy Matching Cas D’utilisation
Il existe de multiples façons d’utiliser la FM dans des applications rĂ©elles, dont certaines font partie de votre vie quotidienne. Examinons quelques exemples ci-dessous (la liste n’est pas exhaustive) :
- Extraction de données de document
- Suggestion automatique avec vérification orthographique
- DĂ©duplication
- Séquençage Du Génome
Extraction de données de document
Bien que l’OCR, Ă©galement connue sous le nom de technologie d’extraction image-texte, soit plus avancĂ©e qu’il y a 10 ou mĂŞme 20 ans, il peut toujours produire des rĂ©sultats d’extraction de donnĂ©es inexacts. Comme de nombreuses entreprises traitent un large Ă©ventail de documents en grande quantitĂ©, des rĂ©sultats d’extraction de donnĂ©es inexacts peuvent leur faire perdre des sommes d’argent considĂ©rables.
Pour complĂ©ter le logiciel OCR et contribuer Ă rĂ©soudre ce problème, il est possible d’appliquer le Fuzzy Matching. Lorsque l’OCR ne parvient pas Ă trouver une “correspondance exacte” lors de l’extraction de certains champs de donnĂ©es et de donnĂ©es de documents, Fuzzy Matching peut aider Ă trouver la correspondance la plus proche grâce Ă une correspondance approximative des chaĂ®nes de caractères en utilisant la distance de Levenshtein.
Ainsi, les entreprises sont toujours en mesure d’extraire les donnĂ©es des documents au lieu que le logiciel d’OCR ne produise aucun rĂ©sultat lorsqu’aucune correspondance exacte ne peut ĂŞtre trouvĂ©e.
Suggestion automatique avec vérification orthographique
Vous avez probablement rencontré ou utilisé différents moteurs de recherche au cours de votre vie. Ce faisant, vous avez également remarqué que les moteurs de recherche nous fournissent parfois le contenu que nous recherchons malgré les mots ou les phrases mal orthographiés.
Cela est dû au fait que les moteurs de recherche tels que Google utilisent des algorithmes de Fuzzy Matching. Google comprend ce que vous avez voulu taper comme requête principale et vous propose une option pour le mot recherché lorsque vous tapez dans la barre de recherche.
Avec l’IA ou la ML, le Fuzzy Matching a permis d’amĂ©liorer les moteurs de recherche tels que Google et YouTube afin d’amĂ©liorer l’expĂ©rience de la recherche.
DĂ©duplication
Comme mentionné précédemment, de nombreuses entreprises souffrent de données en double, principalement en raison de transferts de données, d’un manque de contrôle ou d’erreurs de saisie de données. Les copies carbone d’un document (nom, adresse, courriel, numéro de téléphone, etc.) ou les copies partielles sont courantes pour les organisations.
Avec Fuzzy Matching, les organisations peuvent fusionner, supprimer ou réorganiser les données en trouvant des correspondances approximatives. Il permet aux organisations de rationaliser la gestion de leurs enregistrements et de leurs données, ce qui s’accompagne de divers avantages abordés plus loin dans ce blog.
La déduplication est également très utile lorsque vous entraînez des modèles OCR à extraire des informations de documents. En supprimant les échantillons de données en double des ensembles de données d’apprentissage, la formation devient plus efficace et la précision de prédiction des modèles OCR s’améliore considérablement.
Séquençage du génome
Dans les soins de santé et la science, l’appariement flou peut être très utile, en particulier dans le séquençage du génome. Il permet aux chercheurs de trouver une correspondance approximative avec une séquence génomique particulière en exécutant un algorithme sur la séquence.
Avec l’algorithme d’appariement flou, ils sont capables de trouver la séquence d’appariement la plus proche ou l’ensemble de séquences pour déterminer à quel organisme la séquence appartient en fonction du résultat. Un exemple serait de trouver la correspondance la plus proche d’une certaine bactérie ou d’un virus afin de trouver le bon remède.
En d’autres termes, Fuzzy Matching peut aider les chercheurs à trouver un remède pour certaines maladies. Intéressant, n’est-ce pas?
À présent, il devrait être clair que l’utilisation de FM est flexible et peut être appliquée dans divers cas d’utilisation. Quel que soit votre cas d’utilisation, Fuzzy Matching présente divers avantages.
Avantages de Fuzzy Matching
Les avantages les plus courants pour les organisations utilisant Fuzzy Matching comme approche pour identifier les correspondances sont les suivants:
- PrĂ©cision des donnĂ©es – Les organisations peuvent atteindre une prĂ©cision Ă©levĂ©e de correspondance des donnĂ©es, car FM a la capacitĂ© de rechercher des correspondances approximatives en analysant les chaĂ®nes et en calculant le score de distance “modifier” Ă l’aide d’algorithmes.
- DonnĂ©es consultables – Fuzzy Matching permet aux utilisateurs de trouver des correspondances malgrĂ© les variations dues Ă des erreurs telles que des fautes d’orthographe, des majuscules manquantes ou une mise en forme manquĂ©e de mots ou de chaĂ®nes.
- FlexibilitĂ© – Il existe de nombreuses façons dont les algorithmes de logique floue peuvent aider Ă rĂ©soudre mĂŞme les problèmes les plus complexes.
- Base de donnĂ©es plus propre – Les algorithmes de Fuzzy Matching peuvent aider les organisations Ă trouver des enregistrements de donnĂ©es en double pour une base de donnĂ©es plus saine, plus propre et plus prĂ©cise.
Inconvénients de Fuzzy Matching
Tout ce qui concerne la correspondance de chaînes floues n’est pas parfait. Au contraire, la FM est livrée avec diverses limitations, notamment:
- Liens incorrects – Bien que Fuzzy Matching soit excellente pour trouver des correspondances approximatives, elle entraĂ®ne parfois un grand nombre de faux positifs conduisant Ă des liens incorrects, en particulier avec des bases de donnĂ©es plus volumineuses.
- NĂ©cessite une maintenance – Les algorithmes doivent ĂŞtre constamment testĂ©s et les règles qu’ils contiennent mises Ă jour afin d’effectuer une correspondance de chaĂ®ne prĂ©cise.
Bien qu’il y ait des inconvénients, l’utilisation de Fuzzy Matching profite davantage aux entreprises qu’à la création de défis. Alors, comment pouvez-vous l’implémenter dans vos propres solutions? Jetons un coup d’œil à cela ensuite!
Application Fuzzy Matching
Vous pouvez implémenter des algorithmes de fuzzy matching à l’aide de différents langages de programmation, notamment:
- Python – Fuzzywuzzy La bibliothèque Python applique l’approche Levenshtein Distance pour effectuer une correspondance approximative de chaĂ®nes.
- Java – Il est très difficile d’implĂ©menter FM en Java, cependant, cela se fait via un rĂ©fĂ©rentiel GitHub pour implĂ©menter la bibliothèque Fuzzywuzzy en Java.
- Excel – Mise en Ĺ“uvre facile de FM via des add-ons tels que Exis Echo, Fuzzy Lookup et mĂŞme en utilisant la fonction native RECHERCHEV.
Bien sûr, il est possible de créer vos propres solutions pour trouver des correspondances de chaînes approximatives, mais cela prend du temps et nécessite des ressources. Il est souvent préférable d’acquérir une solution qui utilise des algorithmes de Fuzzy Matching pour soutenir votre analyse de rentabilisation.
Si vous ĂŞtes curieux de savoir comment chez Klippa nous utilisons Fuzzy Matching dans nos solutions, continuez Ă lire!
Comment Klippa utilise-t-il Fuzzy Matching?
De nombreux logiciels OCR comme Klippa DocHorizon se concentrent principalement sur la recherche d’une correspondance exacte dans les champs de données pour l’extraction de données. Cependant, tous les logiciels OCR ne peuvent pas toujours trouver des correspondances exactes lors de l’extraction de données pour diverses raisons telles que l’utilisation d’abréviations, de mots abrégés, etc. C’est pourquoi il est important d’utiliser Fuzzy Matching pour s’assurer que les données pertinentes peuvent être extraites des documents.
À cet égard, Klippa utilise la distance de Levenshtein pour trouver des correspondances approximatives et s’assurer que toutes les données pertinentes sont extraites. Une fois l’extraction des données terminée, la sortie des données est fournie au format JSON avec un score de correspondance. Avec le score de match, les clients de Klippa peuvent déterminer s’ils ont besoin de demander à une personne de vérifier les résultats pour éviter d’obtenir des résultats inexacts.
En plus de l’extraction de données, Klippa utilise Fuzzy Matching pour éliminer les données en double des ensembles de données afin d’entraîner des modèles OCR. De cette façon, le processus de formation est plus efficace et apporte de meilleurs résultats d’amélioration car aucun temps n’est perdu et les risques de faux positifs (dans les résultats d’extraction et de reconnaissance des données) sont réduits.
Êtes-vous intéressé à trouver Fuzzy Matches pour améliorer l’extraction ou la gestion des données de votre organisation? N’hésitez pas à planifier une démo via le formulaire ci-dessous pour voir comment notre solution fonctionne avec Fuzzy Matching. Si vous souhaitez avoir une consultation ou obtenir plus d’informations, contactez l’un de nos experts.