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[modifier | modifier le code]

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[modifier | modifier le code]

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é[modifier | modifier le code]

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

(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^[1]

cosinus

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

.

Autres mesures

Exemple de quelques mesures[modifier | modifier le code]

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^[3]

Notes et références[modifier | modifier le code]

↑ ^{a et b} « Similarité entre les mots ».
↑ William Cohen, Pradeep Ravikumar et Stephen Fienberg, « A Comparison of String Distance Metrics for Name-Matching Tasks », IJCAI-03 Workshop on Information Integration,‎ 2003, p. 73–78 (lire en ligne).
↑ 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,‎ octobre 2009, 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é[modifier | modifier le code]

Liens externes[modifier | modifier le code]

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

[Const-1] {a et b} « 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,‎ 2003, 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,‎ octobre 2009, p. 1-9 (DOI 10.1109/BMEI.2009.5305137).

[1]

[2]

[3]