RIA
laboria

laboratoire de recherche
en informatique
et automatique

Automatic sequential
classification
of large tables

E.Diday

Institut de Recherche
d'Informatique
et d'Automatique

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

Rapport de Recherche n° 87

Novembre 1974
AUTOMATIC SEQUENTIAL CLASSIFICATION
OF LARGE TABLES

E. DIDAY

Résumé

On donne une méthode de classification automatique adaptée au traitement
des grands tableaux grâce à l'économie de place en mémoire centrale. On
montre que l'espace des solutions obtenues est identique à celui que l'on
obtient avec la méthode des nuées dynamiques. On donne quelques variantes
et on explicite les critères que ces variantes tendent à optimiser.
Dans le cas d'un tableau de modalité, on propose une formulation de la
distance du $\chi^2$ adaptée à la méthode. On donne un organigramme général
du programme.

Abstract

A method for the automatic classification adapted to the processing of
large table is given ; this has been made possible by the economy of
memory space. It is shown that one gets the same set of solutions
either by the method described here or by the dynamic clusters method.
Some variants are given along with the criteria they optimize. In the
case of a table of qualitative variables, a formulation of the distance
of the $\chi^2$ adapted to the method is proposed. A general organigram of the
program is given.
BIBLIOGRAPHY

1. Introduction

2. Notations

3. The SDCM algorithm

4. Relations between the DCM and SDCM

4.1. Reminders concerning the DCM

4.2. Comparison between the solutions obtained with DCM and SDCM

4.3. A condition sufficient to have R square in the sense of the DCM and the SDCM

4.4. Comparative advantages of the DCM and the SDCM

5. Study of some variants in the sequential case

6. Expression of the criterion in the case where d is quadratic

7. Comparative advantage of different variants

8. Examples of similarity indexes

9. The program
# 1. Introduction

In any field where it is possible to define a set E in which the elements can be connected by a measure of similarity it is possible to find clusters; in other words, to try to detect classes of objects such that two objects of the same class are closer to each other than to objects belonging to other classes in the sense of the measure of similarity.

Classifications may be conceived which are more or less suitable according to a given criterion.

In this paper, we will give methods which tend to optimize such criteria and which are also adapted to the processing of large tables requiring more than 100 K memory words.

Many authors have taken interest in the hierarchical classification (cf. (2), (3), (6), (12), (13), (15), (18)). It is a method permitting to give partitions of E which are encased in one another, giving a hierarchy. This type of method runs into two difficulties :

a) The pruning of the tree into classes which allows to define types.

b) The necessity of storing a table with $\frac{N(N-1)}{2}$ arrays corresponding to the distances taken two by two of the elements of E.

The minimum spanning tree (cf. (11) and (20)) permits an attractive approach to the problem in giving a tree whose vertices are the elements of E and where the length of the edges represents the degree of similarity between the connected elements. This method allows to build a tree whose sum of the edges length is minimum. The visual representation of such a tree can be very enriching even though subjected to chain effect. To define types in the case of sets of large size, it is necessary to use cutting up techniques depending on thresholds determined before hand.

One may conceive many methods which give solely a "good" partition of E. In our opinion, the most interesting ones are those which reduce the number of arbitrary parameters as much as possible, and which at the same time express the criterion being optimized; the methods described in this paper require the knowledge of the number of classes of the searched partition, in other words, the degree of refinement desired by the user; furthermore, a simple criterion allows to grasp the meaning of the partition which has been obtained. The so called
"Dynamic Clusters Methods" are based on the choice of three functions :

- h is a function permitting to define the set E and a method of measure applied to this set (coding, similarity measurements, a priori types, etc...).

- g a function of representation of any class of E ;

- f a function identifying any elements of E with the help of this representation.

The Dynamic Clusters Method (noted DCM - cf. (7) and (9)) consists in storing E in the central memory and in using alternativaly f and g until an equilibrium position is reached (corresponding to a local optimum of the criterion). The Sequentialized Dynamic Clusters Method, (SD CM) to which this paper is devoted, is based on the same principles as the DCM, but the storing in central unit of the data table associated to E is not necessary. This is of great advantage for large tables, there is not an important loss of time compared to the DCM.

The DCM and SDCM may be considered as a generalisation of a set of procedures called by some authors : "Iteration, relocation procedure" (Cormack (1971), Wishart (1971)), k-means by others (Mc Queen (1967), Watanabe (1972)). These procedures may be roughly described as follows.

One starts with k points choosen or estimated in a population, these k
points will be the centers, all the points are assigned to the closest
center according to one of the following two techniques :

a) The k centers may change when <u>All</u> the points are classified (Forgey)
(1965), Hall and Ball (1965), Jancey (1966)). The mean of each group is
computed and gives a new point which is considered as the new center.

b) The k centers may move after the assignment of <u>each</u> point (Thorndike (1953), Mc Queen (1967), Beale (1969), Wishart (1971)). When a point is added to a group, the <u>mean</u> of the group is adjusted by taking in consideration this new point. This mean defines the new center.

Finally, the whole population is classified iteratively and several ti-
mes according to techniques a) - Beale (1969), Wishart (1971) - and
techniques b).

The procedure is ended when a number of iterations (predetermined) has
occured, or when the process either comes to stability or oscillates.
Let us point out that classical programs like `ISODATA` call out arbitrary thresholds to split and union the classes during the algorithm flow (cf. 16).

One may admit that a particular case of the DCM is the case a) when the function of representation g gives the centers of gravity.

In the SDCM one may use g as soon as all the individuals of a cluster are assigned. Even when g gives the centers of gravity, this method stays more general than b) and should save an appreciable amount of time by reducing the number of determinations of the centers.

The most important contributions of this paper are:

1) The introduction of the SDCM

2) The convergence properties of different variants with the associated criteria (meaningful to the user) that the variants tend to optimize.

3) The demonstration of the equivalence of the set of solutions obtained with the DCM and the SDCM (therefore between a) and b)).

4) The description of the SDCM program which has already given a partition in 10 classes of a population of 5000 individuals characterized by 30 parameters in 7 min. on IBM 360-70. This partition could not have been achieved by the DCM because of the storage space required or else because of the number of exchanges that occur if the data are stored on auxillary storage units. However this partition corresponds well to the solution the DCM could have given.

## 2. Notations

E is the set of the objects to be classified.

$L_k = \{ L = (A_1, \dots, A_k) / A_i \subset B \}$, B is a space depending on the variants.

$P(E)$ is the set of the subsets of E.

$P_k$ is the set of the E partition in k classes.

P, Q ∈ $P_k$ will be noted $P = (P_1, \dots, P_k)$ and $Q = (Q_1, \dots, Q_k)$.

$D: E \times P(B) \rightarrow R^+$ is a measure of ressemblance between a point of E and a subset of B.

$F: P_k \times P(E) \times L_k \rightarrow P_k$ is given by:

$F(Q,H,L) = P$ where P is defined by the sequence $\{\Pi_n\}$ of $P_k$ as follows:
let us note $\Pi_l = (\Pi_{l1}, \dots, \Pi_{lk})$ and $H = \{y_1, \dots, y_m\}$.

let $\Pi_0 = Q$, the sequence $\Pi_n$ is defined by recurrence from $\Pi_0$;
once $\Pi_{l-1}$ is given, one builds $\Pi_l$ as follows : (let us suppose
$y_l \in \Pi_{l-1, j}$).

a) $\ni i : D(y_l, A_i) \le D(y_l, A_j)$ with $j < i$ in case of equality ; one has
then $\Pi_l = \Pi_{l-1, i}$

b) $\exists i : D(y_l, A_i) \le D(y_l, A_j)$ with $j > i$ in case of equality ; one has
then $\Pi_{l,i} = \Pi_{l-1,i} \cup \{y_l\}$, $\Pi_{lj} = \Pi_{l-1,j} - \{y_l\}$ and then $\Pi_{ln} = \Pi_{l-1,n}$
$\forall n$ such that $n \ne i, n \ne j$ and $n \in \{1,2,\dots,k\}$. Finally let us give $P = \Pi_m$
$R$ is a function which is defined upon $B \times \mathbb{J}^k \times P_k$ and has values in
$\mathbb{R}^+$ (where $\mathbb{J}^k = \{1,2,\dots,k\}$).

. Given k integers $n_1, \dots, n_k$

$g^s : P_k \to \mathbb{L}_k$ is such that $g^s(P) = L = (A_1, \dots, A_k)$ where $A_i = \{ \text{the } n_i \text{ elements of } B \text{ that minimize } R(x, i, P) \}$.

. W : $V_k = L_k \times P_k \to \mathbb{R}^+$ is the criterion to be optimized, it can be
written $W(v) = \sum_{i \in \mathbb{J}^k} \sum_{x \in A_i} R(x, i, P)$ where $v = (L, P)$

$S' : S'(L,P) = W(v) \quad \forall v = (L,P)$

3. The Basic algorithm of the SDCM (1)

