# Classification automatique optimale sous contrainte d'ordre total

Yves Lechevallier

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

## To cite this version:

Yves Lechevallier. Classification automatique optimale sous contrainte d'ordre total. [Rapport de recherche] IRIA-RR-200, IRIA. 1976, pp.24. hal-04716336

HAL Id: hal-04716336

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

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published 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
<figure><img src="image_3.png" /></figure>

laboria

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

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 5 78150 - Le Chesnay
France
Tél.: 954 90 20

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

laboratoire de recherche
en informatique
et automatique

CLASSIFICATION AUTOMATIQUE
OPTIMALE
SOUS CONTRAINTE
D'ORDRE TOTAL

Y. LECHEVALLIER

Rapport de Recherche N° 200
Novembre 1976
CLASSIFICATION AUTOMATIQUE OPTIMALE SOUS CONTRAINTE
D'ORDRE TOTAL

Y. Lechevallier

résumé :

Un des problèmes qui se posent en classification automatique est de trouver une partition, dont le nombre de classes est fixé, et qui soit optimale pour un critère donné. Ce critère dépend de l'application pour laquelle il est utilisé. Nous décrirons d'abord un algorithme de programmation dynamique efficace (FISHER W.D.) pour le cas où les objets sont définis par une seule variable numérique et où le critère adapté est la variance intra classe. L'objet de cet article est de présenter deux extensions de cet algorithme : définition d'un vaste ensemble de critères utilisables, possibilité d'imposer certaines contraintes sur la solution optimale.

Abstract :

Cluster Analysis involves the problem of finding a partition into clusters which is optimal for a given criterion. This criterion will depend on the application for which it will be used. We shall first describe an efficient dynamic programming algorithm (due to FISHER W.D.) for the case of objects which are points on the real line and where the criterion minimizes the within-groups sums of squares. The purpose of this paper is to present two extensions of this algorithm : first by taking other criteria, then by setting a constraint on the optimal solution.
CLASSIFICATION AUTOMATIQUE OPTIMALE SOUS CONTRAINTE
D'ORDRE TOTAL

I. - Introduction

Etant donné un ensemble de n objets caractérisés par p paramètres.
Il s'agit de trouver la (ou les) partition de ces objets en k classes
optimale pour un critère donné.

Dans Jensen [7] on voit que l'énumération complète de l'ensemble des partitions en k-classes, non vides, devient impossible si le nombre d'éléments que l'on désire classer dépasse la dizaine. Il donne la fonction permettant de calculer le nombre de partitions en k-classes, non vide, d'un ensemble de n individus. Ce nombre, noté S (n,k), est égal à :

$$
S(n,k) = \frac{1}{k!} \sum_{i=0}^{k} C_i^k (-1)^{k-i} i^n
$$

$$
\text{avec } C_i^k = \frac{k!}{i!(k-i)!} \text{ et}
$$

$$
\lim_{n \to \infty} \frac{S(n,k)}{k^n} = \frac{1}{k} \quad (\text{cf. pour la démonstration, en Annexe 1})
$$

Par exemple pour n = 25 et k = 10, pour le nombre de partitions
en 10 classes, non vides, d'un ensemble de 25 éléments, nous obtenons

$S(25,10) = 1.\,203\,163\,392.\,175\,387\,500$ partitions possibles.
# I. 1. - Approche de ce problème par Fischer

Fisher [5] propose un algorithme de programmation dynamique efficace à condition que le critère soit la variance intra-classes et que les éléments que l'on veut classer ne soient mesurés que sur un seul paramètre (c.a.d. que nous pouvons les représenter sur la droite réelle).

On peut obtenir la partition optimale pour plusieurs centaines d'éléments. Le coût de cette méthode est comparable à celui des méthodes de classification hiérarchiques. Ce résultat ne peut-être obtenu que grâce à ce que Fischer nomme la **propriété d'ordre**.

## Définition de la propriété d'ordre [P.O.]

Soit un ensemble $E = \{e_1, e_2, ..., e_n\}$ de n éléments mesurés par un paramètre Q. A chaque élément $e_i$ de E on associe sa mesure $q_i$ et un poids $w_i$.

On dit qu'une partition P de k classes $P_1...P_k$ possède la propriété d'ordre [P.O.] si pour deux éléments $e_i$ et $e_j$ de E classés dans la même classe $P_\ell$ alors : $\forall e_k \in E$ tel que : $q_i < q_k < q_j$ on a $e_k \in P_\ell$

Fisher démontre que pour qu'une partition soit optimale au sens du critère de la variance intra-classe il est nécessaire qu'elle vérifie la propriété d'ordre [P.O.]
## I.2. - Autres approches

Récemment Vinod [9] a généralisé les résultats de Fisher et donne une formulation du problème par la programmation linéaire en nombres entiers.

Les éléments sont alors des points dans l'espace euclidien à p dimensions mais il conserve le critère de la variance intra-classe. Pour résoudre ce problème il généralise la propriété d'ordre de Fisher.

**[G.P.O] Définition de la propriété d'ordre généralisée :**

Soit un ensemble $E = \{e_1, ..., e_n\}$ de n éléments, on associe à cet ensemble une matrice des distances deux à deux des éléments.

$$ \text{Soit } D : \{d_{ij}\} \begin{matrix} i = 1, n \\ j = 1, n \end{matrix} $$

