Clustering

Principe

Cette section regroupe les méthodes destinées à construire automatiquement des groupes homogènes au sein d'un ensemble de données. On parle également de méthodes non-supervisées.

L'objectif est de produire des groupes "naturels" de manière à ce que :
(a) les individus d'un même groupe se ressemblent;
(b) les groupes sont très dissemblables.

Statut des variables

Seules les variables "input" sont à définir, sauf mention contraire, elles doivent être continues.

Opérateurs de clustering

Opérateur Description Paramétrage Remarques

K-Means
K-Means - Algorithmes de Forgy et Mc Queen. Plusieurs essais sont effectués, le meilleur sera retenu.

- T. Hastie, R. Tibshirani, J. Friedman, "The elements of statistical learning. Data Mining, inference and predictions.", Springer, pp.461-463, 2001.
- Un article fondateur : E. Diday, "La méthode des nuées dynamiques", Revue de Stat Appliquée, vol. 19, n°2, pp.19-34, 1971.
- Ouvrage de base : M.R. Anderberg, "Cluster analysis for applications", Academic Press, 1973.
- Ouvrage de référence en français : J.L. Chandon, S. Pinson, "Analyse typologique : théorie et applications", Masson, pp.132-160, 1981.

- Nombre de clusters demandés
- Nombre d'itérations maximum
- Nombre d'essais
- Normalisation des données
- Mode de mise à jour du centre gravité lors de l'optimisation

Kohonen's SOM
Cartes de Kohonen.

- T. Kohonen, "Self-organization and associative memory", Springer-Verlag, 1988.
- K. Mehrotra, C. Mohan, S. Ranka, "Elements of artificial neural network", MIT Press, pp.187-201, 1997.
- T. Hastie, R. Tibshirani, J. Friedman, "The elements of statistical learning. Data Mining, inference and predictions.", Springer, pp.480-485, 2001.

- Nombre de lignes de la carte
- Nombre de colonnes de la carte
- Normalisation des données
- Constante d'apprentissage

LVQ
Learning Vector Quantizers. Dûe à Kohonen, il s'agit d'une méthode de clustering semi-supervisée, à savoir que l'on définit un nombre de clusters par classe (modalité de la variable à prédire), puis l'agorithme cherche les meilleurs clusters dans ces classes.

Au-delà du simple clustering par classe que l'on pourrait effectuer avec un K-Means par exemple, LVQ cherche à créer des prototypes (les centres de groupes) qui sont d'autant plus éloignés les uns des autres qu'ils représentent des modalités différentes de la variable à prédire.

En effet, lors des itérations, pour un nouvel individu présenté, le prototype le plus proche lui sera rapproché s'il appartient à la même classe, en revanche, il sera éloigné s'il appartient à une classe différente.

- T. Kohonen, "Self-organization and associative memory", Springer-Verlag, 1988.
- K. Mehrotra, C. Mohan, S. Ranka, "Elements of artificial neural network", MIT Press, pp.173-176, 1997.
- T. Hastie, R. Tibshirani, J. Friedman, "The elements of statistical learning. Data Mining, inference and predictions.", Springer, pp.414-415, 2001.

- Nombre de clusters par classe
- Constante d'apprentissage
- Nombre d'itérations
- Normalisation pour le calcul des distances
La variable "Target" doit être définie, elle est discrète.

HAC
CAH mixte, décrite dans l'ouvrage de Lebart et al., cette méthode rend possible la construction du dendogramme à partir d'un grand ensemble de données.

La construction de l'arbre est réalisé en deux temps :
(1) à l'aide d'une méthode de clustering quelconque (K-Means, SOM), on produit un nombre élevé de clusters ;
(2) on utilise ces clusters comme point de départ pour construire le dendogramme.

Cette approche améliore grandement le temps de calcul sans faire perdre à la méthode sa capacité à trouver des clusters emboîtés et choisir alors le niveau de coupure qui lui semble le plus approprié.

Reste à spécifier le nombre de clusters dans la première phase, il est sûrement inférieur au nombre d'individus dans la base, cela va de soi, on peut fixer une valeur entre 15 et 20, ce qui assure un bon compromis entre temps de calcul et exploration.

- Méthode de détection des clusters
- Fixer le nombre de clusters
- Normaliser les variables pour le calcul des distances
La variable "Target" doit être définie, elle est discrète, elle serait issue d'un premier clustering avec les K-Means ou SOM.

Dernière modification : 18 avril 2004.