# Sélection typologique de paramètres

Edwin Diday

► To cite this version:

Edwin Diday. Sélection typologique de paramètres. [Rapport de recherche] IRIA-RR-188, IRIA. 1976, pp.34. hal-04716343

HAL Id: hal-04716343

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

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
RIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

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

laboratoire de recherche
en informatique
et automatique

SÉLECTION TYPOLOGIQUE
DE PARAMÈTRES

E. DIDAY

Rapport de Recherche N° 188

Août 1976
# SÉLECTION TYPOLOGIQUE DE PARAMETRES

E. Diday

## Résumé :

Etant donné un ensemble d'objets E caractérisés par deux groupes de paramètres $J_1$ et $J_2$, il s'agit de détecter simultanément le (ou les) paramètre(s) de $J_1$ et la partition de E (en un nombre de classes donné à l'avance) qui optimisent un certain critère W. Ce critère exprime l'adéquation entre les paramètres sélectionnés de $J_1$, la partition obtenue et les paramètres de $J_2$. On introduit des algorithmes donnant une bonne approche à ce type de problèmes. Leurs propriétés sont étudiées notamment dans le cas de données nominales pour des distances quadratices. Enfin, les aspects régression locale et analyse discriminante typologique sont introduits.

## Abstract :

Given a set of objects E characterized by two groups of parameters $J_1$ and $J_2$, the problem is to detect simultaneously the parameter(s) of $J_1$ and the partition of E (into a number of classes given beforehand) that optimize a certain criterion W. This criterion expresses the fit between the selected parameters of $J_1$, the partition that has been obtained and the parameters of $J_2$. Algorithms are introduced that provide a good approach to this type of problem. Their properties are studied in the case of nominal data for quadratic distances. Finally local regression and typological discrimination analysis are introduced.
# PLAN

## RESUME

1. INTRODUCTION

2. NOTATIONS

3. Le PROBLEME

4. COMPARAISON avec la SEGMENTATION CLASSIQUE et la DISCRIMINATION

5. Les FONCTIONS de REPRESENTATION, d'IDENTIFICATION et NOUVELLE EXPRESSION du CRITERE

6. L'ALGORITHME

7. ETUDE de la CONVERGENCE

8. CAS d'une DISTANCE QUADRATIQUE

9. Sur une FAMILLE de PROBLEMES de CLASSIFICATION avec CONTRAINTES MULTIPLES

10. CODAGE sous CONTRAINTE

11. MODELES LINEAIRES LOCAUX

12. ANALYSE DISCRIMINANTE TYPOLOGIQUE
# 1. - Introduction

Dans la pratique, l'utilisateur se trouve de plus en plus souvent confronté à des tableaux de données de grande taille ; chercher à sélectionner les paramètres qui "expliquent" le mieux est l'un de ses soucis majeurs. Le but de ce travail est de permettre la construction d'un ensemble de programmes pour aider l'utilisateur dans cette tache de sélection au sens de certains critères mathématiques bien significatifs et pour de grands tableaux.

Tous ces programmes nécessitent en entrée, la donnée d'un ensemble $E$ d'objets caractérisés par deux groupes de paramètres $J_1$ et $J_2$. Il s'agit de sélectionner les paramètres de $J_1$ qui "expliquent" le mieux $J_2$. Il faut se méfier du terme "expliquer", en fait, les méthodes dont il est question permettent la mise en évidence de certaines occurences numériques entre le ou (les) paramètres sélectionnés de $J_1$ et les paramètres de $J_2$. Ce sera ensuite à l'utilisateur d'interpréter cette constatation en justifiant ou non le terme "expliquer" par une étude complémentaire.

Du point de vue de la reconnaissance des formes, (cf. [6], [7]) il s'agit généralement de sélectionner un ensemble de paramètres parmi un ensemble $J_1$ qui expliquent au mieux des formes données à priori (caractérisées par un paramètre qualitatif nominal, par exemple). Ici, nous supposons la donnée d'un champ de formes floues, imprécises, caractérisées par les paramètres de $J_2$. On cherche alors simultanément les paramètres de $J_1$ et les formes de $J_2$ tels que ces formes soient "significatives" et que ces paramètres les expliquent au mieux.

Du point de vue de l'analyse des données le formalisme qui est énoncé ici, contient comme cas particulier celui de la segmentation classique, (cf.[1],[2],[3]), et présente des liens avec la discrimination la différence principale venant du fait que la partition obtenue n'est ni imposée par les variables explicatives (comme en segmentation) ni par les variables à expliquer (comme en discrimination).
## 2. - Notations

On note :

- E : l'ensemble des objets.

- J : l'ensemble des paramètres caractérisant les éléments de E.

- $J_1$ : l'ensemble des paramètres explicatifs.

- C : l'ensemble $[J_1]^k = J_1 \times \dots \times J_1$, k fois.

- $J_2$ : l'ensemble des paramètres à expliquer.

- B : est un ensemble qui dépend de $J_2$ ( par exemple, l'ensemble des éléments de E caractérisés par les paramètres de $J_2$, ou encore $B = \mathbb{R}^{\text{card}(J_2)}$).

- $\mathcal{P}$ : l'ensemble des parties de E.

- $\mathcal{P}_k$ : l'ensemble des partitions en k classes de E.
### 3. - Le Problème

Il s'agit d'optimiser le critère. W suivant : W est une application $C \times P_k \to \mathbb{R}^+$ telle que :

$$W (j, P) = \sum_{l=1}^{k} \sum_{i \in [P_j]} \left[ \mu_t (x_i) d_{j_l} (h_{j_l} (P_l), x_{i_{j_l}}) + \mu_s (x_i) d (h(P_l), x_i) \right]$$

où :

- $j = (j_1, \dots, j_k)$, dans ce vecteur on peut avoir $j_i$ identique à $j_l$.

- $P = (P_1, \dots, P_k)$

- $x_i$ est le ième élément de E.

- $[P_j]$ est l'ensemble des indices des éléments de E qui appartiennent à $P_j$

- $h_{j_l}$ est une application $\mathbb{P} \to \mathbb{R}^+$ telle que $h_{j_l} (P_j)$ donne le noyau de $P_j$ pour le paramètre $j_l$ (le noyau est une représentation de $P_j$, par exemple, le centre de gravité de $P_j$ restreint au paramètre $j_l$).

- $h$ est une application $\mathbb{P} \to \mathbb{R}^+$ telle que $h (P_j)$ donne le noyau de $P_j$ pour l'ensemble des paramètres à expliquer ($J_2$).

- $\mu_t$ et $\mu_s$ sont deux applications $E \to \mathbb{R}^+$ qui vérifient la propriété $\mu(A) = \sum_{a \in A} \mu(a) \forall A \subset E$

- $x_{i_{j_l}}$ est la coordonnée $j_l$ de l'élément $x_i$.

- $d_{j_l}$ est une mesure de ressemblance associée au paramètre $j_l$.
Elle permet de mesurer la ressemblance de la $j_\ell$ ième coordonnée d'un élément de E à un noyau donné.

- d' permet de mesurer la ressemblance entre un noyau et un élément de E caractérisé par les paramètres de $J_2$.

**Le problème consiste à chercher le couple $(j^*, P^*)$ qui minimise $W$ parmi tous les éléments de $C \times P$.

Afin de donner une idée intuitive de ce que $W$ exprime, il peut s'agir par exemple de découvrir $j^* = (j_1^*, ..., j_k^*)$ et $P^* = (P_1^*, ..., P_k^*)$ tels que $\forall \ell \in \{1,2, ..., k\}, P_\ell^*$ soit le "moins dispersé possible" dans $J_2$ et pour le paramètre $j_\ell^*$.

**Différentes généralisations du problème sont possibles, ainsi en posant** $j = (j_1^{(1)}, ..., j_k^{(1)}) * ... * (j_1^{(n)}, ..., j_k^{(n)})$.

On peut définir le signe $*$ de différentes manières, par exemple

Les $j_\ell$ sont alors des paquets de paramètres (pouvant éventuellement constituer une partition). Chaque paquet peut correspondre par exemple à une combinaison linéaire ou à une combinaison logique (cas de variables binaires considérés comme variables logiques, le signe "*" peut signifier "ou"). Si le signe $*$ exprime comme combinaison linéaire il s'agit de détecter les $k$ combinaisons linéaires de $n$ paramètres

$$J^{(\ell)} = \sum_{i=1}^{n} \lambda_i j_{\ell}^{(i)} \text{ et } P^* = (P_1^*, ..., P_k^*) \text{ tels que } P^*_\ell \text{ soit le moins "dispersé" possible dans } J_2 \text{ et pour } J^{(\ell)}. \text{ Des techniques d'analyse factorielle peuvent intervenir ici.}$$
## 4. - Comparaison avec la segmentation classique et la discrimination

### 4.1. - La segmentation

On peut décomposer le critère W en deux parties $W_1$ et $W_2$ telles que :

$$W_1 (j,P) = \sum_{l=1}^{k} i \sum_{P_l} \mu_t (x_i) d_{j_l} (h_{j_l} (P_l), x_{i_{jl}})$$

$$W_2 (P) = \sum_{l=1}^{k} i \sum_{P_l} \mu_s (x_i) d (h(P_l), x_i)$$

On a donc $W = W_1 + W_2$. On considère ici que $d$ et $d_l$ sont quadratiques et que $h_{j_l} (P_l) (\text{resp. } h (P_l))$ est le centre de gravité de $P_l$ pour le paramètre $j_l$ (resp. les paramètres de $J_2$). Si l'on fixe $K=2$ et si l'on considère que tous les paramètres de $J_1$ sont dichotomiques, alors la segmentation classique consiste à minimiser d'abord $W_1$ puis $W_2$ de la manière suivante :

toute solution $Y_l = (j^*, P^*)$ telle que $j^* = (j_l, j_l)$ et telle que $P^* = (P_1, P_2)$ est la dichotomie associée au paramètre $j_l$ et fait que

$W_1 (j^*, P^*) = 0$. Chercher ensuite à minimiser $W_2$ parmi l'ensemble des partitions $P^*$ induites par les solutions $Y_l (l=1,2, \dots, \text{card } J_1)$ obtenues à l'étape précédente est exactement le problème de la segmentation classique (cf. $[1]$, $[2]$, $[3]$).

### 4.2. - Discrimination

Pour la discrimination (cf. $[4]$, $[5]$), il s'agit de trouver les paramètres les plus discriminants d'une partition donnée. Le problème que nous posons est différent puisque la partition est recherchée en même temps que les paramètres les plus discriminants. Toutefois les deux problèmes sont voisins si $J_2$ est réduit à un seul paramètre
qualitatif. Cela revient alors à chercher à minimiser $W_2$ qui donne P*
(la partition induite par ce paramètre), puis avec la partition ainsi
obtenue, $W_1$ qui donne j* le (ou les) paramètre (s) explicatif (s) le (ou les)
plus discriminant (s).
5. - Les Fonctions de représentation, d'identification et nouvelle expression du critère

- Soit $D_t : J_1 \times \mathbb{P} \times \mathbb{P} \to \mathbb{R}^+$ une mesure de ressemblance de $j_\ell$ à $P_2$ "conditionnée" par $P_1$, autrement dit, telle que :

$$D_t (j_\ell, P_1, P_2) = \sum_i i e[P_2]^\mu_t (X_i) d_{j_\ell} (h_{j_\ell} (P_1), x_{i,j_\ell})$$

- Soit $D_s : \mathbb{B} \times \mathbb{P} \to \mathbb{R}^+$ une mesure de ressemblance point-groupe telle que :

$$D_s (a, P_1) = \sum_i i e[P_1]^\mu_s (X_i) d (a, X_i)$$

- Calcul des noyaux : on introduit les deux applications $R_1$ et $R_2$ suivantes :

• $R_1 : J_1 \times \mathbb{P} \times \mathbb{P} \to \mathbb{R}^+$ est définie par :

$$R_1 (j_\ell, m, Q, P) = D_t (j_\ell, Q, P_m) = \sum_i i e[P_m]^\mu_t (X_i) d_{j_\ell} (h_{j_\ell} (Q), x_{i,j_\ell})$$

• $R_2 : \mathbb{B} \times \mathbb{P} \times \mathbb{P} \to \mathbb{R}^+$ est définie par :

$$R_2 (a, m, P) = D_s (a, P_m) = \sum_i i e[P_m]^\mu_s (X_i) d (a, X_i)$$

- Soit $\mathbb{L}_k = [J_1 \times B \times \mathbb{P}]^k$ l'espace des noyaux.

L'application $g : \mathbb{P}_k \to [J_1 \times B \times \mathbb{P}]^k = \mathbb{L}_k$ est définie par $g(P) = A$ où $A = (A_1, \dots, A_k)$ avec $A_i = (j_i, a_i, P_i)$ où $j_i$ est l'élément qui minimise $R_1 (\cdot, i, P_i, P)$ parmi $j_\ell \in J_1$ ; $a_i$ est l'élément qui minimise $R_2 (\cdot, i, P)$ parmi $a \in B$.
Calcul des partitions :

Soit le noyau $A_i = (j_i, a_i, Q_i) \in J_1 \times B \times P$ alors
D : $E \times \mathbb{L}_k \to \mathbb{R}^+$ qui mesure la ressemblance entre un élément de E et un noyau est définie par :

$$
D (X_\ell, A_i) = \mu_t (X_\ell) \cdot d_j (h_i (Q_i, X_\ell), X_\ell \cdot j_i) + \mu_s (X_\ell) \cdot d (X_\ell, A_i)
$$

L'application $f : \mathbb{L}_k \to \mathbb{P}_k$ est telle que $f(A) = P$ où
$P = (P_1, \dots, P_k)$ avec $P_i = \{ X \in E/D(X, A_i) \le D(X, A_j) \}$ en cas d'égalité
$X$ est affecté à la classe de plus petit indice.

Avec les notations ainsi introduites, on peut exprimer le
critère à l'aide d'une fonction plus générale :

$W_G : \mathbb{L}_k \times \mathbb{P}_k \to \mathbb{R}^+$ telle que :

$$
W_G (A,P) = \sum_{i=1}^{k} \left[ R_1 (j_i, a_i, Q_i, P) + R_2 (a_i, i, P) \right]
$$

où $A = (A_1, \dots, A_k)$ avec $A_i = (j_i, a_i, Q_i)$, $Q = (Q_1, \dots, Q_k)$ est un
ensemble de $k$ parties de $E$ et $P = (P_1, \dots, P_k) \in \mathbb{P}_k$.

On peut retrouver le critère W introduit en 3) car en prenant
$A_i = (j_i, a_i, P_i) \forall i$ on a $W_G(A,P) = W(A,P)$.
## 6. - L'algorithme

Il est basé sur la construction de deux suites $v_n$ et $u_n$ que nous allons maintenant donner :

On pose $P^{(n)} = (P_1^{(n)}, \dots, P_k^{(n)})$, $A^{(n)} = (A_1^{(n)}, \dots, A_k^{(n)})$ avec $A_i^{(n)} = (j_i^{(n)}, a_i^{(n)}, P_i^{(n-1)})$, $v^{(n)} = (A^{(n)}, P^{(n)})$.

On définit $v_n$ à partir de $v_{n-1}$ comme suit : $v_{n-1} = (A^{(n-1)}, P^{(n-1)})$ permet d'abord de définir $A^{(n)}$ à l'aide de $g$ comme suit : $A^{(n)} = g(P^{(n-1)})$ ; plus précisément :

$$ (1) \left\{ \begin{array}{l} j_i^{(n)} \text{ est l'élément de } J_1 \text{ qui minimise} \\ R_1 (., i, P_i^{(n-1)}) = D_t (., P_i^{(n-1)}, P_i^{(n-1)}) \\ \qquad = \sum_{\ell \in [P_i^{(n-1)}]} \mu_t^{(n)}(X_\ell) \text{ d. } (h_i(P_i^{(n-1)}), x_\ell). \\ a_i^{(n)} \text{ est l'élément de } B \text{ qui minimise } R_2 (., i, P^{(n-1)}) = D_s (., P_i^{(n-1)}). \end{array} \right. $$

On déduit $P^{(n)}$ de $A^{(n)}$ à l'aide de $f$ en posant $P^{(n)} = f(A^{(n)})$ ; autrement dit : $P_i^{(n)} = \{ X \in D(X, A_i^{(n)}) \mid D(X, A_i^{(n)}) \}$ avec $D(X, A_i^{(n)}) = \mu_t^{(n)}(X_\ell) \text{ d. } j_i^{(n)}(P_i^{(n-1)}, x_{\ell j_i^{(n)}}) + \mu_s^{(n)}(X_\ell) \text{ d. } a_i^{(n)}$.

### Initialisation :

On voit ainsi que la donnée de $P^{(0)}$ (estimée ou tirée au hasard) permet d'initialiser l'algorithme ; en effet à l'aide de $(i)$ on peut construire $j_i^{(1)}$ et $a_i^{(1)}$, on a donc $A^{(1)}$ d'où $P^{(1)} = f(A^{(1)})$.

Définition de la suite $u_n$ : on pose $u_n = W(v_n)$.
ORGANIGRAMME

<figure><img src="image_2.png" /></figure>
## 7. - Etude de la convergence

Théorème 1 :

Si $h = (h_{j_1}, \dots, h_{j_k})$ est tel que :

$$R_1 (j_\ell, \ell, Q_\ell, P) \ge R_1 (j_\ell, \ell, P_\ell, P) \quad \forall j_\ell \in J_1, Q^\ell \in P$$

$P = (P_1, \dots, P_\ell, \dots, P_k) \in \mathbb{P}_k$, alors la suite $u_n$ décroit en convergeant.

Démonstration :

On a :

$$u_{n-1} = W (A^{(n-1)}, P^{(n-1)}) = \sum_{\ell=1}^{k} \left[ R_1 (j_{\ell}^{(n-1)}, \ell, P_{\ell}^{(n-2)}, P^{(n-1)}) + R_2 (a_{\ell}^{(n-1)}, \ell, P^{(n-1)}) \right]$$

$$\text{Soit } y_n = W (A^{(n)}, P^{(n-1)})$$

$$= \sum_{\ell=1}^{k} \left[ R_1 (j_{\ell}^{(n)}, \ell, P_{\ell}^{(n-1)}, P^{(n-1)}) + R_2 (a_{\ell}^{(n)}, \ell, P^{(n-1)}) \right]$$

D'après l'hypothèse du théorème, on a :

$$R_1 (j_{\ell}^{(n-1)}, \ell, P_{\ell}^{(n-2)}, P^{(n-1)}) \ge R_1 (j_{\ell}^{(n-1)}, \ell, P_{\ell}^{(n-1)}, P^{(n-1)})$$

$$\text{D'où } u_{n-1} \underset{k}{\overset{\sum}{\ge}} \sum_{\ell=1}^{k} \left[ R_1 (j_{\ell}^{(n-1)}, \ell, P_{\ell}^{(n-1)}, P^{(n-1)}) + R_2 (a_{\ell}^{(n-1)}, \ell, P^{(n-1)}) \right] \underset{y_n}{\ge} y_n$$

Par construction même de $j_{\ell}^{(n)}$ et $a_{\ell}^{(n)}$, on obtient la seconde inégalité.
Reste à montrer que $y_n \ge u_n$. Or :

$$
\begin{align*}
y_n &= \sum_{l=1}^{k} \left[ D_t (j_l^{(n)}, P_l^{(n-1)}, P_l^{(n-1)}) + D_s (a_l^{(n)}, P_l^{(n-1)}) \right] \\
&= \sum_{l=1}^{k} \left[ \sum_{i \in P_l^c} (n-1)]^{\mu_t} (X_i^{(n-1)}) d_{j_l} (n) (h_{j_l} (n) (P_l^{(n-1)}), x_{ij_l} (n)) + \right. \\
&\qquad \left. \sum_{i \in P_l^c} (n-1)]^{\mu_s} (X_i^{(n-1)}) d (a_l^{(n)}, X_i^{(n)}) \right]
\end{align*}
$$

$$
(2) \quad y_n = \sum_{l=1}^{k} i \in [P_l^{(n-1)}]^D (X_i, A_l^{(n)}),
$$

D'autre part :

$$
u_n = \sum_{l=1}^{k} \left[ \begin{aligned} & i \in [P_l^{(n)}]^{\mu_t} (X_i^{(n-1)}) d_{j_l} (n) (h_{j_l} (n) (P_l^{(n-1)}), x_{ij_l} (n)) + \\ & i \in [P_l^{(n)}]^{\mu_s} (X_i^{(n-1)}) d (a_l^{(n)}, X_i^{(n)}) \end{aligned} \right]
$$

$$
(3) \quad u_n = \sum_{l=1}^{k} i \in [P_l^{(n)}]^D (X_i, A_l^{(n)}),
$$

Prenons un terme quelconque de la somme (2), soit $D (X_i, A_\ell^{(n)})$
par exemple, comme $P^{(n)}$ et $P^{(n-1)}$ sont des partitions, $X_i$ apparaît
également dans (3) ; soit $D (X_i, A_\ell^{(n)})$ le terme où $X_i$ apparaît
dans (3), par construction même de $P_i^{(n)}$ on a :

$D (X_i, A_\ell^{(n)}) \subset D (X_i, A_\ell^{(n)})$. Comme le même raisonnement peut être
fait $\forall X_i \in E$, on a bien $y_n \ge u_n$.
8. - Cas d'une distance quadratique

8.1. - Expression du critère dans le cas de distances quadratiques

Rappels concernant les distances quadratiques :

On suppose que E est plongé dans $\mathbb{R}^n$.

On note $X_i$ pour $i = 1, ..., \text{card } E$ les éléments de E avec
$$X_i = (x_{i1}, ..., x_{im}).$$

Soit $P = (P_1, ..., P_k)$ une partition de E.

Soit $\mu$ une mesure sur E telle que $\mu(P_i) = \sum_{a \in P_i} \mu(a) \wedge P_i \in E$
et posons : $D(x, P_i) = \sum_{a \in P_i} \mu(a) \wedge (x, a), G(P_i) = \frac{1}{\mu(P_i)} \sum_{a \in P_i} \mu(a) \wedge a,$
$$\text{var } P_i = \frac{1}{\mu(P_i)} \sum_{a \in P_i} \mu(a) \wedge (a, G(P_i))$$

D'après le théorème de Koenig-Huygens, on a :

$$ \begin{array}{l} k \\ (4) \quad \mu(E) \text{ var}(E) = \sum_{i=1}^{k} \mu(P_i) \text{ var } P_i + D(P_1, \dots, P_k) \\ \qquad \text{où } D(P_1, \dots, P_k) = \sum_{i=1}^{k} \mu(P_i) \text{ d}(G(P_i), G(\cup_{j=1}^{k} P_j)) \end{array} $$

De plus on a les propriétés suivantes :

$$ \begin{array}{l} (5) \quad D(x, P_i) = \mu(P_i) \left[ \text{var } P_i + d(x, G(P_i)) \right] \\ \text{et} \\ \qquad D(P_i, P_j) = \frac{\mu(P_i) \mu(P_j)}{\mu(P_i) + \mu(P_j)} \quad \text{d}(G(P_i), G(P_j)) \end{array} $$
Remarque :

$$
\text{Soit } S_j(y) = \sum_{i \in [P_\ell]} \mu_t(x_i) d_j(y, x_{ij})
$$

On montre facilement que si $h_{j\ell}(P_\ell) = \inf_{y \in \mathbb{R}^+} S_j(y)$
alors $R_1(j, \ell, Q_\ell, P) > R_1(j, \ell, P_\ell, P)$. Il en résulte que si les $d_j$
sont des distances quadratiques et si $h_{j\ell}$ est le centre de gravité
de $P_\ell$ pour le paramètre $j_\ell$, alors l'hypothèse du théorème est vérifiée.

Expression générale du critère :

$$
\text{Posons } A = (A_1, \dots, A_k) \text{ avec } A_\ell = (j_\ell, a_\ell, Q_\ell)
$$

$$
\begin{align*}
W (A,P) &= \sum_{\ell=1}^{k} \left[ R_1 (j_{\ell}, \ell, Q_{\ell}, P) + R_2 (a_{\ell}, \ell, P) \right] \\
&= \sum_{\ell=1}^{k} \sum_{i \in P_{\ell}} \left[ \mu_t (x_i) d_{j_{\ell}} (h_{j_{\ell}} (Q_{\ell}), x_{i,j_{\ell}}) + \right. \\
&\qquad \left. \mu_s (x_i) d (a_{\ell}, x_i) \right]
\end{align*}
$$

Nous supposons que $d$ et $d_j$ sont quadratiques $\forall j$. On note
$\text{var}_j$ la variance et $D_j$ la distance entre groupes associées à $d_j$.
$G_j(P_i)$ le centre de gravité de la classe $P_j$ pour le paramètre $j$.

D'après (5) le critère peut s'écrire sous la forme :

$$
(6) \quad W (A,P) = \sum_{\ell=1}^{k} \left[ \begin{aligned} & \mu_t (P_\ell) (\text{var}_{j_\ell} (P_\ell) + d_{j_\ell} (h_{j_\ell} (Q_\ell), G_{j_\ell} (P_\ell))) + \\ & \mu_s (P_\ell) (\text{var}(P_\ell) + d (a_\ell, G(P_\ell))) \end{aligned} \right]
$$
On est amené à supposer ici que $j = (j_1, ..., j_k)$ est tel que
$j_1 = j_2 = ... = j_k$ (autrement dit les $j_i$ expriment tous le même paramètre)
ce qui peut être obtenu en ajoutant cette contrainte au moment du calcul
de $j^{(n)}$ dans l'algorithme sans que cela change les propriétés de convergence.
Si les paramètres de $J_1$ sont suffisamment homogènes, on peut choisir les
d. tous identiques et créer un nouveau paramètre $j$ qui prenne les valeurs
de $j_i$ pour la classe $P_i$. On se place désormais dans l'un ou l'autre cas
et on note $\hat{j}$ ce paramètre.

Une autre expression du critère peut être obtenue en utilisant (4)
En effet, on obtient d'après cette formule :

$$
\begin{gather*}
\sum_{l=1}^{k} \mu_t(P_l) \operatorname{var}_{\hat{j}}(P_l) = \mu_t(E) \operatorname{var}_{\hat{j}} E - D_{\hat{j}}^2(P_1, P_2, \dots, P_k) \quad \text{où} \\
D_{\hat{j}}(P_1, \dots, P_k) = \sum_{l=1}^{k} \mu_t(P_l) d_{\hat{j}}(G_{\hat{j}}(P_l), G_{\hat{j}}(E))
\end{gather*}
$$

En utilisant des formules analogues pour la deuxième partie du
critère, on a :

$$
\begin{equation} \tag{7}
\begin{split}
W (A,P) = \mu_t (E) \operatorname{var}_{\hat{j}} E &+ \mu_s (E) \operatorname{var} E - \sum_{l=1}^{k} \left[ \mu_t (P_l) \operatorname{d}v_{\hat{j}} (G_{\hat{j}}(P_l), G_{\hat{j}}(E)) \right. \\
& \qquad \left. + \mu_s (P_l) \operatorname{d} (G(P_l), G(E)) \right] \\
& + \sum_{l=1}^{k} \left[ \operatorname{d}v_{\hat{j}} (H_{\hat{j}}(Q_l), G_{\hat{j}}(P_l)) + \operatorname{d} (a_{\hat{l}}, G(P_l)) \right]
\end{split}
\end{equation}
$$

8.2. - Variante du centre de gravité

Pour cette variante on considère que $h_j(P_i)$ est le centre de
gravité de $P_i$ et que $B$ est identique à $\mathbb{R}^{\text{card } J_2}$, autrement dit (cf.
démonstration du théorème 1) :
$$
y_n = \sum_{l=1}^{k} i \in [P_l^{(n-1)}] \left[ \mu_t (X_i) d_{\gamma_j} (h_j^n (P_l^{(n-1)}), x_{ij}^\gamma (n)) + \mu_s (X_i) d (a_l^n, X_i) \right]
$$

$$
y_n = \sum_{l=1}^{k} i \in \left[ P_l^{\sum (n-1)} \left[ \mu_t (X_i) d_{\gamma_j} (h_j^n (P_l^{(n-1)}), x_{ij}^\gamma (n) + \mu_s (X_i) d (G(P_l^{(n-1)}), X_i) \right] \right]
$$

Par définition même de "var$_j$" et "var", on obtient :

$$
y_n = \sum_{l=1}^{k} \left[ \mu_t (P_l^{(n-1)}) \operatorname{var}_{\gamma_j} (n) (P_l^{(n-1)}) + \mu_s (P_l^{(n-1)}) \operatorname{var} (P_l^{(n-1)}) \right]
$$

d'où d'après (4) :

$$
y_n = \mu_t (E) \operatorname{var}_{\gamma_j} (n) (E) + \mu_s (E) \operatorname{var} E - \sum_{l=1}^{k} \left[ \mu_t (P_l^{(n-1)}) d_{\gamma_j} (n) (G_j^n (P_l^{(n-1)}), G_j^n (E)) + \mu_s (P_l^{(n-1)}) d (G(P_l^{(n-1)}), G (E)) \right]
$$

Nous avons vu au cours de la démonstration du théorème 1 que
$\forall n$ on a $u_n \le y_n \le u_{n-1}$, comme la suite $u_n$ converge en décroissant
d'après le lemme 1 (choix des $C_j$), la méthode du centre de gravité tend*
à maximiser la quantité suivante :

$$
(8) \quad y_{(j,P)} = \sum_{l=1}^{k} \left[ \mu_t (P_l) d_{\gamma_j} (G_j^n (P_l), G_j^n (E)) + \mu_s (P_l) d (G(P_l), G (E)) \right]
$$

8.3. - Cas de données qualitatives nominales : maximisation du $\chi^2$

Posons $n = \mathrm{card} E$

On a noté $X_i = (x_{i1}, \dots, x_{im})$ les éléments de $E$ ; dans le
cas de données nominales les variables peuvent prendre un nombre fini
de valeurs entières ; autrement dit $x_{ij}^\gamma$ pour $i \in \{1, \dots, n\}$ prend
une valeur entière.

<footnote>*On ne peut pas affirmer que $y_{(j}^\gamma (n), P^{(n)})$ croît à chaque itération du fait que $\mu_t (E) \operatorname{var}_{\gamma_j} (n) (E)$ dépend de $j^\gamma (n)$ (voir 8. 4) .</footnote>
La variable j est caractérisée par le vecteur

$$
Y_j^{\sim} = \begin{pmatrix} x_{1j}^{\sim} \\ \vdots \\ x_{nj}^{\sim} \end{pmatrix}
$$

On peut transformer ce vecteur $Y_j^{\sim}$ en un tableau $n \times m$
(où $m$ est le nombre de modalités de la variable $j$) en remplaçant
chaque $x_{ij}^{\sim}$ par le vecteur $\hat{x}_{ij}$ coordonnées $(0,...,0, 1, 0, ...0)$ qui
ne contient que des 0 sauf pour la coordonnée de rang $x_{ij}^{\sim}$ qui vaut 1.
Notons $(z_{i1}, ..., z_{im}^{\sim})$ un tel vecteur.

Exemple :

$$
Y_j^{\sim} = \begin{pmatrix} x_{1j}^{\sim} \\ x_{2j}^{\sim} \\ x_{3j}^{\sim} \\ x_{4j}^{\sim} \end{pmatrix} = \begin{pmatrix} 3 \\ 1 \\ 2 \\ 3 \end{pmatrix} \qquad Z_j^{\sim} = \begin{pmatrix} z_{11} & z_{12} & z_{13} \\ z_{21} & z_{22} & z_{23} \\ z_{31} & z_{32} & z_{33} \\ z_{41} & z_{42} & z_{44} \end{pmatrix} = \begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}
$$

Considérons la distance quadratique suivante :

$$
d(X_i, X_j) = \sum_{q=1}^{m} \frac{1}{z_{iq}} (z_{iq} - z_{i',q})^2 \quad \text{où } z_{iq} = \sum_{i=1}^{\sum E} z_{iq}
$$
D'autre part à partir d'une partition $P = (P_1, \dots, P_k)$ et pour une variable $Y_j$ fixée, on peut construire le tableau de contingence suivant :

<table><thead><tr><th>P<br>Y<sub>γ</sub><br>j</th><th>P<sub>1</sub></th><th>P<sub>2</sub></th><th>P<sub>k</sub></th><th>E</th></tr></thead><tbody><tr><td>1</td><td>n<sub>11</sub></td><td>n<sub>12</sub></td><td>...</td><td>n<sub>1k</sub></td><td>n<sub>1.</sub></td></tr><tr><td>2</td><td>n<sub>21</sub></td><td>n<sub>22</sub></td><td>...</td><td>n<sub>2k</sub></td><td>n<sub>2.</sub></td></tr><tr><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td></tr><tr><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td></tr><tr><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td></tr><tr><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td></tr><tr><td>m</td><td>n<sub>m1</sub></td><td>n<sub>m2</sub></td><td>...</td><td>n<sub>mk</sub></td><td>n<sub>m.</sub></td></tr><tr><td>somme</td><td>n<sub>.1</sub></td><td>n<sub>.2</sub></td><td></td><td>n<sub>.k</sub></td><td>n<sub>..</sub></td></tr></tbody></table>

Posons $\mu_t(X_i) = \mu_s(X_i) = 1 \forall i$.

Considérons le tableau Z ; d'après les formules données ci-dessus, on a : $G_{\gamma_j}(P_i) = \frac{1}{\text{card } P_i} \sum_{z \in P_i} z = \frac{1}{n_{.i}} (n_{1i}, \dots, n_{mi})$

$G_{\gamma_j}(E) = \frac{1}{n_{..}} (n_1, n_2, \dots, n_m)$ de plus $\frac{1}{z_{.q}} = \frac{1}{n_{.q}}$

$d_{\gamma_j}(G(P_i), G(E)) = \sum_{q=1}^{m} \frac{1}{n_{.q}} \left( \frac{n_{qi}}{n_{.i}} - \frac{n_{q.}}{n_{..}} \right)^2$

Nouvelle expression de y (j,P) :
on a $\ell = \sum_{i=1}^{k} \mu_t(P_\ell) d_{\gamma_j}(G_{\gamma_j}(P_\ell), G_{\gamma_j}(E)) = \ell \sum_{q=1}^{k} \sum_{q'=1}^{m} \frac{n_{.q}}{n_{.q'}} \left( \frac{n_{q.\ell}}{n_{.\ell}} - \frac{n_{q'.\ell}}{n_{..}} \right)^2$

En multipliant cette quantité par $n_{..}$ on obtient exactement un $\chi^2$ de rang $(k-1) \cdot (m-1)$.
Si $J_2$ est réduit à une seule variable nominale ayant m modalités, prenant $d \equiv d_j$ on arrive à un résultat analogue :

$$ \text{k} \sum_{l=1}^{k} \mu_s(P_l) d(G(P_l), G(E)) = \chi^2_{(k-1) (m-1)} $$

Finalement, la méthode tend à découvrir la partition $P = (P_1, \dots, P_k)$ et le paramètre $j$ qui maximisent la somme de deux $\chi^2$ ; le premier d'ordre (k-1) ($\stackrel{\sim}{m}-1$) s'il est suffisamment grand permet de rejeter l'hypothèse d'indépendance entre la partition $P$ et le paramètre $j$ ; le second, d'ordre (k-1) (m-1) s'il est suffisamment grand permet de rejeter l'hypothèse d'indépendance entre le paramètre à expliquer $J_2$ et la partition $P$.

On peut étendre le résultat au cas où $J_2$ contient plusieurs **paramètres** qualitatifs $y_1, y_2, \dots, y_q$ de modalité $m_1, m_2, \dots, m_q$ ; on obtient alors un $\chi^2$ d'ordre (k-1) ($\sum_{l=1}^q m_l - 1$) (voir [11]).

### 8. 4. Le problème du nombre de modalités

Dans ce paragraphe nous conservons les hypothèses de 8. 3. ; nous notons $m_j$ le nombre de modalités du paramètre $j \in J_1 \cup J_2$ et $\chi^2_{j,P}$ le $\chi^2$ à ($m_j - 1$)(k - 1) degré de liberté associé au tableau $j \times P$ où $P \in P_k$ et $j \in J_1 \cup J_2$.

Si le nombre de modalités de chaque paramètre explicatif est le même, on est assuré de la croissance du $\chi^2_{j}(n), P_{j}(n)$ à chaque itération de l'algorithme.

Si le nombre de modalités varie, on n'est plus assuré de la croissance du $\chi^2_{j}(n), P_{j}(n)$ à chaque itération ; en effet : on peut par exemple décomposer l'algorithme en deux étapes :

1) Une fois $P^{(n-1)}$ fixé on cherche $j_{\ell}^{(n)}$ qui minimise $W_1$ (voir organigramme en 6))

2) Une fois $P^{(n-1)}$ et $j_{\ell}^{(n)}$ fixés, on calcule $P^{(n)}$ à l'aide de $h_{j_{\ell}^{(n)}}(P_i^{(n-1)})$ et $a_i^{(n)}$.

La première étape consiste à passer de $(P^{(n-1)}, j_{\ell}^{(n-1)})$ à $(P^{(n-1)}, j_{\ell}^{(n)})$ et la seconde de $(P^{(n-1)}, j_{\ell}^{(n)})$ à $(P^{(n)}, j_{\ell}^{(n)})$.
Au cours de la deuxième étape le $\chi^2$ augmente ; plus précisément le $\chi^2$ associé à $P^{(n)}$ et $j_{\ell}^{(n)}$ est plus grand que celui qui était associé à $P^{(n-1)}$ et $j_{\ell}^{(n)}$. Cela est vrai d'après les équations déduites du théorème de Kcenig-Huygens et de l'équation (4) donnée en 8. 3. :

$$
(5) \quad \left\{
\begin{array}{@{}l@{\quad}l@{}}
\text{var}_{j_1} E = & \displaystyle \sum_{i=1}^{k} \text{card } P_i^{(n)} \text{var}_{j_1} P_i^{(n)} + \frac{1}{n\cdot} \chi^2 (k-1) \binom{m_{j_1-1}}{k-1} \\[2ex]
\text{var}_{j_\ell} E = & \displaystyle \sum_{i=1}^{k} \text{card } P_i^{(n)} \text{var}_{j_\ell} P_i^{(n)} + \frac{1}{n\cdot} \chi^2 (k-1) \binom{m_{j_\ell-1}}{k-1} \\[2ex]
\text{var}_{j_{N_1}} E = & \displaystyle \sum_{i=1}^{k} \text{card } P_i^{(n)} \text{var}_{j_{N_1}} P_i^{(n)} + \frac{1}{n\cdot} \chi^2 (k-1) \binom{m_{j_{N_1}-1}}{k-1}
\end{array}
\right.
\quad \text{(où } j_1, \dots, j_{N_1} \text{ sont les paramètres explicatifs, } N_1 = \text{card } J_1\text{).}
$$

La deuxième étape implique en effet que

$$
\sum_{i=1}^{k} \text{card } P_i^{(n-1)} \text{var}_{j_\ell} P_i^{(n-1)} \ge \sum_{i=1}^{k} \text{card } P_i^{(n)} \text{var}_{j_\ell} P_i^{(n)}
$$

comme $j_{\ell}^{(n)}$ est fixé on a d'après les équations (5) :

$$
\chi^2_{j_{\ell}^{(n)}, p^{(n-1)}} \le \chi^2_{j_{\ell}^{(n)}, p^{(n)}}.
$$

Par contre au cours de la première étape on cherche $j_{\ell}^{*}$ qui minimise

$$
W_1(j_\ell) = \sum_{i=1}^{k} \text{card } P_i^{(n-1)} \text{var}_{j_\ell} P_i^{(n-1)}
$$

on voit d'après les équations (5) que cette étape (passage de $P^{(n-1)}$,
$j^{(n-1)}$) à $(P^{(n-1)}, j^{(n)})$ n'implique rien sur le $\chi^2$associé à $j_\ell^*$ et $P_\ell^{(n)}$.

C'est pourquoi nous disons en 8. 3. simplement que le $\chi^2$ tend
à croître, en supposant que la lère étape a un effet moyen nul. Remarquons
que le $\chi^2$ associé à $J_2$ et $P^{(n)}$ croît assurément à chaque itération.
A partir de ces constatations, en modifiant la première étape de l'algorithme, on peut imaginer différentes expressions du critère qui permettent d'assurer la croissance de $\chi_j^2(n)$, $p(n)$ (ou de certaines fonctions croissantes de $\chi_j^2(n)$, $p(n)$) à chaque itération. Signalons par exemple trois variantes du critère : $V_1, V_2, V_3$.

Le critère tel qu'il est énoncé en 8.3. s'écrit :

$$y_n = W(A^{(n)}, P^{(n-1)}) = \sum_{l=1}^{k} \left[ \mu_t(P_l^{(n-1)}) \text{var}_j(n) (P_l^{(n-1)}) + \mu_s(P_l^{(n-1)}) \text{var}(P_l^{(n-1)}) \right]$$

a) Première variante :

$$V_1(A^{(n)}, P^{(n-1)}) = \sum_{l=1}^{k} \left[ \frac{1}{m_j^{(n)-1}} \mu_t(P_l^{(n-1)}) \text{var}_j(n) P_l^{(n-1)} + \frac{1}{m_{J_2}^{-1}} \mu_s(P_l^{(n-1)}) \text{var}(P_l^{(n-1)}) \right]$$

Si la première étape de l'algorithme s'écrit "chercher j qui minimise $\frac{1}{m_j^{-1}} \text{var}_j P_l^{(n-1)}$ pour $j \in J_1$

L'algorithme fait croître à chaque itération $\frac{1}{m_j^{(n)-1}} \chi_j^2(n)$, $p(n)$ et $\frac{1}{m_{J_2}^{-1}} \chi_{J_2}^2$, $p(n)$ d'après les équations (5) et du fait que $\text{var}_j E = m_l^{-1}$ on utilise la distance du $\chi^2$)

b) Deuxième variante :