Les quantités dans la $j$-ième colonne peuvent être ordonnées ainsi :

$$ d_{jj} < d_{ji_1} < d_{ji_2} < ... < d_{ji_{n-1}} $$

Nous avons un ordre sur chaque ligne de la matrice D ; par exemple pour la ligne $j$ nous avons l'ordre $j, i_1, i_2, ..., i_{n-1}$. On dit qu'une partition P vérifie la propriété d'ordre généralisée si pour chaque ligne elle vérifie la propriété d'ordre définie par Fisher.

Cette généralisation de la propriété d'ordre nous donne une condition qui n'est plus nécessaire pour l'optimalité.

Rao [8] donne un exemple :

Soient quatre points dans le plan ayant pour coordonnées

$$ x_1 = (1,2), x_2 = (2,3), x_3 = (1,1) \text{ et } x_4 = (1,0) $$

d'où le tableau des carrés de distance suivant :

<table><thead><tr><th></th><th>x<sub>1</sub></th><th>x<sub>2</sub></th><th>x<sub>3</sub></th><th>x<sub>4</sub></th></tr></thead><tbody><tr><th>x<sub>1</sub></th><td>0</td><td>2</td><td>1</td><td>4</td></tr><tr><th>x<sub>2</sub></th><td>2</td><td>0</td><td>5</td><td>10</td></tr><tr><th>x<sub>3</sub></th><td>1</td><td>5</td><td>0</td><td>1</td></tr><tr><th>x<sub>4</sub></th><td>4</td><td>10</td><td>1</td><td>0</td></tr></tbody></table>
La partition optimale au sens du critère de la variance est
({x₁, x₂}, {x₃, x₄}) pourtant x₁ est plus près de x₃ que x₂. Nous
pouvons le vérifier en construisant les quatre ordres associés au
tableau des distances

pour x₁ on a 1 < 3 < 2 < 4

pour x₂ on a 2 < 1 < 3 < 4

pour x₃ on a 3 < 1 = 4 < 2

pour x₄ on a 4 < 3 < 1 < 2

on voit que la partition optimale n'induit pas sur la ligne x₁ la con-
dition d'ordre donnée par Fisher.

Mais on peut vérifier qu'il n'y a aucune partition qui vérifie
cette condition d'ordre généralisée. Alors si on pose comme hypothèse
qu'il existe une partition qui vérifie cette condition d'ordre généralisée
on peut démontrer que, dans ce cas, la condition est nécessaire.

Le problème a été aussi étudié par Garfindel et Nemhausser [ 6 ]
et par Edwards et Cavalli [ 4 ] donnant un algorithme de programmation
dynamique efficace pour résoudre ce problème mais à condition que l'on se
restreigne à deux classes.

1.3. - *Notre approche*

Dans cet article nous nous proposons de reprendre le programme de
programmation dynamique de Fisher en essayant de l'appliquer sur un
ensemble de critères adaptés à un tableau de contingence. Le problème
peut être posé de la manière suivante :

Soit un ensemble E = {e₁, ..., eₙ} de n éléments mesurés par un
paramètre ordonné X.

Sur cet ensemble E de n éléments nous avons, à priori, une partition
en l classes : P = (P₁, ..., P_l).

On recherche la partition Q respectant la condition d'ordre sur X
qui optimise le critère W associé au tableau de contingence Q x P.
## II. - Algorithme de Fisher [5]

Les éléments sont représentés sur la droite réelle. Nous cherchons la partition qui minimise la variance intra-classe ce qui peut être écrit comme ceci :

$$ \text{Minimiser} \quad \sum_{i=1}^{n} \sum_{j=1}^{K} \omega_i \delta_j^i (x_i - \bar{x}_j)^2 $$

où

n est le nombre d'élément de l'ensemble E que l'on veut classer
K est le nombre de classes, non vides, de la partition que l'on désire

$\omega_i$ est le poids de l'élément $e_i$ de E

$x_i$ est la valeur de l'élément $e_i$ de E

$\delta_j^i = 1$ si l'élément $e_i$ a été classé dans la classe j

$\delta_j^i = 0$ sinon

$$ \text{et } \bar{x}_j = \frac{\sum_{i=1}^{n} \omega_i \delta_j^i x_i}{n \sum_{i=1}^{n} \omega_i \delta_j^i} \quad (\bar{x}_j \text{ est la moyenne de la classe j}) $$

Nous supposons que si $k > i$ alors $x_k > x_i$

Nous devons aussi nous assurer que $x_i \neq x_j$ si $i \neq j$. Sinon il faut regrouper $e_i$ et $e_j$ en un même élément en lui affectant le poids $\omega_i + \omega_j$.

Fisher démontre que pour qu'une partition P puisse être optimale pour le critère de la variance intra-classe elle doit vérifier la propriété d'ordre [P.O]. (C'est-à-dire qu'elle doit être composée de K segments de droite). Puis il définit une relation de recurence permettant de parcourir l'ensemble des partitions vérifiant la propriété d'ordre.
Pour démontrer que l'algorithme de Fisher nous donne bien la meilleure solution nous avons divisé la démonstration en deux parties :

- $\text{1ère partie :}$ la partition optimale doit vérifier la propriété d'ordre [P.O].

