Similarités, Distances et Proximité

Gilles HUNAULT Angers, 1997

Contenu

1. Introduction  2
2. Définitions  3
3. Exemples  4
3.1 Exemples généraux  4
3.2 Cas où les éléments de E sont des vecteurs de 0/1  5
3.3 Cas où les éléments de E sont des comptages  6
3.4 Cas des tableaux de variables quantitatives  7
4. Modèles de fonctions de distances sur E  9
4.1 Cas où E est sans dissimilarité  9
4.2 Cas où E est avec dissimilarité  9
4.3 Distances sur lR^{n}  10
4.4 Distances induites  10
5. Distances et relations binaires  10
5.1 Distance induite par une relation binaire  10
5.2 Relation induite par une fonction numérique  10

1. Introduction

La notion de distance est une notion ”transversale” puisqu’elle peut s’appliquer à n’importe quel ”objet” : les distances de la vie quotidienne (comme la distance entre deux villes) sont là pour le montrer. En science, on trouve des distances partout : entre éléments d’un même ensemble (non forcément numérique), entre ensembles, entre fonctions, entre suites, entre classes ou centres de gravité de classes, voire même entre distances elles-mêmes.

Les distances jouent un rôle important en mathématiques car elles permettent de construire certaines topologies via la notion de limite, continuité. En biologie, c’est en particulier pour les classifications, les typologies est les comparaisons et les alignements que les distances sont utiles. En informatique théorique, elles permettent aussi de comparer des éléments, de les classer.

Nous commencerons par rappeler les définitions classiques des métriques et par donner des exemples simples et généraux avant de passer aux distances sur tableaux en 0/1 et sur tableaux de comptages et aux tableaux de variables quantitatives. Ensuite, des modèles généraux de construction de distances seront fournis avec, comme suite logique, la présentation des liens entre distances et relations binaires.

On notera que si au départ on dispose d’indices ou de coefficients numériques d pour quantifier les distances, on peut se ramener très facilement à un cas booléen (0 ou 1) en posant d_{bool}(x, y) = 0 si d(x, y) = 0 et 1 ailleurs.

2. Définitions

Soit E un ensemble quelconque, c’est à dire non forcément numérique. Soit f une fonction de E × E dans lR^{+}. f est donc positive ou nulle. Pour tous x, y, z et t dans E, on définit les termes suivants

f est d-nulle  ssi f(x, x) = 0
f est séparée  ssi f(x, y) = 0 ⇒ y = x
f est symétrique  ssi f(x, y) = f(y, x)
f est équidiagonale ssi f(x, x) = f(y, y)
f est sous-diagonale ssi f(x, y) ≤ f(x, x) = f(y, y)
f est triangulaire  ssi f(x, y) ≤ f(x, t) + f(t, y)
f est sous-maximale ssi f(x, y) ≤ max( {f(x, z), f(y, z)} )

Une similarité  est une fonction symétrique et sous-diagonale.
Une dissimilarité  est une fonction symétrique et d-nulle.
Une pseudo-métrique est un indice de dissimilarité triangulaire.
Une métrique  est une pseudo-métrique séparée.
Une ultramétrique  est une pseudo-métrique sous-maximale.

On utilise classiquement les termes écart et indice d’écart comme synonymes de pseudo-métrique, le mot distance comme synonyme de métrique. Dans certains ouvrages, on trouve les termes ”indice de (dis)similarité” ou ”coefficient de (dis)similarité” plutôt que ”(dis)similarité”.

Il est à noter qu’une ultramétrique est une distance particulière.

3. Exemples

3.1 Exemples généraux

La fonction nulle ν est définie par ν(x, x) = 0 pour tout x. Elle est d-nulle, symétrique, sous-diagonale, triangulaire et sous-maximale. Elle n’est pas séparée.

L’application égalitaire est la fonction δ telle que δ(x, x) = 0 et δ(x, y) = 1 pour y ≠ x. Elle est d-nulle, séparéee, symétrique, triangulaire. Elle n’est pas sous-diagonale.