$$V_2(j,p) = \sum_{l=1}^{k} \mu_t(P_l) d_j(G(P_l), G_j(E)) + \mu_s(P_l) d(G(P_l), G(E)).$$

Au cours de la seconde étape de l'algorithme, on sait que $V_2$ croît. Dans cette variante la première étape consiste à chercher $j^{(n)}$ qui maximise $\chi_j^2(p^{(n-1)})$ parmi $j \in J_1$. Dans cette variante le $\chi_j^2(n)$, $p(n)$ et le $\chi_{J_2}^2$, $p(n)$ croissent à chaque itération de l'algorithme.
c) La troisième variante

Elle s'inspire de l'idée de Dehedin (13) qui consiste à utiliser
une fonction croissante du $\chi^2$ indépendante du degré de liberté et donc,
dans notre cas du nombre de modalités et de classes.

La formule de Wilson-Hilferty par exemple :

$$
Y(j,p) = \sqrt{\frac{9v_j}{2}} \cdot \left( \sqrt[3]{\frac{\chi^2_{j,p}}{v_j}} + \frac{2}{9v_j} - 1 \right) \sim \eta (0,1)
$$

où $v_j = (m_j - 1) (k - 1)$ est le degré de liberté.

Le critère s'écrit :

$$
V_3 (j,p) = Y(j,p) + Y(J_2,p)
$$