- $\text{2ème partie :}$ définir un algorithme efficace qui, en parcourant l'ensemble des partitions vérifiant la propriété d'ordre [P.O] permet d'extraire dans cette ensemble la meilleure partition.
(Un algorithme simple nous permet de résoudre le problème c'est l'algorithme d'énumération complète mais il est non efficace).

## II. 1. Partie I

La partition en k classes non vides, minimisant le critère de la variance intra-classe, doit vérifier la propriété d'ordre [P.O].

### Démonstration

Supposons que la partition P en k classes non vides minimisant le critère de la variance intra-classe ne vérifie pas la propriété d'ordre [P.O]. Alors on peut construire une partition R en k classes non vides, qui améliore le critère de la variance intra-classe et qui vérifie la propriété d'ordre [P.O] ;

Soient ($P_1, ..., P_k$) les k classes de P, ($R_1... R_k$) les k classes de R ; on associe à chaque classe $P_i$ de P un centre de gravité noté $g_i$

La partition R est construite ainsi :

On affecte $x_i$ à $R_j$ si $(x_i - g_j)^2 < \text{Min}_{\ell \neq l} (x_i - g_\ell)^2$,
$\ell=1, ..., k$

on construit la partition R.
Vérifions que R améliore le critère W de la variance intra-classe

Soit Q la partition issue de l'intersection de deux partitions
P et R, on note $C_{ij} = P_i \cap R_j$

$$
d'où Q = (C_{11}, \dots, C_{kk})
$$

$$
\text{alors } W(P) = \sum_{i=1}^{k} \sum_{j=1}^{k} \sum_{e_{\ell} \in C_{ij}} (x_{\ell} - g_i)^2 g_i \text{ centre de gravité de } P_i
$$

$$
\text{et } W(R) = \sum_{i=1}^{k} \sum_{j=1}^{k} \sum_{e_{\ell} \in C_{ij}} (x_{\ell} - g_j^*)^2 g_j^* \text{ centre de gravité de } R_j
$$

. si i ≠ j on a affecté e_ℓ de P_i à R_j. Le centre de gravité de P_j est plus proche de x_ℓ que celui de P_i nous avons

$$
\forall x_{\ell} \in C_{ij} \ (i \neq j) \ (x_{\ell} - g_{i})^{2} > (x_{\ell} - g_{j})^{2}
$$

. si i = j il n'y a pas de modification.

On suppose aussi que R est différent de P donc on peut écrire que :

$$
\sum_{i=1}^{k} \sum_{j=1}^{k} e_{\ell}^{\Sigma} e_{C_{ij}}^{\Sigma} (x_{\ell} - g_j)^2 < \sum_{i=1}^{k} \sum_{j=1}^{k} e_{\ell}^{\Sigma} e_{C_{ij}}^{\Sigma} (x_{\ell} - g_i)^2 \quad [1]
$$

et d'après le théorème de Huygens on a

$$
W(R) = \sum_{j=1}^{k} e_{\ell}^{\Sigma} e_{R_j}^{\Sigma} (x_{\ell} - g_j^*)^2 < \sum_{j=1}^{k} e_{\ell}^{\Sigma} e_{R_j}^{\Sigma} (x_{\ell} - g_j)^2 \quad [2]
$$

1'inégalité [1] peut aussi s'écrire :

$$
\sum_{j=1}^{k} \sum_{i=1}^{k} \sum_{e_{\ell} \in C_{ij}} (x_{\ell} - g_j)^2 < \sum_{i=1}^{k} \sum_{j=1}^{k} \sum_{e_{\ell} \in C_{ij}} (x_{\ell} - g_i)^2
$$

d'où

$$
\sum_{j=1}^{k} \sum_{e_{\ell} \in R_j} (x_{\ell} - g_j)^2 < \sum_{i=1}^{k} \sum_{e_{q} \in P_i} (x_q - g_i)^2
$$

et en comparant cette inégalité avec l'inégalité [2] on a.
$$ W (R) = \sum_{j=1}^{k} \sum_{e_{\ell} \in R_j} (x_{\ell} - g_j^*)^2 < \sum_{i=1}^{k} \sum_{e_q \in P_i} (x_q - g_i)^2 = W (P) $$

$$ \text{donc } W(R) < W(P) $$

## Alors R vérifie la propriété d'ordre de Fisher

Il suffit de démontrer que l'affectation des points de E au centre de gravité le plus proche découpe notre droite en k segments.

Si $e_{\ell} \in E$ a été classé dans $P_j$ ceci peut s'exprimer par

$$ \forall_i \neq j (x_{\ell} - g_i)^2 > (x_{\ell} - g_j)^2 \quad \text{et aussi par} $$

$$ \forall_i \neq j |x_{\ell} - g_i| > |x_{\ell} - g_j| $$

R ne vérifie pas la propriété d'ordre cela veut dire qu'il existe un élément $e_q$ de E vérifiant $g_j^* < x_q < x_{\ell}$ et que cet élément n'est pas classé dans $R_j$.

Démontrons que cette affirmation est fausse l'élément $x_q$ est classé dans la classe $R_i$, alors le centre de gravité $g_i^*$ de cette classe ne peut se situer que dans les trois cas suivants :

$$ \text{a)} \quad g_j^* < g_i^* < x_{\ell} $$

$$ \text{b)} \quad g_i^* < g_j^* $$

