Qu’est-ce que fuzzy matching?
Fuzzy matching (également appelée correspondance approximative de chaînes) est une approach qui permet d’identifier deux éléments de texte, chaînes ou entrées qui sont à peu près similaires mais ne sont pas exactement identiques.
Par exemple, prenons le cas d’une liste d’hôtels à New York comme le montrent Expedia et Priceline dans le graphique ci-dessous.
Nous pouvons voir qu’Expedia et Priceline décrivent la même annonce de manières légèrement différentes. Grâce à la fuzzy matching qui identifie deux morceaux de texte à peu près similaires, nous sommes en mesure de faire correspondre la même liste d’hôtels sur chacun de ces websites, même si leurs descriptions ne sont pas exactement les mêmes.
Il existe de nombreuses conditions dans lesquelles les strategies de fuzzy matching peuvent s’avérer utiles. Examinons quelques exemples concrets d’utilisation de Fuzzy Matching.
1) Création d’une vue shopper distinctive (SCV) : une vue shopper distinctive (SCV) fait référence à la collecte de toutes les données sur les purchasers et à leur fusion en un seul enregistrement.
Par exemple : supposons que vous gérez un restaurant. Vous pouvez disposer des sources de données/tables suivantes. Le tableau 1 contient des informations sur l’historique des commandes de vos purchasers et le tableau 2 contient des informations sur leurs habitudes de navigation sur le website Net du restaurant.
Une grande organisation dispose forcément d’une multitude de tables de ce sort qu’elle peut rejoindre pour obtenir une vue shopper distinctive. Cela nécessite souvent une correspondance de chaîne floue (dans notre scénario, les tableaux 1 et 2 doivent être joints à l’aide de l’attribut Nom du shopper).
Le restaurant pourrait exploiter les informations SCV comme go well with :
lorsqu’un shopper régulier appelle pour passer une commande, le restaurant pourrait suggérer un nouveau plat en fonction de son historique de commandes et des recettes qu’il a consultées. Le restaurant pourrait également envoyer du contenu personnalisé (nouvelles recettes passionnantes) à ses purchasers en utilisant les informations SCV.
2) Exactitude des données :
Selon une étude récente, plus de 60 % des entreprises ont mis en œuvre des options basées sur le Machine Studying. Alors que les entreprises s’appuient sur l’intelligence artificielle et l’apprentissage automatique, l’exactitude des données devient extrêmement cruciale.
Des recherches révolutionnaires sont souvent menées pour améliorer la précision des réseaux neuronaux et des applied sciences d’apprentissage automatique, mais peu d’efforts sont faits pour garantir que des données de bonne qualité soient transmises à ces modèles. Un wonderful algorithme d’apprentissage automatique sans données précises équivaut au lancement d’une fusée sur Mars à l’aide de gaz naturel comprimé.
La correspondance de chaînes floues peut contribuer à améliorer la qualité et la précision des données grâce à la déduplication des données, à l’identification des fake positifs, and many others.
3) Détection de fraude :
Un bon algorithme de correspondance de chaînes floues peut aider à détecter la fraude au sein d’une organisation. Plus loin dans cet article, nous verrons remark la FAA a utilisé la correspondance de chaînes floues pour identifier plusieurs pilotes ayant présenté un comportement frauduleux.
Cas d’utilisation intéressants de fuzzy matching
1) Correcteur orthographique (Supply : http://norvig.com/spell-correct.html )
De nos jours, la plupart d’entre nous ne prennent même pas la peine de trouver l’orthographe correcte lors de la rédaction d’un e-mail, telle est la confiance que nous accordons aux correcteurs orthographiques modernes.
Dans les paragraphes suivants, je tenterai de décrire les principes de base d’un easy correcteur orthographique.
L’équation suivante est utilisée pour trouver la correction la plus possible :
Ici, P(c) indique la fréquence à laquelle le mot « c » est utilisé dans la langue anglaise. Il peut être calculé en comptant le nombre de fois qu’un mot apparaît dans un grand corpus de texte. P(w|c) est la probabilité que l’auteur ait tapé le mauvais mot « w » au lieu du bon mot « c ». P(w|c) dépend de notre modèle d’erreur.
Les étapes suivantes permettent de connaître une orthographe corrigée :
i) L’étape floue : trouver tous les mots valides possibles ayant des distances d’édition (nombre minimal de substitutions, d’insertions ou de suppressions de caractères uniques requises pour transformer une chaîne en l’autre) de 1 et 2 par rapport au mot donné.
(ii) Le modèle d’erreur : supposons que les mots à une distance d’édition de 1 sont plus probables que les mots à une distance d’édition de 2 (normalement, quelque selected de plus sophistiqué devrait être utilisé pour le modèle d’erreur).
Puisque nous avons P(c) et P(w|c), nous pouvons trouver la correction la plus possible. En parcourant l’algorithme, nous pouvons voir qu’il mix simplement la correspondance de chaînes floues avec la théorie des probabilités pour construire un correcteur orthographique easy mais efficace.
2. Classification des données génomiques (Supply : http://www.ipcsit.com/vol30/019-ICNCS2012-G1021.pdf )
Dans ce travail, les auteurs étudient le problème consistant à tenter de déterminer le groupe d’une séquence génomique invisible. Les auteurs résolvent le problème de l’identification des groupes en utilisant une vaste base de données de séquences génomiques.
Ils essaient de faire correspondre la séquence de requête (la séquence inconnue) avec des candidats potentiels dans la base de données.
La correspondance exacte n’est pas très utile, automotive la séquence de requête correspond rarement exactement aux séquences du génome de la base de données. Pour résoudre ce problème, les auteurs effectuent une fuzzy matching entre la séquence de requête et la base de données génomique.
Les correspondances sont ensuite transmises en tant qu’entrées à un classificateur (SVM, rétropropagation, and many others.) qui détermine le groupe du génome.
J’espère que vous êtes convaincu que la fuzzy matching des noms est un sujet necessary et qu’il vaut la peine d’y consacrer du temps.
La logique traditionnelle est de nature binaire, c’est-à-dire qu’une affirmation est vraie ou fausse. Dans l’exemple précédent, un enregistrement de la Table1 correspondait exactement à un enregistrement de la Table2 ou non.
Au contraire, la logique floue indique dans quelle mesure une affirmation est vraie. Par exemple, des règles floues peuvent indiquer que les annonces sous Expedia correspondent potentiellement à la même annonce sous Priceline.
Comprendre la fuzzy matching avec un exemple du monde réel
Essayons de comprendre le idea de fuzzy matching en considérant un exemple concret. La determine 4 montre le schéma de base de données d’une petite organisation.
Si on vous confiait la tâche de joindre plusieurs tables au sein de ce schéma pour créer une vue distinctive pour les données shopper ou produit, remark procéderiez-vous ?
En théorie, si toutes les données étaient parfaitement propres (pas de doublons, pas de mots mal orthographiés, and many others.), nous pourrions effectuer l’opération de jointure en utilisant les clés primaires et secondaires appropriées. Cependant, les données du monde réel sont souvent très imparfaites, désordonnées et inexactes.
Une enquête menée par Gartner souligne que « la mauvaise qualité des données est l’une des principales raisons pour lesquelles 40 % de toutes les initiatives commerciales ne parviennent pas à atteindre les avantages escomptés » ( https://www.information.com/export/websites/information/widespread/property ). /pdf/DS_Gartner.pdf ).
Étant donné que les données du monde réel sont forcément compliquées, remark procéderions-nous pour joindre des tables individuelles ? Prenons l’exemple illustré à la determine 5.
Supposons que nous souhaitions joindre les tables « Purchasers » et « Commandes » en fonction de l’attribut customer_name. Nous pourrions utiliser une règle déterministe basée sur des correspondances strictes entre les enregistrements de la table1 et de la table2.
Par exemple, un nom de shopper « John Chambers » dans le tableau 1 correspond à toutes les occurrences du même nom de shopper (« John Chambers ») dans le tableau 2.
Bien que cette approche soit théoriquement valable, elle fonctionne rarement en pratique. Par exemple, si le nom « John Chambers » est mal orthographié comme « Jon Chamber » dans le tableau 2, la jointure résultante serait incohérente. Remark pourrions-nous résoudre un tel problème ?
La fuzzy matching peut être utile dans de tels scénarios.
L’un des cas d’utilisation les plus importants de la fuzzy matching survient lorsque nous souhaitons joindre des tables à l’aide du champ de nom.
Pour comprendre le problème de la fuzzy matching floue des noms, considérons le problème suivant.
Disons qu’une société de advertising envoie un questionnaire à de nombreuses personnes. Certaines personnes prennent le temps de remplir le questionnaire tandis que d’autres ne s’en donnent pas la peine. Désormais, la même entreprise envoie un questionnaire différent après 6 mois au même groupe de personnes.
L’entreprise stocke les réponses aux premier et deuxième questionnaires dans deux tableaux distincts. Pour fusionner les informations collectées, l’entreprise souhaiterait joindre les tables 1 et 2 en utilisant l’attribut « nom » comme clé primaire.
Cependant, rien ne garantit qu’une personne remplira exactement le même nom dans le premier et le deuxième questionnaire. Par exemple, une personne dont le nom officiel est « Dr. Jack Murphy » pourrait remplir « Jack » dans le premier questionnaire et « Dr Jack » dans le deuxième questionnaire. Les faire correspondre nécessite un ensemble de règles capables de gérer de légères variations dans le champ de nom. Ces ensembles de règles sont appelés règles floues et nous appelons ce processus Fuzzy Title Matching.
Formalisons le problème. Nous avons une base de données avec ‘n’ tables que nous souhaitons rejoindre en utilisant l’attribut title. Utiliser une règle stricte selon laquelle nous imposons que chaque caractère d’un nom dans la table1 doit correspondre exactement à chaque caractère d’un nom dans la table2 n’est pas pratique, comme le montre clairement l’exemple ci-dessus.
Par exemple, l’ensemble de règles que nous formulons devrait pouvoir faire correspondre le nom « Mike Daniel » dans le tableau 1 avec « Mike D », « Dr. » Mike’, ‘MikeDaniel’ and many others.
La correspondance de noms floue est-elle vraiment utile ? Une étude de cas sur l’utilisation de la correspondance de noms floue pour détecter la fraude
(Supply : https://dataladder.com/whitepapers/how-best-in-class-fuzzy-matching-solutions-work-combining-established-and-proprietary-algorithms/ )
Lorsqu’une base de données composée de 40 000 pilotes d’avion a été comparée à une base de données composée de personnes recevant des prestations d’invalidité de la sécurité sociale, les dossiers de quarante pilotes sont apparus dans les deux bases de données.
Cela signifiait que soit les individus mentaient sur leur maladie pour recevoir des prestations d’invalidité, soit ils volaient avec ces maladies, deux infractions punissables.
La logique floue est au cœur de cette opération puisque les noms des pilotes devaient correspondre sur plusieurs tables.
Il existe de nombreux algorithmes populaires qui peuvent être utilisés pour effectuer une correspondance de noms floue. La part suivante parle de certains de ces algorithmes populaires de correspondance de noms flous.
Algorithmes de correspondance de noms flous
1) Distance de Levenshtein :
La distance de Levenshtein est une métrique utilisée pour mesurer la différence entre 2 séquences de cordes.
Il nous donne une mesure du nombre d’insertions, de suppressions ou de substitutions de caractères uniques nécessaires pour transformer une chaîne en une autre.
Mathématiquement, on peut définir la distance de Levenshtein comme go well with :
Où tail (a) est une chaîne comprenant tous les caractères de la chaîne a à l’exclusion du premier caractère. D’après la définition, il est clair que la distance de Levenshtein fonctionne bien avec les noms mal orthographiés.
Par exemple, la distance de Levenshtein (le nombre d’insertions, de suppressions ou de substitutions d’un seul caractère) entre les chaînes JOHN (comme on l’écrit aux États-Unis) et JOHAN (comme on l’écrit au Japon, en Suède et en Norvège) ‘ est de 1 comme montré sur la Fig7.
L’inconvénient le plus évident de l’utilisation de la distance de Levenshtein est qu’elle ne prend en compte que la différence dans la manière dont nous épelons les mots.
Par exemple, la distance de Levenshtein entre les mots « ROBERT » et « BOBBY » est de 4. (REMARQUE : Bobby est le surnom de Robert)
2) L’algorithme Soundex :
Soundex est un algorithme phonétique utilisé pour rechercher des noms qui se ressemblent mais sont orthographiés différemment.
Il est le plus souvent utilisé pour les recherches dans les bases de données généalogiques.
L’algorithme Soundex génère un code à 4 chiffres nommé. (La web page Wikipédia https://en.wikipedia.org/wiki/Soundex explique bien l’algorithme Soundex)
Par exemple, les noms « Stuart » et « Stewart » produisent le même code Soundex S363.
3) Les algorithmes métaphone et double métaphone :
L’algorithme Metaphone est une amélioration par rapport à l’algorithme vanille Soundex, tandis que l’algorithme double Metaphone s’appuie sur l’algorithme Metaphone.
L’algorithme « double » Metaphone renvoie deux clés pour les mots qui ont plus d’une prononciation.
Considérons l’exemple suivant :
Soundex (« Phillip ») = P410
Soundex (« Fillipe ») = F410
Double métaphone (« Phillip ») = FLP
Double métaphone (« Fillipe ») = FLP
Nous pouvons clairement voir que l’algorithme Doublemetaphone est beaucoup plus robuste que l’algorithme Soundex.
Désavantages:
Un cas d’échec que j’ai rencontré a eu lieu lorsque j’ai utilisé le nom de Jésus (prononcé Haysoos en espagnol).
Double métaphone (‘Jésus’) = (‘JSS’, ‘ASS’)
Double métaphone (‘Haysoos’) = (‘HSS’, ‘ ‘)
4) Similitude cosinus :
Cosinus La similarité entre deux vecteurs non nuls est égale au cosinus de l’angle qui les sépare.
Si nous représentons chaque chaîne (nom) par un vecteur, nous pouvons comparer les chaînes en mesurant l’angle entre leurs représentations vectorielles correspondantes.
Si les vecteurs sont parallèles (theta=0 et cos(theta)=1) alors ils sont égaux les uns aux autres, cependant, s’ils sont orthogonaux (theta=90 degrés et cos(theta)=0), ils sont différents.
Comprenons les différentes étapes impliquées dans le calcul de la similarité cosinus entre deux mots avec un exemple easy. Exemple : Nom1 = « Johan », Nom2 = « Jean ».
i) Divisez les noms dans leurs représentations « n-gram » correspondantes.
ii) Vectorisez chaque n-gramme en utilisant une approach d’encodage. Les strategies de codage les plus couramment utilisées sont le codage par sac de mots ou le codage tf-idf.
iii) Calculez la similarité cosinusoïdale entre les vecteurs.
La determine 8 illustre toutes les étapes impliquées dans le calcul de la similarité cosinusoïdale entre les vecteurs.
Remarque : j’ai été assez surpris lorsque j’ai tapé « Ressources d’apprentissage automatique pour la fuzzy matching ». Pour une fois, je n’ai pas été inondé de centaines d’articles et de leurs référentiels GitHub correspondants.
Les personnes intéressées peuvent se référer au lien suivant : https://www.cs.utexas.edu/~ml/papers/marlin-dissertation-06.pdf et au référentiel GitHub correspondant. Il explique les mesures de similarité apprenables qui peuvent être entraînées pour effectuer un couplage, un regroupement et un blocage précis des enregistrements.
Vous envisagez une fuzzy matching pour votre produit ou votre answer ? Lis ça…
Cette part fournit quelques indications sur la façon dont vous pouvez utiliser la correspondance de chaînes floues pour améliorer le flux de travail existant dans votre produit ou answer.
Supposons que votre équipe commerciale ait du mal à déployer du contenu/des produits personnalisés pour des purchasers potentiels en raison d’une mauvaise gestion du stockage des données.
Votre meilleur pari est de créer une vue shopper unifiée qui aiderait votre équipe commerciale à atteindre ses objectifs. Vous décidez d’implémenter un ou plusieurs algorithmes de correspondance de chaînes floues pour faire le travail. Voici quelques factors que vous devez garder à l’esprit.
i) Temps et ressources requis :
en général, il est logique d’investir une quantité décente de temps et de ressources dans la configuration du logiciel de correspondance de chaînes floues en fonction de votre cas d’utilisation spécifique.
Des assessments unitaires rigoureux sont bénéfiques, surtout si votre cas d’utilisation exige une grande précision. La bonne nouvelle est qu’une fois la configuration du logiciel terminée, la majeure partie du flux de travail peut être automatisée.
En prenant l’exemple de la génération d’une vue shopper unifiée, le logiciel de fuzzy matching doit simplement être exécuté à intervalles réguliers pour garantir que votre vue shopper est mise à jour.
ii) Fiabilité : en supposant que vous ayez consacré le temps nécessaire à la configuration du logiciel, quelle serait sa fiabilité ? Presque tous les algorithmes de correspondance de chaînes floues sont voués à générer des fake positifs.
Cela signifie généralement une vérification manuelle des erreurs. Vous devez trouver le bon équilibre entre le nombre de fake positifs, la quantité de principal d’œuvre que vous pouvez vous permettre pour vérifier les erreurs et l’effet que les fake positifs auraient sur votre entreprise.
Par exemple, si des fake positifs amènent un shopper à recevoir une publicité pour une recette de pâtes au lieu d’une recette de pizza, vous êtes du bon côté.
Quelques bonnes pratiques et faits à considérer…
a) La correspondance de chaînes floues est un domaine largement étudié et de nouveaux algorithmes/logiciels sont périodiquement publiés. Il vaut la peine de garder les yeux et les oreilles ouverts aux nouveaux développements.
b) Même après des assessments rigoureux, vous obtiendrez forcément quelques fake positifs. Assurez-vous de ne pas utiliser de logiciel flou pour traiter des données sensibles.
c) La correspondance de chaînes floues rapporte les dividendes les plus élevés lorsque vous disposez d’un grand nombre de données qui, si elles sont correctement mises en correspondance, entraînent un avantage necessary, tandis que les fake positifs n’ont pas beaucoup d’significance.
Implémentation de la fuzzy matching dans différents langages de programmation
Voyons remark les algorithmes de Fuzzy Matching peuvent être implémentés dans différents langages de programmation.
Nous implémenterons la correspondance de chaînes floues dans divers langages de programmation sur l’ensemble de données du restaurant.
L’ensemble de données contient 864 enregistrements de eating places provenant des guides de eating places Fodor’s et Zagat qui contiennent 112 doublons. (Supply : https://www.cs.utexas.edu/customers/ml/riddle/information.html ).
Nous illustrons une software importante de la correspondance de chaînes floues, à savoir la détection des doublons . Par exemple : considérez la determine 10.
On voit bien que le premier et le deuxième enregistrement correspondent au même restaurant, de même, le troisième et le quatrième enregistrement correspondent au même restaurant. Notre objectif est de découvrir tous les doublons dans la base de données en utilisant la correspondance de chaînes floues.
Dans le processus d’implémentation de la détection des doublons à l’aide de divers langages de programmation, nous passons en revue certains des packages intégrés fournis par ces langages de programmation, à l’aide desquels presque toute la complexité est abstraite du programmeur.
Pour simplifier le problème, nous tenterons de détecter les doublons uniquement en utilisant le champ nom.
Correspondance de chaînes floues à l’aide de Python
Présentation de Fuzzywuzzy : Fuzzywuzzy est une bibliothèque Python utilisée pour la correspondance de chaînes floues. La métrique de comparaison de base utilisée par la bibliothèque Fuzzywuzzy est la distance de Levenshtein.
En utilisant cette métrique de base, Fuzzywuzzy fournit diverses API qui peuvent être directement utilisées pour la fuzzy matching. Passons en revue tout le pipeline de détection des doublons.
i) Prétraitement des données :
Puisque nous détectons les doublons en utilisant uniquement le champ « nom », lors de l’étape de prétraitement (nettoyage des données), nous convertissons le nom entier en minuscules et supprimons la ponctuation des noms. L’extrait de code de la determine 11 illustre ce processus.
ii) Création d’un index :
Une manière naïve de faire correspondre les enregistrements dans une desk consiste à comparer chaque enregistrement avec tous les autres enregistrements. Cependant, en utilisant cette méthode, le nombre de paires augmente quadratiquement, ce qui pourrait ralentir l’algorithme.
Nous utilisons le Python Document Linkage Toolkit à l’aide duquel plusieurs méthodes d’indexation telles que le blocage et l’indexation de quartier triée peuvent être implémentées. (REMARQUE : pour notre ensemble de données, nous avons calculé un index complet automotive il ne contient que 863 enregistrements)
L’extrait de code de la determine 12 illustre la création d’un index pour la comparaison des enregistrements.
iii) Identifier les doublons à l’aide de Fuzzywuzzy :
Les doublons ont été identifiés à l’aide de la méthode partial_ratio de Fuzzywuzzy. Étant donné deux chaînes str1(longueur n1) et str2(longueur n2) telles que n1 > n2, il calcule la distance de Levenshtein entre str2 et toutes les sous-chaînes de longueur n2 dans str1.
Grâce à cette méthode, nous avons identifié 201 doublons.
Correspondance de chaînes floues à l’aide de R
Tout d’abord, je dois avouer que je suis vierge R. Cependant, il s’avère que la programmation en R est extrêmement easy et intuitive. J’ai effectué les mêmes étapes, à savoir le prétraitement des données (conversion des noms en minuscules et suppression de la ponctuation) suivi d’une correspondance de noms floue à l’aide de la métrique de distance de Levenshtein.
L’extrait de code suivant illustre le pipeline utilisé pour la détection des doublons.
La ponctuation a été éliminée en utilisant la fonction gsub . Suite à cela, une matrice a été construite en utilisant la métrique de distance commonplace de Levenshtein entre les champs de nom.
Enfin, le nombre de doublons a été compté (si la distance de Levenshtein entre deux enregistrements est inférieure à 2, ils sont considérés comme des doublons).
L’algorithme détecte 164 enregistrements en double.
Remarque : L’implémentation ci-dessus n’est pas optimisée.
Correspondance de chaînes floues à l’aide de Java
Les choses étaient un peu plus difficiles en Java automotive il n’est pas spécifiquement conçu pour la science des données. Cependant, il existe de nombreux référentiels Github disponibles qui effectuent une correspondance de chaînes floues à l’aide de Java.
Le référentiel suivant https://github.com/xdrop/fuzzywuzzy contient une implémentation Java de la bibliothèque Python Fuzzywuzzy. Un exemple easy est présenté sur la determine 14.
REMARQUE : La fonction tokenSortRatio divise les chaînes en jetons, trie les jetons individuels et calcule la distance de Levenshtein entre eux.
Le bundle de similarité de chaînes Java ( https://github.com/tdebatty/java-string-similarity ) implémente un sure nombre d’algorithmes (distance d’édition de Levenshtein, Jaro-Winkler, LCS, and many others.).
Fuzzy matching sans utiliser de code
N’ayez crainte, Microsoft Excel et Stata peuvent vous aider à effectuer une correspondance de chaînes floues à l’aide de l’interface graphique.
Correspondance de chaînes floues à l’aide de Microsoft Excel
Les utilisateurs d’Excel connaissent peut-être la fonction RECHERCHEV utilisée pour rechercher des correspondances exactes entre les colonnes d’un tableau. Excel fournit également un complément de recherche floue utilisé pour effectuer une fuzzy matching entre les colonnes de la model de bureau.
Comme j’utilisais un système d’exploitation basé sur Linux au second de la rédaction de cet article de weblog, je n’ai pas pu utiliser le complément Fuzzy Lookup.
Cependant, la model Net de Microsoft Excel fournit un complément similaire appelé Exis Echo. Il possède une interface extrêmement easy, sélectionnez simplement le nombre souhaité de lignes parmi les colonnes que vous souhaitez faire correspondre et Exis Echo fait le reste.
Comme le montre la determine 17, les eating places portant les noms « hôtel bel-air » et « hôtel bel-air » sont identifiés comme des doublons (c’est-à-dire qu’ils sont placés dans le même groupe). Cependant, l’algorithme n’identifie pas « l’épicerie effective » et « l’épicerie effective » comme le même restaurant.
Le complément fournit plusieurs paramètres que nous pouvons ajuster pour notre cas d’utilisation spécifique.
Comparaison rapide des logiciels de fuzzy matching
Ce qui go well with est une comparaison des différents langages ou logiciels que j’ai utilisés pour implémenter la fuzzy matching.
J’ai attribué une observe sur 5, 5 étant la meilleure et 1 la moins bonne.
| Logiciel/Langue utilisé | Facilité d’utilisation | Évolutivité | Vitesse | Notice globale totale |
|---|---|---|---|---|
| Python | 4.0 | 4.0 | 3.0 | 11.0 |
| R. | 4.0 | 4.0 | 2.5 | 10.5 |
| Java | 2.0 | 3.0 | 5.0 | 10,0 |
| Microsoft Excel | 5.0 | 1,5 | 3.0 | 9.5 |
Mise à l’échelle de la mise en œuvre de la fuzzy matching
Jusqu’à présent, nous avons envisagé de traiter quelques centaines d’enregistrements à l’aide de la correspondance de chaînes floues. Cependant, dans le monde réel, nous traiterions des milliers, voire des centaines de milliers de paperwork.
Dans cette part, nous présenterons quelques strategies qui pourraient aider à faire évoluer notre algorithme de correspondance de chaînes floues.
Pour illustrer cela, j’ai utilisé un ensemble de données contenant un grand nombre de noms d’entreprises. Parcourons le code, examinons la fonction de chaque extrait de code et examinons la sortie correspondante.
La cellule ci-dessus cost les données dans une trame de données pandas. Nous pouvons voir que l’ensemble de données contient 1 040 569 entrées.
Certains prétraitements de données sont effectués dans Cell2. Les noms de sociétés sont convertis en minuscules et toute ponctuation en est supprimée.
Nous définissons également une liste de mots vides courants tels que « assn », « inc », and many others. que nous supprimons de la liste des noms de sociétés.
Dans Cell3, nous divisons les noms d’entreprise en n-grammes, puis nous vectorisons les noms d’entreprise à l’aide de la fonction Tf-idf. L’étape suivante consiste à calculer la similarité cosinus entre chaque paire de vecteurs dans tf_idf_matrix.
Il est essential de le faire efficacement pour garantir que l’approche soit bien évolutive.
Scikit-learn fournit une fonction intégrée pour calculer la similarité cosinusoïdale entre les vecteurs. Cependant, l’équipe ING Wholesale Banking Superior Analytics a créé une bibliothèque personnalisée appelée sparse_dot_topn pour calculer la similarité cosinus à l’aide de Cython (https://github.com/ing-bank/sparse_dot_topn).
Leur mise en œuvre améliore la rapidité d’environ 40 %. J’ai emprunté le code des cellules 4 et 5 sur le website Net suivant : https://bergvca.github.io/2017/10/14/super-fast-string-matching.html .
La matrice « correspondances » contient les indices et les scores de similarité grâce auxquels nous pouvons identifier les doublons. Étant donné que cet ensemble de données n’a pas été spécifiquement conçu pour la détection des doublons ou l’identification des fake positifs, il a déjà été nettoyé et ne contenait aucun doublon.
Remarque : j’ai téléchargé le code sur mon référentiel Github. https://github.com/Varghese-Kuruvilla/Fuzzy_String_Matching .
Je vous encourage à l’utiliser comme référence pour analyser de nouveaux ensembles de données et comprendre les bases de la correspondance de chaînes floues.
Problèmes/problèmes courants rencontrés avec la fuzzy matching et la answer
Dans cette part, je vais essayer de répondre à quelques questions que j’ai vues sur StackOverflow lors de la lecture de cet article de weblog. J’encourage les lecteurs à parcourir l’intégralité de l’article pour avoir une bonne compréhension globale de la correspondance de chaînes floues.
1) Remark calculer le rating en correspondance de chaînes floues ?
L’un des moyens les plus efficaces de calculer les scores d’un algorithme de correspondance de chaînes floues consiste à utiliser la similarité cosinus. La similarité cosinus entre deux vecteurs non nuls est simplement le cosinus de l’angle entre ces vecteurs.
Ainsi, deux chaînes similaires auraient un rating de similarité cosinus plus élevé que deux chaînes différentes. Le succès de cette méthode dépend de la manière dont les chaînes sont converties en leurs représentations vectorielles correspondantes.
Deux des méthodes les plus populaires pour faire de même sont : les extracteurs de fonctionnalités Bag-of-words (BOW) et TF-IDF.
Un extracteur de fonctionnalités BOW calcule la représentation vectorielle d’une chaîne en prenant en compte la fréquence de chaque mot dans le doc. Un inconvénient majeur de l’extracteur de fonctionnalités BOW est que des mots comme « le », « de », and many others. reçoivent un rating très élevé automotive ils apparaissent très fréquemment dans le doc.
TF-IDF tente de surmonter ce problème en utilisant des informations sur le nombre de fois que le mot apparaît dans le doc.
Un exemple manuscrit montrant chacune des étapes individuelles du calcul de la similarité cosinus est présenté dans la determine 8.
2) Correspondance de logique floue ( https://stackoverflow.com/questions/37978098/fuzzy-logic-matching )
Pour votre cas d’utilisation de listes de correspondance de noms d’entreprises, je vous suggère de passer en revue les factors suivants.
a) Attribut distinctive : tout d’abord, assurez-vous que vous ne pouvez pas faire de correspondance en utilisant un autre attribut distinctive comme une adresse, and many others. Un attribut distinctive simplifierait grandement le problème. Après vous être assuré que vous disposez uniquement de l’attribut de nom de société pour la correspondance, vous pouvez procéder aux étapes suivantes.
b) Prétraitement des données : supprimez les mots vides courants du texte. Certains traitements manuels, tels que la sélection des mots qui ne sont pas pertinents pour la liste des noms de sociétés parmi les mots les plus fréquents, s’avéreraient utiles.
c) Indexation : La comparaison de tous les enregistrements est une tâche coûteuse en termes de calcul. Une méthode d’indexation telle que l’indexation par bloc ou par voisinage trié peut être utilisée pour réduire le nombre de comparaisons à effectuer.
d) Fuzzy matching: une mesure telle que la distance de Levenshtein peut être utilisée pour calculer les scores entre des paires de chaînes. Plusieurs implémentations de la distance de Levenshtein sont couvertes dans le bundle python populaire Fuzzywuzzy.
Pour ce cas d’utilisation, je recommanderais d’utiliser les fonctions token_set_ratio ou partial_ratio.
3) Algorithme de recherche floue ( https://stackoverflow.com/questions/32337135/fuzzy-search-algorithm-approximate-string-matching-algorithm ) :
Le problème peut être décomposé en deux events :
- Choisir la bonne métrique de chaîne.
- Proposer une mise en œuvre rapide de la même selected.
Choisir la bonne métrique : la première partie dépend largement de votre cas d’utilisation. Cependant, je suggérerais d’utiliser une combinaison d’un rating basé sur la distance et d’un codage phonétique pour une plus grande précision, c’est-à-dire en calculant initialement un rating basé sur la distance de Levenshtein et plus tard en utilisant Metaphone ou Double Metaphone pour compléter les résultats.
Encore une fois, vous devez baser votre décision sur votre cas d’utilisation, si vous pouvez utiliser uniquement les algorithmes Metaphone ou Double Metaphone, vous n’avez pas à vous soucier beaucoup du coût de calcul.
Implémentation : une façon de limiter le coût de calcul consiste à regrouper vos données en plusieurs petits groupes en fonction de votre algorithme et à les charger dans un dictionnaire.
Par exemple, si vous pouvez supposer que votre utilisateur saisit correctement la première lettre du nom, vous pouvez stocker les noms basés sur cet invariant dans un dictionnaire.
Ainsi, si l’utilisateur saisit le nom « École nationale », vous devez calculer la métrique uniquement pour les noms d’école commençant par la lettre « N ».
Conclusion
J’espère que vous avez passé un bon second à lire sur la logique floue.
Nous avons d’abord passé en revue le idea de logique floue, leurs functions pratiques et cas d’utilisation, les éléments à prendre en compte si vous choisissez d’utiliser la fuzzy matching, les différents algorithmes utilisés pour implémenter la correspondance de chaînes floues et leur implémentation dans les langages de programmation populaires.
En tant qu’humains, nous sommes souvent incertains de nos décisions, c’est-à-dire que, de par notre nature même, nous sommes flous. Tant que nous restons flous, il est logique que les outils que nous concevons le soient également. Sur cette observe plutôt philosophique, je vous retrouverai dans le prochain article du weblog.