La première étape de l'algorithme consiste à chercher $j^*$ qui
maximise $V_3(j, P^{(n-1)})$ parmi $j \in J_1$.

La seconde étape donne $\chi^2_{j,p(n-1)} \ge \chi^2_{j,p(n)}$ et $\chi^2_{J_2,p(n-1)} \ge \chi^2_{J_2,p(n)}$
On est donc assuré de la croissance du critère $V_3 (j,P)$

Remarque :

Dans le cas "mélangé" où il n'est pas imposé à chaque classe de
la partition P(n) d'être associée à la même variable (cas j) on peut
définir des variantes analogues. Il faut remarquer que (5) contient N x k
égalités.

Les deux étapes de l'algorithme et ses variantes s'écrivent
comme précédemment en remplaçant partout j par $j^_v$.
## 9. - Sur une famille de problèmes de classification avec contraintes multiples

Rappelons que J l'ensemble des paramètres est la réunion de $J_1$ et $J_2$. Notons $(E_1, E_2)$ une partition de E et soit $J^l$ un paquet de paramètres contenus dans $J_1$. On note $I = (J^1, J^2, ..., J^n)$. On peut alors définir le critère :

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

$$W(P, I) = \sum_{\ell=1}^{n} \sum_{i=1}^{k} \alpha_{1} F(P_{i}, J_{1}^{\ell}) + \alpha_{2} F(J_{1}^{\ell}, P_{1}) + \sum_{i=1}^{k} F(P_{i}, J_{2}) + \alpha_{4} \sum_{\ell=1}^{n} F(J_{2}^{\ell}, E_{2})$$

