Klastrowanie hierarchiczne — Hierarchical clustering

W eksploracji danych i statystyk , hierarchiczne grupowanie (zwany również hierarchiczna analiza skupień lub HCA ) jest metodą analizy skupień , które chce zbudować hierarchię klastrów. Strategie hierarchicznego grupowania generalnie dzielą się na dwa typy:

  • Aglomeratów materiałem : To jest „ oddolne podejście”: każdy zaczyna obserwacji w swoim klastrze i pary klastrów są scalane jako jeden porusza się w górę hierarchii.
  • Podział : jest to podejście „z góry na dół ”: wszystkie obserwacje zaczynają się w jednym klastrze, a podziały są wykonywane rekurencyjnie w miarę przesuwania się w dół hierarchii.

Generalnie fuzje i podziały są określane w sposób zachłanny . Wyniki hierarchicznego grupowania są zwykle przedstawiane w dendrogramie .

Standardowy algorytm hierarchicznego aglomeratów materiałem klastrów (HAC) ma złożoność czasową z i wymaga pamięci, co czyni go zbyt powolne dla zbiorów danych nawet średnich. Jednak w niektórych szczególnych przypadkach znane są optymalnie wydajne metody aglomeracyjne (o złożoności ): SLINK dla pojedynczego połączenia i CLINK dla pełnego łączenia w klastry . Dzięki stercie czas wykonywania ogólnego przypadku może zostać skrócony do , co jest ulepszeniem w stosunku do wspomnianej granicy , kosztem dalszego zwiększania wymagań dotyczących pamięci. W wielu przypadkach koszty pamięci związane z tym podejściem są zbyt duże, aby było praktycznie użyteczne.

Z wyjątkiem szczególnego przypadku pojedynczego wiązania, żaden z algorytmów (z wyjątkiem wyszukiwania wyczerpującego w ) nie może zagwarantować znalezienia optymalnego rozwiązania.

Grupowanie z podziałem z wyczerpującym wyszukiwaniem to , ale często używa się szybszej heurystyki do wybierania podziałów, takich jak k -średnie .

Odmienność klastrów

W celu podjęcia decyzji, które skupienia należy połączyć (w przypadku aglomeracji) lub gdzie klaster należy podzielić (w przypadku podziału), wymagana jest miara niepodobieństwa między zestawami obserwacji. W większości metod grupowania hierarchicznego osiąga się to poprzez zastosowanie odpowiedniej metryki (miara odległości między parami obserwacji) oraz kryterium powiązania, które określa odmienność zbiorów w funkcji odległości par obserwacji w zbiorach.

Metryczny

Wybór odpowiedniej metryki wpłynie na kształt klastrów, ponieważ niektóre elementy mogą być stosunkowo bliższe sobie w ramach jednej metryki niż innej. Na przykład, w dwóch wymiarach, pod metryką odległości Manhattan, odległość między początkiem (0,0) i (0,5, 0,5) jest taka sama jak odległość między początkiem a (0, 1), natomiast pod odległością euklidesową metryka ta ostatnia jest zdecydowanie większa.

Niektóre powszechnie używane metryki do hierarchicznego grupowania to:

Nazwy Formuła
Odległość euklidesowa
Kwadrat odległości euklidesowej
Odległość od Manhattanu (lub bloku miejskiego)
Maksymalna odległość (lub odległość Czebyszewa)
Odległość Mahalanobisa gdzie S jest macierzą kowariancji

W przypadku danych tekstowych lub innych danych nienumerycznych często używane są metryki, takie jak odległość Hamminga lub odległość Levenshteina .

Odległości euklidesowe i Manhattan są szczególnymi przypadkami uogólnionej odległości Minkowskiego z p = 1 (dla Manhattanu) i p = 2 (dla euklidesowego).

Istnieje kilka innych miar rozbieżności. W szczególności odległości korelacji - odległości korelacji Pearsona, Eisena, Spearmana, Kendalla, które są szeroko stosowane do analizy danych dotyczących ekspresji genów. Odległość oparta na korelacji jest definiowana przez odjęcie współczynnika korelacji od 1. Mówiąc ściśle, odległości oparte na korelacji nie mogą być używane jako metryka, podczas gdy pierwiastek kwadratowy z nich może być.