One starts from $P^{(0)}$ and one deduces $L^{(1)} = g^s(P^{(0)})$
and $P^{(1)} = F(P^{(0)}, H^{(0)}, L^{(1)})$.

Let us note $H^{(0)}, H^{(1)}, \dots, H^{(N)}$ a partition of $E$ and let us also
define the sequence $\{H^{(n)}\}$ in taking $H^{(n)} = H^{(r)}$ where $r$ is the re-
mainder of the division of $N + 1$ into $n$.

The SDCM is defined by the following sequence $v_n$ :

one has $v_1 = (L^{(1)}, P^{(1)})$ and $v_{n+1} = (L^{(n+1)}, P^{(n+1)})$ is deduced
from $v_n = (L^{(n)}, P^{(n)})$ as follows :

$$
P^{(n+1)} = F(P^{(n)}, H^{(n)}, L^{(n+1)}) \quad \text{and} \quad L^{(n+1)} = g^s(P^{(n)}) \quad (2)
$$

<footnote>(1) SDCM means "Sequentialized Dynamic Cluster Method".</footnote>

<footnote>(2) $L^{(n+1)}$ differs from $L^{(n)}$ only if there exists at least one "improving element", this notion will be precised in [7].</footnote>
Let $u_n = W(v_n)$, $z_n = S'(L^{(n+1)}, P^{(n)})$, $H^{(n)} = \{y_o^{(n)}, \dots, y_m^{(n)}\}$, the sequence $\Pi$ associated to $H^{(n)}$ will be noted $\Pi^{(n)}$. To simplify, let us suppose that all the $H^{(n)}$ blocks are such that $\text{card}(H^{(n)}) = m$ fixed hence $\text{card} E = mN$ (all the following demonstrations are still valid if $m$ is varying).

**Definition :**

We shall say that $R$ is square in the SDCM sense if $\forall P,L,y$

$$S'(L,F(P,y,L)) \prec S'(L,P)$$

**Theorem 1**

If $R$ is square in the sense of the SDCM then the sequences $u_n$ and $z_n$ are convergent and decreasing and the sequence $v_n$ converges.

**Demonstration**

Let $v_n = (L^{(n)}, P^{(n)})$, one has $W(v_n) = S'(L^{(n)}, P^{(n)})$ hence

$$u_n = \sum_{i=1}^{k} \sum_{x \in A_i} (n) R(x, i, P^{(n)})$$

As

$$z_n = S'(L^{(n+1)}, P^{(n)})$$

one has necessarily :

$$u_n \ge Z_n = \sum_{i=1}^{k} \sum_{x \in A_i} (n+1) R(x, i, P^{(n)})$$

as $A_i^{(n+1)}$ is formed by elements of $B$ that minimize $R(\cdot, i, P^{(n)})$ and that $A_i^{(n)} \subset B$. As $R$ is square one has :

$$S'(L^{(n+1)}, F(P^{(n)}, y_o^{(n)}, L^{(n+1)})) \prec S'(L^{(n+1)}, P^{(n)}),$$

in other words :

$$S'(L^{(n+1)}, \Pi_o^{(n)}) \prec S'(L^{(n+1)}, P^{(n)}).$$

one has likewise

$$S'(L^{(n+1)}, F(\Pi_o^{(n)}, y_l^{(n)}, L^{(n+1)})) \prec S'(L^{(n+1)}, \Pi_o^{(n)}),$$

or else

$$S'(L^{(n+1)}, \Pi_l^{(n)}) \prec S'(L^{(n+1)}, \Pi_o^{(n)})$$
The same reasoning may be started over with $y_2^{(n)}$, $y_3^{(n)}$ until $y_m^{(n)}$ the last element of $H^{(n)}$ hence

$$S'(L^{(n+1)}, \prod_m^{(n)}) \le S'(L^{(n+1)}, \prod_{m-1}^{(n)}) \le \dots \le S'(L^{(n+1)}, P^{(n)}).$$

$$\text{where} \quad S'(L^{(n+1)}, P^{(n+1)}) \le S'(L^{(n+1)}, P^{(n)})$$

this implies

$$u_{n+1} \le Z_n$$

The sequence $u_n$ is positive and decreasing thus it converges. Furthermore it reaches its limits because it can take only a finite number of values.

The convergence of the sequence $v_n$ can be demonstrated as follows :

let

$$u_M = \lim_{n \to \infty} u_n$$

there, exists :

$$v_M : u_M = W(v_M)$$

because $u_n$ reaches its limit.

If an integer $M_1$ would exist such that $M_1 > M + N$ and $v_{M_1} \ne v_M$, two cases may occur because W is not necessarily injective :

$$\text{a)} \quad L^{(M_1)} \neq L^{(M)}$$

$$\text{b)} \quad P^{(M_1)} \neq P^{(M)}$$

Should case a) occur, one should find at least one improving element between the iteration M and M-1 hence $u_{M_1} < u_M$ which is impossible.

The case b) cannot occur because the kernels have not been modified during N successive iterations (N has been defined in 3).

**Remark 1 :**

When B is a function of $n \ge 1$ (the iteration number) and such that

$$B_n = \bigcup_{i=1}^{k} A_i^{(n)} \cup \{H^{(n)}\} \cup C$$
(where C may assume any value). The same result is obtained.

In fact $A_i^{(n+1)}$ is formed of the $n_i$ elements of $B_n$ which minimize $R(.,i,P^{(n)})$ and $A_i^{(n)} \subset B_n$; hence if improving elements exist in $B_n$ one has necessarily $u_{n+1} < u_n$.

## 4 - Relations between the DCM and the SDCM

### 4.1 - Reminder_concerning_the_DCM

R is defined as before :

A function $f$ is introduced $f : L_k \to P_k$ such that $f(L) = P$ where

$$P_i = \{ x \in E/D(x, A_i) \leftarrow D(x, A_j) \}$$

if there is equality, one assigns $x$ to the class of smallest index.

The function $g : P_k \to L_k$ is given by $g(P) = L$ where $L = (A_1, \dots, A_k)$ with $A_i = \{ \text{the } n_i \text{ elements of } B \text{ which minimize } R(.,i,P) \}$.

$S$ is a function $L_k \times L_k \to \mathbb{R}^+$ such that

$$S(L,M) = \sum_{i=1}^{k} \sum_{x \in A_i} R(x,i,f(M))$$

The criterion may then be written

$$W(v) = \sum_{i=1}^{k} \sum_{x \in A_i} R(x, i, P)$$

where $v = (L,P)$

### 4.2 - Comparison between the solutions obtained by the DCM and the SDCM

In order to simplify the statement of the following result, we shall say that an SDCM algorithm is associated with a DCM algorithm if the corresponding $F,f,g^s$ and $g$ functions are defined from the same $D$ and $R$ functions. Let us remind that a function $R$ is said to be square in the sense of the DCM
$$ (\text{cf } (1), (2)) \text{ if } \forall L, M \in \mathcal{L}_k \ S(L,M) \le S(M,M) \Rightarrow S(L,L) \le S(L,M) \quad (2) $$

We have shown (cf [3]) that if R is square in the sense of the DCM, the basic DCM algorithm decreases the criterion W.

## Theorem 2

Let $B \equiv E$. Having a basic DCM algorithm and its associated SDCM algorithm, if R is square in the sense of the SDCM and in the sense of the DCM, then these two algorithms decrease the same criterion and converge toward the same solutions.

## Demonstration

R being square in the sense of the two methods, they both decrease the same criterion :

$$ W(v) = \sum_{i=1}^{k} \sum_{x \in A_i} R(x, i, P) \quad \text{where} \quad V = (L, P) \quad \text{and} \quad L = (A_1, \dots, A_k) $$

A last point should now be demonstrated namely that both algorithms converge necessarily on an unbiased element (1) (cf [8]) ; we are going to show that the same is true for the SDCM algorithm. $u_M = \lim_{n \to \infty} u_n$.

Whatever $i \in \{1, 2, \dots, N\}$ ($N$ is defined in 3) $L^{(M)} = L^{(M+i)}$ as a consequence of $u_M = u_M + i$, (if an improving element should exist, we would have $u_M < u_{M+i}$); As the $H^{(M+i)}$ constitutes an overlapping of $E$ when $i$ varies from $1$ to $N$, one has $g(P^{(M)}) = L^{(M)}$.

By definition of $F$ and because $L^{(M+i)} = L^{(M)}$ $\forall i \in \{1, 2, \dots, N\}$ one has

$$ \forall x \in \bigcup_{i=1}^{n} H^{(M+i)} = E \quad \text{et} \quad \forall x \in P_j^{(M+N)} $$

$$ D(x, A_j^{(M)}) \le D(x, A_q^{(M)}) $$

(and $j \le q$ in case of equality) because :

$$ P^{(M+i+1)} = F(P^{(M+i)}, H^{(M+i)}, L^{(M+i+1)}) = F(P^{(M+i)}, H^{(M+i)}, L^{(M)}) $$