où $P = (P_1, ..., P_k)$ est une partition de $E_1$. $W(P, I)$ est une application de $P(E) \times P^n(J_1) \rightarrow \mathbb{R}^+$

Posant $F(x,y) = \text{var}_x y$ on a :

$F(P_i, J^l) = \text{var}_{P_i} J^l, F(J^l, P_i) = \text{var}_{J^l P_i} P_i$ (où $\text{var}_x y$ est la variance de y avec pour paramètres, les éléments de x) et $\alpha_2 = \alpha_3 = 0$, l'algorithme que nous avons étudié ici, permet d'améliorer le critère :

$$W(P, J^l) = \sum_{i=1}^{k} \alpha_1 F(P_i, J^l) + \alpha_3 \sum_{i=1}^{k} F(P_i, J_2) \text{ avec } P \text{ et } P_k \\ J^l \text{ et } J_1 \text{ et } \text{card } J^l \text{ fixé.}$$

G. GOVAERT [14] a proposé un algorithme dans le cas où les $J^l$ forment une partition de J permettant d'améliorer le critère $W(P, I) = \sum_{i} \sum_{\ell} (\alpha_1 F(P_i, J^l) + \alpha_2 F(J^l, P_i))$; dans ce cas il s'agit de trouver la partition des individus et la *partition* des paramètres telles que le tableau de contingence des classes associées à ces partitions tendent à maximiser le $\chi^2$ de contingence à (n-1) (k-1) degrés de liberté associé à ce tableau.

