Méthodes neuronales en classification non supervisée
44
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
44
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
CNAM IS 2009-2010
Méthodes neuronales en
classification non
supervisée
Yves Lechevallier
INR
I
A-Rocquencourt
E_mail : Yves.Lechevallier@inria.fr
Yves Lechevallier
Cours CNAM IS
1 Méthodes de partitionnement
La structure classificat
oire recherchée est la
partition
. En
définissant une fonction d’homogénéité
ou
un critère de
qualité
sur une partition le probl
èm
e de classification devient
un problème parfaitement défini en optimisation discrète.
Trouver, parmi l’ensemble de toutes les partitions
possibles,
une partition qui optimise un critère défini a priori
.
E
est fini donc il y a un ensemble f
i
ni de partitions
possibles
alors
le
problème
est toujours soluble par l’énumération
complète.
Cependant,
en pratique, cette approche est
irréalisable car nous avons approximativement avec
un
N
KK
!
ensemble de N objets en K classes solutions possibles.
Yves Lechevallier
Cours CNAM IS
2 Problème d’optimisation
+
℘
(
E
)
→
ℜ
Soit un critère
U
, défini de , où
est
K
℘
()
E
l’ensemble
de toutes les partitions en
K
classes
K
non vides de alors le problème d’optimisation se pose
sous la forme:
U
(
P
)
=
Min
U
(
Q
)
Q
∈
℘
(
E
)
K
Yves Lechevallier
Cours CNAM IS
3 Optimisation itérative
(
0
)
On part d’une solution réalisable
Choix
Q
∈
℘
(
E
)
K
(
t
)
A l’étape
t+1
, on a une solution réalisable
Q
(
t
+
1
)
(
t
)
Q
=
g
(
Q
)
on cherche une solution ...
Voir
Méthodes neuronales en
classification non
supervisée
Yves Lechevallier
INR
I
A-Rocquencourt
E_mail : Yves.Lechevallier@inria.fr
Yves Lechevallier
Cours CNAM IS
1 Méthodes de partitionnement
La structure classificat
oire recherchée est la
partition
. En
définissant une fonction d’homogénéité
ou
un critère de
qualité
sur une partition le probl
èm
e de classification devient
un problème parfaitement défini en optimisation discrète.
Trouver, parmi l’ensemble de toutes les partitions
possibles,
une partition qui optimise un critère défini a priori
.
E
est fini donc il y a un ensemble f
i
ni de partitions
possibles
alors
le
problème
est toujours soluble par l’énumération
complète.
Cependant,
en pratique, cette approche est
irréalisable car nous avons approximativement avec
un
N
KK
!
ensemble de N objets en K classes solutions possibles.
Yves Lechevallier
Cours CNAM IS
2 Problème d’optimisation
+
℘
(
E
)
→
ℜ
Soit un critère
U
, défini de , où
est
K
℘
()
E
l’ensemble
de toutes les partitions en
K
classes
K
non vides de alors le problème d’optimisation se pose
sous la forme:
U
(
P
)
=
Min
U
(
Q
)
Q
∈
℘
(
E
)
K
Yves Lechevallier
Cours CNAM IS
3 Optimisation itérative
(
0
)
On part d’une solution réalisable
Choix
Q
∈
℘
(
E
)
K
(
t
)
A l’étape
t+1
, on a une solution réalisable
Q
(
t
+
1
)
(
t
)
Q
=
g
(
Q
)
on cherche une solution ...
CNAM IS 2009-2010
Méthodes neuronales en classification non supervisée
Yves Lechevallier
INRIA-Rocquencourt
_ vallie @inria.fr E mail : Yves.Leche r
Yves Lechevallier
Cours CNAM IS
1
Méthodes de partitionnement
La structure classificatoire recherchée est lapartition. En définissant une fonction d’homogénéité ou un critère de qualité sur une partition le problème de classification devient un problème parfaitement défini en optimisation discrète.
Tr armi l’ nsemble de toutes les partitions possibles, ouver, p e une partition qui optimise un critère défini a priori.
Eest fini donc il y a un ensemble fini de partitions possibles alors le problème est toujours soluble par l’énumération complète. Cependant, en pratique, cette approche est irréalisable car nous avons approximativement avec un ensemble de N objets en K classesK N K ! solutions possibles.
Yves Lechevallier
Cours CNAM IS
2
Problème d’optimisation
Soit un critèreU, défini deK ( E ) → ℜ + est où , l’ensemble ( E )de toutes les partitions enKclasses non vides de alors le problème d’optimisation se pose sous la forme:
U(P)
Yves Lechevallier
Q∈M℘Ki(nE)U(Q)
Cours CNAM IS
3
4
Yves Lechevallier
Choix
Cours CNAM IS
L’algorithme s’arrête dès que
Q(t+1)∈Q(0),LQ(t) ,
on cherche une solution réalisable
vérifiant
U(Q(t+1))≤U(Q(t))
Choix
Q(t+1)=g(Q(t))
Q(t)
On part d’une solution réalisable
A l’étapet+1, on a une solution réalisable
Optimisation itérative
Q(0)∈℘K(E)
Algorithme de voisinage
Une des stratégies la plus utilisée pour construire la fonctiongest :
•d’associer à toute solution réalisableQun ensemble fini de solutions réalisablesV(Q),appelévoisinagedeQ,
•puis de sélectionner la solution optimale pour ce critèreUdans ce voisinage, ce qui est couramment appelésolution localement optimale. Par exempleon peut prendre comme voisinage deQtoutes les partitions obtenues à partir de la partitionQen changeant un seul individude classe Deux exemples les plus connus de ce type d’algorithme sont l’algorithme detransfertet l’algorithme desk-means
Yves Lechevallier
Cours CNAM IS
5
Algorithme desk-means
Avec un algorithme de voisinage, il n’est pas nécessaire, pour obtenir la décroissance du critère, de prendre systématiquement la meilleure solution, il suffit de trouver dans ce voisinage une solution meilleure que la solution en cours. Pour l'algorithme desk-meansl’étape (b) devient : l l=dz w determiner tel que argj=m1,iL,nK2(i,j)
La décroissance du critèreUde l’inertie intra-classe est assurée grâce au théorème de Huygens
Remarquons qu’il est impossible de démontrer que l'une des stratégies donne systématiquement une meilleure solution.
Yves Lechevallier
Cours CNAM IS
6
Affectation d’un nouvel individu
..,K éfinit une pUanrtei tfioonnc t i oF Φn d ’ a fF f 1 e, c Lt a, t i F o K n } φ l’ed deDn ioatnt ecaved ecapsesérpe}rd snC {=,1ead
Fj= {z
∈D/
(z)
j}
A la convergence de ces algorithmes, la fonctionφest construite de la manière suivante :
∀z∈D
(z)
Yves Lechevallier
jsid(z,wj)
kM1,iKn d(z,wk =
Cours CNAM IS
)}
7
Exemp
Trajectoires des 3 centres d’un nuage de points bidimensionnel
Les hyperplans séparateurs entre les classes
Yves Lechevallier
le
Cours CNAM IS
8
Choix d’un critère ou d’un modèle
Classification « naturelle »
Classification avec les centres mobiles. Cette classification ne correspond pas à la structure cachée
Le critère optimisé est la somme des carrés de écarts entre les valeurs des points et la moyenne de la classe
Yves Lechevallier
Cours CNAM IS
9
Perte d’information
Le critère U représente la perte d’information en remplaçant le tableau des données Z par le tableau des centres de gravité. 1⎤ 1 1 1 1 Réduction⎡⎢z1zjzp⎥⎥⎥ 1 des lignesZ=[z,=L,zi,L,zKN]⎡=⎢⎣⎢=⎢zggzik1NzzggijkjjjNzzggppkippN⎤⎥⎦ 1 1 1 d’un tableau1 G[g1,K,g]⎢⎢gKgjKgpK⎦⎥ ⎣1⎥ Cet algorithme est identique à l’algorithme LVQ (Learning Vector Quantisation) de Kohonen. Dans ce cadre la fonctionφest appelée « quantificateur » et dictionnaire ou « codebook ».
Yves Lechevallier
Cours CNAM IS
10
Algorithme de gradient stochastique
On suppose que nous avonsun échantillon de taille infinie.
A la réalisationztnous ne disposons que de l'information connue sur l’échantillon de taillet.
Au lieu de U(φ) calculé sur l’échantillon de taille infinie nous avonsu(φ,t).
Dans ce cas on doit résoudre le problème suivant:
φm∈iΦnU(
Yves Lechevallier
)
min Eu( φ∈Φ
Cours CNAM IS
,t)]
11
