MÉTHODES DE CLASSIFICATION

Pierre-Louis

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

• Classe préparatoire ENS Cachan D1
• Centre de masse d'une plaque homogène
• D'une ombre à l'autre
• Polynôme de Hurwitz
• Moment quadratique
• Partie civile en France

Informations

• Publié par: Allu
• Nombre de lectures: 612
• Langue: Catalan

Extrait

 

 

 

 

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 • P n,k nombre de partitions en k classes de n P n,k =P n−1,k−1 +k   P n−1,k rrneec )( éruc (nombre de Stirling de 2 ème espèce) Ex :P 12,5 =1   379   400       • P n = nombre total de partitions (nombres de Bell) Ex :P 12 =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 d 2 ( i,i ′) distance euclidienne   Soit une partition en k classes de poidsP i    

 

 

g 1 , g 2  ... g k  de gravité centres I 1 ,   I 2   ...   I k  inerties associées I W = ∑ P i I i   inertie intra I B = ∑ P i d 2 ( g i ,g ) inertie inter   I B +I=I  = centre de gravité des n individus g  

x x x x  x x x x x  x  x x x x x x x x g x x x 1 x x x x g 2 x x x x x g

x x x x x  x  x x x x x x x g k x x x

8

    Comparaison de deux partitions en k classes: La meilleure est celle qui a linertieI W la plus faible (ou linertieI B la 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 x c 1 x x x c 2 x x x x x x x  x x x x x x x  x x x  x  x x c 3 x x x x  x x x     1ère étape: choix de centresc i  partition associée (les etc i  sont choisis au hasard). La classeE c i est formée de tous les points plus proches dec i   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 x g 1 2 x x x g 2                 x x x x x  x  x x x x x g 2  x 3  x x x x x x  x x     RÉSULTAT FONDAMENTAL Linertie intra-classe diminue à chaque étape.

 

  Démonstration:   SoitE g i  classe obtenue en remplaçant lac i  pa 2 ntre d rg i  ce e gravité deE c i . Daprès le théorème de Konig-Huygens,g i nétant pas le centre de gravité deE g i   n 1   i ∑ = k 1   ⎢ ⎣ ⎡ A∈ ∑ E i g d 2 ( A,g i ) ⎥ ⎦ ⎤  supérieur à linertie intra-classe de la est itio . part nE g i

10

 

      Il suffit de montrer alors que :   k k n 1   = ∑ 1   ⎢ ⎡ ⎣   ∈ ∑ i d 2 ( j, g i )   ⎥ ⎦ ⎤   ≥   1 n   = ∑ 1 ⎢ ⎡ A∈ ∑ E i g d 2 ( A, g i ) ⎤ ⎦ ⎥   i j E c i   Or, si on considère un point quelconque, il figurera dans le membre de droite avec son carré de distance aug i qui sera le plus proche de lui par construction desE g i , tandis que dans le membre de gauche, il figurera avec sa distance à ung i qui ne sera pas forcément le plus proche de lui, mais qui sera seulement son centre de gravité dans la partitionE c . 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