Rappel sur les classifications
Les classifications traditionnelles de l'Analyse des
Données sont les CAH (Classifications Hiérarchiques
Ascendantes) c'est à dire des méthodes qui partent de
classes réduites aux individus isolés pour construire
des classes contenant de plus en plus d'individus. Le
regroupement d'individus ou de classes pour former une
nouvelle classe est binaire et se fait suivant un
critère d'agrégation. Les distances entre les anciennes
et la nouvelle classe sont alors mises à jour selon une
formule de recalcul. Le poin t de départ de la
classification n'est pas ici le tableau des données
brutes mais une matrice de distances construite à partir
de ce tableau, souvent par exemple celle des distances
induites par une Analyse Factorielle (Composantes
Principales, Correspondances) du tableau de données.
Nous commencerons par expliciter sur un exemple ces
différentes opérations avant de les programmer
progressivement. Supposons, donc, qu'on désire
effectuer une classification sur 6 éléments nommés
A,B,C,D,E,F. L'étape initiale consiste à mettre chacun
des éléments dans une classe, soit :
Classe 1 : A
Classe 2 : B
Classe 3 : C
Classe 4 : D
Classe 5 : E
Classe 6 : F
Il faut ensuite munir ces classes d'une matrice de
distances. Comme celle-ci peut être construite sur des
critères biologiques, résulter d'analyses préliminaires
etc. ; nous supposerons ici qu'elle nous est donnée par
le tableau
A B C D E F
A 0
B 9 0
C 7 4 0
D 7 4 2 0
E 5 3 5 5 0
F 5 1 3 4 7 0
Ce tableau est symétrique et nous n'en donnons donc que
sa partie triangulaire inférieure. Pour simplifier les
calculs, nous prendrons comme critére d'agrégation la
valeur minimale des distances et comme formule de
recalcul l'arrondi entier de la distance moyenne (non
pondérée). Sous ces termes techniques se cachent les
calculs les plus simples et "na‹fs" possibles. Cela
signifie pour notre matrice que la première agrégation
doit être faite pour la plus petite distance. Il s'agit
ici de la distance 1 entre B et F.
Nous définissons donc la classe 7 : BF (obtenue pour la
distance 1). Le nouveau tableau de distances est alors
A BF C D E
A 0
BF ? 0
C 7 ? 0
D 7 ? 2 0
E 5 ? 5 5 0
La distance entre la nouvelle classe BF et l'ancienne
classe A notée dist(BF,A) vaut, compte tenu de notre
choix de recalcul de distances, l'arrondi entier de [
dist(B,A) + dist(F,A) ] / 2 soit ici ron[(9+5)/2]=7. De
même, la distance entre BF et C vaut ron[ dist(B,C) +
dist(F,C) /2 ] soit ron[( 4+3)/2 ]=4. Après tous les
recalculs, le nouveau tableau de distances est
A BF C D E
A 0
BF 7 0
C 7 4 0
D 7 4 2 0
E 5 5 5 5 0
Si on recommence le processus, la nouvelle plus petite
distance est 2, pour C et D, soit la Classe 8 : CD
(obtenue pour la distance 2). Après mise à jour des
distances, le nouveau tableau se réduit à
A BF CD E
A 0
BF 7 0
CD 7 4 0
E 5 5 5 0
Pour la prochaine agrégation, c'est BF et CD qui seront
réunies, soit la classe 9 : BFCD (obtenue pour la
distance 4) et il ne reste plus, comme tableau de
distances :
A BFCD E
A 0
BFCD 7 0
E 5 5 0
Clairement, on construit alors la classe 10 : AE
(obtenue pour la distance 5) qui donne le tableau de
distances
AE BFCD
AE 0
BFCD 6 0
Et finalement on a la classe 11 : ABFCDE (obtenue pour
la distance 6).
L'historique de la classification peut alors être dressé comme suit :
Nø Distance Ainé Benjamin Nombre Liste des éléments
11 6 10 9 6 A B F C D E
10 5 1 5 2 B F C D E
9 4 7 8 4 B F C D
8 2 3 4 2 C D
7 1 2 6 2 B F
et sa représentation graphique (dendrogramme) est alors :
Dessin
Introduction au projet
Le but du projet que nous allons présenter et du
logiciel qui en résulte est de réaliser une
classification hiérarchique ascendante et le tracé
automatique du dendogramme associé. Il y a trois
parties nettement distinctes dans ce projet : le calcul
des distances à partir des données, l'établissement des
classes et leur tracé. Ces trois parties seront liées
par des fichiers texte, car elles sont prévues pour
fonctionner sur des machines avec des systèmes
d'exploitation différents et le format "texte brut" es t
un bon format d'échange. Nous créérons au passage un
générateur aléatoire de distances. Le fichier de
données sera repéré par le type .Dat ; la classification
fournira un fichier .Scr qui sera interprété en termes
graphiques par AutoLisp qui est la version de Lisp
utilisée par AutoCad.
La création automatique d'une matrice de distances passe
par la définition d'un seul paramètre : la taille de la
matrice. Cette valeur est un nombre entier. Nous
supposerons que ce nombre est passé à l'algorithme de
création automatique. Sous Unix ou sous Dos, on
réalisera un test sommaire pour vérifier qu'on passe
bien une valeur en quelques lignes de JCL (Job Control
Language). Ainsi, sous Dos, si la création se fait sous
Awk avec le fichier programme Aleacl.Awk, le passage
d'un paramètre (ici le seul e t donc de nom %1) peut
être effectué par le fichier "Batch" suivant :
@echo off
if $%1 == $ goto erreur
awk -f aleacl.awk %1
goto fin
:erreur
echo Erreur, vous n'avez pas donné le nombre d'éléments
echo Syntaxe : Aleacl [ Nombre ]
echo.
echo Exemple : Aleacl 12
:fin
La création automatique doit générer des identificateurs
de ligne et des valeurs numériques que nous prendrons
entières par raison de simplicité. Un identificateur de
ligne facile à fabriquer est celui qui vaut E001 pour le
premier élément, E002 pour le second etc. ; cette
construction limite la taille de la matrice à 999 ce qui
était suffisant pour notre application et qui permet de
respecter une norme de 4 caractères au maximum par
identificateur. Une généralisation facile serait de
cadrer sur 4,5,6 carac tères, si besoin est, donnant par
exemple E00001 comme identificateur au premier élément.
La méthode serait exactement la même.
Appelant nbval le nombre de termes à créer, une boucle
pour suffit à cet effet. On appelle id l'identificateur
courant, et on l'écrit dans le fichier fs associé au nom
de fichier "aleacl.cla" ; on utilise la fonction format
pour convertir une valeur numérique en chaîne, ainsi
format(3) renvoie "3".
associer "aleacl.cla" à fs
ouvrir fs
pour i de1à nbval
ids <-- ""
si (i<100) alors
ids <-- "0"
finsi (i<100)
si (i<10) alors
ids <-- ids + "0"
finsi (i<10)
ids <-- "E" + ids + format(i)
écrire ids sur fs
finpour i de1à nbval
fermer fs
Nous supposerons de plus qu'il existe une fonction
aléatoire nommée aléa() qui renvoie un nombre entre 0 et
1, le tirage de nombres consécutifs étant uniformément
réparti, ce qui souvent le cas pour de nombreux langages
de programmation. La création de la matrice
triangulaire inférieure est alors réalisée par deux
boucles emboitées.