Let $M_1 = M + N$ one has :

$$ f(L^{(M_1)}) = P^{(M_1)} $$

as

$$ g(P^{(M_1)}) = L^{(M_1)} $$

<footnote>(1) In other words an element $(L, P) \in \mathcal{L}_k \times \mathcal{P}_k : f(L) = P$ and $g(P) = L$</footnote>
because $M_1$ is greater than $M$, $(L^{(M_1)}, P^{(M_1)})$ is really an unbiased element in the sense of the DCM.

Reciprocally any unbiased element $v$ may be considered as a limit of the sequence $v_n = v$, this being true for both methods. Thus there is identity between the two spaces of the solutions obtained by the DCM and the SDCM.

**Remark :**

If the set $B$ associated to the SDCM is a function of $n$ (the iteration number) and if $B$ is such that $B_n = \bigcup_{j=1}^k A_j^{(n)} \cup \{H^{(n)}\}$ the same result is obtained.

As a matter of fact, let us come back to the previous demonstration ; one has $L^{(M)} = L^{(M+i)}$ because $U_M = U_{M+i}$, which means that no element of $H^{(M+i)}$ $\forall i \in \{0,1,...,N\}$ (hence no element of $E$) improves $L^{(M)}$, we consequently have $L^{(M)} = g(P^{(M)})$.

### 4.3 - Conditions sufficient to get R square in the sense of the DCM and SDCM

**Proposition 1**

In order to have R square simultaneously in the sense of the DCM and in the sense of the SDCM it is sufficient that the following condition be verified.:

$$ (1) \quad S'(L,P) = \sum_{i=1}^{k} \sum_{z \in P_i} \mu(z) D(z,A_i) \quad \forall L = (A_1, \dots, A_k) \in L $$

and

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

**Demonstration**

Let us first show that (1) produces as a consequence $R$ to be square in the sense of the DCM. If the relation $S'(L,P) = \sum_{i=1}^k \sum_{z \in P_i} D(z,A_i)$ is true $\forall P \in P$ one has necessarily $\forall MeL_k$ such that ;

$$ f(M) = Q, S(L,M) = \sum_{i=1}^{k} \sum_{x \in A_i} R(x,i,Q) = S'(L,Q), $$

hence :

$$ (2) \quad S(L,M) = \sum_{i=1}^{k} \sum_{z \in Q_i} \mu(z) D(z,A_i) \quad \forall L, MeL $$
This draws :

$$ (3) \quad S(L,L) = \sum_{i=1}^{k} \sum_{z \in Q_i} \mu(z) D(z,A_i) \quad \text{if } f(L) = Q' = (Q'_1, \dots, Q'_k) $$

Let us suppose that the same element $z \in E$ appears in (2) under the form $D(z, A_j)$ and in (3) under the form $D(z, A_i)$. As a result from the way $Q'$ has been built up, one has necessary $D(z, A_i) \prec D(z, A_j)$. As each element $z \in E$ appears once and only once in (1) and (2) because $Q$ and $Q'$ are partitions of $E$, the same reasoning can be made $\lor z \in E$, hence $S(L,L) \prec S(L,M)$.

The function $R$ is therefore square in the sense of the DCM.

It remains to be shown that the function $R$ is square in the sense of the SDCM :

$$ (1) \quad S'(L,P) = \sum_{i=1}^{k} \sum_{z \in P_i} \mu(z) D(z,A_i) \quad \forall L \in L_k \quad \text{and} \quad P \in P_k $$

$$ (4) \quad \Rightarrow S'(L,F(P,y,L)) = \sum_{i=1}^{k} \sum_{z \in P_i} \mu(z) D(z,A_i) \quad \forall y \in E $$

where $P' = F(P,y,L)$.

Let us suppose that $y$ belongs to $P'j$, one knows that the two following cases may occur :

1) $\exists i : D(y,A_i) \prec D(y,A_j)$ with $j < i$ in case of equality, then $F(P,y,L) \equiv P$

2) $\exists i : D(y,A_i) \prec D(y,A_j)$ with $j > i$ in case if equality, then by definition of $F(P,y,L)$, the expressions (1) and (4) are formed by identical terms, except for the term $y$ which appears in (1) under the form $D(y,A_j)$ and in (4) under the form $D(y,A_i)$. In all cases, one has :

$$ S'(L,F(P,y,L)) \prec S'(L,P) $$

which proves that $S'$ is really square in the sense of the SDCM.

### 4.4 - Comparative advantages of the two methods

The SDCM may be conceived in such a way as to require only once the storing of the whole population in the central unit at each iteration<sup>(1)</sup>

<footnote>(1) We shall say that an "iteration" has been achieved when all the elements of $E$ have been checked for the realisation of a new partition and the computation of new kernels.</footnote>
the means being computed sequentially, block by block, while the DCM needs twice this loading in central unit at each iteration (once to compute the partition, a second time to calculate the kernels).

Furthermore for the DCM the Centerings are accomplished class by class, which is very unpractical when the data table is not stored in the central unit.

The drawback of the SDCM is the need of N - k (N being the number of parts $H_i$) additional and more expensive centerings at each iteration (the number of iterations before convergence seems to be quite the same for the two methods).

## 5 - Study of some variants in the sequential case

A function d is introduced $d : E \times E \rightarrow R^+$ symmetrical and a measure $\mu : P(E) \rightarrow R^+$ such that $\mu(A) = \sum_{x \in A} \mu(x)$.

In the case of the variants 5.1, 5.2, 5.3 which follows, we shall simply give D and R; the associated DCM and SDCM algorithms are defined as in (2) and (4.1) from the function $F,g^s,f$ and $g$ deduced from D and R.

### 5.1 - Constant mass case

In this case $\mu(x)$ is constant, to simplify we shall take $\mu(x) - 1 \quad \forall x \in E$

$$D(x,A) = \frac{1}{\text{card } A} \sum_{a \in A} d(x,a) \quad \text{and} \quad R(x,i,P) = \frac{\text{card}(P_i)}{n_i} D(x,P_i)$$

(n_i the number of elements per kernel is constant $\forall i$)

### 5.2 - The variable mass case

In this case, $\mu(x)$ can take any value, D and R are chosen as follows

$$D(x,A) = \sum_{y \in A} \mu(y) d(x,y)$$

$$R(x,i,P) = \mu(x) D(x,P_i)$$
5.3 - The sequentialized "centers of gravity"-method

Here one has

$$
E \subset \mathbb{R}^m, B \equiv \mathbb{R}^m, n_i = 1 \forall i \in \{1, 2, \dots, k\}
$$

$$
D(x,A) = d(x,G(A))
$$

where

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

$$
R(x, i, P) = \sum_{y \in P_i} \mu(y) d(x, y)
$$

Thorndike (1953) introduced this type of method which has been
thoroughly studied by Mac Queen (1967). We shall now precise the func-
tions F and g<sup>s</sup> easily deduced from D and R.

. F is defined as in 1) by replacing wherever found D by d.

· g<sup>s</sup> : P<sub>R</sub> → L<sub>R</sub> is such that g<sup>s</sup>(P) = L = (A<sub>1</sub>, A<sub>2</sub>, ..., A<sub>k</sub>) where element of B which minimizes

$$
R(x, i, P) = \sum_{y \in P_i} \mu(y) d(x, y)
$$

As d is quadratic, one can easily deduce that

$$
A_i = \frac{1}{\mu(P_i)} \sum_{x \in P_i} \mu(x)x. \quad (\text{i.e. } A_i \text{ is the center of gravity of } P_i)
$$

From a computing stand-point on spares time in using the centers
obtained at the n-th iteration :

$$
A_j^{(n+1)} = \frac{A_j^{(n)} \omega_j^{(n)} + \sum_{i=1}^{m} \epsilon_i \mu(y_i^{(n)}) y_i^{(n)}}{\omega_j^{(n+1)}}
$$

where

$$
\epsilon_i = -1 \quad \text{if} \quad y_i^{(n)} \in P_i^{(n)} \quad \text{and} \quad y_i^{(n)} \notin P_i^{(n-1)}
$$

$$
\epsilon_i = -1 \quad \text{if} \quad y_i^{(n)} \in P_j^{(n)} \quad \text{and} \quad y_i^{(n)} \in P_i^{(n-1)} \quad (\text{for } j \neq i).
$$
$$ \epsilon_i = 0 \quad \text{if} \quad y_i^{(n)} \in P_i^{(n)} \quad \text{and} \quad y_i^{(n)} \notin P_i^{(n-1)} $$

$$ \hat{\omega}_i^{(n+1)} = \omega_i^{(n)} + \epsilon_i \mu(y_i^{(n)}), \quad \hat{\omega}_i^{(0)} = \mu(P_i^{(0)}) $$

It can be easily verified with the help of these formulas that $A_i^{(n+1)}$ is really the center of gravity of $P_i^{(n)}$.

