MÉTHODES DE CLASSIFICATION
28
pages
Catalan
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
28
pages
Catalan
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
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 « ...
MÉTHODES
DE
CLASSIFICATION
Pierre-Louis GONZALEZ
Objet Données
MÉTHODES DE CLASSIFICATION
Opérer des regroupements en classes homogènes dun ensemble dindividus.
Les données se présentent en général sous la forme dun tableau individus×variables. 1. Ayant défini un critère de distance (dissemblance) ou dissimilarité (pas nécessairement diné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 densembles 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
Avantageslarbre 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 à laffectation dun individu à une classe (existant a priori) dans le cadre de lanalyse 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=Pn−1,k−1+k Pn−1,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é dalgorithmes pour trouver une bonne partition. Comment définir la qualité dune 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 linertieIWla plus faible (ou linertieIBla 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 dune 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 Linertie intra-classe diminue à chaque étape.
Démonstration: SoitEgi classe obtenue en remplaçant laci pa2ntre d rgi ce e gravité deEci. Daprès le théorème de Konig-Huygens,ginétant pas le centre de gravité deEgi n1 i∑=k1 ⎢⎣⎡A∈∑Eigd2(A,gi)⎥⎦⎤ supérieur à linertie intra-classe de la est itio . part nEgi
10
Il suffit de montrer alors que : k k n1 =∑1 ⎢⎡⎣ ∈∑id2(j, gi) ⎥⎦⎤ ≥ 1n =∑1⎢⎡A∈∑Eigd2(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, lalgorithme converge. Lexpérience montre que le nombre ditérations nécessaires est en général faible.
11