Si on se pose le même problème avec $\alpha_3 \neq 0$ et $\alpha_4 \neq 0$, il s'agit de trouver les partitions P et I donnant la meilleurs contingence sous la contrainte $E_2$ et $J_2$.

Dans tous les cas la représentation simultanée des $F(P_i, J^l)$ pour tout $i$ et $l$ peut être intéressante notamment dans le cas de grands tableaux.

Signalons enfin que ce type de tableau peut-être généralisé à n variables croisées, chacune d'elle étant sous contrainte. (cf. J.D. CAROLL et al [12]).
10. - Codage sous contrainte

Dans le cas où les paramètres de $J_1$ sont tous des variables ordinales (qualitatives ou quantitatives) la partition obtenue à la convergence de l'algorithme, induit un codage du paramètre sélectionné qui a tenu compte de la contrainte imposée par les paramètres de $J_2$. Ainsi, si tous les paramètres sont continus il est inutile de faire un codage préalable et on a une méthode de codage adaptatif des paramètres sélectionnés.

Dans le cas où l'on voudrait coder un paramètre fixé $j$ sous la contrainte $J_2$. Le critère à optimiser s'écrit alors

$$W (j,P) = \sum_{i=1}^{k} (\mathrm{var}_j P_i + \mathrm{var}_{J_2} P_i)$$

