Classification par blocs sous l'approche modéle de mélange

icon

60

pages

icon

Français

icon

Documents

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

icon

60

pages

icon

Français

icon

Documents

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

1
Classiflcation par blocs sous l’approche modele de m¶elange
Mohamed Nadif (a) and G¶erard Govaert (b)
(a)CRIP5, Universit¶e Paris Descartes
(b) HEUDIASYC, UMR CNRS 6599, Universit¶e de Technologie de Compiegne
08 mars 2007 2
Histoire de la Classiflcation
o Apprentissage non supervis¶e : classiflcation automatique
o La classiflcation automatique ofire une vue simplifl¶ee d’un ensemble de donn¶ees en
le structurant en classes homogenes
o Outil indispensable dans la fouille de donn¶ees
o D¶emarche naturelle et ancienne
Aristote : classiflcations en logique et en politique
Linn¶e en 1763 : classiflcation complete des ^etres vivants
Darwin 1859 : interpr¶etation de l’¶evolution des especes
Apres 1960 : apparition des algorithmes automatisant la construction des classes 3
Objectifs de la Classiflcation
o Donn¶ees
jSoit x=(x ) la matrice des donn¶ees de taille r£si
i2I l’ensemble des r lignes (individus, objets, instances)
j2J l’ensemble des s colonnes (variables, attributs)
I Premier objectif : classiflcation simple
R¶esumer l’information en utilisant des classes d’individus "homogenes"a l’aide
d’une partition sur l’ensemble I
I Second objectif : classiflcation crois¶ee
R¶esumer l’information en utilisant des blocs homogenes a l’aide d’une paire de
partitions d¶eflnies sur l’ensemble I et l’ensemble J 4
Exemple : Donn¶ees binaires
o I =fA;B;C;D;E;F;G;H;I;Jg et J =f1;2;3;4;5;6;7g
o Classiflcation simple : (fA;C;Hg;fB;F;Gg;fD;G;I;Eg)
o Classiflcation crois¶ee :
{ classes en ligne (fA;C;Hg ...
Voir icon arrow

Publié par

Nombre de lectures

69

Langue

Français

Classicationparblocssouslapprochemod`eledem´elange
MohamedNadif(a)andG´erardGovaert(b)
(a)CRIP5,Universite´ParisDescartes
(b)HEUDIASYC,UMRCNRS6599,Universit´edeTechnologiedeCompi`egne
08 mars 2007
1
Histoire de la Classification
sivrc:e´ssalacitienagssonenpesutionautomatiqueprAp
aLlcsaisctaoianpmiseuvedee´iliqatomutunreouenee´sesembunendonnlede lestructurantenclasseshomoge`nes
ilutdiinOdonn´eesouillededenalsfapsneaslb
ennienctaeellerutanehcrame´D
Aristote: classifications en logique et en politique
e´Linncoonticaedetl`mpserteˆsestnaviv7136nessic:al
Darwinluvoontisede`espsec1859:interrpe´atitnoedle´
2
`rpA91sea:06laogdnsetioippramesrithautomatisantla construction des classes
Objectifs de la Classification
oDsenne´ Soitx= (xjitailledeciodsee´nnedsela)trmar×s iIl’ensemble desrlignes (individus, objets, instances)
jJl’ensemble desscolonnes (variables, attributs)
IPremier objectif: classification simple R´esumerlinformationenutilisantdesclassesdindividushomog`enesa`laide d’uneapionrtitsur l’ensembleI
ISecond objectifticaissla:cee´siorcno R´erlinformationenutilisantdesblocshomog`enesa`laidedunepaire de esum partitionsein´drleessublensemIet l’ensembleJ
3
6},{
4
)5,3,2}7,
Classicationcrois´ee: – classes en ligne – classes en colonne
Classification simple :({A, C, H},{B, F, G},{D, G, I, E})
et
Exemple:Donn´eesbinaires
G,I,E}){(,1}4{,A,({,D{,}G,F,B{,}H,C7}6,5,{=J}J,,4,3,2,1,B,C,D,E,F,G,H,I=IA{
Me´thodeshi´erarchiques
aeBuocusedp´ccupoesdeuronsdeen´eer´´eodemllaietsdArbres
IL’algorithme CAH – Chaque point est dans sa propre classe Achaqueite´ration,onagglom`erelesclasseslesplusprochesausensdune distancead`irn´e Onre´pe`teceprocessusjusqua`obteniruneseuleclasse IPblrome`estgirm´hegeationetcompiloedxxictu´ierd`etlreadlegoarch:
5
Me´thodesdePartionnement
elliaT´nnodsedeeegsardntionnemedesdepar´Mteohtn
Recherche d’une partition enkclasses
6
partredenombe:leix´tlpe´Cmoeedblemnsneudselbissopsnoitinindividus eng classes
1g g!kX0(1)k1×µgk×kr = Parexemple,ilexiste611501partitionspossiblesde12individusr´epartisen4 classes.
idPelicrPmeNebo`l
Plusieurs algorithmes (voir l’ouvrage de J.P Nakache et J. Confais)
IgoalthrimeLk-means (Forgy 1965) Partitionet`erucriiondsitanimimPi,kzikd2(xi,gk) – Etape Affectation : assignation des points aux classes EtapeRepre´sentation:recherchedescentresdesclassesgk
Extension:me´thodedesnu´eesdynamiques(Diday1971)
7
Plan de la partie I
ClassicationsimpleetApprochem´elange
udoM`dle´treeˆstngeedem´elaIn
ApprochesimationEst(ML) etssiacitCalon(CML)
Algorithmes de type EM
8
IsnoitatoN
Partition dezdeIengclasses
(z1, . . . ,zr)
ziindique la classe dei,
zik si= 1zi=ketzik sinon= 0
Exemple :I={i1, i2, i3, i4, i5},n= 5 etg= 3
P artition= ({i5},{i2},{i1, i3, i4})
(z1, . . . ,z5) = (3,2,3,3,1) ou
i130 0 1 i220 1 0 i330 0 1 i430 0 1 i511 0 0
psnoitatonsemeˆMionrtitnepaouruwdeJenmclasses
9
I
Notations
Donn´eesx= (x1, . . . ,xr)rvecteurs deR
s
Lorsquezest connu, (x,z) sont lesdon ´ nees
Proble`me:trouverzapa`edritrx
compl´et´ees
10
IInt´ ˆt ere s
ClassicationetApprocheme´lange
enG´ra´eelrustnessimitpoundioatert`rinctnelelemhtdomse´assiesclrepoques metrique : ´ krlsuriecbantess´treneire`tide-meW(ra)dosnaesCtHA Commentjustierlutilisationdececrite`re?
Evolution des approcheslha.og.rueoe´g.mvers une approche probabiliste
ocheLparpm´elangepermssecealeled´eidndiootanmrofedtelresila
toiredebleal´eavenuairatnaddsed´inenepatisnsiosontidus´ealdesrdnvielis densit´ef
fseutmnsseeclauqahca`serporpset´sienededngla´e
ubdaolmittnie´iieed``dnlleantioAtte
11
Voir icon more
Alternate Text