Chapitre 2 Clustring

Upgrade to remove ads
Upgrade to remove ads
Unformatted text preview:

CHAPITRE 2 Clustering 2 1 k means Principe page 3 Homog n it des dimensions page 6 Am liorations de l initialisation page 7 K means page 7 K means page 7 Estimation de probabilit s page 8 S lection du nombre de classes page 9 Crit re de qualit page 9 Maxima de la fonction densit page 10 D croissance du nombre de classes page 11 Extension des nu es dynamiques page 13 Classes elliptiques page 13 Rival Penalized Competitive Learning RPCL page 14 RPCL based local PCA page 16 Frequency Sensitive Competitive Learning FSCL page 17 Bibliographie page 18 D nomination fran aise algorithme des centres mobiles 2 1 1 Principe Les centres mobiles ou nu es dynamiques sont un algorithme de classi cation non supervis e A partir d un ensemble de points il d termine pour un nombre de classes x une r partition des points qui minimise un crit re appel inertie ou variance intra classe Algorithme A1 centre mobile k means On consid re un ensemble de points Xi 1 i P cid 31 RN cid 35 P 3 Machine Learning Statistiques et Programmation Version 0 1 407 A chaque point est associ e une classe ci 1 i P 1 C P On d nit les barycentres des classes Gi 1 i C cid 31 RN cid 35 C Initialisation L initialisation consiste choisir pour chaque point une classe al atoirement dans 1 C On pose t 0 Calcul des barycentres I t cid 26 P t t 1 i 1 d2 cid 37 Xi Gt i cid 40 ct for k in 1 C Gt k cid 26 P i 1 Xi 1 ct i k cid 26 P i 1 1 ct i k Calcul de l inertie if t 0 et It It 1 arr t de l algorithme Attribution des classes for in 1 P ct 1 i arg min o d Xi Gt d Xi Gt k k k est la distance entre Xi et Gt k Retour l tape du calcul des barycentres jusqu convergence de l inertie I t Th or me T1 convergence des k means Quelque soit l initialisation choisie la suite It t 0 construite par l algorithme des k means page 3 converge La d monstration du th or me n cessite le lemme suivant Lemme L1 inertie minimum Soit X1 XP cid 31 RN cid 35 P P points de RN le minimum de la quantit Q cid 31 Y RN cid 35 Q Y d2 Xi Y 2 1 P cid 11 i 1 i 1 Xi le barycentre des points X1 XP 1 est atteint pour Y G P cid 26 P Soit X1 XP cid 31 RN cid 35 P P cid 11 i 1 P points de RN GXi 0 P cid 11 i 1 d2 Xi Y d2 Xi G P d2 G Y P cid 11 i 1 arg min Y RN d2 Xi Y G P cid 11 i 1 4 Chapitre 2 Clustering Machine Learning Statistiques et Programmation Version 0 1 407 On peut maintenant d montrer le th or me L tape d attribution des classes consiste attribuer chaque point le barycentre le plus proche On d nit Jt par On en d duit que J t 1 ct 1 d2 cid 37 Xi Gt i cid 40 P cid 11 i 1 i cid 40 J t 1 cid 11 i ct d2 cid 37 Xi Gt d2 cid 37 Xi Gt i cid 40 cid 11 i ct i ct 1 ct 1 ct i i i cid 40 ct 1 d2 cid 37 Xi Gt i cid 40 ct i ct 1 d2 cid 37 Xi Gt i cid 6 ct 1 i J t 1 cid 11 i ct cid 11 i ct J t 1 J t 1 I t i cid 6 ct 1 i 2 2 2 3 2 4 2 5 Le lemme pr c dent appliqu chacune des classes 1 C permet d af rmer que I t 1 la suite It t 0 est d croissante et minor e par 0 elle est donc convergente L algorithme des centres mobiles cherche attribuer chaque point de l ensemble une classe parmi les C disponibles La solution trouv e d pend de l initialisation et n est pas forc ment celle qui minimise l inertie intra classe l inertie nale est un minimum local N anmoins elle assure que la partition est form e de classes convexes soit c1 et c2 deux classes diff rentes on note C1 et C2 les enveloppes convexes des points qui constituent ces deux classes alors o C2 La gure suivante pr sente un exemple d utilisation de l algorithme des centres mobiles Des points C1 sont g n r s al atoirement dans le plan et r partis en quatre groupes J t 1 Par cons quent o 2 1 k means 5 Machine Learning Statistiques et Programmation Version 0 1 407 C est une application des centres mobiles avec une classi cation en quatre classes d un ensemble al atoire de points plus dense sur la partie droite du graphe Les quatre classes ainsi form es sont convexes Homog n it des dimensions Les coordonn es des points Xi RN sont g n ralement non homog nes les ordres de grandeurs de chaque dimension sont diff rents C est pourquoi il est conseill de centrer et normaliser chaque dimension On note i 1 P Xi Xi 1 Xi N Les points centr s et normalis s sont 1 P Xi k gk EX k P cid 11 i 1 vkk cid 37 E X EX 2 cid 40 kk i cid 49 xi 1 g1 v11 i 1 P X cid 20 k cid 31 EX 2 cid 35 kk g2 vN N cid 3 xi N gN 6 Chapitre 2 Clustering Machine Learning Statistiques et Programmation Version 0 1 407 L algorithme des centres mobiles est appliqu sur l ensemble X cid 20 i 1 i P Il est possible ensuite de d corr ler les va riables ou d utiliser une distance dite de Malahanobis 2 d nie par dM X Y X M Y cid 20 o Y cid 20 d signe la transpos e de Y et M est une matrice sym trique d nie positive Dans le cas de variables corr l es la matrice M 1 o 1 est la matrice de variance covariance des variables al atoires Xi i 2 1 2 Am liorations de l initialisation K means L article Arthur2007 page montre que l initialisation al atoire n est pas ef cace et est sensible aux outliers ou points aberrants L tape d initialisation est remplac e par la suivante Algorithme A2 initialisation k means Cette tape d initialisation viendra remplacer celle d nie dans l algorithme k means page 3 On consid re un en semble de points X Xi 1 i P cid 31 RN cid 35 P A chaque point est associ e une classe ci 1 i P 1 C P Pour k centres …


View Full Document
Download Chapitre 2 Clustring
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Chapitre 2 Clustring and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Chapitre 2 Clustring 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?