Przegląd analizy skupień w badaniach psychologii zdrowia wykazał, że najczęstszą miarą odległości w opublikowanych badaniach w tym obszarze badawczym jest odległość euklidesowa lub kwadrat odległości euklidesowej.

Kryteria powiązania

Kryterium powiązania określa odległość między zestawami obserwacji jako funkcję odległości parami między obserwacjami.

Niektóre powszechnie stosowane kryteria powiązania między dwoma zestawami obserwacji A i B to:

Nazwy Formuła
Grupowanie z maksymalnym lub pełnym powiązaniem
Grupowanie minimalne lub z jednym powiązaniem
Nieważone grupowanie średnich powiązań (lub UPGMA )
Średnie ważone grupowanie powiązań (lub WPGMA )
Grupowanie powiązań centroid lub UPGMC gdzie i są centroidami odpowiednio klastrów s i t .
Minimalne klastrowanie energii

gdzie d jest wybraną metryką. Inne kryteria powiązania obejmują:

  • Suma wszystkich wariancji wewnątrz klastra.
  • Wzrost wariancji dla scalanego klastra ( kryterium Warda ).
  • Prawdopodobieństwo, że klastry kandydujące odradzają się z tej samej funkcji rozkładu (powiązanie V).
  • Iloczyn stopnia wejściowego i zewnętrznego na wykresie k-najbliższego sąsiedztwa (powiązanie stopni wykresu).
  • Przyrost pewnego deskryptora klastra (tj. ilości zdefiniowanej do pomiaru jakości klastra) po połączeniu dwóch klastrów.

Dyskusja

Grupowanie hierarchiczne ma tę wyraźną zaletę, że można użyć dowolnej prawidłowej miary odległości. W rzeczywistości same obserwacje nie są wymagane: stosuje się jedynie macierz odległości.

Przykład grupowania aglomeracyjnego

Surowe dane

Załóżmy na przykład, że te dane mają być grupowane, a odległość euklidesowa jest metryką odległości .

Hierarchiczny dendrogram grupowania wyglądałby następująco:

Tradycyjna reprezentacja

Wycięcie drzewa na danej wysokości zapewni grupowanie partycjonowania z wybraną precyzją. W tym przykładzie cięcie za drugim rzędem (od góry) dendrogramu da klastry {a} {bc} {de} {f}. Cięcie po trzecim rzędzie da skupienia {a} {bc} {def}, co jest grubszym skupieniem, z mniejszą liczbą, ale większymi skupiskami.

Ta metoda buduje hierarchię z poszczególnych elementów poprzez stopniowe łączenie klastrów. W naszym przykładzie mamy sześć elementów {a} {b} {c} {d} {e} i {f}. Pierwszym krokiem jest określenie, które elementy połączyć w klaster. Zazwyczaj chcemy wziąć dwa najbliższe elementy, zgodnie z wybraną odległością.

Opcjonalnie na tym etapie można również skonstruować macierz odległości , gdzie liczba w i-tym wierszu j- tej kolumnie jest odległością między i-tym i j-tym elementem. Następnie, w miarę postępu grupowania, wiersze i kolumny są scalane w miarę łączenia klastrów i aktualizowania odległości. Jest to powszechny sposób implementacji tego typu klastrowania i ma tę zaletę, że odległości między klastrami są buforowane. Prosty algorytm grupowania aglomeracyjnego jest opisany na stronie grupowania z jednym wiązaniem ; można go łatwo dostosować do różnych typów połączeń (patrz poniżej).

