CADCOM/MANUEL D'UTILISATION


Algorithme des Nuées Dynamiques


Principe

Les nuées dynamiques sont en fait une généralisation de l'algorithme  des k-moyennes.
On cherche à constituer une partition en K classes des données d'entrée. Chaque classe est représentée 
par son centre,également appelé noyau, constitué du petit sous-ensemble de la classe 
qui minimise le critère de dissemblance.

 

Les deux fonctions de base sur lesquelles repose l'algorithme sont les suivantes;

 La fonction de réallocation 
                      Elle partitionne,c'est à dire qu'elle affecte chaque individu du
                      nuage E aux centres d'attractions que forment les noyaux.
                      Elle est définie par l'équation
  

                      où nj  est le nombre d'éléments du noyau 
  
 La fonction de recentrage
                      Elle recalcule les nouveaux noyaux à partir des classes déjà formées. 
                      Elle est définie par l'équation  
                       
                      où Njest le nombre d'éléments de la classe ou partition 

Déroulement de l'algorithme

 
  Initialisation aléatoire des K premiers noyaux 
  Affectation: Calcul de la classe de chaque point du nuage .
  Mise à jour des centres (ou attributs des classes). 
                                          Calcul des nouveaux centres de chaque classe (barycentre )
  Test de convergence: 
                      L'exécution de l'algorithme se termine lorsque le partitionnement n'évolue plus, c'est à dire
                      lorsque le critère d'inertie  intra-classe ,défini par l'équation ,converge.
 
                      
 
                      où Gj est le centre de gravité de la classe  défini par l'équation 
                      CENTER>
  
 Le résultat change selon le choix des conditions initiales(Monte-Carlo).
 Il faut donc exécuter plusieurs fois l'algorithme et comparer les résultats de manière à extraire
 les classes stables, c'est à dire à dégager ce qu'on appelle des formes fortes.

(SOMMAIRE)

Webmaster:
Last revised:05/2001