On peut obtenir un bon optimum local d'un tel critère en utilisant la méthode des nuées dynamiques sur la population caractérisée par les paramètres $j \in J_2$.

Dans le cas où $j$ est une variable ordonnée Y. LECHEVALLIER* [15] donne un algorithme permettant de minimiser de façon optimale

$$W (P) = \sum_{i=1}^{k} \mathrm{Card} P_i \cdot \mathrm{var}_{J_2} P_i \quad \text{avec la contrainte : "pour tout i, deux individus quelconques de } P_i \text{ font partie du même intervalle contigu de j".}$$

<footnote>*Rapport Laboria à paraître</footnote>
11 - Modèles linéaires locaux

1. - Le problème *:

Les données se présentent sous la forme de m lignes notées
z∈E et n+1 colonnes notées x¹, x², ..., xP, y.

Le ième objet de E est noté

$$
z_i = (x_i^1, x_i^2, \dots, x_i^P, y_i)
$$

L'espace des noyaux est L = ℝ<sup>P</sup>. On note L<sub>k</sub> = (L) <sup>k</sup> l'espace des
k noyaux : B ∈ L<sub>k</sub> ⇒ B = (B<sub>1</sub>, ..., B<sub>k</sub>) avec B<sub>j</sub> ∈ ℝ<sup>n</sup>.

On note $\mathbb{P}_k$ l'espace des k partitions :

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

On note :

$z_i^j$ le ième élément de la classe $P_j$ ; les coordonnées correspondantes sont $z_i^j = (x_i^{1,j}, \dots, x_i^{p,j}, y_i^{j})$.

$$
\text{Soient } n_j = \text{card } P_j, \quad Z^j = \begin{pmatrix} z_1^j \\ \vdots \\ z_{n_j}^j \end{pmatrix}, \quad X^{\ell,j} = \begin{pmatrix} x_1^{\ell,j} \\ \vdots \\ x_{n_j}^{\ell,j} \end{pmatrix}
$$

$X_i^j = (x_i^{1,j}, x_i^{2,j}, \dots, x_i^{p,j})$ représente les p premières coordonnées du ième élément de $P_j$.

$$
X^j = \begin{pmatrix} x_1^{1,j} & \cdots & x_1^{p,j} \\ x_2^{1,j} & \cdots & x_2^{p,j} \\ \vdots & & \vdots \\ x_{n_j}^{1,j} & \cdots & x_{n_j}^{p,j} \end{pmatrix} \qquad B_j = \begin{pmatrix} b_1^j \\ \vdots \\ b_{p}^j \end{pmatrix} \qquad y^j = \begin{pmatrix} y_1^j \\ \vdots \\ y_{n_j}^j \end{pmatrix}
$$

*On trouvera dans [8] une bibliographie récente concernant ce problème.
2. - Le critère à optimiser :