Załóżmy, że połączyliśmy dwa najbliższe elementy b i c , mamy teraz następujące klastry { a }, { b , c }, { d }, { e } i { f } i chcemy je dalej scalić. Aby to zrobić, musimy wziąć odległość między {a} i {bc}, a zatem zdefiniować odległość między dwoma skupieniami. Zwykle odległość między dwoma skupiskami i jest jedną z następujących:

  • Średnia odległość między elementami każdego klastra (zwana także przeciętnym klastrowaniem linków, używana np. w UPGMA ):
  • Suma wszystkich wariancji wewnątrz klastra.
  • Wzrost wariancji dla scalanego klastra ( metoda Warda )
  • Prawdopodobieństwo, że klastry kandydujące odradzają się z tej samej funkcji rozkładu (powiązanie V).

W przypadku związanych minimalnych odległości para jest wybierana losowo, dzięki czemu jest w stanie wygenerować kilka strukturalnie różnych dendrogramów. Alternatywnie, wszystkie powiązane pary mogą zostać połączone w tym samym czasie, tworząc unikalny dendrogram.

Zawsze można zdecydować się na zaprzestanie klastrowania, gdy liczba klastrów jest wystarczająco mała (kryterium liczby). Niektóre powiązania mogą również gwarantować, że aglomeracja występuje w większej odległości między klastrami niż aglomeracja poprzednia, a następnie można zaprzestać klastrowania, gdy klastry są zbyt daleko od siebie, aby można je było połączyć (kryterium odległości). Nie dotyczy to jednak np. połączenia środka ciężkości, gdzie mogą wystąpić tzw. odwrócenia (inwersje, odstępstwa od ultrametrii).

Grupowanie dzielące

Podstawowa zasada grupowania z podziałem została opublikowana jako algorytm DIANA (DIvisive ANAlysis Clustering). Początkowo wszystkie dane znajdują się w tym samym klastrze, a największy klaster jest dzielony, dopóki każdy obiekt nie zostanie oddzielony. Ponieważ istnieją sposoby dzielenia każdego klastra, potrzebna jest heurystyka. DIANA wybiera obiekt o maksymalnej średniej odmienności, a następnie przenosi do tej gromady wszystkie obiekty, które są bardziej podobne do nowej gromady niż do pozostałych.

Oprogramowanie

Implementacje open source

Grupowanie hierarchiczne dendrogram na zbiorze Iris (przy użyciu R ). Źródło
Klastrowanie hierarchiczne i interaktywna wizualizacja dendrogramów w pakiecie Data Mining Orange .
  • ALGLIB implementuje kilka hierarchicznych algorytmów klastrowania (pojedyncze łącze, pełne łącze, Ward) w C++ i C# z pamięcią O(n²) i czasem wykonywania O(n³).
  • ELKI zawiera wiele hierarchicznych algorytmów grupowania, różne strategie powiązań, a także wydajne algorytmy SLINK, CLINK i Anderberg, elastyczne wyodrębnianie klastrów z dendrogramów i różne inne algorytmy analizy klastrów .
  • Octave , odpowiednik GNU do MATLAB, implementuje hierarchiczne grupowanie w funkcji „linkage”.
  • Orange , pakiet oprogramowania do eksploracji danych, obejmuje hierarchiczne grupowanie z interaktywną wizualizacją dendrogramów.
  • R ma wiele pakietów, które udostępniają funkcje do hierarchicznego klastrowania.
  • SciPy implementuje hierarchiczne klastrowanie w Pythonie, w tym wydajny algorytm SLINK.
  • scikit-learn implementuje również hierarchiczne grupowanie w Pythonie.
  • Weka zawiera hierarchiczną analizę skupień.

Realizacje komercyjne

  • MATLAB zawiera hierarchiczną analizę skupień.
  • SAS zawiera hierarchiczną analizę skupień w PROC CLUSTER.
  • Mathematica zawiera pakiet hierarchicznego klastrowania.
  • NCSS zawiera hierarchiczną analizę skupień.
  • SPSS zawiera hierarchiczną analizę skupień.
  • Qlucore Omics Explorer zawiera hierarchiczną analizę skupień.
  • Stata zawiera hierarchiczną analizę skupień.
  • CrimeStat zawiera hierarchiczny algorytm klastrowy najbliższego sąsiada z graficznymi danymi wyjściowymi dla systemu informacji geograficznej.

Zobacz też

Bibliografia

Dalsza lektura