<figure><img src="image_1.png" /></figure>

HAL
open science

# Apprentissage et mesures de ressemblances adaptatives

Edwin Diday, Gérard Govaert

► To cite this version:

Edwin Diday, Gérard Govaert. Apprentissage et mesures de ressemblances adaptatives. [Rapport de recherche] IRIA-RR-089, IRIA. 1974, pp.22. hal-04715966

HAL Id: hal-04715966

https://inria.hal.science/hal-04715966v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
RIA
laboria

laboratoire de recherche
en informatique
et automatique

Apprentissage et mesures
de ressemblances adaptatives

<figure><img src="image_3.png" /></figure>

E.Diday,G.Govaert

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

Rapport de Recherche n° 89

Novembre 1974
APPRENTISSAGE ET MESURES
DE RESSEMBLANCES ADAPTATIVES

E. DIDAY, G. GOVAERT

**Résumé :**

Nous montrons d'abord le lien entre la notion d'indice de simi-
larité et la reconnaissance de formes dans son aspect "classi-
fication" et "clustering". Sont ensuite présentés des indices
de ressemblance usuels suivant la nature des données (quantita-
tives, qualitatives, ordinales ou nominales, etc...).

Les vues des auteurs concernant les recherches ultérierues dans
ce domaine sont ensuite présentées en faisant ressortir l'impor-
tance de l'aspect dynamique de la notion d'indice de ressemblance.
Dans cet esprit, il est donné des algorithmes utilisant des distances
adaptatives (d'abord dans le cas de distances quadratiques puis pour
des distances quelconques) et il est suggéré un lien avec les idées
de la "Gestalt theorie".

**Abstract :**

We first show the link between the notion of similarity index and Pattern Recognition in its "clustering" aspect. Afterwards usual resemblance measures are presented according to the nature of the data (quantitative, qualitative, ordinal or nominal, etc...).

The authors' views on further researches in that field are then
presented, pointing at the importance of the dynamical aspect of
the notion of resemblance measure. Algorithms are given that use
adaptative distances in this turn of mind (first in the case of
quadratic distances and after for any kind of distance). A link
with the main ideas of the "Gestalt theorie" is suggested.
# PLAN

1. INTRODUCTION

2. LES DIFFERENTS TYPES D'INDICES DE RESSEMBLANCE

2.1. Nature des données

2.2. Distances pour des données quantitatives

2.3. Distances pour des données qualitatives

2.3.1. Codage de données qualitatives ordinales et nominales

2.3.2. Mesures de ressemblance entre objets

2.3.3. Mesures de ressemblance entre Variables Nominales

2.3.4. Distances entre groupes d'objets.

3. DISTANCE ADAPTATIVE

3.1. Formalisation du problème

3.2. La méthode

3.3. Etude de la convergence

3.4. Cas de noyaux contenant plusieurs points

3.5. Lien avec l'apprentissage

4. UNE GENERALISATION DE L'ALGORITHMES DES DISTANCES ADAPTATIVES

4.1. Notations

4.2. Le critère à optimiser

4.3. L'algorithme

4.4. Convergence de l'algorithme

4.5. Condition de construction de l'algorithme

5. INDICE DE RESSEMBLANCE ET PERCEPTION

6. CONCLUSION
# 1. - INTRODUCTION

Dans tout ce qui suit une mesure de ressemblance ou une distance est une application symétrique de $E \times E$ dans $\mathbb{R}^+$ où E est l'ensemble des objets. La différence entre ces deux appellations vient du fait que la distance est une mesure de dissemblance. Cette notion de mesure de ressemblance ou de distance apparaît en reconnaissance des formes sous deux aspects :

* en classification afin d'affecter un objet à la classe qui lui est le plus similaire (au sens d'un indice donné) parmi un ensemble de classes fixées à priori ;

* en clustering, afin de construire des classes d'objets similaires.

De nombreux algorithmes sont basés sur le fait que la mesure de ressemblance est définie a priori une fois pour toute Cependant quand on passe à des objets ne faisant pas partie de l'ensemble d'apprentissage, des difficultés peuvent apparaître, soit que les classes définies a priori sur l'ensemble d'apprentissage soient erronées, soit que les variables ne peuvent exprimer ces classes. C'est pourquoi alors que dans la première partie nous faisons un bref rappel des principales distances utilisées ces dernières années, dans la seconde, nous proposons des méthodes récemment développées en clustering permettant de définir des distances adaptatives.

# 2. - LES DIFFERENTS TYPES D'INDICES DE RESSEMBLANCE

## 2.1. - Nature des données

On peut grossièrement ranger les données en deux types : quantitatif et qualitatif.

Les données quantitatives sont celles où les paramètres peuvent prendre des valeurs numériques continues (mesure) ou discrètes (fréquences).

Les données qualitatives peuvent être nominales (couleur, nom de maladie) ou binaires (réponse par oui ou non).

## 2.2. - Distances pour des données quantitatives

On note m le nombre d'objets et n le nombre de variables. Un objet est représenté par le vecteur $X_i^T = (x_{ij}, ..., x_{in})$, les variables seront notées $Y_j^T = (x_{lj}, ..., x_{mj})$, on a alors les
distances classiques suivantes :

