Hierarchikus csoportosítás

Az informatikai területen , pontosabban az elemzés és az adatok automatikus osztályozása terén a hierarchikus csoportosítás fogalma különböző klaszterezési módszereket takar , és két fő családba sorolható: „alulról felfelé építkező” módszerek és „leszármazottak”.

Hierarchikus csökkenő besorolás

Az úgynevezett "felülről lefelé" módszerek egy általános megoldástól egy specifikusabbig indulnak. Az ebbe a kategóriába tartozó módszerek egyetlen klaszterrel kezdődnek, amelyek mindegyiküket tartalmazzák, majd az egyes szakaszokban egy kritérium szerint felosztják, amíg különböző klaszterek halmazát nem kapják meg.

Növekvő hierarchikus osztályozás (CAH)

Az úgynevezett "felülről lefelé" módszerektől eltérően az emelkedő hierarchikus osztályozást "alulról felfelé" hívják, mert abból a helyzetből indul ki, amikor az összes egyén egyedül van egy osztályban, majd egyre nagyobb osztályokba gyűlik össze. A hierarchikus minősítő abból a tényből származik, hogy létrehoz egy H hierarchiát , az osztálykészletet az algoritmus minden szakaszában, amely ellenőrzi a következő tulajdonságokat:

$\ Omega \ H-ban$ : a hierarchia csúcsán, amikor úgy csoportosulunk, hogy egyetlen osztályt kapjunk, az összes egyén csoportosul;
$\ forall \ omega \ in Omega, \ {\ omega \} \ in H$ : a hierarchia alján minden egyén egyedül van;
$\ forall (h, h ') \ H ^ 2-ben, h \ cap h' = \ emptyyset$ vagy vagy : ha a csoportosítás két osztályát vesszük figyelembe, akkor vagy nincs közös egyénük, vagy az egyik a másikba tartozik. $h \ h részhalmaz$ $h '\ h részhalmaz$

Ez egy automatikus osztályozási módszer, amelyet az adatok elemzésében használnak ; n egyedből álló halmazból az a célja, hogy ezeket az egyéneket bizonyos számú osztályba sorolja. $\Omega$

A módszer azt feltételezi, hogy az egyének között van egy bizonyos mértékű eltérés ; az euklideszi térben elhelyezkedő pontok esetében a távolságot használhatjuk az eltérés mértékeként. Megjegyezzük az x és y egyedek közötti különbséget . $disszim (x, y)$

Algoritmus

Elv

Kezdetben minden egyén osztályt, azaz n osztályt alkot . Megpróbáljuk csökkenteni az órák számát , erre iteratív módon kerül sor. Minden lépésben két osztályt egyesítenek, ezzel csökkentve az osztályok számát. Az egyesítésre kiválasztott két osztály az, amelyik a legközelebb áll, más szóval azokhoz, amelyek közötti eltérés minimális közöttük, ezt az eltérési értéket összesítési indexnek nevezzük . Mivel a legközelebbi egyedeket gyűjtik össze először, az első iterációnak alacsony az aggregációs indexe, de az iterációból az iterációig növekszik. $nb_ {osztályok} <n$

Az osztályok közötti különbségek mérése

Két, egyedet tartalmazó osztály különbségét egyszerűen az egyének közötti különbség határozza meg. $C_1 = \ {x \}, C_2 = \ {y \}$ $disszim (C_1, C_2) = disszim (x, y)$

Ha az osztályoknak több egyén van, akkor több szempont is lehetővé teszi az eltérés kiszámítását. A legegyszerűbbek a következők:

A legkisebb ugrás megtartja a legkisebb távolságot az egyének között és : ; $C_1$ $C_2$ $disszim (C_1, C_2) = \ min_ {x \ a C_1-ban, y \ a C_2-ben (disszim (x, y))$
A legnagyobb ugrás a különbözőség az egyének között és a legtávolabbi: ; $C_1$ $C_2$ $disszim (C_1, C_2) = \ max_ {x \ a C_1-ban, y \ a C_2-ben (disszim (x, y))$
Az átlagos link kiszámításához közötti átlagos távolság az egyének és a : ; $C_1$ $C_2$ $disszim (C_1, C_2) = átlagos_ {x \ a C_1-ban, y \ a C_2-ban (disszim (x, y))$
A Ward távolság célja, hogy maximalizálja inter-osztály tehetetlenség: a és a számok a két osztályt, és azok a súlypontok. $disszim (C_1, C_2) = \ frac {n_1 * n_2} {n_1 + n_2} disszim (G_1, G_2)$ $n_1$ $n_2$ $G_1$ $G_2$

Álkód megvalósítás

Bejegyzés:

egyének: egyének felsorolása
nbClasses: azon osztályok száma, amelyeket végül meg akarunk szerezni

Kilépés:

osztályok: az osztályok kezdetben üresek, az osztály egyének listájaként jelenik meg

Pour i=1 à individus.longueur Faire classes.ajouter(nouvelle classe(individu[i])); Fin Pour Tant Que classes.longueur > nbClasses Faire // Calcul des dissimilarités entre classes dans une matrice triangulaire supérieure matDissim = nouvelle matrice(classes.longueur,classes.longueur); Pour i=1 à classes.longueur Faire Pour j=i+1 à classes.longueur Faire matDissim[i][j] = dissim(classes[i],classes[j]); Fin Pour Fin Pour // Recherche du minimum des dissimilarités Soit (i,j) tel que matDissim[i][j] = min(matDissim[k][l]) avec 1<=k<=classes.longueur et k+1<=l<=classes.longueur; // Fusion de classes[i] et classes[j] Pour tout element dans classes[j] Faire classes[i].ajouter(element); Fin pour supprimer(classes[j]); Fin Tant Que

Dendrogram

A dendrogram egy növekvő hierarchikus osztályozás grafikus ábrázolása; Gyakran bináris faként mutatják be, amelynek levelei az x tengelyre igazított egyedek. Amikor két osztály vagy két egyén találkozik az összesítési indexszel , a két osztály abszcisszájából függőleges vonalak húzódnak az ordinátáig , majd ezeket vízszintes szakasz köti össze. Az összesítési indexből olyan koordináta vonalat rajzolhatunk, amely a dendrogramon osztályozást mutat. A besorolási fa bonyolultabb változatai potenciálisan segíthetnek a döntési fa felépítésében . $\ tau$ $\ tau$ $\ tau$ $\ tau$

Lásd is

Kapcsolódó cikkek

Külső linkek

A vizuális expedíció belül a Linux fájlrendszerek : tanulmány a hasonlóság a fájlrendszerek megvalósított Linux , és például hierarchikus osztályozás szerint növekvő

Bibliográfia

Tézis "kontextualizáció, megjelenítés és értékelés a felügyelet nélküli tanulás" Laurent Candillier (University of Lille 3) 2006/09/15, PDF, 250 oldal.

Megjegyzések és hivatkozások

(in) Székely J. Gábor és Maria L. Rizzo, " Hierarchikus klaszterezés a közös távolságon belüli távolságok között: Ward minimális varianciamódszerének kiterjesztése. ” , Journal of Classification , vol. 22, n o 22005. szeptember, P. 151-183 ( DOI 10.1007 / s00357-005-0012-9 )