Méthodes neuronales en classification non supervisée

Lecheval

Description

CNAM IS 2009-2010
Méthodes neuronales en
classification non
supervisée
Yves Lechevallier
INR
I
A-Rocquencourt
E_mail : [e-mail]
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 ...

Sujets

• Partition héraldique
• D'une ombre à l'autre
• Méthodes quantitatives
• Taux actuariel
• Ijimaia
• Réseau de neurones artificiel

Informations

• Publié par: Thoek
• Nombre de lectures: 74
• Langue: English

Extrait

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 classes K     N      K   !  solutions possibles.

Yves Lechevallier

Cours CNAM IS

2

Problème d’optimisation

Soit un critèreU, défini de K    (    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 ℘ K i ( n E) 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 arg j= m 1, i L, n K 2 ( 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 p U a n rt e i   t f i o o n n c    t   i   o F    Φ n        d    ’    a   f F   f   1   e ,    c   L t    a ,   t   i   F   o   K   n   }    φ      l’ ed  de D n ioatnt  ecaved ecapsesérpe } r d   snC {=,1 e ad

F j = { 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,w j )

k M 1, i K n d(z,w k =

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 ⎡ ⎢ z 1 z j z p ⎥ ⎥ ⎥ 1 des lignes Z= [ z, = L,z i ,L,z K N ] ⎡ = ⎢ ⎣ ⎢ = ⎢ z g g z i k 1 N z z g g i j k j j j N z z g g p p k i p p N ⎤ ⎥ ⎦ 1 1 1 d’un tableau 1 G [ g 1 ,K,g ] ⎢ ⎢ g K g j K g p K ⎦ ⎥ ⎣ 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éalisationz t nous 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