$$
\cdot d_1(X_i, X_j) = \begin{bmatrix} n \\ \sum_{j=1} |x_{ij} - x_{i',j}|^{1/\lambda} \end{bmatrix}_{\lambda} \quad (\text{métrique de Minkowsky})
$$

$$
\cdot d_2(X_i, X_j) = \sum_{j=1}^{n} \frac{|x_{ij} - x_{i',j}|}{(x_{ij} + x_{i',j})} \quad (\text{métrique de Camberra})
$$

$$
\cdot d_3(X_i, X_j) = \max_j |x_{ij} - x_{i',j}|
$$

$$
\begin{array}{ll}
\cdot d_4(X_i, X_j) = (X_i - X_j)^T Q (X_i - X_j) & \text{(métrique quadratique)} \\
\text{où Q est matrice (m × m)} &
\end{array}
$$

$$
\cdot d_5(X_i, X_j) = (X_i - X_j)^T W^{-1} (X_i - X_j) \quad (\text{métrique de Mahalanobis})
$$
où W est la matrice de variance
covariance de $(Y_1, \dots, Y_n)$.

$$
\cdot d_6(X_i, X_j) = \frac{\sum_{j=1}^{n} (x_{ij} - \bar{x}_j)(x_{i',j} - \bar{x}_{j'})}{\left[ \sum_{j=1}^{n} (x_{ij} - \bar{x}_j)^2 \sum_{j=1}^{n} (x_{i',j} - \bar{x}_{j'})^2 \right]^{1/2}} \quad (\text{corrélation})
$$

$$
\cdot d_7(X_i, X_j) = \sum_{j=1}^{n} w_j |x_{ij} - x_{i',j}|
$$

$$
\cdot d_8(X_i, X_j) = \sum_{j=1}^{n} \frac{1}{x_i} \left( \frac{x_{ij}}{x_i} - \frac{\bar{x}_{i,j}}{x_{i'}} \right) \quad (\text{métrique du } \chi^2 \text{ due à Benzecri})
$$

$$
\text{où } x_j = \sum_{i=1}^{m} x_{ij} \quad \text{et} \quad x_i = \sum_{j=1}^{n} x_{ij}
$$

Cette distance très utilisée en France, vérifie un certain nom-
bre de propriétés dont celle dite "d'équivalence distribution-
nelle". Autrement dit, on peut remplacer deux individus i et i'
qui ont le même profil (i.e. $\frac{x_{ij}}{x_i} = \frac{x_{i'j}}{x_{i'}}$) par un troisième

iº de même profil affecté de la somme des masses de i et i' sans que les distances (par d8) entre les objets ou entre les varia- bles ne soient modifiées.

## 2.3. - Distances pour des données qualitatives

### 2.3.1. - Codage de données qualitatives ordinales et nominales

On utilise l'application $Z : \mathbb{N} \rightarrow \{0,1\}^k$, si $k$ est le nombre de modalités possibles d'une variable donnée. Dans le cas de données nominales, $Z^T(x_{ij}) = (0, \dots, 0, 1, 0, \dots, 0)$ est un vecteur qui ne contient que des zéros sauf pour la coordonnée de rang $x_{ij}$ autrement dit :

$$ (i) \quad Y_e = \begin{pmatrix} 1 \\ 3 \\ 2 \\ 2 \\ 1 \end{pmatrix} \xrightarrow{Z^T} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix} $$

Dans le cas de données ordinales $Z^T(x_{ij}) = (1, \dots, 1, 0, \dots, 0)$ est un vecteur où toutes les coordonnées sont égales à 1 jusqu'à celle de rang $x_{ij}$, les suivantes étant nulles, autrement dit :

$$ (ii) \quad Y_e = \begin{pmatrix} 1 \\ 3 \\ 2 \\ 2 \\ 1 \end{pmatrix} \xrightarrow{Z^T} \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix} $$

Une description plus détaillée de ce codage est fournie dans [20].

### 2.3.2. - Mesures de ressemblance entre objets

Soit $Z_i = (z_{i1}, \dots, z_{it})$ le vecteur représentant la ligne i du tableau transformé par $Z^T$.

On voit qu'à l'aide de ce codage, n'importe quelle donnée qualitative ou binaire peut être utilisée sur le tableau transformé par $Z^T$.

On peut montrer que la distance

$$ d(Z_i, Z_{i'}) = \sum_{j=1}^{k} \frac{1}{z_j} (z_{ij} - z_{i',j})^2 \quad \text{revient à un calcul de } \chi^2. $$
On peut montrer aussi que la distance $d_8$ du $\chi^2$ due à Benzecri s'écrit sous la forme suivante :

$$d_9(X_i, X_{i'}) = \sum_{j=1}^{n} \left( \frac{1}{p(x_{ij})} + \frac{1}{p(x_{i'}, j)} \right) \delta_{ii'}^j$$

$$\text{où } \delta_{ii'}^j = \begin{cases} 1 & \text{si } x_{ij} \neq x_{i'j} \\ 0 & \text{si } x_{ij} = x_{i'j} \end{cases}$$

et $p(x_{ij})$ le nombre de fois que la modalité $x_{ij}$ est atteinte par la variable $j$.

Voyons maintenant quelques distances classiques spécifiques aux variables qualitatives ordinales, aux suites finies et aux données binaires :

- **Coefficient des rangs de Spearman :**

$$d_{10}(X_i, X_{i'}) = 1 - \frac{6}{n(n^2-1)} \sum_{j=1}^{n} (x_{ij} - x_{i'j})^2$$

On peut montrer que cet indice est équivalent à $d_6$ donc le coefficient des rangs de Spearman mesure la corrélation des rangs. De plus, il existe des tables permettant de juger l'indépendance de $X_i$ et $X_{i'}$.

- **Corrélation des rangs de Kendall :**

$$\text{Soit } \Delta_{jk} = \text{signe de } (x_{ij} - x_{ik})$$

$$\Delta'_{jk} = \text{signe de } (x_{i'}j - x_{i'k})$$

$$\tau = \frac{2}{n(n-1)} \sum_{j<k} \Delta'_{jk} \Delta_{jk} = 2 \frac{a-b}{n(n-1)}$$

où $a$ est le nombre de fois où $\Delta_{jk}$ et $\Delta'_{jk}$ sont de même signe et $b$ le nombre de fois où ils sont de signe contraire. Finalement, on pose :

$$d_{11}(X_i, X_{i'}) = 1 - \tau.$$

- **Distance entre suites finies :**

P.M. Sellers [18] propose une distance entre une suite
a = (a₁, a₂, ..., aₙ) et b = (b₁, ..., bₙ). d(a,b) est le plus petit nombre de pas nécessaires pour rendre les suites identiques, où un pas est :

(i) la suppression d'un terme de la suite,

(ii) le changement d'un terme d'une suite pour le rendre égal à un terme de l'autre suite.

Exemple :

a = (x, y, w, x)

b = (x, w, y, y, x)

on a $d(a,b) = 2$ parce qu'il faut au moins deux pas pour les rendre identiques :

1. changer w en y dans a,

2. enlever w dans b.

- Données binaires

Si $X_i$ et $X_i'$ sont deux vecteurs binaires, pour définir $D(X_i, X_i')$

il est nécessaire d'introduire les 4 quantités suivantes :

a le nombre de fois où $x_{ij} = x_{i'}j = 1$

b le nombre de fois où $x_{ij} = 0$ et $x_{i'}j = 1$

c le nombre de fois où $x_{ij} = 1$ et $x_{i'}j = 0$

d le nombre de fois où $x_{ij} = x_{i'}j = 0$.

Les mesures de ressemblance suivantes ont souvent été utilisées :

$$ \cdot D_1(X_i, X_{i'}) = \frac{a}{a+b+c+d} \qquad (\text{Russel and Raw}) $$

$$ \cdot D_2(X_i, X_{i'}) = \frac{a}{a+b+c} \qquad (\text{Jaccard, Needham}) $$

$$ \cdot D_3(X_i, X_{i'}) = \frac{2a}{2a+b+c} \qquad (\text{Dice}) $$

$$ \cdot D_4(X_i, X_{i'}) = \frac{a}{a+2(b+c)} \qquad (\text{Sokal et Sneath}) $$
$$
\cdot D_5(X_i, X_{i'}) = \frac{a+d}{a+b+c+d} \qquad (\text{Sokal et Michener})
$$

$$
\cdot D_6(X_i, X_{i'}) = \frac{a}{b+c} \qquad (\text{Kulzinsky})
$$

$$
\cdot D_7(X_i, X_{i'}) = \frac{a+d}{a+d+2(b+c)} \quad (\text{Rogers et Tanimoto})
$$

$$
\cdot D_8(X_i, X_{i'}) = \frac{ad-bc}{ad+bc} \qquad (\text{Yule})
$$

$$
\cdot D_9(X_i, X_{i'}) = \frac{ad - bc}{\left[ (a+b)(c+d)(a+c)(b+d) \right]^{1/2}} \quad (\text{Corrélation})
$$

2.33. - Mesures de ressemblance entre Variables Nominales

On a la table de contingence suivante :

<table>
  <thead>
    <tr>
      <th>Y<sub>l</sub></th>
      <th>1</th>
      <th>2</th>
      <th>3</th>
      <th>-- r</th>
      <th></th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>Y<sub>k</sub></th>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>1</th>
      <td>n<sub>11</sub></td>
      <td>n<sub>12</sub></td>
      <td></td>
      <td></td>
      <td>n<sub>1.</sub></td>
    </tr>
    <tr>
      <th>2</th>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>...</th>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>q</th>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th></th>
      <td>n<sub>1.</sub></td>
      <td></td>
      <td></td>
      <td></td>
      <td>n<sub>..</sub></td>
    </tr>
  </tbody>
</table>

$$
\cdot d_{11}(Y_l, Y_k) = n_{..} \sum_{i=1}^{q} \sum_{j=1}^{r} \left( n_{ij} - \frac{n_{i.} \cdot n_{.j}}{n_{..}} \right)^2 \frac{1}{n_{i.} \cdot n_{.j}}
$$

$$
\cdot d_{12}(Y_l, Y_k) = \sum_{i=1}^{q} n_{i.} \cdot \sum_{j=1}^{r} \left| \frac{n_{ij}}{n_{i.}} - \frac{n_{.j}}{n_{..}} \right|
$$

$$
\cdot d_{13}(Y_l, Y_k) = \frac{1}{n_{..}} \sum_{i=1}^{q} \max_j n_{ij} \quad \text{Cf. [14]}
$$
## distance utilisant l'information :

$$d_{14}(Y_{\ell}, Y_{k}) = I(Y_{\ell}) + I(Y_{k}) - I(Y_{\ell} \cap Y_{k})$$

où :

$$I(Y_{\ell}) = - \sum_{i} p_{i} \log_{2} p_{i} \quad \text{où} \quad p_{i} = \frac{n_{i}}{n}$$

$$I(Y_{k}) = - \sum_{j} p_{.j} \log_{2} p_{.j} \quad \text{où} \quad p_{.j} = \frac{n_{.j}}{n}$$

$$I(Y_{\ell} \cap Y_{k}) = \sum_{i,j} p_{ij} \log_{2} p_{ij}$$

Sous l'hypothèse d'indépendance entre $Y_{\ell}$ et $Y_{k}$, on montre que
$$d_{14}(Y_{\ell}, Y_{k}) \approx \frac{\chi^2}{\mathrm{Log} \ 2}.$$

## 2.3 A. - Distances entre groupes d'objets

Soit $\mu$ une application de l'ensemble des partitions de E dans $\mathbb{R}^{+}$ telle que $\mu(A) = \sum_{a \in A} \mu(a) \forall A \subset E$.

$$\text{On pose } D(x,A) = \sum_{a \in A} d(x,a)$$

$$G(A) = \frac{1}{\mu(A)} \sum_{a \in A} \mu(a) \cdot a$$

$$\mathrm{var}(A) = \frac{1}{\mu(A)} \sum_{a \in A} d(a, G(A))$$

Dans le cas où d est quadratique, on peut utiliser le théorème de Koenig-Huygens et en déduire les formules suivantes :

$$D(x,A) = \mu(A) \left[ d(x, G(A)) + \cdot \mathrm{var} \ A \right]$$

$$\mathrm{var}(\bigcup_{i=1}^{k} A_i) = \sum_{i=1}^{k} \mu(A_i) \mathrm{var} \ A_i + D(A_1, \dots, A_k)$$

$$\text{où } D(A_1, \dots, A_k) = \sum_{i=1}^{k} \mu(A_i) d \left[ G(A_i), G\left(\bigcup_{j=1}^{k} A_j\right) \right]$$
Dans le cas de dichotomie et si $A \cap B = \emptyset$, on a :

$$D(A,B) = \frac{\mu(A) \cdot \mu(B)}{\mu(A) + \mu(B)} \quad d(G(A), G(B)).$$

Supposons maintenant que le tableau initial a été transformé par l'application $z^T$. Si on prend $\mu(a) = 1 \forall a \in E$,

$$G(A) = \frac{1}{\text{card}(A)} \quad \sum_{a \in A} Z(a) = (G_1(A), \dots, G_k(A)),$$

k est le nombre de modalités d'une variable donnée $Y_k$.

Soient $A_1, A_2$, deux parties de E, on a le tableau :

<table><thead><tr><th>Y<sub>e</sub></th><th>A<sub>1</sub></th><th>A<sub>2</sub></th><th></th></tr></thead><tbody><tr><th>1</th><td>n<sub>11</sub></td><td>n<sub>12</sub></td><td>n<sub>1</sub></td></tr><tr><th>2</th><td></td><td></td><td></td></tr><tr><th>...</th><td></td><td></td><td></td></tr><tr><th>k</th><td>n<sub>k1</sub></td><td>n<sub>k2</sub></td><td>n<sub>k</sub></td></tr><tr><th></th><td>n<sub>.1</sub></td><td>n<sub>.2</sub></td><td></td></tr></tbody></table>

$$d'\text{où } G_j(A_i) = \frac{n_{ji}}{n_i}.$$

**Exemple** : Soit $A_1 = \{X_2, X_5, X_6\}$,

$$Y = \begin{pmatrix} x_{1e} \\ \vdots \\ x_{6e} \end{pmatrix} = \begin{pmatrix} 1 \\ 3 \\ 2 \\ 2 \\ 1 \\ 1 \end{pmatrix}$$

et plaçons-nous dans le cas de variables ordinales, alors :

$$\begin{pmatrix} z^T(X_2) \\ z^T(X_5) \\ z^T(X_6) \end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix}$$

$$\text{et } G_1(A_1) = 1, G_2(A_1) = \frac{2}{3}, G_3(A_1) = \frac{1}{3}$$
soit $d_{15}(Z_i, Z_j) = \sum_{k=1}^{k} \frac{1}{z_k} (z_{ik} - z_{ji})^2$

on a alors :

$$
\begin{align*}
D(A_1, A_2) &= \mu(A_1) d(G(A_1), G(A_1 \cup A_2)) \\
&\quad + \mu(A_2) d(G(A_2), G(A_1 \cup A_2)) \\
&= \sum_{i=1}^{2} \sum_{j=1}^{k} \frac{1}{n_j} \left( \frac{n_{ji}}{n_i} - \frac{n_{ji}}{n_j} \right)^2 \\
&= \sum_{i=1}^{2} \sum_{j=1}^{k} \frac{1}{n_j \cdot n_i} \left( n_{ji} - \frac{n_j \cdot n_i}{n_j \cdot n_i} \right)^2 = \frac{\chi^2}{n}
\end{align*}
$$

3. - DISTANCE ADAPTATIVE

Dans la majorité des algorithmes de classification qui existent,
la mesure de ressemblance utilisée est la même pour tout l'es-
pace E et reste fixée pendant le déroulement de l'algorithme.
Dans ce travail, nous présentons un nouveau type d'algorithme
pour lequel la mesure de ressemblance, tout en restant quadra-
tique, évolue en s'adaptant localement à la structure de l'es-
pace E jusqu'à la convergence, en faisant décroître un certain
critère qui exprime cette adaptation.

3.1. - Formalisation du problème

3.1.1. - Notations

On suppose que l'ensemble E à classer est dans $\mathbb{R}^p$.

On pose $\mathcal{L} = \mathbb{R}^p \times \mathcal{D}$ où $\mathcal{D}$ est l'ensemble des distances quadra-
tiques définies sur $\mathbb{R}^p$ dont la matrice associée a un détermi-
nant égal à 1.

On définit une mesure de ressemblance D entre un élément x de
E et un élément λ = (a,d) de L par : D (x,λ) = d(x,a).

On définit une mesure de ressemblance I entre une partie finie
B de $\mathbb{R}^p$ et un élément $\lambda = (a,d)$ de $\mathcal{L}$ par : $I(B,\lambda) = \sum_{y \in B} d(a,y)$,

I(B,λ) est donc le moment d'inertie,mesuré avec la distance d,
de B par rapport au point a.
Soit $\mathbb{P}_k$ l'ensemble des partitions de $E$ en $k$ classes et $\mathbb{L}_k$
1'ensemble des $k$-uples $(\lambda_1, ..., \lambda_k)$ où $\lambda_i \in \mathbb{L} = \mathbb{R}^P \times \mathcal{D}$,
$k$ est une valeur fixée a priori.

3.1.2. - Critère

Le critère que l'on cherche à optimiser est l'application de
$V_k = \mathbb{L}_k \times \mathbb{P}_k$ dans $\mathbb{R}^+$ définie par :

$$
\begin{gather*}
\hat{W}(v) = W(L,P) = \sum_{i=1}^{k} I(P_i, \lambda_i) = \sum_{i=1}^{k} \sum_{y \in P_i} d_i(a_i, y) \\
\text{où } v = (L,P)
\end{gather*}
$$

$$
\text{où } v = (L,P)
$$

$$
L = (\lambda_1, \dots, \lambda_k) \text{ avec } \lambda_i = (a_i, d_i)
$$

et $P = (P_1, \dots, P_k)$.

Minimiser $W$ revient à chercher *parmi tous les couples* $(L,P)$ *celui*
qui minimise la somme des moments d'inertie des classes $P_i$ par
rapport au point $a_i$ mesurés avec la distance $d_i$.

On voit que la distance utilisée n'est pas fixée une fois pour
toute et de plus n'est pas la même pour chacune des classes.

3.2. - La méthode

3.2.1. - L'algorithme

On recherche l'élément $v$ de $\mathcal{W}_k$ qui minimise $W(v)$. L'algorithme consiste à construire, à partir d'un élément quelconque $v_o$ de $\mathcal{W}_k$, une suite $(v_n)$, telle que la valeur du critère $W(v_n)$ associé à cette suite décroisse.

Pour construire cette suite, on utilise deux fonctions :

- $f: \mathbb{L}_k \to \mathbb{P}_k$ fonction qui associe à k couples point-distance
une partition en k classes de E.

- $g: \mathbb{P}_k \to \mathbb{L}_k$ fonction qui associe à une partition en k classes de E, k couples point-distance.

La suite $(v_n)$ est alors définie par $v_o = (L^{(o)}, P^{(o)})$ quelconque et :

$$
v_{n+1} = (g_o f(L^{(n)}), f(L^{(n)})) \text{ si } v_n = (L^{(n)}, P^{(n)}).
$$
On définit maintenant $f$ et $g$ de façon précise.

### 3.2.2. - La fonction d'identification f

$f : \mathbb{L}_k \to \mathbb{P}_k$

Si $L \in \mathbb{P}_k$ avec $L = (\lambda_1, ..., \lambda_k)$ et $\lambda_i = (a_i, d_i)$, $f(L)$ est la partition $P = (P_1, ..., P_k)$ où :

$$P_i = \{x \in E / D(x, \lambda_i) \le D(x, \lambda_j) \quad \forall j \ne i\}$$

Comme $D(x, \lambda_i) = d_i(x, a_i)$ c'est équivalent à :

$$P_i = \{x \in E / d_i(x, a_i) \le d_j(x, a_j) \quad \forall j \ne i\}.$$

La classe $P_i$ est donc formée des éléments de $E$ qui sont plus près de $a_i$ au sens de $d_i$ que de n'importe quel $aj$ au sens de $dj$ pour $j \ne i$.

### 3.2.3. - La fonction de représentation g

$g : \mathbb{P}_k \to \mathbb{L}_k$

Si $P = (P_1, ..., P_k)$ est une partition en $k$ classes de $E$, $g(P)$ est le $k$-uple $L = (\lambda_1, ..., \lambda_k)$ où $\lambda_i = (a_i, d_i)$ vérifiant :

$$I(P_i, (a_i, d_i)) = \min_{(a,d) \in \mathbb{R}^P \times \mathbb{D}} I(P_i, (a,d))$$

Si $B$ est une partie finie de $\mathbb{R}^P$, $d$ une distance quadratique quel-
conque sur $\mathbb{R}^P$ et $a^*$ défini par $I[B, (a^*, d)] = \min_{a \in \mathbb{R}} I[B, (a, d)]$

on démontre que $a^*$ est le centre de gravité de $B$ (on remarque
que $a^*$ ne dépend donc pas de $d$).

Prenons les notations 3.2.1., $B$ étant encore une partie finie de $\mathbb{R}^P$, si $(a^*, d^*)$ est défini par :

$$I[B, (a^*, d^*)] = \min_{(a,d) \in \mathbb{R}^P \times \mathbb{D}} I[B, (a, d)]$$

on montre en utilisant les résultats de [15] et de [17] la
proposition suivante :

**Proposition 1 :**

$a^*$ est centre de gravité de $B$.
d* est la distance définie par la matrice

$M = |Q|^{1/p} \cdot Q^{-1}$ où Q est la matrice de variance-covariance de B (i.e. d* est la distance de Mahalanobis associée à B).

En conséquence, la fonction g associera à une partition $(P_1, \dots, P_k)$ un k-uple $(\lambda_1, \dots, \lambda_k)$, $\lambda_i$ étant le couple centre de gravité - distance de Mahalanobis de $P_i$.

### 3.3. - Etude de la convergence

On dira que la suite $(v_n)$ est une suite convergente si et seulement si $\exists N, \forall n > N \ v_n = v_N$.

Soient
$$v_n = (L^{(n)}, P^{(n)})$$
$$L^{(n)} = (\lambda_1^{(n)}, \dots, \lambda_k^{(n)})$$
$$\lambda_i^{(n)} = (a_i^{(n)}, d_i^{(n)})$$
et $Q_i^{(n)}$ la matrice de variance-covariance de $P_i^{(n)}$.

En utilisant les résultats de [15] et [17] on montre le résultat suivant :

**Théorème :**

La suite $(v_n)$ converge en faisant décroître le critère :

$$W(v_n) = \sum_{i=1}^{k} \sum_{x \in P_i^{(n)}} d_i^{(n)} (a_i^{(n)}, x)$$

que l'on peut écrire :

$$W(v_n) = p \sum_{i=1}^{k} \text{card}(P_i^{(n)}) \cdot |\theta_i^{(n)}|^{1/p}$$

On montre de plus que :

**Proposition 2 :**

La méthode tend à nous donner des classes telles que pour chaque classe le produit des variances sur chacun des axes principaux d'inertie de cette classe soit le plus petit possible.

**Proposition 3 :**

La solution obtenue est invariante pour tout changement de base de
l'espace vectoriel $\mathbb{R}^p$ contenant l'ensemble E des individus à
classer.

### 3.4. - Cas de noyaux contenant plusieurs points

Dans l'algorithme précédent, les éléments $\lambda$ de $\mathbb{L}$ étaient formés d'un élément de $\mathbb{R}^p$ et d'une distance. On peut montrer que le même algorithme, utilisant cette fois des éléments $\lambda$ formés de plusieurs points de E (un nombre $l$ fixé a priori) et d'une distance quadratique, possède les mêmes propriétés de convergence.

### 3.5. - Lien avec l'apprentissage

On parle d'apprentissage quand on cherche à définir des algorithmes qui, par itérations successives, apprennent l'exécution de tâches à la machine en tenant compte des connaissances acquises à mesure que l'algorithme progresse. Ces tâches peuvent être par exemple la recherche de classes d'objets similaires (en clustering) ou la recherche de fonctions d'identification ou de décision (en discrimination).

Quand il y a une intervention extérieure pendant le déroulement de l'algorithme, par exemple arrivée de nouveaux individus étiquetés, on parle d'apprentissage avec professeur, dans le cas contraire, sans professeur.

Dans le cas de notre algorithme, il s'agit d'apprentissage de distance sans professeur. En effet, à chaque itération de l'algorithme, les distances utilisées sont remises en question et sont modifiées pour mieux s'adapter aux classes auxquelles elles sont associées. L'algorithme s'arrêtant lorsqu'on ne remet plus en question les distances utilisées.

Nous avons préféré parler d'adaptation de distance. En effet, pour l'instant les distances sont obligatoirement des distances quadra-tiques et seules sont remises en question les matrices de défini-tion des distances.

Nous verrons dans l'algorithme suivant comment on peut réaliser de l'apprentissage avec professeur.

Nos recherches s'orientent vers l'utilisation de mesures de ressemblance beaucoup plus riches. On pourrait par exemple introduire des mesures de ressemblance qui n'utiliseraient que les relations d'ordre sur les valeurs des paramètres d'entrée ainsi que des opérateurs logiques.

Nous présentons maintenant un algorithme plus général que le pré-cédent qui a l'avantage d'être plus souple dans la recherche des
distances. Il sera donc plus facile de l'utiliser avec les dis-
tances dont nous venons de parler.

4. - UNE GENERALISATION DE L'ALGORITHME DES DISTANCES ADAPTATIVES

Dans l'algorithme précédent, on recherchait en même temps un élé-
ment a de $\mathbb{R}^p$ et une distance d qui optimisaient une certaine
fonction. Nous allons maintenant le faire en deux étapes.

4.1. - Notations

Soient :

. E l'ensemble des éléments à classer.

. $\mathbb{P}_k$ l'ensemble des partitions en k classes de E.

. $\mathbb{L}_k$ l'ensemble des k-uples $(\lambda_1, \dots, \lambda_k)$ où $\lambda_i \in A$, ensemble
qui reste à préciser suivant le cas.

. $\mathcal{D}$ un ensemble d'indices de ressemblance entre éléments de E et éléments de A.

. $\Delta_k$ l'ensemble des k-uples $(d_1, \dots, d_k)$ où $d_i \in \mathcal{D}$ .

. D une fonction de E x A x D dans $\mathbb{R}^+$.

. I une fonction de $\mathcal{P}(E) \times A \times \mathcal{D}$ dans $\mathbb{R}^+$.

4.2. - Le critère à optimiser

C'est la fonction W : $\mathbb{P}_k \times \mathbb{L}_k \times \Delta_k \to \mathbb{R}^+$ définie par :

$$
W(P, L, \Delta) = \sum_{i=1}^{k} I(P_i, \lambda_i, d_i)
$$

où :

$$
P = (P_1, \dots, P_k) \in \mathbb{P}_k
$$

$$
L = (\lambda_1, \dots, \lambda_k) \in \mathbb{L}_k
$$

et $\Delta = (d_1, \dots, d_k) \in \Delta_k$

Le but est de trouver le triplet (P, L, Δ) qui minimise le
critère.
### 4.3. - L'algorithme

On peut le résumer par le schéma suivant :

<figure><img src="image_4.png" /></figure>

Il est construit à partir de trois fonctions :

* $f: \mathbb{L}_k \times \Delta_k \to \mathbb{P}_k$

Si $L = (\lambda_1, \dots, \lambda_k) \in \mathbb{L}_k$ et $\Delta = (d_1, \dots, d_k) \in \Delta_k$

$P = (P_1, \dots, P_k) = f(L, \Delta)$ est définie par :

$P_i = \{x \in E / D(x, \lambda_i, d_i) \le D(x, \lambda_j, d_j) \quad \forall j \ne i \}$.

* $g: \Delta_k \times \mathbb{P}_k \to \mathbb{L}_k$

Si $\Delta = (d_1, \dots, d_k) \in \Delta_k$ et $P = (P_1, \dots, P_k) \in \mathbb{P}_k$

$g(P, \Delta)$ est le k-uple $L = (\lambda_1, \dots, \lambda_k) \in \mathbb{L}_k$ où $\lambda_i$ vérifie :

$$I(P_i, \lambda_i, d_i) = \min_{\lambda \in \Lambda} I(P_i, \lambda, d_i).$$

* $e: \mathbb{P}_k \times \mathbb{L}_k \to \Delta_k$

Si $P = (P_1, \dots, P_k) \in \mathbb{P}_k$ et $L = (\lambda_1, \dots, \lambda_k) \in \mathbb{L}_k$

$e(P, L)$ est le k-uple $\Delta = (d_1, \dots, d_k) \in \Delta_k$ où $d_i$ vérifie :

$$I(P_i, \lambda_i, d_i) = \min_{d \in \mathcal{D}} I(P_i, \lambda_i, d)$$

A partir d'un élément de départ quelconque $v_o = (P_o, L_o, \Delta_o)$, on construit une suite $v_n = (P_n, L_n, \Delta_n)$ à l'aide des trois fonctions
f, g et e de la manière suivante :

$$ 
\begin{aligned}
v_{n+1} &= (P_{n+1}, L_{n+1}, \Delta_{n+1}) \\
&= (f(L_n, P_n), g(\Delta_n, f(L_n, P_n)), e(f(L_n, P_n), g(\Delta_n, f(L_n, P_n)))
\end{aligned}
$$

### 4.4. - Convergence de l'algorithme

#### 4.4.1. - Définition

On dit que $I$ est fonction carrée de $D$ si et seulement si on a les relations :

$$ 
\begin{gathered}
W(P, L, \Delta) \ge W(P, g(P, \Delta), \Delta) \\
\text{et } W(P, L, \Delta) \ge W(P, L, e(P, L)).
\end{gathered}
$$

**Exemple :**

On peut montrer facilement qu'il suffit que :

$$ I(B, \lambda, d) = \sum_{x \in B} D(x, \lambda, d) $$

où $B$ est une partie finie de $E$, pour que $I$ soit fonction carrée de $D$.

#### 4.4.2. - Propriétés de convergence

On démontre les résultats suivants :

**Proposition :**

Si $I$ est fonction carrée de $D$, si $A$ ou $\mathcal{D}$ sont des ensembles de cardinaux finis et si $W$ est injectif, alors la suite $(P_n, L_n, \Delta_n)$ converge en faisant décroître le critère.

### 4.5. - Condition de construction de l'algorithme

Les deux fonctions $f$ et $g$ étant toujours constructibles, une seule condition est nécessaire pour que fonctionne l'algorithme : il faut savoir construire l'élément de $\mathcal{D}$ qui minimise la fonction $I$.

C'est le cas lorsque $\mathcal{D}$ est fini ou quand il possède des propriétés particulières (par exemple l'ensemble des distances quadra-tiques). Par contre, dans les autres cas, on peut se restreindre simplement à minimiser sans optimiser à chaque itération ce qui
est suffisant pour conserver les propriétés de convergence.

## 5. - INDICE DE RESSEMBLANCE ET PERCEPTION

Il semble qu'il existe une analogie entre l'approche présentée en 3. et 4. et la "Gestalt Theorie" (Cf. [10]). En effet, la perception peut être considérée comme l'interprétation d'un filtrage (aspect syntaxique) du monde extérieur (l'univers), à l'aide des organes des sens. L'intelligence de la situation (aspect sémantique) intervient alors et peut remettre en question la perception, et ainsi de suite jusqu'à l'obtention d'une position d'équilibre. "... l'intelligence ne se surrajoute pas à la perception. Les progrès de l'intelligence d'une situation sont des remaniements formels de la perception, des changements d'aspects où les caractères sensibles sont altérés" (P. GUILLAUME dans [9]).

Les méthodes basées sur des distances adaptatives s'inspirent en fait du même modèle. A partir du monde extérieur, on a défini le champ à étudier à l'aide d'un opérateur h. Ce champ est caractérisé par la donnée d'un ensemble d'apprentissage (codage, types a priori) et il est fonction de la distance retenue. L'intelligence de la situation (interprétation des clusters, liens entre eux, ...) est obtenue après utilisation d'un opérateur de classification f et elle peut être remise en question par l'opérateur g (g remet en cause d, donc le champ). Les schémas suivants font ressortir l'analogie en question.

<figure><img src="image_5.png" /><figcaption>Schéma 2</figcaption></figure>

## 6. - CONCLUSION

Nous avons défini des algorithmes qui permettent d'utiliser des mesures de ressemblance beaucoup plus générales que celles utilisées jusqu'alors. De plus, on peut concevoir un espace $\mathcal{D}$ dans
lequel des opérateurs permettraient de définir des combinaisons (algébriques par exemple) des éléments.

Ces algorithmes débouchent sur des méthodes d'apprentissage. On peut envisager un apprentissage sans professeur en fixant la partition, les noyaux ou les mesures de ressemblance. Dans la pratique, par exemple, il peut se produire des cas où le critère et les noyaux sont donnés, il s'agira alors de laisser évoluer seulement la partition et les distances.

Un apprentissage avec professeur peut être également envisagé en faisant évoluer au cours de l'algorithme les espaces $P_k$, $\Delta_k$ et $L_k$ tout en conservant l'amélioration du critère.

La notion de mesure de ressemblance est étroitement liée au champ retenu : mode de codage, ensemble d'apprentissage, types a priori, etc... Les algorithmes de classification ou de clustering font intervenir un certain nombre d'opérateurs qui, combinés avec la mesure de ressemblance utilisée influent sur le résultat obtenu. Les recherches ultérieures devront tenir compte des deux idées suivantes :

1. L'interaction entre la mesure de ressemblance, le champ, les opérateurs implicites aux algorithmes utilisés.

2. Selon les idées de J.C. SIMON [19] après avoir dégagé les primitives du schéma 2 par exemple, faire intervenir à l'aide de l'outil informatique des opérations plus riches que celles habituellement utilisées par le mathématicien.
BIBLIOGRAPHIE

[1] Anderberg M.R., 1973 - "Cluster Analysis for applications", Acad. Press.

[2] Benzecri J.P. et Collaborateurs. "L'analyse des données" 1 - La taxinomie - Dunod, 1973.

[3] Ball J.M., 1970 - "Pattern clustering by Multivariate Behavorial" - Res. 5, N° 3, 329 - 350.

[4] Chernoff H., 1970 - "Metric considerations in cluster analysis" - Proc. of the sixth Berkeley Symposium on Math. Stat. and Prob.

[5] Diday E., 1972 - Thèse d'Etat, Université de PARIS VI.

[6] Diday E., 1973 - "Analyse factorielle typologique" - Rapport Laboria n° 27, IRIA Rocquencourt (78).

[7] Diday E., Govaert G., 1974. Classification avec distance adaptative - C. R. Acad. Sc. - Paris t-278 (8 avril 1974)

[8] Guillaume P., 1947 - "La psychologie de la forme" - Gallimard, 1964.

[9] Guillaume P., 1973, Préface à "L'intelligence des singes supérieurs" de Köhler, CEPL PUF.

[10] Köhler W., 1964 - "La psychologie de la forme" - Gallimard.

[11] Lerman I.C., 1970 - "Les bases de la classification automatique."

[12] Lerman I.C., 1973 - "Introduction à une méthode de classification automatique illustrée par la recherche d'une typologie des personnages enfants à travers la littérature enfantine" - Revue de Statistique Appliquée, Vol. XXI, n° 3, PARIS 1973.

[13] Mac Queen J., 1967 - "Some methods for Classification and Analysis of multivariate observations" - The 5th Berkeley Symposium on Mathematics, Statistics and Probability, Vol. 1 n° 1.
14 Morgan J.N., Messenger R.C., 1973 - "Thaïd" Thomson-Shore, Ann-Arbor (Michigan).

15 Romeder J.M., 1969 - "Méthode de discrimination" - Thèse de 3ème cycle, statistique Mathématique, Faculté des Sciences de Paris VII.

16 Scott A.J., SYMONS M.J., 1971 - "Clustering Methods Based on Likelihood Ratio criteria" - Biometrics 27, n° 2, 387-398.

17 Sebeystien G.S., 1962 - "Decision Making Processes in Pattern Recognition", The Macmillan Company.

18 Sellers P., 1974 - "An algorithm for the distance between two finite sequences" - Journal of combinatoriel Theory (A) 16, 253-258.

19 Simon J.C., 1974 - "A formal aspect of Pattern Recognition and Scene Analysis" - I.J.C.P.R. II, Feb. 74.

20 Sneath P., Sokal R., 1974 - "Numerical Taxonomy", W.M. Freeman Ed.

21 Tenenhaus M., Bouroche J.M., 1970 - "Some segmentation methods" - Metra vol. IX, n° 3.

22 Wishart D., 1971 - "Some problems in the Theory and application of the methods of numerical taxonomy" - Ph. D. Thesis University of St Andrews.

23 Wolfe J.M., 1970 - "Pattern clustering by Multivariate behavioral" - Res. 5, N° 3, 329-350.