# The dynamic clusters method sequentialization in non hierarchical clustering

Edwin Diday

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

## To cite this version:

Edwin Diday. The dynamic clusters method sequentialization in non hierarchical clustering. [Research Report] IRIA-RR-026, IRIA. 1973, pp.16. hal-04715920

HAL Id: hal-04715920

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

Submitted on 1 Oct 2024

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
Eaus: 01987

RR26

RIA
laboria

laboratoire de recherche
en informatique
et automatique

The dynamic
clusters method and
sequentialization in non
hierarchical clustering

E.Diday

16p

Institut de Recherche
d'Informatique
et d'Automatique

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

Rapport de Recherche n°26
août 1973
THE DYNAMIC CLUSTERS METHOD
AND SEQUENTIALIZATION IN
NON HIERARCHICAL CLUSTERING*

E. Diday

Résumé

Etant donné un ensemble fini E ⊂ Rⁿ, il s'agit de détecter les groupes homogènes et bien séparés de E, ainsi que les éléments bien séparés de cet ensemble. Une formulation mathématique originale est donnée. Les algorithmes sont basés sur des groupes de points qui se déplacent à la recherche des formes intéressantes. Nous donnons différents résultats concernant la convergence et la décroissance du critère qui explicite dans le cas d'une distance quadratique.

Nous étudions la séquentialisation de l'algorithmme et il est prouvé que les deux algorithmes (séquenti-
tialisé et non séquentialisé) convergent vers les mêmes solutions. Nous illustrons ces résultats à l'aide
de quelques exemples.

Abstract

Given a finite set E ⊂ Rⁿ, the problem is to find clusters (or subsets of "similar" points in E), and
at the same time to find the most typical elements of this set. An original mathematical formulation
is given to the problem. The proposed algorithm operates on groups of points, called "samplings";
these "samplings" adapt and evolve into interesting clusters. Compared with other clustering
algorithms, this algorithm requires less machine time and storage. We provide some propositions
about non-probabilistic convergence and a sufficient condition which ensures the decrease of the
criterion.

We study a sequentialization of the algorithm and it is proved that both algorithms (sequentialized and non-sequentialized) converge towards the same solutions. Some computational experiments are presented.

<footnote>* This paper has been accepted for presentation and publication at the conference proceedings of the "International Joint Conference on Pattern Recognition", 30 oct.-1 nov. 1973, Washington DC.</footnote>
THE DYNAMIC CLUSTERS METHOD AND
SEQUENTIALIZATION
IN NON HIERARCHICAL CLUSTERING

by

E. Diday

# TABLE OF CONTENTS

## I.- INTRODUCTION

I.1 - The problem

I.2 - The "Dynamic Clusters Method" (D.C.M)

I.3 - Comparison with other techniques

## II.- THE DYNAMIC CLUSTERS METHOD

II.1 - The mathematical formulation of the problem

II.2 - The recursive algorithm

## III.-CONVERGENCE PROPERTIES

## IV.- DISCUSSION ON THE OPTIMALITY OF THE METHOD

IV.1 - The notion of "strong pattern"

IV.2 - Significance of the criterion W.

V.- THE SEQUENTIALIZED DYNAMIC CLUSTER METHOD

VI.- THE COMPUTER PROGRAM

VII.-NUMERICAL EXPERIMENTS

VIII.- CONCLUSION

-BIBLIOGRAPHY -

## I.- INTRODUCTION

### I.1- The problem

In the different life sciences (medicine, biology, archeology, economy, etc...), the specialist often finds himself confronted with a large set of comparable objects where a finite number of parameters represents each object. An important step for the specialist in understanding his data often consists in parti-

tioning this set into "natural" and "homogeneous" groups and finding the most representative elements.

Before we present the mathematical formulation of the problem, let us give some notation : Let $E$ be the set of all the objects. We say that $C = (C_1, ..., C_K)$ is a $K$-partition of $E$, if $C_i \subseteq E$, $U C_i = E$ and $C_i \cap C_j = \emptyset$ ; each $C_i$ is called a category of the partition $C$. A subset $E_i \subseteq E$ is called a "sampling", (usually such that $card(E_i) < card(C_i)$ *). The element $L=(E_1, ..., E_K)$ is called a "K-sampling" of $E$.

This paper presents an approach to the following original problem. Given a certain objective criterion $\Delta$, one must find the $K$-partition and at the same time the $K$-sampling of $E$ which optimizes $\Delta$.

This problem will be expressed under its general form in I.2, but in order to give a preliminary notion of the approach we shall state it approximately as follows :
Given the positive integers $K$ and $n_1, n_2, ..., n_K$. Let $C = (C_1, ..., C_K)$ be a $K$-partition of $E$. Let $L = (E_1, ..., E_K)$ be a $K$-sampling of $C$ such that $card(E_i) = n_i$. Let $D(E_i, C_i)$ be the "degree of similarity" of $E_i$ to $C_i$. If $\Delta(L, C) = \sum_i D(E_i, C_i)$, the problem is to find the pair $(L, C)$ which minimizes $\Delta$. In other words, the partition retained will give the "most representative" samplings in the sense of the degree of similarity used.

**Example 1 :**

Let $E$ be the set of 17 points shown in figure 1.

We have $K = 2$, $n_1 = 3$, $n_2 = 2$ and $D(E_i, C_i) = \sum_{x \in E_i} \delta(E_i, C_i)$

*"card" for cardinal number of the set elements
Σ d(x,y) where d is the Euclidian distance.
y∈C₁

The solution to the problem is given in figure 2, where $E_1$ is formed from the three points designated by "@" and $E_2$ formed from the two points designated by ".". However, simply solving the mathematical problem is not enough, since this solution which optimizes $\Delta$, does not give sufficient precision on "bridge" and groups of objects more or less "solidly" grouped. We shall give an approach to that second problem.

## I.2- The "Dynamic Clusters Method" (D.C.M.)

Our algorithm (D.C.M) can be stated informally as follows: initially K groups of points (the samplings) $E_1^{(0)},...,E_K^{(0)}$ are randomly drawn from the population E, or chosen as representatives of the population. First, we achieve a partition $C = (C_1,...,C_K)$ of E, such that the $C_i$ are formed from the set of elements $x \in E$ such that $D(x,E_i^{(0)}) \le D(x,E_j^{(0)})$. Second, we define new samplings $E_i^{(1)}$ by taking the $n_i$ elements of E closest to $C_i$ in the sense of a certain function $R$; the $n_i$ can be chosen advance or taken proportional to $card(C_i)$. We repeat this procedure until convergence is attained. We shall show that this procedure make the criterion $\Delta$ decrease after each iteration if $R$ is well chosen. Thus, we obtain a local optimum for the mathematical formulation of the problem. This algorithm allows the comparison of the different local optima obtained after various drawings and brings out "fuzzy sets"*(called "strong patterns" and "fringe points").

## I.3- Comparison with other techniques