$$
W : \mathcal{L}_k \times \mathcal{P}_k \to \mathbb{R}^+ \quad W(L,P) = \sum_{j=1}^{k} \| y^j - x^j B_j \|^2 = \sum_{j=1}^{k} \sum_{i=1}^{n_j} (y_i^j - x_i^j B_j)^2
$$

Il s'agit de trouver $(L^*, P^*)$ tels que :

$$
W(L^*, P^*) = \begin{array}{l} \text{Min} \\ (L,P) \in \mathcal{L}_k \times \mathcal{P}_k \end{array} \qquad W(L,P)
$$

3. - La méthode :

3.1. - La fonction d'identification f :

$$
f \text{ est une application } \mathcal{L}_k \to \mathcal{P}_k : f(B) = P \text{ où}
$$

$$
P_i = \{ z \in E / d(z, B_i) \le d(z, B_j) \}
$$

$$
où d : E \times \mathbb{R}^n \to \mathbb{R}^+
$$

$$
d(z_i, B_i) = (y_i - x_i B_i)^2 \quad \text{où} \quad x_i = (x_i^1, \dots, x_i^p) \text{ et } z = (x_i, y_i)
$$

3.2. - La fonction de représentation g :

$$
g \text{ est une application } \mathcal{P}_k \to \mathcal{L}_k : g(P) = (B_1, B_2, \dots, B_k)
$$

$$
où B_j \text{ minimise } R(B,j,P) = \sum_{z \in P_j} d(z, B) ((x^j)^T x^j)^{-1}
$$

$$
R(B_j, j, P) = \inf \{ R (B, j, P) \mid B \in \mathbb{R}^n \} \quad B_j = ((x^j)^T x^j)^{-1} (x^j)^T y^j \\
(\text{équations normales, on suppose donc que } X \text{ est injective}).
$$

Construction des suites $v_n$ et $u_n$.

La suite $v_n$ est définie de la manière suivante : $v_0 = (P^{(o)}, B^{(o)})$
où $P^{(o)}$ est estimé ou pris au hasard. $v_{n+1}$ est déduit de $v_n = (P^{(n)}, B^{(n)})$
comme suit : $B^{(n+1)} = g(P^{(n)})$ et $P^{(n+1)} = f(B^{(n+1)})$.

La suite $u_n$ est définie par $u_n = W(v_n)$

Théorème : la suite $u_n$ décroît en convergeant.
Démonstration :

Il suffit de montrer successivement que $(B^{n+1}, P^n) = w_n$
vérifie $W(v_n) > W(w_n)$ puis que $W(w_n) > W(v_{n+1})$.

On sait que $B^{(n+1)} = g(P^{(n)})$ est défini par les équations normales
d'où $\sum_{i=1}^{n_j} (y_i^j - x_i^j B_j^{(n)}) > \sum_{i=1}^{n_j} (y_i^j - x_i^j B_j^{(n+1)})$, (les $y_i^j$ et $x_i^j$ étant
fixés $B_j^{(n+1)}$ est d'ailleurs la meilleure solution possible) et cela pour
toutes les classes. Reste à montrer que $W(w_n) > W(v_{n+1})$. Prenons un
terme quelconque dans le développement de $W(w_n)$ par exemple
$(y_i^j - x_i^j B_j^{(n+1)})$ ; deux cas peuvent se produire :

a) $d(z_i^j, B_j^{(n+1)}) < d(z_i^j, B_m^{(n+1)}) \forall m$, $z_i^j$ ne change pas de classe.

b) m : $d(z_i^j, B_j^{(n+1)}) > d(z_i^j, B_m^{(n+1)})$ alors par construction
de $v_{n+1}$, $z_i^j$ appartient à la classe m et le terme $(y_i^j - x_i^j B_j^{(n+1)})$ de
$W(w_n)$ est remplacée par le terme $(y_i^m - x_i^m B_m^{(n+1)})$ de $W(v_n)$ ; comme
$(y_i^m - x_i^m B_m^{(n+1)}) < (y_i^j - x_i^j B_j^{(n+1)})$ et que l'on peut faire le même
raisonnement pour tous les termes de $W(w_n)$ on a le résultat.

3.3. - La sélection de paramètres :

Il faut adapter au modèle linéaire local les méthodes classiques
de sélections de paramètres dans le cadre du modèle linéaire :
examen de toutes les regressions possibles puis choix de la meilleure ;
eliminations descendantes: on part de la régression complète et on enlève
la variable qui provoque la plus faible augmentation de l'erreur (ou la
plus faible diminution du rapport F) et on recommence avec les n-1
variables restantes. On peut aussi utiliser l'introduction ascendante
des paramètres (cf. [9] et [10]).

Des problèmes de convergence qui apparaissent dans le cadre du modèle
linéaire local nous conduiraient à de trop grands développements dans
le cadre de cet article.
## 12. - Analyse factorielle discriminante typologique

### 12.1. - Le problème

Etant donné une population de n individus caractérisés par p paramètres, il s'agit de chercher simultanément k classes d'individus et le plan (ou l'hyperplan) factoriel le plus discriminant de ces classes.

L'analyse factorielle discriminante typologique sous contrainte s'énonce de la même manière, avec la condition supplémentaire que les classes obtenues devront être de variance minimum sur $J_2$.

### 12.2. - Formulation mathématique

$$ \text{Soit } \mathcal{L}_k = (\mathbb{R}^q)^k \times \mathbb{R}^p \text{ où } p = \text{card } J_1, q = p + \text{card } J_2 $$

$$ \text{Soit W l'application } \mathbb{P}_k \times \mathcal{L}_k \to \mathbb{R}^+ $$

$$ W(P,L) = \sum_{\ell=1}^{k} \left[ \sum_{i \in \mathbb{P}_{\ell}} \left[ \sum_{j \in J_1} b_j (x_{ij} - a_{\ell,j}) \right]^2 + \alpha \operatorname{var}_{J_2} P_{\ell} \right] $$

où $P = (P_1, ..., P_k)$ et $L = (a,b)$ avec $a = (a_1, ..., a_k) \in (\mathbb{R}^q)^k$ et $b = (b_1, ..., b_p) \in \mathbb{R}^p$ joue le rôle du premier axe de l'analyse factorielle discriminante typologique.

$\operatorname{var}_{J_2} P_{\ell} = \sum_{i \in \mathbb{P}_{\ell}} \sum_{j \in J_2} c_j (x_{ij} - a_{\ell,j})^2$, $a_{\ell,j}$ est le centre de gravité de la classe $\mathbb{P}_{\ell}$ pour le paramètre $j$ ; $x_{ij}$ est la coordonnée $j$ de l'élément $i$. $c = (c_1, ..., c_{q-p})$ est une pondération des paramètres de $J_2$ à définir par l'utilisateur.

La formulation mathématique du problème est la suivante :

Il s'agit de trouver $P$ et $b$ qui minimisent $W(P,L)$ dans $\mathbb{P}_k \times \mathcal{L}_k$.
Minimiser W (P,L) quand P est fixé et α = 0 revient à minimiser

$$
\sum_{\ell=1}^{k} \sum_{i \in [P_{\ell}]} \left[ \sum_{j \in J_1} b_j (x_{ij} - a_{\ell,j}) \right]^2 . \text{ Soit } \hat{a}_{\ell} = (a_{\ell 1}, \dots, a_{\ell p}) \in \mathbb{R}^p.
$$

$$
\sum_{\ell=1}^{k} \sum_{i \in [P_{\ell}]} b'_{i} (x_{i} - \hat{a}_{\ell})' (x_{i} - \hat{a}_{\ell}) b = b' H b = H (b, b)
$$

où H est la matrice d'inertie intra-classes.

On évite la solution triviale b = 0 en introduisant la contrainte

$$
\sum_{\ell=1}^{k} m_{\ell} \left(\sum_{j=1}^{p} b_j a_{\ell,j}\right)^2 = 1 \text{ ou encore } B(b,b) = 1
$$

$$
\text{avec } B = \hat{a} D_m \hat{a}' \text{ où } \hat{a} = (\hat{a}_1, \dots, \hat{a}_k) \text{ et } D_m = \begin{pmatrix} m_1 & & 0 \\ & \ddots & \\ 0 & & m_k \end{pmatrix}
$$

avec $m_j = \text{card } P_j$ (pour simplifier).

Le problème se ramène donc à minimiser :

$$
H (b,b) \text{ sous la contrainte } B(b,b) = 1
$$

On sait que la solution est donnée par le vecteur propre de plus grande
valeur propre de $V^{-1}B$ où V est la matrice de variance covariance du
nuage E.

La méthode :

On définit deux applications g et f :

1) $g : P_k \rightarrow \mathbb{L}_k$ $L = g(P)$ est défini par :

$L = (a_1, \dots, a_k, b)$ où $a_i$ est le centre de gravité de la classe $P_i$ et

b est le vecteur propre de plus grande valeur propre de $V^{-1}B$ avec

$$
B = \hat{a} D_m \hat{a}' \text{ et } \hat{a} = (\hat{a}_1, \dots, \hat{a}_k) \in [\mathbb{R}^p]^k.
$$
2) $f : L_k \to P_k$ est défini par $f(L) = P=(P_1, \dots, P_k)$ avec
$P_\ell = \{X_i \in E/d_b(X_i, a_\ell) < d_b(X_i, a_\ell) \forall j \neq \ell\}$ en cas d'égalité, on
affecte $X_i$ à la classe de plus petit indice.