## Proposition 2

R is square in the sense of the DCM and SDCM for the methods 5.1, 5.2 and 5.3.

## Demonstration

In the case of the algorithm 5.1 one has:

$$ S'(L,P) = \sum_{i=1}^{k} \sum_{x \in A_i} R(x,i,P) = \sum_{i=1}^{k} \sum_{x \in A_i} \frac{\text{card } P_i}{n_i} D(x,P_i) \Rightarrow $$

$$ (1) \quad S'(L,P) = \sum_{i=1}^{k} \sum_{x \in A_i} \frac{1}{n_i} \sum_{z \in P_i} d(x,z) \Rightarrow $$

$$ S'(L,P) = \sum_{i=1}^{k} \sum_{z \in P_i} D(z,A_i) $$

In the case of the algorithm 5.2 one has:

$$ S'(L,P) = \sum_{i=1}^{k} \sum_{x \in A_i} R(x,i,P) = \sum_{i=1}^{k} \sum_{x \in A_i} \mu(x) D(x,P_i) $$

$$ S'(L,P) = \sum_{i=1}^{k} \sum_{x \in A_i} \mu(x) \sum_{z \in P_i} \mu(z) d(x,z) $$

$$ (2) \quad \Rightarrow S'(L,P) = \sum_{i=1}^{k} \sum_{z \in P_i} \mu(z) \sum_{x \in A_i} \mu(x) d(z,x) $$

$$ \Rightarrow S'(L,P) = \sum_{i=1}^{k} \sum_{z \in P_i} \mu(z) D(z,A_i) $$

In the case of the sequentialized centers of gravity one has:

$$ S'(L,P) = \sum_{i=1}^{k} \sum_{x \in A_i} R(x,i,P) = \sum_{i=1}^{k} R(A_i,i,P) = \sum_{i=1}^{k} \mu(y) d(A_i,y) $$

$$ (3) \quad S'(L,P) = \sum_{i=1}^{k} \mu(y) D(y,A_i) $$

(because $A_i$ is reduced to a unique point hence $G(A_i) = A_i$)
It is sufficient to apply proposition 1 to the equalities (1)
(2) and (3) to obtain the result.

5.4 - A variant of the sequentialized centers of gravity method

One has $E \subset \mathbb{R}^m$, $B \equiv \mathbb{R}^m$, $n_i = 1$, $\forall i \in \{1, 2, \dots, k\}$

The functions D' and R are defined as follows :

$$
D' : E \times P(E) \times E \to \mathbb{R}^+ : D(x, B, A) = \frac{\mu(x) \mu(\bar{B}) d(x, A)}{\mu(x) + \mu(\bar{B})}
$$

where

$$
\bar{B} = \mathcal{C}_B \text{ et } R(x,i,P) = \sum_{y \in P_i} \mu(y) d(x,y)
$$

The functions F and g<sup>s</sup> are slightly modified in this variant, one
has :

$$
g' : \mathbb{P}_k \times E \to \mathbb{P}_k \times E \times \mathbb{L}_k \quad \text{such that :}
$$

$g'(P,x) = (P,x,L)$ where $L = (A_1, \dots, A_k)$ is defined as
follows :

Let $x \in P_j$, $A_i$ is then the element which minimizes $R(\cdot, i, P)$ $\forall i \neq j$
and $A_j$ is the element which minimizes $R(\cdot, j, \bar{P})$ where

$$
\bar{P} = (P_1, \dots, \bar{P}_j, \dots, P_k) \text{ with } \bar{P}_j = \bar{P}_j - \{x\}
$$

These amounts to say that the $A_i$ are the centers of gravity of $P_i$ (as
for the SCG method) except for $A_j$ which is the center of gravity of
$P_j - \{x\}$

$$
F' : \mathbb{P}_k \times E \times \mathbb{L}_k \to \mathbb{P}_k \times E
$$

such that

$F'(Q, x, L) = (P, y)$

where P is defined using Q in the following way (let us suppose that
x ∈ Q_j)

$$
a) \quad \forall i : D(x, Q_i, A_i) \le D(x, Q_j, A_j)
$$

with $j < i$ in the case of equality then $P = Q$.
$$ b) \quad \exists i : D(x, Q_i, A_i) \le D(x, Q_j, A_j) $$

with $j > i$ in case of equality then

$$ P_i = Q_i \cup \{x\}, \quad P_j = Q_j - \{x\} $$

and for $1 \ne i, 1 \ne j, P_1 = Q_1$.

- As far as the element $y$ is concerned, it can be deduced from $x$ with the help of the sequence $x^{(n)}$ that has been defined in 2), in the following way :

as $x \in E$, $\exists n$ such that $x = x^{(n)}$ (with $0 \le n \le \text{card } E$), let us suppose then $y = x^{(n+1)}$.

The algorithm unfolds the following way : one starts from $P^{(0)}$ and $x^{(0)}$, one deduces from this :

$$ L^{(1)} = g'(P^{(0)}, x^{(0)}) \quad \text{and} \quad P^{(1)} = F(P^{(0)}, x^{(0)}, L^{(1)}) $$

$$ \text{Having} \quad v_n = (L^{(n)}, P^{(n)}) $$

one can decide

$$ v_{n+1} = (L^{(n+1)}, P^{(n+1)}) $$

where

$$ L^{(n+1)} = g'(P^{(n)}, x^{(n)}) \quad \text{and} \quad P^{(n+1)} = F'(P^{(n)}, x^{(n)}, L^{(n+1)}) $$

It will be shown later in theorem 3 that if $d$ is a quadratic distance the algorithm associated to the variant decreases the sequence

$$ u_n = \sum_{i=1}^{k} \text{card } P_i^{(n)} \quad \text{var } P_i^{(n)} $$

## 5.5 - The kernel-partition method

In this method, the set of the kernels forms a partition of $E$. In this case, one has $ECR^m, B \equiv R^m, n_i = 1 \text{ vie } 1,2,...,k$

$$ D(x,A) = \sum_{y \in A} \mu(y) d(x,y) $$

$$ R(x,i,P) = \mu(x) D(x,P_i) $$
The function F can be deduced from D and R as in 1), on the contrary the function g is completely changed and becomes identical to F. Therefore the algorithm unfolds as follows : one starts with P(0) and H(0), one deduces :

$$L^{(1)} = F(P^{(0)}, H^{(0)}, P^{(0)}) \quad \text{and} \quad P^{(1)} = F(L^{(1)}, H^{(1)}, L^{(1)}) \\ v_{n+1} = (L^{(n+1)}, P^{(n+1)})$$

is obtained from

$$v_n = (L^{(n)}, P^{(n)})$$

in taking

$$L^{(n+1)} = F(P^{(n)}, H^{(n)}, P^{(n)})$$

and

$$P^{(n+1)} = F(L^{(n+1)}, H^{(n+1)}, P^{(n+1)})$$

let

$$u_n = W(v_n) = \sum_{i=1}^{k} \sum_{x \in L_i} (n) \quad R(x, i, P^{(n)})$$

## Proposition 3

The kernels-partition method decreases the sequence $u_n = W(v_n)$.

## Demonstration

$$u_n = \sum_{i=1}^{k} \sum_{x \in L_i} (n) \quad R(x, i, P^{(n)}) = \sum_{i=1}^{k} \sum_{x \in L_i} (n) \quad \mu(x) \quad D(x, P_i^{(n)})$$

$$z_n = \sum_{i=1}^{k} \sum_{x \in L_i} (n+1) \quad \mu(x) \quad D(x, P_i^{(n)})$$

$$\text{Let } x \in P_j^{(n)} \cap H^{(n)}$$

Two cases may arise :
$$
a) \exists i : D(x, P_i^{(n)}) \le D(x, P_j^{(n)}) \text{ then } z_n = u_n
$$

$$
b) \exists i : D(x, P_i^{(n)}) < D(x, P_j^{(n)}) \text{ then } I_j^{(n+1)} = P_j^{(n)} - \{x^{(n)}\}
$$

and

$$
L_i^{(n+1)} = P_i^{(n)} \cup \{x^{(n)}\}. \text{ Now } \mu(x) D(x, P_i^{(n)}) < \mu(x) D(x, P_j^{(n)}),
$$

as the same reasoning can be made

$$
x \in P_j^{(n)} \cap H^{(n)} \quad \text{and} \quad \forall j \in \{1, 2, \dots, k\}
$$

one has then necessarily $z_n \triangleleft u_n$ as only the elements of $H^{(n)}$ could
have changed of class.

It remains to be shown that $u_{n+1} \le z_n$

One has :

$$
\begin{align*}
u_{n+1} &= \sum_{i=1}^{k} \sum_{x \in L_i^{(n+1)}} \mu(x) D(x, P_i^{(n+1)}) \\
&= \sum_{i=1}^{k} \sum_{y \in P_i^{(n+1)}} \mu(y) \sum_{x \in L_i^{(n+1)}} \mu(x) D(x, P_i^{(n+1)}) \\
&= \sum_{i=1}^{k} \sum_{y \in P_i^{(n+1)}} \mu(y) D(y, L_i^{(n+1)})
\end{align*}
$$