For the Dynamic Clusters Method (D.C.M.), it is necessary to define, a priori, the number K of categories in the partition we want to obtain. This is an inconvenience in comparison to other methods which do not require the introduction of any a priori parameters. These methods usually give a tree of interesting clusters (cf. Sokhal & Sneath [1963], Johnson [1967], Lerman [1970]). In fact and in practice, it often happens that it is useless to have an exhaustive tree of all possible interesting clusters. Furthermore, the programs written for this purpose have enormous storage requirements, large calculation time and give results which are difficult to interpret, whenever the data exceeds 350 objects.

A specialist may get an idea of the number of K classes by either making a factorial analysis or using a hierarchical clustering method on a sample extracted from the population if it is too large.

Most of the proposed methods of cluster analysis require the computation of the similarity between the objects two by two and the storing of a table of dimension $\frac{N(N-1)}{2}$ where $card(E) = N$. The D.C.M. does not require this table, thus permitting us to work with a much

larger population. Compared with many other techniques the D.C.M. is very fast**For instance, the program using our D.C.M. method obtained a good classification of 1,800 objects (each one characterized by 3 parameters) in 28 seconds on the CDC6600. On the IBM 360/91 with a population of 900 individuals (each one characterized by 35 parameters), the running time was $3^{1/2}$ mn.

No a priori thresholds are required either to find the clusters or to stop the process. Such thresholds are needed in many techniques (cf. Sebestyen G.S. (1966), Bonner, R.E. (1964), Hill D.R. (1967) etc...).

Thus, with a good choice of $R$, the convergence is generally achieved, for D.C.M., in about five iterations. An easily programmable cut-off point permits the selection of this convergence.

The D.C.M. does not show the "chain effect". For example, the two patterns in figure 4 are not recognized because of their proximity. However, by contrast, D.C.M. will have more success with the patterns shown in figure 5, whereas many other techniques (cf. Zahn, C.T (1971), Roux M. (1968) etc...) would tend to consider $C$ closer to $B$ than to $A$, because a chain of points linking $C$ to $B$ exists (the "chain effect"). Taking the notion of admissibility as defined by Fisher, L. and Van Ness J.W. (1971) we can say that the D.C.M. is "convex admissible" and "non connected admissible".

Unlike other many techniques (cf. Mac Queen**(1967), Sebestyen (1966)) the D.C.M. does not depend on the order of introduction of the data, once the initial drawing is fixed.

The principal originality of D.C.M. comes from the use of samplings and the introduction of the $R$ function. This gives results which are different from the "cluster method"(cf. Watanabe (1971), Hall and Ball**(1965)). The advantages are:

- by taking the form of "interesting clusters" (cf. 6.1.1), the samplings elements have a greater efficiency than simple centers of gravity, to detect and represent their respective clusters,

- by using samplings $E_i$ formed from several elements of the population itself, we avoid the artificial effect which would have been produced by the use of the centers of gravity or averages of the samplings (cf. 6.1.2). Also, we have a wide choice for the $D$ functions (e.g $D(x,E_i)$ can be the Mahalanobis **** distance from $x$ to $E_i$ which are of no interest if $card(E_i) = 1$).

- by using the $R$ function, we introduce a great flexibility in the centering of the samplings (cf. example 2),

- Minimizing $\Delta$ results in finding the partition such that each sampling $E_i$ is as close as possible to the category $C_i$. Hence, the samplings obtained, represent the most typical elements of the population.

<footnote>* see Fig. 18</footnote>

<footnote>** cf. appendix 4.</footnote>

<footnote>*** Note also that the notion of average does not make sense for certain kinds of data</footnote>

<footnote>**** cf. appendix 1</footnote>

<footnote>* see Zadeh L.A. (1965).</footnote>
After giving the mathematical formulation of the problem and then stating the algorithm, we shall give a few convergence properties. These properties allow us to point out :

- the importance of the choice of the R function, as far as the convergence is concerned,

- the explanation of the value of the attained results by showing that whatever the choice of the initial samplings, the criterion decreases at each iteration,

- several optimality properties of the solution.

## II.- THE DYNAMIC CLUSTERS METHOD

### II.1.- The problem

We first give the following notation :

- P = {A / A ⊂ E}, (P is the power set of E).

- D a function defined on E x P taking its values in R+. In practice D(x,A) (where x ∈ E and A ⊂ E) express the similarity from x to A.

- L_K = P_1 x P_2 ... x P_K where P_i is the set of subsets of E which have n_i objects. In other words, given integers K and n_1, ..., n_K, L_K is the set of all elements L = (E_1, ..., E_K) where E_i ⊂ E and, card(E_i) = n_i.

- Q_K is the set of all the partitions of E in K classes.

- f a function of L_K on Q_K such that f(L)=C where L = (E_1, ..., E_K) and C=(C_1, ..., C_K): C_i = {x ∈ E / D(x,E_i) ≤ D(x,E_j) for j≠i}, in case of equality x is assigned to the smaller index category.

- Q'_K = {C ∈ Q_K / C = f(L), L ∈ L_K}

- T the set of all the integers k such that 1 ≤ k ≤ K.

- R a function of E x T x L_K on R+. For instance R(x,i,L) = D(x,E_i) / Σ_j D(x,E_j) where L = (E_1, ..., E_K)

- g a function of Q_K on L_K such that g(c)=L with E_i = the n_i elements a ∈ A which minimize R(a,i,P).

- S a function of L_K x L_K on R+ such that S(L,M) = Σ_{i=1}^L Σ_{j=1}^M R(x,i,M).

- Δ a function of L_K x Q'_K on R+ such that Δ(L,f(M)) = S(L,M)

The problem can now be stated as follows : find L* ∈ L_K and C* ∈ Q'_K such that :