$$ \text{c)} \quad g_i^* > x_{\ell} $$

a) Impossible car la règle d'affectation de $x_{\ell}$ implique que

$$ |x_{\ell} - g_j^*| < |x_{\ell} - g_i^*| $$

b) on a

$$ x_q - g_i^* = (x_q - g_j^*) + (g_j^* - g_i^*) $$

ce qui entraîne

$$ (x_q - g_i^*) < (x_q - g_j^*) $$
$$ (g_i^* - x_q) = (g_i^* - x_\ell) + (x_\ell - x_q) $$

$$ (x_\ell - x_q) > 0 \text{ et} $$

$$ (g_i^* - x_q) > (x_\ell - g_j^*) \text{ (d'après la règle d'affectation de } x_\ell\text{) d'où} $$

$$ (g_i^* - x_q) > (x_\ell - g_j^*) > (x_q - g_j^*) \qquad \text{c.q.f.d.} $$

## Démonstration géométrique

Si $|g_j^* - x_\ell| < \min_{i \neq j} |g_i^* - x_\ell|$ les centres de gravité $g_i$ doivent se trouver uniquement dans les zones hachurées ci-dessous

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

et s'il existe un $e_q$ de E tel que $g_j^* < x_q < x_\ell$ on peut alors voir que $x_q$ doit nécessairement vérifier $|g_j^* - x_q| < \min_{i \neq j} |g_i^* - x_q|$

c.q.f.d.

Nous avons démontré que R vérifie la propriété d'ordre [P.0] et de plus elle améliore le critère de la variance intra-classe.

Cela implique que la propriété d'ordre est une condition nécessaire pour qu'une partition puisse être optimale au sens du critère de la variance intra-classe.

## II.2. - Partie II

Un algorithme nous permettant de trouver la partition en K classes non vides optimale pour le critère de la variance intra-classe peut être défini ainsi :

**Etape 1** : Enumération complète pour trouver la partition optimale en 2 classes de notre ensemble E.
**Etapes suivantes** : La relation de recurrence ci-dessous nous permet de passer de (k-1) classes à k classes pour la recherche de la partition optimale.

Cette relation de recurrence s'écrit ainsi :

$$ [R1] F_k(i) = \min_{1<i<j} [c_{ij} + F_{k-1}(j+1)] \text{ pour } j = 1, \dots, n \\ k = 3, \dots, K $$

avec :

- $c_{ij}$ ($j > i$) est la variance intra-classe des éléments de E dont la valeur est comprise entre $q_i$ et $q_j$.

- $F_k(i)$ est la valeur optimale du critère de la variance intra-classe pour un partitionnement en k classes de la sous population $\{e_1, \dots, e_n\}$

## Démonstration

**Etape 1** : nous pouvons faire l'énumération complète de l'ensemble des partitions en 2 classes non vides respectant la propriété d'ordre [P.O] de la manière suivante :

- On construit la première partition $(\{e_1\}, \{e_2 \dots e_n\})$ et on calcule le critère de la variance pour la classe $\{e_2, \dots, e_n\}$ nous noterons cette valeur $F_1(2)$.

La construction de la $j^{\text{ième}}$ partition se fait ainsi :

$(\{e_1, \dots, e_j\}, \{e_{j+1}, \dots, e_n\})$. On calcule la variance de la classe $\{e_1, \dots, e_j\}$ soit $F_1(j)$.

Et on continue ainsi de suite jusqu'à la partition $(\{e_1, \dots, e_{n-1}\}, \{e_n\})$.
Nous avons ainsi construit les n partitions en deux classes respectant la propriété d'ordre [P.O]. Pour trouver la partition optimale il suffit de rechercher celle qui minimise le critère de la variance intra-classe.
Et de plus nous avons initialisé la relation de recurrence [R1].
### Etapes suivantes :

On notera $w(B)$ la variance de la classe BCE. Le critère de la variance intra-classe d'une partition $P$ s'écrit alors :

$$W(P) = \sum_{j=1}^{k} w(B_j)$$

ou $B_1, \dots, B_k$ sont les classes de $P$ et $B_1 = (e_1, \dots, e_i)$

### Lemme

Si $P$ est optimale pour $k$ classes alors ceci implique que la partition $(B_2, \dots, B_k)$ est la partition optimale en $k-1$ classes de l'ensemble $\{e_{i+1}, \dots, e_n\}$.

### Démonstration

Sinon il suffirait de prendre la partition optimale en $k-1$ classe, de cet ensemble soit $(A_2, \dots, A_k)$ alors on aurait

$$\sum_{j=2}^{k} w(A_j) < \sum_{j=2}^{k} w(B_j)$$

d'où la partition $Q$ construite ainsi :

$P = (B_1, A_2, \dots, A_k)$ vérifie ceci :

$$W(Q) = w(B_1) + \sum_{j=2}^{k} w(A_j) < \sum_{j=1}^{k} w(B_j) = W(P)$$

donc $(B_2, \dots, B_k)$ est la partition optimale en $k-1$ classes de l'ensemble $\{e_{i+1}, \dots, e_n\}$ c.q.f.d.
Ainsi la partition optimale en k classes appartient bien à l'ensemble des partitions suivantes : ({e₁}, O₂), ..., ({e₁}, ..., eₙ₋₁), Oₙ₋₂).

ou O₂, ..., Oₙ₋₂ sont les partitions optimales, de sous ensemble de E, construites à l'étape k-1. La valeur associée à une partition Oᵢ est donnée par Fₖ₋₁ (i). Pour l'étape k il faut rechercher la partition Cᵢ en k-1 classes optimales du sous ensemble {e₁, ..., eₙ} en parcourant l'ensemble suivant

$$ ( \{e_i, \dots, e_j\}, O_{j+1}), \dots, ( \{e_i, \dots, e_{n-k+1}\}, O_{n-k+2}) $$

(cf. organigramme en annexe II)

**Remarque** : nous pouvons généraliser l'application de cet algorithme à d'autres critères que le critère de la variance intra-classe ; et à condition de supposer que l'on recherche une partition qui respecte la propriété d'ordre de Fisher nous obtenons la partition optimale.

## Généralisation

L'algorithme décrit dans la partie II permet de trouver la partition P = (B₁, ..., Bₖ) en k classes non vides, parmi l'ensemble des partitions respectant la propriété d'ordre, optimale pour un critère W (P) pouvant s'écrire de la manière suivante W (P) = Σ<sub>i=1</sub><sup>k</sup> w (Bᵢ) où w (Bᵢ) est un nombre réel positif pour toutes les classes Bᵢ appartenant à W(E).

## Démonstration

C'est la même démonstration que celle de la partie II car la seule propriété du critère de la variance que nous avons utilisé est que ce critère peut se mettre sous la forme :

$$ W(P) = \sum_{i=1}^{k} W(B_i) \text{ où } W(B_i) \text{ est, dans ce cas, la variance de la classe } B_i \text{ (et de plus, c'est un nombre positif ou nul).} $$
### III. - Remarques sur la propriété d'ordre généralisée de Vinod

Chaque ligne de la matrice des distances D doit vérifier la propriété d'ordre de Fisher, c.a.d. que si $i_k$ appartient à la classe C de l'individu j alors $\Psi_{ij}$ vérifiant $d_{ji_k} < d_{ji_l}$ ; $i_l$ doit appartenir à C et ceci quelque soit les éléments appartenant à C. Dont on peut écrire que la propriété d'ordre généralisée de Vinod est équivalente à $\Psi_{i,j}$ appartenant à la même classe alors $\Psi_k$ n'appartenant pas à cette classe on a $d_{ij} < d_{ik}$ et $d_{ij} < d_{jk}$ où $\Psi_{i,j} = \max\{d_{ij}\} < \min\{d_{ik}\} \le \Psi_k$

Cette propriété est très forte et il est peut probable que l'on puisse trouver facilement une partition en K classes vérifiant cette propriété.

Et si, de plus, on suppose qu'il existe une partition en K classes vérifiant la propriété d'ordre généralisée de Vinod on démontre la Méthode des Nuées Dynamiques permet d'obtenir la partition optimale.

Prenons la méthode des Nuées Dynamiques [1] ou les noyaux sont définis par un seul élément appartenant à l'ensemble que l'on désire classer.

Nous avons K noyaux $\{n_1, ..., n_K\}$ où $n_i \in E$ et si de plus on suppose que les noyaux appartiennent chacun à une classe de la partition vérifiant [G.P.O] alors à la première itération on obtient la partition optimale.

Donc cette propriété d'ordre est très restrictive.
IV. - Partitionnement sous contrainte d'ordre total

Nous nous donnons un ensemble fini E de N éléments :

E = {e₁, ..., eᵢ, ..., eₙ}. On appelle P (E) l'ensemble des classes de E.

A chaque élément eᵢ de E est associé un couple (xᵢ, ωᵢ) tel que
xᵢ ∈ X et ωᵢ ∈ Ω où

X est un ensemble totalement ordonné (par exemple R)

Ω est un ensemble fini, il sera appelé l'ensemble des formes a priori

On appelle P<sub>k</sub> (E) l'ensemble des partitions en K classes, non vides,
et respectant la propriété d'ordre de Fisher sur l'ensemble X. (c.a.d.
soit P = (B<sub>1</sub>, ..., B<sub>k</sub>) ∈ P<sub>k</sub> (E) si e<sub>i</sub> ∈ B<sub>m</sub> et e<sub>j</sub> ∈ B<sub>m</sub> ∀ e<sub>l</sub> ∈ E vérifiant
x<sub>i</sub> < x<sub>l</sub> < x<sub>j</sub> alors e<sub>l</sub> ∈ B<sub>m</sub>)

Le problème est de rechercher la partition Q de P_k (E) **optimale** pour
un critère W donné. On impose au critère W de s'écrire de la façon
suivante :

$$
W(P) = \sum_{i=1}^{K} w(B_i) \text{ où}
$$

w est une application de P (E) dans R⁺ mais cette application peut tenir compte de l'affectation des éléments de E dans Ω.

Théorème 3

L'algorithme décrit dans la partie II permet de résoudre ce problème.
***Démonstration***

Reprenons pour cette démonstration la généralisation cette partie II.

Ce théorème nous permet d'écrire que l'algorithme trouve bien, parmi
l'ensemble des partitions respectant la propriété d'ordre de Fisher, la
partition optimale au critère W (P) si ce critère peut s'écrire sous la
forme $W(P) = \sum_{i=1}^{k} w(B_i)$. Nous sommes bien ici dans ce cas.
Il faut maintenant adapter la fonction de recurrence [R1] à
notre problème. Cette relation s'écrit maintenant

$$
\text{[R2]} \quad F_k(i) = \min_{1<i<j} [C_{ij} + F_{k-1}(j-1) \text{ pour } j = 1, \dots, N \\ \phantom{\text{[R2]} \quad F_k(i) = \min_{1<i<j} [} k = 3, \dots, K]
$$

(On suppose que l'ensemble E est rangé suivant l'ordre total de X)
avec

$$
C_{ij} = w(B) \text{ ou } B = \{e_i, \dots, e_j\}
$$

et

$F_{k-1}(j-1)$ est la valeur optimale du critère W pour le partitionnement
en $k-1$ classes de la sous population $\{e_{j-1}, \dots, e_n\}$ de E.

C.Q.F.D.
## V. - Exemples de critères

### V.1. - Critère basé sur la quantité d'information

L'ensemble $\Omega$ est l'ensemble des formes a priori de X l'ensemble des résultats de E. A chaque élément $e_i$ de E est associé une forme a priori $\omega_i$ et le résultat $x_i$ d'une mesure sur l'ensemble des réels.

On associe à ces deux ensembles une mesure de probabilité conjointe $P_{X\Omega}$ définie de la manière suivante :

si U est un intervalle de X alors

$$P_{X\Omega}(U, \omega) = \frac{\text{card}(\{e_i \in E / x_i \in U\} \cap \{e_i \in E / \omega_i \in \omega\})}{\text{card}(E)}$$

On peut ainsi définir les probabilités induites sur les deux ensembles X et $\Omega$ telles que

$$\forall U \text{ intervalle de } X, P_X(U) = \sum_{\omega \in \Omega} P_{X\Omega}(U, \omega)$$

$$\text{et } \forall \omega \in \Omega \quad P_{\Omega}(\omega) = \int_X d_P_{X\Omega}(x, \omega)$$

### Définition

On appelle Information mutuelle au sens de SHANNON ou information "utile" la fonction suivante :

$$I(P) = \sum_{i=1}^{k} \sum_{\omega \in \Omega} P_{X\omega}(P_i, \omega) \log \frac{P_{X\omega}(P_i, \omega)}{P_X(P_i)P_{\Omega}(\omega)}$$
### Proposition 5

L'algorithme de la partie II, permet de trouver la partition P de l'ensemble $P_K(E)$ des partitions en K classes de l'ensemble E respectant la propriété d'ordre pour l'ensemble X optimale pour le critère I :

$$I(P) = \begin{cases} \text{Max} & I(Q) \\ Q \in P_k(E) \end{cases}$$

### Démonstration

D'après le théorème 4 il suffit que le critère I puisse se mettre sous la forme suivante :

$$I(P) = \sum_{i=1}^{k} W(B_i) \quad \text{où } P = (B_1, \dots, B_K)$$

et W une application de P (E) dans $\mathbb{R}$ d'après la définition de l'information au sens de Shannon nous avons

$$I(P) = \sum_{i=1}^{k} \sum_{\omega \in \Omega} P_{X \times \Omega}(P_i, \omega) \log \frac{\hat{P}_{X \times \Omega}(P_i, \omega)}{P_X(P_i) P_{\Omega}(\omega)}$$

$$\text{avec } B_i = \{e_j \in E \mid x_j \in P_i \text{ intervalle de } X\}$$

et $(P_1, \dots, P_K)$ un découpage en K intervalles disjoints de X.

$$\text{Si on pose } W(B_i) = \sum_{\omega \in \Omega} P_{X \times \Omega}(P_i, \omega) \log \frac{P_{X \times \Omega}(P_i, \omega)}{P_X(P_i) P_{\Omega}(\omega)}$$

alors on vérifie que cette valeur ne dépend que de $B_i$ donc ce critère de l'information au sens de Shannon peut s'écrire suivant la forme

$$I(P) = \sum_{i=1} W(B_i)$$

avec W une application de P (E) dans $\mathbb{R}$

C.Q.F.D.
## V.2. - Critère base sur le khi_2

Nous reprennons la définition des ensembles E, Ω et X et la définition de la probabilité conjointe $P_{Xx\Omega}$ du paragraphe précédent (V.1).

Le problème est maintenant de découper l'ensemble des nombres réels en K intervalles disjoints tel que ce découpage maximise le $\chi^2$ de contin-gence entre la probabilité conjointe $P_{Xx\Omega}$ et le produit des probabilités marginales des deux ensemble X et Ω qui sera considéré comme probabilité théorique.

Notons que la probabilité conjointe $P_{Xx\Omega}$ sera égale à $P_X \circ P_\Omega$ s'il y a indépendance entre E et Ω.

### Définition

Nous appellerons intensité de dépendance, pour un partitionnement P en K classes non vide de E, entre la probabilité conjointe $P_{Xx\Omega}$ et la probabilité produit $P_X \cdot P_\Omega$ la valeur $\emptyset^2 (P)$ tel que

$$ \emptyset^2 (P) = \sum_{i=1}^{k} \sum_{\omega \in \Omega} \frac{(P_{Xx\Omega}(P_i, \omega) - P_X(P_i) \cdot P_\Omega(\omega))^2}{P_X(P_i) P_\Omega(\omega)} $$

### Théorème 6

L'algorithme de la partie II nous permet de trouver P de $P_k(E)$ qui maximise l'intensité de dépendance entre le découpage en K intervalles disjoints et non vide de l'ensemble des nombres réels et l'ensemble des formes a priori $\Omega$.

$$ \emptyset^2 (P) = \max_{Q \in \mathcal{P}_k(E)} \emptyset^2 (Q) $$

### Démonstration

C'est la même démonstration que pour le théorème 5. Il suffit de vérifier que la valeur

$$ W(B_i) = \sum_{\omega \in \Omega} \frac{(P_{Xx\Omega}(P_i, \omega) - P_X(P_i) \cdot P_\Omega(\omega))^2}{P_X(P_i) \cdot P_\Omega(\omega)} $$

ne dépend que de $B_i$ ce qui se vérifie facilement.
Soient I et J deux ensembles en correspondance tels que $\text{card}(I) = p$ et $\text{card}(J) = q$. Nous noterons $P_{I \times J}$ la probabilité conjointe entre I et J et $P_I$ et $P_J$ les probabilités sur I et J alors l'inertie de ce nuage N est

$$I(N) = n \sum_{i,j} \frac{(P_{ij} - P_i \cdot P_j)^2}{P_i \cdot P_j}$$

Pour justifier de l'existence d'une liaison stochastique entre deux variables aléatoires I et J on utilise cette inertie qui suit, dans l'hypothèse d'indépendance, un loi du $\chi^2$ à (p-1) (q-1) degrés de liberté.

On montre immédiatement que

$$\chi^2 = n \phi^2$$

Nous avons une relation simple entre le $\chi^2$ de contingence et l'intensité de dépendance.

Dans le cas de l'hypothèse d'indépendance on recherche, avec cette méthode, la meilleure liaison stochastique entre un découpage en intervalles disjoints de l'ensemble des réels et l'ensemble J des formes a priori

## Généralisation à plusieurs paramètres

On a toujours $\Omega$ l'ensemble des formes a priori mais nous avons p paramètres. A chaque individu on associe maintenant un (p+1) uple tel que $e_i \in E$ ; $(x_1^i, ..., x_p^i, \omega_i) \in \mathbb{R}^p \times \Omega$ ou $x_j^i$ est la valeur que prend l'individu $e_i$ pour le paramètre j.

Alors on décompose le (p+1) uple associé à chaque individu en p couples $(x_j^i, \omega_i)$ $j = 1, ..., p$. A chaque couple $(x_j^i, \omega_i)$ nous revenons au cas précédent c.a.d. on recherche pour le paramètre j la meilleure liaison stochastique entre découpage en $k_j$ intervalles disjoints de ce paramètre et l'ensemble des formes a priori.
Donc nous avons p découpages en $k_1, ..., k_p$ intervalles disjoints.
Chaque découpage $U^j = (U^j_1, ..., U^j_{k_j})$ est optimal pour la liaison de
dépendance du paramètre j et de $\Omega$. Si nous construisons le tableau de
contingence suivant : $(U^1, ..., U^P) \times \Omega$ alors l'intensité de dépendance
est optimale au sens suivant :

Soit $P_{k_j}(E,j)$ l'ensemble des partitions en $k_j$ classes, respectant
la propriété d'ordre de Fisher sur le paramètre j alors

si $(V^1, \dots, V^P)$ est un découpage quelconque on a :

$$ \emptyset^2 (V^1, \dots, V^P) < \emptyset (U^1, \dots, U^P) $$

ou $(U^1, \dots, U^P)$ étant le p uple des découpages optimaux que nous
avons obtenus.

Dans l'hypothèse d'indépendance nous avons la meilleure liaison
stochastique entre les p découpages en $k_j$ intervalles des paramètres
et l'ensemble des formes a priori et dans ce cas l'inertie suit un

$$ \chi^2 \text{ à } \left( \sum_{i=1}^{p} (k_i - 1) \right), (q - 1) \text{ degré de liberté.} $$

Dans ce cas nous pouvons vérifier avec le test du $\chi^2$ si la liaison
stochastique entre les p paramètres et les formes a priori est forte ou pas.

Si cette liaison n'est pas significative pour le test du $\chi^2$
il est donc inutile de rechercher un codage qui est fonction croissante
de chaque paramètre puisque la valeur, au sens du $\chi^2$, de ce codage
sera inférieure à la valeur que nous avons obtenue.
V.4. - Critère basé sur la variance

A l'ensemble E que l'on désire partitionner est associé un ensemble
totalement ordonné X et un ensemble Ω de mesures.

A chaque élément $e_i$ de E est associé p mesures $(y_1^i, ..., y_p^i)$ e Ω et une valeur $x_i$ e X.

L'ensemble totalement ordonné X peut être la variable temps ou la
profondeur ou l'âge des individus de E. Ici on désire découper en inter-
valles de temps ou de profondeur ou tranches d'âge l'ensemble E de manière
à minimiser le critère de la variance sur l'ensemble Ω des p mesures
(qui est souvent $\mathbb{R}^p$).

Pour pouvoir utiliser l'algorithme que nous avons décrit il suffit que
le critère se décompose ainsi :

$$
W(P) = \sum_{i=1}^{k} W(B_i) \text{ ou } P = (B_1 \dots B_k) \text{ et } P \in \mathcal{G} \quad (E)
$$

Soit $g_i$ le centre de gravité de la classe $B_i$ alors la variance de cette classe s'écrit

$$
W(B_i) = \sum_{e \in B_i} \sum_{j=1}^{p} (y_j^{(e)} - g_i^j)^2
$$

cette valeur est indépendante des autres classes. Nous pouvons donc
utiliser l'algorithme de la partie II.

C.Q.F.D.
# ANNEXE I

## Formule pour le clacul du nombre de partition en k classes d'un ensemble de n éléments

On note $S(n,k)$ le nombre de partitions en k classes d'un ensemble de n éléments. Le nombre est égal à :

$$S(n,k) = \frac{1}{k!} \sum_{i=0}^{k} C_{i}^{k} (-1)^{k-i} i^{n} \quad [1]$$

pour démontrer cette formule il faut vérifier la relation de récurrence suivante :

$$S(n,k) = S(n-1, k-1) + k S(n-1, k) \quad [2]$$

valable pour $1 \le k < n$ et en posant $S(n,0) = 0$

1. - L'interprétation de la formule de recurrence [2] est la suivante :

On suppose que le nombre de partitions d'un ensemble de n-1 éléments en k classes et celui en k-1 classes sont connus.

(Ce qui correspond dans la relations de recurrence [2] à $S(n-1, k-1)$ et $S(n-1, k)$ donnés).

Le fait d'affecter un nouvel élément à cet ensemble entraine deux solutions :

a) soit cet élément crée une nouvelle classe

b) soit il est mis dans une classe non vide.

Le nombre de partitions en k classes de cet ensemble de n éléments est donc égal à la somme des partitions créée par la solution a) et celles par la solution b).

