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).
| 