$$ \Delta(L^*, C^*) = \inf \{ \Delta(L, C) / L \in L_K, C \in Q'_K \} $$

### II.2.- The recursive algorithm

Let L^{(n)} = (E_1^{(n)}, E_2^{(n)}, ..., E_K^{(n)}) where L^{(n)} ⊂ L_K.

Knowing L^{(n)}, the following three statements explain the computation of L^{(n+1)} ⊂ L_K:

1. Compute D(x, E_i^{(n)}) for all x ∈ E and for all i ∈ {1, 2, ..., K}.

2. Make a partition of E into K categories such that : f(L^{(n)}) = C^{(n)}.

3. Define L^{(n+1)} = g(C^{(n)}).

In other words the elements of E^{(n+1)} are in the "center" of class C_i^{(n)} in the "R meaning".

Let us give some examples in the choice of R.

**Example 2 :**

$$ \text{Let } L = (E_1, \dots, E_K) \in L_K, f(L) = C = (C_1, \dots, C_K), \\ n \ge o \text{ and } R(x, i, L) = \frac{D(x, C_i)}{(D(x, E_i))_n^1} $$

D(x, C_i) has the effect of bringing the elements of E_i toward the center of C_i and D(x, E_i) has the effect of improving the clustering of the elements of each E_i among each other. Note that as n increases, the dispersion of the sampling E_i, in each group C_i decreases while, at the same time, more fully expressing it skeletal pattern. When n→∞ we obtain at the limit R(x,i,L) = D(x,C_i), the effect of which is shown in 6.1.

## III.- CONVERGENCE PROPERTIES

Before stating theorems on convergence, let us give some notation and definitions :

$$ \text{let } E_i = \{e_{ji} \in E / j = 1, 2, \dots, n_i\} \text{ and} \\ L = (E_1, E_2, \dots, E_K) $$

**Definition of an improving element** : x ∈ C_E^* is said to be an "improving" element of E_i in E if there exist a j ∈ {1, 2, ..., n_i} such that R(x, i, L) < R(e_j, i, L), e_ji will be called an "improved" element.

**Definition of a non-biaised element**\*\*: L ∈ L_K is said to be a non-biaised element if g(f(L)) = L.

**Definition of a local optimum**\*\*\*: we shall say that L = (E_1, ..., E_K) ∈ L_K is a local optimum if ∀i ∈ {1, 2, ..., K}, E_i has no improving element.

$$ * C_E^* = \{x \in E / x \notin E_i\} $$

\*\* This name comes from the fact that the samplings corresponding to such an element are in the center (in the meaning of g) of the class they determine (in the meaning of f).

\*\*\* We shall explain in 4 in what way the term "local optimum" is also used.
Equality in $L_K^n$: if $M=(F_1, \dots, F_K) \in L_K^n$, we shall say that $L = M$ if $E_i = F_i \forall i \in \{1, \dots, K\}$

**Definition of convergence**: The sequence $L^{(n)}$ (defined in 2.2) is said to be convergent and $L$ is called its limit if there exist $N$ such that $n>N \Rightarrow L^{(n)} = L$.

**Definition of the sequence** $U_p^n$: $U_p^n = S(L^{(0)}, L^{(0)})$.

If $p$ is even: $p = 2n$, then $U_p^n = S(L^{(n)}, L^{(n)})$.

If $p$ is odd: $p = 2n-1$, then $U_p^n = S(L^{(n)}, L^{(n-1)})$.

Note, that if the sequence $U_p$ decreases then the value of $S$ becomes lower and the value of $\Delta$ too. As we shall show, the D.C.M. allows the decreasing of the sequence $U_n$ until convergence on a local optimum.

**Definition of a square function**:

We shall say that the function $R$ is a **square function** on $E$ if for all $L$, $M \in L_K^n$ we have:

$$S(L,M) \le S(M,M) \Rightarrow S(L,L) < S(L,M).$$

**Example 3**:

Let us give an example of such a function $S$:

let $L, M \in R^+$ and $S(L,M) = L, M$, then:
$$S(L,M) \le S(M,M) \Rightarrow L, M \le M, M \Rightarrow L \le M \Rightarrow L, M \le S(L,L) \le S(L,M).$$

**Example 4**:

Another example : this time of a square function.

Let $R$ be: $R(x,i,L) = D(x, C_i)$ where:

$L = (E_1, E_2, \dots, E_K)$ and $C = (C_1, \dots, C_K) = f(L)$

Under that hypothesis $R$ is a square function (for the demonstration see appendix 2).

Let us now give some results for which the proofs may be found in Appendix 3, or in more detail, together with other results, in Diday E, (1970).

**Theorem 1**:

If the sequence $L^{(n)}$ converges, its limit is a local optimum.

**Theorem 2**:

If the sequence $U_n$ is convergent, then the sequence $L^{(n)}$ converges towards a non-biased element.

**Theorem 3**:

If $R$ is square, the sequence $U_n$ converges and $U_n$ is decreasing.

From these three theorems we can deduce the following:

**Theorem 4**:

If $R$ is a square function, the sequence $L^{(n)}$ converges and its limit is a local optimum.

N.B. That $R$ is a square function is a sufficient but not necessary condition for convergence. In practice, the method is often convergent even if $R$ is not a square function. But, when $R$ is square we are certain that the method converge

IV.- DISCUSSION ON THE
OPTIMALITY OF THE METHOD

IV.1- The notion of "Strong Pattern"

We have used the term "local optimum" with a view to express the following idea : to an element $L \in L_K^n$ with no improving element, corresponds the set of all $L^{(n)}$ sequences which have $L$ for their limit. Now, if $R$ is square, one gets : $S(L^{(n)}, L^{(n)}) > S(L,L)$, therefore $L$ is an optimum with regards to the $X$ part of $L_K^n$ formed by the set of the elements of each of these sequences. There are several reasons* which would lead us to think that $X$ is usually large in $L_K^n$.

Because of this local optimality and the speed of the D.C.M. algorithm, several trials using different values of $L^{(0)}$ can be made ; let $X_i$ be the part of $L_K^n$ with respect to which the attained solution at the $i$th drawing constitute an optimum. If there are $n$ drawings, and if after each drawing, the same group of points appears joined in one of the $K$ classes, this means that this group is compatible with the optimal solution of parts $X_1, X_2, \dots, X_n$ and is therefore representative of the set of all the solutions contained in $X_1, \dots, X_n$**

These considerations allow us to provide the user with an additional tool for the interpretation of his data : he will be able to characterize "strong patterns" which are groups of points which always appear in a same class of each local optimum obtained whatever the choice of $L^{(0)}$. He will also be able to detect the fringe objects by the fact that, for each trial, they fluctuate from one class to another. He can consider each "strong pattern" $A$, as a fuzzy set $f_A$. Let $h$ be the function $R \to \{0,1\}$ such that $h(o) = 1$ and $h(y) = 0$ if $y \ne 0$. Let $x_j$ (resp. $a_j$) be the number of the category in which $x \in E$ (resp. $a \in E$), appears in the partition obtained after $j$th trial. Then a "strong pattern $A$" is a fuzzy set characterized by the function $f_A: E \to [0,1]$ such that:

$$f_A(x) = \frac{1}{n} \sum_{j=1}^{n} h(x_j - a_j).$$

(Note that $f_A(x) = 1$ if $x = A$).

**Example 5**:

Let $E$ be the 8 points of Fig. 6, $K = 3, n_i = 1$, $R$ and $D$ chosen as in example 1. After 4 trials using different values for $L^{(0)}$ we obtain Table 1 where : $j$ is the drawing number, $i$ the point number, case $(i,j)$ of the table contains the number of the class in which the $i$th object appear after the $j$th drawing. From this table we can easily see that subsets $\{1,2,3\}$ and $\{5,6,7,8\}$ are two "strong patterns" while $\{4\}$ is a fringe point.

<footnote>* For more detail, see Diday E. (1972)</footnote>

<footnote>** $U$ signifies union</footnote>

<footnote>*** See Zadeh, L.A. (!965) and Ruspini, E.N. (1970)</footnote>
How can the various solutions be compared? Let U be the limit of the sequence $U_n$ and L that

of the sequence $L^{(n)}$. $S(L^{(n)}, L^{(n)})$ expresses the proximity between $E_i^{(n)}$ and $C_i^{(n)}$ for all

i = 1, 2, ..., K and therefore, the aggregating level of the obtained classes. So, at the limit $S(L, L)$, or "stress", may be considered as a criterion of the validity of the solution obtained and may be used to compare the different partitions resulting from different initial choices of $L^{(0)}$. We note that S decreases at each iteration of the algorithm if R is square as was shown in theorem 3.

## IV.2- Significance of the criterion W

In this section, results of LECHEVALLIER, DIDAY (1973) will be used.

Let $\mu: E \to R^+$ be a measure such that :

$$ \mu(A) = \sum_{a \in A} \mu(a) $$

d is a quadratic distance: $d(x,y) = (x-y)Q(x-y)$

Let us consider now the three following cases :

### a/ Case of a constant ponderation :

$\mu(x)$ is constant, for all x.

Let us take $\mu(x) = 1$, $\forall x \in E$,
then $\mu(A) = \text{card}(A)$, $\forall A \in E$

We also take for D :

$$ D(x,A) = \frac{1}{\sum_{A \in A} \text{card}(A)} \sum_{A \in A} d(x,a) $$

$$ \text{and } R(x,i,P) = D(x,P_i) \times \frac{\text{card}(P_i)}{\text{card}(L_i)} $$

We can then prove that SDCM makes the following criterion decrease :

$$ W(v) = \frac{1}{2} \sum_{i=1}^{k} [\text{card}(P_i) \text{var}(P_i) + \text{var}(L_i) + \text{var}_{Li}(P_i) + \text{var}_{P_i}(L_i)] $$

$$ \forall v \in L_k \text{ x } P_k, v = (L, P) \text{ where } L = (L_1, \dots, L_k) $$

$$ \text{and } \text{Var}_A(B) = \sum_{b \in B} \frac{\mu(b)}{\mu(B)} \text{ d}(b, G(A)) $$

This formula can also be written :

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

### b/ Case of variable ponderation :

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

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

$$ R(x,i,P) = \mu(x) \cdot D(x,P_i) $$

We then can prove that SDCM makes the following criterion decrease :

$$ W(v) = \sum_{i=1}^{k} \mu(P_i)\mu(L_i)[\text{var}(P_i) + \text{var}(L_i) + \text{var}_{Li}(P_i) + \text{var}_{P_i}(L_i)] $$

### c/ The centre of gravity method :

There we take any $\mu$ and $E \subset R^n$.

D, R and g are chosen as follows :

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

$$ - R(x,i,P) = d(s,G(P_i)) $$

$$ - g: P^k \to (R^n)^k: g(P) = L \text{ where } L \text{ is the point of } R^n \text{ that minimizes } R(\cdot, i, P) $$

Then the following criterion decreases :

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

## V.- THE SEQUENTIALIZED DYNAMIC CLUSTER METHOD

Among the methods of clustering, DCM may be classified in a field of procedure that has been called "iterative relocation procedure" by some authors as CORMACK (1971), WISHART (1971), and "K-means", "cluster centres" by others as MC. QUEEN (1967), WATANABE (1972).

These various methods start from K points that are drawn either at random (MC.QUEEN (1967)) or among the population* (HALL and BALL (1965)). These K points are chosen as initial centres, all the points are then allocated to the nearest centres according to one of the two following techniques :

A) The K centres may be changed when each point is allocated (THORNDIKE (1953), MC.QUEEN (1967), BEALE (1969), WISHART (1971)). When a point is added to a group, the mean of that group is adjusted in order to take the new point into account. This mean usually defines the new centre (MC. QUEEN (1967)).