With a demonstration similar to the preceeding one ($L_i^{(n+1)}$ playing
the role of $P_i^{(n)}$ and $P_i^{(n+1)}$ the one of $L_i^{(n+1)}$) one comes the result.

6 - Expression of the criterion in the case where d is quadratic

In the case where d is a quadratic distance and for the different
variants we can express the criteria to be optimized in function of the
variance of the classes and the kernels. We shall say that d is a qua-
dratic distance if ∀x, y ∈ E one has ;

$$
d(x,y) = (x-y)'Q(x-y)
$$

where Q is a matrix defined positive.

Furthermore, in all that follows let :

$$
\operatorname{var} B = \frac{1}{\mu(B)} \sum_{x \in B} \mu(x) d(x, G(B)) \quad \text{and} \quad G(B) = \frac{1}{\mu(B)} \sum_{x \in B} \mu(x) x \quad \forall B \subset E.
$$
Let $v = (L,P)$ with $L = (A_1, \dots, A_k)$ and $P = (P_1, \dots, P_k)$

**Theorem 3**

a) . The method 5.1. (constant mass) decreases the criterion :

$$W_1(v) = \sum_{i=1}^{k} \mu(P_i) [\text{var } P_i + \text{var } A_i + d(G(A_i), G(P_i))]$$

b) . The method 5.2. (variable mass) decreases

$$W_2(v) = \sum_{i=1}^{k} \mu(P_i) \mu(A_i) [\text{var } P_i + \text{var } A_i + d(G(A_i), G(P_i))]$$

c). The sequentialized centers of gravity method decreases simultaneously the two following criteria :

$$W_3(v) = \sum_{i=1}^{k} [\mu(P_i) \text{var } P_i + d(A_i, G(P_i))]$$

$$W_4(v) = \sum_{i=1}^{k} \mu(P_i) \text{var } P_i$$

d). The method 5.4. decreases the criterion $W_4(v)$

e). The kernels partition-method decreases :

$$W_5(v) = \sum_{i=1}^{k} \mu(L_i) \mu(P_i) [\text{var } P_i + \text{var } L_i + d(G(P_i), G(L_i))]$$

**Demonstration**

According to proposition 2 and theorem 2 one knows that the methods 5.1, 5.2 and 5.3 decrease their corresponding criterion

$$W(v) = S'(L,P)$$

We shall now explicit the value of $W(v)$ in each of the three cases.

a) - For the method 5.1 (constant ponderation) one has :

$$W(v) = S'(L,P) = \sum_{i=1}^{k} \sum_{x \in A_i} R(x,i,P) = \sum_{i=1}^{k} \sum_{x \in A_i} \frac{\text{card } P_i}{n_i} D(x,P_i) \\ = \sum_{i=1}^{k} \sum_{x \in A_i} \frac{1}{n_i} \sum_{y \in P_i} d(x,y)$$

As $d$ is quadratic, one may use Huyghens's theorem hence :
$$
\begin{align*}
W(v) &= \sum_{i=1}^{k} \frac{1}{n_i} \sum_{x \in A_i} \text{card } P_i [d(x, G(P_i)) + \text{var } P_i] \\
&= \sum_{i=1}^{k} \text{card } P_i \left[ \sum_{x \in A_i} \frac{d(x, G(P_i))}{n_i} + \frac{\text{card } A_i}{n_i} \cdot \text{var } P_i \right] \\
&= \sum_{i=1}^{k} \text{card } P_i [\text{var } A_i + d(G(A_i), G(P_i)) + \text{var } P_i]
\end{align*}
$$

For this variant one actually sets $W(v) = W_1(v)$

b) - In the case of a variable ponderation (method 5.1) one has :

$$
\begin{align*}
W(v) &= \sum_{i=1}^{k} \sum_{x \in A_i} R(x, i, P) = \sum_{i=1}^{k} \sum_{x \in A_i} \mu(x) D(x, A_i) \\
&= \sum_{i=1}^{k} \sum_{x \in A_i} \mu(x) \sum_{y \in P_i} \mu(y) d(x, y)
\end{align*}
$$

According to Huyghens's theorem one can deduce

$$
\begin{align*}
W(v) &= \sum_{i=1}^{k} \sum_{x \in A_i} \mu(x) [\mu(P_i) \text{var } P_i + \mu(P_i) d(x, G(P_i))] \\
&= \sum_{i=1}^{k} [\mu(P_i) \sum_{x \in A_i} d(x, G(P_i)) + \mu(A_i) \mu(P_i) \text{var } P_i] \\
&= \sum_{i=1}^{k} [(P_i)[(\mu(A_i) d(G(A_i), G(P_i)) + \mu(A_i) \text{var } A_i)] \\
&\quad + \mu(A_i) \mu(P_i) \text{var } P_i] \\
&= \sum_{i=1}^{k} \mu(P_i) \mu(A_i) [\text{var } P_i + \text{var } A_i + d(G(A_i), G(P_i))]
\end{align*}
$$

c) - As far as the centers of gravity method is concerned one has :

$$
W(v) = \sum_{i=1}^{k} R(A_i, i, P) = \sum_{i=1}^{k} \sum_{y \in P_i} \mu(y) d(A_i, y)
$$

$$
\text{Hence} \quad W(v) = \sum_{i=1}^{k} \mu(P_i) [d(A_i, G(P_i)) + \text{var } P_i] = W_3(v)
$$

According to theorem 1 and proposition 2 one knows that the sequence
$z_n = S'(L^{(n+1)}, P^{(n)})$ is decreasing.
Now $S'(L^{(n+1)}, P^{(n)}) = \sum_{i=1}^{k} R(G(P_i^{(n)}), i, P^{(n)})$ according to the definition of $L^{(n+1)}$.

$$ \text{Hence : } z_n = \sum_{i=1}^{k} \sum_{y \in P_i^{(n)}} \mu(y) d(G(P_i^{(n)}), y) \\ = \sum_{i=1}^{k} \mu(P_i^{(n)}) \text{var } P_i^{(n)} = W_4(v_n) $$

d) - For the variant 5.4 we shall show that $W_4(P^{(n+1)}) \le W_4(P^{(n)})$

Let us remind that

$$ g'(P^{(n)}, x^{(n)}) = L^{(n+1)} $$

$$ \text{and} \quad F'(P^{(n)}, x^{(n)}, L^{(n+1)}) = (P^{(n+1)}, x^{(n+1)}) $$

$$ \text{where} \quad P^{(n+1)} = F(P^{(n)}, x^{(n)}, L^{(n+1)}) $$

It is known, by definition, that two cases may occur ; let suppose $x^{(n)} \in P_j^{(n)}$ :

**1st case :**

$\mathfrak{A}_i : D(x^{(n)}, P_i^{(n)}, A_i^{(n+1)}) \le D(x^{(n)}, P_j^{(n)}, A_j^{(n+1)})$ with $j < i$ in case of equality, then $P \equiv Q$

**2nd case :**

$$ \exists i : D(x^{(n)}, P_i^{(n)}, A_i^{(n+1)}) < D(x^{(n)}, P_j^{(n)}, A_j^{(n+1)}) $$

$$ \text{then} \quad P_i^{(n+1)} \equiv P_i^{(n)} \cup \{x^{(n)}\}, \quad P_j^{(n+1)} \equiv P_j^{(n)} - \{x^{(n)}\} $$

$$ \text{and} \quad \forall \ell \ne i, \ell \ne j \quad P_\ell^{(n+1)} \equiv P_\ell^{(n)} $$

In the case of a) one has $W_4(P^{(n+1)}) = W_4(P^{(n)})$ ; in the case of b) one has :
$$D(x^{(n)}, P_i^{(n)}, A_i^{(n+1)}) < D(x^{(n)}, P_j^{(n)}, A_j^{(n+1)}) \Rightarrow$$

$$(1) \qquad \frac{\mu(x) \quad \mu(P_i^{(n)})}{\mu(x) + \mu(P_i^{(n)})} \quad \left( d(x, G(P_i^{(n)})) < \frac{\mu(x) \quad \mu(\bar{P}_j^{(n)})}{\mu(x) + \mu(\bar{P}_j^{(n)})} \quad d(x, P_j^{(n)}) \right)$$

$$\text{where} \qquad \bar{P}_i^{(n)} = P_i^{(n)} - \{x^{(n)}\}$$

It can be easily demonstrated with the formula of Huygens that, for any ACE, BCE and d quadratic one has :

$$\frac{\mu(A) \quad \mu(B)}{\mu(A) + \mu(B)} d(G(A), G(B)) = \mu(A \cup B) \cdot \text{var}(A \cup B) - \mu(A) \cdot \text{var}(A) - \mu(B) \cdot \text{var}(B)$$

