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. 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)

• Coefficient de Dice

dice$(X,Y)={\frac {2|X\cap Y|}{|X|+|Y|}}$.

• Indice et distance de Jaccard ou de Tanimoto

jaccard$(X,Y)={\frac {|X\cap Y|}{|X\cup Y|}}$.

• Indice de Tversky (en)

tversky$_{\alpha ,\beta }(X,Y)={\frac {|X\cap Y|}{|X\cap Y|+\alpha |X\setminus Y|+\beta |Y\setminus X|}}$.

• Coefficient de recouvrement (en)

recouvrement$(X,Y)={\frac {|X\cap Y|}{\min(|X|,|Y|)}}$.

• Cosinus

cosinus$(X,Y)={\frac {|X\cap Y|}{\sqrt {|X||Y|}}}$.

Autres mesures

• Distance de Manhattan
• Distance de Jaro-Winkler
• Simple matching coefficient (en) (SMC)
• Distance de Hellinger ou Distance de Bhattacharyya
• divergence de Jensen-Shannon (en))
• distance tau de Kendall (en),
• Divergence de Kullback-Leibler
• TF-IDF

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. kitten → sitten (substitution de "s" à "k") sitten → sittin (substitution de "i" à "e") sittin → sitting (insertion de "g" à la fin).
Distance de Jaro-Winkler	Distance de Jaro entre MARTHA et MARHTA : $d_{j}={\frac {1}{3}}\left({\frac {m}{|s_{1}|}}+{\frac {m}{|s_{2}|}}+{\frac {m-t}{m}}\right)={\frac {1}{3}}\left({\frac {6}{6}}+{\frac {6}{6}}+{\frac {6-{\frac {2}{2}}}{6}}\right)=0.944$ $m$ est le nombre de caractères correspondants; $t$ 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

Notes et références

(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é

• Matrice de similarité
• Alignement de séquences
• Analyse de similitudes

Liens externes

• Matthieu Constant, « Similarité entre les mots », Master Informatique, Université Paris-Est Marne-la-Vallée, 2012 (consulté le 1^er décembre 2015)
• « Sam's string metrics ». Une collection de mesures de similarité, 2011.
• Carnegie Mellon University open source library.
• StringMetric project, une bibliothèque de mesures de similarité et d'algorithmes phonétiques, en langage Scala.
• Natural project, une bibliothèque de traitement de langage naturel, en JavaScript, comprenant les métriques usuelles.
• Hellotools, mesurer la similarité entre deux textes