B) The K centres may be changed when all points are allocated (HALL and BALL (1965), FORGEY (1965), JANCEY (1966)). The average of each group is computed and this point is used as a new cluster centre.

Finally, the whole population is iteratively relocated several times as well with the technique A) (BEALE (1969), WISHART (1971)) as with the technique B). The process stops when a fixed number of iterations has occured, when it converges, or when an oscillation occurs.

The technique A) has the advantage that data may be sequentially entered into the memory. This is convenient, from a computing point of view, for large data tables, by reducing

* Other variants for the initial centres choice are proposed by THORNDIKE (1953), JANCEY (1966), KENNARD and STONE (1969), E. DIDAY (1970)
memory requirements. On the other hand, the technique B) saves computing time because for one entry of the population E, K centres are to be computed while technique A) computes card (E) centres. Computational experiments seem to prove that the number of iterations is approximately the same for both techniques.

As we have previously stated, the DCM may be considered as a generalization of technique B) by taking "multi-centres" (the samplings) instead of only one centre and by using the R function for the centering.

In the same way, technique A) may be generalized by the using multi-centres and the R function to obtain the "Sequentialized Dynamic Cluster Methods" (S.D.C.M.).

Let us now give the following notation we need to define the S.D.C.M.

## V.1- Notations

$\mathbb{L}_k = \{(A_1, A_2, ..., A_k)/A_i \subseteq E\}$, where B depends on variants of the method.

$\mathbb{P}_k$ is the set of all partitions of E in k classes.

$Q \in \mathbb{P}_k$ will be written : $Q = (Q_1, ..., Q_k)$

$F$ : $\mathbb{P}_k \times E \times \mathbb{L}_k \rightarrow \mathbb{P}_k$ is given by :

$F(Q, x, L) = P$ where $P = (P_1, ..., P_k)$ is defined as follows :

Let j be so that : $x \in Q_j$, then there are two possibilities :

a/ $\exists i : D(x, L_i) \subset D(x, L_j)$ - with $j < i$ in case of equality, then $P \equiv Q$.

b/ $\exists i : D(x, L_i) < D(x, L_j)$ then :

$$P_i = Q_i \cup \{x\}$$

$$P_j = Q_j - \{x\}$$

and $P_n = Q_n, \forall n \neq i, n \neq j$ and $n \in \{1, 2, ..., k\}$

R' : $E \times T \times M_k \rightarrow R^+$