Soit E un ensemble numérique. L’application (x, y) → |x−y| est une distance nommée distance usuelle sur E.

L’application (x, y) → |\frac{1}{x} − \frac{1}{y}| est une distance sur lR^{∗}.

L’application (x, y) → |arctangente(x − y)| est une distance sur lR^{∗}.

Si f et g sont deux fonctions intégrables,

(f, g) → ∫_{0}^{1} |f − g| est une distance.

(f, g) → ∫_{0}^{1} (|f − g| + |f′ − g′|) est une distance.
(f, g) → sup_{[0,1]} |f − g| est une distance.

Citons aussi les distances p-adiques qui utilisent la décomposition en base p, les distances d’éditions entre chaines de caractères, les distances entre prédicats, les distances entre suites numériques...

3.2 Cas où les éléments de E sont des vecteurs de 0/1

Ce cas est très important en biologie, en informatique, en statistiques car il correspond aux descriptions d’états en présence/absence, aux tables de vérité en vrai/faux, aux événements en réussite/échec... De nombreuses fonctions portent alors le nom d’indice. Afin de les comparer entre eux et pour de nombreux couples, certains indices sont normalisés à 1, ce qui signifie que 0 ≤ f(x, y) ≤ 1 pour tous x et y.

Soit I un ensemble fini de valeurs de cardinal n. Si x = (x_{i})_{i∈I} et y = (y_{i})_{i∈I} sont deux vecteurs de 0 et de 1, on définit classiquement les nombres et indices suivants où toutes les sommes sont prises pour i de 1 à n (uu est souvent jugé comme ”déterminant”).

uu le nombre de fois où x = 1 et y = 1  soit ∑ x_{i}y_{i}
zz le nombre de fois où x = 0 et y = 0  soit ∑(1 − x_{i})(1 − y_{i})
uz le nombre de fois où x = 1 et y = 0  soit ∑ x_{i}(1 − y_{i})
zu le nombre de fois où x = 0 et y = 1  soit ∑(1 − x_{i})y_{i}
ux le nombre de fois où x = 1  soit uu + uz = ∑ x_{i}
uy le nombre de fois où y = 1  soit uu + zu = ∑ y_{i}
zx le nombre de fois où x = 0  soit zu + zz = ∑(1 − x_{i})
zy le nombre de fois où y = 0  soit uz + zz = ∑(1 − y_{i})
n le nombre  ux + zx = uy + zy = uu + zz + uz + zu.

Notation Nom  Année Formule
I_{1} Jaccard 1908 uu/(uu + uz + zu)
I_{2}  Sokal-Michener 1958 (uu + zz)/p
I_{3}  Sokal-Sneath I  I_{2}/(2 − I_{2})
I_{4}  Czekanowski  1913 2I_{1}/(1 + I_{1})
I_{5}  Russel-Rao  1940 uu/p
I_{6}  Kulczynski  1927 uu(1/ux + 1/uy)/2
I_{7}  Sokal-Sneath II 1963 I_{1}/(2 − I_{1})
I_{8}  Ochiai  1957 \sqrt{I_{4}I_{6}}

L’indice I_{2} de Sokal-Michener est aussi nommé indice de Rogers-Tanimoto (1960). L’indice I_{4} de Czekanowski est aussi nommé indice de Dice (1945) ou encore indice de Sorensen (1948).

3.3 Cas où les éléments de E sont des comptages

Soit à nouveau I un ensemble fini de valeurs de cardinal n et soient maintenant x = (x_{i})_{i∈I} et y = (y_{i})_{i∈I} sont deux vecteurs d’entiers positifs ou nuls. On note d_{i} la différence x_{i} − y_{i}, s_{i} la somme x_{i} + y_{i}, r l’inverse de n, p_{i} le minimum de x_{i} et y_{i} et g_{i} le maximum de x_{i} et y_{i}. On utilise classiquement les indices suivants (toutes les sommes sont prises pour i de 1 à n).

