Mesure de similarité

En mathématiques et en informatique théorique, une mesure de similarité, plus exactement une mesure de distance entre mots, est une façon de représenter par un nombre la différence entre deux mots, ou plus généralement deux chaînes de caractères. Cela permet de comparer des mots ou chaines de façon simple et pratique. C'est donc une forme de distance mathématique et de métrique pour les chaînes de caractères.

En programmation, la mesure la plus simple et la plus courante est la distance de Levenshtein : elle est obtenue en comptant le nombre de modification de caractères individuels (ajout, retrait, ou changement) pour passer d'une chaîne à l'autre. Elle est utilisée dans la recherche approximative ou la comparaison de chaînes, aussi appelée en anglais fuzzy string searching.

Définition

Pour qu'une mesure de similarité soit une métrique de chaînes de caractères, elle doit satisfaire l'inégalité triangulaire. Le résultat fourni par une métrique est un nombre qui est une indication sur la distance, et peut varier d'un algorithme à l'autre.

La mesure la plus connue est une mesure rudimentaire appelée distance de Levenshtein, aussi connue sous le terme distance d'édition. Elle opère sur deux chaînes données, et retourne un nombre qui est le nombre d'insertions, suppression ou substitutions de caractère nécessaires pour transformer l'une des chaînes en l'autre. De telles distances ont été étendues pour s'appliquer également à la comparaison phonétique, à l'analyse lexicale, aux comparaisons grammaticales et autres.

Ce concept provient du concept informatique de similarité, notamment utilisé dans le cadre de tâche de classification non supervisée.

Applications

Les domaines d'application de mesures de similarité sont nombreux. Elles sont utilisées couramment dans les techniques d'analyse des données pour la détection de fraudes, comme l'empreinte digitale, la détection du plagiat, et également dans l'analyse génétique, l'analyse d'image, l'apprentissage automatique, la fusion d'ontologies et dans les bases de données notamment la déduplication et l'intégrité référentielle, enfin dans l'exploration de données, dans les interfaces Web comme les suggestions de complétion dans le style d'Ajax, intégration des représentations des connaissances.

Quelques mesures de similarité

Certaines mesures s'expriment de manière ensembliste[1]. Soient X et Y deux ensembles. On note |Z| le nombre d'éléments d'un ensemble Z. Toutes ces mesures de similarité ne conduisent pas à une métrique, elles ne respectent pas l'inégalité triangulaire (ex : le Cosinus)

dice.
jaccard.
  • Indice de Tversky (en)
tversky.
  • Coefficient de recouvrement (en)
recouvrement.
cosinus.

Autres mesures

Exemple de quelques mesures

Nom Exemple
Distance de Hamming "karolin" et "kathrin" sont à distance 3.
Distance de Levenshtein
et Distance de Damerau-Levenshtein
kitten et sitting sont à distance 3.
  1. kitten → sitten (substitution de "s" à "k")
  2. sitten → sittin (substitution de "i" à "e")
  3. sittin → sitting (insertion de "g" à la fin).
Distance de Jaro-Winkler Distance de Jaro entre MARTHA et MARHTA :
  • est le nombre de caractères correspondants;
  • est le nombre de transpositions (ici seulement H, T).

Le choix de la mesure dépend de la nature des données et des observations que l'on veut réaliser[3]

Notes et références

  1. « Similarité entre les mots ».
  2. William Cohen, Pradeep Ravikumar et Stephen Fienberg, « A Comparison of String Distance Metrics for Name-Matching Tasks », IJCAI-03 Workshop on Information Integration, , p. 73–78 (lire en ligne).
  3. ShengLi Tzeng, Han-Ming Wu et Chun-Houh Chen, « Selection of Proximity Measures for Matrix Visualization of Binary Data », Biomedical Engineering and Informatics, 2009. BMEI '09. 2nd International Conference on, , p. 1-9 (DOI 10.1109/BMEI.2009.5305137).
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « String metric » (voir la liste des auteurs).

Article lié

Liens externes

  • Portail de l'informatique théorique
  • Portail des mathématiques
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.