Mesure de similarité

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.

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.

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)

• Coefficient de Dice

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

• Indice et distance de Jaccard ou de Tanimoto

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

• Indice de Tversky (en)

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

• Coefficient de recouvrement (en)

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

• Cosinus[1]

cosinus${\displaystyle (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[2]

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 : ${\displaystyle 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}$ ${\displaystyle m}$ est le nombre de caractères correspondants; ${\displaystyle 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[3]

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

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

• Portail de l'informatique théorique
• Portail des mathématiques