Question Comparer les algorithmes de similarité


Je veux utiliser des fonctions de similarité de chaîne pour trouver des données corrompues dans ma base de données.

Je suis tombé sur plusieurs d'entre eux:

  • Jaro,
  • Jaro-Winkler,
  • Levenshtein,
  • Euclidienne et
  • Gramme,

Je voulais savoir quelle est la différence entre eux et dans quelles situations ils fonctionnent le mieux?


38
2018-03-23 15:43


origine


Réponses:


Expansion dans mon commentaire wiki-walk dans les errata et notant une partie de la littérature de base sur la comparabilité des algorithmes qui s'appliquent à des espaces problématiques similaires, explorons l'applicabilité de ces algorithmes avant de déterminer s'ils sont numériquement comparables.

De Wikipedia, Jaro-Winkler:

En informatique et statistique, la distance Jaro-Winkler   (Winkler, 1990) est une mesure de la similarité entre deux chaînes. C'est   une variante de la métrique de distance de Jaro (Jaro, 1989, 1995) et   principalement [citation requise] utilisée dans le domaine du couplage d’enregistrements   détection). Plus la distance entre Jaro et Winkler est élevée,   plus les cordes sont similaires. La mesure de distance de Jaro-Winkler est   Conçu et mieux adapté aux chaînes courtes telles que les noms de personnes. le   le score est normalisé tel que 0 équivaut à aucune similitude et 1 est un   correspondance exacte.

Distance Levenshtein:

En théorie de l’information et en informatique, la distance Levenshtein   est une métrique de chaîne pour mesurer la quantité de différence entre deux   séquences. La distance d'édition de terme est souvent utilisée pour désigner spécifiquement   à la distance de Levenshtein.

La distance Levenshtein entre deux chaînes est définie comme le minimum   nombre de modifications nécessaires pour transformer une chaîne en une autre, avec   les opérations d'édition autorisées sont l'insertion, la suppression ou   substitution d'un seul caractère. Il porte le nom de Vladimir   Levenshtein, qui a considéré cette distance en 1965.

Distance euclidienne:

En mathématiques, la distance euclidienne ou la métrique euclidienne est la   distance "ordinaire" entre deux points qu'on mesurerait avec un   règle, et est donné par la formule de Pythagore. En utilisant cette formule   en tant que distance, l'espace euclidien (ou même n'importe quel espace produit interne) devient   un espace métrique La norme associée est appelée norme euclidienne.   La littérature plus ancienne se réfère à la métrique comme métrique pythagoricienne.

Et Encodage Q ou N-gram:

Dans les domaines de la linguistique computationnelle et des probabilités, un n-gramme   est une suite contiguë de n éléments d'une séquence donnée de texte ou   discours. Les éléments en question peuvent être des phonèmes, des syllabes, des lettres,   mots ou paires de bases selon l'application. n-grammes sont   recueillies à partir d'un corpus de texte ou de discours.

Les deux noyaux   avantages des modèles n-gram (et des algorithmes utilisant   eux) sont la simplicité relative et la capacité à évoluer   augmenter n un modèle peut être utilisé pour stocker plus de contexte avec un   compromis spatio-temporel bien compris, permettant aux petites expériences de   évoluer très efficacement

Le problème est que ces algorithmes résolvent différents problèmes qui ont une applicabilité différente dans l'espace de tous les algorithmes possibles pour résoudre le problème. plus longue sous-séquence commune problème, dans vos données ou en greffant un utilisable métrique de ceux-ci. En fait, tous ne sont même pas métrique, comme certains d'entre eux ne satisfont pas le inégalité de triangle.

Au lieu de vous mettre en quatre pour définir un système douteux de détection de la corruption de données, Faites-le correctement: en utilisant sommes de contrôle et bits de parité pour vos données. N'essayez pas de résoudre un problème beaucoup plus difficile lorsqu'une solution plus simple suffira.


36
2018-03-29 21:48



La similarité des chaînes aide de nombreuses manières différentes. Par exemple

  • Google signifie-t-il que les résultats sont calculés en utilisant la similarité des chaînes?
  • La similarité de chaîne est utilisée pour corriger les erreurs OCR.
  • La similarité de chaîne est utilisée pour corriger les erreurs de saisie du clavier.
  • La similarité de chaîne est utilisée pour trouver la séquence la plus appropriée de deux ADN en bioinformatique.

Mais comme une taille ne convient pas à tous. Chaque algorithme de similarité de chaîne est conçu pour un usage spécifique, bien que la plupart d'entre eux soient similaires. Par exemple Levenshtein_distance est de savoir combien de char vous changez pour que deux chaînes soient égales.

kitten → sitten

Ici la distance est 1 changement de caractère. Vous pouvez donner différents poids à la suppression, à l'ajout et à la substitution. Par exemple, les erreurs d'OCR et les erreurs de clavier donnent moins de poids à certains changements. OCR (certains caractères sont très similaires aux autres), certains caractères du clavier sont très proches les uns des autres. La similarité des chaînes bioinformatiques permet beaucoup d'insertion.

Votre deuxième exemple de "Jaro-Winkler  la distance métrique est conçue et mieux adaptée aux chaînes courtes telles que les noms de personnes "

Par conséquent, vous devez garder à l’esprit votre problème.

Je veux utiliser des fonctions de similarité de chaîne pour trouver des données corrompues dans ma base de données.

Comment vos données sont corrompues? Est-ce une erreur de l'utilisateur, similaire à une erreur de saisie au clavier? Ou est-ce similaire aux erreurs OCR? Ou autre chose?


2
2018-03-29 20:36