MÉTHODES DE CLASSIFICATION

MÉTHODES DE CLASSIFICATION

-

Documents
28 pages
Lire
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description





MÉTHODES
DE
CLASSIFICATION







Pierre-Louis GONZALEZ

MÉTHODES DE CLASSIFICATION




Objet Opérer des regroupements en classes homogènes d’un
ensemble d’individus.



Données Les données se présentent en général sous la forme d’un
tableau individus × variables.

1. Ayant défini un critère de distance (dissemblance) ou
dissimilarité (pas nécessairement d’inégalité triangulaire)
entre les individus, on procède au regroupement des
individus.

2. Ce regroupement nécessite une stratégie de
classification : critère de classification.

2


MÉTHODES




• NON HIERARCHIQUES

Partition en k classes

Exemples : Centres mobiles
Nuées dynamiques


Avantages : Permettent la classification d’ensembles volumineux.


Inconvénients : On impose au départ le nombre de classes.

3




• HIÉRARCHIQUES : suites de partitions emboîtées


a, b, c, d, e
ab, c, d, eOU
abc, de
abcde abcde



Avantages : La lecture de l’arbre permet de déterminer le nombre
optimal de classes.


Inconvénients : Coûteux en temps de calcul.


4



Éléments de vocabulaire


→ classification automatique
→ classification non supervisée
→ apprentissage sans professeur


Le terme « classification » en anglais fait référence à l’affectation d’un
individu à une classe (existant a priori) dans le cadre de l’analyse
discriminante. Il se traduit en français par le terme classement.

L’équivalent en anglais de « ...

Sujets

Informations

Publié par
Nombre de visites sur la page 609
Langue Catalan
Signaler un problème
 
 
 
 
MÉTHODES
DE
CLASSIFICATION 
 
 
 
 
 
 
 
Pierre-Louis GONZALEZ 
    Objet     Données 
 
  MÉTHODES DE CLASSIFICATION
Opérer des regroupements en classes homogènes dun ensemble dindividus.
Les données se présentent en général sous la forme dun tableau individus×variables.  1. Ayant défini un critère de distance (dissemblance) ou dissimilarité (pas nécessairement dinégalité triangulaire) entre les individus, on procède au regroupement des individus.  2. Ce regroupement nécessite une stratégie de classification : critère de classification.  
2
Exemples: Centres mobiles Nuées dynamiques
Avantages: Permettent la classification densembles volumineux.
    NON HIERARCHIQUES          
Partition en k classes
Inconvénients: On impose au départ le nombre de classes.
3
 
   M É T H O D E S
     HIÉRARCHIQUES: suites de partitions emboîtées   
 
 
a b c d e
OU
a, b, c, d, e ab, c, d, e abc, de abcde  
  Avantageslarbre permet de déterminer le nombre: La lecture de optimal de classes.   Inconvénients: Coûteux en temps de calcul.   
4
    Éléments de vocabulaire   classification automatique classification non supervisée apprentissage sans professeur
  Le terme « classification » en anglais fait référence à laffectation dun individu à une classe (existant a priori) dans le cadre de lanalyse discriminante. Il se traduit en français par le terme classement.  Léquivalent en anglais de « classification automatique » est « cluster analysis ».  
 
5
    Éléments de vocabulaire   E : ensemble des n objets à classer   Dissimilarité :      Similarité   
 
:
d(i, j) =d j, i) d(i, i) =0 d(i, j) ≥0
si,j=s,ji
( ) ) s(i, j) ≥0 s(i, i) ≥ js i,) 
6
  I.MÉTHODES DE PARTITIONNEMENT  1. Considérations combinatoires  = individus Pn,knombre de partitions en k classes de n Pn,k=Pn1,k1+k Pn1,krrneec )( éruc (nombre de Stirling de 2èmeespèce) Ex :P12,5=1 379 400   Pn= nombre total de partitions (nombres de Bell) Ex :P12=4 213 597   Nécessité dalgorithmes pour trouver une bonne partition.  Comment définir la qualité dune partition ?  
 
7
 2. Inertie intra-classe et Inertie inter-classe  n points dans un espace euclidien d2(i,i′)distance euclidienne  Soit une partition en k classes de poidsPi  
 
 
g1, g2 ... gk de gravité centres I1, I2 ... Ik inerties associées IW=PiIi inertie intra IB=Pid2(gi,g)inertie inter  IB+I=I = centre de gravité des n individus g  
xx x x x xx x x x x xxxxxx xgxx x1xxxxg2x x x x x g
x xx x x x x x x x x xxgkx xx
8
  Comparaison de deux partitions en k classes: La meilleure est celle qui a linertieIWla plus faible (ou linertieIBla plus forte).  
Remarque: Ce critère ne permet pas de comparer des partitions à nombres différents de classe.   3. Méthode des centres mobiles  
 
x x x x x x x x x x xc1xxx c2 xx x x x x x x x x x x x x x x x x x xc3xx x x x xx   1ère étape: choix de centresci partition associée (les etci sont choisis au hasard). La classeEciest formée de tous les points plus proches deci que de tout autre centre.  
9
 
 2èmeétape: calcul des centres de gravité de chaque classe définition dune nouvelle partition.   
+ itérations  successives
x x x x x x x x x x          2 xg12 x x xg2                x x x x x  x  x x x x xg2  x3  x x x x x x x x   RÉSULTAT FONDAMENTAL Linertie intra-classe diminue à chaque étape.
 
 Démonstration:  SoitEgi classe obtenue en remplaçant laci pa2ntre d rgi ce e gravité deEci. Daprès le théorème de Konig-Huygens,ginétant pas le centre de gravité deEgi n1 i=k1 AEigd2(A,gi) supérieur à linertie intra-classe de la est itio . part nEgi
10
 
   Il suffit de montrer alors que :  k k n1 =1  id2(j, gi)   1n =1AEigd2(A, gi) i j Eci  Or, si on considère un point quelconque, il figurera dans le membre de droite avec son carré de distance augiqui sera le plus proche de lui par construction desEgi, tandis que dans le membre de gauche, il figurera avec sa distance à ungiqui ne sera pas forcément le plus proche de lui, mais qui sera seulement son centre de gravité dans la partitionEc. i  Le nuage étant fini, lalgorithme converge.  Lexpérience montre que le nombre ditérations nécessaires est en général faible.  
11