II.2. Les méthodes
monothéiques
Les méthodes nomothétiques divisent un segment
(classe C) de l'arbre hiérarchique en deux sous-segments (sous-classes
C1 et ) en fonction d'une variable et de deux groupes de valeurs de cette
variable.
Si la variable est quantitative le segment est divisé
suivant la réponse à la question de la forme "valeur de la
variable inferieur ou égal à c?". Le premier sous-segment C1
contient les individus pour lesquels la valeur de la variable est
inférieure ou égale à c, et l'autre les individus pour
lesquels la valeur de la variable est strictement supérieure à c.
Si la variable est qualitative, un individu est affecté au premier
sous-segment C1 si sa description pour cette variable appartient à un
premier groupe de modalités, sinon il est affecté au
deuxième sous-segment .
La stratégie utilisée par ces méthodes
pour choisir la variable de division (parmi celles caractérisant les
individus) ainsi que la valeur de coupure (c pour les variables quantitatives,
et les groupes de modalités pour les variables qualitatives) repose sur
l'optimisation d'un critère d'évaluation bien
déterminée (par exemple le diamètre d'une partition
donné par la plus grande dissimilarité entre deux individus d'une
même classe: ainsi nous choisissons la classe et la coupure qui
fournissent une partition de petit diamètre).
Les classifications autour de centres mobiles ou
partitionnements, consistent à agréger les individus autour des
noyaux qui, au départ, sont proposés par l'utilisateur ou
tirés au hasard. On aboutit à une première partition qui
dépend beaucoup du tirage des premiers noyaux. On recommence donc en
prenant cette fois pour noyaux les centres de gravité des classes
obtenues à l'étape précédente, et ainsi de suite
jusqu'à la stabilisation des classes. Le résultat de l'algorithme
est une partition unique.
II.3. Segmentation non
hiérarchique
Dans cette approche, on souhaite obtenir une
décomposition de l'ensemble de données X en K groupes non
hiérarchisés que l'on notera
G1, G2,... GK. On a : X =  plusieurs méthodes existent dans cette catégorie.
II.3.1 La méthode des
centres mobiles.
L'algorithme des centres mobiles est également
dénommé k-moyennes, ou centroides. L'objectif est de segmenter
les données en k groupes, k étant fixé a priori.
L'idée de cet algorithme est très intuitive et, de fait, cet
algorithme a été réinventé à plusieurs
reprises. Il en existe de nombreuses variantes, en particulier l'algorithme
bien connu des « nuées dynamiques ». L'idée de
l'algorithme des centres mobiles est la suivante : on part de K données
synthétiques (c'est-à-dire des points de l'espace de
données D ne faisant pas forcément parti du jeu de
données) que l'on nomme des « centres ». Chaque centre
caractérise un groupe. A chaque centre sont associés les
données qui lui sont les plus proches ; cela crée un groupe
autour de chaque centre. Ensuite, on calcule le centre de gravité de
chacun de ces groupes ; ces k centres de gravité deviennent les nouveaux
centres et on recommence tant que les groupes ne sont pas stabilisés,
c'est-à-dire. Tant qu'il y a des données qui changent de groupe
d'une itération à la suivante ou encore, tant que l'inertie varie
substantiellement d'une itération à la suivante. Cet algorithme
converge en un nombre fini d'itérations.  
Où g = (g1, . . . ,gs),   est le centre de la classe   . Rappelons que le critère W(z,g), qui est simplement la somme
des inerties des s classes, est appelé inertie intra classe. La
méthode des centres mobiles consiste à chercher la partition
telle que le W soit minimal pour avoir en moyenne des classes bien
homogènes, ce qui revient à chercher le maximum de l'inertie
interclasse.
Avec   le centre de gravité de l'ensemble I et   est le poids de la classe
Algorithme de centres mobiles.
Nécessite: 2 paramètres : le jeu de
données X, le nombre de groupes à constituer
K €N
Prendre K centres arbitraires ck € D
Répéter
pour k € {1....K} faire
Gk ?Ø
Fin pour
pour i = {1....N} faire
k* =arg min k={1....K} d(xi;
ck)
Gk? Gk  xi
Fin pour
pour k € {1....K} faire
Gk ? centre de gravité de
Gk
Fin pour
I ? IW
Calculer IW
Jusque I - IW < seuil.
Quelques remarques sur les centres
mobiles
La segmentation obtenue dépend des centres initiaux
Lors de l'initialisation de l'algorithme, on prend K points dans l'espace de
données au hasard. La segmentation calculée par les centres
mobiles dépend de cette initialisation.
Pour contrer ce problème, on exécute plusieurs
fois l'algorithme en prenant à chaque fois des centres
initialisés différemment. On compare les segmentations obtenues
à chaque itération et on retient celle dont l'inertie intra
classe est la plus faible. En général, un certain nombre de
données se trouvent toujours regroupées ensemble, alors que
d'autres ne le sont pas. On peut considérer que les premières
indiquent nettement des regroupements, alors que les secondes correspondent
à des données éventuellement atypiques, ou à des
données bruitées. De toute manière, cette information est
intéressante.
Le nombre de groupes
Le K choisi peut être mauvais. On peut tester plusieurs
valeurs de K en exécutant plusieurs fois l'algorithme avec des K
croissants. Pour chaque valeur.
| 