$d_b$ est l'application $E \times \mathbb{R}^p \to \mathbb{R}^+$ :

$$
d_b (X_i, a_\ell) = \sum_{j \in J_1} \left[ b_j (x_{ij} - a_{\ell,j}) \right]^2 + \alpha \sum_{j \in J_2} c_j (x_{ij} - a_{\ell,j})^2
$$

Définition des suites $u_n$ et $v_n$ :

$u_n = W(v_n)$ où $v_n$ est défini comme suit :

$v_o = (P^{(o)}, L^{(o)})$ où $L^{(o)} = (a^{(o)}, b^{(o)})$ avec $a^{(o)} \in \mathbb{R}^p$ et $b^{(o)} \in \mathbb{R}^p$

$v_n = (P^{(n)}, L^{(n)}) \quad \text{où} \quad P^{(n)} = (P_1, \dots, P_k) \text{ et } L^{(n)} = (a^{(n)}, b^{(n)})$

$v_{n+1} = (P^{(n+1)}, L^{(n+1)})$ avec $L^{(n+1)} = (a^{(n+1)}, b^{(n+1)}) = g(P^{(n)})$

et $P^{(n+1)} = f(L^{(n+1)})$.

Proposition : sous la contrainte $B (b,b) = 1$ la suite $u_n$ converge en décroissant.

Démonstration
---

Montrons d'abord que $W(P^{(n)}, L^{(n)}) > W(P^{(n)}, L^{(n+1)})$.

En effet, on a d'abord $W(P^{(n)}, (a^{(n)}, b^{(n)})) > W(P^{(n)}, (a^{(n+1)}, b^{(n)}))$
puisque $a_\ell^{(n+1)}$ est le centre de gravité de la classe $P^{(n)}$ (par définition
de l'application $g$).
Ce qui n'est pas nécessairement le cas de $a_\ell^{(n)}$.

On a de plus :

$W(P^{(n)}, (a^{(n+1)}, b^{(n)})) \ge W(P^{(n)}, (a^{(n+1)}, b^{(n+1)}))$ car sous la contrainte
$B(b,b) = 1$, on sait que $H(b^{(n+1)}, b^{(n+1)}) \le H(b,b) \le b \in \mathbb{R}^p$ par construc-
tion de g.

On a donc bien $W(P^{(n)}, L^{(n)}) \ge W(P^{(n)}, L^{(n+1)})$, reste à montrer que

$W(P^{(n)}, L^{(n+1)}) \ge W(P^{(n+1)}, L^{(n+1)})$

$$
\text{Or } W(P^{(n)}, L^{(n+1)}) = \sum_{\ell=1}^{k} \sum_{X_i \in P^{(n)}_{\ell}} d_{B^{(n+1)}}^{(n+1)} (X_i, a_{\ell}^{(n+1)}) \quad (1)
$$

$$
W(P^{(n+1)}, L^{(n+1)}) = \sum_{\ell=1}^{k} \sum_{X_i \in P_{\ell}^{(n+1)}} d_{B^{(n+1)}}^{(n+1)} (X_i, a_{\ell}^{(n+1)}) \quad (2)
$$

Prenons un individu X quelconque par construction même de P<sup>(n+1)</sup> et
supposons qu'il apparaisse dans le terme d<sub>b</sub><sup>(n+1)</sup>(X, a<sub>j</sub><sup>(n+1)</sup>) dans (1) et
d<sub>b</sub><sup>(n+1)</sup>(X, a<sub>l</sub><sup>(n+1)</sup>), dans (2), par construction même de P<sup>(n+1)</sup>, on a
nécessairement d<sub>b</sub><sup>(n+1)</sup>(X, a<sub>j</sub><sup>(n+1)</sup>) ≥ d<sub>b</sub><sup>(n+1)</sup>(X, a<sub>l</sub><sup>(n+1)</sup>) ; comme on peut faire le
même raisonnement pour tous les individus de la population on a le résultat.
## CONCLUSION

En ce qui concerne la poursuite et l'extension des résultats obtenus, de nombreuses voies de recherches sont ouvertes : en segmentation, l'étude de différents types de codages (seul le cas nominal ayant été approfondi), des heuristiques pour la sélection de combinaisons de paramètres, le choix de différents types de distances; en regression typologique, l'étude des singularités, l'introduction de pseudo-inverses, de la ridge régression ; en discrimination typologique, l'introduction des méthodes pas-à-pas, la recherche des k-hyperplans les plus discriminants, l'utilisation d'autres règles d'affectation.

La problématique que nous avons soulevée est indépendante des algorithmes qui ont été proposés, il faudrait confronter différents types d'algorithmes et étudier des techniques d'amélioration des optimums locaux.

En terme de reconnaissance des formes le travail que nous avons présenté admet comme thème de fond le problème de perception suivant : comment sélectionner les paramètres qui permettent de représenter et reconnaître un ensemble d'objets dans un contexte donné ?

Autrement dit :

<table><thead><tr><td>Reconnaître quoi ?<br>Représenter comment ?</td><td>Pour expliquer quoi ?</td><td>Avec quoi ?</td></tr></thead><tbody><tr><td>P ∈ P<sub>k</sub>, g(P<sub>k</sub>)</td><td>J<sub>2</sub></td><td>f(j), j ⊂ J<sub>1</sub></td></tr></tbody></table>
BIBLIOGRAPHIE

[1] A. BACCINI (1975). "Aspect synthétique de la segmentation et traitement de variables qualitatives à modalités ordonnées" Thèse Université Paul Sabatier de Toulouse.

[2] J.N. MORGAN, R.C. MESSENGER (1974). "A sequential analysis program for the analysis of nominal scale dependent variable survey research center". Institute for Social research. The University of Michigan, USA.

[3] M. TENENHAUS, J.M. BOUROCHE (1970). "Quelques méthodes de segmentation". RAIRO, vol V-2.

[4] J.M. ROMEDER (1969). "Méthodes de discrimination" Thèse de 3° Cycle - Faculté des Sciences de Paris - ISUP

[5] G. SEBESTYEN (1962). "Decision - Making Process in Pattern Recognition". New-York : Mac Millan C°.

[6] L. KANAL (1974). "Patterns in Pattern Recognition : 1968-1974" I.E.E.E. on Inf. th. vol II-20, N° 6.

[7] B.V. DASARATHY (1974). "Feature selection and the concept immediate neighborhood in the context of clustering techniques" Proc. I.E.E.E. (Lett.) pp. 529-530 Avril 1974.

[8] SCOTT B. GUTHERY (1974). "Partition Regression" J.A.S.A. Vol 69, N° 348

[9] EFROYMSON M. (1962). "Multiple regression analysis" Ralston-Wilf Math. meth. for dig. comp. Wiley. New-York.
[10] DRAPER N. SMITH H. (1966) "Applied Regression Analysis" Wiley. New York

[11] DIDAY E. (1974) "Classification séquentielle pour grands tableaux" RAIRO (9e année mars 1975, B-1, p 29 à 61)

[12] CAROLL J.D. ; GREEN P.E. ; CARMONE (1976) "CANDELING a new method for multidimensional analysis with constrained solutions". INT. CONG. of Psychology in Paris, France.

[13] DEHEDIN J. (1975) "Discrimination sur variables qualitatives" Thèse de 3e cycle. Université Paris VI.

[14] GOVAERT G. (1976) "Un algorithme de classification d'un tableau de contingence" Congrès Européen de Statistique. Grenoble.

[15] LECHEVALLIER Y. (1976) "Découpage optimal au sens du Khi 2 de contingence, d'ensembles totalement ordonnés". Congrès Européen de Statistiques. Grenoble.