WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

Contribution à  l'optimisation complexe par des techniques de swarm intelligence

( Télécharger le fichier original )
par Lamia Benameur
Université Mohamed V Agdal Rabat Maroc - Ingénieur spécialité : informatique et télécommunications 0000
  

précédent sommaire suivant

3.5.2 La couche de classification automatique floue

C'est une approche qui cherche à détecter la présence éventuelle de classes homo-
gènes au sein d'un ensemble d'observations multidimensionnelles X = {x1, x2, ..., xn} ?

Rp, de structure totalement inconnue a priori. Elle ne fait aucune hypothèse préalable sur le nombre de classes à détecter et suppose que les données sont entièrement non étiquetées.

Cette méthode est constituée de deux étapes [Bouroumi et al, 2000]. La première étape est une procédure d'apprentissage flou qui explore les données de X, moyennant une mesure de similarité inter-objets et un seuil associé Smin, en vue d'y détecter la présence éventuelle de classes plus au moins séparées. Elle fournit, en plus du nombre c de classes détectées dans X, une bonne estimation des prototypes V = {v1, v2, . . . , vc} ? Rc × Rp et de la matrice des degrés d'appartenance U = {u1, u2, . . . , uc} ? Rc × Rn. La seconde étape est une procédure d'optimisation qui applique l'algorithme des C-moyens flous, initialisé avec les résultats de la première étape, notamment le nombre de classes c et la matrice des prototypes V.

Phase d'apprentissage

Cette procédure cherche à exploiter l'information, apportée par les vecteurs de X, dans le but de détecter la présence éventuelle de groupements homogènes au sein de X. Pour cela, elle commence par générer une première classe dont le prototype (centre) est initialisé avec le premier vecteur objet analysé. Ensuite, les (n-1) autres vecteurs objets sont séquentiellement examinés. Une nouvelle classe est automatiquement créée chaque fois que l'objet traité présente un faible degré de similarité, i.e., inférieur à un seuil donné Smin, par rapport aux différents centres de classes déjà créées.

Pour mesurer la similarité entre deux vecteurs xi et xj de Rp, l'expression (3.4) est utilisée :

s(i, j) = 1 - d(xi, xj)

vp

= VEio=1 11xik - xjk112 1 - (3.4)

vp

oil d(xi, xj) est une mesure de distance Euclidienne, calculée à partir des valeurs normalisées de xi et xj. Pour normaliser la Kème composante de chaque vecteur (1 = k = p), oil p est la dimension de l'espace des objets (nombre total de paramètres), la relation suivante a été utilisée :

x i ? max(k) - min(k) xi - min(k)

(3.5)

xki représente le Kème composante (valeur) du ième vecteur objet, max(k) et min(k) désignent respectivement les valeurs maximale et minimale prises par cette composante sur l'ensemble des vecteurs de X.

En remplaçant, dans l'équation (3.4), xj par le représentant (prototype) de la classe j (vj), la relation peut également être interprétée comme le degré d'appartenance de l'objet xj à la classe j.

d(xi, vj)

uij = 1 - (3.6)

vp

Lors du processus d'apprentissage, l'équation (3.6) est effectivement utilisée à chaque itération pour évaluer le degré d'appartenance de l'objet courant à chacune des c classes existantes (avec c variable). La condition de création d'une nouvelle classe peut alors s'exprimer sous la forme :

max(uij) < Smin (3.7)

i=j=c

Lorsque la condition (3.7) n'est pas vérifiée, les C prototypes des classes précédemment créées sont actualisés selon la règle d'apprentissage donnée par l'équation (3.8) :

vi(k) = vi(k - 1) + uik

çi(k)[xk - vi(k - 1)] (3.8)

oil çi(k) dénote le cardinal flou de la ième classe à l'itération k, soit :

çi(k) = Xk uij (3.9)

j=1

Il est clair que le choix du paramètre Smin joue un rôle essentiel dans le processus d'apprentissage. Théoriquement, si à la limite Smin est très faible ( 0%), une seule classe, formée des n objets de X, peut être obtenue (C = 1). Inversement, si Smin est trop élevé ( 100%), chaque objet peut former une classe à part et on aura (C = n).

Intuitivement, pour découvrir les groupements naturels supposés présents dans X, une valeur adéquate de Smin doit être typiquement inférieure aux similarités inter-classes et supérieure aux similarités intra-classes. Il sera donc plus commode de faire varier Smin entre 2 valeurs S1 et S2 qui dépendent de l'ensemble X et qui sont automatiquement déterminées par l'algorithme selon les équations suivantes :

S1 = min{S(xi, xk)} (3.10a)

i6=k

S2 = max

i6=k

{S(xi, xk)} (3.10b)

Généralement, lorsqu'un algorithme produit une C-partition des données, plusieurs questions surviennent à propos de la qualité de la partition obtenue, du degré de confiance qu'on peut lui attribuer, de la possibilité de trouver une partition meilleure, etc. C'est le problème de validation des résultats qui constitue le dernier stade du modèle. Ce problème est intimement lié à toute classification automatique et traite de la validité de la structure des données produite par un algorithme.

Pour valider les résultats de classification, plusieurs critères de validité ont été testés. Ceux-ci incluent le coefficient de partition [Bezdek, 1981], l'indice de Xie et de Beni [Xie et Beni, 1991], l'indice de Fukuyama et de Sugeno, l'indice de Bensaid et le critère d'entropie [Bezdek, 1981]. Les résultats expérimentaux ont prouvé que, dans cette étude, le critère de l'entropie (h) est l'index le plus fiable. Ce critère

dépend uniquement de la matrice des degrés d'appartenance U et est donné par la formule (3.11) :

1 1

h(U) = -- ÓC j=1uij log(uij) (3.11)
log(C) n

Phase d'optimisation

La seconde phase de l'approche de classification floue sert à améliorer la partition apprise, générée lors de la phase d'apprentissage. En général, la procédure utilisée est basée sur l'algorithme C-moyennes (C-means) floues (CMF) [Bezdeck, 1981].

L'algorithme des C-moyennes floues est une extension directe de l'algorithme classique, oil la notion d'ensemble flou est introduite dans la définition des classes. L'algorithme des C-moyennes est l'exemple type des algorithmes de "clustering" (regroupement). Le principe de base, qui reste inchangé dans la version floue, est de former C groupes qui soient les plus homogènes et naturels possibles. CMF est une technique d'optimisation qui cherche à minimiser la somme pondérée des carrées des distances interclasses.

Dans l'algorithme des C-moyennes, on suppose que le nombre de classes C est connu. En fait, l'implémentation de cet algorithme présuppose que le nombre de classe est déterminé préalablement lors de la phase d'auto-apprentissage.

Les étapes de l'algorithme des C-moyennes se déroulent de la manière suivante (C fixé) :

1. Utiliser la matrice d'appartenance générée par la phase d'apprentissage,

2. Calculer les centres des classes,

3. Réajuster la matrice d'appartenance suivant la position des centres,

4. Calculer le critère d'arrêt : s'il n'a pas convergé, retourner à l'étape 1.

Enfin, une procédure de "defuzzification" est utilisée pour affecter définitivement chaque objet à sa classe naturelle, i.e., pour laquelle il présente le degré d'appartenance le plus élevé. On obtient ainsi une partition classique à C classes représentées par leurs centres (prototypes) vi, (1 i C).

précédent sommaire suivant






Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy