% dist.tex
\documentclass[12pt,a4paper]{article}
\parindent 0cm
\parskip   0.5 cm
%
\renewcommand{\thesection}{\arabic{section}.}
\renewcommand{\thesubsection}{\arabic{section}.\arabic{subsection}}
\newcommand{\cmt}[1]{}
\newcommand{\tdnu}[1]{\textit{#1}}
%
\def\N{\mbox{I\hspace{-0.11em}N}}
\def\Z{\mbox{Z\hspace{-0.35em}Z}}
\def\Q{\mbox{l\hspace{-0.43em}Q}}
\def\R{\mbox{l\hspace{-0.11em}R}}
\def\C{\mbox{l\hspace{-0.43em}C}}
\def\rb{{\textsf{R}}}
\def\dr{\delta_\rb}
\def\rd{{\textsf{R}_{d,\varepsilon}}}
\def\rf{{\textsf{R}_{f,\varepsilon}}}
\def\rz{{\textsf{R}_{f,0}}}
\def\re{{\textsf{RE}}}
\def\de{\delta_\re}
\def\pde{{\mathcal{P}}(E)}
\def\ctdn{\hspace{0.5cm}}
\begin{document}
\title{Similarit\'{e}s, Distances et Proximit\'{e}}
\author{Gilles HUNAULT}
\date{Angers, 1997}
\maketitle
%
\thispagestyle{empty}
\section*{Contenu}

\begin{tabular}{llr} \\
1.  & \tdnu{Introduction}         & \hspace{2cm} \textsf{\pageref{intr}} \\[0.3cm]
2.  & \tdnu{D\'{e}finitions}      & \textsf{\pageref{defs}} \\[0.3cm]
3.  & \tdnu{Exemples}             & \textsf{\pageref{xmps}} \\[0.3cm]
    & 3.1  {Exemples g\'{e}n\'{e}raux} & \textsf{\pageref{xgen}} \\
    & 3.2  {Cas o\`{u} les \'{e}l\'{e}ments de $E$ sont des vecteurs de 0/1} & \textsf{\pageref{vect}}\\
    & 3.3  {Cas o\`{u} les \'{e}l\'{e}ments de $E$ sont des comptages} & \textsf{\pageref{compt}}\\
%    & 3.4  {Cas des tableaux de variables qualitatives} & \textsf{\pageref{qual}}\\
    & 3.4  {Cas des tableaux de variables quantitatives} & \textsf{\pageref{quant}}\\[0.3cm]
4.  & \tdnu{Mod\`{e}les de fonctions de distances sur $E$} & \textsf{\pageref{modl}} \\[0.3cm]
    & 4.1  {Cas o\`{u} E est sans dissimilarit\'{e}} & \textsf{\pageref{nodis}}\\
    & 4.2  {Cas o\`{u} E est avec dissimilarit\'{e}} & \textsf{\pageref{whdis}}\\
    & 4.3  {Distances sur $\R^n$}                    & \textsf{\pageref{disrn}}\\
    & 4.4  {Distances induites}                      & \textsf{\pageref{disind}}\\[0.3cm]
5.  & \tdnu{Distances et relations binaires} & \textsf{\pageref{relb}}\\[0.3cm]
    & 5.1  {Distance induite par une relation binaire} & \textsf{\pageref{drelb}} \\
    & 5.2  {Relation induite par une fonction num\'{e}rique} & \textsf{\pageref{rfnum}}\\
\end{tabular}\\
%
\newpage
%
\section{Introduction} \label{intr}
%

La notion de $distance$ est une notion "transversale" puisqu'elle peut s'appli-quer
\`{a} n'importe quel "objet"~: les distances de la vie quotidienne (comme la distance entre
deux villes) sont l\`{a} pour le
montrer. En science, on trouve des distances partout : entre \'{e}l\'{e}ments
d'un m\^{e}me ensemble (non forc\'{e}ment num\'{e}rique),
entre ensembles, entre fonctions, entre suites, entre classes ou centres de gravit\'{e} de
classes, voire m\^{e}me entre distances elles-m\^{e}mes.

Les distances jouent un r\^{o}le important en math\'{e}matiques car elles permettent
de construire certaines topologies via la notion de limite, continuit\'{e}.
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\'{e}orique, elles permettent aussi
de comparer des \'{e}l\'{e}ments, de les classer.

Nous commencerons par rappeler les d\'{e}finitions classiques des m\'{e}triques et
par donner des exemples simples et g\'{e}n\'{e}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\`{e}les g\'{e}n\'{e}raux
de construction de distances seront fournis avec, comme suite logique, la
pr\'{e}sentation des liens entre distances et relations binaires.
% pour finir par une application aux logiques multivalu\'{e}es.

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

\newpage
%
\section{D\'{e}finitions} \label{defs}
%
Soit $E$ un ensemble quelconque, c'est \`{a} dire non forc\'{e}ment num\'{e}rique.
Soit $f$ une fonction de $E\times E$ dans $\R^+$.
$f$ est donc positive ou nulle. Pour tous $x,y,z$ et $t$ dans $E$, on d\'{e}finit les
termes suivants

\begin{center}
\begin{tabular}{lll}
\hspace{0.2cm}$f$ est \hspace{0.2cm}\textit{d-nulle}           & ssi & $f(x,x)=0$ \\
\hspace{0.2cm}$f$ est \hspace{0.2cm}\textit{s\'{e}par\'{e}e}   & ssi & $f(x,y)=0 \Rightarrow y=x$ \\
\hspace{0.2cm}$f$ est \hspace{0.2cm}\textit{sym\'{e}trique}    & ssi & $f(x,y)=f(y,x)$  \\
\hspace{0.2cm}$f$ est \hspace{0.2cm}\textit{\'{e}quidiagonale} & ssi & $f(x,x)=f(y,y)$  \\
\hspace{0.2cm}$f$ est \hspace{0.2cm}\textit{sous-diagonale}    & ssi & $f(x,y) \leq f(x,x)=f(y,y)$  \\
\hspace{0.2cm}$f$ est \hspace{0.2cm}\textit{triangulaire}      & ssi & $f(x,y) \leq f(x,t)+f(t,y)$ \\
\hspace{0.2cm}$f$ est \hspace{0.2cm}\textit{sous-maximale}     & ssi & $f(x,y) \leq max(\ \{f(x,z),f(y,z)\}\ )$
\end{tabular}
\end{center}

{%\parskip  0.3 cm
\begin{tabular}{ll}
Une \textbf{similarit\'{e}}  &
    est une fonction sym\'{e}trique et sous-diagonale.\\
Une \textbf{dissimilarit\'{e}} &
    est une fonction sym\'{e}trique et d-nulle.\\
Une \textbf{pseudo-m\'{e}trique} &
    est un indice de dissimilarit\'{e} triangulaire.\\
Une \textbf{m\'{e}trique} &
    est une pseudo-m\'{e}trique s\'{e}par\'{e}e.\\
Une \textbf{ultram\'{e}trique} &
    est une pseudo-m\'{e}trique sous-maximale.
\end{tabular}
}% fin de parskip 0.3 cm

On utilise classiquement les termes \textbf{\'{e}cart} et
\textbf{indice d'\'{e}cart} comme synonymes de pseudo-m\'{e}trique,
le mot \textbf{distance} comme synonyme de m\'{e}trique.
Dans certains ouvrages, on trouve les termes "indice de (dis)similarit\'{e}"
ou "coefficient de (dis)similarit\'{e}" plut\^{o}t que "(dis)similarit\'{e}".

Il est \`{a} noter qu'une ultram\'{e}trique est une distance particuli\`{e}re.
\newpage
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% non utile pour un expos\'{e} en info ou biologie
%
\cmt{
Si de plus $E$ est un espace vectoriel sur $\R$, on rajoute les d\'{e}finitions suivantes,
pour $f$ de $E\times E$ dans $\R$, $\alpha$ et $\beta$ dans $\R$,
$x_1,x_2,y_1$ et $y_2$ dans $E$

\begin{center}
\begin{tabular}{lll}
\hspace{0.2cm}$f$ est \hspace{0.2cm}\textit{d\'{e}finie positive}      & ssi & $f(x,x)\geq 0$ et $(\ f(x,x)=0\Leftrightarrow x=0\ )$ \\
\hspace{0.2cm}$f$ est \hspace{0.2cm}\textit{lin\'{e}aire \`{a} gauche} & ssi &
   $f(\alpha x_1+\beta x_2,y)=\alpha f(x_1,y) + \beta f(x_2,y)$ \\
\hspace{0.2cm}$f$ est \hspace{0.2cm}\textit{lin\'{e}aire \`{a} droite} & ssi &
   $f(x,\alpha y_1+\beta y_2)=\alpha f(x,y_1) + \beta f(x,y_2)$ \\
\hspace{0.2cm}$f$ est \hspace{0.2cm}\textit{bi-lin\'{e}aire} & ssi & $f$ est lin\'{e}aire \`{a} droite et \`{a} gauche \\
\end{tabular}
\end{center}

Un \textbf{produit scalaire} est une fonction bilin\'{e}aire sym\'{e}trique d\'{e}finie positive.
Si $f$ est un produit scalaire, l'application $(x,y)\to\sqrt{f(x-y),f(x-y)}$
est nomm\'{e}e distance induite par $f$.

Une distance est \textbf{euclidienne} s'il existe un produit scalaire dont elle
est la distance induite.
}
%
\section{Exemples} \label{xmps}

\subsection {Exemples g\'{e}n\'{e}raux}  \label{xgen}

La fonction nulle $\nu$ est d\'{e}finie par $\nu(x,x)=0$ pour tout $x$.
Elle est d-nulle, sym\'{e}trique, sous-diagonale,
triangulaire et sous-maximale. Elle n'est pas s\'{e}par\'{e}e.

L'application \'{e}galitaire est la fonction $\delta$ telle que
$\delta(x,x)=0$ et $\delta(x,y)=1$ pour $y\neq x$. Elle est d-nulle,
s\'{e}par\'{e}ee, sym\'{e}trique, triangulaire.
Elle n'est pas sous-diagonale.
% Elle n'est pas ??? triangulaire d\`{e}s que $E$
% a plus de deux \'{e}l\'{e}ments.

Soit $E$ un ensemble num\'{e}rique.
L'application $(x,y)\to |x-y|$ est une distance
nomm\'{e}e \textit{distance usuelle} sur $E$.

L'application $(x,y)\to \left|\displaystyle \frac{1}{x} -\displaystyle \frac{1}{y} \right|$
est une distance sur $\R^*$.

L'application $(x,y)\to |arctangente(x-y)|$
est une distance sur $\R^*$.

Si $f$ et $g$ sont deux fonctions int\'{e}grables,

\hspace{2cm} $(f,g) \to \displaystyle \int_0^1\ |f-g|$ est une distance.

\hspace{2cm} $(f,g) \to \displaystyle \int_0^1\ (|f-g|+|f'-g'|)$ est une distance.

\hspace{2cm} $(f,g) \to \displaystyle \sup_{[0,1]} |f-g|$ est une distance.

Citons aussi les
distances $p$-adiques qui utilisent la d\'{e}composition en base $p$, les
distances d'\'{e}ditions entre chaines de caract\`{e}res, les
distances entre pr\'{e}dicats, les distances entre suites num\'{e}riques...
\newpage
\subsection {Cas o\`{u} les \'{e}l\'{e}ments de $E$ sont des vecteurs de 0/1}\label{vect}

Ce cas est tr\`{e}s important en biologie, en informatique, en statistiques car
il correspond aux descriptions d'\'{e}tats en pr\'{e}sence/absence,
aux tables de v\'{e}rit\'{e} en vrai/faux, aux \'{e}v\'{e}nements
en r\'{e}ussite/\'{e}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\'{e}s \`{a} 1,
ce qui signifie que $0\leq f(x,y) \leq 1$ pour tous $x$ et $y$.
% La valeur de $f$ est alors souvent affich\'{e}e comme un
% pourcentage (m\^{e}me si ce n'en pas un).

Soit $I$ un ensemble fini de valeurs de cardinal $n$.
Si $x=(x_i)_{i\in I}$ et $y=(y_i)_{i\in I}$ sont deux vecteurs de 0 et de 1,
on d\'{e}finit classiquement les nombres et indices suivants
o\`{u} toutes les sommes  sont prises pour $i$ de 1 \`{a} $n$
($uu$ est souvent jug\'{e} comme "d\'{e}terminant").

\begin{center}
\begin{tabular}{cclll}
&$uu$ & le nombre de fois o\`{u} & $x=1$ et $y=1$ & soit $\sum x_iy_i$ \\
&$zz$ & le nombre de fois o\`{u} & $x=0$ et $y=0$ & soit $\sum (1-x_i)(1-y_i)$\\
&$uz$ & le nombre de fois o\`{u} & $x=1$ et $y=0$ & soit $\sum x_i(1-y_i)$\\
&$zu$ & le nombre de fois o\`{u} & $x=0$ et $y=1$ & soit $\sum (1-x_i)y_i$\\
&$ux$ & le nombre de fois o\`{u} & $x=1$          & soit $uu+uz=\sum x_i$ \\
&$uy$ & le nombre de fois o\`{u} & $y=1$          & soit $uu+zu=\sum y_i$ \\
&$zx$ & le nombre de fois o\`{u} & $x=0$          & soit $zu+zz=\sum (1-x_i)$ \\
&$zy$ & le nombre de fois o\`{u} & $y=0$          & soit $uz+zz=\sum (1-y_i)$ \\
&$n$  & le nombre                & $ux+zx$ = $uy+zy$  & = $uu+zz+uz+zu$.
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{llll}
\hspace{-0.2cm}\textsf{Notation} & \textsf{Nom}
  &\hspace{-0.2cm}\textsf{Ann\'{e}e} &\hspace{-0.2cm} \textsf{Formule} \\
$I_1$ \hspace{0.8cm}    & 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_4I_6}$\\
\end{tabular}
\end{center}

L'indice $I_2$ de Sokal-Michener est aussi nomm\'{e} indice de Rogers-Tanimoto (1960). \\
L'indice $I_4$ de Czekanowski est aussi nomm\'{e} indice de Dice (1945) ou encore
indice de Sorensen (1948).
\newpage
%
\subsection {Cas o\`{u} les \'{e}l\'{e}ments de $E$ sont des comptages} \label{compt}
%
Soit \`{a} nouveau $I$ un ensemble fini de valeurs de cardinal $n$ et
soient maintenant
$x=(x_i)_{i\in I}$ et $y=(y_i)_{i\in I}$ sont deux vecteurs d'entiers
positifs ou nuls. On note $d_{i}$ la diff\'{e}rence $x_i-y_i$,
$s_{i}$ la somme $x_i+y_i$, $r$ l'inverse de $n$, % : $r=1/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 \`{a} $n$).
%
\begin{center}
\begin{tabular}{llll}
\hspace{-0.2cm}\textsf{Notation} & \hspace{-0.2cm}\textsf{Nom}
  &\hspace{-0.2cm}\textsf{Ann\'{e}e} &\hspace{-0.2cm} \textsf{Formule} \\[0.3cm]
$I_9$   \hspace{0.8cm} & Czekanowski          & 1932 & $r\sum |di|$\\[0.3cm]
$I_{10}$ & Euclidienne moyenne                &      & $\sqrt{r\sum di^2}$\\[0.3cm]
$I_{11}$ & Lance-Williams \hspace{0.8cm}      & 1966 & $r\sum (|di|/si)$\\[0.3cm]
$I_{12}$ & Clark                & 1952 & $\sqrt{r\sum (|di|/si)^2}$\\[0.3cm]
$I_{13}$ & Odum                 & 1950 \hspace{0.8cm}& $(\sum |di|)/(\sum si)$\\[0.3cm]
$I_{14}$ & Kulczynski           &      & $(\sum m_i)\ /\ (\sum s_i)$\\[0.3cm]
$I_{15}$ & Marczewski-Steinhaus &      & $(\sum [d_i|)\ /\ (\sum g_i)$\\[0.3cm]
\end{tabular}
\end{center}

$I_9$ est aussi nomm\'{e} indice de Haltenorth (1937),
indice de Cain-Harrison (1958).

$I_{13}$ est aussi nomm\'{e} indice de Bray-Curtis (1957),

On remarquera que $I_{14}$ = $(1-I_{13})/2$ et que
$I_{15}$ = $2I_{13}/(1+I_{13})$.
%
\newpage
%\subsection {Cas des tableaux de variables qualitatives} \label{qual}
%\newpage
%
\subsection {Cas des tableaux de variables quantitatives} \label{quant}
%
Il y a historiquement de nombreuses formules de distances (entre lignes) et de coefficients
de liaison ou "corr\'{e}lations" (entre colonnes).
Nous rappelons ici les plus importantes.
L'application de formules en g\'{e}n\'{e}ral pr\'{e}vues pour les colonnes du
tableau des donn\'{e}es (les "variables" de la statistique classique) aux lignes
du m\^{e}me tableau peut alors n'avoir aucun sens.
%
Les distances traditionnelles entre lignes sont nomm\'{e}es

\begin{tabular}{cll}
\hspace{1cm} & $d_e$    & Distance euclidienne usuelle ("plate")\\
 & $d_{ep}$    & Distance euclidienne pond\'{e}r\'{e}e \\
 & $d_\chi$ & Distance du $\chi^2$ \\
 & $d_m$    & Distance de l'\'{e}cart moyen \\
 & $d_M$    & Distance de l'\'{e}cart maximum \\
\end{tabular}

et les coefficients entre colonnes (sauf $\rho_D$)

\begin{tabular}{cll}
\hspace{1cm} & $\rho$    & Coefficient de corr\'{e}lation lin\'{e}aire usuel $[$de Pearson(-Bravais)$]$\\
             & $\rho_K$  & Coefficient de corr\'{e}lation des rangs de Spearman\\
             & $\rho_S$  & Coefficient de corr\'{e}lation des rangs de Kendall\\
             & $\rho_D$  & Coefficient de corr\'{e}lation des divergences $[$de Clark$]$\\
\end{tabular}

%
Rappelons maintenant les formules.
%Soit $X=(X[i,j])_{i=1..n,i=1..p}$ un tableau de donn\'{e}es o\`{u} les
Soit $X[i,j]$ un tableau de donn\'{e}es o\`{u} les
$n$ individus $i$ sont en ligne et les $p$ variables $j$ sont en colonne.
On note~:

\begin{tabular}{lll}
\hspace{1cm}$m_j$      & la moyenne de la colonne $j$,     & soit $m_j=\Sigma_i\ X[i,j]/n$,\\[0.2cm]
\hspace{1cm}$\sigma_j$ & l'\'{e}cart-type de la colone $j$ & soit $\sigma_j^2=\Sigma_i\ (X[i,j]_m(j))^2/n$,\\[0.2cm]
\hspace{1cm}$s_{i.}$   & la somme de la ligne $i$          & soit $s_{i.}=\Sigma_j\ X[i,j]$,\\[0.2cm]
\hspace{1cm}$s_{.j}$   & la somme de la colonne $j$        & soit $s_{.j}=\Sigma_i\ X[i,j]$,\\[0.2cm]
\hspace{1cm}$r_j(a,b)$ & le sens de $j$ entre $a$ et $b$,\\[0.2cm]
\hspace{1cm}$r(i,j)$   & le rang de $X[i,j]$ pour $j$.     \\[0.2cm]
\end{tabular}

On rappelle que

\begin{tabular}{clcrl}
\hspace{1cm}  & $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{tabular}
\newpage
Si $a$ et $b$ sont deux indices de lignes du tableau

\begin{tabular}{clcl} \hspace{1cm}
 & $d_e(a,b)^2$    & = & $\sum_j\ \left(X[a,j]-X[b,j]\right)^2$\\[0.3cm]
 & $d_{ep}(a,b)^2$ & = & $\sum_j\ w_j\left(X[a,j]-X[b,j]\right)^2$ (souvent $w_j=1/\sigma_j^2$)\\[0.3cm]
 & $d_\chi(a,b)^2$ & = & $\sum_j\ \left(X[a,j]/s_{a.}-X[b,j]/s_{b.}\right)^2/s_{.j}$\\[0.3cm]
 & $d_m(a,b)$      & = & $\sum_j\ \left|X[a,j]-X[b,j]\right|/p$\\[0.3cm]
 & $d_M(a,b)$      & = & $Max_j\ \left\{\ X[a,j]-X[b,j]\ \right\}$ \\[0.3cm]
 & $\rho_D(a,b)$   & = & $(1/p)\ \sum_j\ \displaystyle\frac{X[a,j]-X[b,j]}{X[a,j]+X[b,j]}$ \\
\end{tabular}

Si $c$ et $d$ sont deux indices de colonnes du tableau

\begin{tabular}{clcl} \hspace{1cm}
 & $\rho(c,d)$   & = & $\sum_i\ \left(\,X[i,c]-m_c\,\right)\left(\,X[i,d]-m_d\,\right)/\sigma_c\sigma_d$\\[0.2cm]
 & $\rho_S(c,d)$ & = & $1-6\sum_i \left(\,r(i,c)-r(i,d)\,\right)^2/n(n^2-1)$\\[0.2cm]
 & $\rho_K(c,d)$ & = & $2\displaystyle\sum_{a<b} r_{c}(a,b)r_{d}(a,b)/n(n-1)$\\
\end{tabular}

\newpage
\section {Mod\`{e}les de fonctions de distances sur $E$} \label{modl}
%
Si $s$ est une similarit\'{e}
alors $d$ telle que $d(x,y)=s_M - s(x,y)$ est une dissimilarit\'{e}
o\`{u} $s_M=s(x,x)=s(y,y)$ d\'{e}signe la valeurs de $s$ sur la diagonale.
%
\subsection{Cas o\`{u} E est sans dissimilarit\'{e}}\label{nodis}
%
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\'{e}
$p_x$ est positif ou nul et la somme des $p_x$ vaut 1. Alors
pour tout $q$ r\'{e}el sup\'{e}rieur ou \'{e}gal \`{a} 1,
l'application $d$ d\'{e}finie par

$$d(A,B) = \sqrt[q]{\displaystyle \sum_{x\in E} p_x|f_A(x)-f_B(x)|^q}$$

est une distance, nomm\'{e} distance de $Minkowski$ discr\`{e}te \`{a} l'ordre $q$ relative au
poids $p$.

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

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

Autre cas particulier : distance du $\chi^2$ entre distributions de probabilit\'{e}.

\subsection{Cas o\`{u} E est avec dissimilarit\'{e}}\label{whdis}

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

\subsection{Distances sur $\R^n$}\label{disrn}

\subsection{Distances induites}\label{disind}

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\'{e}t\'{e}s de $d$.
Si $f$ est injective, $f_d$ est aussi une distance.
Ainsi $(x,y) \to |x^2-y^2|$ n'est pas une distance mais
$(x,y) \to |x^3-y^3|$ en est une.
%
Si $d$ est une distance
$(x,y) \to min(\ \{1,d(x,y)\}\ )$ et
$(x,y) \to \displaystyle \frac{d(x,y)}{1+d(x,y)}$
sont aussi des distances.
%
Si les $d_i$ sont les distances, si les $\alpha_i$ sont des r\'{e}els
psositifs ou nuls, alors $m=max({d_i})$,
$c=\sum \alpha_id_i$ et $r=\sqrt{\sum \alpha_id_i^2}$ sont aussi
des distances.
%
\section{Distances et relations binaires} \label{relb}
%
\subsection{Distance induite par une relation binaire} \label{drelb}
%
Soit $\rb$ une relation binaire totale sur $E$ et $\dr$ la fonction
d\'{e}finie sur $E\times E$ par $\dr(x,y)=0$ si $\rb(x,y)$ est vrai
et $\dr(x,y)=1$ si $\rb(x,y)$ est faux.
Si $\rb$ est r\'{e}flexive alors \`{a} $\dr$ est \'{e}quidiagonale (donc d-nulle).
$\rb$ est sym\'{e}trique \'{e}quivaut \`{a} $\dr$ est sym\'{e}trique. De plus si
$\rb$ est transitive alors $\dr$ est sous-maximale donc triangulaire.
Une relation d'\'{e}quivalence $\re$ induit donc une distance $\de$
nomm\'{e}e \textit{distance discr\`{e}te induite par} $\re$.
%
\subsection{Relation induite par une fonction num\'{e}rique}\label{rfnum}
%\`{a} un seuil donn\'{e}}
%
Si $f$ est une fonction d\'{e}finie sur $E\times E$ \`{a} valeurs dans $R$
et $\varepsilon$ un r\'{e}el positif ou nul, on dit que
$x$ et $y$ sont $\varepsilon$-proches au sens $f$ ssi $|d(x,y)|\leq \varepsilon$.
Soit $\rf$ la relation binaire d\'{e}finie par $\rf(x,y)$ est vraie ssi
$x$ et $y$ sont $\varepsilon$-proches au sens de $f$ et faux sinon.

Si $f$ est une distance $d$,
$\rf$ est alors r\'{e}flexive, sym\'{e}trique et transitive, c'est la relation
d'\'{e}quivalence nomm\'{e}e \textit{relation de proximit\'{e}} induite par $d$
et
pour toute fonction $f$, $\rz$ est la relation classique d'\'{e}galit\'{e}.
%
%\newpage
%\subsection{Applications aux logiques multivalu\'{e}es} \label{lmult}
%
\end{document}