g : $\mathbb{P}_k \rightarrow \mathbb{L}_k$ is given by : $g(P)=L=(A_1, ..., A_k)$ where $A_i = \{ \text{the } n_i \text{ elements of B that minimize } R'(x, i, P) \}$

S : $\mathbb{L}_k \times \mathbb{P}_k \rightarrow R^+$ : $S(L, P) = \sum_{i} \sum_{x \in A_i} R'(x, i, P)$

We note $V_k = \mathbb{L}_k \times \mathbb{P}_k$.

W : $V_k \rightarrow R^+$ : $W(v) = S(L, P)$ if $v = (L, P)$

## V.2- The algorithm of the sequentialized Dynamic clusters Method (S.D.C.M.)

Starting from $P^{(0)}, L^{(0)} = g(P^{(0)})$ is deduced and therefore : $v_o = (L^{(0)}, P^{(0)})$.

The data are given in any order and we note $x^{(i)}$, the i-th element ; if $i = \text{card}(E)$, then $x^{(i+1)} = x^{(0)}$, and more generally, if r is the remainder in the division of i by card(E), we have : $x^{(i)} = x^{(r-1)}$.

$v_{n+1}$ is defined from $v_n$ as follows :

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

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

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

## V.3- Convergence of the algorithm and identity between DCM and SDCM

Let $v = (L, P) \in V_k$

and $M \in \mathbb{L}_k$

**Definition R'** will be said to be **square**, if :

$$S(L, P) \leq S(M, P)$$

implies : $S(L, F(P, y, L)) \leq S(L, P)$

for all $v, M$ and $y$.

The proof of the two following results may be found in appendix 4.

**Theorem 5 :**

If R' is square, the sequence $u_n$ converges and decreases, and the sequence $v_n$ converges.

**Theorem 6 :**

The algorithm of the Dynamic Clusters method and the algorithm of the sequentialized Dynamic Clusters method converge towards the same set of solutions.

## VI.- THE COMPUTER PROGRAM*

If N is the number of objects and M the number of measures on each object, the storage space used is about N.M + 5N.

The short execution time of the program may be explained by the fact that the algorithm requires only the computation of $D(x, E_i)$ and of $R(x, i, L)$ for $x \in E$ and $i = 1, 2, ..., K$.

Thus, we can see that if D is well chosen (see appendix I for an example) it will be fruitless to compute the similarities of the objects two by two. It saves the storage of an

$\frac{N(N-1)}{2}$ array (where N is the number of objects to be classified) and it also saves an appreciable amount of computing time. We remark, since only the $n_i$ smallest values of $R(x, i, L)$ for $x \in E$ are used, that the program does not need to compute all the $R(x, i, L)$ for all $i=1, 2, ..., K$ and all $x \in E$. For similar reasons, we do not need the computation of all the $D(x, E_i)$.

How to choose $n_i$ and $L^{(0)}$ :

<footnote>* This program is available at I.R.I.A. Rocquencourt 78 (France)</footnote>
If the user does not have sufficient knowledge of his data to make a choice of the first samplings, then he will take

vi, $n_i = \frac{1}{c} \frac{\text{card}(E_i)}{k}$. This means, essentially, that each group may be characterized by its $c^{th}$ part. $L^{(o)}$ will then be drawn randomly.

A simple test indicates when the algorithm has converged, i.e. when $U_{n+1} = U_n$. The program therefore stops computing when

$$1 - \frac{U_n}{U_{n+1}} < \epsilon \text{ where } \epsilon \text{ is within the computer precision range.}$$

Let us now give the input and output of the program :

### Input

- The data matrix

- The maximum number of classes wanted : K.

- $n_1, n_2, \dots, n_K$.

- $L^{(o)}$ can be chosen randomly from the population by the program, or optionally specified by the user.

### Output

- The samplings $E_1^{(H)}, \dots, E_K^{(H)}$ where H is the number of iterations required for convergence.

- The partition obtained : $(C_1^H, C_2^H, \dots, C_K^H)$

- The stress for the whole partition

$U_H = \lim U_n = S(L_1^{(H)}, L_2^{(H)})$ and the stress for each class obtained : $\sum_{x \in C_i^H} R(x, i, L_1^{(H)})$.

- Optionally: The values taken by the function $f: C_i^H(x) = D(x, F_i^{(H)}) / \text{Max } D(y, E_i^{(H)})$ which characterize each fuzzy set $C_i^H$.

## VII.- NUMERICAL EXPERIMENTS

### VII.1- Two artificial examples

VII.1.-1- The problem consists in searching the forms described by 283 points in the plane. We have used the following input :

$K = 2, n_1 = n_2 = 40, R(x, i, L) = D(x, C_i)$ where D is Mahalanobis distance [see Mahalanobis, P.C. (1936) or Sebestyen, G.S. (1962)]

Fig. 7 shows the 283 points; the 40 points of $E_1^{(o)}$ are represented by "o" and those of $E_2^{(o)}$ are represented by x. These 80 points have been obtained from a random drawing. Fig. 8 shows the samplings obtained at the end of the first iteration. Fig. 9 shows the samplings obtained at convergence. The two patterns that the eye recognized initially have been found automatically. The importance of the samplings, which work as a "skeleton" or "discrete factorial axis" for each of the recognized pattern, is seen. By taking the $n_i$

too small, or only the center of gravity, the recognized forms would have been "rounded up" and it would not have been possible to recognize these elongated forms.

VII.1.2- We have applied our method to an artificial example proposed by Ruspini, E.H. (1970), see Fig. 11. First, this enables us to observe that the D.C.M. is within the order of 10 to 15 times faster than Ruspini's method. The D.C.M. has been used with $K = 4$, $n_1 = n_2 = n_3 = n_4 = 5$, $R(x, i, L) = D(x, C_i) = \sum_{y \in C_i} d(x, y)$ where d is the Euclidian distance. The histogram shown in Fig. 10 gives an idea of the distribution function of the various solutions obtained from 50 random drawings ** of the starting samplings. The value $U = \lim_{n \to \infty} U_n$ for each solution is represented on the x axis (the convergence is generally reached after 4 iterations). The solution which shows up most frequently is that giving the four best classes; the value of U corresponding to this solution is clearly smaller than for the other solutions, which shows, indeed, that this is the best partitioning. The solutions which appear the most frequently are indicated Figs. 12, 13, 14 and 15. From these solutions, we obtain 4 "strong patterns" which correspond exactly to the 4 categories of the best solution. Taking $K = 3, K = 5$, using "strong patterns" the same 4 best categories are easily found, as for $K = 4$.

### VII.2- Numerical experiment on the Fisher Data

The well known data of Fisher, R.A. (1936) are listed in table 2; this table gives measurements on two varieties of iris. We have used the D.C.M. with $K = 2, n_1 = n_2 = 20, R(x, i, L) = D(x, C_i)$ where D expresses the $\chi^2$ distance (see Appendix 1). In table 3, the totality of the obtained results are found.

By making other runs with the same data taking $n_1 = n_2 = 10$ and then $n_1 = n_2 = 30$, we have obtained essentially the same results with the same missclassified 6 or 7 iris. Fig. 16 gives an example of the values taken by the $U_n$ series.

### VII.3- Variation of the IBM 360/91 machine time with respect to number of objects to classify.

The experiment has been carried out on a population in which each object was characterized by 35 parameters. $K = 7$ and $n_i = \frac{1}{10} \frac{\text{card } E_i}{7}$ have been used, the convergence was generally obtained after 5 iterations. The number of required iterations has been limited to five. The results obtained are shown in Fig. 17.

## CONCLUSION

The Dynamic Clusters Method is of interest because of the original manner in which the problem is stated, the algorithm which is proposed to solve it, the convergence properties

* As in Ball and Hall method for example

* The execution time has been 3 min on the C.I.I. 10.070 to get the whole of the 50 solutions.
the amount of information which it brings to the user, the value of the obtained results, its efficiency from the point of view of machine time and storage space, and finally, because of numerous applications in different life sciences*. For all of these reasons, it appears desirable to us that research be continued in this field, notably in the choice of the function R for sampling problems and in finding a deeper characterization of square functions, local optimality and "strong patterns".

## Acknowledgements

This work has been carried out at the "Institut de Recherche en Informatique et Automatique". (IRIA)

The author wishes to thank Prof. Simon for his encouragement and advice on this work, Dr Donio who gave me the opportunity to do this study and Dr J. Moloney and Dr H. Vandenburgh for their aid in the translation.

## BIBLIOGRAPHY

- Ball, Geoffrey H. and Hall, David J. 1965, "ISODATA - a novel Method of Data Analysis and Pattern Classification" Technical Report, SRI Project 5533, Stanford Research Institute, Menlo Park, Calif. U.S.A.

- Benzecri, J.P. 1969, "Legons sur la reconnaissance des Formes". Laboratoires de Statistique de la Faculté des Sciences de Paris au Quai St-Bernard.

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

- Bonner R.E. 1964. "On some clustering techniques" IBM Journal of Research and Development.

- Diday, E. 1970 "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.

- Diday, E. 1970 "La méthode des nuées dynamiques et la reconnaissance des formes. Cahiers de l'IRIA.

- Diday, E. 1971, "Optimisation en classification automatique non-hierarchique". A Available at IRIA.

- Fisher L., Van Ness, J.W. 1971, Admissible clustering procedures Biometrika 58,1, p.91.

- Fisher, R.A. 1936, The use of multiple measurements in taxonomie problems, Ann, Eugenics 7, 179.

- Forgey, E.W. 1965, "Cluster analysis of multivariate data". AAAS-Biometric Society (WNAR), Riverside, California, U.S.A.

- Gitman, I. 1970. Dept. of Electrical Engineering, Ph. D. Thesis. Mc. Gill University Canada.

- Hill, D.R. 1967, "Mechanized Information Storage, retrieval and dissemination", Proceedings of the F.I.D./I.F.I.P. Joint conference Rome.

- Jancey, R.C. 1966, "Multidimensionnal Group Analysis". Aust. J. Bot. vol 14, p. 127.

- Johnson, S.C. 1967, "Hierarchical clustering schemes". Psychometrica 32, 241-45.

- Kennard, R.W. and Stone, L.A. 1969. Computer aided design of experiments technometrica, 11, 137-148.

- Lerman, H. 1970, "Les bases de la classification automatique". Gauthier-Villars Editor.

- Mac Queen James 1967, "Some methods for classification and analysis of multivariable observations", 5th Berkeley Symposium on Mathematics, Statistics and Probability, vol 1 N° 1 pp. 281-297.

- Nagy, G. 1968, "State of the art in pattern recognition" Proc. IEEE.56, pp. 836-882.

- Roux, M. 1968, "Un algorithme pour construire une hiérarchie particulière". Thèse de 3ème cycle. Laboratoire de statistique Mathématique Faculté des Sciences de Paris.

- Ruspini, E.H. 1970, "Numerical Method for Fuzzy Clustering". Information Sciences 2 pp. 319-350.

- Sebestien, George S. 1962, "Decision-Making Process in Pattern Recognition". Néw-York : The MacMillan Co.

- Sokal, RR and Sneath, P.H.A., 1963, "Numerical Taxonomy", W.H. Freeman and Co., San Francisco and London.

- Thorndike, R.L. 1953, "Who belongs in the family?" Psychometrika. Vol. 18, p. 267-276.

- Watanabe, S. 1971, "A unified view of clustering Algorithms". IFIP Congress 71, Booklet TA-2, pp. 64-69.

- Wishart, D. 1971, Some problems in the theory and application of the methods of numerical Taxonomy. Ph. D. Thesis (1971). University of St. Andrews.

- Zadeh, L.A. 1965, "Fuzzy sets". Information and Control 8, pp. 338-353.

- Zahn, C.T. 1971, "Graph Theoretical Methods for detecting and describing gestralt clusters". I.E.E.E. Transactions on computers Vol. C-20 N° 1 January.

- Lechevallier, Y., Diday, E. 1973, "Etude de critères optimisés par la méthode des nuées dynamiques". IRIA - Rocquencourt.

## APPENDIX I

$$ \text{Distance of } \chi^2 $$

Let us consider N subjects, characterized by M measures

$o(i,j)$ is the $j^{th}$ measure on the $i^{th}$ object.

<footnote>* In particular an investigation on the demography of Lebanon by IRFED (Institut de Recherche Français d'Etudes Démographiques, Paris)(1970), an investigation on medical data carried out in collaboration with Pr Sandor at the "Institut Pasteur" and a geological study for the B.R.G.M. (Bureau de Recherche Géologique et Minier Tour) (1971).</footnote>
If E is the set of the objects, we will note :

$$ \rho(j) = \sum_{i} \rho(i, j) $$

$$ \rho(i) = \sum_{j} \rho(i, j) $$

$$ \rho(j/i) = \frac{\rho(i, j)}{\rho(i)} $$

$$ \rho(G) = \sum_{i \in G} \rho(i) \text{ where } G \subset E $$

$$ \rho(j/G) = \frac{1}{\rho(G)} \sum_{i \in G} \rho(i, j) $$

Then D is defined by :

$$ D(i, G) = \sum_{j=1}^{M} \frac{1}{\rho(j)} [\rho(j/i) - \rho(j/G)]^2 $$

For further information about this distance, see Benzecri (1969).

## Mahalanobis distance

$D(x, E_i) = (x - y_i)^{-1}(x - y_i)^T$, where Q is the covariance matrix of $E_i$ and $y_i$ is the average point of $E_i$.

# APPENDIX 2

## Proposition

Let d be a symmetric function of $E \times E \to R^+$ and D such that :

$$ D(x, A) = \sum_{y \in A} d(x, y). \text{ Let R be :} $$

$$ R(x, i, L) = D(x, C_i) $$

where : $L = (E_1, ..., E_K)$

and $f(L) = C = (C_1, C_2, ..., C_K)$. Then R is a square function.

## Proof

Let $M \in L_K$ be such that $M = (F_1, ..., F_K)$ where $F_i \in P_i$.

We have :

$$ \sum_{i=1}^{K} \sum_{x \in E_i} D(x, C_i) = \sum_{i=1}^{K} \sum_{x \in E_i} \sum_{y \in G_i} d(x, y) $$

$$ \sum_{i=1}^{K} \sum_{x \in E_i} \sum_{y \in G_i} d(x, y) $$

where $f(M) = G = (G_1, ..., G_K)$. On the other hand, we have :

$$ S(L, M) = \sum_{i=1}^{K} \sum_{x \in E_i} D(x, C_i) = \sum_{i=1}^{K} \sum_{x \in E_i} \sum_{y \in C_i} d(x, y) $$

As d is symmetrical we have :

$$ S(L, M) = \sum_{i=1}^{K} \sum_{y \in G_i} D(y, E_i) \quad (1) $$

$$ S(L, L) = \sum_{i=1}^{K} \sum_{y \in C_i} D(y, E_i) \quad (2) $$

The same y element can appear in (1) under the form $D(y, E_j)$ and in (2) under the form $D(y, E_i)$ but by the construction of $C_i$, we have necessarily :

$d(y, E_i) \le d(y, E_j)$. As each y element appears once and only once in (1) and (2) and as G and C form a partition of E, the same reasoning applies $\forall y \in E$; therefore : $S(L, L) \le S(L, M)$. Thus R is square.

q.e.d

We note, although it is not used in the proof, that

$$ S(M, M) = \sum_{i=1}^{K} \sum_{y \in G_i} d(y, F_i) \ge S(L, M). $$

# APPENDIX 3

## Theorem 1

If the sequence $L_n$ converges, its limit is a local optimum.

## Proof

Let L be the limit of the sequence $L_n$. By definition of the convergence in $L_K$, we know that an N exists such that $L_n = L \ \forall n > N$.

For $n > N$ we therefore have : $L_n = L_{n+1}$, that is to say, $E_i^{(n+1)} = E_i^{(n)}$ $i = 1, 2, ..., K$.

This explains that $E_i^{(n)}$ has no improving element, in fact, should $E_i^{(n)}$ have one then : $\exists x \in E_i^{(n)}$ and $j \in \{1, 2, ..., n_K\}$ such that

$$ R(x, i, L^{(n)}) < R(e_{ji}^{(n)}, i, L^{(n)}) \text{ where } E_i^{(n)} = \{e_{ji}^{(n)} / j = 1, 2, ..., n_K\} $$

The $n_i$ elements of E which make R as small as possible would contain x and, thus, we would have $E_i^{(n+1)} \ne E_i^{(n)}$. We can use similar reasoning for all i and thus show that L is truly the local optimum.

q.e.d.

## Theorem 2

If the sequence $U_n$ converges then the sequence $L_n$ converges.

## Proof

Let U be the limit of the sequence $U_n$. We will
show first that this limit is attained if $U_n$ converges. In other words, that there exists an $N$ such that $n > N$, $U_n = U$; the set $W$ of values taken by $S(L,M)$, for all $L$ and $M \in L_K$, is finite since $L_K$ is finite. Let $\epsilon_1$ we have : $\forall n > N_1$, $U_n \in$

From the choice of $\epsilon_1$, we can have only one point $t \in W$ in the interval $[U - \frac{\epsilon_1}{2}, U + \frac{\epsilon_1}{2}]$. Suppose $t \neq U$ and let $\epsilon$ be the distance between this point and $U$, we know that there exists an $N$ such that $\forall n > N$ we have $U_n \in$

$[U - \frac{\epsilon}{2}, U + \frac{\epsilon}{2}]$. This is not possible since $U_n^2 \in W \cap U$ and we have assumed that $t$ is the only point of $W$ in $[U - \frac{\epsilon}{2}, U + \frac{\epsilon}{2}]$. The only possibility is that $t = U$. Therefore we have shown that there exists $N_0 : \forall n > N_0$, $U_n = U$.

Suppose that there exists an $N > N_0$ such that $L^{(n)} \neq L^{(n+1)}$; this means that there exists an $i$ such that $E_i^{(n)}$ contains at least one improving element $x$. Then

$$U_{2N} = S(L^{(n)}, L^{(n)}) > S(L^{(n+1)}, L^{(n)}) = U_{2N+1}$$

since the new terms in $S(L^{(n+1)}, L^{(n)})$ come from the improving element $x$ which imposes inequalities of the form

$$R(e_{ji}^{(n)}, i, L^{(n)}) > R(x, i, L^{(n)})$$

Thus we would have $U_{2N+1} < U_{2N}$ which is not possible since $2N > N_0$. Hence, there exists no $N > N_0$ such that $L^{(N)} \neq L^{(N+1)}$ from which we have $\forall n > N_0$, $L^{(n)} = L^{(n+1)}$. Thus $L^{(n)}$ converges.

q.e.d.

### Theorem 3

If $R$ is square, the sequence $U_n$ converges and $U_n$ is decreasing.

### Proof

It is sufficient to show first for $p$ even and then for $p$ odd that $U_{p+1} < U_p$.

Let $p = 2n$ then $U_p = S(L^{(n)}, L^{(n)})$. We have the following two cases :

1. For all $i \in \{1, 2, ..., K\}$, $E_i^{(n)}$ has no improving element, then

$$S(L^{(n+1)}, L^{(n)}) = S(L^{(n)}, L^{(n)}) \text{ which implies } U_{p+1} = U_p$$

2. If such that $E_i^{(n)}$ has at least one improving element; then $U_{p+1} < U_p$ since each element $x$ of $E_i^{(n+1)}$ which is not in $E_i^{(n)}$ is such that

$$R(x, i, L^{(n)}) \le R(e_{ji}^{(n)}, i, L^{(n)})$$

So if $p$ is even, we have necessarily $U_{p+1} \le U_p$. Now let $p = 2n - 1$; since $p - 1$ is even, from the above we have $U_p < U_{p-1}$ from which we obtain $S(L_n, L_{n-1}) \le S(L_{n-1}, L_{n-1})$. Since $R$ is square, we have $S(L_n, L_n) \le S(L_n, L_{n-1})$ which implies $U_{p+1} < U_p$. Thus, since we have shown that the sequence $U_p$ is decreasing and as it is bounded from below by 0, it converges.

q.e.d.

## APPENDIX 4

### Theorem 5

If $R$ is square, the sequence $u_n$ converges and decreases, and the sequence $v_n$ converges.

### Proof

$$\text{Let } v_n = (L^{(n)}, P^{(n)}), \text{ then}$$

$$W(v_n) = S(L^{(n)}, P^{(n)}) \text{ and therefore :}$$

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

If $z_n = S(L^{(n+1)}, P^{(n)})$, then, necessarily :

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

because $A_i^{(n+1)}$ is the set of the $n_i$ elements of $B$ that minimize $R(\cdot, \cdot, P^{(n)})$, and because $A_i^{(n)} \subset B$.

Therefore :

$$z_n = S(L^{(n+1)}, P^{(n)}) \le S(L^{(n)}, P^{(n)}) = u_n$$

As $R$ is square, if $P^{(n)} = F(P^{(n-1)}, x^{(n-1)}, L^{(n-1)})$

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

Then : $S(L^{(n+1)}, P^{(n+1)}) \le S(L^{(n+1)}, P^{(n)})$, which implies $u_{n+1} \le z_n \le u_n$,

As the sequence $u_n$ is positive, it converges decreasingly. Moreover, it reaches its limit since it can only take a finite number of values.

The convergence of sequence $v_n$ is proved as follows :

Let $u_N$ be the limit of sequence $u_n$, there exists $V_N$ as : $u_N = W(V_N)$ since $u_n$ reaches its limit. If there was an integer $m$ such that $m > N$ and $V_m \ne V_N$, then it would exist an improving element and we would have $U_m < U_N$, which is impossible.

q.e.d.
## Theorem 6

The algorithm of the dynamic clusters method and the algorithm of the Sequentializes Dynamic Clusters method converge towards the same set of solutions.

## Proof

DCM basic algorithm necessarily converges to a non-biaised element (cf. appendix 1). We shall prove that it is also true for SDCM. Let $V_N = \lim_{n \to \infty} v_n$, and let m be the smallest integer multiple of card(E) which is bigger than N.

For all $i \in \{0, 1, ..., card(E)\}$, we have : $V_m = V_{m+i}$, which implies :

$$P^{(m)} = P^{(m+i)} = F(P^{(m)}, x^{(i)}, L^{(m)})$$

According to the definition of F, we can infer that :

$x^{(i)} \in P_j^{(m)}$ implies $D(x^{(i)}, A_j^{(m)}) \le D(x^{(i)}, A_n^{(m)})$ (with $j < n$ in case of equality).

Therefore : $f(L^{(m)}) = P^{(m)}$ (by definition of f - cf. appendix 1).

Moreover, $L^{(m)} = L^{(m+1)} = g(P^{(m)})$ since $V_m = V_{m+1}$.

As $f(L^{(m)}) = P^{(m)}$ and

$L^{(m)} = g(P^{(m)})$, $(L^{(m)}, P^{(m)})$ is a non-biaised element. Reciprocally, any non-biaised element $v$ can be considered as a limit of the sequence $V_n = V$, and that is true for both methods.

q.e.d.

<figure><img src="image_3.png" /><figcaption>Figure 1</figcaption></figure>

The set on which the clusters are searched.

<figure><img src="image_4.png" /><figcaption>Figure 2</figcaption></figure>

The solution of the problem is given by $C_1, C_2$ and the two samplings designated by "$*$" and "$o$".

<figure><img src="image_5.png" /><figcaption>Figure 3 a.</figcaption></figure>

The points "$*$" show elements to be classified and the point "$o$" represents the center of gravity of these five elements.

<figure><img src="image_6.png" /><figcaption>Figure 3 b.</figcaption></figure>

The three elements which are the nearest of the five elements are represented by the points "$*$"; the center of gravity of these three elements reduces the effect of the marginal point.

<figure><img src="image_7.png" /><figcaption>Figure 4</figcaption></figure>

D.C.M. is not appropriate for recognizing these two distinct patterns.

<figure><img src="image_8.png" /><figcaption>Figure 5</figcaption></figure>

D.C.M. does not show the chain effect.

<figure><img src="image_9.png" /><figcaption>FIGURE 6.
The set on which clusters are searched</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>TABLE 1.</figcaption></figure>

Clusters of Fig.6 obtained by using D.C.M. after 4 trials of $L^{(o)}$.
<figure><img src="image_11.png" /><figcaption>FIGURE 7.</figcaption></figure>

The points "+" designate the set on which clusters are searched

The points "b" designate the trial of the sampling $k_1^{(0)}$

The points "*" designate the trial of the sampling $k_2^{(0)}$

<figure><img src="image_12.png" /><figcaption>Figure 8</figcaption></figure>

Results obtained
after the first
iteration of the
D.C.M. algorithm

<figure><img src="image_13.png" /><figcaption>FIGURE 10</figcaption></figure>

The value $f = 0.5$ corresponds to the solution illustrated in Fig. 12
$f = 2.11$ corresponds to the solution illustrated in Fig. 13
$f = 2.22$ corresponds to the solution illustrated in Fig. 14
$f = 3.817$ corresponds to the solution illustrated in Fig. 15

Figure 9
Results obtained at convergence (second iteration)
The two patterns have been recognized.

Line separating the two
classes which have been
recognized by the method.
<figure><img src="image_14.png" /><figcaption>FIGURE 12</figcaption></figure>

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

The dotted lines indicate the categories obtained.

<figure><img src="image_16.png" /><figcaption>FIGURE 14</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>FIGURE 15</figcaption></figure>

<figure><img src="image_18.png" /></figure>
<figure><img src="image_19.png" /><figcaption>FIGURE 17</figcaption></figure>

Values taken by the $U_k$ series during the successive iterations.

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

Execution time vs number of objects for the D.C.M. (Dynamic Clusters Method)

<caption>FIGURE 18</caption>

n = number of the trial of L⁽⁰⁾

H = number of iterations until convergence

A = First class obtained

B = second class obtained

+ = iris virginica

- = iris versicolor

Classification
obtained at convergence

<table><thead><tr><th rowspan="2">n</th><th rowspan="2">H</th><th rowspan="2">Values of U</th><th colspan="3">A</th></tr><tr><th>44</th><th>47</th></tr></thead><tbody><tr><td rowspan="2">1</td><td rowspan="2">3</td><td>U<sub>1</sub> = 3.4581.10<sup>-5</sup></td><td>A</td><td>4</td><td>3</td></tr><tr><td>U<sub>5</sub> = U<sub>6</sub> = 2.4729.10<sup>-6</sup></td><td>B</td><td>4</td><td>47</td></tr><tr><td rowspan="2">2</td><td rowspan="2">5</td><td>U<sub>1</sub> = 4.0122.10<sup>-5</sup></td><td>A</td><td>3</td><td>46</td></tr><tr><td>U<sub>9</sub> = U<sub>10</sub> = 2.4729.10<sup>-6</sup></td><td>B</td><td>47</td><td>4</td></tr><tr><td rowspan="2">3</td><td rowspan="2">4</td><td>U<sub>1</sub> = 2.8610.10<sup>-5</sup></td><td>A</td><td>46</td><td>3</td></tr><tr><td>U<sub>3</sub> = U<sub>6</sub> = 2.4769.10<sup>-6</sup></td><td>B</td><td>4</td><td>47</td></tr><tr><td rowspan="2">4</td><td rowspan="2">3</td><td>U<sub>1</sub> = 2.0040.10<sup>-5</sup></td><td>A</td><td>4</td><td>3</td></tr><tr><td>U<sub>5</sub> = U<sub>6</sub> = 2.4769.10<sup>-6</sup></td><td>B</td><td>46</td><td>47</td></tr><tr><td rowspan="2">5</td><td rowspan="2">3</td><td>U<sub>3</sub> = 20610.10<sup>-5</sup></td><td>A</td><td>46</td><td>3</td></tr><tr><td>U<sub>5</sub> = U<sub>6</sub> = 2.4789.10<sup>-6</sup></td><td>B</td><td>4</td><td>47</td></tr><tr><td rowspan="2">6</td><td rowspan="2">5</td><td>U<sub>1</sub> = 1.9690.10<sup>-5</sup></td><td>A</td><td>46</td><td>3</td></tr><tr><td>U<sub>5</sub> = U<sub>6</sub> = 2.4789.10<sup>-6</sup></td><td>B</td><td>4</td><td>47</td></tr><tr><td rowspan="2">7</td><td rowspan="2">6</td><td>U<sub>1</sub> = 1.9736.10<sup>-5</sup></td><td>A</td><td>3</td><td>46</td></tr><tr><td>U<sub>11</sub> = U<sub>12</sub> = 2.4729.10<sup>-6</sup></td><td>B</td><td>47</td><td>4</td></tr><tr><td rowspan="2">8</td><td rowspan="2">3</td><td>U<sub>1</sub> = 2.3672.10<sup>-5</sup></td><td>A</td><td>46</td><td>3</td></tr><tr><td>U<sub>5</sub> = U<sub>6</sub> = 2.4733.10<sup>-6</sup></td><td>B</td><td>4</td><td>47</td></tr><tr><td rowspan="2">9</td><td rowspan="2">3</td><td>U<sub>1</sub> = 2.6293.10<sup>-5</sup></td><td>A</td><td>1</td><td>45</td></tr><tr><td>U<sub>5</sub> = U<sub>6</sub> = 2.4014.10<sup>-6</sup></td><td>B</td><td>49</td><td>5</td></tr><tr><td rowspan="2">10</td><td rowspan="2">3</td><td>U<sub>1</sub> = 6.1333.10<sup>-5</sup></td><td>A</td><td>45</td><td>1</td></tr><tr><td>U<sub>5</sub> = U<sub>6</sub> = 2.4014.10<sup>-6</sup></td><td>B</td><td>5</td><td>49</td></tr></tbody></table>

Results obtained by D.C.M. on Fisher's data after
10 trials of L⁽⁰⁾

<caption>TABLE 3</caption>