Une contribution du datamining àƒÂ la segmentation du marché et au ciblage des offres àƒÂ l'aide de la statistique de Bayes

II.3.2 Les nuées dynamiques

La méthode dite des nuées dynamiques est l'une des méthodes de partitionnement dite de « réallocation » pouvant avantageusement s'appliquer sur une grande population (grand ficher numérique ou grand tableau) avec un critère de qualité de la partition obtenue. Les algorithmes des nuées dynamiques sont itératifs et optimisent un critère mathématique.

Cette méthode a été développé par Diday dans [Diday, 1971] se distingue principalement des approches précédentes par le mode de représentation des classes appelé aussi noyau. Ce dernier peut être son centre de gravité (dans ce cas nous retrouvons l'approche des centres mobiles), un ensemble d'individus, une distance (l'approche des distances adaptatives, une loi de probabilité, la décomposition de mélanges), etc.

II.3.2.1 Bases théoriques de l'algorithme

Soit, un ensemble de n individus. Chaque individu , muni de sa masse est caractérisé par p variables.

Le problème posé est de trouver sur l'ensemble I une partition en k (k fixé à priori) classes au maximum satisfaisant un critère global de qualité.

Principe général de la méthode

Soient :

- I : l'ensemble de n individus à partitionner en k classes au maximum ;

- P(I) = {P⁰, P¹, ..., P^m_, ..., P^k} : ensemble des parties de I ;

- A : un ensemble de k noyaux A_i ;

- On suppose que l'espace R^p supportant les n points individus est muni d'une distance appropriée ; notée d ;

Chaque classe est représentée par son centre A_i, également appelé noyau, constitué du petit sous-ensemble de la classe qui minimise le critère de dissemblance. Les éléments constitutifs d'un noyau sont appelés étalons. Ce genre de noyau a pour certaines applications, un meilleur pouvoir descriptif que des centres ponctuels.

Chaque individu , est par conséquent, caractérisé par sa masse et par la distance qui le sépare du noyau de sa classe.

La méthode des nuées dynamiques consiste à trouver deux applications sur lesquelles repose l'algorithme. Ces deux fonctions de base sont telles que:. La fonction de réallocation a pour rôle de former une partition, c'est à dire d'affecter chaque individu du nuage N(I) aux centres d'attractions que forment les noyaux.

A = v(P)

La fonction de recentrage v a pour rôle de recalculer les nouveaux noyaux à partir des classes déjà formées.

L'algorithme est une succession d'appels à ces deux fonctions, il se présente de la manière suivante :

a) Initialisation

Ø Le choix (au hasard ou non) des k premiers noyaux, , induisant la première partition de l'ensemble I et k classes .

b) Recherche de la meilleure partition

Ø Par l'exécution de sur ces noyaux et on poursuit les autres étapes jusqu'à l'arrêt de l'algorithme.

L'algorithme se termine soit lorsque deux itération successives conduisent à la même partition, soit lorsqu'un critère judicieusement choisi (par exemple, la mesure de la variance intra classes) cesse de décroître de façon sensible (convergence), soit encore lorsqu'un nombre maximal d'itération fixé à priori est atteint.

II.3.2.3 Choix des fonctions

Le choix de deux fonctions de base, de l'algorithme, est guidé par des considérations suivantes :

1°)

Avec

Chaque individu est associé au noyau le plus proche.

2°) A = v(P), A = {A₁, ..., A_k}

Avec A_i, un ensemble de n_i éléments qui minimisent une fonction L(v i, I, P)

3°) la fonction L(v i, I, P) induit une notion de « distance » de l'individu v i à la classe C_m de la partition P ;

On peut alors définir un critère de qualité de la partition P autour d'un ensemble de noyaux A par :