Grupowanie hierarchiczne
W IT dziedzinie , a dokładniej w dziedzinie analizy i automatycznej klasyfikacji z danymi , pojęcie hierarchiczne grupowanie obejmuje różne grupowania metod i jest podzielone na dwie główne rodziny: Metody „oddolne” i "zstępnych.
Hierarchiczna klasyfikacja malejąca
Tak zwane metody „odgórne” rozpoczynają się od rozwiązania ogólnego do bardziej szczegółowego. Metody w tej kategorii rozpoczynają się od pojedynczego klastra zawierającego je wszystkie, a następnie są dzielone na każdym etapie według kryterium, aż do uzyskania zestawu różnych klastrów.
Rosnąco hierarchiczna klasyfikacja (CAH)
W przeciwieństwie do tak zwanych metod „odgórnych”, rosnąca hierarchiczna klasyfikacja nazywana jest „oddolną”, ponieważ zaczyna się od sytuacji, w której wszystkie jednostki są same w klasie, a następnie gromadzą się w coraz większych klasach. Kwalifikator hierarchiczny bierze się stąd, że tworzy hierarchię H , zbiór klas na wszystkich etapach algorytmu, który weryfikuje następujące właściwości:
-
Ω∈H.{\ displaystyle \ Omega \ in H} : na szczycie hierarchii, kiedy grupujemy się w jedną klasę, wszystkie jednostki są zgrupowane razem;
-
∀ω∈Ω,{ω}∈H.{\ Displaystyle \ forall \ omega \ in \ Omega \ {\ omega \} \ in H} : na dole hierarchii wszystkie jednostki są same;
-
∀(godz,godz′)∈H.2,godz∩godz′=∅{\ displaystyle \ forall (h, h ') \ in H ^ {2}, h \ cap h' = \ emptyset}lub albo : jeśli rozważymy dwie klasy zgrupowania, to albo nie mają one wspólnej jednostki, albo jedna jest zawarta w drugiej.godz⊂godz′{\ displaystyle h \ subset h '}godz′⊂godz{\ displaystyle h '\ podzbiór h}
Jest to automatyczna metoda klasyfikacji stosowana w analizie danych ; z zestawu z n jednostek, jego celem jest rozpowszechnianie tych osób do pewnej liczby klas.
Ω{\ displaystyle \ Omega}
Metoda zakłada, że mamy miarę niepodobieństwa między jednostkami; w przypadku punktów znajdujących się w przestrzeni euklidesowej jako miary odmienności możemy posłużyć się odległością . Zostanie odnotowana odmienność między osobami x i y .
rejassjam(x,y){\ Displaystyle dissim (x, y)}
Algorytm
Zasada
Początkowo każda osoba tworzy klasę, tj. N klas. Staramy się zredukować liczbę klas do , odbywa się to iteracyjnie. Na każdym kroku łączone są dwie klasy, zmniejszając w ten sposób liczbę klas. Dwie klasy wybrane do połączenia to te, które są najbliższe, innymi słowy te, których podobieństwo między nimi jest minimalne, ta wartość niepodobieństwa nazywana jest indeksem agregacji . Ponieważ najbliższe osobniki są zbierane jako pierwsze, pierwsza iteracja ma niski wskaźnik agregacji, ale będzie rosła od iteracji do iteracji.
niebvslwssmis<nie{\ displaystyle nb_ {klasy} <n}
Pomiary niepodobieństwa międzyklasowego
Niepodobieństwo dwóch klas, z których każda zawiera osobę, jest definiowane po prostu przez odmienność między jej jednostkami.VS1={x},VS2={y}{\ Displaystyle C_ {1} = \ {x \}, C_ {2} = \ {y \}}rejassjam(VS1,VS2)=rejassjam(x,y){\ Displaystyle dissim (C_ {1}, C_ {2}) = dissim (x, y)}
Gdy klasy mają kilka osób, istnieje wiele kryteriów, które pozwalają obliczyć niepodobieństwo. Najprostsze są następujące:
- Minimalny skok zachowuje minimalne odległości między jednostkami i : ;VS1{\ displaystyle C_ {1}}VS2{\ displaystyle C_ {2}}rejassjam(VS1,VS2)=minx∈VS1,y∈VS2(rejassjam(x,y)){\ Displaystyle dissim (C_ {1}, C_ {2}) = \ min _ {x \ w C_ {1}, y \ w C_ {2}} (dissim (x, y))}
- Maksymalny skok jest odmienność między jednostkami i najdalej: ;VS1{\ displaystyle C_ {1}}VS2{\ displaystyle C_ {2}}rejassjam(VS1,VS2)=maxx∈VS1,y∈VS2(rejassjam(x,y)){\ Displaystyle dissim (C_ {1}, C_ {2}) = \ max _ {x \ w C_ {1}, y \ w C_ {2}} (dissim (x, y))}
- Przeciętny link jest obliczyć średnią odległość między jednostkami i : ;VS1{\ displaystyle C_ {1}}VS2{\ displaystyle C_ {2}}rejassjam(VS1,VS2)=moyminieniemix∈VS1,y∈VS2(rejassjam(x,y)){\ Displaystyle dissim (C_ {1}, C_ {2}) = średnia_ {x \ w C_ {1}, y \ w C_ {2}} (dissim (x, y))}
- W odległości Ward ma na celu maksymalizację inter klasy zamachowego: z i numery dwóch klas, a ich odpowiednie środki ciężkości.rejassjam(VS1,VS2)=nie1∗nie2nie1+nie2rejassjam(sol1,sol2){\ Displaystyle dissim (C_ {1}, C_ {2}) = {\ Frac {n_ {1} * n_ {2}} {n_ {1} + n_ {2}}} dissim (G_ {1}, G_ {2})}nie1{\ displaystyle n_ {1}}nie2{\ displaystyle n_ {2}}sol1{\ displaystyle G_ {1}}sol2{\ displaystyle G_ {2}}
Implementacja pseudokodu
Wpisy:
- osoby: lista osób
- nbClasses: liczba klas, które ostatecznie chcemy uzyskać
Wyjście :
- klasy: lista klas początkowo pusta, klasa jest traktowana jako lista osób
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
Dendrogram jest graficznym przedstawieniem wznoszącego klasyfikacją hierarchiczną; Często jest przedstawiane jako drzewo binarne, którego liście są osobnikami wyrównanymi na osi X. Kiedy dwie klasy lub dwie osoby spotykają się ze wskaźnikiem agregacji , pionowe linie są rysowane od odciętych dwóch klas do rzędnej , a następnie są połączone poziomym odcinkiem. Z indeksu agregacji możemy narysować linię rzędnych, która przedstawia klasyfikację na dendrogramie.
Bardziej złożone wersje drzewa klasyfikacyjnego mogą potencjalnie pomóc w tworzeniu drzewa decyzyjnego .
τ{\ displaystyle \ tau}τ{\ displaystyle \ tau}τ{\ displaystyle \ tau}τ{\ displaystyle \ tau}
Zobacz też
Powiązane artykuły
Linki zewnętrzne
Bibliografia
Uwagi i odniesienia
-
(w) Gabor Székely J. i Maria L. Rizzo, „ Hierarchical clustering via Joint Between-Within Distances: Extending Ward's Minimum Variance Method. ” , Journal of Classification , t. 22 N O 2Wrzesień 2005, s. 151-183 ( DOI 10.1007 / s00357-005-0012-9 )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">