Notation Nom  Année Formule
I_{9}  Czekanowski  1932 r ∑ |di|
I_{10}  Euclidienne moyenne  \sqrt{r ∑ di^{2}}
I_{11}  Lance-Williams  1966 r ∑(|di|/si)
I_{12}  Clark  1952 \sqrt{r ∑(|di|/si)^{2}}
I_{13}  Odum  1950 (∑ |di|)/(∑ si)
I_{14}  Kulczynski  (∑ m_{i}) / (∑ s_{i})
I_{15}  Marczewski-Steinhaus  (∑[d_{i}|) / (∑ g_{i})

I_{9} est aussi nommé indice de Haltenorth (1937), indice de Cain-Harrison (1958).

I_{13} est aussi nommé indice de Bray-Curtis (1957),

On remarquera que I_{14} = (1 − I_{13})/2 et que I_{15} = 2I_{13}/(1 + I_{13}).

3.4 Cas des tableaux de variables quantitatives

Il y a historiquement de nombreuses formules de distances (entre lignes) et de coefficients de liaison ou ”corrélations” (entre colonnes). Nous rappelons ici les plus importantes. L’application de formules en général prévues pour les colonnes du tableau des données (les ”variables” de la statistique classique) aux lignes du même tableau peut alors n’avoir aucun sens. Les distances traditionnelles entre lignes sont nommées

d_{e} Distance euclidienne usuelle (”plate”)
d_{ep} Distance euclidienne pondérée
d_{χ} Distance du χ^{2}
d_{m} Distance de l’écart moyen
d_{M} Distance de l’écart maximum

et les coefficients entre colonnes (sauf ρ_{D})

ρ Coefficient de corrélation linéaire usuel [de Pearson(-Bravais)]
ρ_{K} Coefficient de corrélation des rangs de Spearman
ρ_{S} Coefficient de corrélation des rangs de Kendall
ρ_{D} Coefficient de corrélation des divergences [de Clark]

Rappelons maintenant les formules. Soit X[i, j] un tableau de données où les n individus i sont en ligne et les p variables j sont en colonne. On note :

m_{j}  la moyenne de la colonne j, soit m_{j} = Σ_{i} X[i, j]/n,
σ_{j}  l’écart-type de la colone j soit σ_{j}^{2} = Σ_{i} (X[i, j]_{m}(j))^{2}/n,
s_{i.}  la somme de la ligne i  soit s_{i.} = Σ_{j} X[i, j],
s_{.j}  la somme de la colonne j  soit s_{.j} = Σ_{i} X[i, j],
r_{j}(a, b) le sens de j entre a et b,
r(i, j) le rang de X[i, j] pour j.

On rappelle que

\begin{aligned}r_{j}(a, b) & = & 1 & si X[a, j] > X[b, j], \\ r_{j}(a, b) & = & 0 & si X[a, j] = X[b, j], \\ r_{j}(a, b) & = & -1 & si X[a, j] < X[b, j]. \end{aligned}

Si a et b sont deux indices de lignes du tableau

\begin{aligned}d_{e}(a, b)^{2} & = & ∑_{j} (X[a, j] − X[b, j])^{2} \\ d_{ep}(a, b)^{2} & = & ∑_{j} w_{j} (X[a, j] − X[b, j])^{2} (souvent w_{j} = 1/σ_{j}^{2}) \\ d_{χ}(a, b)^{2} & = & ∑_{j} (X[a, j]/s_{a.} − X[b, j]/s_{b.})^{2} /s_{.j} \\ d_{m}(a, b) & = & ∑_{j} |X[a, j] − X[b, j]| /p \\ d_{M}(a, b) & = & Max_{j} \{ X[a, j] − X[b, j] \} \\ ρ_{D}(a, b) & = & (1/p) ∑_{j} \frac{X[a, j] − X[b, j]}{X[a, j] + X[b, j]} \end{aligned}

Si c et d sont deux indices de colonnes du tableau

\begin{aligned}ρ(c, d) & = & ∑_{i} ( X[i, c] − m_{c}) ( X[i, d] − m_{d}) /σ_{c}σ_{d} \\ ρ_{S}(c, d) & = & 1 − 6 ∑_{i} ( r(i, c) − r(i, d) )^{2} /n(n^{2} − 1) \\ ρ_{K}(c, d) & = & 2 ∑_{a<b} r_{c}(a, b)r_{d}(a, b)/n(n − 1) \end{aligned}

4. Modèles de fonctions de distances sur E

Si s est une similarité alors d telle que d(x, y) = s_{M} − s(x, y) est une dissimilarité où s_{M} = s(x, x) = s(y, y) désigne la valeurs de s sur la diagonale.

4.1 Cas où E est sans dissimilarité

Soit E un ensemble fini, et F l’ensemble des applications de E dans R. Soit f de E dans F. Soit p une fonction de poids sur E : p(x) noté p_{x} est positif ou nul et la somme des p_{x} vaut 1. Alors pour tout q réel supérieur ou égal à 1, l’application d définie par

d(A, B) = _{q} \sqrt{∑_{x∈E} p_{x}|f_{A}(x) − f_{B}(x)|^{q}}

est une distance, nommé distance de Minkowski discrète à l’ordre q relative au poids p.

Cas particulier : q=1, f(A) = χ_{A}, fonction caractéristique de A. Cette distance est nommée distance de la différence symétrique.

Autre cas particulier : q=2, f(x) = 1/\sqrt{p(A)} si x ∈ A. Cette distance est nommée distance d’Ochiai.

Autre cas particulier : distance du χ^{2} entre distributions de probabilité.

4.2 Cas où E est avec dissimilarité

Les distances associées sont alors plus compliquées que les distances précédentes. Nous nous contentons de citer deux distances : la distance de Hausdorff et la distance du maximum. On trouvera sur le web avec Google des articles présentant ces distances.

4.3 Distances sur lR^{n}

4.4 Distances induites

Si A est muni d’une distance d et si f est une fonction de I dans A alors l’application f_{d} telle que f_{d}(x, y) = d( f(x), f(y)_{)} transporte les propriétés de d. Si f est injective, f_{d} est aussi une distance. Ainsi (x, y) → |x^{2} − y^{2}| n’est pas une distance mais (x, y) → |x^{3} − y^{3}| en est une. Si d est une distance

(x, y) → min( \{1, d(x, y)\} ) et (x, y) → \frac{d(x, y)}{1 + d(x, y)} sont aussi des distances.

Si les d_{i} sont les distances, si les α_{i} sont des réels psositifs ou nuls, alors m = max(d_{i}), c = ∑ α_{i}d_{i} et r = \sqrt{∑ α_{i}d_{i}^{2}} sont aussi des distances.

5. Distances et relations binaires

5.1 Distance induite par une relation binaire

Soit R une relation binaire totale sur E et δR la fonction définie sur E × E par δR(x, y) = 0 si R(x, y) est vrai et δR(x, y) = 1 si R(x, y) est faux. Si R est réflexive alors à δR est équidiagonale (donc d-nulle). R est symétrique équivaut à δR est symétrique. De plus si R est transitive alors δR est sousmaximale donc triangulaire. Une relation d’équivalence RE induit donc une distance δRE nommée distance discrète induite par RE.

5.2 Relation induite par une fonction numérique

Si f est une fonction définie sur E × E à valeurs dans R et ε un réel positif ou nul, on dit que x et y sont ε-proches au sens f ssi |d(x, y)| ≤ ε. Soit R_{f,ε} la relation binaire définie par R_{f,ε}(x, y) est vraie ssi x et y sont ε-proches au sens de f et faux sinon.

Si f est une distance d, R_{f,ε} est alors réflexive, symétrique et transitive, c’est la relation d’équivalence nommée relation de proximité induite par d et pour toute fonction f, R_{f,0} est la relation classique d’égalité.