hence (1) implies :

$$\begin{align*}
& \mu(P_i^{(n)} \cup \{x^{(n)}\}) \quad \text{var}(P_i^{(n)} \cup \{x^{(n)}\}) - \mu(P_i^{(n)}) \quad \text{var}(P_i^{(n)}) \\
< & \mu(\bar{P}_j^{(n)} \cup \{x^{(n)}\}) \quad \text{var}(\bar{P}_j^{(n)} \cup \{x^{(n)}\}) - \mu(\bar{P}_j^{(n)}) \quad \text{var}(\bar{P}_j^{(n)}) \Rightarrow \\
& \mu(P_j^{(n+1)}) \quad \text{var}(P_j^{(n+1)}) - \mu(P_i^{(n)}) \quad \text{var}(P_i^{(n)}) \\
< & \mu(P_j^{(n)}) \quad \text{var}(P_j^{(n)}) - \mu(P_j^{(n+1)}) \quad \text{var}(P_j^{(n+1)})
\end{align*}$$

hence

$$0 > (P_i^{(n+1)}) \text{ var } P_i^{(n+1)} + \mu(P_j^{(n+1)}) \text{ var } P_j^{(n+1)} \\ - [\mu(P_i^{(n)}) \text{ var } P_i^{(n)} + \mu(P_j^{(n)}) \text{ var } P_j^{(n)}]$$

$$\text{As} \quad P_j^{(n+1)} \equiv P_i^{(n)} \quad \forall l \neq i \text{ and } l \neq j \quad \text{it can be deduced that} \\ 0 > \sum_{i=1}^{k} \mu(P_i^{(n+1)}) \text{ var } P_i^{(n+1)} - \sum_{i=1}^{k} \mu(P_i^{(n)}) \text{ var } P_i^{(n)}$$

Hence finally : $W_4(P^{(n+1)}) < W_4(P^{(n)})$ ; this inequality becoming large when taking in account the case a)

e) - Finally let us consider the "kernels partition" method

The proposition 3 proves that the method decreases the criterion :
$$
\begin{align*}
W(v) &= \sum_{i=1}^{k} \sum_{x \in L_i} R(x, i, P) = \sum_{i=1}^{k} \mu(x) D(x, P_i) \\
&\Rightarrow W(v) = \sum_{i=1}^{k} \sum_{x \in L_i} \mu(x) \sum_{y \in L_i} \mu(y) d(x, y) \\
&= \sum_{i=1}^{k} \sum_{x \in L_i} \mu(x) \mu(P_i) [\text{var } P_i + d(x, \text{E}(P_i))] \\
&= \sum_{i=1}^{k} \mu(L_i) \mu(P_i) [\text{var } P_i + \text{var } L_i + d(G(P_i), G(L_i))] = W_5(v)
\end{align*}
$$

Let us note that when convergence occurs one has $L^{(n+1)} = P^{(n)}$ and that the criterion value is therefore expressed in the following way :

$$
W(v) = 2 \sum_{i=1}^{k} \mu(P_i)^2 \text{var } P_i
$$

7 - Comparative advantages of the different variants

. In the case of the constant mass method (variant 5.1), the tendency
is to decrease the variance of the classes and the kernels and to bring
at the best each kernel closer to the center of the associated class.

. The same observation can be made for the variant 5.2 in pointing out
that this method favours the kernels of low mass. For instance, in the
contingency of a table, when the mass of an individual corresponds to his
frequence, the tendancy will be to form classes which are close to
kernels formed by similar and characteristic individuals (because they
are of low frequency).

. In the case of the centersof gravity method (5.3) the algorithm gives
classes located around mean points, without being influenced by the fact
that such points are situated at high density location. This may be distur-
bing especially in the case when the number of required classes is small
compared to the number of individuals. Empty classes may be of interest
to obtain geometrical or artificial patterns.

Yet in the case of lifescience data (physics, biology, economics etc)
a pattern is a being that nature tends to reproduce more or less perfectly.
The better this copy the more objective the reality of this pattern will
be and will correspond to a region of high density points in the parameter
space. It is this type of pattern which interesses the user and it corres-
ponds to filled classes. Let us remark in addition that the classes obtained by the center of gravity method will be all the more better when far apart from the global center of gravity (it is sufficient to apply Huyggens's theorem).

The variant of the center of gravity method (5.4) has the advantage of decreasing the same criterion as the variant (5.3) but does not admit the same unbiased elements. It can be easily seen that an unbiased element for 5.4. is unbiased for 5.3. but that the reciprocal is not true. The method 5.4. should permit to improve the solutions obtained by 5.3.

Let us consider at last the kernels-partition method. On the contrary of variants 5.1 and 5.2 the assignment of an individual to a class is realised by comparing the individual to parts of E having different size (forming a partition), and not those of same size (the kernels).

As the distance used is $D(x,P_i) = \sum_{j} \mu(y) d(x,y)$ one can see that an individual will tend to be assigned to a class of low population or low mass. Let us keep in mind that this variant has the tendency to give classes of fairly similar weight and size reducing at the same time the variance of these classes.

### Example of an application of the kernel-partition variant

This variant could be used to get the electoral cut-up of a country taking as objects : the polling office ; and as parameters : their geographical location ; the weight of each office being the number of registrated voters ; the number of classes k being obviously equal to the number of deputies.

## 8 - Example of a similarity index

### 8.1 - $\chi^2$ distance

Let us note $P(i,j)$ the value taken by the individual $y_i$ for the parameter j.

Let :

$$P(i,..) = \sum_{j} P(i,j) \quad P(.,j) = \sum_{i} P(i,j)$$

$$P(.,..) = \sum_{i,j} P(i,j).$$
The $\chi^2$ distance between two individuals i and i' can be written :

$$d(i, i') = \sum_j \frac{1}{P(\cdot, j)} \left( \frac{P(i, j)}{P(i, \cdot)} - \frac{P(i', j)}{P(i', \cdot)} \right)^2$$

Let us consider that an individual $y_i$ is characterized by the vector :

$$y_i = \left( \frac{P(1, j)}{P(1, \cdot)}, \dots, \frac{Pcard(E), j)}{P``card(E), \cdot)} \right)$$

and let $Q$ be the diagonal matrix such that $Q_{i,j} = \frac{1}{P(\cdot, j)}$. In this condition $d$ can be written the following way :