Pour la solution a) le nombre de partitions est égal au nombre de partitions en k-1 classes de n-1 éléments puisque le n-ième élément crée sa propre classe d'où le nombre est égal à $S(n-1,k-1)$ pour la solution b) on peut affecter le nouvel élément dans k classes différentes et dans chaque cas le nombre de partitions est égal au nombre de partitions en k classes de l'ensemble de n-1 éléments d'où le nombre est égal à $k S(n-1,k)$.
## 2. - Démonstration

Le deuxième membre de [2] s'écrit au moyen de l'expression [1] proposée de la façon suivante :

$$ \sum_{i=0}^{k-1} (-1)^{k-1-i} \frac{i^{n-1}}{i! (k-1-i)!} + \sum_{i=0}^{k} (-1)^{k-i} \frac{i^{n-1}}{i! (k-i)!} $$

en rapprochant les termes de même rang dans les deux sommes il vient

$$ \sum_{i=0}^{k-1} (-1)^{k-i} \left[ \frac{k \cdot i^{n-1}}{i! (k-i)!} - \frac{i^{n-1}}{i! (k-1-i)!} \right] + \frac{k^n}{k!} $$

soit encore

$$ \sum_{i=0}^{k-1} (-1)^{k-i} \frac{i^{n-1}}{i! (k-1-i)!} \left[ \frac{k}{k-i} - \frac{k-i}{k-i} \right] + \frac{k^n}{k!} $$

