NEUROMUSE3

Work in progress …

code source


Parent page.

Classification Ascendante Hiérarchique

Dans le cadre de Neuromuse3, une procédure de discrimination de la carte en fanaux peut être réalisé par classification ascendante hiérarchique – notée CAH – selon la méthode de Ward. Le choix de la méthode reste empirique, mais dans le cas de figure qui nous interesse, la méthode de Ward parait la plus appropriée dans le cadre d'une classification automatique.

Pour mémoire, il ne sera exposé ici que les linéaments de la CAH et de la méthode de Ward, décrit plus précisément dans l'article de Marie Chavent: La classification automatique de données quantitatives. et de Cosma Shalizi: Distances between Clustering, Hierarchical Clustering..

Illustration 1 – Diagramme de l'algorithme CAH assuré par la fonction dendogram. [ Comprendre le format Newick: The Newick tree format et wikipedia: Newick format ]

Méthode de Ward

Avec la méthode de Ward, la distance entre deux classes A et B est calculée de la façon suivante:

avec

Dans certains cas, la hiérarchie du dendogramme peut présenter des inversions. Cela peut être éviter en appliquant la relation suivante: ∀A, B ∈ H, h(A ∪ B) = max(d(A, B), h(A), h(B)).

Enfin, l'inertie intraclasse est calculée pour chaque nœud (slot inertia) – en tant que potentielle classe C – telle que1):

Application

Dans la perspective d'une discrimination en fanaux (voir fonction cah-fanaux), la représentation du dendrogramme du SOM color (voir illustration 3 page N3_color) permet une vue d'ensemble du processus opéré.

Illustration 2 – Dendrogramme appliqué au SOM color avec la méthode de Ward.

Pour mémoire, le dendrogramme de l'illustration 2 a été réalisé de la façon suivante:

  1. Conversion de la couleur de chaque neurone au format RGB:
    Lisp code
    (>data-file "color.dat" (loop for i in (neurons-list color) collect (cons i (mapcar #'(lambda (x) (round (* 255 x))) (output i)))))
  2. Écriture du fichier color.map avec les images couleurs des neurones associés réalisés avec ImageMagick:
    Script bash
    #!/bin/bash
    > color.map
    mkdir img
    while read LINE
    do
    	name=`echo $LINE | awk '{print $1}'`
    	C1=`echo $LINE | awk '{print $2}'`
    	C2=`echo $LINE | awk '{print $3}'`
    	C3=`echo $LINE | awk '{print $4}'`
    	echo "\"<image width='60' height='25' xlink:href='...current_directory.../img/$name.png'/>\" I $name" >> color.map
    	convert -size 100x60 xc:'rgb('$C1','$C2','$C3')' img/$name.png 
    done < color.dat
  3. Réalisation de l'image SVG avec newick_utils:
    Script bash
    #!/bin/bash
    # $1 is the newick file generated by the lisp function DENDROGRAM - i.e. (dendrogram color 3) 
    name=$(basename $1)
    nw_display -sr -S -w 1000 -W 20 -b 'opacity:0' -o color.map $1 > $name.svg

Index

  • [ Variables ]
    • *TREE*
      Le nœud racine (root node) du dernier arbre construit avec la fonction DENDROGRAM.
  • [ Fonctions ]
    • CAH-FANAUX som node n-class &key diss-fun trim
      L'arbre définit par node est « élagué » afin d'obtenir un nombre de branches égal à n-class. Le résultat est la liste de neurones (les plus proches du centre de gravité de chaque branche élaguée) appartenant au som. La clef trim ne liste que les branches rattachées au nœud racine.
    • DENDROGRAM som aggregation &key diss-fun newick with-label with-data
      Réalise l'arbre de som selon la méthode de classification ascendante hiérarchique avec une méthode d'aggregation par saut minimum (1), par diamétre (2) ou par la méthode de Ward (3).
      diss-fun est une liste regroupant la fonction de dissimilarité plus les options (par défaut c'est la distance euclidienne appliquée à l'output des neurones).
      newick permet d'éviter la procédure de sauvegarde qui est effective par défaut.
      with-label permet d'afficher sur le dendrogramme le nom de tout les nœuds (par défaut seul les neurons sont nommés).
      with-data génére un fichier de données avec par ligne le nombre de classes associé à la distance du prochain nœud (ou la prochaine division de classe) et la somme des inerties des classes concernées (”# number_of_classes dx_distance inertia_sum”).
    • GET-LEAVES node &key trim
      Liste toutes les feuilles (définit par un neurone – i.e. node-data) pour un nœud donné (i.e. ”prune”) ou avec la clef trim tout les nœuds d'une distance donné (qui peut être définit par un nœud) au nœud racine node.
    • SAVE node
      Sauvegarde de l'arbre définit par node selon le chemin suivant: *N3-BACKUP-DIRECTORY*/aggregation[number]_node_SOM[epoch]/SOM[name].tree.
Imprimer/exporter
QR Code
QR Code wiki:n3_cah (generated for current page)