$$d(i, i') = y_i \rightarrow Q_{y_i}$$

The measure $\mu$ of $E \rightarrow R^+$ is $\mu(y_i) = P(i, \cdot)$ for $ACE$. Let us note $\mu(A) = \sum_{y_i \in A} \mu(y_i)$

$$\text{let } [A] = \{i | y_i \in A\}$$

The center of gravity is then written as :

$$\vec{G}(A) = \frac{1}{\mu(A)} \sum_{i \in [A]} \mu(y_i) \vec{y}_i$$

$$\text{hence} \quad G_j(A) = \frac{1}{\sum_{i \in [A]} P(i, \cdot)} \sum_{i \in [A]} P(i, \cdot) \frac{P(i, j)}{P(i, \cdot)} \\ = \frac{1}{\sum_{i \in [A]} P(i, \cdot)} \sum_{i \in [A]} P(i, j)$$

By definition one has :

$$\text{var } A = \frac{1}{\mu(A)} \sum_{i \in [A]} \mu(y_i) d(y_i, G(A))$$

In the case of the variant 5.1 where it is necessary for the kernels to have the same mass, one has $\mu(y_i) = 1$ $\forall i$. The same formulas may be obtained by replacing $\mu(A)$ by $\text{card}(A)$.
## 8.2 - Use of the $\chi^2$ distance in the case of a table of qualitative variables

These tables are composed of objects characterized by parameters which may take several integer values. Such table may be used only when the parameters are qualitative or are a combination of qualitative and quantitative parameters (zones are cut up and coded).

Let us note :

k the parameter number

The value $t_{ik}$ achieved by the k parameter for the object i.

Exemple : $t_{1,2} = 2$ in the table 1.

<table><caption>Table 1</caption><thead><tr><th>i</th><th>k</th><th>1</th><th>2</th><th>3</th></tr></thead><tbody><tr><td>1</td><td></td><td>4</td><td>2</td><td>1</td></tr><tr><td>2</td><td></td><td>1</td><td>2</td><td>2</td></tr><tr><td>3</td><td></td><td>3</td><td>1</td><td>2</td></tr><tr><td>4</td><td></td><td>1</td><td>3</td><td>2</td></tr></tbody></table>

<table><caption>Table 2</caption><thead><tr><th>i</th><th>k</th><th colspan="4">k = 1</th><th colspan="4">k = 2</th><th colspan="4">k = 3</th></tr></thead><tbody><tr><td>1</td><td></td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td></tr><tr><td>2</td><td></td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td></tr><tr><td>3</td><td></td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td></tr><tr><td>4</td><td></td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td></tr></tbody></table>

We shall now give formulas allowing the computation of the distance between two objects, between an object and a group and between two groups.

These formulas allow the use of the DCM or SDCM without having to store in the central unit a table of type 2 ; the table 1 giving the codes being sufficient in itself. It can be seen that the gain is of importance when the number of values is important.

Similarly, we shall note :

$$ - p^k (i,j) = \begin{cases} 1 & \text{when the value j of the k parameter is achieved for the object i} \\ 0 & \text{otherwise} \end{cases} $$
In other words :

- $p_k(i,j)$ = content of the column j for the parameter k for the individual i in table 2.

Exemple :

$$ P^{(2)} (1,2) = 1 \qquad P^{(3)} (3,1) = 0 \text{ in table 2} \\ - p^k (j) = \sum_i p^k (i,j) \qquad p^k (i) = \sum_j p^k (i,j) = 1 $$

In other words $p^k(j)$ represents the number of time the parameter k has taken the value j.

- $P(t_{i,j})$ = number of achievements, $t = t_{i,k}$ in the variable k.

(In other words $P(t_{i,k})$ represents the number of individuals equal or different of i which have taken the same value than i on the kth parameter).

Exemple :

$$ P(t_{2,1}) = 2 \text{ (cf. table 1)} \\ - \delta_{i,i'}^k = \begin{cases} 1 & \text{if } t_{i,k} \neq t_{i',k} \\ 0 & \text{if } t_{i,k} = t_{i',k} \end{cases} $$

## Proposition 4

Let $d(i,i')$ the $\chi^2$ distance between i and i' one has :

$$ d(i,i') = \sum_i \left( \frac{1}{P(t_{i,k})} + \frac{1}{P(t_{i',k})} \delta_{i,i'}^k \right) $$

## Demonstration

$$ \text{Reminder : } d(i,i') = \sum_j \frac{1}{P(j)} \left( \frac{P(i,j)}{P(i)} - \frac{P(i',j)}{P(i')} \right)^2 $$

with our notations one has :

$$ d(i,i') = \sum_k d^k (i,i') $$
$$ \text{where} \quad d^k(i, i') = \sum_{j=1}^{n(k)} \frac{1}{p^k(j)} \left( \frac{p^k(i, j)}{p^k(i)} - \frac{p^k(i', j)}{p^k(i')} \right)^2 $$

where $n(k)$ is the number of values of the parameter k.

$$ d^k(i, i') = \sum_{j=1}^{n(k)} \frac{1}{p^k(j)} (p^k(i, j) - p^k(i', j))^2 $$

If $t_{ik}$ is different from $t_{l',k'}$ there exists $j_1$ and $j_2$ such that :

$$ \begin{gather*} d^k(i, i') = \frac{1}{p^k(j_1)} (p^k(i, j_1))^2 + \frac{1}{p^k(j_2)} (p^k(i, j_2))^2 \\ d^k(i, i') = 0 \quad \text{if} \quad t_{i,k} = t_{i',k} \end{gather*} $$

$$ \text{Now} \quad \begin{gather*} P_{(j_1)}^k = P(t_{ik}), \quad P_{(j_2)}^k = P(t_{i',k}), \quad P_{(i,j_1)}^k = P_{(i,j_2)}^k = 1 \\ \Rightarrow d^k(i, i') = \left( \frac{1}{P(t_{i,k})} + \frac{1}{P(t_{i',k})} \right) \delta^{k}_{i,i'} \\ \Rightarrow d(i, i') = \delta^{k}_{k} \left( \frac{1}{P(t_{i,k})} + \frac{1}{P(t_{i',k})} \right) \delta^{k}_{i,i'} \end{gather*} $$

## Interprétation

The more frequent the achievement $t_{i,k}$ of a variable (i.e., $P(t_{i,k})$ large) the less this achievement has importance in the computing of the distances. One can also say that two individuals are all the closer when they take the same values for achievements of low frequency.

## 4 - Computation of $D(i_o, I)$

Let $D(i_o, I) = \sum_{i \in I} d(i_o, i)$. (d being symmetrical, one can easily deduce that R is square using proposition 1).
$$D(i_o, I) = \sum_{i \in I} \sum_{k} \left( \frac{1}{P(t_{i_o,k})} + \frac{1}{P(t_{i,k})} \right) \delta_{i_o i}^k$$

$$= \sum_{i \in I} \sum_{k} \left( \frac{\delta_{i_o i}^k}{P(t_{i_o,k})} + \frac{\delta_{i_o i}^k}{P(t_{i,k})} \right)$$

$$= \sum_k \sum_i \left( \frac{\delta_{i_o i}}{P(t_{i_o,k})} + \sum_k \sum_i \frac{\delta_{i_o i}}{P(t_{i,k})} \right)$$

$$D(i_o, I) = \sum_k \frac{1}{P(t_{i_o,k})} \sum_{i \in I} \delta_{i_o i}^k + \sum_k \sum_{i \in I} \frac{\delta_{i_o i}^k}{P(t_{i,k})}$$

Let us pose

$$\Delta_{i_o i}^k = 1 - \delta_{i_o i}^k \qquad \Delta_{i_o i}^k = \begin{cases} 1 & \text{if } t_{i_o,k} = t_{i,k} \\ 0 & \text{if } t_{i_o,k} \neq t_{i,k} \end{cases}$$

hence

$$D(i_o, I) = \sum_k \frac{1}{P(t_{i_o,k})} \sum_{i \in I} (1 - \Delta_{i_o i}^k) + \sum_k \sum_{i \in I} \frac{1 - \Delta_{i_o i}^k}{P(t_{i,k})}$$

Let $P_I(t_{i_o,k})$ be the number of times that $t_{ik} = t_{i_o k}$

$$\text{Then :} \quad \sum_{i \in I} \delta_{i_o i} = \sum_i (1 - \Delta_{i_o i}^k) = \text{card}(I) - P_I(t_{i_o,k})$$

In other words : $\sum_{i \in I} \delta_{i_o i}$ is the number of times that $t_{ik}$ is different from $t_{i_o k}$.

$$\Rightarrow D(i_o, I) = \sum_k \frac{1}{P(t_{i_o,k})} (\text{card}(I) - P_I(t_{i_o,k})) + \sum_k \sum_{i \in I} \frac{1}{P(t_{i,k})} - \sum_k \sum_i \frac{\Delta_{i_o i}^k}{P(t_{i,k})}$$
**Remark 1:**

1st case) If one has $k : P_I(t_{i_o,k}) = P(t_{i_o,k})$ and $card I = P(t_{i_o,k})$ (which means that all the elements of E such that $t_{i,k} = t_{i_o,k}$ are in I and I contains only these elements)

$$
\text{Then} \quad D(i_i, I) = \sum_k \left( \frac{1}{P(t_{i_o,k})} (-P(t_{i_o,k})) + \sum_{I \in I} \frac{1}{P(t_{i,k})} \right) \\
= \sum_k \left( -1 + \frac{\text{card}(I)}{P(t_{i_o,k})} \right) = 0
$$

2nd case) If one has $P_I(t_{i_o,k}) \le P(t_{i_o,k}) \forall k$

one has $\text{card } I \ge P_I(t_{i_o,k})$

hence
$$ D(i_o, I) = \sum_k \left[ \frac{\alpha_k}{P(t_{i_o,k})} + \sum_{I \in I} \frac{1}{P(t_{i,k})} \right] \quad \text{where} \quad k \ge -1 $$

where $\alpha_n > 0$

The 3rd case $P_I(t_{i_o,k}) > P(t_{i_o,k})$ is impossible.

**Remark 2 :**

If I is reduced to a unique element one finds again the formula of proposition 1.

9 - Programmation of the basic algorithm, in the case of a quadratic distance

9.1 - Choice of the starting partition in the case of large tables

One enters $H^{(0)}$ a sampling estimated or drawn at random from the
total population. One enters $P_i^{(0)}$ until saturation (with $B^{(0)}$) of the
memory. One may enter $P_i^{(0)}$ in the same order of arrangement as the data
or else draw k points or k kernels $A_1, \dots, A_k$ estimated or taken ran-
domly, $P_i^{(0)}$ is then formed by points closer to $A_i$ than to $A_j \sim \text{je} \{1,2,\dots,k$
## 9.2 - Building up of the new kernels and partitions

$P_i^{(0)}$ being stored in the central unit, one computes $G(P_i^{(0)})$ and $D(x, G(P_i^{(0)})$, where from one can decuce $L_i^{(0)}$ which is formed by the ni elements which minimize $D(x, G(P_i^{(0)}))$ among the elements of $P_i^{(0)} \cup B^{(0)}$. This calculation having been done for $i=1,...,k$ (keeping in memory the number of the class to which each individual has been assigned), one enters $H^{(n)} = \{y_1^{(n)},..., y_m^{(n)}\}$; for each element $y_i^{(n)}$ two cases may occur :

a) the closest kernel to $y_i^{(n)}$ is of a different class from the one where $x^{(n)}$ was, it is then assigned to that class.

b) $y_i^{(n)}$ is closer to the kernel of the class to which it was assigned than to any other kernel, in this case $y_i^{(n)}$ does not change of class. All the elements $H^{(n)}$ having been considered the centers of gravity of all the modified classes are computed. In case a) as in case b) one checks if $y_i^{(n)}$ could not be an improving element of the kernel of the class to which it was assigned. More precisely, it is verified that $A_i^{(n+1)}$ is actually formed by the ni elements which minimize $D(.,G(P_i^{(n)})$ among $B_n = B^{(0)} \cup A_i^{(n)} \cup H^{(n)}$ (cf Remark 1) or else (more economically) $B_n = A_i^{(n)} \cup H^{(n)}$.

## 9.3 - Cut-off tests

In the finite case one cuts off when the criterion is not decreasing significantly for two consecutive overlappings of E by the $H^{(n)}$.

In the infinite case the sequence $H^{(n)}$ is constituted by a sequence of parts of E with empty intersections, the process is ended when the criterion does not decrease in a significant way and when at the same time $\cup_n H^{(n)}$ is statiscally representative of the population : the Smirnov-Kolgorov test may be used for instance, or else a sequential analysis method.

## 9.4 - The organigram

To understand the organigram it is necessary to know the following notations :
<figure><img src="image_1.png" /></figure>

• The **X** means computing of X

• The **X** means storage of X in memory
$$
T(i) = D(y_l^{(N)}, G(A_i^{(N-1)})) + n_i \operatorname{var} A_i^{(N-1)}
$$

(nᵢ is the number of elements per kernel). C<sub>J</sub><sup>(N)</sup> (ℓ) is the class number
where y<sub>ℓ</sub><sup>(N)</sup> is found at the iteration J.

$$
Q^{(N)} = (Q_{1}^{(N)} = (Q_{1}^{(N)}, \dots, Q_{k}^{(N)}), B^{(N)} = (B_{1}^{(N)}, \dots, B_{k}^{(N)}))
$$

$$
\text{where}
$$

$$
B_i^{(N)} = \left\{ \bigcup_l y_l^{(N)} \mid C_{N-1}^{(N)} (l) = i, C_N^{(N)} (l) \neq i \right\}
$$

In other words $Q_i^{(N)}$ is formed by the set of elements of $H^{(N)}$ that must
be added and $B_i^{(N)}$ those that must be removed from $P_i^{(N-1)}$ to obtain $P_i^{(N)}$.

$$
Q_i^{(N)} \cup \left[ \begin{array}{c} B_i^{(N)} \\ P_i^{(N-1)} \end{array} \right] = P_i^{(N)}
$$

M is the smallest integer such that H⁽⁰⁾ U ... U H⁽M⁾ ≡ E

$$
W(v_N) = \sum_{i=1}^{k} \left( \text{card}(P_i^{(N)}) \cdot \text{card}(A_i^{(N)}) \middle| \text{var } P_i^{(N)} + \text{var } A_i^{(N)} \right. \\
\left. + \text{d}(G(A_i^{(N)}), G(P_i^{(N)})) \right)
$$

9.5 - Performances of the program

Storing space needed :

For the initialisation phase there are two options :

a) to store successively the $P_i^{(0)}$ (as indicated on the organigram) their
size being of the order of $\frac{\text{card } E}{k}$.

b) to store sequentially the data in the central unit twice, the first
time to compute the $G(P_i^{(0)})$, the second time to obtain the kernels
$A_i^{(0)}$ and $\text{var } P_i^{(0)}$ which will be used to compute the criterion for the
cut-off test.

Once the initialisation achieved, the storing of the data is done
sequentially by small lots (the H⁽¹⁾) and the storage space needed is
negligible. It is therefore possible to work on a table of any size
either in using the initialisation a) (in choosing k sufficiently large)
or the initialisation b) (N + 2 sequential storing's of data will take
place, if N is the number of iteration needed for convergence).