d'où

$$ \sum_{i=0}^{k-1} (-1)^{k-i} \frac{i^{n-1}}{i! (k-1-i)!} \left[ \frac{i}{k-i} \right] + \frac{k^n}{k!} $$

$$ \sum_{i=0}^{k} (-1)^{k-i} \frac{i^n}{i! (k-i)!} $$

C.Q.F.D.
# ANNEXE II

<figure><img src="image_7.png" /><figcaption>Organigramme de l'algorithme de la partie II</figcaption></figure>
BIBLIOGRAPHIE

[1] DIDAY E., "Nouvelles méthodes et nouveaux concepts en classification automatique et reconnaissance des formes"
Thèse d'Etat 1972.

[2] DIDAY E., "Selection typologique de paramètres"
Rapport de Recherche n° 188 IRIA-Laboria 1976.

[3] BELMAN R.E., and DREYFUS S.E., "Applied Dynamic Programming"
Princeton N°5 1962.

[4] EDWARDS A.W.F., and CAVALLI., SFARZALL., "A Method for Cluster Analysis"
Biometrics (june 1965) 362-75.

[5] FISHER W.D., "On grouping for maximum Homogeneity"
Journal of the American Statistical Association 53 (Dec 58) 789-98.

[6] GARFINDEL R., and NEMHAUSER G.L., "The Set-Partitioning Problem : Set Covering With Equality Constraints"
Operation Research 17 (Sept-Oct 69) 848-56.

[7] JENSEN R.E., "A Dynamic Programming Algorithm for Cluster Analysis"
Operation Research 12 (Nov-Dec 69) 1084-57.

[8] RAO M.R., "Cluster Analysis and Mathematical Programming"
Journal of the American Statistical Association (Sept 71) 622-626.

[9] VINOD M.D., "Integer Programming and theory of Grouping"
Journal of the American Statistical Association (juin 69) 506-19.

[10] WARD J.H. Jr., "Hierarchical Grouping to optimise an objective function"
Journal of the American Statistical Association (Mars 53) 236-244.