Universite de Nice SV1 annee Departement de Mathematiques Mathematiques pour la Biologie semestre

Description

Niveau: Supérieur
Universite de Nice SV1, annee 2009-2010 Departement de Mathematiques Mathematiques pour la Biologie (semestre 2) Cours 8 : Classification automatique de donnees par la methode des centres mobiles. Comme l'algorithme de classification hierarchique ascendante, l'algorithme des centres mobiles (K- mean clustering en anglais) est un outils de “fouille de donnees”(data mining). La fouille de donnees joue un role important dans presque tous les domaines scientifiques, du marketing qui l'a fait naıtre1, a la genetique en passant par l'informatique (reconnaissance de forme) ou la linguistique. 1 L'algorithme des centres mobiles : L'objectif de la methode est de partitionner en differentes classes des individus pour lesquels on dispose de mesures. On represente les individus comme des points de l'espace ayant pour coordonnees ces mesures. On cherche a regrouper autant que possible les individus les plus semblables (du point de vue des mesures que l'on possede) tout en separant les classes le mieux possible les unes des autres. Ici encore (comme dans le cas de la classification hierarchique ascendante) on choisit de proceder de fac¸on automatique, c'est-a-dire qu'on ne cherche pas a utiliser l'expertise que l'on aurait des individus pour trouver des regroupements avec ce que l'on connait les concernant mais plutot un moyen de faire apparaıtre, uniquement a partir des mesures, des ressemblances et des differences a priori peu visibles.

• methode des centres mobiles


• nuage


• nuage de point


• somme ponderee


• somme ponderee des carres des distances


• exploration de donnees


• classification automatique de donnees par la methode des centres mobiles

Sujets

• Moyenne pondérée
• Exploration de données

Informations

• Publié par: chaeh
• Nombre de lectures: 40
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

Universit´edeNice D´epartementdeMath´ematiques

SV1,ann´ee2009-2010 Math´ematiquespourlaBiologie(semestre2)

Cours8:Classificationautomatiquededonn´ees parlame´thodedescentresmobiles.

Commel’algorithmedeclassificationhi´erarchiqueascendante,l’algorithmedescentresmobiles(K- mean clusteringnelgna)sia(iulldedeno´nee”sestunoutilsde“fodata miningedelliuosee´nnodjoueaf.L) 1 unrˆoleimportantdanspresquetouslesdomainesscientifiques,dumarketingquil’afaitnaˆıtre,`ala g´ene´tiqueenpassantparl’informatique(reconnaissancedeforme)oulalinguistique.

1 L’algorithmedes centres mobiles : L’objectifdelame´thodeestdepartitionnerendiff´erentesclassesdesindividuspourlesquelson disposedemesures.Onrepr´esentelesindividuscommedespointsdel’espaceayantpourcoordonn´ees cesmesures.Oncherchea`regrouperautantquepossiblelesindividuslesplussemblables(dupointde vuedesmesuresquel’onposs`ede)toutense´parantlesclasseslemieuxpossiblelesunesdesautres. Iciencore(commedanslecasdelaclassificationhi´erarchiqueascendante)onchoisitdeproc´ederde fa¸conautomatiqueqsu`’aountnielcih-e`ar-cdhierpeareict,ees’utqseslre’pxtdaiines’oelurnaividsud pour trouver des regroupements avec ce que l’on connait les concernant mais plutot un moyen defaire apparaˆıtreteedcnsee´erdsffi`aprncespeuviori.selbisi,uniquemenpa`titrasedrusems,resrdeseeslamb Cetteid´ee,travaillerautomatiquement,a`l’aidedel’ordinateureten aveugleee,etspaep´lapprentissage nonsupervise´.

Lame´thodedescentresmobiless’appliquelorsquel’onsaita`l’avancecombiendeclassesonveut obtenir. Appelonskce nombre de classes. L’algorithme est le suivant : 0 0 Etape 0 :Pour initialiser l’algorithme, on tire au hasardkapalt`anenrtpaap,noitalupodisudnviiC,C, 1 2 0 ...,C: ce sont leskcentresrateelqux.aunoOne´muetordni’neciiinitffie´eldscsneertnetl’tressantexpo k indique qu’il s’agit deskcentres initiaux. On choisit aussi une distance entre individus. Onvaensuiter´epe´terungrandnombredefoislesdeuxe´tapessuivantes: 0 00 Etape 1 : Constitution de classes :dusenesindivimesndelbitrae’ltOnepr´k, ,classes Γen..., Γ 1 2 k 0 regroupant autour de chaque centreCpouri= 1, . . . , nl’ensemble des individus qui sont plus proches i 0 0 du centreCque des autres centresCpourj6=i(au sens de la distance choisie). i j Etape 2 : Calcul des nouveaux centres :seednerttie´rgvaeterOnd´lescmineG 1 ,G 2 , .... ,G k des 1 1 ktscommelecespoindne´isngneeuesotsecxuertnonseaevusessalctboisniaC=G 1 ,C=G 2 , .... , 1 2 1 C=G k k Re´pe´titiondes´etapes1et2:’`quasalbitasalinoit’ledoglahtirme,c’est-ussjpeta´euxdeescete`pe´rno `a-direjusqu’a`cequeled´ecoupageenclassesobtenunesoit(presque)plusmodifie´paruneite´ration suple´mentaire. Lesch´emaci-dessousillustrelam´ethode(a`noterqu’enpratique,biensur,onnefaitpascescalculs “a`lamain”maisa`l’aided’unlogicield’analysededonne´es).Danscettefigureladistancechoisieest ladistanceeuclidienne:eneffet,pourr´epartirlespointsdunuageendeuxgroupes,ceuxquisontles 0 0 plus proches d’un pointCet ceux qui sont les plus proches d’un autre pointCau sens de la distance 1 2 0 0 euclidienne,ilsuffitdetracerlam´ediatricedusegment[C ,C]. 1 2 Maisest-onsuˆrquecetalgorithmeconduitbiena`unepartitionmeilleureque celle dont on est parti, c’est-a`-direcellequie´taitissuedutirageale´atoireinitialdekntrecenope`erdoP?s´rruties,onetacqute ilfaudraitpr´ecisercequel’onentendparmeilleure. Nous allons pour cela introduire la notion d’inertie d’un nuage de points.

1 Selonw.ki//rftt:phsee´nnodednoitarloxp/Eeg.oiaedipiremonte`a1956sec,telaogirhtemuqeebrntiareved´cune`le mettanten´evidencepourlesmagasinsWal-Martunlienentrel’achatdecouchespourb´ebe´setl’achatdebie`reslesamedi apr`esmidi.L’analysedesre´sultatsd’uneclassificationautomatiquepermitdecomprendrequ’ils’agissaitdemessieurs envoye´sparleurscompagneschercherdescouches,jug´eestropvolumineuses,etquis’offraientalorsdespacksdebie`re.On r´eorganisalesrayonsdesmagasinsendisposantcouchesetpacksdebie`rea`proximite´etlesventesdebi`eres’envol`erent.

1