## Computing time :

The group of Mr ROUMEGUERE worked out a program which in 7 min
(execution + compilation) on IBM 360-70 achieved the classification of
5000 individuals characterized by 30 parameters in 14 classes and 10
individuals per kernel that were asked for.

## Conclusion :

The SDCM should already permit the processing of large tables.
In a near future, the following direction should be fruitful :

a) the stochastic aspect, especially in the case of infinite tables, in
order, for instance, to define cut-off tests, b) the learning aspect by
calling out labelled individuals during the flow of the algorithm, c) the
on line computing aspect (for keeping up to date nomenclatures for ins-
tance), d) the programming of different variants could perhaps improve
the solutions obtained by changing rooted tree.

To classify allows man to give himself a concise representation
of the universe (in agreement with a limited mind) and to locate any
element according to this representation. It is obvious that man will
have to confront continuously that representation with an objective
reality because of new elements that have to be located. May be, philoso-
phers, psychologists will tell us, some day, if h, field function, g, re-
presentation function and f, location function, allow the representation
in machine of that dialectic and are constituting an approach to three
implicit functions of knowledge.
BIBLIOGRAPHY

( 1 ) . Beale (1969) "Euclidean cluster analysis" Bull I.S.E., 43 Book 2 pp. 92 - 94 (London).

( 2 ) . Benzecri J.P. (1973) "Taxonomie - l'Analyse des Données" (Dunod).

( 3 ) . Benzecri J.P. (1969) "Construction ascendante d'une classification hiérarchique" (L.S.M. I.S.U.P.).

( 4 ) . Benzecri J.P. (1970) "Algorithmes rapides d'agrégation" (sup. class.) (L.S.M. I.S.U.P.).

( 5 ) . Brianne J.P. (1972) "L'algorithme d'échange". Thèse de 3° cycle (L.S.M. I.S.U.P.).

( 6 ) . Cormack R.M. (1971) "A review of classification". The journal of the Royal Statistical Society - serie A vol. 134, part 3.

( 7 ) . Diday E. (1971) "Une nouvelle méthode en classification automatique et reconnaissance des formes : la méthode des nuées dynamiques". Revue de statistique appliquée. Vol XIX n° 2.

( 8 ) . Diday E. (1972) "Optimisation en classification automatique et reconnaissance des formes" RAIRO vol. 3 p. 61 à 96.

( 9 ) . Diday E. (1973) "Introduction à l'analyse factorielle typologique". Rapport Laboria n° 27 (IRIA Rocquencourt (78)).

( 10 ) . Forgey E.W. (1965) "Cluster analysis of multivariate data" ARAS Biometric Society (WNRR) Riverside California USA.

( 11 ) . Gower J.C. and Ross G.J.S. (1969) "Minimum spanning trees and single-linkage cluster analysis". Appl. Stat. 18, 54-64.

( 12 ) . Jardine N. and Sibson R. (1971) "Mathematical Taxonomy". J. Wiley and sons ltd.

( 13 ) . Jambu M. (1972) "Techniques de classification automatique" Thèse de 3° cycle (L.S.M. I.S.U.P.).

( 14 ) . Jancey R.C. (1966) "Multidimensional group analysis" Aust. J. Bot. vol. 14 p. 127.

( 15 ) . Lerman I.C. (1970) "Les bases de la classification automatique" Gauthiers Villars.
( 16 ) . Hall and Ball (1967) "A clustering technique for summerizing multivariate data" Behavioral Science Vol. 12 n° 2.

16 bis. Northouse R.A., From F.R. (1973) "Some results of Non-parametric clustering on large Data Problems". Proc. of the First Int. Joint Conf. on Pattern recognition.

( 17 ) . Mc Queen J. (1967) "Some methods for classification and analysis of multivariable observations". 5th Berkeley Symposium on Mathematical statistics and Probability Vol. 1 n° 1 pp. 281-297.

( 18 ) . Roux M. (1968) "Un algorithme pour construire une hiérarchie particulière". Thèse de 3° cycle (L.S.M. I.S.U.P.).

( 19 ) . Thorndike R.L. (1953) "Who belongs in the family ?" Psychometrika, vol. 18 pp. 267-276.

( 20 ) . Zahn C.T. (1971) "Graph theoretical methods for detecting and describing gestalt clusters" I.E.E.E. Trans. and Comp. vol. C 20 n° 1.
Acknowledgments

---+---+---+---+---+---+

I wish to acknowledge Mr ROUMEGUERRE who gave me the opportunity to realise this work by keeping me informed of the problems presented by large tables at the SNCF (Research department) and gave me the possibility to take advantage of the experience of his group. In this group, I would like to thank especially Mrs BAUDOIN and BARTHELEMY for their advices during this work. I also wish to thank Y. LECHEVALLIER who elucidated a number of criterion associated with the DCM, allowing me to progress more easily for the SDCM (cf. chap. 5). And finally I thank A. SCHROEDER and G. GOVAERT for their intelligent remarks at the time of the find drafting of this manuscript.